Delphi World - Еще раз о нечетком сравнении строк
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Еще раз о нечетком сравнении строк

Автор: Дмитрий Кузан

По мотивам обсуждения статьи Функция приблизительного (нечеткого) сравнения строк

Второй вариант поиска: 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 Суффиксные деревья
Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования