La distancia física entre dos lugares

Question

Necesito medir la distancia física entre dos lugares cuyos nombres se proporcionan en forma de cadenas. Ya que a veces los nombres se escriben de forma ligeramente diferente, que estaba buscando una biblioteca que me podría ayudar a medir la diferencia y luego combino con una medida de la latitud y longitud para seleccionar las correspondencias correctas. idiomas preferidos: Java o PHP.

¿Alguna sugerencia?

Answer 1

Tener un vistazo a la distancia Levenshtein . Esta es una forma de medir cuán diferente dos cadenas son el uno del otro.

Con suerte he entendido bien su pregunta; el uso de "distancia" en la misma frase como "latitud y longitud" podría ser confuso!

Answer 2

Aunque escrito en C (con Python y TCL fijaciones), libdistance sería una herramienta para aplicar varias métricas distancias en secuencias / datos.

Las métricas incluye:

• floración
• Damerau
• euclid
• Hamming
• Jaccard
• levenshtein
• manhattan
• minkowski
• needleman_wunsch

Answer 3

Es posible obtener algunos resultados decentes usando un algoritmo de para encontrar nombres ligeramente misspelld.

Además, si se utiliza una distancia de edición más mecánico, es probable que vea mejores resultados utilizando una función ponderada que tiene en cuenta la geometría del teclado (es decir, físicamente cerca teclas son "más barato" de reemplazar que lejos unos). Eso es un método patentado por cierto, así que ten cuidado de no escribir algo que se vuelve demasiado popular;)

Answer 4

Me tomé la libertad de traducir un pedazo de código C # que he escrito para calcular la distancia Levenshtein en código Java. Se utiliza sólo dos matrices de una sola dimensión que se alternan en lugar de una gran matriz escalonada:

public static int getDifference(String a, String b)
{
    // Minimize the amount of storage needed:
    if (a.length() > b.length())
    {
        // Swap:
        String x = a;
        a = b;
        b = x;
    }

    // Store only two rows of the matrix, instead of a big one
    int[] mat1 = new int[a.length() + 1];
    int[] mat2 = new int[a.length() + 1];

    int i;
    int j;

    for (i = 1; i <= a.length(); i++)
        mat1[i] = i;

    mat2[0] = 1;

    for (j = 1; j <= b.length(); j++)
    {
        for (i = 1; i <= a.length(); i++)
        {
            int c = (a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1);

            mat2[i] =
                Math.min(mat1[i - 1] + c,
                Math.min(mat1[i] + 1, mat2[i - 1] + 1));
        }

        // Swap:
        int[] x = mat1;
        mat1 = mat2;
        mat2 = x;

        mat2[0] = mat1[0] + 1;
    }

    // It's row #1 because we swap rows at the end of each outer loop,
    // as we are to return the last number on the lowest row
    return mat1[a.length()];
}

No se prueba rigurosamente, pero parece estar funcionando bien. Se basa en una implementación de Python que hice para un ejercicio universitario. Esperamos que esto ayude!

Answer 5

Yo recomendaría o Levenshtein Distancia o la Jaccard Distancia para comparar el texto.

Answer 6

SumMetrics en Java, pero no tienen usado.