Rambler's Top100
"Knowledge itself is power"
F.Bacon
Поиск | Карта сайта | Помощь | О проекте | ТТХ  
 Сокровищница
  
 

Фильтр по датам

 
 К н и г и
 
Книжная полка
 
 
Библиотека
 
  
  
 


Поиск
 
Поиск по КС
Поиск в статьях
Яndex© + Google©
Поиск книг

 
  
Тематический каталог
Все манускрипты

 
  
Карта VCL
ОШИБКИ
Сообщения системы

 
Форумы
 
Круглый стол
Новые вопросы

 
  
Базарная площадь
Городская площадь

 
   
С Л С

 
Летопись
 
Королевские Хроники
Рыцарский Зал
Глас народа!

 
  
ТТХ
Конкурсы
Королевская клюква

 
Разделы
 
Hello, World!
Лицей

Квинтана

 
  
Сокровищница
Подземелье Магов
Подводные камни
Свитки

 
  
Школа ОБЕРОНА

 
  
Арсенальная башня
Фолианты
Полигон

 
  
Книга Песка
Дальние земли

 
  
АРХИВЫ

 
 

Сейчас на сайте присутствуют:
 
  
 
Во Флориде и в Королевстве сейчас  13:24[Войти] | [Зарегистрироваться]

Еще раз о нечетком сравнении строк

Дмитрий Кузан
дата публикации 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 сообщений
  
Время на сайте: GMT минус 5 часов

Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter.
Функция может не работать в некоторых версиях броузеров.

Web hosting for this web site provided by DotNetPark (ASP.NET, SharePoint, MS SQL hosting)  
Software for IIS, Hyper-V, MS SQL. Tools for Windows server administrators. Server migration utilities  

 
© При использовании любых материалов «Королевства Delphi» необходимо указывать источник информации. Перепечатка авторских статей возможна только при согласии всех авторов и администрации сайта.
Все используемые на сайте торговые марки являются собственностью их производителей.

Яндекс цитирования