Автор оригинала: Frank Hofmann.
Фонетическое сходство слов: Векторизованный подход в Python
В более ранней статье Я дал вам введение в фонетические алгоритмы и показал их разнообразие. Более подробно мы рассмотрели расстояние редактирования, которое также известно как Расстояние Левенштейна . Этот алгоритм был разработан для того, чтобы вычислить количество буквенных замен, чтобы перейти от одного слова к другому.
Как вы, возможно, уже отмечали в предыдущей статье, существуют различные методы расчета звучания слова, такие как Soundex, Metaphone и Match Rating codex. Некоторые из них встречаются чаще, чем другие. Например, реализация Soundex является частью каждого языка программирования, а также систем управления базами данных (СУБД), таких как Oracle, MySQL и PostgreSQL. В отличие от этого, как Metaphone, так и Match Rating codex используются редко и в большинстве случаев требуют установки дополнительных программных библиотек в вашей системе.
Рассматриваемая как предложение, эта статья демонстрирует, как объединить различные фонетические алгоритмы в векторизованном подходе и использовать их особенности для достижения лучшего результата сравнения, чем использование отдельных алгоритмов по отдельности. Чтобы реализовать это, в игру вступает основанная на Python библиотека с именем AdvaS Advanced Search on SourceForge . AdvaS уже включает в себя метод, позволяющий вычислить несколько фонетических кодов для слова за один шаг.
Фонетические Алгоритмы Объяснены
Если быть более точным, каждый из этих алгоритмов создает определенное фонетическое представление одного слова. Обычно такое представление представляет собой либо строку фиксированной длины, либо строку переменной длины, состоящую только из букв, либо комбинацию букв и цифр. Детальная структура представления зависит от алгоритма. На самом деле, если два представления, вычисленные с помощью одного и того же алгоритма, похожи, то два исходных слова произносятся одинаково независимо от того, как они написаны. На самом деле это помогает обнаружить похожие по звучанию слова, даже если они написаны по-разному – независимо от того, сделано ли это намеренно или случайно.
Каждый из этих алгоритмов был разработан с определенным языком или целью в виду, и не вписываются друг в друга языки точно так же. Имейте в виду, что представления не всегда являются оптимальными, но предназначены для того, чтобы соответствовать как можно ближе. Например, оригинальный алгоритм Soundex фокусируется на английском языке, в то время как фонетика Кельнера фокусируется на немецком языке, который содержит умлауты и другие специальные символы, такие как “β”.
Далее мы кратко рассмотрим некоторые фонетические алгоритмы. Для более подробного описания перейдите по ссылкам, приведенным ниже. Имейте в виду, что уровень документирования алгоритмов довольно разный – от очень подробного до довольно скудного.
Soundex
Результирующее представление алгоритма Soundex представляет собой слово из четырех букв. Это основано на символе, за которым следуют три цифры. Например, значение Soundex “Knuth” равно K530, что аналогично “Kant”. Эта простота приводит к довольно многочисленным ошибочным представлениям. Хотя в целом результаты неплохие. Первоначально разработанный для американского английского языка, Soundex сегодня доступен в различных языковых версиях, таких как французский , немецкий и иврит.
Разработанный Робертом Расселом и Маргарет Кинг Оделл в начале 20-го века, Soundex был разработан с учетом английского языка. Он широко использовался для обнаружения похожих по звучанию фамилий в рамках переписи населения США в 1930-х годах.
Метафона
Разработанный Лоуренсом Филлипсом в 1990 году, Metaphone также был разработан с учетом английского языка. Он попытался усовершенствовать механизм Soundex, используя информацию о вариациях и несоответствиях в английском написании/произношении для получения более точных кодировок. В результате фонетическое представление представляет собой слово переменной длины, основанное на 16 согласных “0BFHJKLMNPRSTWXY”. 5 гласных “AEIOU” тоже разрешены, но только в начале представления.
Первоначальное описание алгоритма Метафона было довольно неточным и привело к разработке как Двойного Метафона, так и Метафона 3. Последний может исправить тысячи ошибок, которые были произведены первыми двумя версиями. Metaphone 3 доступен в качестве коммерческого программного обеспечения и поддерживает как немецкое, так и испанское произношение.
На рисунке 1 ниже приведен скриншот , взятый с сайта голландской генеалогии , и показаны различные представления для Soundex, Metaphone и Double Metaphone для имени “Knuth”. Кроме того, на рисунке показана подборка слов, которые представлены одинаково и имеют одинаковый фонетический код (“Gleiche Kodierung wie”). Чем более своеобразен алгоритм, тем меньше слов с одинаковым фонетическим кодом лучше.
Рисунок 1
Алгоритм Metaphone является стандартной частью только нескольких языков программирования, например PHP . Для Python как Метафона, так и Двойной метафон являются частью пакета Фонетика . Коммерческие реализации доступны для языков программирования C++, C#, Java, Python и Ruby.
Каверфон
Алгоритм Caverphone был создан Дэвидом Худом в 2002 году. Пересмотренная версия была выпущена в 2004 году. Проектная среда-это проект |/Caversham Project в Университете Отаго, Новая Зеландия. Основой для алгоритма была помощь в сопоставлении данных списков избирателей между концом 19-го и началом 20-го века, где имена должны были быть только в “общепризнанной форме”. Алгоритм назван в честь муниципалитета, в котором находится университет, и оптимизирован для специфичных для языка буквосочетаний, где проводилось исследование названий.
По умолчанию представление Caverphone состоит из шести символов и цифр. Некоторые реализации позволяют увеличить длину до десяти символов и цифр. В качестве примера “Томпсон” преобразуется в код “TMPSN1”. В настоящее время алгоритм доступен для C#, Python (пересмотренная версия), Java (как оригинальная, так и пересмотренная версия) и R.
Система идентификации и разведки штата Нью-Йорк
Этот алгоритм был разработан в 1970-х годах в рамках системы идентификации и разведки штата Нью-Йорк (NYSIS). Говорят, что его качество, все еще используемое сегодня, близко к алгоритму Soundex.
Дизайн был оптимизирован специально под американские названия. Итак, два имени “Уэбберли” и “Уибберли” представлены фонетическим кодом “УОБАРЛИ”.
Кельнская фонетика
Основываясь на алгоритме Soundex, в 1969 году Ганс Иоахим Постель разработал фонетику Кельнера . Он ориентирован на немецкий язык, а позже стал частью систем SAP. Фонетическое представление-это просто строка цифр переменной длины.
В настоящее время известны реализации на Perl, PHP и JavaScript.
Подход к Оценке Соответствия
Кодекс Match rating approach (MRA) был разработан в 1977 году компанией Western Airlines. Идея состояла в том, чтобы обнаружить гомофонные имена в списках пассажиров с сильным акцентом на английский язык. Например, представление для “Smith” – это “SMITH”, тогда как “Smith” кодируется “SMYTH”.
В настоящее время MRA доступен как реализация C# с архивного веб-сайта и как метод Python в модуле Jellyfish .
Реализация
Расчет степени сходства основан на трех векторах, обозначенных как список кодов 1 , список кодов 2 и вес в приведенном ниже списке исходного кода. В Python вектор может быть реализован в виде массива, например, с помощью пакета NumPy . Векторы номер один и два представляют фонетический код для двух разных слов. Вектор номер три представляет определенный вес алгоритма и содержит дробное значение от 0 до 1, чтобы описать этот вес. Сумма единичных значений вектора три является точным значением 1 и не должна быть ни ниже, ни выше этого. В этом случае единичные значения вектора три должны быть предварительно нормализованы.
На рис. 2 показаны три вектора.
Рисунок 2 Три вектора, используемые для хранения данных
Вычисленная степень сходства между двумя словами представляет собой десятичное значение, основанное на расчете по фонетическому алгоритму (промежуточный итог). Каждый промежуточный итог является произведением расстояния Левенштейна между конкретным фонетическим представлением списка кодов 1 и списка кодов 2 и соответствующим весом для конкретного фонетического алгоритма. Для NYSIS он рассчитывается следующим образом:
nysiis = Levenshtein(codeList1["nysiis"], codeList2["nysiis"]) * weight["nysiis"]
= Levenshtein("Knatt", "Kand") * 0.1
= 3 * 0.1
= 0.3
Как описано в предыдущей статье, расстояние Левенштейна возвращает количество правок, необходимых для перехода от одного слова к другому. В нашем случае эти два слова являются фонетическими кодами, которые вычисляются по алгоритму. Чем меньше количество изменений (правок) между кодами, тем выше уровень фонетического сходства между исходными словами с точки зрения алгоритма.
Приведенный ниже код Python использует класс Phonetics из модуля AdvaS, а также модуль NumPy. Определение функции Левенштейна аналогично предыдущей статье о Расстоянии Левенштейна и просто включено для полноты картины. Затем три вектора инициализируются, как показано на рисунке 2 , промежуточные итоги вычисляются в цикле, а итоговая сумма выводится в 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)
Предположим, что исходный код хранится в файле phonetics-vector.py результат выглядит следующим образом:
$ 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 $
Чем меньше степень сходства, тем более идентичны эти два слова с точки зрения произношения. Как показано в приведенном выше примере “Кнут” и “Кант”, расчетное значение составляет 1,6, причем довольно низкое.
Вывод
Описанный здесь подход помогает найти решение, позволяющее сбалансировать особенности различных фонетических методов. Пока что первый результат многообещающий, но, возможно, еще не оптимальный. Весовой вектор используется для регулирования влияния каждого конкретного фонетического алгоритма. Необходимы дальнейшие исследования, чтобы найти соответствующее распределение весовых значений по языкам. Кроме того, список алгоритмов, которые принимаются во внимание, может быть легко расширен.
Признание
Автор хотел бы поблагодарить Герольда Рупрехта и Золеку Хатитонгве за их поддержку при подготовке статьи.