Саундекс
Soundex — это фонетический алгоритм индексации на английском имен по звуку, произносимому языке. Цель состоит в том, чтобы омофоны были закодированы в одно и то же представление, чтобы их можно было сопоставлять, несмотря на незначительные различия в написании . [1] Алгоритм в основном кодирует согласные; гласная не будет закодирована, если это не первая буква. Soundex — наиболее широко известный из всех фонетических алгоритмов (отчасти потому, что это стандартная функция популярных программ управления базами данных, таких как IBM Db2 , PostgreSQL , [2] MySQL , [3] SQLite , [4] Ingres , MS SQL-сервер , [5] Оракул , [6] КликХаус , [7] Снежинка [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 Вычислительная техника , особенно когда она описана в книге Дональда Кнута «Искусство компьютерного программирования» . [14]
Национальное управление архивов и документации (NARA) поддерживает текущий набор правил для официального внедрения Soundex, используемого правительством США. [1] Эти правила кодирования можно получить в NARA по запросу в виде брошюры с общей информацией 55 «Использование Census Soundex».
Американский Саундекс
[ редактировать ]Код имени Soundex состоит из буквы, за которой следуют три числовые цифры : буква — это первая буква имени, а цифры кодируют остальные согласные . Согласные в одинаковом месте артикуляции имеют одну и ту же цифру, поэтому, например, губные согласные B, F, P и V кодируются цифрой 1.
Правильное значение можно найти следующим образом:
- Сохраните первую букву имени и отбросьте все остальные буквы a, e, i, o, u, y, h, w.
- Замените согласные цифрами следующим образом (после первой буквы):
- б, е, п, v → 1
- в, г, j, k, q, s, x, z → 2
- д, т → 3
- л → 4
- м, п → 5
- р → 6
- Если в исходном имени (до шага 1) соседствуют две или более буквы с одинаковым номером, сохраните только первую букву; также две буквы с одинаковым номером, разделенные буквами «h», «w» или «y», кодируются как одно число, тогда как такие буквы, разделенные гласной, кодируются дважды. Это правило касается и первой буквы.
- Если в слове слишком мало букв для присвоения трех цифр, добавляйте нули, пока не останется три цифры. Если чисел четыре или более, сохраните только первые три.
Используя этот алгоритм, и «Роберт», и «Руперт» возвращают одну и ту же строку «R163», а «Рубин» возвращает «R150». «Эшкрафт» и «Эшкрофт» дают «А261». «Tymczak» дает «T522», а не «T520» (символы «z» и «k» в названии дважды кодируются как 2, поскольку между ними находится гласная). «Pfister» дает «P236», а не «P123» (первые две буквы имеют одинаковый номер и один раз кодируются как «P»), а «Honeyman» дает «H555».
Следующему алгоритму следуют большинство языков SQL (за исключением PostgreSQL). [ нужен пример ] ):
- Сохраните первую букву. Составьте карту всех вхождений a, e, i, o, u, y, h, w. до нуля(0)
- Замените все согласные (включая первую букву) цифрами, как в [2.] выше.
- Замените все соседние одинаковые цифры одной цифрой, а затем удалите все нулевые (0) цифры.
- Если цифра сохраненной буквы совпадает с полученной первой цифрой, удалите цифру (сохраните букву).
- Добавьте 3 нуля, если результат содержит менее 3 цифр. Удалите все, кроме первой буквы и трех цифр после нее (этот шаг аналогичен [4.] в объяснении выше).
Два приведенных выше алгоритма не возвращают одинаковые результаты во всех случаях, главным образом из-за разницы в том, когда удаляются гласные. Первый алгоритм используется большинством языков программирования, а второй — SQL. Например, «Тымчак» дает «T522» в первом алгоритме, но «T520» в алгоритме, используемом SQL. Часто оба алгоритма генерируют один и тот же код. Например, и «Роберт», и «Руперт» дают «R163», а «Ханиман» — «H555». При разработке приложения, сочетающего SQL и язык программирования, архитектор должен решить, следует ли выполнять все кодирование Soundex на сервере SQL или все на языке программирования. Реализация MySQL может возвращать более 4 символов. [15] [16]
Варианты
[ редактировать ]Похожий алгоритм под названием «Reverse Soundex» добавляет последнюю букву имени вместо первой.
Алгоритм Системы идентификации и разведки штата Нью-Йорк (NYSIIS) был представлен в 1970 году как усовершенствование алгоритма Soundex. NYSIIS обрабатывает некоторые многосимвольные n-граммы и поддерживает относительное расположение гласных, тогда как Soundex этого не делает.
Звук Дейча-Мокотоффа (D-M Soundex) был разработан в 1985 году специалистом по генеалогии Гэри Мокотоффом и позже улучшен специалистом по генеалогии Рэнди Дейчем из-за проблем, с которыми они столкнулись при попытке применить Soundex Рассела к евреям с германскими или славянскими фамилиями (например, Московиц против Московиц или Левин против Левина). D – M Soundex иногда называют «еврейским Soundex» или «восточноевропейским Soundex». [17] хотя авторы не рекомендуют использовать эти имена. Алгоритм D-M Soundex может возвращать до 32 отдельных фонетических кодировок для одного имени. Результаты DM Soundex возвращаются в числовом формате от 100 000 до 999 999. Этот алгоритм намного сложнее, чем Russell Soundex.
В ответ на недостатки алгоритма Soundex Лоуренс Филипс разработал алгоритм Metaphone в 1990 году. В 2000 году Philips разработал улучшение Metaphone, которое он назвал Double Metaphone. Double Metaphone включает гораздо больший набор правил кодирования, чем его предшественник, обрабатывает подмножество нелатинских символов и возвращает первичную и вторичную кодировку для учета различного произношения одного слова на английском языке. Philips создала Metaphone 3 как дополнительную версию в 2009 году, чтобы предоставить профессиональную версию, которая обеспечивает гораздо более высокий процент правильных кодировок для английских слов, неанглийских слов, знакомых американцам, а также имен и фамилий, встречающихся в Соединенных Штатах. Он также предоставляет настройки, которые обеспечивают более точное сопоставление согласных и внутренних гласных, что позволяет программисту более точно сосредоточить внимание на точности совпадений.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б «Система индексации Soundex» . Национальный архив . Национальное управление архивов и документации . 30 мая 2007 г. Архивировано из оригинала 12 марта 2020 г. . Проверено 24 декабря 2010 г.
- ^ «Документация: 9.1: fuzzystrmatch» . ПостгреСБЛ . Архивировано из оригинала 23 июля 2020 года . Проверено 3 ноября 2012 г.
- ^ «Справочное руководство MySQL 5.5 :: 12.5 Строковые функции» . MySQL . САУНДЭКС(ул.). Архивировано из оригинала 15 сентября 2016 года.
- ^ «Встроенные SQL-функции скалера» . SQLite . 16 июля 2022 г. soundex(X). Архивировано из оригинала 20 декабря 2022 года . Проверено 24 декабря 2022 г.
- ^ «SOUNDEX (Transact-SQL)» . Microsoft Learn . 10 января 2010 г. Архивировано из оригинала 23 октября 2022 г. Проверено 3 ноября 2012 г.
- ^ «САУНДЭКС» . Справочник по SQL базы данных . Архивировано из оригинала 21 октября 2017 года . Проверено 20 октября 2017 г.
- ^ «САУНДЭКС» . Функции для работы со строками .
- ^ «SOUNDEX — Документация Снежинки» . docs.snowflake.com . Проверено 16 января 2023 г.
- ^ «саундекс» . Программные решения SAP . 28 мая 2014 г. Архивировано из оригинала 25 декабря 2022 г. . Проверено 24 мая 2021 г.
- ^ «Фонетическое соответствие: лучший звук» . Проверено 3 ноября 2012 г.
- ^ Оделл, Маргарет Кинг (1956). «Прибыль в делопроизводстве» . Системы . 20 . Нью-Йорк: 20.
- ^ Патент США 1261167 , RC Russell, «(без названия)», выдан 2 апреля 1918 г. ( в архиве ).
- ^ Патент США 1435663 , RC Russell, «(без названия)», выдан 14 ноября 1922 г. ( в архиве ).
- ^ Кнут, Дональд Э. (1973). Искусство компьютерного программирования: Том 3, Сортировка и поиск . Аддисон-Уэсли. стр. 391–92. ISBN 978-0-201-03803-3 . ОСЛК 39472999 . Архивировано из оригинала 4 сентября 2008 г. Проверено 17 сентября 2010 г.
- ^ CodingForums.com ( [1] )
- ^ «MySQL :: Справочное руководство MySQL 5.5 :: 12.5 Строковые функции — SOUNDEX» . dev.mysql.com .
- ^ Мокотофф, Гэри (8 сентября 2007 г.). «Звукозапись и генеалогия» . Проверено 27 января 2008 г.