Którą strukturę danych należy użyć do geokodowania?

Question

Próbuję utworzyć skrypt w języku Python, który przyjmie adres jako dane wejściowe i wypisze jego szerokość i długość geograficzną lub szerokości i długości w przypadku wielu dopasowań, podobnie jak Nominatim.

Tak, to możliwe wejścia i wyjścia mogą być: -

1. w: Nowym Jorku, USA => Out: New York (łac: x1 lon: y1)
2. W : New York => Out: New York (łac: x1 lon: y1)
3. w: Pearl Street, Nowy Jork, USA => Out: Pearl Street (łac: x2 lon: y2)
4. w: Pearl Street, USA => Out: Pearl Street (łac: x2 lon: y2), Pearl Street (łac: x3 lon: y3)
5. w: Pearl Street => Out: Pearl Street (łac: x2 lon: y2), Pearl Street (łac: x3 lon: y3)
6. w: 103 Alkazam, Nowy Jork, USA => Out: Nowy Jork (lat: x1 dług: y1)

W 6 powyżej, Nowy Jork został zwrócony, ponieważ nie znaleziono żadnego miejsca o adresie 103 Alkazam, New York, USA, ale mógł przynajmniej znaleźć New York, USA.

Początkowo myślałem o stworzeniu drzewa reprezentującego relację hierarchiczną, w której rodzeństwo jest sortowane alfabetycznie. Mogło być tak: -

         GLOBAL 
             | 
        --------------------------------------------- 
        |   | ... 
        USA 
      --------------- 
      |  | ... 
     CALIFORNIA NEW YORK 
      |   | 
    ----------- ------------- 
    |  |.. |   |.... 
PEARL STREET  PEARL STREET 

Ale problem był użytkownik może dostarczyć niepełny adres jak w 2, 4 i 5.

Więc następny myśli używając drzewa wyszukiwania i przechowywać w pełni kwalifikowana adres w każdym węźle. Ale to też jest bardzo złe, ponieważ: -

• Spowoduje to przechowywanie wysoce nadmiarowych danych w każdym węźle. Ponieważ będzie to naprawdę duże dane, więc ochrona przestrzeni ma znaczenie.
• Nie będzie w stanie wykorzystać faktu, że użytkownik zawęził obszar wyszukiwania.

Mam jedno dodatkowe wymaganie . Muszę wykryć błędy pisowni. Sądzę, że trzeba będzie traktować je jako osobny problem i traktować każdy węzeł jako generyczne łańcuchy.

Aktualizacja 1

Trochę opracowanie. Dane wejściowe byłyby listą, w której pozycja na niższym indeksie jest elementem nadrzędnym elementu o wyższym indeksie; i oczywiście mogą, ale nie muszą być bezpośrednim rodzicem lub dzieckiem. Tak więc dla zapytania 1 dane wejściowe to ["USA", "NEW YORK"]. Tak więc idealnie jest, że USA, New York nie zwraca wyniku.

Użytkownik powinien mieć możliwość zlokalizowania budynku, jeśli ma on adres, a nasze dane są tak szczegółowe.

Update 2 (Pominięcie Case)

Jeśli użytkownik pyta Pearl Street, USA, więc nasz algo powinien być w stanie zlokalizować adres ponieważ wie Pearl Street ma New York Jako rodzic i USA jest jego rodzicem.

Update 3 (nadwyżka Case)

Załóżmy zapytań użytkowników dla 101 C, Alley A, Pearl Street, New York. Załóżmy również, że nasze dane znają 101 C, ale nie o Alley A. Zgodnie z nim 101 C jest bezpośrednim dzieckiem Pearl Street. Nawet w tym przypadku powinno być możliwe zlokalizowanie adresu.

Answer 1

Dzięki wszystkim za swoje odpowiedzi, ich odpowiedzi były pomocne, ale nie odniósł wszystko, co potrzebne. W końcu znalazłem podejście, które zajmowało się wszystkimi moimi przypadkami. Podejście to jest zmodyfikowaną wersją tego, co zasugerowałem w pytaniu.

podstawowe podejście

Tutaj będę odnosić się do czegoś, co nazywa „węzeł”, jest to obiekt klasy, która będzie zawierać geo informacji, takich jak szerokości miejscem jednostki, długości, może wymiar zbyt, a jego pełny adres.

