Простая поисковая система

Стандарт cgi (common gateway interface) изначально был разработан для того, чтобы дать возможность пользователям запускать программы, доступные на сервере через Веб. Первые cgi-программы служили простым интерфейсом для стандартных команд grep и finger, преобразовывали информацию, выдаваемую этими командами, в формат html и передавали полученные результаты браузеру пользователя.

cgi-программы и прочие программы, выполняемые сервером, с тех пор значительно усложнились. Но одно из их возможных применений не теряет своей актуальности со временем. Это возможность поиска среди документов, хранящихся на веб-сайте, по ключевому слову или строке. Если поисковые системы (сейчас их называют порталами) делают возможным поиск по всей сети Интернет среди огромного количества серверов, то cgi-программы реализуют упрощенную задачу поиска. Они выполняют поиск в файлах только одного, локального сервера и генерируют список url к различным документам по запросу пользователя.
Рассмотрим способы создания нескольких типов поисковых программ. Они хотя и не смогут соревноваться с ht://dig и webglimpse, но дают возможность разобраться в том, как работают подобные программы и как они создаются.

Простой поиск и командная строка

Мой любимый язык для создания таких программ - perl. В основном благодаря возможностям обработки текстов. perl позволяет с легкостью найти один фрагмент текста внутри другого. Например, вот эта программа, которая состоит из одной строки, выводит каждую строку файла test.txt, которая содержит слово "foo":

