¿Qué estructura de datos debo usar para geocodificar?

Question

Estoy tratando de crear una secuencia de comandos de Python que tomará una dirección como entrada y escupirá su latitud y longitud, o latitudes y longitudes en caso de múltiples coincidencias, como Nominatim.

Por lo tanto, la posible entrada y salidas pueden ser: -

1. En: Nueva York, EE.UU. => Salida: Nueva York (Lat: x1 lon: y1)
2. En : Nueva York => salida: Nueva York (Lat: x1 lon: y1)
3. En: Pearl Street, Nueva York, EE.UU. => salida: Pearl Street (Lat: x2 lon: y2)
4. En: Pearl Street, EE.UU. => Salida: Pearl Street (Lat: x2 lon: y2), la calle Pearl (Lat: x3 lon: y3)
5. En: Pearl Street => salida: Pearl Street (Lat: x2 lon: y2), la calle Pearl (Lat: x3 lon: y3)
6. En: 103 Alkazam, Nueva York, EE.UU. => Fuera: Nueva York (lat: x1 lon: y1)

En 6, se devolvió Nueva York ya que no se encontró ningún lugar con la dirección 103 Alkazam, New York, USA, pero al menos podría encontrar New York, USA.

Inicialmente pensé en construir un árbol que representara la relación jerárquica donde los hermanos se ordenan alfabéticamente. Podría haber sido como: -

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

Pero el problema era usuario puede proporcionar la dirección incompleta como en 2, 4 y 5.

Por lo tanto, la próxima pensado en utilizar un árbol de búsqueda y almacenar el completo dirección en cada nodo. Pero esto también es bastante malo ya que: -

• Esto almacenará datos altamente redundantes en cada nodo. Dado que esto será realmente un gran dato, la conservación del espacio importa.
• No podrá aprovechar el hecho de que el usuario ha reducido el espacio de búsqueda.

Tengo un requisito adicional. Necesito detectar errores ortográficos. Supongo que tendrá que tratarse como un problema aparte y puede tratar a cada nodo como cadenas genéricas.

Actualización 1

A poca elaboración. La entrada sería una lista, donde el elemento en el índice más bajo es padre del artículo en un índice más alto; y, por supuesto, pueden o no ser padres o hijos inmediatos. Por lo tanto, para la consulta 1, la entrada sería ["USA", "NEW YORK"]. Por lo tanto, está perfectamente bien que USA, New York no devuelva ningún resultado.

El usuario debería poder localizar un edificio si tiene la dirección y nuestros datos son tan detallados.

Actualización 2 (Omisión Caso)

Si Pearl Street, USA usuario consulta, por lo que nuestro algo debe ser capaz de localizar la dirección, ya que sabe Pearl Street tiene New York como padre y USA es su padre.

Actualización 3 (Caso Excedente)

Supongamos que las consultas de los usuarios para 101 C, Alley A, Pearl Street, New York. Supongamos también que nuestros datos sí saben de 101 C pero no de Alley A. De acuerdo con él 101 C es un hijo inmediato de Pearl Street. Incluso en este caso, debería poder ubicar la dirección.

Answer 1

Gracias a todos por sus respuestas, sus respuestas fueron útiles, pero sin abordar todo lo que necesitaba. Finalmente encontré un enfoque que se ocupó de todos mis casos. El enfoque es la versión modificada de lo que sugerí en la pregunta.

El enfoque básico

Aquí me referiré a algo que se llama 'nodo', es un objeto de la clase que contendrá la información geográfica como la latitud de una entidad lugar, longitud, quizá dimensión demasiado, y su dirección completa.

Si la dirección de la entidad es '101 C, Pearl Street, Nueva York, EE. UU.', Significa que nuestra estructura de datos tendrá al menos cuatro nodos para - '101 C', 'Pearl Street', 'Nuevo York 'y' EE. UU. ' Cada nodo tendrá una parte name y una address. Para '101 C', name será '101 C' y la dirección será 'Pearl Street, Nueva York, EE. UU.'.

La idea básica es tener un árbol de búsqueda de estos nodos, donde se usará el nodo name como la clave para la búsqueda. Es posible que obtengamos varias coincidencias, por lo que más adelante debemos clasificar los resultados sobre cuán bueno coincide el nodo address con el consultado.

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

Supongamos que tenemos una información geográfica como la anterior.Por lo tanto, una búsqueda de '101 C, NUEVA YORK' no solo devolverá los nodos '101 C' en 'NUEVA YORK', sino también la de 'INDIA'. Esto se debe a que el algoritmo solo usará el name, es decir, '101 C' aquí, para buscar los nodos. Luego podemos calificar la calidad del resultado midiendo la diferencia de address del nodo de la dirección consultada. No estamos usando una coincidencia exacta ya que el usuario puede proporcionar una dirección incompleta, como en este caso.

