На главную -> MyLDP -> Тематический каталог -> Решение административных задач в Linux

---

Поиск текста (часть 2)

В первой части данной серии статей мы рассмотрели разнообразные методы, помогающие нам индексировать текст и организовывать поиск текста. Основной упор делался на работу с базами данных средствами языка SQL. Если пообещаете не нервничать по случаю оставления темы SQL запросов в покое, я могу показать вам ещё один путь создания индекса ( Прим. перев. Обычно под индексом понимается обозримого размера таблица или группа таблиц, которые составлены с целью упрощения процесса задания к ним запросов на выборку. ) для осуществления к нему запросов на поиск вашей любимой фразы. Приготовьтесь ко встрече с Lucene!

Сбор и конвертирование файлов

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

Когда дело доходит до индексирования, нужен plain text (Прим. перев. Последовательность символов в файле, читающаяся как текст без форматирования.), это значит что приходится конвертировать содержимое файла. Учитывая, что понятие текст без форматирующей информации (plain text) на сегодня условно, приходится принимать во внимание кодировку символов. Будет ли достаточно использовать 7-битную US ASCII? Использовать ли ISO-8859-1 или даже ISO-8859-15 потому, что нам нужен символ валюты Евро? Может быть хорошей идеей будет использование UTF-8. Кодирование символов в Unicode совпадает с 7-битной US ASCII до тех пор пока не потребуются дополнительные биты для кодирования множества "странных" символов. В этом причина того, что Unicode использует так много людей. Помните, что если используете Unicode в одном месте, нужно применять эту кодировку везде. Это сделает жизнь гораздо проще.

При работе с кучей из сотни тысяч файлов на сервере, вам, вероятно, не нужны они все; те, что вам нужны либо содержат текст, либо могут быть конвертированы в текст. Изображение может содержать текстовые поля (например, JPEG EXIF или PNG iTXt/tEXt разметка), но чаще удобнее придерживаться формата текстовых файлов. Как же его определить (формат)? Наиболее простой способ - взглянуть на расширение файла. Способ, конечно, не очень точный, так как расширения ".jpg" и ".jpeg" обычно применяются для обозначения файлов в формате JPEG, однако выяснение формата файла через анализ его содержимого - сложная задача (программа GNU file может помочь в это деле). В данной работе, для упрощения проблемы, будем работать с расширениями.

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

extension = [ ".doc", ".htm", ".html", ".odp", ".ods", ".odt", ".pdf", ".txt", ".xls" ];
nice = 13;
output = "filelist.txt";

