Soundex: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Нет описания правки |
Tv0r0g (обсуждение | вклад) Нет описания правки |
||
| Строка 26: | Строка 26: | ||
Примеры: |
Примеры: |
||
* аmmonium -> ammnm -> a5555 -> a5 |
* аmmonium -> ammnm -> a5555 -> a5 |
||
* implementation -> implmnttn -> |
* implementation -> implmnttn -> i51455335 -> i514535 -> i514 |
||
==Пример исполнения== |
==Пример исполнения== |
||
Ниже приведен пример реализации алгоритма на языке программирования [[Perl]]. |
Ниже приведен пример реализации алгоритма на языке программирования [[Perl]]. |
||
<source lang="perl"> |
<source lang="perl"> |
||
sub soundex |
|||
{ |
|||
my($useword) = $_[0]; |
|||
my |
my $word = lc (shift // $_); |
||
$word =~ tr/\t //d; |
|||
my($idx,$prev,$perhaps,$thechar); |
|||
| ⚫ | |||
| ⚫ | |||
$useword =~ tr/ //d; # rid spaces |
|||
$word = substr $word, 1; |
|||
$useword = lc($useword); # lower-case for consistency |
|||
if (length($useword) < 1) { |
|||
$word =~ tr/bfpvcgjkqsxzdtlmnraehiouwy/111122222222334556/ds; |
|||
return($result); |
|||
return substr "$fl$word", 0, 4; |
|||
} |
|||
} |
|||
$result = substr($useword,0,1); # first letter |
|||
$prev = "0"; |
|||
$idx = 1; |
|||
while ($idx <= length($useword)) { |
|||
$perhaps = "0"; |
|||
| ⚫ | |||
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> |
</source> |
||
Версия от 01:53, 24 мая 2010
Soundex — алгоритм сравнения двух строк по их звучанию. Он устанавливает одинаковый индекс для строк, имеющих схожее звучание.
Этот алгоритм имеет сильную зависимость от языка, слова которого сравниваются.
Soundex был разработан Робертом Расселлом (Robert Russel) и Маргарет Обелл (Margaret Obell) и запатентован в 1918 и 1922 годах (U.S. Patent 1,261,167 и U.S. Patent 1,435,663). Этот алгоритм стал популярным в 1960-х годах, после того как стал темой нескольких статей в журналах «Communications of the Association for Computing» и «Journal of the Association for Computing Machinery» (CACM и JACM). Еще большую популярность этот алгоритм получил после того, как был опубликован в книге Дональда Кнута. Искусство программирования, том 1. Основные алгоритмы.
Описание
- Первая буква сохраняется
- В остальной части слова:
- Гласные (aehiouwy) выбрасываем
- Каждую согласную заменяем на цифру от 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
- Избавляемся от повторов: любая последовательность одинаковых цифр заменяется на одну такую цифру.
- Обрезаем до первых четырёх символов
Примеры:
- аmmonium -> ammnm -> a5555 -> a5
- implementation -> implmnttn -> i51455335 -> i514535 -> i514
Пример исполнения
Ниже приведен пример реализации алгоритма на языке программирования 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;
return substr "$fl$word", 0, 4;
}