Труды КНЦ вып.18 (ОКЕАНОЛОГИЯ вып. 4/2013(18))

УДК 004.94 А.А. Зуенко1,2, А.А. Апмаматов1 1ФГБУН Институт информатики и математического моделирования технологических процессов КНЦРАН 2Кольский филиал ПетрГУ ПОИСКОВЫЕ ЗАПРОСЫ НА ОСНОВЕ ОПЕРАЦИЙ С ЛОГИЧЕСКИМИ ВЕКТОРАМИ* Аннотация Предлагается оригинальный алгоритм поиска в естественно-языковых текстах, основанный на алгебраическом представлении исходного текста и поисковых операций. Для гибкого задания различных условий поиска применяются поисковые шаблоны, которые транслируются в совокупность алгебраических операций над логическими векторами. Ключевые слова: поисковый запрос, логические векторы, регулярные выражения. А.А. Zuenko, А.А. Almamatov RETRIEVAL REQUESTS USING OPERATIONS ON BOOLEAN VECTORS Abstract An original algorithm for searching in natural language texts based on the algebraic representation of the source text and search operations is proposed. The algorithm uses search patterns for flexible setting various search conditions. The patterns are translated into a sets of algebraic operations on boolean vectors. Key words: retrieval request, boolean vectors, regular expressions. Введение В настоящее время существует множество алгоритмов поиска подстроки в строке: Бойера-Мура, Чж у - Такаоки, Бойера - Мура - Хорспула, Кнута - Морриса - Пратта, Рабина - Карпа и т.д. Кроме задачи отыскания точного вхождения подстроки в строку, очень широко распространена задача поиска, где некоторые символы или после­ довательности символов могут быть заданы не точно, а в виде интервалов символов, некоторых классов символов, условных выражений и тд . Для стандартизации таких запросов в различных приложениях используются общепринятые стандарты регулярных выражений. В документальных информационных системах применяется два наибо­ лее распространенных языка регулярных выражений для поисковых запросов: • POSIX - (Portable Operating System Interface for Unix - переносимый интерфейс операционных систем Unix; *Работа выполнена при финансовой поддержке РФФИ (проекты №№ 11-08-00641, 12-07-00550-а, 12-07-00689-а, 13-07-00318-а), ОНИТ РАН (проект 2.3 в рамках текущей Программы фундаментальных научных исследований) и Президиума РАН (проект 4.3 Программы № 16). 119