2010-05-20 16 views
5

Estoy trabajando en un programa de encuestas en el que las personas recibirán consideraciones promocionales la primera vez que llenen una encuesta. En muchos escenarios, la única forma en que podemos evitar que la gente engañe al sistema y obtener un ascenso que no se merece es verificar las cadenas de direcciones entre sí.algoritmo para verificar las direcciones de las coincidencias?

Estaba buscando usar distancia levenshtein para darme un número para medir la similitud, y considerar aquellos que están por debajo de un cierto umbral un duplicado.

Sin embargo, si alguien estuviera buscando jugar con el sistema, podrían escribir fácilmente "S 5th St" en lugar de "South Fifth Street", y levenshtein consideraría esas cadenas como muy diferentes. Así que estaba pensando en convertir todas las cadenas en una 'forma de dirección estándar', es decir, 'Sur' se convierte en 's', 'Quinto' se convierte en '5', etc.

Entonces pensé que esto era inútil, y demasiado esfuerzo para que funcione de manera robusta. ¿Lo es?

Estoy trabajando con PHP/MySql, así que tengo las limitaciones inherentes a ese sistema.

+1

¿Qué pasa si en lugar de "S. 5th St." alguien entra a "S. 4th St."? Esto no se podría usar para jugar con el sistema (suponiendo que esté enviando por correo las cosas promocionales), pero podría descalificar a las personas por vivir a una cuadra. Solo una caja de borde para probar. –

+0

@Bill ese escenario no es un problema porque entonces no recibirían su consideración promocional. A menos que estén confabulados con las personas que residen en la dirección de esa casa en la calle 4, pero solo hay muchos hogares con los que pueden conspirar. Es autolimitante, creo :) – user151841

+0

@ user15841: No, me refiero a si esas dos personas legítimamente se registran independientemente una de la otra? Su algoritmo debe ser lo suficientemente inteligente como para ver la diferencia entre esas dos direcciones, pero también lo suficientemente inteligente como para ver los ejemplos originales que dio como iguales. –

Respuesta

3

Creo que su segunda idea es mejor que usar la distancia Levenshtein. Si intenta comparar las direcciones para la similitud , entonces dos personas diferentes que viven cerca una de la otra podrían accidentalmente "engañarse" mutuamente de su premio. Si vivo en "S. 4th St." pero mi vecino en "S. 5th St." Ya se inscribieron, esas dos direcciones pueden parecer demasiado similares por la distancia Lev.

Podría reducir (pero probablemente no eliminar) una gran cantidad de posibles trampas ejecutando direcciones a través de un normalizador de sinónimos. Antes de comprobar por la igualdad, simplemente convertir

Norte -> N.
Este -> E.
...
Primera -> primera
Segundo -> segunda
Tercera -> tercera
. ..
Calle -> St.
Avenida -> Avenida.

Cuanto más larga sea la lista de sinónimos que se te ocurra, mejor será en la captura de coincidencias. Será un poco más lento en el procesamiento, pero las direcciones son pequeñas.

Esto es similar a la conversión de cadenas a todas las cajas inferiores (o superiores) antes de compararlas. (Que también recomiendo, naturalmente.)

+0

¡Oh, finalmente entiendo lo que dices! No he usado levenshtein, por lo que no estaba lo suficientemente familiar como para saber cómo surgiría esa situación :) – user151841

+0

Además, debe tenerse en cuenta que varios residentes pueden estar viviendo en el mismo edificio ... Ahí es donde se vuelve complicado , incluso después de la estandarización. Por ejemplo, "511 N 15th St, Unit 123" frente a "511 NORTH 15th St, Apt 124" –

+1

También debería considerar el uso de la comparación de distancia de cuerdas en los sinónimos. De lo contrario, "Sur" se convertirá en "S", pero "Soith" (error tipográfico) no lo hará, y "Soith" -> "S" no es similar. Además, tenga en cuenta que hay miles de caracteres Unicode que producirán caracteres que se parecen a los caracteres a-z pero no lo son. Además, "Street" -> "St". puede conducir a un falso positivo para la abreviatura 'Saint' "St.". –

0

Puede utilizar Google Map API (o cualquier otra API de mapeo) para normalizar las direcciones como ubicación geográfica (lat/long).

+1

No funcionaría porque la mayoría de estas api geoespaciales no consideran los números de los departamentos (por ejemplo, la 6ª planta del piso 12). – code4life

+0

Sí, dicha normalización no sería 100% precisa y también necesitaría hacer comprobaciones adicionales. –

0

Vea thesequestions para la discusión relacionada.

  • Normalizar los datos de la primera medida de lo posible:

    avenida -> Ave carretera -> rd Rd.-> rd

    primera -> 1 primero -> 1

Se podría buscar en SOUNDEX o algo similar para atrapar los casos en que las sanas palabras igual pero tienen diferente ortografía (por ejemplo, Schmitt, Schmitd, Smith) . SOUNDEX funciona a nivel de palabra, por lo que primero deberá dividir la dirección en palabras y comparar los valores SOUNDEX.


También puede alimentar a las direcciones de algunos geo servicio de localización como Google Maps, resultando tienda longitud y latitud a su base de datos. Cuando se ingresa una nueva dirección, obtiene su longitud/latitud y la compara con las ubicaciones existentes en su base de datos. See this question para más detalles.

Cuestiones relacionadas