Исследование фонетических алгоритмов
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?се гласные и некоторые согласные), игнорируются. Смежные символы, или символы, разделенные буквами H или W, входящие в одну и ту же группу, записываются как один. Результат обрезается до 4 символов. Недостающие позиции заполняются нулями. Несложно заметить, что после всех этих процедур остается всего лишь 7 тысяч различных вариаций такого кода, что влечет за собой множество совершенно ничем не похожих друг на друга слов, имеющих одинаковый Soundex-код. Таким образом, результат в большинстве случаев включает в себя большое количество ложноположительных значений.
Рисунок 2.1 - Структура алгоритма Soundex
В улучшенной версии, как можно заметить, буквы разбиты на большее количество групп. Помимо этого, никакого особого внимания буквам H и W не уделяется, они просто игнорируются. Кроме того, никаких операций с длиной результата не производится - код не имеет фиксированной длины и не обрезается.
Приведем примеры работы данного алгоритма.
Оригинальный Soundex:> Дедловский, Дедловских, Дидилев, Дителев, Дудалев, Дудолев, Дутлов, Дыдалев, Дятлов, Дятлович.> Нагимов, Нагмбетов, Назимов, Насимов, Нассонов, Нежнов, Незнаев, Несмеев, Нижневский, Никонов, Никонович, Нисенблат, Нисенбаум, Ниссенбаум, Ногинов, Ножнов.
Улучшенный Soundex:> Насимов, Нассонов, Никонов.> Нисенбаум, Ниссенбаум.> Нагимов, Нагонов, Неганов, Ногинов.> Нагмбетов.> Назимов, Нежнов, Ножнов
В среднем, на одно значение кода Soundex приходится 21 фамилия. В случае же улучшенной версии Soundex, к одному и тому же коду преобразуются всего 2-3 фамилии.
2.2 Алгоритм NYSIIS
Разработанный в 1970 году как часть системы New York State Identification and Intelligence System, этот алгоритм дает несколько лучшие результаты относительно оригинального Soundex, используя более сложные правила преобразования исходного слова в результирующий код. Этот алгоритм разработан для работы именно с американскими фамилиями.
Приведем алгоритм вычисления кода NYSIIS.
1.Преобразовать начало слова по следующим правилам:
MAC > MCC
KN > N
K > C
PH, PF > FF> SSS
2.Преобразовать конец слова по следующим правилам:
EE > Y
IE > YDT, RT, RD, NT, ND > D
3.Затем все буквы, кроме первой, преобразуются по следующим правилам:
EV > AF, E, I, O, U > A> G> S> N> N> C> SSS
PH > FF
4.После гласных: удалить H, преобразовать W > A
5.Удалить S на конце
.Преобразуем AY на конце > Y
.Удалить A на конце
.Обрезать до 6 символов (необязательный шаг).
Приведем примеры работы данного алгоритма> Каспаравичус, Касперович, Каспирович.> Катников, Цитников, Цотников.> Ленченко, Леонченко, Линченко, Лунченко, Лямзенко.> Приходский, Проходский, Прудский, Прудских, Прудской.> Стадников.преобразует к одному и тому же коду немногим более двух фамилий.
.3 Алгоритм Daitch-Mokotoff Soundex
Этот алгоритм в 1985 году разработали два генеалога - Гарри Мокотофф и Рэнди Дэйч, стремясь достичь лучших, относительно оригинального Soundex, результатов при работе с восточно-европейскими (в том числе русскими) фамилиями.
Этот алгоритм имеет мало общего с оригинальным Soundex, разве что результатом всё так же остается последовательность цифр, однако теперь первая буква также кодируется.
Он имеет значительно более сложные правила конверсии - теперь в формировании результирующего кода участвуют не только одиночные символы, но и последовательности из нескольких символов. Кроме того, результат вида 023689 обеспечивает около 600 тысяч различных вариаций кода, что вкупе с усложненными правилами уменьшает количество лишних, т.е. ложноположительных слов в результирующем множестве.
Преобразования осуществляются по следующей таблице (порядок преобразований соответствует порядку буквосочетаний в таблице):
Таблица 2.1 - Преобразования алгоритма Daitch-Mokotoff Soundex
Исходные буквосочетанияВ началеЗа гласнойОстальноеAI, AJ, AY, EI, EY, EJ, OI, OJ, OY, UI, UJ, UY01AU0712341234IA, IE, IO, IU1EU11A, UE, E, I, O, U, Y0J111SCHTSCH, SCHTSH, SCHTCH, SHTCH, SHCH, SHTSH, STCH, STSCH, STRZ, STRS, STSH, SZCZ, SZCS244SHT, SCHT, SCHD, ST, SZT, SHD, SZD, SD24343CSZ, 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, ZS444SC244DT, D, TH, T333CHS, KS, X55454S, Z444CH, CK, C, G, KH, K, Q555MN, NM6666M, N666FB, B, PH, PF, F, P, V, W777H55L888R999
Альтернативные варианты буквосочетаний (используются для генерации нескольких альтернативных кодов из исходного слова):> TCH> TSK> TZ> DZH
Приведем примеры работы данного алгоритма.
> Архипцев, Архипцов, Архипычев, Арцыбасов, Арцыбашев, Арчибасов
> Архипков, Архипцев, Архипцов, Архипычев
> Галстян, Галустян, Гильштейн, Глистин, Глуздань, Голштейн, Гольдштеин, Гольдштейн, Калустьян, Хлистун, Хлыстун, Хлюстин.
К одному и тому же коду этот алгоритм преобразует в среднем 5 фамилий. Впоследствии Александр Бейдер и Стивен Морзе разработали Beider-Morse Name Matching Algorithm , нацеленный на уменьшение количества ложноположительных значений относительно Daitch-Mokotoff Soundex при работе с еврейскими (ашкенази) фамилиями.
2.4 Алгоритм Metaphone
Несколько лучшими характеристиками обладает алгоритм Metaphone (1990 год), отличающийся от предыдущих алгоритмов несколько иным подходом к процессу кодирования: он преобразует исходное слово с учетом правил английского языка, используя заметно более сложные правила, и при этом теряется значительно меньше информации, так как буквы не разбиваются на группы. Итоговый код представляет собой набор символов из множества 0BFHJKLMNPRSTWXY, в начале слова также могут быть гласные из множества AEIOU.
Алгоритм вычисления кода Metaphone.
1.Удаляем