Общие слова
~~~~~~~~~~~
Словоформой считается жадная последовательность русских букв, латинских букв
и цифр. Например, "Екатерина", "England", "1974", "H2O".
"H_2O", "Владивосток-2000" -- это пары словорм.
Начальная форма словоформы, не состоящей целиком из
русских букв -- это сама словоформа.
Регистр букв при поиске не учитывается.
Поиск по части слова не поддерживается. Не поддерживаются и
регулярные выражения.
Список новых файлов, которые планируется поставить под CVS.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Словари:
dict.koi Словарь Александра Лебедева для ispell.
Образован слиянием всех словарей,
которые я смог найти.
mydict.koi Самопальное дополнение словаря. Допускаются некоторые
вольности. Например, в Лебедевском словаре
существительные второго склонения, как правило,
помечены ключем "K" или, если они не имеют формы
множественного числа - ключём "J". В mydict.koi
все такие существительные попадают с ключём "K".
ndict.koi Автоматически сгенерированный дополнительный словарь.
Пример: в dict.koi нет слова "Эйдельман",
а в базе встречаются словоформы "Эйдельман"
и "Эйдельмана". Скрипт, обнаружив это,
понял, что это могут быть формы существительного
женского рода "Эйдельмана" ("Эйдельман" -- форма
родительного падежа множественного числа), и дополнил
ею словарь.
raff.koi Таблица аффиксов к словарю Лебедева.
Скрипты:
makecheck.pl По таблице аффиксов генерирует текст функции,
ищущей начальную форму словоформы.
mkRS.pl Пересоздаёт поисковые таблицы и обнуляет поле
ProcessedBySeacrh у всех вопросов.
updateRS.pl Ищет вопросы с нулевым ProcessedBySearch
и добавляет информацию о них в таблицы.
Работает очень медленно (около секунды на вопрос на
AMD-400), начинает обрабатывать следующий ий вопрос
только после того, как в базе появилась информация о
предыдущем. В результате может быть в любой момент прерван
без ущерба для таблиц.
updateRS1.pl Делает тоже самое, что updateRS.pl, но обрабатывает вопросы
порциями, записывая информацию в память, скидывая
информацию в базу только после того, как порция
будет полностью обработана. Оптимальный размер порции
зависит от мощности машины.
dumpRS.pl Скидывает в файл дамп таблицы word2question.
dumpin2out.pl Скидывает в файл таблицу соответствий
идентификатор вопроса в базе -> внешнее имя
(Турнир.Тур.Номер).
dump2dump.pl Преобразует дамп таблицы word2question
под другую заливку базы, используя таблицы
соответствий двух заливок. Суть в том, что
при перезаливке базы изменяются идентификаторы
вопросов. Использование этого скрипта позволяет избежать
запуска "долгих" скриптов updateRS.pl и updateRS1.pl
Кроме того, скрипт может использоваться при переносе таблиц,
например, с бильбо на кулички.
delRS Удаляет из дампа таблицы word2question информацию о
вопросах, соответствующих указанным файлам.
checkPBS.pl Проставляет поле ProcessedBySearch на основании
информации из таблицы word2question
Вспомогательные файлы:
chgk.cnf Конфигурационный файл.
chgkfiles.pm Модуль для работы c файлами
dbchgk Модуль для работы с базой
Стандартные процедуры
~~~~~~~~~~~~~~~~~~~~~
Полная заливка
Запустить mkRS.pl, затем updateRS.pl и подождать сутки или больше.
Вместо updateRS.pl можно использовать updateRS1.pl, тогда будет побыстрее,
но всё равно довольно долго.
Перенос таблиц на другую машину
На первой машине:
dumpRS.pl dump1
dumpin2out.pl first
Затем залить dump1 и first на вторую машину и уже там:
dumpin2out.pl second
dump2dump.pl dump1 dump2 first second
loaddump second
Все созданные файлы можно удалить.
Добавление в базу новых файлов
Добавить файлы скриптом updatedb.pl и запустить updateRS.pl.
Этот скрипт генерирует список нераспознанных слов.
Их начальные формы можно добавить в словарь mydict.koi.
В принципе, эту процедуру хорошо бы делать перед заливкой (проверив
текстовые файлы), но во-первых скрипта для проверки файлов пока нет
(потому как я только сейчас его придумал), а во-вторых утяжелит
процесс апдейта. Лучше или иногда (раз в несколько месяцев) делать полную
переиндексацию, или сохранив список новых файлов, раз в те же самые
несколько месяцев проделывать процедуру удалить-добавить.
Исправление существующих файлов
Перед удалением старой базы:
dumpRS.pl temp
delRS temp список удалённых или исправленных файлов
После заливки таблиц Questions и Tournaments:
loaddump.pl temp
rm temp
updateRS.pl
Генерация дополнительного словаря
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Автоматически сгенерированный автоматический словарь
нужен для обработки слов, которых нет в стандартном словаре,
но которые встречаются в базе, причём в разных формах.
В основном, это имена собственные. Работа это одноразовая,
она проделана, потому скрипты не выкладываю.
1. Сделали полный список русских словоформ, встречающихся в базе.
2. Проверили каждую словоформу, используя основные словари,
получили список неопознанных словоформ
3. Построили граф, вершины которого -- неопознанные словоформы (около 70000),
а рёбро есть в том и только том случае, когда одна словоформа
может являться нальной формой другой.
4. Разбили граф на компоненты связности, в каждой попытвлись
найти словоформу, которая может быть начальной формой всех остальных.
Если такая нашлась -- добавили её в дополнительный словарь.
В результате работы этого алгоритма образовались допсловарь (около 7000
начальных форм) и список так и неопознанных словоформ (их осталось
около 40000). Большая часть этих слов -- орфографические ошибки. Очень
много из них получились из-за того, что в некоторых файлах в русских
словах встречаются латинские буквы, совпадающие по начертанию с русскими.
Для всеобщей гармонии необходимо сделать следующее:
1. Исправить орфографические ошибки
2. Проверить и исправить автоматически сгенерированные начальные формы.
3. Добавить в словарь почём зря не опознанные словоформы.
Вторым и третьим пунктами я иногда медленно и печально занимаюсь.
Структура таблиц для русского поиска
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Таблица nf. В этой таблице живут список начальные формы.
Поля:
id INT UNSIGNED - идентификатор начальной формы
word CHAR(30) - сама начальная форма, записанная
заглавными русскими буквами.
flag CHAR(5) - список флагов таблицы аффиксов
number - количество вхождений форм данной начальной
формы в вопросы
Таблица nests. В этой таблице живут пары соответствий словоформа -
начальная форма. Одной словоформе могут соответствовать несколько
начальных форм.
Поля:
id INT UNSIGNED - идентификатор записи
w1 CHAR(30) - словоформа, записанная заглавными буквами
w2 INT UNSIGNED - идентификатор начальной формы.
Таблица word2question. Таблица соответствий начальная форма -
список вхождений в вопросы. Наверное, эту таблицу можно
было объединить с таблицей nf.
Поля:
word INT UNSIGNED - идентификатор начальной формы
questions MEDIUMBLOB - список вхождений. Каждому вхождению соответствует
4 байта: один на номер поля, два на номер вопроса,
один на позицию в вопросе. С ужасом жду, когда
Олег добавит вопрос номер 65536 и придётся
увеличивать число байт, отведенных на вхождение
или возиться с битами :) Хранится только нижний байт
номера вхождения в поле. Погрешность, связанную
с этим, считаю пренебрежимо малой.
Поиск
~~~~~
Русский поиск производится скриптом db.cgi при указании опции
"metod=rus". Вот алгоритм:
1. Выделяем из поисковый строки максимальные последовательности
русских, латинских букв и цифр.
2. Ищем начальные формы полученных словоформ по таблице nests. Формы,
которых там нет, проверяем по словарю и таблице аффиксов. Формы, которые
всё ещё неопознаны, считаем ненайденными.
3. По таблице word2questions ищем списки вхождений слов в
затребованные поля, выделяем списки вопосов, в которые входят слова,
в зависимости от значения опции all берём их объединение или пересечение -
это список найденных вопросов. Сохраняем для каждого вопроса списки вхождений.
4. Считаем для каждого найденного вопроса релевантность поисковой фразы и
сортируем по ней.
5. При выводе выделяем жирным шрифтом вхождения искомых слов.
Шаблон, по которому выделяются слова, формируется по таблице
nests.
В db.cgi добавлена также опция debug, при установке которой
выводится отладочная информация.
В db.cgi поддерживаются также поиск по Simple Query и Advanced
Query (как их понимает altavista), но оказалось, что
поиск по регулярному выражению на пятидесяти тысячах вопросов работает
чересчур долго, потому эти возможности не используются.
Но, вообще-то, для них есть опции "metod=simple" и "metod=advancde".
Формула релевантности
~~~~~~~~~~~~~~~~~~~~~
Честно говоря, я взял первую пришедшую на ум формулу, вроде худо-бедно
работает.
Пусть поисковая фраза состоит из слов s1,s2,...sn.
Каждое найденное слово добавляет к релевантности следующее значение:
количество_вхождений_в_вопрос+1000+1000/количество_вхождений_в_базу.
Каждая пара (si, sj) добавляет к релевантности следующее значение:
10 * (10- (min ( distance(i,j) , 10)).
distance(i,j)=min(|i-j-pi+pj|)
(pi и pj -- позиции слов i и j в вопросе, минимум
считается по всем pi и pj)
Суть в том, что максимальная релевантность будет у вопросов, в которых
встречается максимальное количество искомых слов (это имеет значение,
если all=no), затем учитывается распространённость каждого слова и
близость их в вопросе друг к другу. Максимальная релевантность,
как правило, будет у вопросов, в которых поисковые слова встречаются подряд,
в том же порядке, что и в запросе.
Какие формы признаются одинаковыми
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Те, которые попадают в одно гнездо, согласно таблице аффиксов словаря Лебедева
для ispell.
Описывать, какие словоизменения учитываются, а какие -- нет,
непросто. Поскольку словарь создан не для определения начальной формы,
а для проверки орфографии, очень много словоизменений он не учитывает.
Например, в словаре можно встретить и слово агнец, и слово агнцев --
добавить формы в словарь, видимо, оказалось проще, чем править
таблицу аффиксов. По-хорошему над таблицей аффиксов и словарём надо очень
серьёзно работать. В идеале, надо использовать не словарь Лебедева, а
словарь Зализняка, но его таблиц в удобном для обработки электронном виде
я не нашёл.
Роман Семизаров
roma7@zaba.ru
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>