Полнотекстовый поиск: первое приближение

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

Немного о терминологии.
stopwords - слова, которые встречаются очень часто и их необходимо игнорировать при поиске, чтобы не "засорять" результаты. Например, "это", "и", "что" и проч.
stemmer (стеммер) - алгоритм определения значащей части слова. Приведу цитату из вики:

Сте́мминг — это процесс нахождения основы слова для заданного исходного слова. Основа слова необязательно совпадает с морфологическим корнем слова. Данный процесс применяется в поиcковых системах для обобщения поискового запроса пользователя.
Конкретные реализации стемминга называются алгоритм стемминга или просто стеммер.

Как поисковый "движок" по многим причинам для меня интересен модуль FTS3 для SQLite. Ранжирование не поддерживается, но, как было указано в предисловии, это не столь важно. На его основе сделан, в частности, десктопный поисковик tracker. Последний умеет и ранжирование, что достигнуто ценой переделки всего модуля FTS3, но, пробежавшись по исходникам, не увидел использования этой возможности (везде используется значение ранга 0, а так как ранг всегда больше или равен нулю, то учитываются результаты с любым рангом). Далее, как я понимаю, tracker выполняет zlib-сжатие хранимого текста, что, несомненно, полезная функция. Заданные наборы категорий, на мой взгляд, реализованы странновато - логичнее было бы сделать группы (mime)типов с правилами их обработки, нежели чем жестко привязывать типы файлов к категориям. Скажем, потоковое видео с камер наблюдения явно не стоит включать в категорию "фильмы", да и метатэги нет смысла искать.
А теперь самое страшное - во-первых, tracker целиком "завязан" на d-bus, а во-вторых, индексатор совмещен с поисковым движком. Таким образом, получается нечто несуразное - демон, который работает в локальном сеансе пользователя. Очень жаль, что в погоне за модной свистелкой авторы tracker не додумались, что такая архитектура не позволит, к примеру, запустить индексатор на файлсервере и потом всем пользователям работать с одной индексной базой. Дублирование поискового индекса для каждого пользователя и, соответственно, "отжирание" у каждого из них немалых ресурсов на индексацию, очевидно, делают это решение неприменимым. Из интересного - судя по копирайтам Nokia в некоторых файлах исходников, проект допиливался для maemo.
Как результат, становится очевидным, что использовать будем именно FTS3. Преобразование форматов, стемминг, удаление стоп-слов должны быть внешними модулями, которые можно заменить или скомбинировать из нескольких, как вариант - ispell+snowball, russian ispell + english ispell и так далее.

Для поиска с учетом морфологии понадобится стеммер, причем написанный на чистом C и без лишних зависимостей и, разумеется, с поддержкой русского языка. Таким условиям удовлетворяет snowball, причем у него есть и отдельное описание русского стеммера. Интересен еще ispell, но в качестве дополнения, поскольку он умеет работать только со "знакомыми" словами. Когда-то я строил словарь для всех возможных комбинаций, распознаваемых ispell, получалось что-то порядка миллиона слов, так что при использовании c SQLite все их можно в табличку БД сложить и выполнять поиск нормальной формы по исходному слову.

В исходниках snowball есть утилита stemwords, которая может быть использована через пайпы:

$ echo -e "нафига\nпопу\nнаган\nесли\nпоп\nне\nхулиган"|./stemwords -p -l ru
нафига -> нафиг
попу -> поп
наган -> нага
если -> есл
поп -> поп
не -> не
хулиган -> хулига

Можно и два стеммера по очереди применить:

$ echo -e "нафига\nпопу\nнаган\nесли\nпоп\nне\nхулиган"|./stemwords -l en|./stemwords -p -l ru
нафига -> нафиг
попу -> поп
наган -> нага
если -> есл
поп -> поп
не -> не
хулиган -> хулига

Поисковый движок Xapian также использует snowball, да к тому же на сайте нашлось неплохое описание стемминга как такового Xapian: Stemming Algorithms

Также необходим словарь стоп-слов, например, Russian Stopwords (471 слово) и Free Stop Word Lists in 23 Languages. Первая ссылка, на мой взгляд, предоставляет наиболее адекватный список стоп-слов для русского языка. Проект snowball также предлагает набор стоп-слов для многих языков, так что можно выбирать на свой вкус. Для английского языка несколько списков, в т.ч. используемый MySQL FullText, представлен в статье List of English Stop Words. Не представляет сложностей сделать консольную утилиту для фильтрации стоп-слов. Вероятно, есть и уже готовая, но проще написать на свой вкус.

