Саундекс
Фонетический алгоритм индексации имен по звучанию

Soundex — фонетический алгоритм для индексации имен по звуку, как они произносятся на английском языке. Цель состоит в том, чтобы кодировать омофоны в одно и то же представление, чтобы их можно было сопоставить, несмотря на незначительные различия в написании . [1] Алгоритм в основном кодирует согласные; гласная не будет кодироваться, если она не является первой буквой. Soundex — наиболее широко известный из всех фонетических алгоритмов (отчасти потому, что это стандартная функция популярного программного обеспечения для баз данных, такого как IBM Db2 , PostgreSQL , [2] MySQL , [3] SQLite , [4] Ingres , MS SQL Server , [5] Oracle , [6] ClickHouse , [7] Snowflake [8] и SAP ASE . [9] ) Улучшения Soundex являются основой для многих современных фонетических алгоритмов. [10]

История

Soundex был разработан Робертом С. Расселом и Маргарет Кинг Оделл [11] и запатентован в 1918 [12] и 1922 годах. [13] Вариант, American Soundex, использовался в 1930-х годах для ретроспективного анализа переписей населения США с 1890 по 1920 год. Код Soundex приобрел известность в 1960-х годах, когда он стал предметом нескольких статей в Communications and Journal of the Association for Computing Machinery , и особенно после описания в книге Дональда Кнута «Искусство компьютерного программирования» . [14]

Национальное управление архивов и документации (NARA) поддерживает текущий набор правил для официальной реализации Soundex, используемого правительством США. [1] Эти правила кодирования доступны в NARA по запросу в форме Информационного буклета общего назначения 55 «Использование переписного Soundex».

Американский Саундекс

Код Soundex для имени состоит из буквы, за которой следуют три числовые цифры : буква является первой буквой имени, а цифры кодируют остальные согласные . Согласные в схожем месте артикуляции имеют одну и ту же цифру, так, например, губные согласные B, F, P и V кодируются как число 1.

Правильное значение можно найти следующим образом:

  1. Сохраните первую букву имени и отбросьте все остальные вхождения a, e, i, o, u, y, h, w.
  2. Замените согласные цифры следующим образом (после первой буквы):
    • б, е, п, в → 1
    • с, г, дж, к, д, с, х, z → 2
    • д, т → 3
    • л → 4
    • м, н → 5
    • г → 6
  3. Если в исходном имени (до шага 1) рядом стоят две или более букв с одинаковым номером, оставьте только первую букву; также две буквы с одинаковым номером, разделенные 'h', 'w' или 'y', кодируются как одно число, тогда как такие буквы, разделенные гласной, кодируются дважды. Это правило также применяется к первой букве.
  4. Если в слове слишком мало букв для присвоения трех цифр, добавляйте нули, пока не получится три цифры. Если цифр четыре или больше, оставьте только первые три.

Используя этот алгоритм, и "Robert", и "Rupert" возвращают одну и ту же строку "R163", в то время как "Rubin" возвращает "R150". "Ashcraft" и "Ashcroft" возвращают "A261". "Tymczak" возвращает "T522", а не "T520" (символы "z" и "k" в имени кодируются как 2 дважды, так как между ними находится гласная). "Pfister" возвращает "P236", а не "P123" (первые две буквы имеют одинаковый номер и кодируются один раз как "P"), а "Honeyman" возвращает "H555".

Следующий алгоритм используется в большинстве языков SQL (за исключением PostgreSQL [ необходим пример ] ):

  1. Сохраните первую букву. Отобразите все вхождения a, e, i, o, u, y, h, w. на ноль (0)
  2. Замените все согласные (включая первую букву) цифрами, как в [2.] выше.
  3. Замените все соседние одинаковые цифры одной цифрой, а затем удалите все нули (0).
  4. Если цифра сохраненной буквы совпадает с полученной первой цифрой, удалите цифру (букву сохраните).
  5. Добавьте 3 нуля, если результат содержит менее 3 цифр. Удалите все, кроме первой буквы и 3 цифр после нее (Этот шаг такой же, как [4.] в объяснении выше).

Два алгоритма выше не возвращают одинаковые результаты во всех случаях, в первую очередь из-за разницы между тем, когда удаляются гласные. Первый алгоритм используется большинством языков программирования, а второй — SQL. Например, «Tymczak» возвращает «T522» в первом алгоритме, но «T520» в алгоритме, используемом SQL. Часто оба алгоритма генерируют один и тот же код. Например, и «Robert», и «Rupert» возвращают «R163», а «Honeyman» возвращает «H555». При проектировании приложения, которое объединяет SQL и язык программирования, архитектор должен решить, выполнять ли всю кодировку Soundex на сервере SQL или все на языке программирования. Реализация MySQL может возвращать более 4 символов. [15] [16]

Варианты