Jeśli adres podmiotu to "101 C, Pearl Street, Nowy Jork, USA", oznacza to, że nasza struktura danych będzie miała co najmniej cztery węzły dla - '101 C', 'Pearl Street', 'New York "i" USA ". Każdy węzeł będzie miał część name i jedną address. Dla "101 C", name będzie "101 C", a adresem będzie "Pearl Street, Nowy Jork, USA".

Podstawową ideą jest posiadanie drzewa wyszukiwania tych węzłów, gdzie węzeł name będzie używany jako klucz do wyszukiwania. Możemy uzyskać wiele dopasowań, więc później musimy uszeregować wyniki na podstawie tego, jak dobrze węzeł address pasuje do zapytanego.

        EARTH 
             | 
       --------------------------------------------- 
       |           | 
       USA          INDIA 
       |           | 
     ---------------------------      WEST BENGAL 
     |       |       | 
    NEW YORK     CALIFORNIA     KOLKATA 
     |       |       | 
    ---------------   PEARL STREET    BARA BAZAR 
    |    |           | 
PEARL STREET TIME SQUARE         101 C 
    |    | 
    101 C   101 C 

Załóżmy, że mamy dane geograficzne jak powyżej.Szukanie "101 C, NEW YORK" spowoduje nie tylko zwrócenie węzłów "101 C" w "NEW YORK", ale również w "INDIA". Dzieje się tak, ponieważ algo użyje tutaj tylko name, tj. "101 C" do przeszukiwania węzłów. Później możemy ocenić jakość wyniku, mierząc różnicę węzła od address z adresu zapytania. Nie używamy ścisłego dopasowania, ponieważ użytkownik może podać niekompletny adres, tak jak w tym przypadku.

Klasyfikację Wynik wyszukiwania

do stopnia jakość wyniku możemy wykorzystać Longest Common Subsequence. Przypadki "pomijanie" i "nadwyżka" są w tym przypadku dobrze zadbane.

Najlepiej, jeśli pozwolę kodowi mówić. Poniżej znajduje się implementacja Pythona dostosowana do tego celu.

def _lcs_diff_cent(s1, s2): 
    """ 
    Calculates Longest Common Subsequence Count Difference in percentage between two strings or lists. 

    LCS reference: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem. 
    Returns an integer from 0-100. 0 means that `s1` and `s2` have 0% difference, i.e. they are same. 
    """ 
    m = len(s1) 
    n = len(s2) 

    if s1 == s2: 
     return 0 
    if m == 0: # When user given query is empty then that is like '*'' (match all) 
     return 0 
    if n == 0: 
     return 100 

    matrix = [[0] * (n + 1)] * (m + 1) 
    for i in range(1, m+1): 
     for j in range(1, n+1): 
      if s1[i-1] == s2[j-1]: 
       matrix[i][j] = matrix[i-1][j-1] + 1 
      else: 
       matrix[i][j] = max(matrix[i][j-1], matrix[i-1][j]) 

    return int((1 - float(matrix[m][n])/m) * 100) 

Zoptymalizowany Podejście

I wyskoczył na powyższym podejściem (podstawowej), ponieważ zmuszony redundancję, a to nie może wyciąć wykorzystać fakt, że jeśli użytkownik dostarczył „USA” w swoim zapytaniu Następnie musimy nie zaglądaj do węzłów w "INDIA".

To zoptymalizowane podejście w pewnym stopniu rozwiązuje oba powyższe problemy. Rozwiązaniem nie jest jedno duże drzewo wyszukiwania. Możemy podzielić przestrzeń wyszukiwania na "USA" i "INDIA". Później możemy dalej podzielić te przestrzenie wyszukiwania pod kątem stanu. To właśnie nazywam "krojeniem".

Na poniższym diagramie - SearchSlice reprezentuje "plaster", a SearchPool reprezentuje drzewo wyszukiwania.

      SearchSlice() 
            | 
      --------------------------------------------- 
      |           | 
     SearchSlice(USA)       SearchSlice(INDIA) 
      |           | 
    ---------------------------     SearchPool(WEST BENGAL) 
    |       |     | 
SearchPool(NEW YORK)  SearchPool(CALIFORNIA) |- KOLKATA 
    |       |     |- BARA BAZAR, KOLKATA 
    |- PEARL STREET   |- PEARL STREET  |- 101 C, BARA BAZAR, KOLKATA 
    |- TIME SQUARE 
    |- 101 C, PEARL STREET 
    |- 101 C, TIME SQUARE 

