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

С.И.Моисеенко (sergemois@cmail.ru), А.Майстренко (for_alexm@cmail.ru)
Донской государственный технический университет

В основе предлагаемого подхода лежат две базовые идеи:

1. Использование возможностей SQL-запросов к реляционным базам данных при осуществлении поиска.

2. Любой текст можно описать посредством предметного указателя (мы избегаем здесь использовать английский аналог предметного указателя - index, чтобы это не вызывало аналогии со структурами хранения информации во внешней памяти).

Первый пункт предполагает, что необходимая для поиска информация о документе должна содержаться в базе данных. Это даст возможность использовать средства СУБД, связанные с индексированием таблиц и оптимизацией запросов, что в идеале должно обеспечить оптимальную скоростьСкорость (часто обозначается , от англ.velocity или фр.vitesse)— векторная физическая величина, характеризующая быстроту перемещения и направление движения материальной точки в пространстве относительно выбранной системы отсчёта (например угловая скорость). Этим же словом может называться скалярная величина, точнее модуль производной радиус-вектора. выполнения последних.

Второй пункт связан с вопросом о том, что следует хранить в базе данных, а точнее, в полях таблицы базы данных. Современные серверы БД практически не ограничивают объемы информации, которую можно записать в поле таблицы базы данных. Так, например, IBM DB2 Universal DataBase позволяет хранить неструктурированные текстовые документы объемом до 2 Гбайт [1]. Однако такими возможностями обладают далеко не все СУБД. Кроме того, для эффективного поиска в таких полях, так или иначе, необходимы некоторые вспомогательные структуры хранения данных, построение которых берет на себя СУБД. Эти структуры могут находиться как в базе данных, так и в файловой системе.

Мы исходим из того, что хранить документы в базе данных - излишняя роскошь. Достаточно хранить только ссылки (URL) на документы. Здесь, конечно, могут возникнуть непринципиальные в рассматриваемом контексте проблемы, связанные с изменением местоположения документДокумент (от лат.documentum— «образец, свидетельство, доказательство») — материальный объект, содержащий информацию в зафиксированном виде и специально предназначенный для её передачи во времени и пространстве .ов. Мы также считаем неэффективным сохранение в базе данных всего словарного множестваМножество— один из ключевых объектов математики, в частности, теории множеств и логики. документа, предлагаемого в работе [2], отдавая должное простоте реализации и быстродействию алгоритма индексирования.

Здесь дело не только в том, что в базу данных попадут одинаковые слова, имеющие разные падежные окончания и т.п. Причем проблему "избыточности" нельзя решить с помощью уникального индекса. Помимо этого такая база данных будет содержать много излишней информации. Это глаголыГлагол— часть речи, объединяющая слова, которые, по традиционному определению, обозначают действие или состояние и отвечают на вопросы что делать? что сделать? что делал(а, и,о)?., служебные слова, местоимения и т.д. В качестве подтверждения сказанного рассмотрим предметный указатель, эффективно используемый для поиска в научно-технической литературе. Предметный указатель это, по сути дела, терминологическая база данного текста. Она включает базовые термины (существительныеИмя существительное (существительное)— знаменательная (самостоятельная) часть речи, принадлежащая к категории имени и классу полнозначных лексем, может выступать в предложении в функциях подлежащего, дополнения и именной части сказуемого. В русском языке— самостоятельная часть речи, обозначающая предмет и отвечающая на вопрос «кто?»/«что?». Одна из основных лексических категорий; в предложениях существительное, как правило, выступает в роли подлежащего или дополнения, а также обстоятельства и сказуемого.) и уточненные термины (существительные с определяющими их прилагательными и, возможно, предлогами).

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

Сама структура такой поисковой словарной базы должна обеспечить не только быстрый, но и релевантный поиск. Релевантность обусловлена еще и тем, что при формировании терминологической словарной базы конкретного документа сохраняется не только сам термин, но и частота его вхождения в документ. Поэтому при выполнении поиска, можно упорядочить его результаты по частоте вхождения искомого термина в документ. Кроме того, можно ввести некоторое пороговое значение f (например, f > 1), которое должно использоваться в качестве критерия отбора записей в поисковом запросе. Причем на это не потребуется дополнительных затрат времени. Основные временные затраты придутся не на поиск, а на предобработку документа (формирование предметного указателя), которая осуществляется не в реальном времени выполнения запроса, а один раз при регистрации документа в системе.

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

