A distância física entre dois lugares

Question

Eu preciso para medir a distância física entre dois lugares cujos nomes são fornecidos como strings. Já que às vezes os nomes são escritos de forma ligeiramente diferente, eu estava procurando uma biblioteca que poderia me ajudar a medir a diferença e, em seguida, combiná-lo com uma medida da latitude e longitude para selecionar as combinações corretas. Línguas preferidas:. Java ou PHP

Todas as sugestões?

Answer 1

Tenha um olhar para o Levenshtein distância . Esta é uma forma de medir o quão diferente duas cordas são um do outro.

Espero que eu entendi sua pergunta corretamente; usando "distância" na mesma frase como "latitude e longitude" poderia ser confuso!

Answer 2

Apesar de escrito em c (com python e ligações TCL), libdistance seria uma ferramenta para a aplicação de várias métricas distâncias em cordas / dados.

Metrics incluído:

• flor
• Damerau
• euclid
• Hamming
• Jaccard
• levenshtein
• manhattan
• minkowski
• needleman_wunsch

Answer 3

Você pode obter alguns resultados decentes usando um fonética algoritmo para encontrar nomes ligeiramente misspelld.

Além disso, se você usar uma distância de edição mais mecânica, você provavelmente vai ver melhores resultados usando uma função ponderada que representa a geometria do teclado (ou seja fisicamente chaves próximos são "mais barato" para substituir do que longe uns). Isso é um método patenteado btw, por isso, não ser cuidado para escrever algo que se torna demasiado popular;)

Answer 4

Tomei a liberdade de traduzir um pedaço de código C # Eu tenho escrito para calcular a distância Levenshtein em código Java. Ele utiliza apenas duas matrizes de dimensão única que se alternam em vez de uma matriz denteada grande:

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

Não é rigorosamente testado, mas parece estar funcionando bem. Foi baseado em uma implementação de Python eu fiz para um exercício universidade. Espero que isso ajude!

Answer 5

Gostaria de recomendar ou Levenshtein Distância ou o Jaccard Distância para comparar texto.

Answer 6

SumMetrics em Java, mas não têm -lo usado.