Эта тема на forum.dklab.ru


Юрий Насретдинов: Неточный поиск
Вот, пытаюсь разработать алгоритм для неточного поиска... Кое-что у меня, конечно, получается, но ищет он больно медленно - около мегабайта индекса в секунду, а точный поиск ищет со скоростью 60 мегабайт/сек:


<?
$file="index.dat";
//**
function find($q)
{
global $r,$sz;
$res=array();
//**
for($i=0;$i<$sz;$i++)
{
$t=explode("\t",$r[$i]);
$a=explode(" ",$t[2]);
$siz=sizeof($a);
for($j=0;$j<$siz;$j++) if(levenshtein($a[$j],$q)<3) @$res[$i]+=1;
}
//**
return $res;
}
//**
?>
<form action='index.php?search' method=post>
<input type='text' name='name' value='<?if(isset($_POST['name'])) echo $_POST['name'];else echo "запрос";?>'>&nbsp;<input type='submit' value='найти!'>
</form>
<?
if(isset($_POST['name']))
{
$time=explode(" ",microtime());
$time=$time[0] + $time[1];
//**
$f=fopen($file,"rb");
$r=explode("\n",fread($f,filesize($file)));
fclose($f);
$sz=sizeof($r)-1;
//**
$res=find($_POST['name']);
asort($res,SORT_NUMERIC);
//**
foreach($res as $k=>$v)
{
$tmp=explode("\t",$r[$k]);
echo "<br><a href='".$tmp[0]."'>".$tmp[1]."</a> - ";
$a=explode(" ",$tmp[2]);
$siz=sizeof($a);
for($j=0;$j<$siz;$j++) if(levenshtein($a[$j],$_POST['name'])<3) echo "... ".$a[$j-2]." ".$a[$j-1]." <b>".$a[$j]."</b> ".$a[$j+1]." ".$a[$j+2]."...";
}
//**
$time1=explode(" ",microtime());
echo "<br><br>Время генерации: ".(($time1[0]+$time1[1])-$time)." сек";
}
?>


В индексе записи идут следующим образом:

URL \t Заголовок страницы \t текст индекса \n
URL \t Заголовок другой страницы \t текст индекса другого документа \n
...

Догадываюсь, что никому не захочется читать этот код, и вникать в него, но тем не менее. Написал я этот алгоритм за 5 минут, хочу выставить на суд вам. Хотелось бы услышать предложения по оптимизации алгоритма неточного поиска, и т.д... И возможно ли это вообще :).
Евгений Галашин:
Вникать действительно лень...
Моя идея такая: выбирать "кандидетав" из индекса, у которых совпадают первые две-три буквы. После этого - ищем левенштейн-расстояние. ИМХО будет гораздо быстрее...
Кирилл Моисеенков:
Видели, как сделал индекс я в своём скрипте? Очень даже быстро. Только индексирует действительно довольно медленно (только большие объёмы > 10 мегабайт).
Евгений Галашин:
Кирилл Моисеенков:
Нет. неужели, что-то страшно уникальное?..
Silent:
Тут как раз самое время переходить на нормальный инвертированный индекс, который обсуждается в соседней теме. Потому что тогда вместо перебора 100Мб перебирать придется только лексикон, который будет иметь примерно 100000 уникальных слов (зависит от характера текстов и языка), что при средней длине слова 10 символов дает около 1 Мб. Уже стократное ускорение. А если ввести различные ограничения (например первая буква слова из запроса должна быть правильной), то можно и еще ускорить в десяток раз.
Кирилл Моисеенков:
Евгений Галашин:
http://www.hvuneland.narod.ru/mixeyka/vonuchka/fuzzysearch.rar
Создайте базу и посмотрите на индекс в data.php. Впечатляет *)
Юрий Насретдинов:
Создайте базу и посмотрите на индекс в data.php. Впечатляет *)
Здорово ! Просто замечтательно ! Особенно если учесть, что выдается Parse error: parse error, unexpected '}' in search.php on line 225
Евгений Галашин:
Кирилл Моисеенков:
Лень. ВЫ б хоть код форматировать научились...
Ну и что там за супер-индекс? php-массив?.. Старо...
Дмитрий Котеров:
yUAC:
По-моему, ты не совсем правильно понимаешь, что такое индекс. Видел в книгах предметный указатель, отсортированный по алфавиту? Вот это — индекс.
Кирилл Моисеенков:
yUAC:
Исправил. Лежит на http://www.hvuneland.narod.ru/dklab/fuzzysearch.rar .
Config.php поправьте путь к папке scandir.
Юрий Насретдинов:
Дмитрий Котеров:
Да, ты наверное прав :) . И все же, разрабатывать поиск на PHP для больших сайтов или не имеет смысла, или нужно очень долго ломать голову над оптимизацией такого поиска :)_
Кирилл Моисеенков:
yUAC:
Конечно. У неточного поиска есть как минимум два огроменных минуса:
1. Скорость.
2. Несоответствие запросу. Т. е. скрипт постоянно будет думать, что юзер ошибся, будет считать сам мебя "более умным". Даже Яндекс с его точным поиском (но со словарём и проверкой морфологии) всё равно ошибается.

