¿Encontrar la coincidencia más cercana para los nombres de ciudades mal escritos?

podría usar una función de damerau-levenstein para obtener la distancia de cuerda entre dos cuerdas. (Esto también verifica la transposición)

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

Si sus tablas son grandes, es posible que deba optimizar un poco el algoritmo para romper una vez que la distancia de la cadena exceda un umbral.

Además, si puede suponer que la primera letra de la ciudad está escrita correctamente, eso debería reducir el número de comparaciones.

No es PHP, pero si es de alguna ayuda, aquí hay una versión de Java que escribí:

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