Поиск схожих слов.

[melo]

Привет.
Есть задача, на вход поступает предложение. Есть справочник, с количеством слов более 10тыщ. Введенное предложение может быть написано с ошибками/опечатками. Необходимо из этого справочника найти слова наиболее близкие к словам из предложения. Если слово из справочника совпадает со словом из предложения, то ошибки нет. Я использую функцию levenshtein. Справочник сам лежит в файле. Читаю этот файл и все запихиваю в массив и сортирую в нем слова по длине. Потом слова из введенного предложения сравниваю с частью массива, в котором слова по длине равны, если ничего не нахожу, беру массив длина+1, если снова ничего, то массив длина-1, дальше +2, -2. Цена любой операции у меня равна 1. Вот, все вроде бы работает, но при длинном предложении есть тормоза) Хочу спросить, есть ли какие-то общие алгоритмы для таких задач? Нормально ли держать такой большой массив в памяти(хотя как по-другому я хз)?

 

[Welcome]

sphinx?

 

[melo]

нене, друг, тут сфинкс не покатит, именно такие условия.

 

[iceman]

по другому - держать его в БАЗЕ ДАННЫХ

 

[Sender]

Случаем не пазлами балуешься? http://www.facebook.com/careers/puzzles.php?puzzle_id=17?

 

[melo]

Sender
да, это оно))) Взявшись делать, понял, что я совсем ничего не смыслю в типовых алгоритмах)
iceman
в базе не могу)

 

[Sender]

Да, задачки там зачетные, мозги шевелят, тоже на алкоанализаторе застрял

Вот мой вариант, суть та же что и у тебя, только разве что ты не описал условия выхода из циклов.
http://ewgra.googlecode.com/svn/trunk/facebookPuzzle/breathalyzer

Но он не проходит Не знаю почему, работает довольно шустро по моему мнению.

Есть мысли которые надо пробовать:

1. поиск расстояния для коротких слов работает быстрее, то есть надо искать нужное расстояние начиная с коротких слов.

2. php не лучший язык для этой задачи видимо надо пробовать другой. Там народ отписывался что выполняются тесты ~1 сек, те которые у меня 60 сек занимают. Может конечно машинка у меня слабенькая.

3. возможно реализация функции Левеншейна в php не самая лучшая. Есть мысль закодить участки в функции, чтобы профайлер показал более точно какие участки тормозят.


А так я где что не читал по этой задаче, никаких особых чудес там не придумано. Все варианты кода которые я видел примерно реализуют один алгоритм.


Покажи свой liarliar интересно сравнить скорость.

 

[craz]

переведите на русский плиз задание или ссылку дайте, там на каком то не понятном сленге написано.. Чето не до понимаю сути

 

[melo]

Я только начал, и во втором блоке сразу взялся за эту. liarliar ещё не делал.

1. Возможно, надо тестить.
2. Да, я вот поэтому тоже удивлен. Все пишут там 1 секунда, я аж в недоумении. Но нашел пост, что кто-то из писавших на пхп, написал, что его тест прошел. Вот и думаю, может алгорит неправильный.
3. Ну тут сомневаюсь.

Тоже, на сколько читал, то никаких чудес там нет. странно.

 

[melo]

craz
у тебя есть входное предложение, которое может написать кто-то пьяный например. у тебя также есть словарь, который лежит в текстовом файле. надо найти минимальное расстояние между словами введенными в предложении и со словаря, цена замены, удаления, добавления = 1.

 

[Sender]

Я только начал, и во втором блоке сразу взялся за эту. liarliar ещё не делал.

1. Возможно, надо тестить.
2. Да, я вот поэтому тоже удивлен. Все пишут там 1 секунда, я аж в недоумении. Но нашел пост, что кто-то из писавших на пхп, написал, что его тест прошел. Вот и думаю, может алгорит неправильный.
3. Ну тут сомневаюсь.

Тоже, на сколько читал, то никаких чудес там нет. странно.

Пройди обязательно meepmeep, просто чтобы убедиться что ты правильно решение оформляешь. Я первые три раза неправильно решение оформлял, еще там были проблемы с отсылкой решений с gmail, но сейчас их устранили, все в порядке.

liarliar тоже веселый пазл, мне кажется даже сложнее breathalyzer. На выходных попробую след. итерацию отправить, может прокатит.

 

[melo]

я эти два прошел - hoppity, meepmeep. и потом сразу за breathalyzer.
а у тебя breathalyzer прошел?

 

[craz]

а всякие методы золотого сечение вы применяете?

 

[Sender]

я эти два прошел - hoppity, meepmeep. и потом сразу за breathalyzer.
а у тебя breathalyzer прошел?

нет, я писал что не проходит и почему не знаю, скорее всего потому что медленно

а всякие методы золотого сечение вы применяете?

тут имхо это не применимо, если мы проверим одну точку, то не можем однозначно утверждать что искомое решение лежит справа или слева. По крайней мере я не вижу возможности отсортировать так эталонные слова. Это имелось ввиду? Если нет то поподробнее расскажи

 

[Sender]

Your solution ran for 8158.586 ms on its longest test case
В общем решил.

Вот тут описана странная ошибка с которой я столкнулся:
http://www.facebook.com/topic.php?uid=15325934266&topic=15405