kilku kluczowych punktów, aby zauważyć powyżej ...

• Każdy plaster jest tylko jeden poziom głębokości. Cóż, nie jest to tak naprawdę widoczne powyżej.
• Nazwa plasterkowanego poziomu nie pojawia się w adresach jego dzieci. Na przykład SearchSlice(USA) utrzymuje kawałek stanów w "USA". Węzły oznaczone jako "NEW YORK" nie zawierają nazwy "NEW YORK" ani "USA" w ich address. To samo dotyczy innych regionów. Relacja hierarchii niejawnie definiuje pełny adres.
• '101 C' address zawiera także kod rodzica name, ponieważ nie są one krojone.

Skalowanie Możliwości

Gdzie jest wiadro (basen), istnieje możliwość skalowania niejawny. Podzielmy dane geograficzne dla "USA" na dwie grupy. Oba mogą być na różnych systemach. Jest więc całkiem dobrze, jeśli pulę "NEW YORk" jest w systemie A, ale pula "CALIFORNIA" jest w systemie B, ponieważ nie udostępniają żadnych danych, z wyjątkiem oczywiście rodziców.

Tutaj jest zastrzeżenie. Musimy zduplikować rodziców, którzy zawsze będą kawałkiem. Ponieważ liczba plasterków ma być ograniczona, więc hierarchia nie będzie zbyt głęboka, więc nie powinna być zbyteczna, aby je powielić.

Kodeks Pracy

Proszę odnieść się do mojego GitHub na working demo Python code.

Answer 2

Co powiesz na temat korzystania z mapy przechowywania klucz-wartość i wyszukiwania pełnotekstowego.

• klucz do lokalizacji ciąg
• wart location_level i łac & danych Lon.
• wyszukiwanie:
  • rozłamu wprowadzania danych przez użytkownika ciąg pojedynczych lokalizacjach słów (nie tylko przecinkiem)
  • wyszukiwać każdy słowa mapie
  • zwróci łac & lon poziomu najmniejszy lokalizacji

python.dict, memcached, mongodb .... spotka się z twoją potrzebą.

• jeśli u mieć zbyt wiele słów, lokalizacja, Split location_level jako nową mapę, dwie wyszukiwania przyspieszy
• zapomnieć poziomu lokalizacji, traet jak pełnotekstowego wyszukiwania
• ogromne danych? Klawisz skrótu do krótkiego łańcucha lub numerów

niektóre questiongs do rozważenia:

• sposobu przechowywania danych w bazie
• jak init drzewo Wyszukiwanie z danymi, jeśli w ogóle
• jak przedłużyć/edytować drzewo wyszukiwania w środowisku wykonawczym
• fault-tolerant dla wejścia/przechowywania
• przestrzeń dyskowa> prędkość? lub prędkość> miejsce do przechowywania?

więc, bardziej użytkowej sprawdzian dla danych wejściowych użytkownika

101 C, Time Square, New York, US 
101 C, Pearl street, New York, US 

101 C, Time Square, SomeCity, Mars 
101 C 
101 C, US 
101 C, New York, US 

101 C, New York, Time Square, US 

North Door, 101 C, Time Square, New York, US 
South Door, 101 C, Time Square, New York, US 

dla sytuacji:

• szybkie łącze z ogromnym-danych;
• pełna odporność na uszkodzenia;
• łatwe dostosowanie do przechowywania i wykonywania

najlepszym rozwiązaniem (również kompleks est)

• płaski klucz-wartość mapa przechowywania
• pełny wyszukiwania
  • lub klawisz skrótu z wyszukiwaniem w drzewie B:

Twój program/witryna może działać tak szybko, jak Google.

Answer 3

Jeśli spróbujesz utworzyć strukturę danych dla tego problemu, myślę, że będziesz mieć nadmiarowość danych. Zamiast tego możesz użyć drzewa/wykresu & spróbuj zaimplementować algorytm wyszukiwania, który wyszukuje słowa z danych wejściowych użytkownika względem wartości węzłów. Fuzzy dopasowanie może pomóc w wygenerowaniu najbardziej prawdopodobnych wyników, a Ty możesz zasugerować/pokazać użytkownikowi kilka z nich w zależności od poziomu ufności ich podobieństwa.

Można również dbać o literówki itp