logo

Морфоэдро

Морфоэдро > Технология Статьи

Статьи: Александр Родишевский

Алгоритмы приблизительного сравнения текста, часть 1

Часть 1, Часть 2

Содержание

Введение

В настоящее врея компьютеры содержат огромное количество данных. Однако извлечение текстовой информации затрудняется когда написано с ошибками или когда неточно известно.

Эта статья посвящена алгоритмам приблизительного сравнения строк текста. Она даёт упрощенное но ясное описание алгоритмов с примерами.

Во-первых, мы собираемся объяснить процедуры конструирующие фонетические коды для искомого текста, который звучит одинаково, но пишется по-разному. Во-вторых, мы объясним процедуры дающие разные типы метрика похожести текста, используемые в поиске позволяющем ошибки. В заключении, алгоритмы сравниваются, чтобы читатель смог выбрать наиболее подходящий. Смотрите также ресурсы в конце статьи.

Прошу посылать комментарии и вопросы по адресу: alexandre.rodichevski@chiappani.it.

Фонетическое кодирование

Обсуждаемые здесь процедуры используются для облегчения поиска в базах данных, когда известно, как текст проиносится, но не как пишется. Для этого конструируются фонетические коды для искомого текста, в то время как база данных предварительно индексируется используя эти коды. Фамилии, которые звучит одинаково, но пишутся по-разному, как SMITH и SMYTH, имеют одинаковый код и могут помещаться рядом. Использование фонетических кодов уменьшает проблемы поиска из-за неправильного или разного написания.

Фонетическое кодирование очень полезно для объединения перечней личных имён или имён предприятий. Оно также используется для опознавания речи и в поисковыых системах баз данных таких как анти-террористических.

Саундэкс

Саундэкс (Soundex) конструирует фонетические коды для личных имён. Результирующий код состоит из одной буквы и трёх цифр, каждая из которых соответствует 6 согласным звукам. Алгоритм впервые был применён в переписи США в 1880 году.

Процедура
  1. Взять первую букву.
  2. Транслировать остальные буквы:
    B, F, P, V → 1
    C, G, J, K, Q, S, X, Z → 2
    D, T → 3
    L → 4
    M, N → 5
    R → 6
  3. Удалить смежные буквы имеющие одинаковый код.
  4. Удалить неначальные A, E, I, O, U, Y, W и H.
  5. Взять первые 4 буквы заполняя справа нулями.
Примеры
  1. ALEXANDRE → A4E2A536E → A4E2A536E → A42536 → A425.
  2. ALEKSANDER → A4E22A53E6 → A4E2A53E6 → A42536 → A425.

Саундэкс Дэйча-Мокотоффа

В 1985 году новый алгоритм Саундэкс Дэйча-Мокотоффа (Daitch-Mokotoff Soundex) было применён для фонетического кодирования фамилий славянских и идиш с похожим произношением но разным написанием. Наиболее важные улучшения по сравнению с Саундэкс: более длинный код - 6 символов; производятся два разных кода когда возможны два разных произношения; кодирование использует 10 цифр от 0 к 9.

Система идентификации и сведений штата Нью-Йорк

Система идентификации и сведений штата Нью-Йорк (NYSIIS - New York State Identification and Intelligence System) была разработана в 1970 году посредством строгого эпирического анализа. В этом алгоритме конструируется фонетический код до 6 букв.

Процедура
  1. Транслировать первые буквы имени:
    MAC → MCC
    PH → FF
    KN → NN
    PF → FF
    K → C
    SCH → SSS
  2. Транслировать последние буквы имени:
    EE → Y
    IE → Y
    DT, RT, RD, NT, ND → D
  3. Транслировать остальные буквы по правилами, букву за буквой:
    EV → AF; иначе E, I, O, U → A
    Q → G
    Z → S
    M → N
    KN → N; иначе K → C
    SCH → SSS
    PH → FF
    H → предыдущая буква, если предыдущая или последующая - не гласная
    W → предыдущая буква, если предыдущая - гласная
  4. Проверить последнюю букву:
    если последняя буква - S, удалить её
    если последние буквы - AY, заменить на Y
    если последняя буква - A, удалить её
  5. Удалить вторую из двойных букв.
  6. Взять первые шесть букв.
Примеры
  1. ALEXANDRE → ALAXANDRA → ALAXANDR → ALAXANDR → ALAXAN
  2. ALEKSANDER → ALACSANDAR → ALACSANDAR → ALACSANDAR → ALACSA

Метафон

Алгоритм Метафон (Metaphone) фонетически кодирует слова путем уменьшения их до 16 согласных звуков: B, X, S, K, J, T, F, H, L, M, N, P, R, 0, W, Y. Ноль представляет звук "th"; X представляет "sh".

Процедура
  1. Удалить вторую из двойных букв, за исключением C.
  2. Если слово начинается с KN, GN, PN, AE, WR, удалить первую букву.
  3. Удалить B в конце слова после M.
  4. C → X в CIA или CH; C → S в CI, CE или CY; C → K в противном случае.
  5. D → J в DGE, DGY или DGI; D → T в противном случае.
  6. Удалить G в GH и если не в конце или перед гласным в GN или GNED; G → J перед I или E или Y если не двойная GG; G → K в противном случае.
  7. Удалить H после гласной и если следующая буква не гласная.
  8. Удалить K после C.
  9. P → F в PH.
  10. Q → K.
  11. S → X в SH или SIO или SIA.
  12. T → X в TIA или TIO; T → 0 в TH; T удаляется в TCH.
  13. V → F.
  14. Если слово начинается с WH, удалить H; удалить W если следующая буква не гласная.
  15. Если слово начинается с X, тогда X → S; X → KS в противном случае.
  16. Удалить Y если следующая буква не гласная.
  17. Z → S.
  18. Гласные сохраняются только когда они находятся в начале слова.
  19. Во всех остальных случаях буквы не меняются.
Примеры
  1. ALEXANDRE → ALEKSANTRE → ALKSNTR
  2. ALEKSANDER → ALEKSANTER → ALKSNTR

Двойной метафон

Двойной метафон (Double metaphone) - улучшенный вариант Метафона. Этот алгоритм фонетически кодирует слова путем уменьшения их до 12 согласных звуков. Оно возвращает два кода если слово имеет два возможных произношения.

Каверфон

Алгоритм фонетического сравнения Каверфон (Caverphone) был создан в рамках Кавершамского проекте в университете Отаго в Новой Зеландии в 2002 году. Алгоритм позволяет акценты присутствующие в изучаемой зоне (южная часть города Дунедин, Новой Зеландия).

Новая версия Каверфон 2.0 была предложена для более общего фонетического сравнения.

Алгоритмы приблизительного сравнения текста
Часть 1, Часть 2