Какую структуру данных следует использовать для геокодирования?

Я пытаюсь создать скрипт Python, который будет принимать адрес в качестве входных данных и выдавать его широту и долготу или широту и долготу в случае множественных совпадений, совсем как Nominatim .

Таким образом, возможные входы и выходы могут быть:-

1. In:New York, USA => Out:New York (lat:x1 lon:y1)
2. В:Нью-Йорк => Выход:Нью-Йорк (широта:x1 lon:y1)
3. Въезд:Перл-стрит, Нью-Йорк, США => Выход:Перл-стрит (широта:x2 долгота:y2)
4. В:Перл-стрит, США => Выход:Перл-стрит (широта:x2 долгота:y2), Pearl Street (широта:x3 lon:y3)
5. In:Pearl Street => Out:Pearl Street (широта:x2 lon:y2), Pearl Street (lat:x3 lon:y3)
6. In:103 Alkazam, New York, USA => Out:New York (lat:x1 lon:y1)

В 6 выше Нью-Йорк был возвращен, так как не было найдено места с адресом 103 Alkazam, New York, USA, но по крайней мере удалось найти New York, USA.

Первоначально я думал о построении дерева, представляющего отношение иерархии, в котором братья и сестры сортируются в алфавитном порядке. Это могло быть как:-

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

Но проблема заключалась в том, что пользователь мог указать неполный адрес, как в 2, 4 и 5.

Итак, я подумал об использовании дерева поиска и сохранении полного адреса в каждом узле. Но это тоже довольно плохо, так как:-

• Это будет хранить сильно избыточные данные в каждом узле. Поскольку это будут действительно большие данные, сохранение пространства имеет значение.
• Он не сможет использовать тот факт, что пользователь сузил область поиска.

У меня есть одно дополнительное требование .Мне нужно обнаружить опечатки. Я предполагаю, что это нужно будет рассматривать как отдельную проблему и можно рассматривать каждый узел как общие строки.

Обновление 1

Небольшое уточнение. Входными данными будет список, в котором элемент с более низким индексом является родителем элемента с более высоким индексом; и они, конечно, могут быть или не быть непосредственными родителями или детьми. Таким образом, для запроса 1 ввод будет ["USA", "NEW YORK"]. Итак, совершенно нормально, что USA, New Yorkне возвращает никакого результата.

Пользователь должен иметь возможность найти здание, если у него есть адрес, а наши данные настолько подробны.

Обновление 2 (Случай упущения)

Если пользователь запрашивает Pearl Street, USA, наш алгоритм должен найти адрес, поскольку он знает, что Pearl Streetимеет New Yorkв качестве родителя, а USAявляется его родителем.

Обновление 3 (Случай излишка)

Предположим, что пользователь запрашивает 101 C, Alley A, Pearl Street, New York. Также предположим, что наши данные знают о 101 C, но не знают о Alley A. Согласно ему 101 Cявляется непосредственным потомком Pearl Street. Даже в этом случае он должен быть в состоянии определить местонахождение адреса.