Похожий алгоритм, называемый «Reverse Soundex», добавляет в качестве префикса последнюю букву имени вместо первой.

Алгоритм системы идентификации и разведки штата Нью-Йорк (NYSIIS) был представлен в 1970 году как усовершенствование алгоритма Soundex. NYSIIS обрабатывает некоторые многосимвольные n-граммы и сохраняет относительное расположение гласных, тогда как Soundex этого не делает.

Daitch–Mokotoff Soundex (D–M Soundex) был разработан в 1985 году генеалогом Гэри Мокотоффом и позже улучшен генеалогом Рэнди Дейчем из-за проблем, с которыми они столкнулись при попытке применить Russell Soundex к евреям с германскими или славянскими фамилиями (такими как Moskowitz vs. Moskovitz или Levine vs. Lewin). D–M Soundex иногда называют «еврейским Soundex» или «восточноевропейским Soundex» [17] , хотя авторы не рекомендуют использовать эти имена. Алгоритм D–M Soundex может возвращать до 32 отдельных фонетических кодировок для одного имени. Результаты DM Soundex возвращаются в полностью числовом формате от 100000 до 999999. Этот алгоритм намного сложнее, чем Russell Soundex.

В ответ на недостатки алгоритма Soundex Лоуренс Филипс разработал алгоритм Metaphone в 1990 году. В 2000 году Philips разработал усовершенствование Metaphone, которое он назвал Double Metaphone. Double Metaphone включает в себя гораздо больший набор правил кодирования, чем его предшественник, обрабатывает подмножество нелатинских символов и возвращает первичную и вторичную кодировку для учета различных произношений одного слова на английском языке. Philips создал Metaphone 3 в качестве дальнейшей доработки в 2009 году, чтобы предоставить профессиональную версию, которая обеспечивает гораздо более высокий процент правильных кодировок для английских слов, неанглийских слов, знакомых американцам, а также имен и фамилий, встречающихся в Соединенных Штатах. Он также предоставляет настройки, которые позволяют более точно сопоставлять согласные и внутренние гласные, позволяя программисту более точно фокусироваться на точности совпадений.

Смотрите также

Ссылки

  1. ^ ab "The Soundex Indexing System". Национальный архив . Национальное управление архивов и документации . 30 мая 2007 г. Архивировано из оригинала 12 марта 2020 г. Получено 24 декабря 2010 г.
  2. ^ "Documentation: 9.1: fuzzystrmatch". PostgreSQL . Архивировано из оригинала 23 июля 2020 г. Получено 3 ноября 2012 г.
  3. ^ "MySQL 5.5 Reference Manual :: 12.5 String Functions". MySQL . SOUNDEX(str). Архивировано из оригинала 15 сентября 2016 г.
  4. ^ "Built-In Scaler SQL Functions". SQLite . 16 июля 2022 г. soundex(X). Архивировано из оригинала 20 декабря 2022 г. Получено 24 декабря 2022 г.
  5. ^ "SOUNDEX (Transact-SQL)". Microsoft Learn . 10 января 2010 г. Архивировано из оригинала 23 октября 2022 г. Получено 3 ноября 2012 г.
  6. ^ "SOUNDEX". Справочник по SQL-базе данных . Архивировано из оригинала 21 октября 2017 г. Получено 20 октября 2017 г.
  7. ^ "SOUNDEX". Функции для работы со строками .
  8. ^ "SOUNDEX — Документация Snowflake". docs.snowflake.com . Получено 16.01.2023 .
  9. ^ "soundex". SAP Software Solutions . 28 мая 2014 г. Архивировано из оригинала 25 декабря 2022 г. Получено 24 мая 2021 г.
  10. ^ "Фонетическое соответствие: Лучший саундекс" . Получено 2012-11-03 .
  11. ^ Оделл, Маргарет Кинг (1956). «Прибыль в управлении записями». Systems . 20. Нью-Йорк: 20.
  12. ^ Патент США 1261167, RC Russell, "(без названия)", выдан 1918-04-02  (Архив)
  13. ^ Патент США 1435663, RC Russell, "(без названия)", выдан 1922-11-14 (Архив) 
  14. ^ Кнут, Дональд Э. (1973). Искусство программирования: Том 3, Сортировка и поиск. Addison-Wesley. С.  391–92 . ISBN 978-0-201-03803-3. OCLC  39472999. Архивировано из оригинала 2008-09-04 . Получено 2010-09-17 .
  15. ^ CodingForums.com ([1])
  16. ^ "MySQL :: Справочное руководство MySQL 5.5 :: 12.5 Строковые функции - SOUNDEX". dev.mysql.com .
  17. ^ Мокотофф, Гэри (2007-09-08). "Soundexing and Genealogy" . Получено 2008-01-27 .
Взято с "https://en.wikipedia.org/w/index.php?title=Soundex&oldid=1266459224"