Identificador: asma-aat
Introducción
Al hacer reservaciones o compras de boletos de avión frecuentemente ocurren errores en los nombres debido, en parte, a que estas operaciones pueden ser realizadas sea por teléfono o bien por terceras partes tales como secretarias o agentes de viajes. El problema puede ser todavía más complicado en líneas aéreas internacionales que manejan nombres “extranjeros”. El problema de reconocer y recuperar nombres mal tecleados es un problema real que debe de resolverse cotidianamente.
El propósito de este proyecto es implementar el algoritmo que se usa (o al menos se usó durante muchos años) para efectuar esta operación.
La idea es, primero, codificar un nombre de persona dado para usar después esta codificación como llave de búsqueda. Si el nombre no contiene errores esta codificación también arroja el resultado deseado. La codificación se hace de manera automática, el agente sólo debe teclear el nombre proporcionado (apellido paterno seguido de la inicial del nombre, como se acostumbra en las líneas aéreas) con la ortografía que mejor pueda.
Codificación
Dada una cadena de caracteres representando un apellido y posiblemente un nombre, una codificación consistente de cinco caracteres se obtiene como se indica:
1) El primer carácter es siempre la primera letra del apellido.
2) El quinto carácter es, o bien la inicial del nombre si éste se proporciona, o bien es un símbolo especial (puede ser punto “.”) diferente de cualquier letra. (El quinto símbolo también pudiera ser una inicial con baja frecuencia de aparición, por ejemplo “Ñ”.)
3) El segundo, tercero y cuarto caracteres de la codificación son consonantes obtenidas del apellido, por el siguiente procedimiento:
i) Eliminar todas las vocales al igual que todas las ocurrencias de las letras H, W o Y (excepto la inicial del apellido).
ii) Cada vez que una letra se repita de manera contigua, se eliminan todas las repeticiones excepto la primera.
iii)Las primeras tres letras resultantes (o el número que sea si son menos de tres) adyacentes a la primera letra conservada son entonces el segundo, tercero y cuarto caracteres de la codificación.
4) Un nombre codificado siempre consiste de cinco caracteres. Si el resultado del paso (3) arroja menos de tres consonantes adicionales, se agregan “espacios” en la cuarta, tercera o segunda posición de la codificación para hacerla de tamaño cinco.
5) Los primeros cuatro caracteres de la codificación serán llamados el “apellido codificado”.
Ejemplos:
MULLER, GERARD MLR_G
MARTINEZ, W. MRTNW
SAN MIGUEL, A. SNMGA
KHUNA, PASCALE KN__P
Búsqueda
1) El agente proporciona un nombre que se codifica como se describió arriba y el “apellido codificado” se busca en los registros de inventarios de acuerdo al vuelo/fecha.
2) Si se encuentra al menos una coincidencia perfecta, se verifica entonces la inicial del nombre. Si al menos un registro concuerda con la inicial entonces solamente los registros que coinciden con la inicial se procesan en el paso siguiente. (En caso contrario, si ningún registro concuerda con la inicial, se procesan los registros que coinciden con el “apellido codificado”.)
3) Aquellos registros que pasaron el paso (2) se procesan usando una búsqueda por apellido completo, sin incluir la inicial del nombre. Los registros que pasan esta prueba son presentados al agente. (Si el número telefónico o alguna otra información secundaria ha sido introducida por el agente como parte de la búsqueda del nombre de una persona, entonces este criterio se aplica automáticamente en este paso para eliminar pasajeros con el mismo nombre pero con la demás información incorrecta.)
4) Si ninguna búsqueda de nombre completo coincide exactamente con el nombre de persona proporcionado por el agente, pero al menos se encontró correctamente un “apellido codificado” entonces los registros de estos pasajeros serán presentados al agente para que tome una decisión (con nombre completo y número telefónico, como aparecen en el archivo). Los errores de ortografía debidos a vocales incorrectas o a las letras W, H o Y serán reconocidos por el agente en este punto. Como de costumbre, si ha habido un registro con la inicial del nombre correcta, sólo los registros de este tipo serán presentados al agente.
5) El agente, ante la lista presentada por el programa con los nombres “correctos” de los candidatos, con sus números telefónicos y cualquier información adicional que aparezca en el archivo, pude efectuar una nueva búsqueda usando sea el nombre tal cual apareció en los registros, sea el número telefónico para, de esta manera, asegurarse de la identificación del registro del pasajero deseado. Esta fase elimina errores tales como MILLER por MUELLER o MULLER, MCRAY por MCRAE, BRUGEL por BREUGHEL o BRUEGHEL, LOUGHLIN por LAUGHLIN, LOUIS por LEWIS, COWAN por COHEN, BOWMAN por BAUMAN, GILCHRIST por GILCRIST. Como se puede fácilmente comprobar, el algoritmo de codificación mencionado antes arroja los mismos “apellidos codificados” para los miembros de grupos de nombres dados.
6) Si no se encontró ningún “apellido codificado” correcto para usar en el paso (4) entonces se utiliza otra rutina llamada nombre_mal_tecleado, descrita posteriormente. Esta rutina calificará cada apellido codificado en los registros de inventario contra el apellido codificado buscado. Al final del proceso de calificación se presentarán al agente los nombres completos y demás información adicional de los (relativamente pocos) registros con la mejor calificación. Como es usual, la inicial del nombre correcta tiene un valor mayor en la calificación. El agente ahora recupera el registro deseado usando un nuevo nombre para la búsqueda, usando el nombre tal cual aparece en la lista de registros proporcionados por la rutina, o bien usando el número telefónico. Ejemplos de nombres mal tecleados recuperados de esta manera se presentan a continuación.
Recuperación de nombres mal tecleados
Como se explicó antes, se usa una calificación para calificar a los nombres candidatos cuando un error significativo se ha hecho al teclear un nombre y no se ha podido identificar con la búsqueda descrita antes. Algunos puntos ayudan a simplificar esta técnica de calificación:
• Ninguna letra aparecerá en un apellido codificado más de dos veces.
• Los espacios en los apellidos codificados aparecen al final.
• Las letras repetidas en un apellido codificado no son contiguas.
La calificación se basa en buscar evidencia de concordancia de letras entre el apellido codificado buscado y los apellidos codificados en los registros, suprimiendo posible “ruido” causado por letras diferentes, no importando si hubo error al teclear estas letras en el nombre buscado o en los almacenados.
La calificación se realiza asignando valores Pi a las cuatro letras de cada apellido codificado que aparece en el registro, llamémosle a este apellido el candidato. Cada carácter Ki en la llave buscada tecleada se compara con los caracteres del candidato, en orden. Si existe algún carácter en el candidato –digamos en posición j– igual a Ki (sean letras o espacios) entonces se guarda la posición j en el “área de respuestas”, en la posición i. Si no existe ningún carácter igual a Ki entonces se pone el valor 0 en la posición i. Se debe tener cuidado con las letras repetidas (no contiguas, por supuesto) ya sea en el candidato o en ambos, candidato y llave buscada.
El área de respuesta, consistente de cuatro valores posicionales, es entonces evaluada para obtener la calificación del candidato con respecto a la llave buscada. Esta calificación es precisamente el máximo de las longitudes de las sucesiones estrictamente crecientes de valores posicionales (diferentes de 0) encontradas en el área de respuesta. Esta calificación es tal que una coincidencia perfecta entre un candidato y una llave arroja un valor igual a 4, mientras que un candidato que no tiene letras o espacios en común con la llave arroja un valor de 0. Si alguna letra, independientemente de su posición, aparece en ambos, candidato y llave, la calificación para ese candidato será al menos 1.
Al final de la búsqueda, solamente aquellos candidatos con la calificación más alta serán mostrados. Como siempre, una inicial correcta en alguno de los candidatos con mayor calificación eliminará a todos los candidatos con igual calificación pero inicial incorrecta.
Ejemplos de recuperación de nombres mal tecleados
El caso más interesante de recuperación es cuando los registros producen una calificación de 3. Una calificación de 4 implica una concordancia perfecta para el apellido codificado, por lo que la rutina de nombre_mal_tecleado no se hubiera usado en este caso. Los siguientes ejemplos ilustran como se reconocen y recuperan nombres mal tecleados con una calificación de 3; estos ejemplos surgieron con un registro de 95 nombres:
PROPORCIONADO RECUPERADO
McGHONE, W. McKONE, W.
BUCKMANN, R. BUCKMAN, R.
CURBIE, D. KIRBY, C.
IGGINS, R. HIGGINS, R.
ANGREIFF, SINGER, A.
Se tecleó BARTON. Como no había Barton en los registros, los nombres de MARTIN y MARTINEZ fueron recuperados. Esto se considera una buena elección.
Los siguientes errores también se recuperarían con una calificación igual a 3: McGUINNESS por MAGGINES, y LESTER por LEICESTER. De igual manera, el nombre oriental LU se hubiera recuperado con una calificación de 3 si se hubiera tecleado como ROO.
Con una calificación de 2, obviamente, se esperaría obtener una mayor cantidad de candidatos en la lista resultante. Tal valor de calificación no se requerirá normalmente.
Extensiones
También se puede implementar un proceso con un valor máximo más bajo para permitir la extracción de registros ocultos por un nombre correcto pero con una codificación igual a la errónea del nombre buscado. Por ejemplo, si LAVIGNE, A. está en el inventario pero se busca como LEVINE, A. y, además, existe un legítimo LEVINE, S. en el inventario, el procedimiento descrito antes siempre regresará LEVINE, S. con una calificación de 4. Para recuperar LAVIGNE, la calificación máxima se debería topar a 3.
Esta técnica de compresión, combinada con un sistema de puntuación y procedimientos de búsqueda secundarios para números telefónicos es una buena solución para el problema práctico de recuperación de nombres erróneos en un inventario de reservaciones aéreas, donde la población en donde se busca es del orden de los cientos.
Referencias
Davidson, Leon. Retrieval of misspelled names in an airlines passenger record system. CACM v5-3, (marzo 1962), 169-171, http://doi.acm.org/10.1145/366862.366913