Clasificación Resultados de la búsqueda

para clasificar la calidad de los resultados podemos utilizar Longest Common Subsequence. Los casos 'Omisión' y 'Excedente' están bien atendidos en este algo.

Es mejor si dejo que el código hable. A continuación se muestra una implementación de Python adaptada para este propósito.

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) 

enfoque optimizado

I rescatados en el enfoque anterior (básico) puesto que obligaba a la redundancia, y que no podía cortar aprovechar el hecho de que si el usuario ha proporcionado 'EE.UU.' en su consulta entonces necesitamos no mirar hacia los nodos en 'INDIA'.

Este enfoque optimizado resuelve los dos problemas anteriormente mencionados hasta cierto punto. La solución es no tener un gran árbol de búsqueda. Podemos dividir el espacio de búsqueda en 'USA' e 'INDIA'. Más adelante podemos reparticionar aún más esos espacios de búsqueda en términos de estado. Esto es lo que llamo 'rebanar'.

En el siguiente diagrama: SearchSlice representa un 'sector', y SearchPool representa un árbol de búsqueda.

      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 

algunos puntos clave de aviso por encima de ...

• Cada corte es solo un nivel profundo. Bueno, esto no es realmente evidente arriba.
• El nombre del nivel cortado no aparece en la dirección de sus hijos. Por ejemplo, SearchSlice(USA) mantiene una porción de estados en 'EE.UU.'. Por lo tanto, los nodos en "NUEVA YORK" no incluyen el nombre "NUEVA YORK" o "EE. UU." En su address. Lo mismo aplica para otras regiones también. La relación jerárquica define implícitamente la dirección completa.
• '101 C' address también incluye el name de su padre, ya que no se cortan.

Posibilidades de escala

Donde hay un cubo (piscina), hay una posibilidad de escalado implícita. Nosotros (digamos) dividimos los datos geográficos de "EE. UU." En dos grupos. Ambos pueden estar en diferentes sistemas. Por lo tanto, está perfectamente bien si el grupo 'NEW YORk' está en el Sistema A, pero el grupo 'CALIFORNIA' está en el Sistema B, ya que no comparten ningún dato, excepto los padres, por supuesto.

Aquí está la advertencia. Necesitamos duplicar a los padres, que siempre será una rebanada. Debido a que los sectores están limitados en número, la jerarquía no será demasiado profunda, por lo que no debería ser demasiado redundante para duplicarlos.

El Código de Trabajo

Por favor refiérase a mi GitHub para un working demo Python code.

Answer 2

¿qué hay de usar un mapa de almacenamiento de valores-clave y búsqueda de texto completo.

• clave para la cadena de ubicación
• valor de & datos lon lat location_level y.
• búsqueda por:
  • dividida cadena de entrada de usuario a los lugares de las palabras individuales (no sólo por comas)
  • buscar en cada palabra en el mapa
  • retorno del lat & lon de nivel más pequeño lugar

python.dict, memcached, mongodb .... cumplirán con su necesidad.

• si tienes demasiadas palabras localización, location_level dividida como un nuevo mapa, dos búsquedas acelerará
• olvidemos niveles traet ubicación, como búsqueda de texto completo
• datos de gran tamaño? clave hash de cadena corta o números

algunos questiongs a tener en cuenta:

• cómo almacenar los datos en la base de datos
• cómo init su árbol de búsqueda de datos, en su caso
• cómo extender/editar árbol de búsqueda en tiempo de ejecución
• tolerante a errores para entrada/almacenamiento
• espacio de almacenamiento> ¿velocidad? o velocidad> almacenamiento?

así, más caso de prueba utilizable la entrada del usuario

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 

para la situación:

• rápida velocidad con gran-datos;
• full-fault-tolerant;
• fácil de ajustar con el almacenamiento y el tiempo de ejecución

la mejor solución: (también compleja-est)

• plana clave-valor del mapa de almacenamiento
• búsqueda de texto completo
  • o tecla hash con búsqueda de árbol B

su programa/sitio web puede funcionar tan rápido como google.

Answer 3

Si intenta crear una estructura de datos para este problema, creo que tendrá redundancia de datos. En su lugar, puede utilizar tree/graph & intente implementar un algoritmo de búsqueda que busque las palabras de la entrada del usuario contra los valores del nodo. La coincidencia difusa puede ayudarlo a generar los resultados más probables, y puede sugerir/mostrar al usuario algunos de ellos según el nivel de confianza de su semejanza-quotent.

Esto también puede hacerse cargo de Erratas etc.