Soundex: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
(Показать все непатрулированные изменения)
[непроверенная версия][непроверенная версия]
← Предыдущая правка
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
 
(не показаны 4 промежуточные версии 2 участников)
Строка 1: Строка 1:
'''Soundex''' — один из [[алгоритм]]ов сравнения двух строк по их звучанию. Он устанавливает одинаковый индекс для строк, имеющих схожее звучание в английском языке.
'''Soundex''' — один из [[алгоритм]]ов сравнения [[Строковый тип|строк]] по их звучанию; устанавливает одинаковый индекс для строк, имеющих схожее звучание в [[Английский язык|английском языке]].


Soundex был разработан Робертом Расселом (Robert C. Russel) и Маргарет Кинг Оделл (Margaret King Odell) и запатентован в 1918 и 1922 годах<ref>{{US patent|1261167}}</ref><ref>{{US patent|1435663}}</ref>. Этот алгоритм стал популярным в 1960-х годах, после того как стал темой нескольких статей в журналах «Communications of the Association for Computing Machinery» и «Journal of the Association for Computing Machinery» (CACM и JACM). Еще большую популярность этот алгоритм получил после того, как был опубликован в книге {{книга
Разработан Робертом Расселом ({{lang-en2|Robert C. Russel}}) и Маргарет Кинг Оделл ({{lang-en2|Margaret King Odell}}) и запатентован в 1918 и 1922 годах<ref>{{US patent|1261167}}</ref><ref>{{US patent|1435663}}</ref>, является исторически первым {{iw|фонетический алгоритм|фонетическим алгоритмом|en|Phonetic algorithm}}. Стал популярным в 1960-х годах после того как ему были посвящены несколько статей в журналах «[[Communications of the ACM|Communications of the ACM»]] и «[[Journal of the ACM|Journal of the ACM»]]; ещё большую известность он обрёл после появления в «[[Искусство программирования|Искусстве программирования]]» [[Кнут, Дональд Эрвин|Кнута]]<ref>{{книга
|автор = [[Дональд Кнут|Дональда Кнута]]
|автор = [[Дональд Кнут]]
|заглавие = Искусство программирования
|заглавие = Искусство программирования
|ссылка =
|ссылка =
|часть = Часть 6. Поиск|том = 3. Сортировка и поиск|страницы = 249|оригинал = The Art of Computer Programming|год = 2012}}
|часть = Часть 6. Поиск|том = 3. Сортировка и поиск|страницы = 249|оригинал = The Art of Computer Programming|год = 2012}}</ref>. С 1980-х годов используется как стандартная функция во многих [[СУБД]].


Изначально ориентирован на [[Фонетика|фонетику]] [[Американский вариант английского языка|американского варианта]] английского языка, посредством модификаций может быть применён и для других вариантов и языков, но в ряде случаев требуются существенные изменения (как, например, в {{iw|алгоритм Дейча — Мокотоффа|алгоритме Дейча — Мокотоффа|en|Daitch–Mokotoff Soundex}}, поддерживающем имена собственные на [[идиш]]е и [[Славянские языки|славянских языках]]). Впоследствии также появились альтернативы, ориентированные в большей степени на обычные слова английского языка, нежели на имена собственные (такие как [[Metaphone]], {{iw|Caverphone}})
⚫
== Описание алгоритма ==


⚫
== Шаги алгоритма ==
⚫
# Запоминаем первую букву. Удаляем все 'h' и 'w', за исключением первой буквы слова.
# Запоминается первая буква слова.
⚫
# Согласные заменяем на цифры от 1 до 6, причём похожим по звучанию буквам соответствуют одинаковые цифры:
⚫
# Удаляются все вхождения <tt>[[H (латиница)|h]]</tt> и <tt>[[w]]</tt> (за исключением первой буквы слова).
#* b, f, p, v &#x2192; 1
⚫
# Согласные заменяются на цифры от 1 до 6, причём похожим по звучанию буквам соответствуют одинаковые цифры:
⚫
#* c, g, j, k, q, s, x, z &#x2192; 2
#* d, t &#x2192; 3
#* <tt>b, f, p, v → 1</tt>
⚫
#* <tt>c, g, j, k, q, s, x, z → 2</tt>
#* l &#x2192; 4
#* m, n &#x2192; 5
#* <tt>d, t → 3</tt>
#* r &#x2192; 6
#* <tt>l → 4</tt>
#* <tt>m, n → 5</tt>
#* <tt>r → 6</tt>
# Любая последовательность одинаковых цифр сокращается до одной такой цифры.
# Любая последовательность одинаковых цифр сокращается до одной такой цифры.
# Удаляем все a, e, i, o, u, y, за исключением первой буквы слова.
# Удаляются все <tt>a</tt>, <tt>e</tt>, <tt>i</tt>, <tt>o</tt>, <tt>u</tt>, <tt>y</tt> (за исключением первой буквы слова).
# Заменяем первый символ буквой, запомненной на шаге 1, делая её заглавной.
# Заменяется первый символ буквой, запомненной на шаге 1, делая её заглавной.
# Итоговая строка обрезается до первых четырех символов. Если длина строки меньше требуемой, недостающие символы заменяются знаком 0.
# Итоговая строка обрезается до первых четырёх символов. Если длина строки меньше требуемой, недостающие символы заменяются знаком 0.


