Limpieza después de la fiesta

16 de diciembre 2008 · Escrito en Perl

"No sólo el monje vive de expresiones regulares, pero no todos los módulos en CPAN."

Recientemente se me asignó la ingrata tarea de llevar a cabo una determinada actividad hacia atrás. El sentido común nos dice que el mejor momento para esterilizar (o desinfectar) los datos en un sistema en algún momento antes de entrar en la base de datos. Esto le ahorra dolores de cabeza enorme, incluso mediante la inyección de SQL.

Desafortunadamente (o afortunadamente) el mundo real no es un mundo ideal y, a veces los datos es necesario limpiar el interior del banco. En mi caso, había varias empresas, cada uno con una base de "clientes" que se introdujo con la mano. En un momento dado estas empresas se fusionaron y unificada en una de las bases (al menos eso es lo que me han dicho) y un tiempo después decidió hacer de esta información (sobre todo las direcciones) a través de la web.

El pequeño detalle es que cada base tiene sus propias inconsistencias, que culminó en conjunto después de un puñado de datos que contiene todas las contradicciones entre sí. ¿Qué hacer ahora? ¿Cómo ahora?

La solución para desinfectar estas direcciones fue atrapado usando una aplicación que cada dirección de uno en uno y comparar con la base de la Dirección Nacional de Direcciones .

Como una cuestión de rendimiento en lnguagem Perl fue adoptado. Las otras opciones, el más rápido tomaría unos años algun funcionando en todo momento para resolver el problema, con una calidad cuestionable.

El principal problema en sí mismo, no se qué hacer, sino cómo hacerlo. Sólo tiene que utilizar una expresión regular no resolver porque tuvimos errores como:

"Caximbo la calle" en vez de "Pipe Street '
'Street Marai de Gracia' en lugar de "la calle Virgen de Gracia '

Tratando de averiguar todas las combinaciones posibles de error llevaría más tiempo que ejecuta la aplicación. Tuvimos que recurrir a los algoritmos de cadena coincidente. Para el deleite de la multitud hay un montón de módulos en CPAN para ello, basta con escoger el más adecuado.

Texto:: Soundex

Esto pegó en el travesaño. Se utiliza un algoritmo fonético para detectar palabras similares de acuerdo con su pronunciación en Inglés ... abordar una serie de errores de ortografía, si las direcciones son las expresiones en Inglés.

Texto:: Levenshtein

Otro módulo interesante. El algoritmo utiliza "Levenshtein distancia de edición", una medida de "distancia" entre las cadenas en función del número de inserciones, supresiones y sustituciones realizadas en una manera que se convierte en el otro y viceversa.

En nuestras pruebas de muestreo demostró que era más rápido que la cadena:: Trigrama, pero con resultados de menor calidad. La propia documentación dice que no es adecuado para esta tarea.

String:: Trigrama

La cadena de módulo:: Trigrama Tarek Ahmed fue la mejor respuesta a nuestras pruebas de muestreo. Se utiliza el algoritmo de n-gramas, que es la de convertir toda una serie de bloques especiales de caracteres n, el n-gramas, y comparar las series de cada cadena. De esta comparación una similitud entre las cuerdas. Por ejemplo:

camión, coche arr} {eta rre ret
cara: {} eta coche se ret

(Coincidencia de n-gramas) / (total de n-gramas) = ​​índice de similitud
3 / 6 = 50%

El módulo también tiene muchas opciones para la puesta a punto.

Otros módulos

Otros módulos como el String:: Similitud y String:: Aprox pero ambos fueron analizados utilizando los algoritmos analizados anteriormente de distancia, y fueron descartados por la misma razón.

El n-Gramática

Puede parecer extraño que el algoritmo de n-gramas es mejor que una salida de distancia, pero eso es lo que funciona mejor con nuestros datos. Además, el módulo nos permite crear una especie de caché con una base de comparación, si las direcciones de la NBS.

Dada una lista de palabras (de la base de las direcciones de NBS limpio), se calcula el n-gramas y los almacena una clave hash una vez. Cada vez que se comprueba una sola palabra en contra de la base, la palabra también se divide en n-gramas que se buscan en el hash de la base. Al final del módulo devuelve una lista de palabras básicas que están más cerca de la palabra seleccionada, limitado por el mínimo grado de similitud que se configura.

La aplicación de

La aplicación final direcciones separadas por código postal y creó una base de micro-con pocas carreteras, por lo que es la comparación más fácil. Después de actualizar o no la dirección en la base de datos "sucios", diciendo que el índice de similitud entre la BNE y la dirección base de entrada. Todo esto, por supuesto, hecho en varios procesos paralelos, tocando el cuello de botella en la capacidad de la base de datos para proporcionar y actualizar los datos.

Tiempo estimado para procesar toda la base? Unos tres meses. Tasa limpiado correctamente las direcciones? 97%

A continuación se presenta un breve esbozo de cómo utilizar la cadena:: trigrama 

  #! / Usr / bin / perl

 use strict;
 uso de advertencias;

 Trigram ; el uso de cadenas:: Trigrama;

 # # Sólo para el diseño de Wordpress no es una mierda ...
 # # Conjunto de la población Nadie como este, está bien!
 ; @ mi base;
 , qw/rato boi tigre coelho dragao serpente/ ; push @ de base qw / rata buey tigre conejo dragón serpiente /;
 , qw/cavalo carneiro macaco galo cao porco/ ; push @ de base qw / oveja caballo cerdo perro mono gallo /;

 # # Por lo tanto, es más apropiado.
 = qw/ratos drogao cavalo caval carneir camelo galinha/ ; my @ palabras = qw / ratones drogao camello caballos carne de pollo /;

 = 0.20 ; ## 20% my $ min_sim = 0,20, 20% # #

 = String :: Trigram -> new ( my $ trig = String:: Trigrama -> new (
     @base , "CmpBase" => @ base de
     $min_sim , "MinSim" => $ min_sim,
     1 , "Warp" => 1,
     1 , "IgnoreCase" => 1,
     1 , "KeepOnlyAlNums" => 1,
     3 , "Ngram" => 3,
     0 , "Debug" => 0,
 );

 ( @words ) { para mi $ alimentación (@ palabras) {
     @best_matches , $sim ) ; mi (@ best_matches, $ yes);

     $trig -> getBestMatch ( $animal , @best_matches ) ; Sí $ = $ trig -> getBestMatch ($ animal, @ best_matches);

     int ( 0.5 + 100 * $sim ) ; $ Sí = int (100 * 0.5 + $ yes);

     $sim >= $min_sim ) { if ($ yes> = $ min_sim) {
         , $/ ; print "La similitud entre $ y $ best_matches animal [0]: Sí% $ t", $ /;
     }
 }

Enlaces de interés, o no ...

Comprehensive Perl Archive Network
La investigación sobre CPAN
String:: Trigrama CPAN

Tags: No Tags

Comentarios

  • Daniel Mantovani

    Fantástica a tener que ir perl.org.br

    Era una forma muy inteligente de hacer una cosa.

    Blaber, ahora que estás de vacaciones y podría dar algunas conferencias en universidades y ampliar la cultura Perl en el país. Este artículo sería un infierno de un ejemplo de cómo Perl es poderoso, y cómo los programadores de Perl son de mierda.

  • Daniel Mantovani

    Fantástica a tener que ir perl.org.br

    Era una forma muy inteligente de hacer una cosa.

    Blaber, ahora que estás de vacaciones y podría dar algunas conferencias en universidades y ampliar la cultura Perl en el país. Este artículo sería un infierno de un ejemplo de cómo Perl es poderoso, y cómo los programadores de Perl son de mierda.

  • Doña María

    De ninguna manera!

  • Doña María

    De ninguna manera!

  • http://twitter.com/renato_cron Renato Souza Santos

    Tenemos que hacer aquí en la empresa, pero en realidad el problema es que las calles no son de código postal.

    Tenemos la base del poste (se actualiza cada dos meses).
    en su caso,
    el cuello de botella era esperar a que el correo electrónico (que es un sitio muy lenta, jajaja)?

  • Blaber http://blabos.org de la ampolla

    Nada. El gragalo desnormalizado estaba en el banco y su tamaño. Simplemente añadiendo algunos índices mejoró el rendimiento bastante.Também tenido la base de datos de oficina de correos en Oracle.

Sitio en Disqus