Лекция
Привет, Вы узнаете о том , что такое metaphone, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое metaphone, soundex, approximate string matching, fuzzy string searching, caverphone, double metaphone, daitch-mokotoff soundex, nysiis, metaphone 3 , настоятельно рекомендую прочитать все из категории Обработка естественного языка.
При использовании алгоритмов текстового майнинга достаточно часто на практике возникают опечатки, один из способов борьбы с ними это использование триграмм. Недостаток этого подхода в том, что он плохо работает со словами короче 5-7 символов. Альтернативный способ — это применение фонетических алгоритмов, которые сопоставляют двум словам со схожим произношением одинаковые коды, что позволяет осуществлять сравнение и индексацию множества таких слов на основе их фонетического сходства.
Рассмотрим наиболее известные алгоритмы, такие как Soundex, daitch-mokotoff soundex , NYSIIS, Metaphone, Double Metaphone, русский Metaphone, Caverphone.
Soundex - это фонетический алгоритм индексации имен по звуку, как произносится в английском языке. Цель состоит в том, чтобы имена с одинаковым произношением были закодированы в одно и то же представление, чтобы их можно было сопоставить, несмотря на незначительные различия в написании.
Soundex — это алгоритм для кодирования имен собственных. Его создали в 1918–1922 гг. в США Роберт Расселл и Маргарет Кинг Оделл, чтобы облегчить поиск похоже звучащих фамилий. В середине XX века Soundex широко использовался в США при анализе результатов переписей населения 1890–1920 гг. Ниже дан пример карточки с данными переписи населения 1910 г. Здесь вы видите, что код Soundex для фамилии Wilson выглядит как W425:
Двум словам, имеющим схожее произношение, соответствует один и тот же ключ soundex. Это свойство может быть использовано, например, при поиске по базе данных, когда известно произношение слова и неизвестно его написание. Данная функция возвращает строку из 4 символов, начинающуюся с буквы.
Данная реализация функции soundex описана Дональдом Кнутом (Donald Knuth) в книге «The Art Of Computer Programming, vol. 3: Sorting And Searching», Addison-Wesley (1973), стр. 391-392.
Если вы хотите реализовать поиск и хотиет внедрить опцию «Возможно вы имели ввиду» как в гугле . Для этого в словарь ispell словоформ добавляем поле, содержащее metaphone() или soundex() ключ, а при поиске вычисляем ключи искомых слов, и если самих слов в базе словаря нет, вычисляем ключи для искомых слов и предлагаем похожее из базы.
В этом примере совершенно два разных слова green (зеленый) и grin (усмешка) дадут один и тот же soundex ключ, потому что произносятся одинаково.
soundex — Возвращает ключ soundex для строки
После выполнения операции «класиво летет» картина следующая:
И это лучшее что мне удалось найти по этой теме.
Может быть ктото знает какие-либо более законченные решения русской реализации этой функции?
Одним из таких алгоритмов является Soundex, который устанавливает одинаковый код вида D321 для слов, имеющих схожее звучание в английском языке. Soundex был разработан Робертом Расселом и Маргарет Кинг Оделл и запатентован в 1918 и 1922 годах. Этот алгоритм стал популярным в 1960-х годах, после того как стал темой нескольких статей в журналах «Communications of the Association for Computing Machinery» и «Journal of the Association for Computing Machinery» и был опубликован в книге Дональда Кнута.
Одним из первых был алгоритм Soundex, изобретенный еще в 10-x годах прошлого века Робертом Расселом. Этот алгоритм (а точнее, его американская версия) сопоставляет словам численный индекс вида A126. Принцип его работы основан на разбиении согласных букв на группы с порядковыми номерами, из которых затем и составляется результирующее значение. Позднее также был предложен ряд улучшений.
Первая буква сохраняется, последующие буквы сопоставляются цифрам по таблице. Символы, не представленные в таблице (а это все гласные и некоторые согласные), игнорируются. Смежные символы, или символы, разделенные буквами H или W, входящие в одну и ту же группу, записываются как один. Результат обрезается до 4 символов. Недостающие позиции заполняются нулями. Несложно заметить, что после всех этих процедур остается всего лишь 7 тысяч различных вариаций такого кода, что влечет за собой множество совершенно ничем не похожих друг на друга слов, имеющих одинаковый Soundex-код. Таким образом, результат в большинстве случаев включает в себя большое количество «ложноположительных» значений.
В улучшенной версии, как можно заметить, буквы разбиты на большее количество групп. Помимо этого, никакого особого внимания буквам H и W не уделяется, они просто игнорируются. Кроме того, никаких операций с длиной результата не производится — код не имеет фиксированной длины и не обрезается.
Давайте разберемся как работает оригинальная версия алгоритма:
1. Запоминаем первую букву. Удаляем все ‘h’ и ‘w’, за исключением первой буквы слова;
2. Согласные заменяем на цифры от 1 до 6, причем похожим по звучанию буквам соответствуют одинаковые цифры:
3. Любая последовательность одинаковых цифр сокращается до одной такой цифры.
4. Удаляем все a, e, i, o, u, y, за исключением первой буквы слова.
5. Заменяем первый символ буквой, запомненной на шаге 1, делая ее заглавной.
6. Итоговая строка обрезается до первых четырех символов. Если длина строки меньше требуемой, недостающие символы заменяются знаком 0.
Таким образом для слова Morphs алгоритм сгенерирует код M612. Несложно заметить, что после всех этих процедур остается меньше 10 тысяч различных вариаций такого кода, что влечет за собой множество совершенно ничем не похожих друг на друга слов, имеющих одинаковый Soundex-код. Таким образом, результат в большинстве случаев включает в себя большое количество ложных срабатываний.
Для уменьшения ложных срабатываний был создан улучшенный алгоритм Soundex, который в отличие от оригинального использует следующую таблицу кодирования символов:
Таким образом число кодов увеличивается почти до 19 тысяч. Более того снимается ограничение на длину кода (код не дополняется символами 0 и не удаляются все символы после 4-ого).
С применение улучшенного алгоритма Soundex слово Morphs будет закодировано в M913.
Soundex хорошо работает с английским языком, остается вопрос можно ли его использовать для русского языка. Оказывается можно. Для этого перед вычислением кода оригинальным или улучшенным алгоритмом нужно выполнить транслитерацию исходного слова на русском языке.
Задание 1 Дан список фамилий и соответствующих им кодов Soundex в перепутанном порядке. Некоторые символы пропущены:
S312, T␣6␣, ␣5␣3, C42␣, T520, L␣42, A536, C155, ␣623, S356, ␣252, ␣152, ␣330, A251, A400, L2␣0
Задание 2. Опишите пошагово, как генерируется код Soundex.
Задание 3. Установите соответствия между фамилиями и кодами Soundex и вставьте пропущенные символы.
Задание 4. Постройте коды Soundex для следующих фамилий: Ferguson, Fitzgerald, Hamnett, Keefe, Maxwell, Razey, Shaw, Upfield.
Подсказка - Каждый код состоит из буквы и трех цифр. Буква повторяет первую букву фамилии, а цифры кодируют согласные, которые содержатся в этой фамилии дальше.
Решение
Все коды Soundex состоят из латинской буквы и трех цифр. Нетрудно догадаться, почему код для фамилии Wilson начинается на W: потому что это первая буква этой фамилии.
После того как стало ясно, что первая буква сохраняется, задача распадается на шесть небольших задач с перепутанными соответствиями:
Chapman, Colquhoun
C42␣, C155
Stanmore, Stubbs
S312, S356
Buckingham, Evans, Fairwright, Kingscott, Whytehead
␣5␣3, ␣623, ␣252, ␣152, ␣330
Вспомним, что Soundex — алгоритм, разработанный для поиска похоже звучащих слов. Вероятно, цифры должны кодировать какие-то характерные звучания. Можно выдвинуть гипотезу, что они соответствуют согласным буквам, которые встречаются в фамилии. Правда, цифр только шесть — значит, одна и та же цифра кодирует целые группы согласных.
Эти группы таковы:
| bpv(f) | cgjkqs(xz) | dt | l | mn | r |
| 1 | 2 | 3 | 4 | 5 | 6 |
Классификация букв в Soundex более или менее соответствует классификации звуков по тому, как они произносятся: в группу 1 входят согласные, произносимые с участием губ; в группу 2 — согласные, произносимые с помощью задней части языка, и свистящие; в группу 3 — переднеязычные смычные (d и t); в группу 5 — носовые. Исходя из этого, можно распределить по группам и те буквы, которые мы не видели в условии (в таблице они даны в скобках). Буква f попадет в группу 1 к губным согласным (там уже находится v, пара f по глухости-звонкости), а x и z — в группу 2 (x состоит из k и s, которые находятся в группе 2, а z — звонкая пара к s). Буквы h и w в эту таблицу не вошли: они при генерации кода Soundex игнорируются. То же касается буквы y, которая в английском языке считается гласной.
Можно заметить, что сочетаниям согласных из одной группы соответствует только одна цифра в коде. Например, из данных в условии кодов фамилии Kingscott может соответствовать только ␣5␣3, в котором 5 отвечает за n, 3 — за t, а цифра в середине должна отвечать за g, s и c (очевидно, это будет цифра 2).
Нули в коде соответствуют случаям, когда согласных не хватило на то, чтобы заполнить три позиции. Например, можно установить, что Allaway — это A400, где двум l соответствует 4, а a, w, a и y в кодировании не участвуют.
1. Обобщая все эти наблюдения, можно построить алгоритм кодирования. Важно обратить внимание на порядок операций, чтобы он позволил получить все коды без ошибок.
2. Оставить первую букву неизменной.
4. Заменить все согласные на цифры (буквы, наиболее частые чтения которых похожи, объединяются в группы):
| bfpv | cgjkqsxz | dt | l | mn | r |
| 1 | 2 | 3 | 4 | 5 | 6 |
5. Две или более одинаковых цифры подряд сократить до одной.
6. Оставить только первые три цифры или дописать нули справа, чтобы длина кода составила одну букву и три цифры.
Ответ на задание 2 (восстановленные символы подчеркнуты).
Ответ на задание 3.
Ferguson: F622, Fitzgerald: F326, Hamnett: H530, Keefe: K100, Maxwell: M240, Razey: R200, Shaw: S000, Upfield: U143.
Задача, для решения которой использовался (и порой продолжает использоваться в наши дни) алгоритм Soundex, в общем виде называется нечетким поиском (approximate string matching, fuzzy string searching).
Умение понимать, что два языковых выражения эквивалентны, — важная часть владения человеческим языком. Это умение может проявляться на разных уровнях. Например, на уровне семантики (значений слов) и синтаксиса (связей между словами в словосочетании и предложении) носитель русского языка легко понимает, что фразы Стометровую дистанцию он проплыл кролем за 45 секунд, На сто метров кролем у него ушло 45 секунд и Стометровку он проплыл кролем за ¾ минуты (Апресян 1995: I, 12) значат одно и то же. Точно так же и на уровне букв мы легко понимаем, что Муравьева и Муравьева — это одна и та же фамилия, а Наталия и Наталья — одно и то же имя (хотя в ситуациях, когда хочется придраться, мы можем притворно говорить что-то вроде «Ну как же, здесь написано Наталья Муравьева, а у вас в паспорте — Наталия Муравьева»). Но автоматизировать такое базовое для нас умение — понимать эквивалентность не совпадающих точно слов и выражений — задача очень сложная.
Такие несовпадения на практике встречаются регулярно. Soundex изначально придумывался именно для сопоставления имен собственных, поскольку в начале XX века вариативность в написании имен собственных была гораздо выше, чем сейчас, — но и сейчас она не совсем сведена к нулю. Так, в книге (Lisbach, Meyer 2013: 15) приводится пример двух вариантов записи информации об одном и том же человеке — например, со слуха в колл-центре и при переписывании с документов с разделением на поля:
| Kate Suzanne Jankowiz |
| Belrive Str. 20, 65920 Frankfurt am Main (Germany) |
| Catherine | Susan | Jennifer | Yankovits-Brunner | |
| 20 | Bellerivestrasse | Frankfurt/M | 65920 | DE |
Важное достоинство Soundex, которое во многом и обеспечило его популярность, — легкость в реализации: в частности, для этого алгоритма не нужен словарь. Soundex упоминается в классическом пособии «Искусство программирования» Дональда Кнута (Knuth 1998: 395–396). Правда, в первом издании (Knuth 1973: 391–392) автор еще не учел все тонкости и предлагал одновременно выкидывать гласные, h и w; тогда, например, Chapman дает не Chapman → Capman → Ca15a5 → C155, а Chapman → Cpmn → C155 → C15 → C150.
Soundex реализован в десятках языков программирования. Например, встроенная функция SOUNDEX есть в системе управления базами данных MySQL. А на Python 3 можно записать все содержание этой задачи в нескольких строчках (автор кода — Иван Держанский):
Недостатки Soundex лежат на поверхности. Иногда этот алгоритм неспособен обнаружить сходство между очень близкими фамилиями: например, Levinson получит код L152, а Lewinson — код L525. Кроме того, Soundex плохо работает в ситуациях, когда произношение сильно расходится с написанием, что в английском языке бывает нередко. Например, шотландская фамилия Colquhoun, данная в условии, читается примерно как Кэхун, а его код Soundex C425 отражает непроизносимые l (4) и q (2). Об этом говорит сайт https://intellect.icu . Другой вариант этой фамилии — Colhoun (вспомним капитана Кассия Колхауна из «Всадника без головы» Майн Рида) — имеет другой код: получится C450. Впрочем, в таком написании обычно произносится л (Колхун), так что разные коды в данном случае — это не так уж и плохо.
Для решения задачи нечеткого поиска нередко используются и более продвинутые алгоритмы. Это могут быть как фонетические алгоритмы наподобие Soundex (например, Metaphone), так и совсем другие подходы — например, связанные с редакционным расстоянием, задача про которое уже публиковалась на нашем сайте.
Задача использовалась на XIII Международной олимпиаде по лингвистике в 2015 году в Благоевграде (Болгария).
Разработанный в 1970 году как часть системы «New York State Identification and Intelligence System», этот алгоритм дает несколько лучшие результаты относительно оригинального Soundex, используя более сложные правила преобразования исходного слова в результирующий код. Этот алгоритм разработан для работы именно с американскими фамилиями.
Алгоритм вычисления кода NYSIIS
Примеры
CASPARAVAS → Каспаравичус, Касперович, Каспирович.
CATNACAV → Катников, Цитников, Цотников.
LANSANC → Ленченко, Леонченко, Линченко, Лунченко, Лямзенко.
PRADSC → Приходский, Проходский, Прудский, Прудских, Прудской.
STADNACAV → Стадников.
NYSIIS преобразует к одному и тому же коду немногим более двух фамилий.
Этот алгоритм в 1985 году разработали два генеалога — Гарри Мокотофф и Рэнди Дэйч, стремясь достичь лучших, относительно оригинального Soundex, результатов при работе со восточно-европейскими (в том числе русскими) фамилиями.
Этот алгоритм имеет мало общего с оригинальным Soundex, разве что результатом все так же остается последовательность цифр, однако теперь первая буква также кодируется.
Он имеет значительно более сложные правила конверсии — теперь в формировании результирующего кода участвуют не только одиночные символы, но и последовательности из нескольких символов. Кроме того, результат вида 023689 обеспечивает около 600 тысяч различных вариаций кода, что вкупе с усложненными правилами уменьшает количество «лишних», т.е. «ложноположительных» слов в результирующем множестве.
Преобразования осуществляются по следующей таблице (порядок преобразований соответствует порядку буквосочетаний в таблице):
| Исходные буквосочетания | В начале | За гласной | Остальное |
| AI, AJ, AY, EI, EY, EJ, OI, OJ, OY, UI, UJ, UY | 0 | 1 | |
| AU | 0 | 7 | |
| IA, IE, IO, IU | 1 | ||
| EU | 1 | 1 | |
| A, UE, E, I, O, U, Y | 0 | ||
| J | 1 | 1 | 1 |
| SCHTSCH, SCHTSH, SCHTCH, SHTCH, SHCH, SHTSH, STCH, STSCH, STRZ, STRS, STSH, SZCZ, SZCS | 2 | 4 | 4 |
| SHT, SCHT, SCHD, ST, SZT, SHD, SZD, SD | 2 | 43 | 43 |
| CSZ, CZS, CS, CZ, DRZ, DRS, DSH, DS, DZH, DZS, DZ, TRZ, TRS, TRCH, TSH, TTSZ, TTZ, TZS, TSZ, SZ, TTCH, TCH, TTSCH, ZSCH, ZHSH, SCH, SH, TTS, TC, TS, TZ, ZH, ZS | 4 | 4 | 4 |
| SC | 2 | 4 | 4 |
| DT, D, TH, T | 3 | 3 | 3 |
| CHS, KS, X | 5 | 54 | 54 |
| S, Z | 4 | 4 | 4 |
| CH, CK, C, G, KH, K, Q | 5 | 5 | 5 |
| MN, NM | 66 | 66 | |
| M, N | 6 | 6 | 6 |
| FB, B, PH, PF, F, P, V, W | 7 | 7 | 7 |
| H | 5 | 5 | |
| L | 8 | 8 | 8 |
| R | 9 | 9 | 9 |
| символ | альтернативы | в начале | перед гласной | в других случаях |
|---|---|---|---|---|
| AI | AJ, AY | 0 | 1 | ничего |
| AU | 0 | 7 | ничего | |
| Ą | (польское) | ничего | ничего | 6 или ничего |
| A | 0 | ничего | ничего | |
| B | 7 | 7 | 7 | |
| CHS | 5 | 54 | 54 | |
| CH | аналогично KH (5) или TCH (4) | |||
| CK | аналогично K (5) или TSK (45) | |||
| CZ | CS, CSZ, CZS | 4 | 4 | 4 |
| C | аналогично K (5) или TZ (4) | |||
| DRZ | DRS | 4 | 4 | 4 |
| DS | DSH, DSZ | 4 | 4 | 4 |
| DZ | DZH, DZS | 4 | 4 | 4 |
| D | DT | 3 | 3 | 3 |
| EI | EJ, EY | 0 | 1 | ничего |
| EU | 1 | 1 | ничего | |
| Ę | (польское) | ничего | ничего | 6 или ничего |
| E | 0 | ничего | ничего | |
| FB | 7 | 7 | 7 | |
| F | 7 | 7 | 7 | |
| G | 5 | 5 | 5 | |
| H | 5 | 5 | ничего | |
| IA | IE, IO, IU | 1 | ничего | ничего |
| I | 0 | ничего | ничего | |
| J | аналогично Y (1) или DZH (4) | |||
| KS | 5 | 54 | 54 | |
| KH | 5 | 5 | 5 | |
| K | 5 | 5 | 5 | |
| L | 8 | 8 | 8 | |
| MN | 66 | 66 | ||
| M | 6 | 6 | 6 | |
| NM | 66 | 66 | ||
| N | 6 | 6 | 6 | |
| OI | OJ, OY | 0 | 1 | ничего |
| O | 0 | ничего | ничего | |
| P | PF, PH | 7 | 7 | 7 |
| Q | 5 | 5 | 5 | |
| RZ, RS | аналогично RTZ (94) и ZH (4) | |||
| R | 9 | 9 | 9 | |
| SCHTSCH | SCHTSH, SCHTCH | 2 | 4 | 4 |
| SCH | 4 | 4 | 4 | |
| SHTCH | SHCH, SHTSH | 2 | 4 | 4 |
| SHT | SCHT, SCHD | 2 | 43 | 43 |
| SH | 4 | 4 | 4 | |
| STCH | STSCH, SC | 2 | 4 | 4 |
| STRZ | STRZ, STSH | 2 | 4 | 4 |
| ST | 2 | 43 | 43 | |
| SZCZ | SZCS | 2 | 4 | 4 |
| SZT | SHD, SZD, SD | 2 | 43 | 43 |
| SZ | 4 | 4 | 4 | |
| S | 4 | 4 | 4 | |
| TCH | TTCH, TTSCH | 4 | 4 | 4 |
| TH | 3 | 3 | 3 | |
| TRZ | TRS | 4 | 4 | 4 |
| TSCH | TSH | 4 | 4 | 4 |
| TS | TTS, TTSZ, TC | 4 | 4 | 4 |
| TZ | TTZ, TZS, TSZ | 4 | 4 | 4 |
| Ţ | (румынское) | 3 или 4 | 3 или 4 | 3 или 4 |
| T | 3 | 3 | 3 | |
| UI | UJ, UY | 0 | 1 | ничего |
| U | UE | 0 | ничего | ничего |
| V | 7 | 7 | 7 | |
| W | 7 | 7 | 7 | |
| X | 5 | 54 | 54 | |
| Y | 1 | ничего | ничего | |
| ZDZ | ZDZH, ZHDZH | 2 | 4 | 4 |
| ZD | ZHD | 2 | 43 | 43 |
| ZH | ZS, ZSCH, ZSH | 4 | 4 | 4 |
| Z | 4 | 4 | 4 | |
| символ | альтернативы | в начале | перед гласной | в других случаях |
«Альтернативные» варианты буквосочетаний (используются для генерации нескольких альтернативных кодов из исходного слова):
CH → TCH
CK → TSK
C → TZ
J → DZH
Принцип кодирования тот же, что и в soundex, но с дополнениями:
Таблица рассчитана на языки на основе латиницы, поэтому, чтобы кодировать русский мат, надо юзать волшебный транслит.
Примеры
f('Майкл Джордан') == f('Michael Jordan') == 658000 493600
f('Арнольд Шварцнеггер') == f('Arnold Schwarzenegger') == 096830 479465
f('Орнольд Шворцнегир') == f('Arnold Schwarzenegger') == 096830 479465
095747 → Архипцев, Архипцов, Архипычев, Арцыбасов, Арцыбашев, Арчибасов
095757 → Архипков, Архипцев, Архипцов, Архипычев
584360 → Галстян, Галустян, Гильштейн, Глистин, Глуздань, Голштейн, Гольдштеин, Гольдштейн, Калустьян, Хлистун, Хлыстун, Хлюстин.
К одному и тому же коду этот алгоритм преобразует в среднем 5 фамилий.
Впоследствии Александр Бейдер и Стивен Морзе разработали Beider-Morse Name Matching Algorithm, нацеленный на уменьшение количества «ложноположительных» значений относительно Daitch-Mokotoff Soundex при работе с еврейскими (ашкенази) фамилиями.
Несколько лучшими характеристиками обладает алгоритм Metaphone (1990 год), отличающийся от предыдущих алгоритмов несколько иным подходом к процессу кодирования: он преобразует исходное слово с учетом правил английского языка, используя заметно более сложные правила, и при этом теряется значительно меньше информации, так как буквы не разбиваются на группы. Итоговый код представляет собой набор символов из множества 0BFHJKLMNPRSTWXY, в начале слова также могут быть гласные из множества AEIOU.
Алгоритм вычисления кода Metaphone
Примеры
AKXN → Агашин, Акаченок, Акишин, Аксионенко, Аксионов, Акчунаев, Акшанов, Акшенцев, Акшинский, Акшинцев, Акшонов.
FSLX → Василишин, Васильчак, Васильченко, Васильчик, Васильчиков, Васильченко, Васильчук, Василющенко.
SRFM → Серафимов, Серафимский, Серафимчук, Церейфман.
Одно и то же значение кода Metaphone имеют в среднем 6 фамилий.
Double Metaphone (2000 год) несколько отличается от других фонетических алгоритмов, генерируя из исходного слова не один, а два кода (оба длиной до 4 символов) — один отражает основной вариант произношения слова, другой же — альтернативную версию. Он имеет большое количество различных правил, учитывающих, помимо всего прочего, различное происхождение слов, уделяя внимание восточно-европейским, итальянским, китайским словам и так далее. Правила преобразований достаточно многочисленны, я не буду их публиковать, а желающие смогут прочитать о них в статье журнала Dr Dobbs.
Примеры
JXRF → Гишаров.
KKRF → Гагаров, Кагаров, Качаровский, Качеровский, Качуривский, Качуров, Качуровский, Кичеров, Кокарев, Кокоуров, Кокоуров, Кочаров, Кочуров, Кукарев, Цакиров, Цокуров, Цугров.
KXRF → Гишаров, Гочаров, Качеров, Качеровский, Кашаревский, Кочаров, Кочерев, Кочеряев, Кочураев, Кошарев, Кошеров.
PNFS → Бановский, Бахновский, Биневский, Бинявский, Буйновский, Буяновский, Паневский, Пановский, Пановских, Пеньевский, Пиневский, Пиуновский, Пихновский.
Double Metaphone сопоставляет в среднем 8-9 фамилий одному и тому же коду.
В 2002 году в 8-ом выпуске журнала «Программист» была опубликована статья Петра Каньковски, рассказывающая о его адаптации английской версии алгоритма Metaphone к суровым сибирским морозам, медведям и балалайкам. Этот алгоритм преобразует исходные слова в соответствии с правилами и нормами русского языка, учитывая фонетическое звучание безударных гласных и возможные «слияния» согласных при произношении. Он показывает очень хорошие результаты на практике, несмотря на то, что основывается на довольно простых правилах. Все буквы разбиты на группы по звучанию — гласные и согласные (vowels и consonants соответственно в английской терминологии), глухие и звонкие. Звонкие согласные преобразуются в соответствующие им парные глухие, объединяются «сливающиеся» при произношении последовательности букв, и проводятся некоторые другие манипуляции. Ниже я приведу немного доработанный вариант, который, в отличие от оригинала Петра Каньковски, привносит правила, связанные с фонетической эквивалентностью Ц и ТС или ДС, и не сжимает окончания — байты экономить — это не наша задача.
Алгоритм вычисления кода русского Metaphone
В итоге, алгоритм очень хорошо справляется со своей задачей — в результирующем наборе содержатся действительно фонетически схожие слова. И при этом остается довольно мало лишних слов, в основном благодаря тому, что гласные не игнорируются, а преобразуются и используются в итоговом коде. Однако же, есть некоторые слова, которые, не смотря на свою фонетическую схожесть, не попадают в результирующий набор из-за слишком «строгих» правил алгоритма.
В случае Адольфа Швардсенеггера результатом работы алгоритма русского Metaphone будет:
Таким образом, алгоритм в данном случае отражает реальное фонетическое сходство этих двух фамилий.
Примеры
ВИТАФСКИЙ → Витавский, Витовский.
ВИТИНБИРК → Витенберг, Виттенберг.
НАСАНАФ → Насанов, Насонов, Нассонов, Носонов.
ПИРМАКАФ → Пермаков, Пермяков, Перьмяков.
Этот алгоритм преобразует к одному и тому же коду в среднем 1-2 фамилии.
В октябре 2009 года была выпущена профессиональная версия, разработанная тем же автором, Лоуренсом Филипсом. Это коммерческий продукт, который продается как исходный код. Metaphone 3 дополнительно улучшает фонетическое кодирование слов английского языка, неанглийских слов, знакомых американцам, а также имен и фамилий, обычно встречающихся в Соединенных Штатах. Это, в частности, значительно улучшает кодирование имен собственных. Автор утверждает, что в целом он улучшает точность всех слов с примерно 89% в Double Metaphone до 98%. Разработчики также могут теперь устанавливать переключатели в коде, чтобы заставить алгоритм кодировать ключи Метафона 1) с учетом не начальных гласных, а также 2) по-разному кодировать звонкие и глухие согласные. Это позволяет более точно сфокусировать набор результатов, если разработчик обнаруживает, что результаты поиска включают слишком много слов, которые недостаточно похожи на поисковый запрос. Metaphone 3 продается как исходный код C ++, Java, C #, PHP, Perl и PL / SQL, оболочки Ruby и Python, обращающиеся к банке Java, а также Metaphone 3 для испанского и немецкого произношения, доступный как исходный код Java и C #. Последней версией алгоритма Metaphone 3 является v2.5.4, выпущенная в марте 2015 года. Исходный код Java Metaphone3 для более ранней версии 2.1.3, в которой отсутствовало большое количество исправлений кодировки, внесенных в текущую версию 2.5.4, был включен как часть проекта OpenRefine и доступен для публичного просмотра.
Есть некоторые заблуждения об алгоритмах Metaphone, которые следует устранить. Верны следующие утверждения:
Эта приблизительная кодировка необходима для того, чтобы учесть то, как носители английского языка изменяют свое произношение и орфографические ошибки или иным образом меняют слова и имена, которые они пытаются написать. Гласные, как известно, очень разнообразны. Британцы часто жалуются, что американцы произносят «Т» так же, как «Д». Учтите также, что все носители английского языка часто произносят 'Z' там, где пишется 'S', почти всегда, когда существительное, оканчивающееся на звонкий согласный или жидкость, имеет множественное число, например «времена года», «лучи», «примеры», и т.д. Отсутствие кодирования гласных после начального гласного звука поможет сгруппировать слова, в которых гласная и согласная могут быть переставлены при неправильном написании или альтернативном произношении
Алгоритм Caverphone был разработан в 2002 году в рамках одного из новозеландских проектов для сопоставления данных в старых и новых электоральных списках, потому он наиболее ориентирован на местное произношение, хотя и для русских фамилий он дает вполне приемлемые результаты.
Алгоритм вычисления кода Caverphone
| cough | rough | tough | enough | gn | mb |
| cou2f | rou2f | tou2f | enou2f | 2n | m2 |
| cq | ci | ce | cy | tch | c | q | x | v | dg | tio | tia | d | ph | b | sh | z |
| 2q | si | se | sy | 2ch | k | k | k | f | 2g | sio | sia | t | fh | p | s2 | s |
| j | ^y3 | ^y | y | 3gh3 | gh | g | s+ | t+ | p+ | k+ | f+ | m+ |
| y | Y3 | A | 3 | 3kh3 | 22 | k | S | T | P | K | F | M |
| n+ | w3 | wh3 | w$ | w | ^h | h | r3 | r$ | r | l3 | l$ | l |
| N | W3 | Wh3 | 3 | 2 | A | 2 | R3 | 3 | 2 | L3 | 3 | 2 |
Примеры
KPRLN11111 → Габрелян, Габриэлян, Габриэльян, Капарулин, Капралин, Капрелян.
MSRFK11111 → Мейзерович, Мисарович, Мисюревич.
PLLF111111 → Балалаев, Балалиев, Балалуев, Билалиев, Билалов, Билялов, Болелов, Палилов, Полилов, Полуляхов.
Caverphone сопоставляет одному и тому же коду около 4-5 фамилий.
Большая часть этих алгоритмов реализована на множестве языков, в том числе на C, C++, Java, C# и PHP. Некоторые из них, например Soundex и Metaphone, интегрированы или реализованы в виде плагинов для многих популярных СУБД, а также используются в составе полноценных поисковых движков, например, Apache Lucene. Область их применения довольно специфична, ведь значительного повышения удобства для пользователей можно добиться лишь при поиске фамилий, но тем не менее грамотное их использование — это плюс для поисковых систем.
1. Ю. Д. Апресян. Избранные труды. Т. I. // Лексическая семантика. М.: Языки русской культуры, 1995.
2. Donald Knuth. The art of computer programming. Vol. 3: Sorting and searching // Reading (Mass.), 1973.
3. Donald Knuth. The art of computer programming. Vol. 3: Sorting and searching. 2 nd ed. // Reading (Mass.), 1998.
4. Bertrand Lisbach & Victoria Meyer. Linguistic identity matching // Wiesbaden: Springer, 2013.
5. Donald Knuth «The Art Of Computer Programming, vol. 3: Sorting And Searching», Addison-Wesley (1973), стр. 391-392.
levenshtein — Вычисляет расстояние Левенштейна между двумя строками
metaphone — Возвращает ключ metaphone для строки
similar_text — Вычисляет степень похожести двух строк
soundex
metaphone
поисковая система
Caverphone
Поисковый индекс
Вертикальный поиск
Извлечение информации
Индекс ( базы данных )
Семантическая паутина
Поиск по сайту
Анализ данных
Исследование, описанное в статье про metaphone, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое metaphone, soundex, approximate string matching, fuzzy string searching, caverphone, double metaphone, daitch-mokotoff soundex, nysiis, metaphone 3 и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Обработка естественного языка
Комментарии
Оставить комментарий
Обработка естественного языка
Термины: Обработка естественного языка