По поводу скрипта. Кто Вам сказал, что неточный поиск - это только метрика Владимира Левенштайна (1965 г.)? (наверное я =)). А Хемминг, а Similar_text?
Вот Вам пара :) полезных линков:
http://algolist.manual.ru/search/lcs/vagner.php - отличный док! Я с ним на конференции выступал :).
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/ - тоже очень интересный
http://aforge.ibd.lv/?27 - очень ясный алгоритм
http://www.merriampark.com/ld.htm - хороший англ. док
http://webmaster.pp.ru/php4/levenshtein.html - ман с пхп.нет, переведённый Пирамидиным
http://webmaster.pp.ru/php4/similar-text.html - ман с пхп.нет, переведённый Пирамидиным
http://alglib.manual.ru/articles/search.php - озор методов поиска
http://www.itman.narod.ru/ - сайт, полностью посвящённый неточному поиску
Евгений Галашин:
Кирилл Моисеенков:
Левенштейн даёт O(m*n), similar_text O(max(m,n)^3). Хемминг.. В Пыхе не нашел... Ещё нужны аргументы? =)
Кирилл Моисеенков:
Евгений Галашин:
А самому что-ли слабо?
Дмитрий Эсс:
А самому что-ли слабо?
Что слабо?
Ненавижу эти "слабо", с какой стати Евгений должен Вам что-то доказывать?
Евгений Галашин:
Кирилл Моисеенков:
Почему же?.. отнюдь... могу даже в качестве extension'a, только зачем, когда есть levehshtein?
Приведите ссылку на алгоритм Хемминга, тогда посмотрим... Всё же, сомниваюсь, что он даст что-то, лучшее чем O(m*n)...
*едит*
Нашел. Частный случай расстоялия Левенштейна, т. е. всё тот же O(m*n). А если не видно разницы, зачем разводить лишние тормоза?...
Silent:
Если уж разговор зашел о сложности алгоритмов, то для поиска нет никакой необходимости считать полное расстояние Левенштейна. Обычно достаточно узнать, является ли расстояние между двумя строками меньше заданного порога. И для этого случая есть оптимизированный алгоритм, который использует ту же двумерную матрицу, что и стандартный алгоритм, только рассчитывается не вся матрица, а полоса определеной ширины. А поскольку средняя длина слов равна примерно 10 символам, это может в несколько раз ускорить работу.
Дмитрий Котеров:
А что, реально ли на практике, имея словарь в 200000 слов, найти ближайшие по Левенштейну к указанному за, скажем, 0.1 с?
Кирилл Моисеенков:
Дмитрий Эсс:
Если нет в пыхе, то почему сразу нет?

