Дмитрий Кузан
дата публикации 10-12-2002 16:11 Еще раз о нечетком сравнении строк
По мотивам обсуждения статьи Функция приблизительного/нечеткого сравнения строк
Второй вариант поиска : Compare1.zip (359 K)
Отличия от первого, по моим субъективным наблюдениям, в следующем:
- 1.Лучше находит похожие слова лежащие в одной плоскости
-
Соха - Сноха - совпадение 88 при том что в первом алгоритме составило 66 при
длине фразы = 3
- 2.Хуже находит похожие (даже идентичные), но перевернутые слова
-
Тихий Дон - Дон Тихий - в первом способе совпадение 79 во втором 55 - очень
существено.
Так что первый способ я рекомендовал для сравнения, например, полей двух баз данных.
Второй способ, по моему убеждению, лучше использовать в поиске по словарю или в тех
местах, где надо найти фразу.
Вообще-то, существуют еще, кроме этих, алгоритмы поиска. Я бы выделил SoundEx
для сравнения, но у него есть свои недостатки — он языкозависим, но отлично
подходит для сравнения английских фраз.
Если вас это заинтересует то могу прислать в оригинале (написан он на C), но перевести в Pascal для людей
которых это заинтересует, не составит труда.
И, напоследок, предлагаю вам архив с примерами алгоритмов анализа строк. К
сожалению страницы указанные в архиве, как начальные, где можно найти
информацию, не работают - поэтому высылаю слепок с сайта.
Скачать Stephen.zip (185 К)
На данных страницах лежит очень много алгоритмов касающихся анализа строк,
приведу список причем очень хорошо документированных и математически
обоснованных.
3. ОБЗОР АЛГОРИТМОВ
- 3. 1 Сопоставления строк
- 3. 2 Расстояния между строками
- 3. 2.1 Обобщенные задачи
- 3. 3 Нечеткое сопоставление строк
- 3. 3.1 Специальные устройства
- 3. 4 Максимальная повторяющаяся подстрока
4. АЛГОРИТМЫ
- 4. 1 Поиск образцов
- 4. 1.1 Наивный подход
- 4. 1.2 Кнут-Моррис-Пратт
- 4. 1.3 Бойер-Мур
- 4. 1.4 Бойер-Мур-Хорспул
- 4. 1.5 Сандей: Быстрый поиск, Максимальный сдвиг, Оптимальное несовпадение
- 4. 1.6 Хьюм и Сандей. Улучшенные алгоритмы Бойера-Мура и Наименьшая цена
- 4. 1.7 Харрисон
- 4. 1.8 Карп-Рабин
- 4. 2 Расстояние между строками и самая длинная общая подпоследовательность
- 4. 2.1 Вагнер-Фишер
- 4. 2.2 Хиршберг
- 4. 2.3 Хант-Шиманский
- 4. 2.4 Машек-Патерсон
- 4. 2.5 Укконен
- 4. 2.6 Самая тяжелая общая подпоследовательность
4. 3 НЕЧЕТКОЕ СОПОСТАВЛЕНИЕ СТРОК
- 4. 3.1 k несовпадений - Ландау-Вишкин
- 4. 3.2 k различий - Ландау-Вишкин
- 4. 4 Самая длинная повторяющаяся подстрока
- 4. 4.1 Наивный подход
- 4. 4.2 Суффиксные деревья
Кузан Дмитрий
[Нечеткое сравнение]
 Обсуждение материала [ 25-04-2003 19:36 ] 7 сообщений |
