Algoritmo de teclas de coincidencia de direcciones

StackOverflow https://stackoverflow.com/questions/824588

Pregunta

Tengo una lista de direcciones en dos tablas separadas que están ligeramente apagadas que necesito para poder coincidir. Por ejemplo, la misma dirección se puede ingresar de varias maneras:

  • 110 Test St
  • 110 Test St.
  • 110 Test Street

Aunque simple, puedes imaginar la situación en escenarios más complejos. Estoy tratando de desarrollar un algoritmo simple que pueda coincidir con las direcciones anteriores como una clave.

Por ejemplo. la clave podría ser "11TEST" - Los dos primeros de 110, los dos primeros de Prueba y los dos primeros de variante de calle. Una clave de coincidencia completa también incluiría los primeros 5 del código postal, así que en el ejemplo anterior, la clave completa podría verse como "11TEST44680".

Estoy buscando ideas para un algoritmo o recursos efectivos que pueda analizar para tener en cuenta al desarrollar esto. Cualquier idea puede ser un pseudo código o en el idioma de su elección.

Solo nos preocupan las direcciones de los Estados Unidos. De hecho, solo estamos buscando direcciones de 250 códigos postales de Ohio y Michigan. Tampoco tenemos acceso a ningún software postal, aunque estaríamos abiertos a ideas para soluciones rentables (esencialmente sería un uso único). Tenga en cuenta que este es un volcado inicial de datos de una fuente gubernamental, por lo que las sugerencias sobre cómo los usuarios pueden limpiarlo son útiles a medida que construyo la aplicación, pero me encantaría tener la mejor inicial posible que pueda al hacer coincidir las direcciones como lo mejor posible

¿Fue útil?

Solución

Estoy trabajando en un algoritmo similar mientras hablamos, debería manejar direcciones en Canadá, Estados Unidos, México y el Reino Unido para cuando termine. El problema al que me enfrento es que están en nuestra base de datos en formato de texto sin formato de 3 campos [quien pensó que eso era una buena idea debería recibir un disparo en mi humilde opinión], así que tratando de manejar rutas rurales, entregas generales , receptores de gran volumen, múltiples países, provincia versus estado versus condado, códigos postales versus códigos postales, los errores ortográficos no son tareas pequeñas o simples.

Los errores de ortografía por sí solos no fueron una tarea fácil, especialmente cuando llegas a países que usan nombres franceses: coinciden con Saint, Sainte, St, Ste, Saints, Saintes, Sts, Stes, Grand, Grande, Grands, Grandes con o sin periodo o la separación silábica a la parte más grande de un nombre no causa problemas de finalización del rendimiento, especialmente cuando St podría significar santo o calle y puede o no haberse ingresado en el contexto correcto (es decir, femenino versus masculino) . ¿Qué sucede si la dirección se ha ingresado correctamente pero tiene una provincia o código postal incorrectos?

Un lugar para comenzar su búsqueda es Algoritmo de distancia de Levenstein que he encontrado que es realmente útil para eliminar una gran parte de los errores de ortografía. Después de eso, se trata principalmente de buscar palabras clave y compararlas con una base de datos postal.

Me interesaría mucho colaborar con cualquiera que esté desarrollando herramientas para hacer esto, quizás podamos ayudarnos mutuamente a encontrar una solución común. Ya soy parte del camino y he superado todos los problemas que he mencionado hasta ahora, tener a alguien más trabajando en el mismo problema sería realmente útil para intercambiar ideas.

Saludos - [ben at afsinc dot ca]

Otros consejos

Si prefiere tonot desarrollar uno y prefiere usar un producto comercial que utiliza muchas de las tecnologías mencionadas aquí, consulte: http://www.melissadata.com/dqt/matchup-api.htm

Descargo de responsabilidad: Tuve un papel en su desarrollo y trabajo para la empresa.

En el Reino Unido usaríamos:

  • Nombre o número de la casa (donde el nombre incluye el número plano para bloques de apartamentos)
  • Código postal

Ciertamente debería usar el código postal, pero en los EE. UU. creo que sus códigos postales cubren áreas muy amplias en comparación con los códigos postales en el Reino Unido. Por lo tanto, necesitaría usar la calle y la ciudad.

Su ejemplo no diferenciaría entre 11 Test Street, 110 - 119 Test Street, etc.

Si su empresa tiene acceso a un sistema de búsqueda de direcciones, ejecutaría todos los datos para recuperar los datos en un formato coherente, posiblemente con claves de dirección que puedan usarse para hacer coincidencias.

Si tuviera que analizar esto, convertiría cada cadena de dirección en un árbol utilizando un orden de operaciones predefinido.

