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

S

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 ​​para 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.

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad