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

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


Разработан Робертом Расселом ({{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>{{книга
Этот алгоритм имеет сильную зависимость от языка, слова которого сравниваются.
⚫
|автор = [[Дональд Кнут]]

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


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


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


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


== Примечания ==
==Пример исполнения==
{{примечания}}
Ниже приведен пример реализации алгоритма на языке программирования [[Perl]].
<source lang="perl">
sub soundex { # return soundex code
my($useword) = $_[0];
my($result) = "0000";
my($idx,$prev,$perhaps,$thechar);
$useword =~ tr/ //d; # rid spaces
$useword = lc($useword); # lower-case for consistency
if (length($useword) < 1) {
return($result);
}
$result = substr($useword,0,1); # first letter
$prev = "0";
$idx = 1;
while ($idx <= length($useword)) {
$perhaps = "0";
$thechar = substr($useword,$idx - 1,1);
if (index("bfpv", $thechar) >= 0) { $perhaps = "1"; }
if (index("cgjkqsxz",$thechar) >= 0) { $perhaps = "2"; }
if (index("dt", $thechar) >= 0) { $perhaps = "3"; }
if (index("l", $thechar) >= 0) { $perhaps = "4"; }
if (index("mn", $thechar) >= 0) { $perhaps = "5"; }
if (index("r", $thechar) >= 0) { $perhaps = "6"; }
if ($perhaps != $prev && $perhaps != "0"
&& $idx != 1) { # avoid dups and ignore first
$result .= $perhaps;
}
$prev = $perhaps;
$idx++;
} #endwhile
$result .= "0000"; # pad with zeros to ensure min length
$result = substr($result,0,4); # only return first four
return($result);
}
</source>


{{нет источников|дата=2015-01-11}}
== См. также ==
* [[Metaphone]]

== Ссылки на попытки создания soundex для русского языка ==
* http://community.livejournal.com/ru_php/1062493.html
* http://kankowski.narod.ru/dev/metaphoneru.htm


[[Категория:Строковые алгоритмы]]
[[Категория:Строковые алгоритмы]]

[[de:Soundex]]
[[en:Soundex]]
[[es:Soundex]]
[[fr:Soundex]]
[[he:סאונדקס]]
[[pl:Soundex]]
[[tr:Soundex]]
[[vi:Soundex]]
[[zh:Soundex]]

Текущая версия от 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