Поисковый движок: паттерн запроса для поиска

 

Введение

Паттерны

   паттерн - регулярное выражение

   паттерн с разбивкой на слова

   запрос для поиска по справочнику

   квантор всеобщности *

   грамматические кванторы

   символы-модификаторы слов в паттерне

Логические выражения в паттернах

Общие опции

   грамматические опции

   взаимное расположение слов

   прочие опции

Определение части документа для поиска

Введение

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

Итак, паттерн - это образец текста, который нужно найти. Элементы паттерна обычно называют термами.

Кроме этого, к паттерну относятся опции, влияющие на процесс сравнения образца (то есть паттерна в узком смысле) и текста.

Простейший пример выполнения поиска одного ключевого слова в группе файлов:

задание паттерна запроса

 

Паттерны

Для поискового движка φaind возможны несколько видов паттернов, которые отличаются алгоритмом сопоставления заданного образца и текста в документе.

Паттерн - регулярное выражение

Этот вид паттернов с одной стороны дает чрезвычайно мощный инструмент для поиска разнообразных данных, а с другой стороны фактически не отличается от возможностей, предоставляемыми другими поисковыми утилитами (к примеру - стандартной для Linux командой grep). Сравнивать с ОС Windows трудно, так как ее консольная команда FINDSTR очень ограничена.

Строка паттерна задается опцией:

-regex "рег_выражение"

Можно сослаться на текстовый файл со строкой паттерна:

-regex @filename

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

Синтаксис регулярных выражений можно посмотреть здесь.

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

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

Паттерн с разбивкой на слова

Можно сказать, что второй вид паттернов - это расширение стандартных регулярных выражений. Поэтому мы называем его расширенным регулярным выражением (Extended Regex - RegexEx). В своих программах Вы можете использовать расширенные регэкспы - подробнее об этом здесь.

Сам текст паттерна формируется опцией

-sample "большая собака"

Слова в паттерне разделяются пробелами, сам текст можно заключить в двойные апострофы.

Текст паттерна можно записать в файл (простой текстовый) и сослаться на него так:

faind ... -sample @my_query

В этом примере my_query - имя файла с текстом паттерна.

 

Запрос для поиска по справочнику

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

-multiword "имя_файла_справочника"

Аргумент команды - это имя файла со справочником. Этот файл имеет формат XML, структура полей описана в разделе о рубрикаторе.Его можно набрать вручную даже в Блокноте, либо использовать команду -topic_db save_xml имя_файла для выгрузки текущей базы авторубрикатора.

Данная команда допускает применение таких модификаторов запроса, как -wordforms, -dynforms, -soundex и других, разрешенных для -sample.

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

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

Для демонстрации принципа запускаем поиск этих терминов в единственном текстовом файле:

faind -file некий_документ.txt -wordforms -multiword "multiword.q" -listfiles:xml res.xml

Результат в файле res.xml (см. описание команды -listfiles) содержит упоминание рубрики "астрономия", а также соответствующее ключевое слово "галактики" и оценку достоверности рубрикации 100%:

Квантор всеобщности *

Символ *, если он не является частью регулярного выражения, совпадает с любым словом в тексте. Обращаем внимание на то, что такая интерпретация квантора расходится с принятой для регулярных выражений. В частности, паттерн "a * b" успешно фиксируется на фрагменте a c b, но фрагмент a b не подойдет. Другими словами, квантор * в точности равен одной (но произвольной!) лексеме текста.

Вообще говоря, такая интерпретация символа * как квантора "любой элемент" является стандартной для языка описания словаря ПРИИСК - см. здесь.

 

Грамматические кванторы

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

Общий формат:

# КЛАСС:* { КООРДИНАТА:СОСТОЯНИЕ ... КООРДИНАТА:СОСТОЯНИЕ }

В данном случае КЛАСС - имя грамматического класса, как оно объявлено в Словаре (см. здесь). КООРДИНАТА:СОСТОЯНИЕ называется координатной парой и задает требование на состояние грамматической координаты (см. описание).

Символ диез # объявляет грамматический квантор в тексте паттерна.

Пример:

"кошка # ПРЕДИКАТ:* {}"

Описание грамматики (имена классов, координат и их состояний) для реализованных языков можно найти здесь.

 

Символы-модификаторы слов в паттерне

Символ тильды ~ означает, что следующее за ним слово является регулярным выражением. Чтобы не произошло разбивки регулярного выражения на части, слово можно заключить в одиночные кавычки:

