Когда отношение эквивалентности используется для определения классов, оказывается полезным определить сигнатуру, отличающую эти классы друг от друга. Сортировка букв слова дает одну из возможных сигнатур для анаграмм, другие варианты могут быть получены, к примеру, путем сортировки и последующей замены повторяющихся букв цифрами, указывающими их количество в слове. Сигнатурой слова mississippi в этом случае будет i4mlp2s4 или i4mp2s4 (если единицу по умолчанию не указывать). Можно также хранить массив из 26 целых чисел (для каждого слова), который будет содержать информацию о количестве повторяющихся букв. Другие области применения сигнатур включают используемый ФБР метод индексации отпечатков пальцев и эвристические алгоритмы Soundex для объединения имен, одинаково звучащих, но по-разному пишущихся (табл. 2.1).
Кнут описывает метод Soundex в главе 6 третьего тома книги «Искусство программирования для ЭВМ, сортировка и поиск».
Опубликовал vovan666
April 16 2013 23:34:49 ·
0 Комментариев ·
3209 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
