Similitud fon茅tica de palabras: un enfoque vectorizado en Python

    En un art铆culo anterior les di una introducci贸n a los algoritmos fon茅ticos y les mostraba su variedad. Con m谩s detalle, echamos un vistazo a la distancia de edici贸n, que tambi茅n se conoce como Distancia de Levenshtein. Este algoritmo fue desarrollado para calcular el n煤mero de sustituciones de letras para pasar de una palabra a la siguiente.

    Como ya habr谩 notado en el art铆culo anterior, existen diferentes m茅todos para calcular el sonido de una palabra como Soundex, Metaphone y el c贸dice Match Rating. Algunos de ellos son m谩s comunes que otros. Por ejemplo, una implementaci贸n de Soundex es parte de todos los lenguajes de programaci贸n, as铆 como de los sistemas de gesti贸n de bases de datos (DBMS) como Oracle, MySQL y PostgreSQL. Por el contrario, tanto Metaphone como el c贸dice Match Rating se utilizan con poca frecuencia y, en la mayor铆a de los casos, es necesario instalar bibliotecas de software adicionales en su sistema.

    Visto como una propuesta, este art铆culo demuestra c贸mo combinar diferentes algoritmos fon茅ticos en un enfoque vectorizado y utilizar sus peculiaridades para lograr un mejor resultado de comparaci贸n que usar los algoritmos individuales por separado. Para implementar esto, la biblioteca basada en Python llamada B煤squeda avanzada de AdvaS en SourceForge entra en juego. AdvaS ya incluye un m茅todo para calcular varios c贸digos fon茅ticos de una palabra en un solo paso.

    Algoritmos fon茅ticos explicados

    Para ser m谩s precisos, cada uno de estos algoritmos crea una representaci贸n fon茅tica espec铆fica de una sola palabra. Por lo general, dicha representaci贸n es una cadena de longitud fija o variable que consta solo de letras, o una combinaci贸n de letras y d铆gitos. La estructura detallada de la representaci贸n depende del algoritmo. En realidad, si dos representaciones, calculadas con el mismo algoritmo, son similares, las dos palabras originales se pronuncian de la misma manera sin importar c贸mo est茅n escritas. En realidad, esto ayuda a detectar palabras que suenan similares incluso si se escriben de manera diferente, sin importar si se hacen a prop贸sito o por accidente.

    Cada uno de estos algoritmos se dise帽贸 con un determinado idioma o prop贸sito en mente, y no encajan exactamente en los dem谩s idiomas de la misma manera. Tenga en cuenta que las representaciones no siempre son 贸ptimas, sino que est谩n destinadas a ajustarse lo m谩s posible. Como ejemplo, el algoritmo original de Soundex se centra en el idioma ingl茅s, mientras que K枚lner Phonetik se centra en el idioma alem谩n, que contiene di茅resis y otros caracteres especiales como una “脽”.

    A continuaci贸n, veremos brevemente una selecci贸n de algoritmos fon茅ticos. Para obtener una descripci贸n m谩s detallada, siga los enlaces que se proporcionan a continuaci贸n. Tenga en cuenta que el nivel de documentaci贸n de los algoritmos es bastante diferente, desde muy detallado hasta bastante escaso.

    Soundex

    La representaci贸n resultante del algoritmo Soundex es una palabra de cuatro letras. Esto se basa en un car谩cter seguido de tres d铆gitos num茅ricos. Como ejemplo, el valor Soundex de “Knuth” es K530, que es similar a “Kant”. Esta simplicidad conduce a bastantes representaciones enga帽osas. Aunque, en general, los resultados son bastante buenos. Originalmente dise帽ado para ingl茅s americano, Soundex est谩 disponible hoy en diferentes versiones espec铆ficas del idioma como franc茅s, Alem谩n y hebreo.

    Desarrollado por Robert C. Russell y Margaret King Odell a principios del siglo XX, Soundex fue dise帽ado pensando en el idioma ingl茅s. Se us贸 ampliamente para detectar apellidos que suenan similares como parte del censo de EE. UU. En la d茅cada de 1930.

    Metafono

    Desarrollado por Lawrence Phillips en 1990, Metafono tambi茅n se dise帽贸 teniendo en cuenta el idioma ingl茅s. Trat贸 de mejorar el mecanismo de Soundex mediante el uso de informaci贸n sobre variaciones e inconsistencias en la ortograf铆a / pronunciaci贸n en ingl茅s para producir codificaciones m谩s precisas. Como resultado, la representaci贸n fon茅tica es una palabra de longitud variable basada en las 16 consonantes “0BFHJKLMNPRSTWXY”. Las 5 vocales “AEIOU” tambi茅n est谩n permitidas, pero solo al comienzo de la representaci贸n.

    La descripci贸n original del algoritmo Metaphone era bastante inexacta y condujo al desarrollo de Double Metaphone y Metaphone 3. Este 煤ltimo puede corregir miles de errores de codificaci贸n que se producen en las dos primeras versiones. Metaphone 3 est谩 disponible como software comercial y es compatible con la pronunciaci贸n tanto en alem谩n como en espa帽ol.

    La Figura 1 a continuaci贸n es una captura de pantalla tomada de un Sitio web de genealog铆a holandesa, y muestra las diferentes representaciones de Soundex, Metaphone y Double Metaphone para el nombre “Knuth”. Adem谩s, la figura muestra una selecci贸n de palabras que est谩n representadas de la misma forma y tienen el mismo c贸digo fon茅tico (“Gleiche Kodierung wie”). Cuanto m谩s distintivo sea el algoritmo, mejor ser谩 la menor cantidad de palabras con el mismo c贸digo fon茅tico.

    Figura 1

    El algoritmo Metaphone es una parte est谩ndar de solo unos pocos lenguajes de programaci贸n, por ejemplo PHP. Para Python, tanto Metaphone como Double Metaphone son parte del Paquete de fon茅tica. Las implementaciones comerciales est谩n disponibles para los lenguajes de programaci贸n C ++, C #, Java, Python y Ruby.

    Caverphone

    los Caverphone El algoritmo fue creado por David Hood en 2002. Una versi贸n revisada fue lanzada en 2004. El entorno del proyecto es el Proyecto Caversham en la Universidad de Otago, Nueva Zelanda. El trasfondo del algoritmo fue ayudar a comparar los datos de los registros electorales entre finales del siglo XIX y principios del siglo XX, donde los nombres solo ten铆an que estar en una “forma com煤nmente reconocible”. El algoritmo lleva el nombre del municipio donde se encuentra la universidad y est谩 optimizado para combinaciones de letras espec铆ficas del idioma donde se llev贸 a cabo la investigaci贸n de los nombres.

    De forma predeterminada, una representaci贸n de Caverphone consta de seis caracteres y n煤meros. Algunas implementaciones permiten extender la longitud hasta diez caracteres y n煤meros. Como ejemplo, “Thompson” se transforma en el c贸digo “TMPSN1”. Actualmente, el algoritmo est谩 disponible para C #, Python (versi贸n revisada), Java (tanto la versi贸n original como la revisada) y R.

    Sistema de identificaci贸n e inteligencia del estado de Nueva York

    Este algoritmo fue desarrollado en la d茅cada de 1970 como parte del Sistema de identificaci贸n e inteligencia del estado de Nueva York (NYSIIS). Todav铆a en uso hoy en d铆a, se dice que su calidad est谩 cerca del algoritmo Soundex.

    El dise帽o se optimiz贸 para coincidir espec铆ficamente con nombres estadounidenses. Entonces, los dos nombres “Webberley” y “Wibberley” est谩n representados por el c贸digo fon茅tico “WABARLY”.

    K枚lner Phonetik

    Basado en el algoritmo Soundex, en 1969 Hans Joachim Postel desarroll贸 el K枚lner Phonetik. Est谩 dirigido al idioma alem谩n y luego se convirti贸 en parte de los sistemas SAP. La representaci贸n fon茅tica es solo una cadena de d铆gitos de longitud variable.

    Actualmente, se conocen implementaciones en Perl, PHP y JavaScript.

    Enfoque de clasificaci贸n de partidos

    los Enfoque de clasificaci贸n de coincidencias (MRA) fue desarrollado en 1977 por Western Airlines. La idea era detectar nombres hom贸fonos en las listas de pasajeros con un fuerte enfoque en el idioma ingl茅s. Como ejemplo, la representaci贸n de “Smith” es “SMTH”, mientras que “Smyth” est谩 codificada por “SMYTH”.

    Actualmente, MRA est谩 disponible como Implementaci贸n de C # desde un sitio web archivado y como un m茅todo de Python en el M贸dulo medusas.

    Implementaci贸n

    El c谩lculo del grado de similitud se basa en tres vectores denominados como codeList1, codeList2y weight en la lista de c贸digo fuente a continuaci贸n. En Python, un vector se puede implementar como una matriz, por ejemplo, usando el NumPy paquete. Los vectores n煤mero uno y dos representan el c贸digo fon茅tico de las dos palabras diferentes. El vector n煤mero tres representa el peso espec铆fico del algoritmo y contiene un valor fraccionario entre 0 y 1 para describir ese peso. El total de los valores individuales del vector tres es el valor exacto de 1, y no debe ser menor ni mayor que ese. En caso de que esto suceda, los valores individuales del vector tres deben normalizarse de antemano.

    La Figura 2 muestra los tres vectores.

    Figura 2 Tres vectores usados 鈥嬧媝ara mantener los datos

    El grado de similitud calculado entre las dos palabras es un valor decimal basado en un c谩lculo por algoritmo fon茅tico (subtotal). Cada subtotal es el producto de la distancia de Levenshtein entre la representaci贸n fon茅tica espec铆fica de codeList1 y codeList2, y el peso correspondiente para el algoritmo fon茅tico espec铆fico. Para NYSIIS, se calcula de la siguiente manera:

    nysiis = Levenshtein(codeList1["nysiis"], codeList2["nysiis"]) * weight["nysiis"]
           = Levenshtein("Knatt", "Kand") * 0.1
           = 3 * 0.1
           = 0.3
    

    Como se describe en el art铆culo anterior, la distancia de Levenshtein devuelve el n煤mero de ediciones necesarias para pasar de una palabra a la siguiente. En nuestro caso las dos palabras son c贸digos fon茅ticos que se calculan por algoritmo. Cuanto menor sea el n煤mero de cambios (ediciones) entre los c贸digos, mayor ser谩 el nivel de similitud fon茅tica entre las palabras originales como se ve desde el punto de vista del algoritmo.

    El siguiente c贸digo de Python usa la clase Fon茅tica del m贸dulo AdvaS, as铆 como el m贸dulo NumPy. La definici贸n de la funci贸n de Levenshtein es similar a la del art铆culo anterior sobre la distancia de Levenshtein, y solo se incluye para completar. A continuaci贸n, los tres vectores se inicializan como se muestra en la Figura 2, los subtotales se calculan en un bucle y el total se imprime en stdout.

    # -*- coding: utf-8 -*-
    
    from phonetics import Phonetics
    import numpy as np
    
    def levenshtein(seq1, seq2):  
        size_x = len(seq1) + 1
        size_y = len(seq2) + 1
        matrix = np.zeros ((size_x, size_y))
        for x in xrange(size_x):
            matrix [x, 0] = x
        for y in xrange(size_y):
            matrix [0, y] = y
    
        for x in xrange(1, size_x):
            for y in xrange(1, size_y):
                if seq1[x-1] == seq2[y-1]:
                    matrix [x,y] = min(
                        matrix[x-1, y] + 1,
                        matrix[x-1, y-1],
                        matrix[x, y-1] + 1
                    )
                else:
                    matrix [x,y] = min(
                        matrix[x-1,y] + 1,
                        matrix[x-1,y-1] + 1,
                        matrix[x,y-1] + 1
                    )
        return (matrix[size_x - 1, size_y - 1])
    
    # -- initialize phonetics object
    
    word1 = Phonetics("Knuth")
    word2 = Phonetics("Kant")
    print ("Comparing %s with %s" % (word1.getText(), word2.getText()))
    
    # -- phonetic code
    codeList1 = word1.phoneticCode()
    codeList2 = word2.phoneticCode()
    
    # -- weight
    weight = {
        "soundex": 0.2,
        "caverphone": 0.2,
        "metaphone": 0.5,
        "nysiis": 0.1
    }
    
    # -- algorithms
    algorithms = ["soundex", "caverphone", "metaphone", "nysiis"]
    
    # -- total
    total = 0.0
    for entry in algorithms:
        code1 = codeList1[entry]
        code2 = codeList2[entry]
        lev = levenshtein (code1, code2)
        currentWeight = weight[entry]
        print ("comparing %s with %s for %s (%0.2f: weight %0.2f)" % (code1, code2, entry, lev, currentWeight))
        subtotal = lev * currentWeight
        total += subtotal
    
    print ("total: %0.2f" % total)
    

    Suponiendo que el c贸digo fuente se almacena en el archivo phonetics-vector.py, el resultado es el siguiente:

    $ python phonetics-vector.py
    Comparing Knuth with Kant
    comparing K530 with K530 for soundex (0.00: weight 0.20)
    comparing KNT1111111 with KNT1111111 for caverphone (0.00: weight 0.20)
    comparing n0h with nt for metaphone (2.00: weight 0.50)
    comparing Knatt with Kand for nysiis (3.00: weight 0.20)
    total: 1.60
    $
    

    Cuanto menor es el grado de similitud, m谩s id茅nticas son las dos palabras en t茅rminos de pronunciaci贸n. Como se demostr贸 en el ejemplo anterior “Knuth” y “Kant”, el valor calculado es 1,6 y bastante bajo.

    Conclusi贸n

    El enfoque explicado aqu铆 ayuda a encontrar una soluci贸n para equilibrar las peculiaridades de los diferentes m茅todos fon茅ticos. Hasta ahora, el primer resultado es prometedor, pero es posible que a煤n no sea 贸ptimo. El vector de ponderaci贸n se utiliza para regular la influencia de cada algoritmo fon茅tico espec铆fico. Se requiere m谩s investigaci贸n para encontrar la distribuci贸n de valor de peso adecuada por idioma. Adem谩s, la lista de algoritmos que se tienen en cuenta se puede ampliar f谩cilmente.

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *