Локальные поисковые системы. Общие вопросы.

Актуальность задачи.
Давно прошло время когда жесткий диск размером в 80Мб считался роскошью. Ныне цифры в десятки гигабайт никого не удивляют, даже фантастическое значение в 200Гб заставляет задуматься лишь на секунду - когда же стоимость этого монстра упадет до ниже психологически важного рубежа: 100 у.е.

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

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

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

Однако, как показывает опыт, люди в подавляющем своем большинстве признают важность проблемы поиска лишь по отношению к Интернету, локальный поиск выглядит в восприятии типичного пользователя чем-то маловажным и ненужным. Данный стереотип оборачивается весьма "увлекательным" и "продуктивным" занятием - поиском методом перебора. Особенно это любят секретарши (в открываемых один за другим файлах много интересного) и/или категория людей, чей заработок зависит от факта присутствия одушевленного тела на рабочем месте, но не от качества и объема работы.

Инструментарий поиска.
К сожалению, в области фундаментальных проблем поиска нашему поколению уже не прославиться - основные алгоритмы и приемы открыты, изучены и описаны лет 40 назад. Тонкости и особенности, безусловно, изучаются и сейчас, но столь специфический предмет, освещаемый в специализированных научных изданиях, неинтересен рядовому пользователю.

 Кроме того, вопросы, связанные с поиском информации в критически важных областях относительно успешно решаются - в огромном большинстве случаев работа в Интернете начинается с обращения к той или иной поисковой машине.

Машин для поиска в Интернете много. Пожалуй, даже больше, чем программ для поиска на локальном компьютере. Последние можно успешно разделить на две категории: сканеры и препроцессоры.

Сканеры при получении поискового запроса выполняют обход локального диска (или нескольких), выполняя последовательный поиск заданных байт. Сканеры весьма однообразны, различия сводятся, в основном, к тонкостям интерфейса, приятным неожиданностям типа сканирования архивов и распознавания основных русских кодировок.

Основной и неустранимый недостаток сканеров: при повторном поиске требуется заново просмотреть все файлы. Все и заново.

Это некритично при маленьком диске, но с увеличением его объема поиск превращается в повод выпить чаю, конечно, в случае, если поблизости нет начальства.

Сканирование - тупиковый путь уже при объеме документов в 1-2Гб, и чтобы особенно ярко прочувствовать проблему, представьте последовательный поиск в Интернете.

Препроцессоры за один просмотр (pre-processing) строят индексную базу и запоминают в ней, какие слова в каком файле были найдены. Последующий поиск проводится уже по индексной базе.

Построение индекса позволяет избежать повторной обработке всех файлов и дает возможность фактически мгновенно обрабатывать самые разнообразные запросы пользователя.

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

Это позволяет при проектировании структуры индексной базы гибко варьировать возможности поиска и сопоставлять их с наличными ресурсами.

Здесь я позволю себе отступление в сторону. Безусловно, автор не открыл ничего принципиально нового. Данная проблема хорошо изучена и в той или иной мере решена, в частности, коллективами программистов, создавшими тот же Google или Рамблер. Снимаю перед ними шляпу.

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

Но оставим вопросы коммерции в стороне. Проектирование препроцессора - это весьма увлекательное занятие с точки зрения алгоритмистики. Некоторые аспекты данного процесса я попытаюсь осветить ниже.

Рассмотрим основные проблемы, с которыми сталкивается разработчик программы-препроцессора, использование которых, по мнению автора, способно сэкономить немало рабочего времени.