-sample "~'кошк(.*)' ~'сп(.*)'"

Для данного примера будут найдены участки текста "кошка спит", "кошки спали" и так далее.

Знак + перед словом означает, что слово обязательно должно быть найдено. Без такого указания некоторые слова даже не будут искаться - например, часто употребляемые (союзы, предлоги).

Пример:

-sample "кошка +и мышка"

Для явного управления пропуском малозначащих слов в паттернах используется опция -skipword (см. здесь).

Конструкция с ключевым словом AS позволяет поименовать результаты поиска в итоговой выборке:

-sample "кошка * AS Verb"

В этом примере слово, которое зафиксировано на кванторе *, будет в итоговой выборке (например, в XML файле результатов) обозначено именем Verb.

 

Наряду с использованием регулярных выражений поисковая машина позволяет использовать так называемые wildcards - символы * и ? означают соответственно любую последовательность символов (в том числе нулевой длины) и произвольный одиночный символ. Для реализации такого режима используется команда -wildcards в паре с основной командой -rx или -regex,  к примеру:

-rx -wildcards -sample "'кош*' 'сп*т'"

-wildcards -regex "кош*"

Пару команд -rx -wildcards можно сократить до -wildcards.

К примеру, результат применения команд -wildcards -sample "мор*" к группе файлов дает:

wildcards в поисковом запросе

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

Поисковый движок может выполнять автоматическое усечение слов до псевдокорней - так называемый стемминг, с помощью плагина стеммера. Более подробно об этой возможности рассказано в описаниях команд -dynforms и -rooting.

Логические выражения в паттернах

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

Логический оператор NOT слово вводит в запрос требование отсутствия слова. К примеру:

-sample "кошка NOT черная"

Логический оператор ИЛИ имеет формат слово1 OR слово2. Это выражение означает, что успех поиска будет зафиксирован, если встретилось либо слово1, либо слово2. Пример:

-sample "кошка OR киска"

Логический оператор И:

-sample "(кошка OR киска)AND(мяукает ORспит)"

Из предыдущего примера видно, что для группировки аргументов логических операторов можно применять круглые скобки, в противном случае из-за большего приоритета логического оператор AND по сравнению с OR выражение

-sample "кошка OR киска ANDмяукает ORспит"

будет проинтерпретировано как

-sample "кошка OR (киска AND мяукает) OR спит"

что вряд ли имеет смысл.

К примеру, поиск паттерна 'море OR корабль' может дать такие результаты:

логические операторы в поисковом запросе

Сложность логического выражения, в частности число вложенных выражений, ничем не ограничивается. Но надо помнить, что скорость сопоставления текста и паттерна весьма быстро падает для сложных логических выражений.

Общие опции

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

Разные опции

-rx - текст для поиска представляет собой набор регулярных выражений, каждое слово - отдельное регулярное выражение. Например:

faind ... -rx -sample "'собак(.*)' 'ла(.*)'"

Опция -rx объявляет все слова в паттерне регулярными выражениями. Если же нужно объявить таковыми только некоторые слова, то для каждого из них можно использовать метасимвол ~ (см. здесь). Опция -rx должна стоять перед -sample.

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

Следует отличать опции -regex и -rx. Если в первом случае следом за опцией идет строка паттерна, и текст анализируется как целая строка, то во втором случае опция -rx лишь влияет на работу опции -sample, а именно - заставляет считать перечисленные в паттерне лексемы регулярными выражениями. Таким образом, текст будет разбит на лексемы, и уже эти лексемы будут сравниваться по отдельности с частями паттерна.

Примеры использования -rx -sample.

 

-allow_partial=true - допускать нахождение не всех слов запроса. По умолчанию значение данное опции false, то есть движок пытается найти в документе соответствие для всех слов поискового запроса. Установив данную опцию в true, можно разрешить пропуск некоторых слов паттерна запроса. В зависимости от того, какие слова не были найдены, будет скорректирована достоверность результата поиска.

При установке в true данная опция требует явного задания параметра допустимой минимальной достоверности найденного контекста -minbound.

-minbound=n.nn - минимально допустимая достоверность фиксации контекста. Если достоверность получается меньше, то считается, что фиксация не удалась. Задание

faind ... -minbound=1.0 -sample "большая собака"

требует, чтобы контекст был зафиксирован точно - без пропуска слов из запроса. А, например, запрос:

faind ... -minbound=0.2 -sample "большая собака"

позволяет пропустить при фиксации одно из слов запроса. Значение minbound по умолчанию записано в ini-файле.

