5

我有一个城市列表,其中同一城市有许多不正确的拼写。一个城市拼错了18次!我正在尝试清理它,但它需要几个小时。是否有一些算法可以“猜测”每个拼写错误的有效城市名称?某种形式的加权?数据在 MySQL 中,我也有一个正确拼写的表来比较。

对此有什么想法吗?如果可能的话,一个 PHP 示例会有所帮助。

4

3 回答 3

4

您可以使用 damerau-levenstein 函数来获取两个字符串之间的字符串距离。(这也检查换位)

http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance

如果您的表很大,那么一旦字符串距离超过阈值,您可能需要稍微优化算法以破坏。

此外,如果您可以假设城市的第一个字母输入正确,那么应该减少比较次数。

它不是 PHP,但如果它有任何帮助,我写了一个 java 版本:

class LevinshteinDistance{
    public static void main(String args[]){
        if(args.length != 2){
            System.out.println("Displays the Levenshtein distance between 2 strings");
            System.out.println("Usage: LevenshteinDistance stringA stringB");
        }else{
            int distance = getLevenshteinDistance(args[0], args[1]);
            System.out.print(getLevenshteinMatrix(args[0], args[1]));
            System.out.println("Distance: "+distance);
        }
    }   

    /**
     * @param a first string for comparison
     * @param b second string for comparison
     * @param caseSensitive whether or not to use case sensitive matching
     * @return a levenshtein string distance
     */  
    public static int getLevenshteinDistance(String a, String b, boolean caseSensitive){
        if(! caseSensitive){
        a = a.toUpperCase();
        b = b.toUpperCase();
        }
        int[][] matrix = generateLevenshteinMatrix(a, b);
        return matrix[a.length()][b.length()];
    }

    /**
     * @param a first string for comparison
     * @param b second string for comparison
     * @return a case sensitive levenshtein string distance
     */  
    public static int getLevenshteinDistance(String a, String b){
        int[][] matrix = generateLevenshteinMatrix(a, b);
        return matrix[a.length()][b.length()];
    }

    /**
     * @param a first string for comparison
     * @param b second string for comparison
     * @return a  case sensitive string representation of the search matrix
     */  
    public static String getLevenshteinMatrix(String a, String b){
        int[][] matrix = generateLevenshteinMatrix(a, b);
        StringBuilder result = new StringBuilder();
        final int ROWS = a.length()+1;
        final int COLS = b.length()+1;

        result.append(rowSeperator(COLS-1, false));
        result.append("|    "+b+" |\n");
        result.append(rowSeperator(COLS-1, true));  

        for(int r=0; r<ROWS; r++){
            result.append('|');
            if(r > 0){
                result.append(a.charAt(r-1));
            }else{
                result.append(' ');
            }
            result.append(" |");
            for(int c=0; c<COLS; c++){
                result.append(matrix[r][c]);
            }
            result.append(" |\n");
        }       
        result.append(rowSeperator(COLS-1, false));
        return result.toString();   
    }   


    private static String rowSeperator(final int LEN, boolean hasGap){
        StringBuilder result = new StringBuilder();
        if(hasGap){
            result.append("+  +-");
        }else{
            result.append("+----");
        }
        for(int i=0; i<LEN; i++) 
            result.append('-');
        result.append("-+\n");
        return result.toString();
    }

    private static int[][] generateLevenshteinMatrix(String a, String b){
        final int ROWS = a.length()+1;
        final int COLS = b.length()+1;
        int matrix[][] = new int[ROWS][COLS];

        for(int r=0; r<ROWS; r++){
            matrix[r][0]=r;
        }
        for(int c=0; c<COLS; c++){ 
            matrix[0][c]=c;
        }

        for(int r=1; r<ROWS; r++){
            char cA = a.charAt(r-1);
            for(int c=1; c<COLS; c++){
                    char cB = b.charAt(c-1);
                int cost = (cA == cB)?0:1;

                int deletion =  matrix[r-1][c]+1; 
                int insertion = matrix[r][c-1]+1;
                int substitution = matrix[r-1][c-1]+cost;
                int minimum = Math.min(Math.min(deletion, insertion), substitution);    

                if( (r > 1 && c > 1) && a.charAt(r-2) == cB && cA == b.charAt(c-2) ){
                    int transposition = matrix[r-2][c-2]+cost;
                    minimum = Math.min(minimum, transposition);
                }
                matrix[r][c] = minimum;
            }
        }   
        return matrix;
    }
}
于 2010-08-18T18:19:16.157 回答
2
  1. 阅读 Levenshtein 距离:http ://en.wikipedia.org/wiki/Levenshtein_distance 。

  2. 查找实现或编写自己的实现。没那么复杂。

  3. 使用它来定位几乎未命中的拼写错误。

于 2010-08-18T18:16:38.780 回答
1

正如臭名昭著的“ Bariteney Spears ”所暗示的那样,正如我们大多数人从经验中所知道的那样,谷歌通过它的爬行,已经非常擅长正确地检查流行名称的拼写。城市是它通常可以很好地纠正的事情。因此,您可能会尝试编写一个解析 Google 搜索页面的 PHP 函数,以查看 Google 建议的更正,或者更复杂(因为页面更复杂),您甚至可以尝试解析 Google 地图提供给您的选项。

于 2010-08-19T01:45:52.030 回答