Подскажите аглоритм проверики строки на примерную схожесть

← →
leonidus © (2007-02-05 08:56) [0]

Господа, есть такая задача. Человек вводит в строке поиска некое слово и жмет кнопку "искать" если данное слово на найдено, программа делает предположение что слово набрано с грамматической ошибкой и должна показать юзеру список слов "похожих" на введенное для того, чтобы он мог быстро повторить поиск, собственно так поступает яндекс. Как реализовать подобный алгоритм?

← →
Separator © (2007-02-05 08:59) [1]

Яндекс поступает не так

← →
Думкин © (2007-02-05 09:02) [2]

Надо ввести на множестве слов метрику. Близкими считать слова, которые имеют расстояние до заданного меньше некоторого фиксированного предела.

← →
novill © (2007-02-05 09:04) [3]

Для начала нужен словарь "правильных" слов.
Для введенного слова высчитывается "расстояние" до "ближайщих" слов в словаре, из ближайших выбирается наиболее частоупотребимое.

В данном случае расстояние - количество элементарных операций для получения слова находящегося в словаре.

← →
leonidus © (2007-02-05 09:25) [4]

>novill словарь правильных слов есть, а как посчитать "расстояние" до ближайших слов, каков в данном случае критерий?

← →
pasha_golub © (2007-02-05 09:31) [5]

> leonidus © (05.02.07 09:25) [4]

Критерий близкорасположенности клавиш на клавиатуре в основном. Ну, и безударные глассные.

← →
@!!ex © (2007-02-05 09:32) [6]

> leonidus © (05.02.07 09:25) [4]

Количество различных символов + смещение.

← →
Kolan © (2007-02-05 09:44) [7]

Есть дома функция которая в процентах возвращает похожесть строк. С этого форума брал, вечером поищу...

← →
novill © (2007-02-05 09:55) [8]

> [4] leonidus © (05.02.07 09:25)
Это уже мат. теория, я сейчас всю ее не расскажу, лучше посмотри в нете.

Если "на пальцах"
За единицу расстояния берется одна элементарная операция с буквами слова например: замена, перестановка, удаление, вставка буквы. Дальше перебор кобминаций. Нахождение наименьшего количества операций между выбранной парой слов. Обычно расстояние >1 не берут, накладно это.

Еще есть смысл предварительно отфильтровать слова пере расчетом расстояний (например по длине и наличию одинаковых букв)

ЗЫ еще раз рекомендую посмотреть алгоритмы в нете.

Вот тут почитай первую главу
http://monkey.belozersky.msu.ru/~evgeniy/genetext_analizys.djvu (3 метра)

>novill а как такой алгоритм по научному называется

>TUser спасибо за ссылочку, сейчас почитаю.

>Kolan поищите пожалуйста, буду очень признательно

http://algolist.manual.ru/search/lcs/

Подскажите аглоритм проверики строки на примерную схожесть Найти похожие ветки