• Определить часть речи слова в документе (морфологический анализ);
• Выяснить, что является составным термином (синтаксический анализ). Предполагается, что простым термином является существительное. С составным же термином дело обстоит сложнее, поскольку нужен достоверный критерий того, какая последовательность слов является терминологически связанной.
• Как хранить термин, чтобы слова с разными падежными и т.д. окончаниями записывались в базу данных один раз. Заметим, что эта же проблема должна решаться и при поиске. Например, запрос на поиск слова "программаПрограмма - (от греч. — пред, греч. — запись) термин, в переводе означающий «предписание», т.е." должен учесть также и слова: "программе", "программы", "программах" и т.д.

Морфологический анализ можно реализовать, оценивая окончания слов в документе [3]. Для неоднозначно трактуемых слов можно использовать специальную таблицу в БД с атрибутами слово и часть речи, и при анализе просматривать сначала ее, а затем (если слова там нет) выполнять оценку по окончанию слова. В этой же таблице будут находиться и незначительное число слов, принадлежащих неизменяемым частям речи, таким как междометие, наречие и т.п.

При выявлении составных терминов мы исходим из следующих предположений:

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

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

На первом шаге выполняется создание поискового образа документа (ПОД) [3] из копии исходного. ПОД - это информационное наполнение документа, т.е. в нем уже не содержится междометий, вводных и служебных слов и т.д. (смотри выше). При этом исключаемые слова в ПОД заменяются (если они не находятся в начале или конце предложения) некоторым разделительным символом для дальнейшего выявления многословных терминов. Можно для всех исключаемых слов использовать один и тот же символ (например, запятую), чтобы упростить синтаксический анализ.

На втором шаге анализируются фрагменты текста между разделительными символами. Извлекаются любые последовательности слов, среди которых есть существительное. Именно эти последовательности заносятся в таблицу Term (термин). Одновременно с этим можно формировать таблицу TermInDoc (термин в документе), в которой, помимо идентификатора термина (внешний ключ), в поле freq будет подсчитываться частота вхождения термина в документ (смотри рисунок). Заметим, что на основе морфологического анализа в таблицу Term заносятся лишь основы слов (PhraseBase), составляющих термин, т.е. всем терминам, отличающимся только падежными окончаниями, соответствует одна запись в этой таблице.

Рис.1. Логическая схема базы данных поисковой системы

Дадим некоторые пояснения к ER-диаграмме (в нотации IDEF1X), представленной на рис.1. Идентификатор связи Р между таблицами Document и TermInDoc означает "один или более", т.е. любой документ должен содержать термины. По сути дела это означает, что при регистрации документа в БД всегда должно выполняться построение его терминологической базы. Если, что маловероятно, при анализе документа термины обнаружены не будут, то данный документ просто не следует включать в БД.

Каждый конкретный термин из таблицы Term может содержаться в любом количестве документов. Допустимо также его отсутствие в таблице TermInDoc. Такая ситуация возможна в следующих случаях:

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

Атрибут Doc_Ref в таблице Document содержит ссылку на местоположение оригинала документа в файловой системе или сети.

Наконец, из таблицы TermInDoc удаляются все записи с частотой вхождения ниже некоторого порогового значения. То есть предполагается, что термины, которые встретились в документе, скажем, один раз, неадекватно характеризуют его содержание. Пороговое значение можно подобрать эмпирически. В этом случае пороговое значение представляет собой постоянную величину (например, единица). Недостатком постоянного порогового значения является то, что в небольших документах может вообще не оказаться терминов с частотой, выше порогового значения. Однако нельзя сказать, что такие документы вообще не несут никакой информации. Найти выход можно с помощью переменного порогового значения, принимающего некоторое значение в интервале между максимальной и минимальной частотой терминов в данном документе. Такое пороговое значение будет являться характеристикой документа. Кроме того, можно определить пороговое значение для совокупности документов [3].

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

Как говорилось выше, список документов, отвечающих запросу, можно упорядочить в соответствии с частотой вхождения термина в документ или же в соответствии с весом данного термина (который можно определить, например, как отношение частотыЧастоты выражены в герцах, а также в кратных единицах: кГц = 1000 Гц, МГц = 1000 кГц = 1000000 Гц, ГГц = 1000 МГц = 10 Гц, ТГц = 1000 ГГц = 10 Гц. Для частот ниже 1 Гц будут приводиться численные значения обратной величины— периода, выраженного в секундах, минутах, часах, сутках и годах, что упростит соотнесение с бытовыми величинами времени. В верхней же части шкалы, помимо частот, приводятся приблизительные эквивалентные значения энергии (в электронвольтах), ибо энергия осциллятора в квантовой механике пропорциональна частоте: E = h, где h— постоянная Планка, Е— энергия, — частота. вхождения термина в документ к числу терминов в документе).