В первую очередь, разработчику следует:
Выяснить структуру текстов, которые предстоит индексировать. Это:
морфологический разбор,
средняя длина слова,
распределение слов по размерам,
частоты тех или иных слов.
Определиться, что будет содержать в себе индексная база:
Флаг наличия слова в файле (1 бит),
Счетчик повторений данного слова в файле(минимум байт),
Список позиций, на которых встретилось данное слово (массив из 16-и (или 32-х) битных целых чисел.
Смысловые особенности: сохранять все слово, или сначала отсекать падежные окончания, окончания формы, числа и пр.
o Лексические тонкости: запоминать, начиналось ли слово с заглавной буквы, был ли за словом знак препинания, и если был, то какой.
Изучение этих двух вопросов доставляет большое удовольствие. При разработке структур, которые составят индексную базу, можно узнать очень много нового, нередко структуры данных получаются эстетичными и красивыми. Там простор для изобретательности и творчества…

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

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

…АТЬ
…ЕТЬ
…ИТЬ
…ОСТЬ
…ЫЙ
…АЯ
…ЫЕ

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

Для английского словарь окончаний меньше - не более 50-70, что было для автора открытием. Есть подозрение, что для языков, использующих иероглифическое письмо, можно обойтись без анализа окончаний вовсе.

Таким образом, первым делом разработчику придется заняться филологией.

Средняя длина слова
Данная величина легко вычисляется из анализа двух-трех сотен типичных файлов после того, как решено, что считать словом и создан словарь для морфологического анализа.

Для типичного компьютера, содержащего документы и художественные тексты на русском языке, а также некоторое количество текстов и документации на английском, средняя длина слова 8-9 байт.

Таким образом, мы можем сделать первый шаг в построении структуры индекса:

TWord = record
Our_Word: string;
end;

Распределение слов по размерам
Тот же ранее выполненный обход файлов позволит получить примерно следующее: Длина
слова,
символов 2-4 5 6 7 8 9 10 11 12 13 14 15 16 и более
Доля, % 18 12 15 13 11 8 6 4 3 2 1 0,8 Менее 1%

То есть, максимально число слов, длиной 6 байт, чем слово длиннее, тем оно реже встречается, а слов длиной более 16 байт - не более 1%.

Уточним базовую структуру нашего словаря:

TWord = record
Our_Word: string[16]; // имеется в виду тип ShortString
end;

Словами длинной более 15 символов мы, в первом приближении, пренебрегаем.
Частоты тех или иных слов.
Толковые словари содержат 50000-100000 слов. Набор слов талантливого писателя составляет 10000-15000 слов, человек обычный обходится в своей обыденной жизнью словарем в 2000-4000 слов, хотя и понимает практически все, включенные в толковый словарь. Случай Эллочки-Людоедки, показанной в бессмертном произведении Ильфа и Петрова, показывает возможность существования словаря в 30 слов.

Это говорит о том, что слова сильно различаются по той частоте, с которой их употребляют, и соответственно, можно ожидать, что будет различаться частота, с которой слова будут встречаться в различных файлах.

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

Таблица
Встречаемость слов для словаря в 47000 словоформ, построенного при обработке 256 файлов.
Встречаемость слов
при базе в 530 файлов Количество слов.
Найдено более чем в 128 файлах: 66 слов.
Более, чем в 64: 303
более 16: 2569
более 4: 6323
только 1-4: 38129

Результат, безусловно, будет варьироваться для различных типов файлов, но главный вывод не измениться: до 80% слов и более встречаются лишь 1-4 раза, в данном случае в 1-4 файлах из 256.

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

Для уточнения структуры, хранящей наши данные, следует определиться, что же мы будем хранить. Рассмотрим вначале, что представляет собой

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

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

Но если мы используем…

Счетчик повторений данного слова в файле,
То получим возможность оценивать рейтинг документа, скажем, чем чаще слово попадалось в документе, тем более он подходит под текущий запрос, и в списке найденного пойдет первым.

При ведении рейтинга документов возможна масса вариантов: можно учитывать частоту (чаще - выше рейтинг), близость к началу документа (чем раньше - тем лучше или наоборот), следить, с какой буквы началось слово (с заглавной - рейтинг выше) и еще масса вариантов, которые следует "затачивать" под конкретные потребности пользователя.

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

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

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

Собственно, такой вариант и реализуется большинством поисковых машин, имеющих опцию "восстановить документ".

Цена решения.
Рассмотрим теперь величину объема индексной базы в зависимости от типа хранящейся информации.

Оговорюсь сразу, что приводимые данные достаточно относительны, поскольку на объем базы повлияет также мастерство программиста, его способность как можно более плотно упаковать информацию. Например, если мы знаем, что слово в среднем имеет длину 8 байт, а отводим на его хранение 16, то просто глупо дать пропасть 8 байтам, которые "в среднем" будут пусты. Кроме того, можно "смухлевать" и подвергнуть базу компрессии при записи на диск.

Объем индексной базы как доля (в %) от объема просмотренных документов
Тип индексной базы Объем индекса, %
"Флаг" 3-5
"Рейтинг" 6-15
"Список позиций" Минимум 30-50.

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

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

На обычной персоналке, как правило, сложно выделить лишний гигабайт под индексную базу. В этой связи локальному препроцессору предпочтительнее вариант "Флага" или, в крайнем случае, "Рейтинга".

Учитывая этот факт, попробуем ввести в нашу структуру следующий вариант:

TWord = record
Our_Word:string[16]; // имеется в виду тип ShortString
Data_Type:Boolean;
Case I:integer of
0: //------- в первом варианте мы храним список файлов "при слове"
array [0..3] of word;
1: // ------ во втором есть некие связанные данные Data размером DataSize
Data:pointer;
DataSize:integer;
end;
end;

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

Запись TWord должна также включать поля для построения бинарного дерева с тем, чтобы обеспечить поиск слова в словаре, но это уже вопрос относящийся к фундаментальным трудам, выполненным на уроне монографии Д.Кнута. "Искусство программирования для ЭВМ".

Рутина.
Форматы файлов.
Приступая к разработке препроцессора, автор определяется с тем, какие именно файлы будут индексироваться с целью последующего поиска. Как правило, это текстовые файлы и документы текстовых процессоров.

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

В случае документов текстовых процессоров, например WinWord'a, необходимо уметь анализировать формат бинарного файла и извлекать из него текстовую часть. Нередко это бывает непростой задачей вследствие закрытости формата файла и отсутствия сколько-нибудь полных описаний, дополнительно возникают осложнения вследствие наличия различных версий текстового процессора и соответственно - разных форматов бинарного файла.

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

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

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

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

Данный проект - локальная поисковая система-препроцессор (SimSearch) - расположен в Интернете по адресу www.simsearch.nm.ru, а автор в настоящее время доступен по адресам электронной почты: gusev.maxim@inp.kz, gusevmaxim@mail.ru.

Проект развивающийся и автор будет рад как помощи так и конструктивной критике.

В рамках проекта решены задачи высокоскоростного построения индексной базы, морфологического анализа, анализа бинарных файлов WinWord'a.

Осталась "неблагодарные" проблемы всестороннего тестирования и разработки интерфейса. Кроме того: очень много просьб о расширении списка поддерживаемых файлов, в частности, типов XLS, DBF, различных гипертекстовых форматов. При этом для легкости распространения через сеть программа должна оставаться компактной и не терять быстродействия.

Внимание! Запрещается перепечатка данной статьи или ее части без согласования с автором. Если вы хотите разместить эту статью на своем сайте или издать в печатном виде, свяжитесь с автором.
Автор статьи: Гусев Максим Николаевич gusevmaxim@mail.ru

Получить ссылку на материал