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

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


Soundex был разработан Робертом Расселом (Robert C. Russel) и Маргарет Кинг Оделл (Margaret King Odell) и запатентован в 1918 и 1922 годах<ref>{{US patent|1,261,167}}</ref><ref>{{US patent|1,435,663}}</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}})
⚫
== Описание алгоритма ==
* Первая буква сохраняется
* В остальной части слова:
** Буквы, обозначающие, как правило, гласные звуки: a, e, h, i, o, u, w и y — отбрасываются
⚫
** Оставшиеся буквы (согласные) заменяются на цифры от 1 до 6, причём похожим по звучанию буквам соответствуют одинаковые цифры:
*** 1: b, f, p, v
⚫
*** 2: c, g, j, k, q, s, x, z
*** 3: d, t
*** 4: l
*** 5: m, n
*** 6: r
** Любая последовательность одинаковых цифр сокращается до одной такой цифры.
* Итоговая строка обрезается до первых четырёх символов. Если длина строки меньше требуемой, недостающие символы заменяются знаком 0.


⚫
== Шаги алгоритма ==
⚫
Примеры:
# Запоминается первая буква слова.
* аmmonium → ammnm → a5555 → a5 → a500
# Удаляются все вхождения <tt>[[H (латиница)|h]]</tt> и <tt>[[w]]</tt> (за исключением первой буквы слова).
* implementation → implmnttn → i51455335 → i514535 → i514
⚫
# Согласные заменяются на цифры от 1 до 6, причём похожим по звучанию буквам соответствуют одинаковые цифры:

⚫
#* <tt>b, f, p, v → 1</tt>

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


⚫
Примеры:
Примеры (первые 2 - те что приведены выше, остальные с английской вики):
* а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>, так как разделены гласной).
* "Pfister" → "P236", а не "P123" (Pfister → 11i23e6 → 1i23e6 → 1236 → P236).

== Пример исполнения ==
Ниже приведен пример реализации алгоритма на языке программирования [[Perl]].
<source lang="perl">
sub soundex
{
my $word = lc (shift // $_);
$word =~ tr/\t //d;
my $fl = substr $word, 0, 1;
$word = substr $word, 1;
$word =~ tr/bfpvcgjkqsxzdtlmnraehiouwy/111122222222334556/ds;
$word = "$fl$word";
return substr($word, 0, 4)."0" x (4 - length($word));
}
</source>
Ну и код видимо не верный. Скорее всего должно быть как-то так:
<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>
Не знаю, что за (shift // $_) в 1м примере было, но у меня перл ругался, потому убрал. Кто лучше перл знает - поправьте.

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


== Примечания ==
== Примечания ==
Строка 96: Строка 35:


{{нет источников|дата=2015-01-11}}
{{нет источников|дата=2015-01-11}}

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

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