-query_filemasks "маска;маска..." - дополнительные маски для файлов, находимых при поиске по индексу.

 

Грамматические опции

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

-wordforms - включение морфологического анализа: использовать Словарь для проецирования слов в запросе и в обрабатываемом тексте для соотнесения грамматических форм одной словарной статьи, а также для более сложных вариантов сравнения слов. Более сложные алгоритмы для морфологического анализа включаются командой -dynforms.

Эта команда позволяет исключить морфологические нерегулярности естественного языка, другими словами - вместо сравнения буквального значения слов (в технической документации это называется лексическое содержимое словоформы) проверяется, относятся ли словоформы к одной и той же словарной статье. Общее представление о том, какие словоформы формируют словарные статьи, можно получить с помощью Грамматического Словаря Русского Языка.

К примеру, поиск ключевого слова 'море' в группе файлов с включенной морфологией дает:

морфология при поиске

 

-dynforms - включение более сложных алгоритмов морфологического анализа. В целом работает аналогично опции -wordforms, но в некоторых случаях позволяет находить больше вариантов паттерна в текстах. К примеру, поиск слова "человек" с опцией -dynforms дает:

нечеткий поиск

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

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

 

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

 

-soundex - включать алгоритм нечеткого сравнения слов, в частности - обрабатывать пропуски букв, опечатки и т.д. Следует обязательно использовать с опцией -wordforms. Правила нечеткого поиска работают в полной мере только в версии Pro поискового движка.

См. примеры нечеткого поиска.

К примеру, нечеткий поиск для слова 'море' может дать такие результаты:

нечеткий поиск

Обратите внимание, что результаты поиска в этом случае получают соответствующую степени похожести оценку достоверности (поле rel=xxx). Кроме пропуска букв и опечаток, алгоритм нечеткого поиска обнаруживает транслитерацию кириллицы (типа чебурашка-tcheburashka), замену кириллицы на визуально эквивалентную латиницу или цифры 0 и 3 для букв О и З, и некоторые другие случаи.

-case - строго учитывать регистр букв. По умолчанию регистр большие и малые буквы при сравнении считаются эквивалентными. Не работает в релизе 0.80.

 

-correlate - проверять грамматическое согласование слов в найденных контекстах. Несмотря на внешнюю простоту данный алгоритм проверки корректности результатов позволяет отсекать обычно около 10-15 % бессмысленных контекстов. Работу алгоритма можно продемонстрировать на таком примере. Допустим выполняется поиск словосочетания "пушистый кот". Встретив предложение "пушистая собака и белый кот" обычный алгоритм поиска успешно сопоставит паттерн запроса и выделенные слова, хотя в предложении эти слова принадлежат к разным синтаксическим группам. С командой -correlate поисковый движок проверит грамматическое согласование слов "пушистая" и "кот" и может либо отвергнуть результат, либо понизить его достоверность. В текущей реализации выполняется понижение достоверности, поэтому такие результаты накапливаются в конце отсортированного по релевантности списка результатов. Более интеллектуальный алгоритм грамматической проверки релевантности результатов предоставляет команда -aa.

Обратите внимание, что данная команда работает только в паре с -distance=s.

 

-aa - выполнять синтаксический анализ текста, выявлять грамматические связи между словами. Это позволяет исключить из результирующей выборки нерелевантные результаты. Пусть, к примеру, паттерн имеет вид "белая кошка". Тогда поиск по тексту "черная кошка и белая собака" даст успех, хотя это очевидно ошибочный вывод. Без построения грамматического дерева не обойтись, что и выполняется с опцией -aa. Пример того, как используется эта опция для извлечения данных, можно посмотреть здесь.

Обратите внимание, что данная команда работает только в паре с -distance=s.

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

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

 

-semnet=N - включение операций с тезаурусом, точнее говоря - задание предельного расстояния между словарными статьями по семантической сети. Если не вдаваться в подробности (которые можно посмотреть здесь), то задание значения 1 позволяет сопоставлять, к примеру, инфинитив ИДТИ с причастием ШЕДШИЙ или деепричастием ИДЯ, или сопоставлять синонимы. См. примеры использования данной опции.

Для нормальной работы данной команды в составе словаря должен быть тезаурус.

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

 

-links=XXX - при сопоставлении слов по тезаурусу (см. команду semnet) использовать связи с именем XXX. Несколько команд-links могут сформировать ИЛИ-набор допускаемых связок, что позволяет выполнять, к примеру, сопоставление по синонимам, по грамматическим связям, по семантическим связям и т.д. Сами типы связей объявляются в Словаре. Если фильтрация связок не задана, то принимаются все связки.

