Ускоренный препроцессинг в задаче поиска подстрок в строке

Введение. Бурное развитие таких систем, как Yandex, Google и пр., предопределило актуальность задачи поиска подстрок в строке. На сегодняшний день активно исследуются подходы к ее решению. Эта задача используется при создании систем управления базами данных, поддерживающих ассоциативный поиск. Кроме того, она применима при решении вопросов информационной безопасности, создании антивирусных программ. Алгоритмы поиска подстрок в строке используются в задачах обнаружения, основанного на сигнатурах.

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

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

Обсуждение и заключения. Предложенная в данной статье процедура препроцессинга основывается на связи между суффиксным массивом, созданным на основе множества строк образцов, и построением функций перехода и ошибок на начальных этапах работы алгоритма Ахо — Корасик. Такой подход отличен от традиционного и требует использования алгоритмов, позволяющих построить суффиксный массив за линейное время. Таким образом, описаны алгоритмы, позволяющие существенно сократить время на предварительную обработку множества строк образцов при условии использования определенного типа алфавита по сравнению с известным подходом, предложенным А. Ахо и М. Корасик. Результаты исследований, приведенные в статье, могут быть применены в антивирусных программах, использующих поиск сигнатур вредоносных информационных объектов в памяти вычислительной системы. Кроме того, данный подход к решению задачи поиска подстроки в строке позволяет значительно ускорить работу систем управления баз данных, применяющих ассоциативный поиск.

1. Stallings, W. Computer security: principles and practice / W. Stallings. — Boston : Pearson, 2012. — 182 p.

2. Исследование возможности применения генетических алгоритмов для реализации криптоанализа блочных криптосистем / Ю. О. Чернышев [и др.] // Вестник Дон. гос. техн. ун-та. — 2015. — T. 15, № 3 (82). — С. 65–72.

3. Садовой, Н. Н. Программные утилиты для контроля и предотвращения сетевых атак на уровне доступа к сети / Н. Н. Садовой, Ю. В. Косолапов, В. В. Мкртичян // Вестник Дон. гос. техн. ун-та. — 2005. — Т. 5, № 2 (24). — C. 173–178.

4. Могилевская, Н. С. Пороговое разделение файлов на основе битовых масок: идея и возможное применение / Н. С. Могилевская, Р. В. Кульбикаян, Л. А. Журавлев // Вестник Дон. гос. техн. ун-та. — 2011 — Т. 11, № 10. — С. 1749–1755.

5. Шелудько, А. А. Поиск информационных объектов в памяти компьютера при решении задач обеспечения кибербезопасности / А. А. Шелудько, Н. В. Болдырихин // Молодой исследователь Дона. — 2018. — № 6 (15). — С. 81–86.

6. Мазуренко, А. В. Обнаружение, основанное на сигнатурах, с использованием алгоритма Ахо — Корасик / А. В. Мазуренко, Н. В. Болдырихин // Тр. Сев.-Кав. ф-ла Моск. техн. ун-та связи и информатики. — 2016. — № 1. — С. 339–344.

7. Мазуренко, А. В. Алгоритм проверки подлинности пользователя, основанный на графических ключах / А. В. Мазуренко, Н. С. Архангельская, Н. В. Болдырихин // Молодой исследователь Дона. — 2016. — № 3 (3). — С. 92–95.

8. Мазуренко, А. В. Геометрическая реализация метода проведения электронных выборов, основанного на пороговом разделении секрета / А. В. Мазуренко, В. А. Стукопин // Вестник Дон. гос. техн. ун-та. — 2018. — Т. 18, № 2. — С. 246–255.

9. Алгоритмическая оценка сложности системы кодирования и защиты информации, основанной на пороговом разделении секрета, на примере системы электронного голосования / Л. В. Черкесова [и др.] // Вестник Дон. гос. техн. ун-та. — 2017. — Т. 17, № 3. — С. 145–155.

10. Антонов, Е. С. Как найти миллион. Сравнение алгоритмов поиска множества подстрок / Е. С. Антонов // RSDN Magazine. — 2011. — № 1. — С. 60–67.

11. Tarakeswar, M. K. Search Engines: A Study / M. K. Tarakeswar, M. D. Kavitha // Journal of Computer Applications. — 2011. — Vol. 4, № 1. — P. 29–33.

12. Karkkainen, J. Linear work suffix array construction / J. Karkkainen, P. Sanders, S. Burkhardt // Journal of the ACM. — 2006. — Vol. 53, № 6. — P. 918–936.

13. Баклановский, М. В. Поведенческая идентификация программ / М. В. Баклановский, А. Р. Ханов // Моделирование и анализ информационных систем. — 2014. — Т. 21, № 6. — С. 120–130.

14. Efficient repeat finding in sets of strings via suffix arrays / V. Becher [et al.] // Discrete Mathematics and Theoretical Computer Science. — 2013. — Vol. 15, № 2. — P. 59–70.

15. Shrestha, A. M. S. A bioinformatician's guide to the forefront of suffix array construction algorithms / A. M. S. Shrestha, M. C. Frith, P. Horton // Briefings in Bioinformatics. — 2014. — Vol. 15, № 2. — P. 138–154.