Примеры:
Примеры:
* аmmonium → а55o5iu5 → а5o5iu5 → a555 → A555
* <tt>аmmonium → а55o5iu5 → а5o5iu5 → a555 → A555</tt>
* implementation → i514e5e53a3io5 → i51455335 → i514 → I514
* <tt>implementation → i514e5e53a3io5 → i51455335 → i514 → I514</tt>
* "Robert" и "Rupert" → "R163", "Rubin" → "R150"
* <tt>Robert = Rupert → R163</tt>, <tt>Rubin → R150</tt>
* "Ashcraft" и "Ashcroft" → "A261", а не "A226" (буквы 's' и 'c' в словах дадут 1 цифру '2', а не 22, т.к. разделены 'h').
* <tt>Ashcraft = Ashcroft → A261</tt> (но не <tt>A226</tt>: буквы <tt>s</tt> и <tt>c</tt> в словах дадут одну цифру <tt>2</tt>, а не <tt>22</tt>, так как разделены <tt>h</tt>).
* "Tymczak" → "T522", а не "T520" (буквы 'z' и 'k' заменяются на 22, т.к. разделены гласной).
* <tt>Tymczak → T522</tt>, а не <tt>T520</tt> (буквы <tt>z</tt> и <tt>k</tt> заменяются на <tt>22</tt>, так как разделены гласной).

== Пример исполнения ==
Ниже приведен пример реализации алгоритма на языке программирования [[Perl]].
<source lang="perl">
sub soundex {
my $word = uc shift;
$word =~ tr/\t //d;

my $fl = substr $word, 0, 1;
$word = substr $word, 1;
$word =~ tr/HW//d;

$word = $fl . $word;
$word =~ tr/BFPVCGJKQSXZDTLMNR/111122222222334556/s;

$word = substr $word, 1;
$word =~ tr/AEIOUY//d;
$word = $fl . $word;

return substr $word . "000", 0, 4;
}
</source>
Примеры использования:
<source lang="perl">
soundex('ammonium');
soundex('implementation');
soundex("Robert");
soundex("Rupert");
soundex("Rubin");
soundex("Ashcraft");
soundex("Ashcroft");
soundex("Tymczak");
soundex("Pfister");
</source>

== См. также ==
* [[Metaphone]]


== Примечания ==
== Примечания ==

Текущая версия от 13:16, 25 декабря 2022

Soundex — один из алгоритмов сравнения строк по их звучанию; устанавливает одинаковый индекс для строк, имеющих схожее звучание в английском языке.

Разработан Робертом Расселом (Robert C. Russel) и Маргарет Кинг Оделл (Margaret King Odell) и запатентован в 1918 и 1922 годах[1][2], является исторически первым фонетическим алгоритмом[англ.]. Стал популярным в 1960-х годах после того как ему были посвящены несколько статей в журналах «Communications of the ACM» и «Journal of the ACM»; ещё большую известность он обрёл после появления в «Искусстве программирования» Кнута[3]. С 1980-х годов используется как стандартная функция во многих СУБД.

Изначально ориентирован на фонетику американского варианта английского языка, посредством модификаций может быть применён и для других вариантов и языков, но в ряде случаев требуются существенные изменения (как, например, в алгоритме Дейча — Мокотоффа[англ.], поддерживающем имена собственные на идише и славянских языках). Впоследствии также появились альтернативы, ориентированные в большей степени на обычные слова английского языка, нежели на имена собственные (такие как Metaphone, Caverphone[англ.])

Шаги алгоритма

[править | править код]
  1. Запоминается первая буква слова.
  2. Удаляются все вхождения h и w (за исключением первой буквы слова).
  3. Согласные заменяются на цифры от 1 до 6, причём похожим по звучанию буквам соответствуют одинаковые цифры:
    • b, f, p, v → 1
    • c, g, j, k, q, s, x, z → 2
    • d, t → 3
    • l → 4
    • m, n → 5
    • r → 6
  4. Любая последовательность одинаковых цифр сокращается до одной такой цифры.
  5. Удаляются все a, e, i, o, u, y (за исключением первой буквы слова).
  6. Заменяется первый символ буквой, запомненной на шаге 1, делая её заглавной.
  7. Итоговая строка обрезается до первых четырёх символов. Если длина строки меньше требуемой, недостающие символы заменяются знаком 0.

Примеры:

  • аmmonium → а55o5iu5 → а5o5iu5 → a555 → A555
  • implementation → i514e5e53a3io5 → i51455335 → i514 → I514
  • Robert = Rupert → R163, Rubin → R150
  • Ashcraft = Ashcroft → A261 (но не A226: буквы s и c в словах дадут одну цифру 2, а не 22, так как разделены h).
  • Tymczak → T522, а не T520 (буквы z и k заменяются на 22, так как разделены гласной).

Примечания

[править | править код]
  1. ↑ U.S. Patent 1 261 167
  2. ↑ U.S. Patent 1 435 663
  3. ↑ Дональд Кнут. Часть 6. Поиск // Искусство программирования = The Art of Computer Programming. — 2012. — Т. 3. Сортировка и поиск. — С. 249.
Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Soundex&oldid=127468119