Для упрощения использования команда позволяет ссылаться на групповые имена:

-links=@translate - выполнять перевод слов

-links=@grammar - грамматические связи (плотность-плотный-уплотнение), подробнее об этих связях на странице Грамматического Словаря Русского Языка.

-links=@semantics - семантические связи (сыр-еда), включая синонимы

-links=@synonyms - синонимы

 

К примеру, поиск с одновременным переводом можно выполнить командами -semnet=1 -links=@translate, как показано на скриншоте:

перевод текста при поиске

 

Грамматические связи позволяют правильно сопоставлять части речи (прилагательные, существительные, глаголы). Например, команда -links=@grammar -sample "детский" может дать такой результат:

использование тезауруса при поиске

 

-language lang1;lang2;...;langN - загружать морфологические анализаторы только для перечисленных языков. Это позволяет уменьшать выделяемую грамматическому движку оперативную память, так как по умолчанию загружаются анализаторы для всех доступных в словаре языков.

Например:

faind -language ru -dir c:\Документы -wordforms -sample сервер

Сокращенные обозначения для реализованных языков: en - английский, ru - русский, fr - французский, es - испанский. Кроме того, можно использовать следующие метаимена: all или * - все языки, user - язык текущего пользователя.

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

-try_translit пробовать также искать слова запроса после их транслитерации

Взаимное расположение слов

-ordered - порядок слов в запросе должен быть соблюден и в найденном тексте. По умолчанию слова отыскиваются в пределах одного файла (или предложения - см. -distance) независимо друг от друга в произвольном порядке. Таким образом, по умолчанию паттерн "черная кошка" совпадет с текстом "белая кошка и черная собака". Используйте опцию -ordered для того, чтобы заставить поисковый движок строго придерживаться порядка слов в запросе.

-distance=N максимальное расстояние между словами. По умолчанию слова в тексте могут быть расположены как угодно далеко друг от друга, что не всегда имеет смысл. Обычно связанные слова находятся в пределах 5-10 лексем друг от друга (если исключать патологические случаи сложных причастных оборотов).

В некоторых случаях можно вводить требование - все слова должны быть в пределах одного предложения. Для этого вместо числа N указывается символ s: -distance=s. В частности, команды проверки грамматического согласования -aa и -correlate требуют указания -distance=s.

Если все слова паттерна должны быть в пределах одной строки текстового файла (только для простых текстовых файлов!), то используется опция -distance=l

 

Определение части документа для поиска

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

-target_filename=true поиск в именах файлов.

-target_content=false не искать в содержимом документов

К примеру, чтобы выполнить поиск фрагмента текста 'hit' только в именах файлов в некоторой области поиска, необходимо применить команду типа -target_filename=true -target_content=false -sample 'hit', результат будет примерно таким:

пример поиска в именах файлов

То есть поисковая машина пытается отыскать в именах файлов указанную группу символов. Аналогичным образом можно применять и обычные регулярные выражения, например поиск по этой же группе файлов для паттерна -regex '\\r(.+)t' дает:

Поиск в и менах файлов с регулярными выражениями

 

Поиск "везде"

Для упрощения повседневного использования поисковых утилит в движке есть две команды обобщенного поиска "везде", описываемые далее. Обе команды допускают совместное использование с командами -listfiles (сохранение результатов поиска), -maxhitcount (изменение числа находимых документов).

Обе команды выполняются в "тихом" режиме(см. -verbose=off), не загрязняя экран потоком имен просматриваемых файлов и папок.

-whereis имя_файла_или_маска

Поиск файла, заданного именем или маской с символами * и ?, ведется на всех жестких дисках компьютера. Поиск выполняется без использования индексной базы, поэтому для получения корректных результатов нет необходимости в какой-то предварительной обработке дисков или обновления индексов.

файловый поиск

-locate паттерн_запроса

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

1. все актуальные индексы в порядке их создания;

2. папка 'Мои документы';

3. все диски компьютера;

4. доступные в локальной сети Windows открытые ресурсы.

Дополнительные материалы

Процедурный API поисковой системы

Морфологический анализатор

Словарь грамматической машины

Грамматический Словарь Русского Языка

Где скачать поисковую систему и SDK

Скачать SDK поисковой системы с примерами и другие компоненты можно здесь поисковая система

  © Mental Computing 2010
изменено 01-Jun-10