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

[Astraport]

Наверное все видели когда неправильно набираешь текст в гугле например, то он предлагает свое значение. Мне требуется что-то похожее.

Пользователь вводит возможно бессмысленный набор букв (или машинный рандом, неважно), а программа должна каким-то образом сравнивать куски текста с базой слов в словаре и предлагать наиболее подходящие значения причем отсортированные по степени релевантности. Например, на запрос «натусупиалонесь» – выдаст как наиболее правильный «наступила осень».
То есть программа должна проанализировать текст, разделить набор букв на слова и выбрать самые подходящие варианты слов.

Не сталкивался ли кто с решениями такой задачи? Библиотеки, исходники, словари?

[mooncar]

Бесплатный пакет вряд ли найдете.
Тут придется разделять строку на кусочки и проверять каждый кусочек по отдельности на какую-то близость к известным словоформам, то есть еще и морфология! Результат где-то хранить временно. Потом пошагово выводить общую релевантность.
Такого даже у Гугла нет.
Вообще, задачка тянет на работу небольшой команды разработчиков не на один месяц.

[iNils]

на запрос «натусупиалонесь» – выдаст... ссылку на эту тему.

[Astraport]

Бесплатный пакет вряд ли найдете.
Тут придется разделять строку на кусочки и проверять каждый кусочек по отдельности на какую-то близость к известным словоформам, то есть еще и морфология! Результат где-то хранить временно. Потом пошагово выводить общую релевантность.
Такого даже у Гугла нет.
Да, я так и предполагал. Мне такая работа не под силу. Вот и ищу подобные реализации.
на запрос «натусупиалонесь» – выдаст... ссылку на эту тему.
На все форумы где я спрашивал:)

Добавлено через 2 минуты
Хорошо. А если упростить задачу и текст будет разделен по словам. Есть же выражение %LIKE% в mySQL. Может есть какой-то подобный способ выборки по базе данных?

[i.o.]

Такого даже у Гугла нет.
зато во FlashDevelop автокомплит именно так работает. Ищет наиболее похожие названия на ввод всякой несуразицы.

[VovkaMorkovka1]

Попробуйте расстояние Хемминга поискать

[Psycho Tiger]

Можно сделать нейросеть и обучить её программой, которая перемешивала бы каждое слово из базы по алгоритму.

[gloomyBrain]

зато во FlashDevelop автокомплит именно так работает

Насколько я помню, во FlashDevelop поиск идет по последовательности букв, а не по похожести. То есть, если набрать ader одним из вариантов будет addEventListener, т.к. в этом слове эти буквы идут друг за другом. Если набрать adezer, то addEventListener в окошке автокомплита не появится

[Котяра]

Попробуйте расстояние Хемминга поискать

Можно сделать нейросеть и обучить её программой, которая перемешивала бы каждое слово из базы по алгоритму.

Вы ещё рандомизированный алгоритм стохастической аппроксимации предложите)

Вообще для начала надо чётко сформализировать задачу:

Из множества символов выбрать группу совпадующую с паттернами за исключением 2-3(?) символов или по-другому? Они ещё и могут быть местами поменяны?.
тут уже начинается самое интересное:
переборы вариантов.
Если в лоб то просто циничным перебором, для начала ищем полные совпадения 3 букв/4/5 итп до несовпадения - меняем 6 на *
проверяем 12345*7 (причём буквы в множестве имеют больший приоритет по сравнению с остальным алфавитом) - если поиск закончился значит либо пробел либо мы не правильно начали заменять с 6 пункта..
в общем как-то так + добавить весов вариантов каких нибудь..
Это чисто теория на практике надо будет ещё очень и очень оптимизировать такие гигантские вычисления
Варианты: кэш и прочее, т.к. чаще всего люди либо просто ошибаются ( Жы-Шы, Варабей, Хлеб)

Кстати пиша/пися этот текст в FF вспомнил про проверку орфографии..
ищите в исходниках FireFox.
он предлагает поменять Жы-Шы на Шипы, что вроде близко к вашей задаче.
а натусупиалонесь = натуралистичность

[Astraport]

Я нашел решение в триграммах Сфинкса (могу скинуть ссылку на статью на Хабре, если кого заинтересовало). Хотя пока не реализовал. Спасибо за FlashDevelop, все никак не проверю этого зверя:)

[AS3Coder]

Если речь идет об ActionScript 3.0 то у Adobe уже имеется готовое решение (http://labs.adobe.com/technologies/squiggly/). Проект "Squiggly". Правда в пререлизе еще, но пользоваться уже можно.

[Astraport]

Если речь идет об ActionScript 3.0 то у Adobe уже имеется готовое решение. Проект "Squiggly". Правда в пререлизе еще, но пользоваться уже можно.
Ого! Спасибо большое, нужно испробовать. Жалко для русского языка нет, но может быть удастся наш словарь подключить.

[AS3Coder]

О том как этим пользоваться "Проверка орфографии в ActionScript 3. (http://as3coder.blogspot.com/2010/10/actionscript-30.html)0". Подключить можно, уже пробовал. Ссылка на словари также имеется в посте.

[Astraport]

Блин, с меня ящик пива:) Спасибо, огромное!

[kutuzov]

а ещё есть Яндекс.Спеллер

[shaman4d]

для быстрого поиска в гугле используются цепи Маркова. Погуглите примеры использования их, они просты в реализации.