Еще о поиске

Еще о поиске

Продолжение. Начало в КГ № 2

Как сделать поиск более эффективным при помощи индексных файлов
(Рейвен Лернер, Linux Journal #70, февраль 2000)

В прошлой статье мы рассмотрели простую поисковую машину для веб-сайтов. Работа этой простенькой CGI-программы была основана на Perl-модуле File::Find. После каждого ввода ключевого слова в HTML-форме она последовательно открывала и исследовала содержимое всех файлов, хранимых на веб-сервере. Но такой метод поиска чрезвычайно неэффективен. Если на сайте размещено несколько десятков файлов, CGI-программа справится с этой задачей, но если на сайте сотни и тысячи файлов, и к нему происходят тысячи обращений за день, то мы без труда заметим стремительное возрастание загрузки. Постараемся сделать работу нашей поисковой машины более эффективной. В результате мы получим поисковый инструмент, который будет уступать в производительности другим программам, но зато простой и легкий в установке и настройке. И, самое важное, у нас будет шанс познакомиться со скрытыми механизмами работы поисковых программ.

Секрет: предварительная индексация
Искать совпадения с ключевой фразой, введенной пользователем, последовательно просматривая файлы, — занятие чрезвычайно неэффективное. Каждый файл нужно открыть, прочитать, просканировать его содержимое и закрыть. Все эти операции требуют времени. Perl-программы претендуют на определенный объем оперативной памяти, и замедление скорости выполнения программ означает, что одновременно в память компьютера таких программ загружено несколько. А это увеличивает риск вероятного использования вашим веб-сервером более медленой виртуальной памяти вместо быстрой оперативной (RAM). Медленные веб-серверы не нравятся пользователям, поэтому не стоит ожидать от них повторного посещения такого сервера.

Чтобы решить эту проблему, мы должны минимизировать или исключить работу поисковой программы с большим количеством файлов. Если поисковый скрипт не будет открывать каждый файл, то поиск значительно ускорится.
Испытанное и верное решение — разделить процесс поиска между двумя программами. Один или два раза в день индексирующая программа просматривает все веб-документы, читает каждый и анализирует набор используемых слов. Эта программа ведет закулисную жизнь, пользователь о ней ничего не знает и не может повлиять на ее работу. Вместо того, чтобы отправлять результаты пользователю, индексатор собирает всю информацию об используемых словах и частоте их появления и сохраняет ее в отдельном файле на диске.
Теперь поисковая программа, которую вызывает пользователь через CGI, не перебирает все файлы. Вместо этого она спокойно открывает один индексный файл, находит в нем названия файлов, в которых встречаются термины, искомые пользователем, и передает их список браузеру.
Индексирование страниц без труда Perl делает благодаря богатой библиотеке регулярных выражений. Оператор m// обычно ищет совпадения с регулярным выражением, заключенным между ограничителями. При вызове с ключом /g и при работе со списком он возвращает все найденные совпадения. Поэтому в выражении

my $found = join ' ', ("encyclopedia" =~ m/[aeiou]/g); print "$found\n";

первая команда находит все гласные буквы в слове "encyclopedia" и возвращает их в виде списка инициатору вызова. В нашем случае инициатор вызова — это оператор join, который сводит все элементы в одну группу, разделяя их пробелами. Вызов команд, приведенных выше, отобразит на экране пользователя следующее:

e o a e i a

Используя встроенный символьный класс для отделения пробелов \S, мы можем применить этот же алгоритм для извлечения слов из строки текста. Например:

my $sentence = "The rain in Spain falls mainly\n\n on the plain.";
my $found = join '|', ($sentence =~ m/\b\S+\b/g);
print "$found\n";

Эти команды выдают следующие результаты:

The|rain|in|Spain|falls| mainly|on|the|plain

Обратите внимание, как использование \b (совпадения в границах слова) позволит нашей программе не волноваться по поводу символов перехода на новую строку, лишних пробелов или знаков препинания.
Считается, что индексаторы должны быть чувствительны к регистру символов. Я лично предпочитаю игнорировать регистр, так как пользователи не всегда о нем помнят, и это устраняет лишние препятствия при поиске желаемого текста. Мы можем преобразовать всю строку в символы нижнего регистра:

my $sentence = "The rain in Spain falls mainly\n\n on the plain."; my $found = join 
'|', map {lc $_} ($sentence =~ m/\b\S+\b/g); print "$found\n";

Сохранение индексного файла
При сохранении индексного файла мы будем использовать хэш-массив %IGNORE. Он содержит слова, которые мы хотим игнорировать при индексации. Любое не нулевое значение будет указывать, что данное слово следует игнорировать.

%IGNORE = ("the" => 1, "in" => 1, "on" => 1); my $sente
nce = "The rain in Spain falls mainly\n\n on the plain."; my $found = join '|', grep {!$IG
NORE{$_}} map {lc $_} ($sentence =~ m/\b\S+\b/g); print "$found\n";

Посмотрите, как мы сводим различные элементы воедино: m// возвращает список, который передается map, который, в свою очередь, возвращает список, отправляемый grep, и далее к join, а результат присваивается переменной $found.
И, наконец, мы проиндексируем слова, создав хэш-массив (%index), в котором соберем все ключевые слова. Значениями будут хэш-ссылка, ключевое слово, название текущего файла и число появлений слова в этом файле. Другими словами,

$index{spain}->
{foo.html} = 5;

означает, что слово spain в файле foo.html встречается 5 раз. Вот фрагмент программы, который делает такую индексацию:

%IGNORE = ("the" => 1, "in" => 1, "on" => 1); my $sente
nce = "The rain in Spain falls mainly\n\n on the plain."; my @found = grep {!$IGNORE{$_}} 
map {lc $_} ($sentence =~ m/\b\S+\b/g); foreach my $word (@found) { $index{$word}->{$filename}++;
 }

Просмотр файловой иерархии веб-сервера
Теперь, зная, как индексировать слова одной строки, мы будем использовать File::Find, чтобы применить эту задачу ко всей иерархии файлов веб-сервера. File::Find поставляется со стандартным дистрибутивом Perl и экспортирует подпрограмму find. Эта подпрограмма в виде аргументов получает названия каталогов. Она вызывает другую подпрограмму (с названием callback) для каждого файла, найденного в указанных каталогах. Задача этой подпрограммы — открыть файл, извлечь его содержимое и, при необходимости, проиндексировать.
Листинг 3 (листинги 3, 4, 5, не вошедшие в статью из соображений экономии места, можно найти по адресу: ftp://ftp.ssc.com/pub/lj/listings/issue70/3800.tgz) содержит простую программу (index-files.pl) которая просматривает всю иерархию файлов веб-сервера, проверяет содержимое файлов и сохраняет информацию о частоте встречаемости слов в хэш-массиве %index. Подпрограмма callback игнорирует все файлы в каталогах, в которых встречается файл с названием .noindex, как и во всех внутренних подкаталогах. А помогает это сделать другой хэш с названием %ignore_di-rectory. Подпрограмма игнорирует все не-HTML-файлы и удаляет команды разметки гипертекста из содержимого каждого файла перед индексацией. Все теги HTML index-files.pl просто заменяет на пробелы. Поэтому два слова, не разделенные пробелами, но между которыми стоит тег, будут оцениваться как два отдельных слова.

Чтобы обойти проблемы, связанные с такими элементами HTML, как >, &, и прочими специальными символами, мы используем модуль HTML::Entities. Этот модуль экспортирует подпрограмму decode_entities, которая превращает эти спецсимволы в обычные. После удаления специальных символов и тегов HTML индексируемый документ содержит только текст.
Хотя работать с хэш-массивами удобно и быстро, они занимают много оперативной памяти. Хэш, использующий вспомогательный хэш, требует еще больше памяти, и сохранение каждого слова в виде ключа в первичном хэше будет пожирать память с космическим аппетитом. Запускать программу index-file.pl можно на компьютере с большим объемом ОЗУ. Данная версия index-file.pl съела всю память моей Linux-системы (с 72 Мб ОЗУ и 64 Мб свопинг-раздела) после того, как я перенаправил вывод программы команде less.

Запись %index на диск
Хотя index-files.pl выполняет важную работу по индексации всей иерархии веб-файлов, он не сохраняет информацию на диске. После завершения работы index-files.pl вся информация теряется навсегда.
Решение ясно — записать индекс на диск. Но как? Наиболее очевидный ответ — использование DBM-файла. DBM-файл — это дисковая версия хэш-массива. Каждый элемент DBM-файла имеет ключ и значение, которые представлены в виде текстовой строки. Как и хэш-массивы, DBM-файлы оптимальны с точки зрения скорости доступа и обрабатываются быстрее, чем обычные текстовые файлы. Существует несколько разновидностей DBM-файлов — от простого классического DBM до GNU-проекта GDBM и Berkeley DB, наиболее популярных в последнее время за счет их интегрирования в Sendmail.

Perl поддерживает различные типы DBM-файлов через свой интерфейс привязки tie, и для каждого типа существует свой объектный модуль. Такая привязка позволяет творить чудеса с переменными, трактовать их различным способом после каждого сохранения данных или обращения к ним. Привязка хэш-массива к DBM-классу означает, что каждый раз, когда новое значение сохраняется в хэше, оно автоматически записывается на диск в соответствующем DBM-файле. Таким же образом эти значения считываются с диска.
Но остается одна проблема: в DBM-файлах можно хранить текстовые строки, но ничего более сложного. Так как каждое значение %index — это ссылка на другой хэш, обычные DBM-классы не смогут работать корректно. Попытка сохранить ссылку в обычном DBM-файле запишет в него строку текста, с которой мы не сможем ничего сделать.
Следует использовать MLDBM-класс, который создан специально для этого. MLDBM взаимодействует с другим DBM-классом для сохранения ссылок в формате, который можно использовать в дальнейшем.

В начале программы импортируем MLDBM командой use и указываем тип DBM-файла:
use MLDBM qw(DB_File);
В нашем случае мы воспользуемся DB_File с модулем Berkeley DB, который поставляется с Perl (большинство Linux-систем также включают Berkeley DB). Можно указать и метод сохранения ссылок — мы остановимся на том, который используется по умолчанию — Data::Dumper. Другие параметры включая Freeze-Thaw и Storable выполняют аналогичные задачи, правда, различными способами. После этого свяжем наш хэш с DBM-файлом командой tie:

# In what file should the index be stored? my $index_file = "/tmp/lj. db"; # Create the word i
ndex hash my %data; tie %data, "MLDBM", $index_ file, O_RDWR|O_CREAT or die "Error tying %data: $! "
;

Теперь каждое значение, сохраняемое в %index, будет записано в файл /tmp/lj.db. Каждое значение, получаемое из %index, на самом деле будет извлечено из этого файла. Сохранять данные индексирования в каталоге /tmp на реальном веб-сервере не следует, так как любые файлы в этом каталоге могут быть удалены системой.
Хотя MLDBM старается работать по возможности прозрачно, временами он вызывает странные ошибки. Например, вот эта команда Perl обычно не приводит к проблемам:

$data{$word}->
{$url}++;

Как мы видели ранее, она наращивает счетчик для конкретного слова, найденного в конкретном файле. Если %data привязан к MLDBM, то эта команда перестает работать. Вместо этого присваивание следует делать в два этапа, извлечь хэш-ссылку, присвоить ей значение и вновь сохранить в %data:

my $hashref = $data {$word}; $hashref->
{$url}++; $data{$word} = $hashref;

Индекс необходимо постоянно регенерировать для того, чтобы он содержал по возможности свежую информацию. Советую использовать cron, который входит во все дистрибутивы Linux и UNIX, и запускать index-files.pl каждый день в 4 часа утра либо в другое удобное время, когда пользователи не так активны.
Текущая версия программы index-files.pl пока еще не может определить время последней индексации. Нужно внести соответствующие изменения, чтобы index-files.pl индексировал только файлы, которые были созданы или изменены после определенной даты.

Чтение индекса
Теперь, когда мы создали индексный файл, нам понадобится программа, которая будет использовать его данные. Это только начало — мы можем, если захотим, написать множество программ, которые будут выполнять различные варианты поиска в DBM-файле.
Наш первый и самый простой поисковый механизм будет получать информацию из HTML-формы. Эта форма позволяет пользователю ввести одиночное ключевое слово для поиска. К сожалению, способ, который мы применяли для индексирования файлов, позволяет легко обрабатывать отдельные слова, но не работает с ключевыми фразами. Другая структура данных позволит выполнять такой поиск, но, несомненно, увеличит размер индексного файла.

Listing 1

<HTML>
<Head>
<Title>
Search form </Title>
</Head>
<
;Body>
<H1>
Search form</H1>
<Form method="POST" action="/cgi-bin/dbsearch.p
l">
<P>
Search term: <input type= "text" name="term">
</P>
<P>
<input type="submit" value="Search!">
</P>
</Form>
</Body>
</HTML
>

В листинге 1 приведена простая HTML-форма, вполне пригодная для поиска. Эта форма передает свои данные CGI-программе dbsearch.pl (листинг 4). dbsearch.pl открывает DBM-файл — вновь с использованием MLDBM и DB_File — и извлекает хэш-ссылки, связанные с ключевым словом. Отсортировав ссылки (которые содержат URL) по их значению (целое число, показывающее, сколько раз ключевое слово встречается в файле), мы легко построим таблицу частот встречаемости. В нашем конкретном случае dbsearch.pl выводит все результаты, но не составит труда отображать только первую двадцатку.

Логические операции при поиске
Реализовать поиск по отдельному слову достаточно просто, но хорошие поисковые системы поддерживают логические операторы "И" и "ИЛИ". Листинг 2 содержит ту же HTML-форму, которая отличается от предыдущей только наличием радиокнопки. Значение радиокнопки по умолчанию соответствует оператору "ИЛИ" — случай, когда любой из искомых терминов может появиться в документе. Поиск с оператором "И" требует, чтобы в документе обязательно присутствовали оба термина.

Listing 2

<HTML>
<Head>
<Title>
Search form </Title>
</Head>
<
;Body>
<H1>
Search form</H1>
<Form method="POST" action= "/cgi-bin/better-db
search.pl">
<P>
Search term: <input type= "text" name="term">
</P>
<
P>
<input type="radio" name ="boolean" value="and">
All words must appear <input typ
e="radio" name= "boolean" value="or" checked>
One or more words may appear </P>
<P><
r>
<input type="submit" value="Search!">
</P>
</Form>
</Body>
<
/HTML>

Версия программы better-dbsearch.pl, которая поддерживает поиск "И" и "ИЛИ", находится в листинге 5.
Если пользователь выбирает "ИЛИ", dbsearch.pl обрабатывает не один хэш, а несколько. Например, у нас есть два хэша: %odds и %evens:
%odds = (one => 1, three => 3, five => 5);
%evens = (two => 2, four => 4, six => 6);
Мы можем объединить их:
%numbers = (%odds, %evens);
Такая технология не будет работать в нашем случае, потому что возможно присутствие обоих ключевых слов в одном файле. И если это произойдет, то возникнет вероятность дублирования ссылок, в отличие от %odds и %evens, содержимое которых не совпадает. Чтобы в нашем поиске заработала логика "ИЛИ", потребуется комбинировать значения основного хэша:

foreach my $word (@terms) { my $frequency = $data {$word}; foreach my $filename (keys %$freque
ncy) { $full_results{$filename} += $frequency->
{$filename}; } }

Этот фрагмент программы не сильно отличается от своего предшественника dbsearch.pl. Основное дополнение — ввод нового хэша, %full_results, в котором ключами являются имена файлов и значения повторяемости для каждого искомого слова. По этому алгоритму файл содержит одну копию обоих искомых терминов аналогично ситуации как если бы один термин повторился дважды.
Чтобы выполнить поиск по логике "И", нам необходимо знать, сколько раз встречается каждый искомый термин в каждом файле. Если количество терминов в файле и в @terms совпадает, то файл можно обрабатывать. Если это количество меньше, то нет.
Чтобы реализовать это на практике, мы будем использовать хэш %match_counter, в котором будем хранить имена файлов и количество искомых терминов в этих файлах. Добавим одну строку к оператору цикла loop:

$match_counter{$filename} ++ if ($boolean eq "and");

По завершении цикла, но до выдачи результатов пользователю извлечем имена файлов из %full_results. Так как ключи для %full_results и %match_ counter совпадают, команды относительно просты:

foreach my $filename (keys %full_results) { delete $full_results{$filename} unless ($match_cou
nter {$file name} == @terms); }

Для удаления элемента хэша воспользуемся delete. Использование undef в $full_results {$filename} обнуляет значение, но не влияет на ключ хэша. delete полностью удаляет и ключ, и соответствующее значение из хэша. Обратите внимание, как мы определяем размер @terms. Оператор "= =" извлекает скалярное содержимое обоих операндов, поэтому нет необходимости в использовании скалярного ключа перед @terms.
Назад, к предварительной индексации
Наш вариант поисковой системы с предварительной индексацией работает гораздо быстрее и эффективнее, чем программа, которую мы рассматривали в прошлой статье. Я не тестировал производительности обеих программ, но разница легко заметна невооруженным глазом.
Облегчилось и составление своеобразного рейтинга файлов по количеству найденных совпадений.
Но предварительная индексация — не панацея. Прежде всего она требует значительного дискового пространства: чтобы проиндексировать около 400 файлов, мне потребовалось 2,6 Mb для индексного файла. И несмотря на то, что дисковые накопители постоянно дешевеют, 10-мегабайтный файл слегка замедлит работу большинства систем.
Еще большая проблема — это недостаток гибкости, которая достигается при использовании предварительной индексации поисковыми системами. Например, наша индексирующая программа использует оператор Perl lc, чтобы преобразовать все символы в символы нижнего регистра. Теперь поиск по ключевым словам с учетом регистра стал невозможен!
Единственное решение в этом случае — использование иной структуры нашего DBM-файла, возможно, с сохранением дополнительных символьных элементов в хэше для каждого файла.

Тогда мы будем знать, что искомое слово в отдельном файле встретилось 5 раз, но два раза как "ABC" и три — как "abc".
Предварительная индексация также означает, что мы больше не сможем осуществлять поиск по ключевой фразе — только поиск по логике "И" и "ИЛИ".
Чтобы решить эту проблему, остается только сохранять информацию по "следующему слову" в отдельном хэше базы данных. Тогда мы сможем выполнить поиск по первому слову фразы, а потом использовать "следующее слово" для очередного поиска, и так одно за другим, по очереди.
И, наконец, предварительная индексация будет постоянно "отставать" от реального содержимого веб-сайта. Если индексация производится каждые 24 часа, то новые документы добавляются к нему только через сутки.
Но можно проводить индексацию чаще — каждые три или шесть часов.

Заключение
Поиск — это важная часть каждого хорошего веб-сайта. Он позволяет пользователям быстро найти интересующую их информацию, а администраторам предоставляет массу важной аналитической информации.
Но, как мы видели в прошлой статье, простой поиск требует больших затрат времени. Предварительная индексация — это стандартное решение подобных проблем, но она требует дополнительного дискового пространства и немного отстает в актуальности информации, размещенной на сервере.
Зато, разобравшись, как создаются подобные программы, вам будет легче сделать выбор среди широко доступного бесплатного или коммерческого программного обеспечения, чтобы сделать поиск на вашем сайте более эффективным, что, несомненно, привлечет к нему больше посетителей.

Перевод Екатерины Грень