Fizyczna odległość między dwoma miejscami

Question

Potrzebuję zmierzyć fizyczną odległość między dwoma miejscami, których nazwy są podane jako ciągi. Ponieważ czasami nazwy pisane są nieco inaczej, szukałem biblioteki, która pomogłaby mi zmierzyć różnicę, a następnie połączyć ją z miarą szerokości i długości geograficznej, aby wybrać poprawne dopasowania. Preferowane języki: Java lub PHP.

Wszelkie sugestie?

Answer 1

Spójrz na Levenshtein distance. Jest to sposób mierzenia różnic między dwoma strunami.

Mam nadzieję, że dobrze zrozumiałem twoje pytanie; użycie "odległości" w tym samym zdaniu, co "szerokość i długość geograficzna" może być mylące!

Answer 2

Chociaż napisany w c (z powiązaniami Pythona i TCL), libdistance byłby narzędziem do stosowania kilku metryk odległości na łańcuchach/danych.

dane obecne:

• drzewa
• damerau
• Euclid
• Hamminga
• Jaccard
• Levenshteina
• Manhattan
• Minkowski
• needleman_wunsch

Answer 3

znalazłem SumMetrics w Javie, ale nie zostały wykorzystane.

Answer 4

Pozwoliłem sobie przetłumaczyć fragment kodu C#, który napisałem, aby obliczyć odległość Levenshteina do kodu Java. Używa tylko dwie tablice pojedynczy wymiar, że alternatywną zamiast dużego postrzępionych tablicy:

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

To nie jest rygorystycznie testowane, ale wydaje się działać dobrze. Oparto go na implementacji Pythona, którą wykonałem dla ćwiczenia uniwersyteckiego. Mam nadzieję że to pomoże!

Answer 5

Możesz uzyskać przyzwoite wyniki, używając nazwy phonetic algorithm, aby znaleźć nazwy nieznacznie błędne.

Ponadto, jeśli używasz bardziej mechanicznej odległości edycyjnej, prawdopodobnie zobaczysz lepsze wyniki przy użyciu funkcji ważonej, która uwzględnia geometrię klawiatury (tzn. Fizycznie zamykane klawisze są "tańsze" do zastąpienia niż odległe). To opatentowana metoda, więc uważaj, aby nie napisać czegoś, co staje się zbyt popularne;)

Answer 6

Polecam albo Levenshtein Distance lub Jaccard Distance dla porównywania tekstu.