Опция extension перечисляет все интересные расширения. nice - уровень приоритета для вашей программы. Сбор информации со всей файловой системы создаёт большую нагрузку на ЦПУ, поэтому предоставим ЦПУ в первую очередь другим процессам. Опция output сообщает программе место для записи списка интересных файлов. Будем вести запись в файл filelist.txt. Синтаксис конфигурационного файла подразумевает применение C/C++ библиотеки libconfig (см. http://www.hyperrealm.com/libconfig/ - Прим. перев.). С помощью данной библиотеки проходит синтаксический анализ файла конфигурации и извлечение из него необходимой программе информации. Синтаксический анализатор не так уж и сложно написать, однако более сложные задачи у нас ещё впереди. Далее в статье будет дана ссылка на исходный код программы filelist, файлы helper.h, helper.cc, filelist.ggo (файл конфигурации опций командной строки) и Makefile, чтобы всё собрать. Для сборки вам нужны будут библиотеки Boost Filesysti и isostream, а также программа gengetopt от проекта GNU. Gengetopt и особенно Boost библиотеки здорово помогают сделать вашу жизнь в C/C++ много проще.

Lucene и её порты

Проект Apache Lucene представляет из себя коллекцию инструментов для создания программ с функциями поиска. Основной компонент - Lucene, написанная на Java библиотека поиска и индексирования. Проект предлагает дополнительный код для построения веб-программ поиска и работы с метаданными. Lucene портировали на Perl (PLucene), Python (PyLucene), C(Lucy) и C++ (CLucene), таким образом, вы можете получить доступ к индексу с помощью цепочки программ, которая вам больше нравится. Код на Java также содержит классы, осуществляющие импорт документов через классы stream. Создание и поддержка индекса - просты, а формат индекса может быть использован на разных платформах и доступен через разные порты Lucene без необходимости доработки.

Для индексирования наших документов, сконцентрируемся на C++ порте Lucene.

Индексирование с CLucene

CLucene вводит концепции, которые нужно рассмотреть перед тем как использовать API. Каждый объект, который включается в индекс, называется документ (document); в идеале данный документ содержит только текст, чтобы упростить работу по индексации. CLucene анализирует содержание и использует разнообразные алгоритмы для извлечения полезных слов или токенов из индексированного документа. Анализаторы представляют собой отдельные классы. Они содержат реализацию алгоритмов разделения пробелами, использования стоп-слов (часто встречающихся слов, не включаемых в индекс), замены специальных символов и другие методы.

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

 
Поле     | Содержание
-----------+-------------------------------
title      | My notes from the conference
author     | R. Pfeiffer
content    | Кучи и кучи текста, ...
timestamp  | 1207958005
type       | Текст на английском языке в формате UTF-8 
...        |

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

Индекс как единое целое хранится в отдельном каталоге и полностью управляется CLucene; Возможность модификации индекса напрямую пользователем не предусмотрена. Перемещение индекса сводится к перемещению каталога. Каталог с индексом может быть перенесён с одной платформы на другую и работать без дополнительной отладки.

Библиотека CLucene работает с кодировкой Unicode. Строки относятся к типу wchar_t *, что означает их принадлежность к двухбайтным символьным литералам (обозначается L, например L'x'). Поэтому я предлагаю вам использовать Unicode при работе с интерфейсом CLucene.

Простая стратегия индексирования

Теперь мы знаем, что необходимо реализовать в очередном куске кода. Я опишу некоторые важные аспекты решения задачи.

Конвертирование документов в текст без форматирующей информации

Я уже говорил, что нам нужен техт; это означает, что нужно конвертировать PDF, PostScript и другие форматы в текст без форматирующей информации. Также необходимо убедиться, что на выходе у нас получится текст в кодировке Unicode (UTF-8, к примеру). Для того, чтобы не делать этого с нуля на C++ внутри нашей программы, используем уже созданные программы конвертирования. Это не очень элегантно (Не соглашусь с автором. - Прим. перев.), но данный подход позволит гибко работать с файлами во множестве форматов без сложных дополнительных изменений внутри нашей программы. Внешние вспомогательные программы ассоциированы по расширениям, указанным в файле конфигурации.

// Список известных расширений файлов и соответствующие им конвертеры 
//для перевода конкретного формата в текст без форматирующей информации 
pdf=(pdftotext -q -eol unix -enc UTF-8 $IN - > $OUT)
ps=(pstotext $IN | iconv -f ISO-8859-1 -t UTF-8 -o $OUT -)
doc=(antiword $IN > $OUT)
html=(html2text -nobs -o $OUT $IN)
htm=(html2text -nobs -o $OUT $IN)
odp=(ooo_as_text $IN > $OUT)
ods=(ooo_as_text $IN > $OUT)
odt=(ooo_as_text $IN > $OUT)
php=(html2text -nobs -o $OUT $IN)
rtf=(unrtf --nopict --text $IN > $OUT)
txt=(cat $IN > $OUT)
xls=(py_xls2txt $IN > $OUT)
xml=(cat $IN > $OUT)

$IN - это имя файла, который конвертируем. $OUT - временный файл, получаемый на выходе конвертора. Расширение находится слева от знака равенства. Команды внутри скобок будут исполнены программой индексации перед тем как отправить содержание файлов в индекс CLucene. Альтернативой было бы использование классов, распознающих форматы файлов, читающие файлы и конвертирующие; проект Strigi. Они называют это JStreams. JStreams предоставляет стандартизированный интерфейс для доступа к содержимому файлов разного формата. Подход с использованием внешних программ является более общим. Имейте в виду, что все форматы документов пакета OpenOffice могут конвертироваться одной единственной программой. (ooo_as_text является частью проекта OOoPy. Вежливо попросите у автора OOoPy копию программы, если она не входит в список файлов для загрузки).

Файл конфигурации проходит синтаксический анализ на базе библиотеки Boost Spirit. Синтаксический анализатор определён с использованием шаблонов. Struct filter_grammar в helper.cc содержит полный набор правил для анализатора. Достаточно один раз понять как работаю шаблоны и библиотека Spirit станет удобным средством построения собственных синтаксических анализаторов.

Управление базой данных, содержащей временные метки

При рассмотрении документов, хранящихся на файловом сервере, выясняется, что в большинство из них изменения вносятся достаточно редко. Частое внесение изменений характерно для ситуации, когда с документами кто-то работает. Если речь идёт о "библиотеке" (которую мы хотим проиндексировать. - Прим. перев.), большинство документов будут храниться не изменяясь. Хорошей идеей было бы вести учёт времени внесения изменений в файлы. Таким образом мы бы смогли вносить изменения в индекс в зависимости от временной метки с датой модификации. При индексировании большого количества документов данный подход позволил бы сэкономить множество операций ввода/вывода.

Программа индексирования будет вести учёт временных меток с помощью базы данных, основанной на SQLite. Таблица базы данных могла бы быть заменена ассоциативным массивом, но я хотел бы больше работать с SQL. В indexer.cc находится предложение, создающее БД.

CREATE TABLE IF NOT EXISTS fileaccess ( filename TEXT PRIMARY KEY, mtime INT(8) )

SQL - слишком для таких целей, поэтому мы используем SQLite. :) Наша тразакция работает в течение всего процесса индексирования. Изменения в БД не вносятся до тех пор, пока все документы не буду проиндексированы без ошибок.