Por ej. 110 Test Street Apt 3. En cualquier lugar California 90210 = >

  1. Obtenga el tipo de dirección. Por ejemplo, las direcciones de calles tienen diferentes formatos que las direcciones de rutas rurales y esto es diferente según el país.
  2. Dado que se trata de una dirección de calle, obtenga la cadena que representa el tipo de calle y conviértala en una enumeración (eBoulevard, eRoad, etc.)
  3. Dado que esta es una dirección postal, extraiga el nombre de la calle (almacenar en minúsculas)
  4. Dado que se trata de una dirección, saque el número de la calle

  5. Dado que esta es una dirección de calle, busque cualquier número de apartamento (podría estar antes del número de la calle con un guión, podría estar después de " Apt. " ;, etc ...) 

       eStreet  //1.an enum of possible address types eg. eStreet, eRuralRoute,...
      |
   eStreet        //2.an enum of street types eg. eStreet, eBlvd, eWay,...
   /   |   \

    Nombre Número Apt     El | El | El |    prueba 110 3

Por ej. RR # 3 en cualquier lugar California 90210 = >

  1. Obtenga el tipo de dirección: ruta rural

  2. Dado que esta es una dirección de ruta rural, obtenga el número de ruta 

       eRuralRoute 
      |
      3

Deberá hacer algo similar para el estado del país y la información del código postal.

Luego compara los árboles resultantes.

Esto hace que la comparación sea muy simple, sin embargo, el código para generar los árboles es muy complicado. Te gustaría probarlo en miles y miles de direcciones. Su problema es más simple si solo le interesan las direcciones de EE. UU. Las direcciones británicas, como ya se mencionó, son bastante diferentes, y las direcciones canadienses pueden tener francés (p. Ej., Place D'Arms, Rue Laurent, etc.)

Si es rentable para su empresa escribir su propia herramienta de normalización de direcciones, sugiero comenzar con estándar de direcciones USPS . Alternativamente, hay muchos proveedores que ofrecen herramientas del lado del servidor y servicios web para normalizar, corregir y verificar direcciones.

Mi empresa utiliza AccuMail Gold para este propósito porque hace mucho más que simplemente estandarizar & amp; corrige la dirección Cuando consideramos el costo del salario de incluso una semana para desarrollar una herramienta internamente, la elección de comprar un producto estándar era obvia.

Si no elige usar un sistema existente, una idea es hacer lo siguiente:

  • Extraer números de la línea de dirección
  • reemplazar las palabras comunes de la calle con espacios en blanco
  • crear cadena de coincidencia

es decir: "555 Canal Street":

  • El número de extracto da " 555 " + " Canal Street "
  • Reemplazar palabras de la calle da " 555 " + " Canal "
  • Crear cadena de coincidencia da " 555Canal "

" Canal st 555 " daría la misma cadena de coincidencia.

Por palabras de la calle me refiero a palabras y abreviaturas de " street " en su idioma, por ejemplo, "st", "st.", "blv", "ave", "etc", etc., etc. se eliminan de la cadena.

Al extraer números y separarlos de la cadena, no importa si son los primeros o los últimos.

use una identidad para la clave principal , esto siempre será único y facilitará la combinación de duplicados más tarde.

forzar la entrada de datos adecuada con la interfaz de usuario. Haz que ingresen cada componente en su propio cuadro de texto. El número de la casa se ingresa en el cuadro propio, el nombre de la calle en su propio cuadro, la ciudad en el cuadro propio, el estado de la lista de selección, etc. Esto facilitará la búsqueda de coincidencias

tiene dos procesos " guardar "

  • después de guardar inicialmente, haga una búsqueda para buscar coincidencias, preséntelas con una lista de posibles coincidencias y la nueva.
  • después de que seleccionen el nuevo, guárdelo, si eligen uno existente, utilicen ese ID

limpiar los datos. Trate de eliminar "street", "st", "drive", etc y guárdelo como un tipo de calle (1) que usa un FK en una tabla que contiene las abreviaturas adecuadas, para que pueda construir la calle.

mira en SOUNDEX y DIFERENCIA

He trabajado en grandes empresas que mantienen listas de correo, y no intentaron hacerlo automáticamente, utilizaron personas para filtrar lo nuevo de los dups porque es muy difícil hacerlo. Planifique una función de combinación para que pueda combinar manualmente duplicados cuando se produzcan, y ripear los valores a través de las PK.

Puede mirar en la API de Google Maps y ver si puede pasar su dirección y obtener una coincidencia. No estoy familiarizado con esto, esto es solo especulación.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top