Нужен алгоритм анализа текста

[VG2]

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

 

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

То есть программа должна проанализировать текст, разделить набор букв на слова и выбрать самые подходящие варианты слов.

 

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

[e-van]

хм... погуглил «натусупиалонесь» вот результат

 

 

как вариант - может сам гугль и подтягивать? хотя поисковик тока один результат подбора выдает. попробовал ворд подтянуть, тож не айс..

[VG2]

как вариант - может сам гугль и подтягивать?

Это первое что пришло в голову, но как?

Пусть хотя бы для начала один вариант. Можно отправлять запрос, парсить результат, выводить результат. Но это же будет все видно юзеру? Или не так?

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

[e-van]

по простому запросу "онесь" гугля выдает только "олесь"

не думаю, что подходит этот вариант )))

[VG2]

Да, это плохой алгоритм. Нужно что-то другое.

Например есть база наиболее употребляемых слов в русском языке, допустим в 10 тыс. слов.

Код должен брать с начала строки 5 символов, сравнивать с базой, заносить во временные результаты найденное, потом увеличивать до 6 символов, потом уменьшать до 4-х. Потом из временных результатов каким-то образом выбрать наиболее подходящее.

Короче задача сложнейшая для разработки с нуля. Нужна какая-то библиотека или готовый движок.

[e-van]

Код должен брать с начала строки 5 символов

а если начало как-раз и кривое? тогда все результаты будут с другим началом

а назначение такой проги можно узнать?

З.Ы. а если по хеш-сумме искать?

[VG2]

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

[PurtCer]

http://api.yandex.ru/speller/ - может пригодиться.

[mr.Faster]

LIKE - хуйня.

твой выбор сфинкс или полнотекстовый поиск mysql

[VG2]

может пригодиться.

нет, это совсем не в тему.

твой выбор сфинкс

А что это? как найти хоть

[VG2]

http://norvig.com/spell-correct.html - вот что нашел. Все не очень сложно и на разных языках. Я так правильно понял, что это скрипт исправления ошибок и вполне может подойти для моего случая?

[mr.Faster]

http://habrahabr.ru/blogs/sphinx/64325/

[VG2]

Спасибоmr.Faster интересно.

[VG2]

Мне тут посоветовали:

1. Использовать Soundex http://www.madirish.net/?article=85

2. Использовать similar_text в PHP

 

Если по второму варианту все ясно и в принципе можно использовать эту функцию для фильтрования выборки LIKE, то по первому варианту все сложнее.

Видимо возможное решение такое:

1. Находим словарь наиболее употребимых русских слов (например 20 тыс.)

2. Создаем на его основе БД.

3. Добавляем новое поле и к каждому слову значение от Soundex (например soundex('text') - это T230.

4. При запросе дергаем скрипт, который переводит запрос в формат soundex и ищет тоже самое в базе (возможно вместе с %LIKE%).

5. Найдя, возвращает нормальное значение и с помощью similar_text сравнивается с оригиналом и выводится процент соответствия.

 

Как находите такой вариант?

 

UPDATE для русского языка функция Soundex не работает

[VG2]

Проанализировав массу материалов я нашел наиболее оптимальное решение - триграммы Сфинкса на который меня навел mr.Faster.

 

И почему гугл не знает о Сфинксе

[VG2]

Вот слепил - сразу на двух языках

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

[e-van]

хм.. чота не работает у мну

[VG2]

хм.. чота не работает у мну

Конкретнее можно?

[e-van]

ввожу текст и жму "найти подобие" и тишина

[VG2]

ввожу текст и жму "найти подобие" и тишина

Текст какой? введи "лсинта", можно копипейстом

[Mastak]

Гляньте в Википедии "расстояние Левенштейна". Это как раз тот способ, которым поисковики автозамену подбирают. Но словарь дял сравнения нужен, это да.