АЛГОРИТМЫ ПОИСКА


     В данном разделе несколько более подробно рассмотрены алгоритмы расширенного и интеллектуального поисков, для простоты не включенные в основные разделы справочной системы.
     

Расширенный поиск  

     
     C помощью расширенного поиска можно найти документы с заданными характеристиками - атрибутами. В ИС Кодекс выделены следующие виды атрибутов:
     Текст - форматированный текст документа, практически неограниченного размера. Каждый документ может состоять из нескольких текстовых объектов (например, текст закона и комментарии к нему). Подсистема поиска рассматривает все тексты одного документа как единое целое.
     Строка с текстом - неформатированный текст длиной до 255 символов (например, наименование, место опубликования).
     Строка с номером - строка символов длиной до 255 символов. В отличие от строки с текстом в данном атрибуте система не выделяет отдельные слова.
     Дата - дата в диапазоне от 01.01.32000 до нашей эры до 01.01.32000 нашей эры.
     Ссылка - указатель на другой объект в базе данных. С помощью ссылок в системе реализованы классификаторы (линейные и иерархические) и деление поискового пространства на разделы.
     По каждому из атрибутов возможности поисковой машины различны.
     
     При контекстном поиске система предоставляет следующие возможности:
     
     - задание в запросе логических формул, в том числе с операторами расстояния. В качестве слов могут выступать цифры, буквенно-цифровые последовательности, слова которые должны быть найдены в заданном виде, а также шаблоны - буквенно-цифровые последовательности с символами "*" (любая подстрока, в том числе пустая) и "?" (любая буква или цифра);
     - встроенный морфологический анализатор, позволяющий автоматически найти все существующие словоформы для большинства слов русского и английского языков.
     
     Для ускорения контекстного поиска система создает индексы по тексту. В целях уменьшения размера, эти индексы не содержат подробной информации о положении слова внутри документа, поэтому в случае использования операторов расстояния подсистема поиска работает в два прохода: на первом отбирает документы, содержащие заданные слова, на втором считывает их тексты в память и проверяет выполнение условия по расстоянию.
     
     При поиске по номеру возможен поиск на точное совпадение строки; поиск строк, начало которых совпадает с заданным; поиск строк содержащих подстроку, совпадающую с заданной. Возможен поиск по шаблону (при использовании символов "*" и "?") - поиск строк, совпадающих с заданной, причем символ "*" может совпадать с любой подстрокой (в том числе пустой), символ "?" может совпадать с любой буквой или цифрой.
     
     При поиске по дате также можно выбрать один из режимов поиска: точно, по, с, с..по.
     
     В режиме "точно" ищутся документы в которых дата точно совпадает с заданной, в режиме "по" - документы с датой до указанной (включая указанную), в режиме "с" - с датой после указанной (включая указанную), в режиме "с..по" - документы, дата которых входит в заданный интервал, причем документы с датами совпадающими с заданными также считаются удовлетворяющими условию.
     