Чтобы сделать систему универсальной, нужно предлагать на выбор функции неточного сравнения - все или какую-нибудь одну. Вот, зачем тут Хемминг. Тем более пятилетний ребёнок смодет написать цикл со сравнением.

Silent:
Именно для этого и есть 3, 4, 5 аргументы в пыхыпыховской функции?

Вопрос к Вам, Silent (зарегестрируйтесь, плз, а то уже надоело оффтопить):
"Как можно объединить хеши (говорил о них в параллельной теме) и Левенштайна, а то ведь всё равно будет "кидать" в "другую" группу"?
Дмитрий Эсс:
Если нет в пыхе, то почему сразу нет?
Не понял.
Silent:
Именно для этого и есть 3, 4, 5 аргументы в пыхыпыховской функции?
Да вроде нет. Они предназначены для задания своих весов для операций удаления или вставки символов. Возможности задать минимальный порог похожести в той функции нет.

Как можно объединить хеши (говорил о них в параллельной теме) и Левенштайна
Скорее всего никак. Нужно придумать еще что-нибудь. Если, например, индекс делать на тернарных деревьях, то нечеткий поиск с заданным порогом похожести там можно реализовать не меняя структуру дерева, просто при его обходе нужно будет еще считать число необходимых вставок и при достижении порога дальше не идти.

В своем поисковике я хочу попробовать более простую схему. Сначала ввести дополнительное ограничение: как минимум одна подстрока длиной 3 символа в веденном слове должна быть правильной. После чего используя дополнительный индекс всех триграмм всех слов лексикона выбрать потенциальных кандидатов и считать расстояние только для этих слов.

Дмитрий Котеров:
А обязятельно искать за 0.1 сек? Все таки нечеткий поиск это непростая задача и его не нужно использовать без особой необходимости. А если уж пользователь его использует, то он наверное подождет лишнюю секунду.
Юрий Насретдинов:
имея словарь в 200000 слов
Ну, 200000 слов - конечно. Слова-то не очень большие, все же Levenstein это не полноэкранный антиалиазинг, работает очень быстро (ну, смотри сам - всего 2 вложенных цикла, и если учесть длину строки (обычно около 8-10 символов), получается 100-150 операций для одной строки). Получается около 20 000 000 итераций, вполне реально. Если еще например считать, что первая буква должна точно совпадать - тем более.
Кирилл Моисеенков:
Дмитрий Эсс:
Забудьте.
Дмитрий Котеров:
На xpoint.ru была очень интересная тема про неточный поиск, кстати. Там еще Дмитрий Эсс давал хорошие ссылки.
Дмитрий Эсс:
Вот эта тема http://xpoint.ru/forums/programming/PHP/thread/24294.xhtml . Ссылки давал Евгений Бондарев, а я только критиковал =).
Silent:
Первые практические результаты: попробовал встроить нечеткий поиск в свой поисковик. Как написано выше, налагается требование, чтобы хотя бы одна подстрока длиной 3 символа в веденном слове была правильной. Это необходимо для первичного отбора кандидатов, для которых уже будет считаться расстояние Левенштейна. Допускается не более двух ошибок в веденном слове. В индексе 2000 документов и 300000 уникальных слов. Поскольку в Перле нет встроенной функции Левенштейна и модуль, написанный на Си, не является стандартным, то для обеспечения переносимости использовалась самописная функция, что раз в 20-30 медленнее, чем если бы она была написана на Си.

В итоге для коротких слов (5-7 символов) после первичного отбора остается в среднем порядка 100-1000 кандидатов, анализ которых не занимает много времени. Если же задать длинное слово (более 10 символов), то число кандидатов вырастает до 5000-15000 и поиск замедляется на 1-2 секунды. Если использовать более быструю функцию для расчета расстояния, то результаты должны быть получше.
Кирилл Моисеенков:
Дмитрий Котеров:
Мной написанная :). Она и до сих пор там. Заглядывайте туда почаще.

Эта тема на forum.dklab.ru