Создание индекса CLucene и запись в него

Перед тем, как вносить изменения в индекс, его нужно открыть. Данное действие похоже на работу с файлами или сокетами. Так или иначе, перед тем как открыть или создать индекс, необходимо создать объект анализатора. Анализатор определяет, как вы будете иметь возможность обрабатывать данные, направляемые в индекс. Учитывая, что мы точно не знаем, что индексируем, будем использовать Whitespace анализатор.

// Это анализатор, который мы используем.
WhitespaceAnalyzer analyser;

// Инициализируем запись в индекс CLucene
IndexWriter::IndexWriter index_repository( args_info.index_arg, &analyser, new_index, true );

args_info.index_arg представляет собой строку, содержащую имя каталога, где будет находиться индекс. &analyser - наш анализатор, а new_index булева переменная отражающая то, открываем ли мы существующий индекс или создаём новый. Крайний аргумент описан с помощью closeDir в документации к CLucene's Doxygen.

Теперь индекс может быть заполнен объектами (документами; см. раздел Индексирование с CLucene). Документ CLucene - это просто контейнер, где храняться поля с описанием чего-либо.

// Поля, которые мы хотим поместить в индекс.
lucene::document::Field *field_filename;
lucene::document::Field *field_file_content;
lucene::document::Field *field_mtime;
lucene::document::Field *field_type;
...

 // Создаём документ Lucene для добавления в каталог, где хранится индекс.
 file_document = new lucene::document::Document;
 // Добавляем поля в объект документа.
 if ( file_has_content ) {
     file_document->add( *field_file_content );
 }
 file_document->add( *field_filename );
 file_document->add( *field_mtime );
 file_document->add( *field_type );
 index_repository.addDocument( file_document, &analyser );
...

Можно добавлять полей столько, сколько вам нужно. Добавление метаданных в данном случае - хорошая идея, так как вам вероятно не хочется всё время проводить поиск по содержимому файлов. Метод addDocument() добавляет документ в репозитарий индекса.

Учитывая то, что CLucene ведёт репозитарий индекса, при внесении изменений в большое количество данных, было бы хорошо вызывать метод оптимизации.

// Оптимизация индекса должна проводиться после вненсения в него изменений.
index_repository.optimize();

// Закрываем индекс.
index_repository.close();

Это было краткое введение в работу с CLucene, основы необходимые вам, чтобы начать. Библиотека (CLucene) способна ещё на очень многое.

Чтение из индекса CLucene

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

using namespace lucene::index;
using namespace lucene::analysis;
using namespace lucene::util;
using namespace lucene::store;
using namespace lucene::document;
using namespace lucene::search;
using namespace lucene::queryParser;

wstring search_string = L"Where is it?";

lucene::index::IndexReader    *index_reader;
lucene::search::IndexSearcher *index_searcher;
Query                         *index_query;
Hits                          *index_hits;
WhitespaceAnalyzer            analyser;

index_reader   = IndexReader::open( args_info.index_arg );
index_searcher = new IndexSearcher(index_reader);
index_query    = QueryParser::parse( search_string.c_str(), L"content", &analyser );
index_hits     = index_searcher->search(index_query);
if ( index_hits->length() > 0 ) {
    for( long i=0; i < index_hits->length(); i++ ) {
        Document &doc = index_hits->doc(i);
        wcout < "FOUND: " < doc.get(L"filename") < endl;
    }
}

delete index_hits;
delete index_query;

index_reader->close();
delete index_searcher;

Важно использовать тот же анализатор, что и процесс индексирования. В нашем случае это снова WhitespaceAnalyzer. IndexReader::open() открывает индекс, QueryParser::parse() осуществляет поиск, в результате CLucene возвращает Query, содержимое которого, объекты Document. Как видно все строки относятся к двухбайтным, поэтому использование Unicode действительно важно.

