Ускоренный препроцессинг в задаче поиска подстрок в строке
Автор: Мазуренко А.В., Болдырихин Н.В.
Журнал: Вестник Донского государственного технического университета @vestnik-donstu
Рубрика: Информатика, вычислительная техника и управление
Статья в выпуске: 3 т.19, 2019 года.
Бесплатный доступ
Введение. Бурное развитие таких систем, как Yandex, Google и пр., предопределило актуальность задачи поиска подстрок в строке. На сегодняшний день активно исследуются подходы к ее решению. Эта задача используется при создании систем управления базами данных, поддерживающих ассоциативный поиск. Кроме того, она применима при решении вопросов информационной безопасности, создании антивирусных программ. Алгоритмы поиска подстрок в строке используются в задачах обнаружения, основанного на сигнатурах.Материалы и методы. Решение задачи базируется на алгоритме Ахо - Корасик, который представляет собой классический способ осуществления поиска подстрок в строке. Вместе с тем применен новый подход в части, касающейся предварительной обработки.Результаты исследования. Показана возможность построения функции перехода и суффиксных ссылок при помощи суффиксных массивов и специальных отображений. Исследована взаимосвязь между префиксным деревом и суффиксными массивами. Это дало возможность разработать принципиально новый способ построения функций перехода и ошибок...
Поиск подстроки, алгоритм ахо - корасик, префиксное дерево, суффиксный массив, поиск информации, функция ошибок, функция перехода
Короткий адрес: https://sciup.org/142221962
IDR: 142221962 | DOI: 10.23947/1992-5980-2019-19-3-290-300
Список литературы Ускоренный препроцессинг в задаче поиска подстрок в строке
- 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.
