Применение теории динамических систем для обработки текстовой информации

Сергей Колесник
Руководитель группы разработки
программных продуктов компании "ИВК"

Постановка задачи

Требуется реализовать хранилище текстовой информации. Хранилище должно удовлетворять следующим свойствам:

• кодировка сохраняемых сообщений - произвольная;
• эффективный поиск всех сообщений, содержащих определенный запрос;
• добавление/удаление сообщений.

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

Алгоритм записи сообщения

Пусть записываемое сообщение представляется в виде конечной последовательности a₁,a₂,...,a_n, a_j E А, где множество А = {0,..,255,256} является алфавитом. Первые 256 элементов алфавита являются всевозможными значениями байта, а значение 256 является дополнительным элементом, который называется "маркер конца сообщения". Для чего нужен маркер конца сообщения? Каждое сообщение представляется в виде цикла, поэтому, чтобы обеспечить однозначное восстановление записанного сообщения, необходимо указать позицию окончания сообщения с помощью дополнительного элемента. Создаваемое хранилище является байт-ориентированным, то есть оно не имеет внутренней кодировки записываемых сообщений, таким образом, в базу можно записывать не только текстовые сообщения в различных кодировках, но и любые данные. Для хранилища записываемое сообщение - это конечная последовательность байтов. Множество Абудем называть основным алфавитом. Элементы множества Апоследовательно пронумерованы значениями от 0 до 256.

Алгоритм записи сообщения состоит из следующих этапов:

1. дополнение сообщения маркером конца сообщения;
2. представление сообщения в виде конечной последовательности отрезков длины q;
3. ортогонализация;
4. запись сообщения, полученного после ортогонализации;
5. соответствующее изменение индексных таблиц.

Пусть а₁ ,а₂, ... ,а_n-1 - исходное сообщение, уровень записи q=2.

Рассмотрим процесс записи поэтапно

В результате 1-го этапа сообщение примет вид а₁ ,а₂,...,a_n гд a_n=256.

На 2-м этапе используется понятие уровня записи q, аналогично алгоритму из статьи "Хаотические процессоры". Например, при q=2 записываемое сообщение а₁ ,а₂,...,a_n представляется в виде последовательности пар (а₁ ,а₂), (а₂ ,а₃),...,(а_n-1,а_n), (а_n,а₁).

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

x₁,x₂ E A U A’ В алгоритме ортогонализации используются элементы множества А', называемого расширенным алфавитом (правила заполнения расширенного алфавита исходят из алгоритма ортогонализации и представлены ниже). Следует заметить, что если в хранилище не сохранено ни одного сообщения, множество Апусто. Каждый элемент множества представляет собой пару (для случая q=2) (x₁,x₂), где x₁,x₂ E A U A’ есть каждый элемент пары может сам являться парой, либо являться элементом основного алфавита. При этом все элементы множества А' последовательно пронумерованы, начиная со значения 257, так как нумерация от 0 до 256 соответствует элементам основного алфавита А. Алгоритм ортогонализации осуществляется в три этапа:

1. замена пар (а₁ ,а₂), (а₂ ,а₃),...,(а_n-1,а_n), (а_n,а₁) элементами расширенного алфавита;
2. внешняя ортогонализация;
3. внутренняя ортогонализация.

Рассмотрим последовательно эти этапы

На 1-м этапе ортогонализации осуществляется последовательный поиск пар (а₁ ,а₂), (а₂ ,а₃),...,(а_n-1,а_n), (а_n,а₁) среди элементов расширенного алфавита А'. Пусть пара (a_i,a_i+1) найдена в множестве А' и данной паре соответствует номер j. Тогда заменяем данную пару в исходном сообщении a₁,a₂,…a_i-1,a_i,a_i+1,a_i+2…,a_n на элемент j, получим преобразованное сообщение, которое будет иметь вид a₁,a₂,…a_i-1,j,a_i+2…,a_n.

Как видно, исходное сообщение сократилось за счет замены парыa_i,a_i+1 элементом расширенного алфавита j.

Снова разбиваем полученное сообщение на пары, получим (a₁,a₂), (a₂,a₃),…, (a_i,a_i+2),…, (a_n-1,an), (a_n,a₁).

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

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

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

Таким образом, выполнение ортогонализации обеспечивает выполнение двух условий:

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

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

На 5-м - обновление индексных таблиц в соответствии с записанным сообщением. Индексные таблицы также сохраняются в файлах. Применение в алгоритме файлов, содержащих индексные таблицы, позволяет существенно сократить трудоемкость алгоритма восстановления сообщений.

Алгоритм восстановления сообщений

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

На вход алгоритма подается несколько основных параметров:

• поисковый запрос - строка а₁,а₂,...,а_n;
• поиск с учетом или без учета регистра;
• набор кодировок, с учетом которых осуществляется поиск строки.

Алгоритм восстановления сообщений состоит из следующих этапов:

1. поиск элемента среди элементов поисковой строки, который имеет наименьшее число вхождений в элементы расширенного алфавита. Найденный элемент обозначается a_j ;
2. инициализация. Формируется множество /, содержащее лишь один элемент - a_j , множество F пусто;
3. для каждого элемента i E l выполняются п. 4-6;
4. для каждого элемента а Е А' проверяются условия:
   • элемент а включает в себя элемент i;
   • элемент а успешно проходит проверку на соответствие поисковому запросу.

Если элемент а удовлетворяет этим условиям, тогда I = I U{a};

5. для каждого сообщения т Е М - множество всех сообщений, записанных в хранилище, содержащем элемент /, осуществляется проверка на полное содержание в нем поисковой строки. Если сообщение полностью содержит поисковую строку, тогда F = F U{m};
6. удаляем элемент из множества: I = I \ {i}. Если / пусто, выход из алгоритма.

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

Выводы

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