La distance physique entre deux lieux

Question

Je dois mesurer la distance physique entre deux lieux dont les noms sont fournis sous forme de chaînes. Étant donné que parfois les noms sont écrits de façon légèrement différente, je cherchais une bibliothèque qui pourrait me aider à mesurer la différence et le combiner avec une mesure de la latitude et la longitude pour sélectionner les matchs corrects. Langues préférées: Java ou PHP.

Toutes les suggestions?

Answer 1

Jetez un oeil à la Levenshtein . Ceci est un moyen de mesurer différents deux chaînes sont les uns des autres.

Si tout va bien je comprends bien votre question; en utilisant la « distance » dans la même phrase que pourrait être source de confusion!

« latitude et longitude »

Answer 2

Bien écrit en C (avec des liaisons de python et Tcl), libdistance serait un outil pour appliquer plusieurs distances métriques sur les chaînes / données.

Metrics inclus:

• fleurs
• Damerau
• Euclide
• Hamming
• Jaccard
• levenshtein
• manhattan
• Minkowski
• needleman_wunsch

Answer 3

Vous pouvez obtenir des résultats décents en utilisant un pour trouver des noms légèrement misspelld.

En outre, si vous utilisez une plus grande distance de montage mécanique, vous verrez probablement de meilleurs résultats en utilisant une fonction pondérée qui tient compte de la géométrie du clavier (à savoir les touches sont physiquement proches « moins cher » pour remplacer de loin ceux). C'est une méthode brevetée BTW, donc attention à ne pas écrire quelque chose qui devient trop populaire;)

Answer 4

Je pris la liberté de traduire un morceau de code C # Je l'ai écrit pour calculer la distance Levenshtein en code Java. Il utilise deux tableaux une seule dimension qui alternent au lieu d'un grand tableau en dents de scie:

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()];
}

Il est pas rigoureusement testé, mais il semble fonctionner bien. Il était basé sur une implémentation de Python j'ai fait pour un exercice universitaire. Espérons que cela aide!

Answer 5

Je recommande soit Levenshtein ou Jaccard Distance pour comparer le texte.

Answer 6

J'ai trouvé SumMetrics en Java, mais pas utilisé.