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

En un artículo anterior, le di una introducción a los algoritmos fonéticos y le mostré su variedad. Con más detalle, echamos un vistazo a la distancia de edición, que es...

En un artículo anterior os hice una introducción a los algoritmos fonéticos, y os muestro su variedad. Con más detalle echamos un vistazo a la distancia de edición, que también se conoce como Distancia de Levenstein. Este algoritmo fue desarrollado para calcular el número de sustituciones de letras para pasar de una palabra a la siguiente.

Como ya habrás 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. Como ejemplo, una implementación de Soundex es parte de todos los lenguajes de programación, así como de los sistemas de administración de bases de datos (DBMS) como Oracle, MySQL y PostgreSQL. En contraste, tanto Metaphone como el códice Match Rating rara vez se usan y, en la mayoría de los casos, requieren la instalación de 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 cómo usar sus peculiaridades para lograr un mejor resultado de comparación que usar los algoritmos individuales por separado. Para implementar esto, entra en juego la biblioteca basada en Python llamada Búsqueda avanzada de AdvaS en SourceForge. AdvaS ya incluye un método para calcular varios códigos fonéticos para 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 de longitud variable que consiste solo en 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 se escriban. En realidad, esto ayuda a detectar palabras que suenan de forma similar incluso si se escriben de forma diferente, sin importar si se hace a propósito o por accidente.

Cada uno de estos algoritmos se diseñó con un determinado lenguaje o propósito en mente, y no encajan en los demás idiomas exactamente de la misma manera. Tenga en cuenta que las representaciones no siempre son óptimas, sino que pretenden ajustarse lo más posible. Como ejemplo, el algoritmo Soundex original se enfoca en el idioma inglés, mientras que Kölner Phonetik se enfoca en el idioma alemán, que contiene diéresis y otros caracteres especiales como "ß".

A continuación, echaremos un breve vistazo a una selección de algoritmos fonéticos. Para obtener una descripción más detallada, siga los enlaces que figuran 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 de idiomas 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. Fue ampliamente utilizado para detectar apellidos de sonido similar como parte del censo de EE. UU. en la década de 1930.

Metáfono

Desarrollado por Lawrence Phillips en 1990, Metáfono también fue diseñado pensando en el idioma inglés. Trató de mejorar el mecanismo de Soundex usando 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 producen las dos primeras versiones. Metaphone 3 está disponible como software comercial y es compatible con la pronunciación en alemán y 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 para Soundex, Metaphone y Double Metaphone por el nombre "Knuth". Además, la figura muestra una selección de palabras que se representan de la misma manera y tienen el mismo código fonético ("Gleiche Kodierung wie"). Cuanto más distintivo sea el algoritmo, menor será el número de palabras con el mismo código fonético.

Representaciones de Soundex, Metaphone y Double Metaphone{.img-responsive}

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 forman parte del Paquete de fonética. Hay implementaciones comerciales disponibles para los lenguajes de programación C++, C#, Java, Python y Ruby.

Caverfono

El algoritmo Caverfono fue creado por David Hood en 2002. Una versión revisada fue lanzada en 2004. El entorno del proyecto es el [Proyecto Caversham](http:// caversham.otago.ac.nz/about/project.php) en la Universidad de Otago, Nueva Zelanda. El trasfondo del algoritmo era ayudar a hacer coincidir los datos de las listas electorales entre finales del siglo XIX y principios del siglo XX, donde los nombres solo debían estar en una “forma comúnmente reconocible”. El algoritmo lleva el nombre del municipio en el que se encuentra la universidad y está optimizado para combinaciones de letras específicas del idioma en el que 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 {#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 los nombres estadounidenses. Entonces, los dos nombres "Webberley" y "Wibberley" están representados por el código fonético "WABARLY".

Fonética de Colonia {#fonética klner}

Basado en el algoritmo Soundex, en 1969 Hans Joachim Postel desarrolló la Kölner Fonética. Está dirigido al idioma alemán y luego se convirtió en parte de los sistemas SAP. La representación fonética es simplemente una cadena de dígitos de longitud variable.

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

Enfoque de calificación de coincidencias

El códice Enfoque de clasificación de coincidencias (MRA) fue desarrollado en 1977 por Western Airlines. La idea era detectar nombres homófonos en 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 método de Python en el [Módulo de medusas](https:// pypi.python.org/pypi/jellyfish).

Implementación

El cálculo del grado de similitud se basa en tres vectores denominados codeList1, codeList2 y 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 paquete NumPy. 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 mayor ni menor que eso. En caso de que esto suceda, los valores individuales del vector tres deben normalizarse de antemano.

La figura 2 muestra los tres vectores.

Phonetic algorithm vectors{.img-responsive}

Figura 2 Tres vectores utilizados para guardar 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:

1
2
3
4
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 visto desde el punto de vista del algoritmo.

El siguiente código Python usa la clase Phonetics del módulo AdvaS, así como el módulo NumPy. La definición de la función de Levenshtein es similar al artículo anterior sobre distancia Levenstein, 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 la salida estándar.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
# -*- 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 está almacenado en el archivo phonetics-vector.py, el resultado es el siguiente:

1
2
3
4
5
6
7
8
$ 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 demuestra 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 puede que aún no sea el óptimo. El vector de peso 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 ponderación adecuada por idioma. Además, la lista de algoritmos que se tienen en cuenta se puede ampliar fácilmente.

Agradecimientos

El autor desea agradecer a Geroldo Rupprecht y Zoleka Hatitongwe por su apoyo durante la preparación del artículo. .