Общие слова ~~~~~~~~~~~ Словоформой считается жадная последовательность русских букв, латинских букв и цифр. Например, "Екатерина", "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