Кроме вышеперечисленного, не обойтись без набора фильтров для преобразования всех исходных документов в текст. Для локального поиска очень желательно уметь извлекать метатэги - для аудио и видео материалов это название композиции, автор, продолжительность, параметры сжатия и проч. Еще для локальных файлов могут быть назначены тэги средствами файловой системы. Меня локальный поиск не интересует, потому и говорить про тэги и метатэги я не буду. Фильтры можно посмотреть в tracker, где для конвертации форматов документов достаточно легковесные утилиты используются. Тем не менее, не обошлось и без "самодеятельности" - в директории ooo_converter в исходниках tracker можно найти и скомпилировать утилиту o3totxt:

gcc -o o3totxt o3totxt.c o3read.c
strip o3totxt
unzip -p test.odt content.xml | ./o3totxt > test.txt

Работает, но выдает кучу пустых строк и строк только с пробелами. Думаю, намного удобнее воспользоваться odt2txt. Кстати, мантейнер деб-пакета именно так и сделал - если заглянем в деб-патчи, увидим следующее:

-nice -n19 unzip -p "$1" content.xml | o3totxt > "$2"
+nice -n19 odt2txt "$1" > "$2"

Как видим, в общем и целом инструментарий в наличии. На офсайте snowball доступны биндинги на питоне, яве, перле, а также есть форк на C++. Где-то в глубинах интернет сгинул тиклевый биндинг. Не обошлось и без php. PostgreSQL также умеет работать со snowball, причем вот эта статья подскажет, как подготовить свой словарь и в чем разница между snowball и ispell.

Дело за малым - собрать все вместе. Над архитектурой долго раздумывать не будем, выбрав изрядно позабытый unix-way. Для отслеживания изменений возьмем inotifywait, фильтрами преобразуем в текст, удалим stopwords, вызовем консольный стеммер stemwords и полученный результат сохраним в виртуальную таблицу FTS3 в базе данных. Понятно, что при таком подходе результаты поиска будут показываться также без стоп-слов и в том виде, в каком их выдает стеммер. Получить исходный текст с выделенными результатами поиска задача более сложная, поскольку требует при индексации сохранения позиций в оригинальном тексте и тут уже не обойтись без модифицированного токенайзера. Последний выполняет потоковую обработку текста и придется заняться своей реализацией функции icuNext. Впрочем, можно сделать следующим образом - хранить еще и исходный текст после фильтра, но до преобразований, и форматировать кусок из него при отображении результатов поиска. Признаться, я сам так делать не буду, но тоже вариант. А у меня, кажется, есть идея, как это лучше сделать, причем при сохранении архитектуры.

Upd.

Совсем забыл про soundex упомянуть (в моей сборке SQLite функция доступна). С помощью этой функции можно найти слова, даже если они написаны с ошибками. Только предварительно кириллицу нужно транслитерировать. Например, поищем слово "Москва":

sqlite> select soundex('Moskva');
M210
sqlite> select soundex('Moscva');
M210
sqlite> select soundex('mascva');
M210
sqlite> select soundex('Moscvaa');
M210

Нашлись и "Москваа" и "масква".

Выберем фильтр для транслитерации. Увы, команда iconv -t ASCII//TRANSLIT заменяет кириллицу на знаки вопроса. В debian-russian мне подсказали такой способ

echo Москва | konwert UTF8-ascii
Moskva

Или можно заняться самодеятельностью, например, так:

translit.tcl

#!/usr/bin/tclsh8.5

set translit {
А A Б B В V Г G Д D Е E Ё Yo Ж Zh З Z И I Й y К K Л L М M Н N О O П P Р R С S Т T У U Ф F Х H Ц C Ч Ch Ш Sh Щ Sh Ъ "" Ы Y Ь "" Э E Ю Yu Я Ya
а a б b в v г g д d е e ё yo ж zh з z и i й y к k л l м m н n о o п p р r с s т t у u ф f х h ц c ч ch ш sh щ sh ъ "" ы y ь "" э e ю yu я ya
}

while {[eof stdin] == 0} {
    puts [string map $translit [gets stdin]]
}

Upd.

Совсем забыл упомянуть про топик в рассылке, где на мои вопросы по сабжу были получены исчерпывающие ответы:
FTS statistics and stemming