Vindt u de beste match voor verkeerd gespelde stadsnamen?

je zou een damerau-levenstein-functie kunnen gebruiken om de snaarafstand tussen twee snaren te krijgen. (Dit controleert ook op transpositie)

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

Als je tabellen groot zijn, moet je de algo misschien een beetje optimaliseren om te breken zodra de stringafstand een drempel overschrijdt.

Ook als je ervan uit kunt gaan dat de eerste letter van de stad correct is getypt, zou dat het aantal vergelijkingen moeten verminderen.

Het is geen PHP, maar als het van enige hulp is, hier is een Java-versie die ik schreef:

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;
    }
}