perl -ne 'print if m/foo/' test.txt
Ключ -n приказывает не выводить все строки по умолчанию, а -e дает нам возможность вставить вызов команды между одиночными кавычками ('). Мы просим perl выводить каждую строку, в которой оператор m// (совпадение) найдет указанное слово. Выполнение этой задачи мы можем вставить в программу, как показано на Листинге 1.

listing 1. simple-search-1.pl
#!/usr/bin/perl -w
use strict;
use diagnostics;
# open the file
my $filename = "test.txt";
open file, $filename
or die qq{cannot read "$filename": $! };
# iterate through each line of the file,
# printing all lines that match
while (<file>)
{
print if m/foo/;
}
close file;

Конечно, эта программа выполняет поиск по простой конкретной маске (строка foo) внутри одного конкретного файла (test.txt). Мы можем расширить действие программы, используя пустой указатель <> вместо поиска в . Пустой указатель <> просматривает каждый элемент в @argv (массив аргументов командной строки), присваивая значение каждого элемента массива переменной $argv. Если командная строка не содержит аргументов, <> ожидает ввода данных от пользователя. Листинг 2 содержит модифицированную версию программы, которая выполняет поиск строки foo в нескольких файлах. Обратите внимание на то, что вместе с найденной строкой эта программа выводит уже и название файла. Так как $_ уже содержит символ перевода на новую строку, нам не нужно добавлять его в конце каждой команды print. Второй листинг тоже можно свести к одной командной строке вызова perl:

perl -ne 'print "$argv: $_" if m/foo/;' *

listing 2. simple--search--2.pl
#!/usr/bin/perl -w
use strict;
use diagnostics;
# iterate through each line of each file
while (<>)
{
# print the matching filename and line
print "$argv: $_" if m/foo/;
}

Теперь мы можем усложнить нашу программу и разрешить пользователю указать маску для поиска и названия файлов - объектов поиска. Программа в листинге 3 берет первый аргумент командной строки, удаляет его из @argv и переносит в $pattern. Чтобы perl понял, что $pattern не изменится, и поиск выполняется только один раз, мы используем m// с параметром /o.

listing 3. simple-search-3.pl
#!/usr/bin/perl -w
use strict;
use diagnostics;
# get the pattern
my $pattern = shift @argv;
# iterate through each line of each file
while (<>)
{
# print the matching filename and line
print "$argv: $_" if m/$pattern/o;<\n>
}
Теперь для поиска строки "f.[aeiou]" во всех файлах с расширением .txt мы используем:

./simple-search-3.pl "f. [aeiou]" *.txt

Будьте уверены: теперь каждая строка, которая содержит символ f, после которого следует гласная буква, указанная в квадратных скобках, отобразится на экране вместе с именем файла.

file::find

Вышеприведенная программа может служить хорошей основой для веб-поиска, если все документы на веб-сайте хранятся в одном каталоге. Но в реальной жизни большинство веб-сайтов представляет собой весьма разветвленную иерархическую систему подкаталогов, заполненных файлами. Хорошая поисковая программа должна пройтись по всей иерархии веб-сайта, просмотреть каждый файл в каждом подкаталоге.
Пока мы старались выполнить эту задачу самостоятельно, кто-то уже поработал за нас. Модуль file::find, который входит в состав perl, позволяет создавать программы, аналогичные find, на этом языке. file::find экспортирует подпрограмму find, которой можно передавать список аргументов. Первый аргумент - это ссылка на подпрограмму, которая вызывается для каждого найденного файла. Остальные аргументы - это названия каталогов и файлов, которые file::find будет просматривать последовательно, пока не доберется до последнего. Например, в Листинге 4 приведена программа, использующая file::find для вывода списка файлов, хранимых в конкретном каталоге. Как видно, file::find экспортирует переменную $file::find::name, которая содержит текущее имя файла. Название текущего каталога помещается в $file::find::dir.

listing 4. simple-find.pl
#!/usr/bin/perl -w
use strict;
use diagnostics;
use file::find;
# invoke "find" with a reference to our
# subroutine, and the initial directory name
find(\&print_name, "/home/reuven");
sub print_name { print "$file::find::name\n"; }
listing 5: simple-find-2.pl
#!/usr/bin/perl -w
use strict;
use diagnostics;
use file::find;
# get the pattern from the input list
my $pattern = shift @argv;
# slurp up the entire contents of a file
$/ = undef;
print qq{searching for "$pattern".\n};
# invoke "find" with a reference to our subroutine,
# with the directories passed as arguments
find(\&find_matches, @argv);
sub find_matches
{
my $filename = $_;
# open the file, and search through its
# contents
if (open file, $filename)
{
# get the file
my $contents = (<file>);
# if there aren't any contents, then return
# right away
return unless $contents;
# print the filename, with the directory
print qq{$file::find::dir/$filename\n}
if ($contents =~ m/\b$pattern\b/is);
close file;
}
else
{
warn qq{unable to open
"$file::find::dir/$filename": $! };
return;
}
}

В Листинге 5 приведена программа simple-find-2.pl, которая использует file::find для поиска в файлах, находящихся в каталогах, вложенных в указанный заданный каталог. Как и в других программах, использующих file::find, основная работа simple-find-2.pl выполняется find_ matches - подпрограммой, вызываемой для обработки каждого файла, найденного в каталогах, перечень которых содержит массив @argv. Чтобы найти все файлы, содержащие слово "f.[aeiou]" в каталогах /home and /development, печатаем:

./simple-find-2.pl "f. [aeiou]" /home /development

Строка 8 программы simple-find-2.pl имеет особое значение: она переназначает $/ - переменную, которая определяет символ конца строки. Обычно оператор <> просматривает файл строка за строкой, возвращая undef при достижении конца строки. Но мы хотим производить поиск во всем файле даже если искомое слово или фраза будет начинаться на одной строке, а заканчиваться на другой. После переопределения $/ строка

my $contents = ();

переносит в переменную $contents все содержимое файла file, а не только одну строку.

Поиск через Веб

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

<html>
<head><title>search form</title></head>
<body>
<form method="post" action="/cgi-bin/simple-cgi-find.pl">

pattern: <input type="text" name="pattern">
<input type="submit" value="start search">
</form>
</body>
</html>

В листинге 6 приведена html-форма, которую можно использовать для подобного ввода. Она передает свое содержимое программе simple-cgi-find.pl - cgi-программе из Листинга 7. Ее параметр pattern содержит маску для поиска, которая будет сличаться с каждым файлом в структуре веб-сайта, а программа simple-cgi-find.pl в итоге возвращает список найденных документов.

listing 7. simple-cgi-find.pl
#!/usr/bin/perl -w
use strict;
use diagnostics;
use file::find;
use cgi;
use cgi::carp qw/fatalstobrowser/
# which directory should start the search?
my $search_root = "/usr/local/apache/htdocs";
# slurp up files in one fell swoop
undef $/;
# create an instance of cgi
my $query = new cgi;
# send a mime header
print $query->header("text/html");
# get the text pattern for which to search
my $pattern = $query->param("pattern");
# make sure that $pattern is defined
unless ($pattern)
{
print $query->start_html(-title =>
"no pattern named");
print "
you must enter a pattern!";
print $query->end_html;
exit;
}
# start the html output
print $query->start_html(-title => "search results");
print qq{
the following documents matched the
pattern "$pattern":\n};
# start an unordered list
print "<ul>\n";
# search for
find(\&find_matches, $search_root);
# end an unordered list
print "</ul>\n";
print $query->end_html;
#-----------------------------------------
# subroutine that searches through files for
# matches
sub find_matches
{
# make sure that this is an html file
return unless m/\.html?$/i;
# get the filename
my $filename = $_;
# open the file, and search through its
# contents
if (open file, $filename)
{
# get the file
my $contents = (<file>);
# print the filename, with the directory
print qq{<li>$file::find::dir/$filename\n}
if ($contents =~ m/\b$pattern\b/is);
close file;
}
else
{
warn qq{unable to open "$filename": $! };
return;
}
}
К сожалению, версия file: :find, поставляемая с perl, не поддерживает флаг -t, который включает режим безопасности tainting. cgi-программы всегда должны запускаться с этим флагом, для того чтобы данные, полученные от внешних источников, не могли представлять потенциальной угрозы безопасности системы. В нашем случае мы не можем использовать этот режим. file::find обращается к подпрограмме fastcwd модуля cwd, который не может нормально работать с флагом -t. В настоящее время я советую использовать эти программы без -t, но с выходом следующей версии perl настоятельно рекомендую обновить текущую версию, чтобы cgi-программы могли работать в режиме tainting.
Нашу подпрограмму поиска find_matches стоит немного изменить для удобства пользователей Веб. Поиск будем производить прежде всего в html или текстовых файлах. Нет смысла перебирать все графические файлы:

return unless (m/\.html?$/i or m/\.te?xt$/i);

На некоторых веб-сайтах гипертекстовые документы имеют расширения .htm (или .htm), а текстовые - соответственно .txt или .txt вместо .text. Приведенная выше маска удовлетворяет всем вариантам, игнорирует регистр символов по ключу /i и рассматривает только расширения (хвосты имен файлов) по метасимволу $.
После получения содержимого текущего файла find_ matches проверяет наличие $pattern внутри переменной $contents, которая и хранит содержимое документа. Мы окружили $pattern символами \b для поиска $pattern в границах одного слова. Теперь поиск foo не совпадет со словом food, несмотря на то, что это слово содержит нашу маску.
Если совпадение найдено, find_matches генерирует url, заменяя $search_root на $url_root и скрывая истинную иерархию хранения html-документов от внешних пользователей. Затем печатается имя файла вместе с гиперссылкой на этот url:

if ($contents =~ m/\b$pattern\b/ios)
{
my $url = "$file::find::dir/$filename";
$url =~ s/$search_root/$url_origin/;
print qq{<li><a href="$url">$filename</a>\n}
}
Развиваем наш веб-поиск

Хотя наша программа simple-cgi-find.pl уже работает, она имеет несколько недостатков. Для начала она не отличает тегов html от содержимого страницы. Поиск img не должен выдавать нам все документы, которые содержат тег - выдаются только те из них, которые содержат это слово вне команд html. Для этого заставим нашу программу "вырезать" теги html из исходного файла.
Начинающие программисты часто думают, что лучший способ избавиться от тегов html - это удалить все, что заключено в скобки < и >, например:

$contents =~ s/<.+>//g;

Так как символ точки "." в perl - это совпадение с любым символом, а плюс "+" - с одним или более предыдущих, приведенная команда по идее должна удалить все теги. К сожалению, в действительности это не так, и эта команда удалит все, что находится между самым первым символом "<" и последним ">" в файле. Это происходит благодаря тому, что стандартные маски у perl слишком "жадные" и стараются максимизировать число найденных символов.
Мы можем уменьшить жадность маски "+" и минимизировать количество совпадений, добавив символ "?", например:

$contents =~ s/<.+?>//g;

Но остается еще одно "тонкое место" - случай, если $pattern содержит пробелы. Можно ли при поиске обрабатывать ключевые фразы, которые включают пробелы? Или мы должны разделять искомые слова логическими операторами "or" или "and"?

listing 8. form with radio buttons
<html>
<head><title>search form</title></head>
<body>
<form method="post" action="/cgi-bin/better-cgi-search.pl">

search string: <input type="text" name="pattern">

<input type="radio" name="type" value="or">
at least one word
<input type="radio" name="type" value="and">
all words
<input type="radio" name="type"
checked value="phrase">exact phrase

<input type="submit" value="search!">
</form>
</body>
</html>

В этом частном случае мы тоже сможем испечь наш пирожок и съесть его. Добавив набор "радио"кнопок в html-форму, можно предоставить пользователю выбор поиска по точному совпадению всей ключевой фразы или по совпадению хотя бы одного слова, входящего в нее.
Теперь мы можем усовершенствовать нашу программу, добавив возможность поиска по всей фразе (как мы и делали до сих пор), поиска по логическому "И" (должны быть найдены все слова ключевой фразы) и логическому "ИЛИ" (поиск хотя бы одного слова из фразы).
Чтобы реализовать поиск по логическому "И", мы разделяем элементы фразы, используя оператор perl "split". Затем подсчитываем количество слов, которое нам нужно найти, перебираем их все на наличие в переменной $contents. Если счетчик $counter достиг нулевого значения, значит, мы перебрали все варианты:

elsif ($search_type eq "and")
{
my @words = split /\s+/, $pattern;
my $count = scalar @words;
foreach my $word (@words)
{
$count- if ($contents =~ m/\b$word\b/is);
}
unless ($count)
{
print qq{<li><a href="$url">$filename</a>\n};
$total_matches++;
}
}
Поиск "ИЛИ" реализовать еще проще: мы опять разбиваем $phrase на части по количеству пробелов. Если найдено хотя бы одно из полученных слов, мы можем незамедлительно выводить имя файла и гиперссылку и возвращаться из find_matches:

elsif ($search_type eq "or")
{
my @words = split /\s+/, $pattern;
foreach my $word (@words)
{
if ($contents =~ m/\b$word\b/is)
{
print qq{<li><a href="$url">$filename</a>\n};
$total_matches++;
return;
}
}
}
В конце концов мы должны сообщить пользователю количество найденных документов. Мы сделаем это, создав новую переменную $total_matches, которая будет увеличиваться на единицу при каждом удачном поиске (как видно из фрагментов программы, приведенных выше для поиска по "И" и "ИЛИ"). Программа, в которую внесены все эти изменения, называется better-cgi-search.pl (листинг 9 в этой статье не приведен, но доступен в архиве, содержащем все тексты программ, по адресу: ftp.ssc.com/pub/ lj/listings/issue69/3753.tgz).

Исключаем каталоги и файлы

Теперь у нас есть готовая поисковая программа, она может выполнять все виды поиска, которые только можно пожелать. Проблема в том, что наша программа может оказаться слишком хорошей и полезной. Многие размещают информацию в Веб и не хотят, чтобы она была немедленно доступна всем. Не создают ссылок на определенные каталоги и документы и не хотят предоставлять к ним общий доступ. Но наша программа никак не зависит от гиперссылок при выполнении поиска.
Самый простой выход - сделать так, чтобы программа не просматривала каталоги, в которых имеется файл .nosearch. Этот файл не должен содержать никакой информации, так как только его наличие означает, что каталог исключен из поиска.
Проверить наличие файла .nosearch в каждом текущем исследуемом каталоге несложно. Но такая проверка при каждом вызове find_matches заметно повлияет на скорость работы программы. Будет лучше, если программа после того, как обнаружит файл .nosearch, сохранит информацию об этом каталоге и будет использовать ее в дальнейшем.

Другая проблема

Мы можем решить эти проблемы, добавив в программу две строки. Первая, в начале find_matches, немедленно возвращает нас обратно в случае, если в текущем каталоге найден файл .nosearch:

return if ($ignore_directory {$file::find::dir});

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

# mark the directory as ignorable ...
$ignore_directory{$file::find::dir} = 1
if (($_ eq ".nosearch") //
(-e ".nosearch") //
(-e "../.nosearch"));
Версия программы better-cgi-search.pl с этими дополнениями хранится в листинге 10 (который можно найти в архиве по ссылке, приведенной выше).

Есть ли способы ускорить поиск?

Если вы уже запустили эти программы, то скорее всего уже столкнулись с упомянутой ранее проблемой: они работают очень медленно. Если ваш веб-сайт состоит из сотни файлов, все работает прекрасно. Но если ваш сайт вырос до 1000 или 10000 файлов, пользователь прервет поиск, не в силах дождаться результатов его работы, так как он занимает очень много времени.

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

В следующей статье я расскажу, как создавать такие индексы и как их просматривать. Возможно, наша простая поисковая программа не сможет состязаться с glimpse и ht://dig, но, по крайней мере, мы узнали, как подобные программы работают и как они создаются.