Distancia física entre dos lugares

Question

Necesito medir la distancia física entre dos lugares cuyos nombres se proporcionan como cadenas. Dado que a veces los nombres se escriben de forma ligeramente diferente, estaba buscando una biblioteca que pudiera ayudarme a medir la diferencia y luego combinarla con una medida de la latitud y la longitud para seleccionar las coincidencias correctas. Lenguas preferidas: Java o PHP.

¿Alguna sugerencia?

Answer 1

Eche un vistazo a Levenshtein distance. Esta es una forma de medir cuán diferentes son dos cadenas entre sí.

Afortunadamente entendí su pregunta correctamente; ¡Usar "distancia" en la misma oración que "latitud y longitud" podría ser confuso!

Answer 2

Aunque escrito en c (con enlaces python y tcl), libdistance sería una herramienta para aplicar varias medidas de distancias en cadenas/datos.

métricas incluyen:

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

Answer 3

encontré SumMetrics en Java, pero no lo he utilizado.

Answer 4

Me tomé la libertad de traducir una parte del código de C# que he escrito para calcular la distancia de Levenshtein en el código de Java. Utiliza sólo dos matrices unidimensionales 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 basó en una implementación de Python que hice para un ejercicio universitario. ¡Espero que esto ayude!

Answer 5

Puede obtener algunos resultados decentes usando un phonetic algorithm para encontrar nombres ligeramente deletreados. También, si usa una distancia de edición más mecánica, probablemente verá mejores resultados utilizando una función ponderada que tenga en cuenta la geometría del teclado (es decir, las teclas físicamente cerradas son más "baratas" de reemplazar que las lejanas). Es un método patentado por cierto, así que tenga cuidado de no escribir algo que se vuelva demasiado popular;)

Answer 6

Recomendaría Levenshtein Distance o Jaccard Distance para comparar texto.