Comments 22
У вас вот этот кусок кода 2 раза подряд в тексте:
Кстати, он мог бы быть короче и быстрее:
foreach($possibleWord as $n=>$k)
{
if(levenshtein($k, $myWord) < $min_levenshtein)
{
$min_levenshtein = levenshtein($k, $myWord);
}
if(levenshtein(metaphone($k), metaphone($myWord)) < $meta_min_levenshtein)
{
$meta_min_levenshtein = levenshtein(metaphone($k), metaphone($myWord));
}
}Кстати, он мог бы быть короче и быстрее:
foreach($possibleWord as $k)
{
$min_levenshtein = min($min_levenshtein, levenshtein($k, $myWord));
$meta_min_levenshtein = min($meta_min_levenshtein, levenshtein(metaphone($k), metaphone($myWord)));
}
Спасибо, переписал немного код.
Спасибо за Левенштейна, познавательно.
Пока пользуюсь в проекте Aspell+tsearch. Aspell'у можно поручить поиск ближайших, работает быстро: 50 результатов в секунду на моем стареньком PPC 1.2GHz 512MB
aspell.suggest(«превед»)
=> [«перед», «переведи», «переведя», «правде», «пред», «прежде», «краевед», «перевей», «перевес», «перевод», «поревем», «поревет», «приведи», «приведя», «проведи», «проведя», «певец», «правд», «прете», «ревем», «ревет», «Певек», «переда», «передо», «правее», «бревен», «древен», «плевел», «прадед», «правей», «предел», «прелюд», «привес», «привет», «привод», «провод», «предо», «правда», «резеда», «праведный», «пребелый»]
Пока пользуюсь в проекте Aspell+tsearch. Aspell'у можно поручить поиск ближайших, работает быстро: 50 результатов в секунду на моем стареньком PPC 1.2GHz 512MB
aspell.suggest(«превед»)
=> [«перед», «переведи», «переведя», «правде», «пред», «прежде», «краевед», «перевей», «перевес», «перевод», «поревем», «поревет», «приведи», «приведя», «проведи», «проведя», «певец», «правд», «прете», «ревем», «ревет», «Певек», «переда», «передо», «правее», «бревен», «древен», «плевел», «прадед», «правей», «предел», «прелюд», «привес», «привет», «привод», «провод», «предо», «правда», «резеда», «праведный», «пребелый»]
А постгресовские модули fts и fuzzystrmatch, позволяющие сделать всё тоже самое внутри БД не подошли?
Может кто и словарик подскажет со всеми формами слов где скачать?
Вот зачем хранить словарь в базе — не совсем понятно (кроме удобства), можно сгенерировать массивчик для php и заранее инклюдить php-файл с массивом, интересно, насколько быстрее будет.
Вот зачем хранить словарь в базе — не совсем понятно (кроме удобства), можно сгенерировать массивчик для php и заранее инклюдить php-файл с массивом, интересно, насколько быстрее будет.
Нашел вот это:
Морфологический словарь на основе словаря Зализняка (MS Access) faqproject.ru/morphological-dictionary-russian-download.html. Правда, за скачивание там денег хотят ($25).
Нужно ли Вам это, посмотрите там же на скриншоты этого словаря.
Учтите, кстати, в этом словаре ошибок много.
Морфологический словарь на основе словаря Зализняка (MS Access) faqproject.ru/morphological-dictionary-russian-download.html. Правда, за скачивание там денег хотят ($25).
Нужно ли Вам это, посмотрите там же на скриншоты этого словаря.
Учтите, кстати, в этом словаре ошибок много.
Для определения словоформ можно mystem или lemmatizer использовать. А реализовать это лучше в виде модуля php, чтобы всё в память грузить.
база русских слов это круто. у меня база со словоформами включает 4.7млн записей (стырено у яндекса, когда-то давно они раздавали сорцы своего сильно обрезаного движка десктопного поиска с включенной базой, не составило труда это оттуда изъять), просто текстовый файл — 85Мб, база с индексами в mysql получается около 250Мб, а если ещё и пару сервисных столбцов засунуть, вдухе ссылки на корень слова и индексы построить по комбинациям — то 600-700мег. так вот, когда вы сделаете
$query = «SELECT ru_words FROM word_list»;
а потом ещё и пробежитесь по всему результату запихивая его в массив — тут-то ваш скрипт и помрет, скорее всего :) я уже молчу о
foreach($word_translit as $n=>$k)
только кэш, хэш и заранее построеные таблицы
$query = «SELECT ru_words FROM word_list»;
а потом ещё и пробежитесь по всему результату запихивая его в массив — тут-то ваш скрипт и помрет, скорее всего :) я уже молчу о
foreach($word_translit as $n=>$k)
только кэш, хэш и заранее построеные таблицы
Согласен, такой нагрузки он не выдержит, этот вариант — попытка сделать «чтоб работало» и получить какие-то советы от более опытных специалистов. Скрипт будет переписываться полностью с учетом советов, которые сейчас пишут в комментариях. Если не сложно, выложите пожалуйста куда-то вашу базу.
вот мой словарик
narod.ru/disk/7662133001/dictionary-rus.rar.html
narod.ru/disk/7662133001/dictionary-rus.rar.html
Предложите что-то лучше. Как по мне очень полезная статья. В 95% скрипт полезен в небольших тематических проектах и служит как эволюция в поиске.
я бы попробовал один из следующих путей:
1) Для каждого слова из словаря заранее построить искаженные формы с расстоянием Д-Л не большим какого-нибудь разумного числа, допустим 10. Таким образом составить отдельную таблицу искажений и для них уже найти нормальные слова.
Далее, когда пользователь что-то вводит ищем уже в построенной таблице искажений что он там ввел и соотв. номарльную форму. Если же он ввел что-то странное чего у нас ещё нет — упс, надо запустить ваш алгоритм, только найдем какую-нибудь его оптимизированную/распараллеленую форму, есть ссылки в англоязычной вики.
2) Использовать не метрику между введеным словом и словом словаря, а что-то где в вычислениях будет присутствовать только введенное слово. Допустим один из фонетических алгоритмов, а для словаря звучания посчитать заранее.
3) Проанализировать много текста (ту же библиотеку Мошкова) и найти допустим по 3-5 наиболее используемых слов всех возможных длин слов в словаре (у меня самое длинное слово из 37 букв, что-то там в духе спецстроймонтажпрокладка :) ).
Далее делаем таблицу на основе словаря — слово и ещё 5 столбоцов с расстояниями Д-Л или другой метрикой до тех 5и заранее найденых популярных слов.
Затем когда пользователь вводит слово, считаем метрику для ввода и популярных слов этой длины +-2, затем из построенной заранее таблицы выбираем слово с минимальной суммой разностей квадратов полученых и сохраненых метрик.
1) Для каждого слова из словаря заранее построить искаженные формы с расстоянием Д-Л не большим какого-нибудь разумного числа, допустим 10. Таким образом составить отдельную таблицу искажений и для них уже найти нормальные слова.
Далее, когда пользователь что-то вводит ищем уже в построенной таблице искажений что он там ввел и соотв. номарльную форму. Если же он ввел что-то странное чего у нас ещё нет — упс, надо запустить ваш алгоритм, только найдем какую-нибудь его оптимизированную/распараллеленую форму, есть ссылки в англоязычной вики.
2) Использовать не метрику между введеным словом и словом словаря, а что-то где в вычислениях будет присутствовать только введенное слово. Допустим один из фонетических алгоритмов, а для словаря звучания посчитать заранее.
3) Проанализировать много текста (ту же библиотеку Мошкова) и найти допустим по 3-5 наиболее используемых слов всех возможных длин слов в словаре (у меня самое длинное слово из 37 букв, что-то там в духе спецстроймонтажпрокладка :) ).
Далее делаем таблицу на основе словаря — слово и ещё 5 столбоцов с расстояниями Д-Л или другой метрикой до тех 5и заранее найденых популярных слов.
Затем когда пользователь вводит слово, считаем метрику для ввода и популярных слов этой длины +-2, затем из построенной заранее таблицы выбираем слово с минимальной суммой разностей квадратов полученых и сохраненых метрик.
А где буква «ё»? Я что-то ее мельком не нашел, а хром при Ctrl+F ищет в тексте и «е»
Мое упущение, но дописать в массив «Ё»=>«E» не составит труда. Если уже заговорили о транслитерации, то тут больше проблема в том, что одной русской букве может соответствовать до трех лат. Значит, при опечатке в этой букве, расстояние Левенштейна увеличится существенно. Поэтому лучше сделать простую замену букв один к одному, а разницу в количестве компенсировать, например, цифрами.
Так как словарь меняется редко — то его можно один раз подгрузить в расшаренную память, а в самом коде просто на чтение цепляться к этому куску памяти. Вариант несколько непортабельный, но быстрый. Но стаья очень интересная, спасибо!
Автор, ну есть же на хабре нормальный <source />, зачем использовать левый хайлайтер?
Очень хочется применить что-то подобное в нашем проекте, блин где бы найти highload решение и желательно под ruby? =)
$correct[] .= $myWord;что-то тут не так
Sign up to leave a comment.
Применение алгоритмов нечеткого поиска в PHP