Найти наиболее подходящий для названия города с ошибкой?

Question

У меня есть список городов, в которых есть множество неправильных написаний для одного и того же города. Один город написан с ошибкой 18 раз! Я пытаюсь это убрать, но это занимает несколько часов. Есть ли какой-нибудь алгоритм, который мог бы «угадать» действительное название города для каждого из них с ошибками? Некоторая форма взвешивания? Данные в MySQL, и у меня есть таблица правильного написания, с которой можно сравнивать.

Есть идеи по этому поводу? Пример PHP поможет, если это возможно.

Answer 1

вы можете использовать функцию 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;
    }
}

Answer 2

1. Читайте о расстоянии Левенштейна: http://en.wikipedia.org/wiki/Levenshtein_distance.

2. Найдите реализацию или напишите свою собственную. Это не так сложно.

3. Используйте его для поиска орфографических ошибок, близких к мисс.

Answer 3

Как говорит печально известный " Баритни Спирс ", и, как большинство из нас знает из опыта, Google благодаря своему сканированию довольно неплохо справляется с правильной проверкой орфографии популярных имен. Город - это то, что он обычно хорошо исправляет. Таким образом, вы можете попытаться написать функцию PHP, которая анализирует поисковую страницу Googlse, чтобы увидеть, какое исправление предлагает Google, или, что более сложно (поскольку страница более сложная), вы можете даже попытаться проанализировать параметры, предоставленные вам Google Maps.