В работе рассмотрена одна из важнейших задач обработки символьных данных - поиск точно заданной подстроки в строке. Данная задача чрезвычайна важна, так как символьные данные являются основной формой обмена информацией и имеют широкое применение в таких областях, как информатика, лингвистика, литература, а также молекулярная биология. Рассмотрены типы символьных данных и особенности алгоритмов, которые используются для каждого типа. Затронут вопрос поиска в статичных данных, к которым относятся различного рода базы данных, архивы, словари, документы, статьи, книги и т.д. Описаны основные сложности, возникающие при поиске в таких данных. Рассмотрены основные алгоритмы, использующиеся для поиска в статичных данных. Рассмотрены их достоинства и недостатки. Представлен алгоритм построения структуры, представляющей строку в виде хеш-таблицы, состоящей из подстрок данной строки, и алгоритм поиска при помощи этой структуры. Рассмотрен вопрос выбора правильной функции хеширования и выбора констант, использующихся при вычислении хеша строки. Приведен псевдокод алгоритма построения структуры и псевдокод алгоритма поиска при помощи этой структуры. Частично затронуты вопросы реализации описанной структуры и алгоритма поиска на языках программирования. Произведено сравнение скорости поиска и предобработки текста разработанного алгоритма с такими алгоритмами, как алгоритм Бойера-Мура, алгоритм поиска в суффиксном дереве и алгоритм поиска подстроки, использующий позиционное представление текста. На основе полученных результатов сделаны выводы об эффективности разработанного алгоритма. Описаны плюсы и минусы полученного алгоритма, а также даны рекомендации по использованию данного алгоритма при различных исходных данных.
展开▼
