Ускоренный препроцессинг в задаче поиска подстрок в строке
Автор: Мазуренко А.В., Болдырихин Н.В.
Журнал: Advanced Engineering Research (Rostov-on-Don) @vestnik-donstu
Рубрика: Информатика, вычислительная техника и управление
Статья в выпуске: 3 т.19, 2019 года.
Бесплатный доступ
Введение. Бурное развитие таких систем, как Yandex, Google и пр., предопределило актуальность задачи поиска подстрок в строке. На сегодняшний день активно исследуются подходы к ее решению. Эта задача используется при создании систем управления базами данных, поддерживающих ассоциативный поиск. Кроме того, она применима при решении вопросов информационной безопасности, создании антивирусных программ. Алгоритмы поиска подстрок в строке используются в задачах обнаружения, основанного на сигнатурах.Материалы и методы. Решение задачи базируется на алгоритме Ахо - Корасик, который представляет собой классический способ осуществления поиска подстрок в строке. Вместе с тем применен новый подход в части, касающейся предварительной обработки.Результаты исследования. Показана возможность построения функции перехода и суффиксных ссылок при помощи суффиксных массивов и специальных отображений. Исследована взаимосвязь между префиксным деревом и суффиксными массивами. Это дало возможность разработать принципиально новый способ построения функций перехода и ошибок...
Поиск подстроки, алгоритм ахо - корасик, префиксное дерево, суффиксный массив, поиск информации, функция ошибок, функция перехода
Короткий адрес: https://sciup.org/142221962
IDR: 142221962 | УДК: 519.689 | DOI: 10.23947/1992-5980-2019-19-3-290-300
Accelerated preprocessing in task of searching substrings in a string
Introduction. A rapid development of the systems such as Yandex, Google, etc., has predetermined the relevance of the task of searching substrings in a string, and approaches to its solution are actively investigated. This task is used to create database management systems that support associative search. Besides, it is applicable in solving information security issues and creating antivirus programs. Algorithms of searching substring in a string are used in signature-based discovery tasks.Materials and Methods. The solution to the problem is based on the Aho-Corasick algorithm which is a typical technique of searching substrings in a string. At the same time, a new approach regarding preprocessing is employed.Research Results. The possibility of constructing the transition function and suffix references through suffix arrays and special mappings, is shown. The relationship between the prefix tree and suffix arrays was investigated, which provided the development of a fundamentally new method of constructing the transition and error functions...
Список литературы Ускоренный препроцессинг в задаче поиска подстрок в строке
- Stallings, W. Computer security: principles and practice / W. Stallings. - Boston: Pearson, 2012. - 182 p.
- Исследование возможности применения генетических алгоритмов для реализации криптоанализа блочных криптосистем / Ю. О. Чернышев// Вестник Дон. гос. техн. ун-та. - 2015. - T. 15, № 3 (82). - С. 65-72.
- Садовой, Н. Н. Программные утилиты для контроля и предотвращения сетевых атак на уровне доступа к сети / Н. Н. Садовой, Ю. В. Косолапов, В. В. Мкртичян // Вестник Дон. гос. техн. ун-та. - 2005. - Т. 5, № 2 (24). - C. 173-178.
- Могилевская, Н. С. Пороговое разделение файлов на основе битовых масок: идея и возможное применение / Н. С. Могилевская, Р. В. Кульбикаян, Л. А. Журавлев // Вестник Дон. гос. техн. ун-та. - 2011 - Т. 11, № 10. - С. 1749-1755.
- Шелудько, А. А. Поиск информационных объектов в памяти компьютера при решении задач обеспечения кибербезопасности / А. А. Шелудько, Н. В. Болдырихин // Молодой исследователь Дона. - 2018. - № 6 (15). - С. 81-86.
- Мазуренко, А. В. Обнаружение, основанное на сигнатурах, с использованием алгоритма Ахо - Корасик / А. В. Мазуренко, Н. В. Болдырихин // Тр. Сев.-Кав. ф-ла Моск. техн. ун-та связи и информатики. - 2016. - № 1. - С. 339-344.
- Мазуренко, А. В. Алгоритм проверки подлинности пользователя, основанный на графических ключах / А. В. Мазуренко, Н. С. Архангельская, Н. В. Болдырихин // Молодой исследователь Дона. - 2016. - № 3 (3). - С. 92-95.
- Мазуренко, А. В. Геометрическая реализация метода проведения электронных выборов, основанного на пороговом разделении секрета / А. В. Мазуренко, В. А. Стукопин // Вестник Дон. гос. техн. ун-та. - 2018. - Т. 18, № 2. - С. 246-255.
- Алгоритмическая оценка сложности системы кодирования и защиты информации, основанной на пороговом разделении секрета, на примере системы электронного голосования / Л. В. Черкесова// Вестник Дон. гос. техн. ун-та. - 2017. - Т. 17, № 3. - С. 145-155.
- Антонов, Е. С. Как найти миллион. Сравнение алгоритмов поиска множества подстрок / Е. С. Антонов // RSDN Magazine. - 2011. - № 1. - С. 60-67.
- Tarakeswar, M. K. Search Engines: A Study / M. K. Tarakeswar, M. D. Kavitha // Journal of Computer Applications. - 2011. - Vol. 4, № 1. - P. 29-33.
- Karkkainen, J. Linear work suffix array construction / J. Karkkainen, P. Sanders, S. Burkhardt // Journal of the ACM. - 2006. - Vol. 53, № 6. - P. 918-936.
- Баклановский, М. В. Поведенческая идентификация программ / М. В. Баклановский, А. Р. Ханов // Моделирование и анализ информационных систем. - 2014. - Т. 21, № 6. - С. 120-130.
- Efficient repeat finding in sets of strings via suffix arrays / V. Becher// Discrete Mathematics and Theoretical Computer Science. - 2013. - Vol. 15, № 2. - P. 59-70.
- 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.