С помощью поиска по классификатору можно найти все документы, имеющие данное значение классификатора. В режиме ИЛИ (по умолчанию) - выбираются все документы, содержащие хотя бы одно значение классификатора из элементов списка поиска; И - выбираются документы, имеющие все элементы списка; КРОМЕ - выбираются документы, не содержащие ни одного значения.

    
Интеллектуальный поиск

     
     Интеллектуальный поиск позволяет найти документ по смыслу содержащейся в нем информации, то есть документы по заданной теме.
     
     В системе реализован алгоритм с использованием компьютерной обработки документа. Согласно гипотезе Ципфа смысл документа зависит от частоты терминов, встречающихся в документе. Предположим, у нас есть набор документов и нас интересуют документы на тему "земельный налог". Очевидно, что документы, в которых больше данных слов, с большей вероятностью содержат интересующую нас информацию. Правда, здесь надо учесть, что документы бывают разного объема. Например, в многостраничном документе, содержащем 5 раз слово "налог", скорее всего меньше говорится о налогах, чем в документе из трех строчек, в котором слово налог встречается 2 раза. Поэтому сравнивается не количество слов, а частота, с которой эти слова встречаются в документе. При этом частота слова определяется как отношение количества этих слов в тексте к общей сумме слов в тексте.
     
     Однако гораздо важнее не сама частота слова, а то, насколько часто в текущем документе это слово встречается относительно других слов. Поэтому вычисляется отношение частоты слова из запроса и частоты самого используемого термина в документе. Таким образом, если в запросе указано слово "налог" и в документе чаще всего встречается слово "налог", то это отношение будет максимальным.
     
     Кроме статистики внутри документа в системе используется статистика термина в базе данных в целом. Например, в при рассмотрении словосочетания "земельный налог" для человека очевидно, что слово "земельный" является определяющим. Эту "важность" слова также можно определить статистически. Для этого исследуется статистика появления данного слова в документах. Если данное слово встречается во многих текстах, то с высокой вероятностью можно предположить, что оно не несет полезной информации по критерию отличия одного документа от другого. В нашем примере слово "налог" будет встречаться гораздо чаще, чем слово "земельный". Значит "земельный" - более "характерное" слово, то есть "сильнее" характеризует отличие документов друг от друга. Для того чтобы это учесть, в системе, для каждого слова введен еще один коэффициент, уменьшающийся с ростом числа документов в которых присутствует данное слово.
     
     Кроме статистических характеристик можно выделить и некоторые "семантические", которые следуют из общих представлений о документах. Каждый документ представляет собой неоднородный текст. При любой структуре документа его название имеет наибольшую информационную ценность. Поэтому системе введен поправочный коэффициент для тех слов, которые встретились в заголовке документа.
     
     Общий вес документа находится как сумма весов всех встретившихся слов в данном документе.
     
     Одними из важных атрибутов документа являются его номер и дата. Поэтому из поискового запроса выделяются последовательности, похожие на номера и даты документов, и проводится поиск этих последовательностей в соответствующих полях документов. Если документы будут найдены, то они получат прибавку к весу.
     
     При достаточно длинных запросах даже такой алгоритм дает неплохие результаты. Однако если запрос состоит из 2-3 слов, и если распределения этих слов сильно отличаются (одно слово встречается часто, а второе - редкое), то редкое слово начинает сильно "перевешивать". В ответе на запрос начинают встречаться документы, содержащие только одно "тяжелое" слово. Поэтому в системе "Кодекс" реализован следующий алгоритм. На первом этапе выбираются документы, содержащие все слова. Если после сортировки этой группы по весу выборка получилась меньше 10 документов, то из запроса "выбрасывается" самое "легкое" (чаще всего встречающеюся в документах) слово и операция повторяется. Поиск прекращается при двух условиях. Во-первых, если при очередном поиске результирующая выборка превысит 10 документов. Во-вторых, если отсутствуют слова, которые можно убрать из запроса. Такой алгоритм поиска использует только тексты документов. Он дает достаточно хорошие результаты, относительно быстро работает и не требует большого объема дополнительной индексной информации.
     
     Имеется также алгоритм уточнения результатов запроса, учитывающий дополнительную информацию о связях между документами. Действительно, если много документов по конкретной теме ссылается на один документ, то он, скорее всего, содержит важную информацию по этому вопросу. Поэтому после "взвешивания" документов по описанному выше алгоритму система "Кодекс" добавляет часть его веса всем документам, на которые документ ссылается.
     
     В пятой версии добавлена обработка атрибутов документов. Система выделяет два типа атрибутов - номер и дата документа. Выделение атрибутов происходит на этапе анализа строки запросов. Если выделяется атрибут даты, то производится поиск документов, у которых один из атрибутов даты (дата принятия, дата редакции и т. д.) совпадает с заданной датой, такие документы получают дополнительный вес. В случае если поисковая фраза содержит числа, то помимо обработки слов фразы будет вестись поиск документов с заданным номером, которые получат дополнительный вес.
     
     

ОГЛАВЛЕНИЕ