Аннотация
Зуенко А. А. Алмаматов А. А. - Поисковые запросы на основе операций с логическими векторами Предлагается оригинальный алгоритм поиска в естественно-языковых текстах, основанный на алгебраическом представлении исходного текста и поисковых операций. Для гибкого задания различных условий поиска применяются поисковые шаблоны, которые транслируются в совокупность алгебраических операций над логическими векторами.
Поисковые запросы на основе операций с логическими векторами
В настоящее время существует множество алгоритмов поиска подстроки в строке: Бойера-Мура, Чжу – Такаоки, Бойера – Мура – Хорспула, Кнута – Морриса – Пратта, Рабина – Карпа и т.д. Кроме задачи отыскания точного вхождения подстроки в строку, очень широко распространена задача поиска, где некоторые символы или последовательности символов могут быть заданы не точно, а в виде интервалов символов, некоторых классов символов, условных выражений и т.д. Для стандартизации таких запросов в различных приложениях используются общепринятые стандарты регулярных выражений.
В документальных информационных системах применяется два наиболее распространенных языка регулярных выражений для поисковых запросов:
- POSIX – (Portable Operating System Interface for Unix – переносимый интерфейс операционных систем Unix;
- PCRE – Perl Compatible Regular Expressions – регулярные выражения,совместимые с языком Perl.
Простота и скорость выполнения запросов, использующих регулярные выражения, зависит от эффективности методов и алгоритмов, реализующих эти запросы, от того насколько исполнение запросов при выбранном подходе поддается распараллеливанию.В настоящей работе [1]описана модификация базового алгоритма полнотекстного поиска в естественно-языковых текстах, подробно рассмотренного в [2].Модификация основана на алгебраическом представлении исходного текста и поисковых операций, обеспечивает возможность гибкого задания различных условий поиска с использованием стандарта POSIX. Поисковые шалоны транслируются в совокупность алгебраических операций над логическими векторами. В виде набора таких векторов представляется и сам исходный текст. При этом существенно повышается быстродействие системы в отличие от известных алгоритмов поиска слов, основанных на последовательном сравнении фрагментов текста с поисковым образом, за счет возможности эффективно распараллеливать процедуры поиска вплоть до отдельного символа запроса.
Далее рассмотрим возможности используемого языка запросов и особенности реализации тех или иных языковых конструкций с помощью операций над логическими векторами.
Формирование поисковых шаблонов
Запрос формируется в виде строки текста, содержащей в себе последовательность символов, классов символов, заданных вариантов, wildcard и т.д.
Рисунок 1 – Классы символов
При необходимости возможно задание некоторого множества символов/классов, а также поиска всего, кроме заданных символов. Для этого нужно множество заданных символов вписать в квадратные скобки. Если необходимо искать все, кроме заданных символов, нужно после открывающейся скобки поставить символ «^».
Рисунок 2 – Многовариантный поиск (ИЛИ-выражение)
Также возможно задание выражения «ИЛИ» вместо некоторого символа в запросе. По принципу работы оно эквивалентно предыдущей функции с той лишь разницей, что между всем, заданным внутри функции, выполняется функция «И». Отрицание выражения с помощью «^» также возможно.
Рисунок 3 – Уточняющий поиск (И-выражение)
Теперь прейдем к описанию базового алгоритма поиска на основе операций с логическими векторами.
Базовый алгоритм поиска подстроки на основе операций с логическими векторами.
Пусть используемый алфавит состоит из N литер. Позиции в тексте отдельной литеры могут быть заданы характеристическим вектором, размерность которого равна длине самого текста L. Каждый элемент характеристического вектора принимает значение 1 или 0 в зависимости от того, присутствует или нет данная литера в тексте в данной позиции. Текст представлен в памяти машины в виде N логических векторов длиной L. Чтобы найти в этой структуре искомое слово, необходимо пронумеровать последовательностью 0, 1, 2, ... литеры искомого слова; выбрать логические векторы, соответствующие этим литерам, и выполнить для каждого из этих векторов сдвиг влево на число разрядов, соответственно нумерации; выполнить логическое умножение выбранных и преобразованных логических векторов; если в результате получится нулевой вектор, то это означает, что искомого слова в данном тексте нет. В противном случае единицы этого характеристического вектора маркируют номера позиций, в которых находится начало искомого слова. Рассмотрим пример.
Пример 1. Пусть задан текст "род рада город". Необходимо найти в нем все вхождения буквосочетания "род". Для простоты будем использовать только литеры, входящие в данный текст, включая пробел. Тогда сам текст будет представлен следующей совокупностью логических векторов:
Базовый алгоритм поиска подстроки на основе операций с логическими векторами.
- V[а] : 00000101000000
- V[г]: 00000000010000
- V[д]: 00100010000001
- V[о]: 01000000001010
- V[р]: 10001000000100
- V[“ “]: 00010000100000
Запись V[s] обозначает булев вектор, соответствующий символу s. Для простоты далее будем использовать следующую сокращенную запись:
- а: 00000101000000
- г: 00000000010000
- д: 00100010000001
- о: 01000000001010
- р: 10001000000100
- пробел: 00010000100000
Начнем процедуру поиска слова "род". Первый логический вектор для литеры "р" оставим без изменений. Второй логический вектор для литеры "о" сдвинем на один разряд влево, а логический вектор для литеры "д" сдвинем на два разряда влево. Результат будет определяться произведением этих векторов. Каждый вектор отыскивается по значению символа s и номеру позиции этого символа в запросе по формуле: V’[s] = SHL(V[s], i), где i – номер позиции символа, SHL – функция побитового сдвига вектора влево на заданное количество позиций.
В итоге получим следующие логические векторы:
- SHL(V[р],0): 10001000000100
- SHL(V[о],1):10000000010100
- SHL(V[д],2):10001000000100
Логическое умножение этих векторов дает вектор: 10000000000100, в котором единицы указывают позиции, где находится начало искомого слова. Вычислительная сложность этого алгоритма при соответствующей аппаратной реализации линейно зависит от длины искомого слова и не зависит от длины текста.
Выводы
Таким образом, была рассмотрена модификация метода биассоциативного поиска текста на случай, когда для задания запросов могут быть использованы регулярные выражения. Алгоритм поиска может быть также применен за пределами задачи поиска текста. Вместо текста может быть всё, что представимо в виде последовательности битов. Например, в качестве последовательности может использоваться набор последовательно поступающих во времени векторов значений входных воздействий некоторой системы, а также выходных значений и внутренних состояний.Более того, алгоритм может использоваться не только при обработке одномерных данных. Возможна работа с данными любой размерности. При заранее известных ограничениях на размерность массива данных по каждому измерению можно будет свести операции сдвигов по любому из них к битовым сдвигам в одномерном массиве данных. К примеру, это может быть использовано в анализе и обработке растровых изображений и воксельных моделей. Алгоритм апробирован на задаче удаления служебных тегов из HTML-документов.