Естественно, при данном подходе не на любые запросы будет получен ответ. Например, если образец поиска будет содержать только исключаемые из ПОД слова. Но, с другойДругой — центральная категория современной философии. Актуализация данного понятия связана с такими событиями, как антропологический и лингвистический поворот. Другой — это не Я, тот, кто противостоит мне, находится по ту сторону меня, моих ценностей, моего мировоззрения. И вместе с тем, Другой такой же как Я: он мыслит, чувствует, ходит и т. д. стороны, какой смысл можно усмотреть в поиске документов по словам: "например" или "следовательно"? Кроме того, учет таких слов может привести к ошибочному выполнению запроса. В качестве примера рассмотрим поиск по словам "можно" и "термин". Ясно, что если поиск ведется по вхождению в документ, хотя бы одного из двух терминов, то возможно, что он весь будет состоять из документов, содержащих слово "можно" (причем с достаточно высокой частотой вхождения) и не содержащих слово "термин". Если же критерий поиска построен на вхождении в документ обоих слов, то релевантностьРелевантность (лат.relevo— поднимать, облегчать)в информационном поиске— семантическое соответствие поискового запроса и поискового образа документа. В более общем смысле, одно из наиболее близких понятию качества «релевантности»— «адекватность», то есть не только оценка степени соответствия, но и степени практической применимости результата, а также степени социальной применимости варианта решения задачи. такого поиска может вызвать сомненияСомнение— психическое состояние или состояние ума в котором возникает воздержание от окончательно определённого суждения, или/и раздвоения (троення ит.п.) его становления, из-за неспособности сознания сделать дискретный однозначный вывод. Если ум не может обнаружить причин, аргументов, которые бы позволили ему прийти к однозначному решению относительно правильности или ошибочности своего мнения, тогда сомнение является отрицательным (то есть фактически блокирование дальнейшего анализа и выводов, «избегание» дискретизации). Если же разум выявил причины и они равной, подобной, сравнительной важности, делая таким образом унитарное решающее мнение невозможным, тогда сомнение считается позитивным (включающим инвариантность). В обоих случаях результатом является: невозможность формирования окончательного суждения (воздержание от него). Существует множество примеров где человек не может победить дискретизировать, перевести в стадию определенности) свои сомнения.. Не будет удивительным, если частота вхождения слова "можно" значительно превысит частоту вхождения слова "термин", в результате чего наверху списка окажутся документы, имеющие меньшую релевантность относительно слова "термин".

Следует отметить критичность данного алгоритма по отношению к точности определения части речи и правильности исключения "незначимых" слов.

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

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

В заключение скажем, что предложенный способМетод (от греч. — «способ»)— систематизированная совокупность шагов, действий, которые необходимо предпринять, чтобы решить определенную задачу или достичь определенной цели. В отличие от области знаний или исследований, является авторским, то есть созданным конкретной персоной или группой персон, научной или практической школой. В силу своей ограниченности рамками действия и результата, методы имеют тенденцию морально устаревать, преобразовываясь в другие методы, развиваясь в соответствии с временем, достижениями технической и научной мысли, потребностями общества. Совокупность однородных методов принято называть подходом. Развитие методов является естественным следствием развития научной мысли. формирования поисковой базы данных документов позволит находить документы, когда поисковым образом является отдельное слово, несколько слов, словосочетание, а также слова, которые должны находиться поблизости друг от друга. В последнем случае анализируются словосочетания в терминологической базе данных.

Цитируемые источники

1. Игнатович НиколайНиколай (греч. — «побеждающий народ»)— мужское имя греческого происхождения. Всегда было популярно в России среди всех сословий.. DB2 Universal Database - ключевые характеристики.
   http://www.S-Networks.ru/seminars/cbd2000/cbd_day1_07.shtml

2. ИгумновИгумнов— русская фамилия, происходит от православного церковного чина «игумен». Евгений. Основные концепции и подходы при создании контекстно-поисковых систем на основе реляционных баз данных.
   http://www.S-Networks.ru/database/articles/search_sys.shtml

3. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации. - М.: "Нолидж", 2000. - 352 с.