Если отлаживать созданные CLucene индексы, вам может пригодиться Luke, набор инструментов для работы с индексом Lucene (the Lucene Index Toolbox). Туда входит программа на Java, с помощью которой можно отобразить содержимое индекса. В частности, можно будет просматривать документы, поля и выполнять запросы на поиск.

Код

Учитывая, что статья уже стала гораздо больше, чем ожидалось, просто приведу ссылку на tar архив с кодом, который рассматривался выше. Также туда входит Makefile для компиляции. Для разработки я использовал GCC/G++ 4.1.2 (хотелось бы узнать, что о моём коде скажет компилятор от Intel). Если используете систему Debian, потребуются следующие пакеты:

• gengetopt
• libboost-filesystem-dev
• libboost-iostreams-dev
• libboost-regex-dev

Я компилировал SQLite, libconfig++ и CLucene из исходников, так как не был доволен пакетами, содержащимися в Debian Etch. Новая версия SQLite особенно интересна, так как предоставляет новый API к некоторым функциям (обозначенным ..._v2()). Если хотите скомпилировать библиотеку Boost, потребуется добавить путь к включаемым файлам (т.е. /usr/local/include/boost-1_35 для текущей версии, если ставить из исходников). По причине того, что библиотека Boost представляет из себя в основном набор шаблонов, время компиляции достаточно мало, несмотря на размер дистрибутива Boost.

Тестовый прогон с "оценкой производительности"

А теперь к вопросу: Зачем всё делалось? Как быстро это всё будет работать? Нужно ли беспокоиться о том, какой порт используем? Не могу ответить на эти вопросы. Всё, что могу - это запустить индексатор для обработки файлов (это конечно не внушает доверия с точки зрения статистики). Содержимое каталог выглядит следующим образом:

rpfeiffer@miranda:/nfs/Bibliothek$ du -h --max-depth=1
1.3M    ./Lyrics
703M    ./Security
0       ./Biometrie
16M     ./Sysadmin
172K    ./Misc
403M    ./Teaching
12M     ./Programming
57M     ./Hardware
3.9M    ./Reports
7.3M    ./Networks
92K     ./Chaos
32K     ./Gfx
12K     ./UTF-8
23M     ./VoIP
1.8M    ./Science
1.2M    ./Manuals
1.2G    .
rpfeiffer@miranda:/nfs/Bibliothek$

Документы находятся на нашем офисном файловом сервере и доступны через NFSv3 по средствам Gigabit Ethernet. Машина, ведущая индексацию работает на Core2 Duo 2,13 Ггц с 2 Гб оперативной памяти. filelist содержит список из 539 интересных файлов (отобранных на основе их расширений, описание см. выше). Давайте запустим индексатор и создадим новый индекс. Имейте в виду, что каталог был отчасти кэширован благодаря запуску du и то, что 539 документов могут занимать меньше, чем 1,2 Гб по причине избранных нами расширений.

rpfeiffer@miranda:~/code$ time ./indexer -c ./indexer.cfg -i /var/tmp/i -n 1 -l ./filelist.txt 

real    1m48.767s
user    1m12.337s
sys     0m17.849s
rpfeiffer@miranda:~/code$ 

Индекс выглядит следующим образом:

rpfeiffer@miranda:/var/tmp/i$ ls -lh
total 5.2M
-rwxr-xr-x 1 rpfeiffer rpfeiffer    4 2008-04-18 23:56 deletable
-rwxr-xr-x 1 rpfeiffer rpfeiffer 5.2M 2008-04-18 23:56 _gk.cfs
-rwxr-xr-x 1 rpfeiffer rpfeiffer   28 2008-04-18 23:56 segments
rpfeiffer@miranda:/var/tmp/i$ 

Итак, индексатор провёл какую-то работу и сохранил её результаты на жёсткий диск. Исследование с помощью Luke показывает знакомые документы и содержание.

Несколько слов про альфа-код и ошибки

Пожалуйста имейте в виду, что код представленный в данной статье, находится в состоянии альфа-тестирования. Исходники содержат лишний код и требуют доработки (особенно с точки зрения использования внешних программ конвертирования). Тем не менее, программа работает без ошибок сегментации. Всё построено на стабильных библиотеках, но до полной готовности к широкому использованию программе ещё далеко. Код нужно немного подчистить, так я не сразу понял, как работать с использованными мною библиотеками. Если у вас предложения, просто присылайте патчи - вот для чего нужна GPL. Если кода у вас нет, но есть хорошие идеи, с радостью выслушаем! Предпочтительнее всего в статье в одном из следующих выпусков. :)

Полезные ресурсы

---

---