WWW.BOOK.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Электронные ресурсы
 

«Journal of Siberian Federal University. Engineering & Technologies, 2017, 10(1), 126-135 ~~~ УДК 681.3.06 Combined String Searching Algorithm ...»

Journal of Siberian Federal University. Engineering & Technologies, 2017, 10(1), 126-135

~~~

УДК 681.3.06

Combined String Searching Algorithm

Roman Yu. Tsarev*,

Elena A. Tsareva and Alexey S. Chernigovskiy

Siberian Federal University

79 Svobodny, Krasnoyarsk, 660041, Russia

Received 17.12.2016, received in revised form 29.01.2016, accepted 17.01.2017

The string search problem is a classical problem of data processing. Despite a number of existing

algorithms for solving this problem, the work in this direction continues. The algorithm proposed in the article develops the theoretical basis of the string search problem by combining the algorithms of two different classes, i.e. forward and backward string searching algorithms, namely, KnuthMorris-Pratt algorithm and Bower-Moore algorithm. The paper provides the analysis of the proposed combined algorithm and comparison of its results with the basic algorithms, confirming the efficacy of the combined string search algorithm.

Keywords: pattern, search, data processing, combined algorithm.

Citation: Tsarev R.Yu., Tsareva E.A., Chernigovskiy A.S. Combined string searching algorithm, J. Sib. Fed. Univ. Eng. technol., 2017, 10(1), 126-135. DOI: 10.17516/1999-494X-2017-10-1-126-135.

Комбинированный алгоритм поиска образа в строке Р.Ю. Царев, Е.А. Царева, А.С. Черниговский Сибирский федеральный университет Россия, 660041, Красноярск, пр. Свободный, 79 Проблема поиска образа в строке является классической задачей обработки данных.

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

Ключевые слова: образ, поиск, обработка данных, комбинированный алгоритм.

© Siberian Federal University. All rights reserved * Corresponding author E-mail address: tsarev.sfu@mail.ru

– 126 – Roman Yu. Tsarev, Elena A. Tsareva… Combined String Searching Algorithm Введение Поиск образа в строке – одна из простых, но, тем не менее, крайне важных задач. Об этом говорит широкая область применения результатов ее решения: текстовые редакторы, обозреватели, средства анализа и распознания речи, а также извлечения знаний, архиваторы данных и пр. [1, 2].

За последние тридцать лет были предложены десятки различных алгоритмов, позволяющих решать задачи поиска с теми или иными особенностями. М. Ахмед с коллегами разработал алгоритм поиска образа в строке, который в отличие от других алгоритмов сравнения строк никогда не выполняет более n сравнений символов при обработке текста длины n [3]. Т.

Лерок дал ряд алгоритмов, основанных на хешировании q-грамм [4]. К. Фредрикссон и С. Грабовский разработали параллельный алгоритм, развивающий алгоритм двоичного поиска строки [5, 6]. Они предложили новый подход для алгоритма поиска строки, позволяющий получить оптимальное время поиска для заданного расстояния Хэмминга [6]. Л. Хи, Б. Фанг и Дж. Суи применили понятие окна, размер которого равен длине образа. Экспериментальное сравнение с существующими алгоритмами показало его преимущества и эффективность [7]. А. Худаиб и др. в [8] представили алгоритм двух скользящих окон. Данный алгоритм использует два скользящих окона, длина каждого из них равна образу. Оба окна движутся одновременно с двух концов строки до тех пор, пока не произойдет совпадение образа со строкой или оба окна не достигнут середины строки.





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

1. Теоретические основы комбинированного алгоритма Предлагаемый комбинированный алгоритм поиска образа в строке основан на двух алгоритмах. Один из них разработан Кнутом, Моррисом и Праттом, второй – Боуером и Муром.

Эти алгоритмы относятся к двум довольно большим подклассам алгоритмов поиска образа в строке. При сравнении символов образа и строки алгоритм Кнута-Морриса-Пратта проходит образ от начала к концу, а алгоритм Боуера-Мура – от конца к началу.

В работе обоих этих алгоритмов можно выделить два этапа:

1. Формирование таблицы d, используемой при сдвиге образа по строке.

2. Непосредственно поиск образа в строке.

Рассмотрим детально работу этих алгоритмов поиска образа в строке. Изложение будет сопровождаться примерами и пояснениями с использованием нотации языка программирования Си.

1.1. Принципы работы алгоритма Кнута-Морриса-Пратта Данный алгоритм был разработан Д. Кнутом, В. Праттом и независимо от них Дж. Моррисом в 1974 г. Однако опубликован он был совместно только в 1977 г. [9]. Этот алгоритм основывается на том соображении, что после частичного совпадения начальной части образа с соответствующими символами строки мы обладаем некоторой информацией, полученной

– 127 – Roman Yu. Tsarev, Elena A. Tsareva… Combined String Searching Algorithm на основе самого образа, которая позволит продвинуться по строке не на единицу, как при простом поиске, а дальше. Для этого алгоритм Кнута-Морриса-Пратта (или КМП-алгоритм) использует при сдвиге образа таблицу d, которая формируется еще до начала поиска образа в строке. Поскольку таблица d, формируемая согласно КМП-алгоритму, будет также использоваться в комбинированном алгоритме, обозначим ее как dKMP.

Итак, таблица dKMP для алгоритма поиска образа в строке Кнута-Морриса-Пратта формируется на основе образа и содержит значения, которые в дальнейшем будут использованы при вычислении величины сдвига образа. Размер данной таблицы равен длине образа, которую можно при программировании на языке Си определить при помощи функции int strlen(char *) библиотеки string.h. Таким образом, таблица dKMP фактически является одномерным массивом, состоящим из числа элементов, равного количеству символов в образе.

Первый элемент массива dKMP всегда равен минус единице.

Для остальных символов образа значение элементов таблицы dKMP вычисляется следующим образом: значение dKMP[ j], соответствующее j-му символу образа, равно максимальному числу символов, непосредственно предшествующих данному символу, совпадающих с началом образа. При этом если рассматриваемому символу предшествует k символов, то во внимание принимаются только k–1 предшествующих символов.

Рассмотрим формирование таблицы dKMP на примере образа “barbarian”. Так, на рис. 1 пятому символу образа “a” непосредственно предшествует один символ “b”, что совпадает с символом “b” в самом начале образа. Оба символа “b” выделены полужирным шрифтом. Поскольку количество совпавших символов равно единице, это значение получает элемент таблицы, соответствующий пятому символу образа “a”. Шестому символу образа “r” непосредственно предшествуют два символа “ba”, что совпадает с символом “ba” в начале образа. Поскольку символу “r” предшествуют два символа, совпадающие с двумя первыми символами образа, то соответствующий элемент таблицы dKMP получает значение два. Никаким другим символам образа “barbarian” не предшествуют символы, совпадающие с началом образа, поэтому соответствующие элементы таблицы dKMP равны нулю.

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

Вторым этапом работы КМП алгоритма является сравнение символов образа и строки и вычисление сдвига образа в случае их несовпадения. Символы образа рассматриваются слева направо, т. е. от начала к концу образа.

При несовпадении символов образа и строки образ сдвигается вправо по строке на следующую величину:

–  –  –

j – dKMP[ j], где j – это индекс текущего символа в образе, а dKMP[ j] – значение таблицы dKMP, соответствующее этому символу.

Приведем пример поиска в строке образа “barbarian”. На рис. 2 показан процесс работы КМП-алгоритма, сравниваемые символы подчеркнуты.

Обратите внимание: при каждом несовпадении символов образ сдвигается на все пройденное расстояние, поскольку меньшие сдвиги не могут привести к полному совпадению.

Что касается эффективности алгоритма поиска образа в строке Кнута-Морриса-Пратта, то его разработчики показывают, что требуется n + m сравнений символов, что значительно лучше, чем n * m сравнений при простом поиске (здесь n – длина строки, m – длина образа, 0 m n) [1, 9]. При этом указатель сканирования строки i никогда не возвращается назад, в то время как при простом поиске после несовпадения просмотр всегда начинается с первого символа образа и поэтому может включать символы строки, которые уже просматривались ранее.

Однако поиск образа в строке с использованием алгоритма Кнута-Морриса-Пратта дает выигрыш только в том случае, когда несовпадению символов из образа и строки предшествовало некоторое число совпадений. Если при сравнении образа и строки первые же символы различны, то образ сдвигается только на один символ. Продвижение образа более чем на единицу происходит лишь в этом случае, когда происходит совпадение нескольких символов образа и строки.

1.2. Принципы работы алгоритма Боуера-Мура В 1977 г. Р.С. Боуер и Дж.С. Мур предложили алгоритм, который не только улучшает обработку самого плохого случая, но и дает выигрыш в общем случае [10]. Алгоритм поиска образа в строке Боуера-Мура (или БМ-алгоритм) основывается на сравнениях символов с конца образа, а не с начала. Скорость в алгоритме Боуера-Мура достигается за счет того, что удается пропускать те части текста, которые заведомо не участвуют в успешном сопоставлении.

Как и при работе КМП-алгоритма, перед началом поиска на основе образа создается таблица d, используемая в дальнейшем при смещении образа по строке. Так как при работе комбинированного алгоритма данная таблица также будет использоваться, обозначим ее dBM.

Первоначально всем элементам таблицы dBM присваивается значение, равное длине образа.

<

–  –  –

Следующим шагом является присвоение каждому элементу таблицы dBM значения, равного удаленности соответствующего символа образа от конца образа. На рис. 3 показан образ и удаленность каждого из его символов от конца образа. Однако если образ содержит несколько одинаковых символов, то элементу таблицы dBM, соответствующему данному символу, присваивается значение, равное удаленности от конца образа самого правого из одинаковых символов [1]. Так, например, образ “barbarian” содержит три символа “a”, удаленность от конца образа самого правого из них равна единице. В связи с этим элементам таблицы dBM, соответствующим остальным символам “a” в образе, присваиваем значение, равное единице (рис. 3).

Аналогично для всех символов “r” значения элементов таблицы dBM принимаем равным трем, а для всех символов “b” – пяти.

При программной реализации алгоритма поиска образа в строке Боуера-Мура, как и комбинированного алгоритма, предлагается для создания таблицы dBM использовать таблицу кодов символов ASCII (табл. 1).

Таблица ASCII содержит 256 символов, поэтому таблицу dBM можно объявить как одномерный целочисленный массив, состоящий из 256 элементов: int d[256].

Любой печатный или служебный символ имеет свой код. Например, код символа “a” равен 97, код символа “r” – 114, а код пробела – 32. Можно отметить, что коды кириллических символов лежат в диапазоне от 192 до 255.

Рассмотрим особенности программной реализации таблицы dBM на примере образа “barbarian”. Поскольку данный образ содержит девять символов, то его длина равна девяти.

Соответственно, на этапе инициализации всем элементам таблицы dBM присваивается значение девять:

d[0] = d[1] = … = d[254] = d[255] = 9.

Далее происходит присваивание элементам таблицы dBM соответствующих значений, равных расстоянию от рассматриваемого символа до конца образа. При этом индекс элемента таблицы dBM, который получает новое значение, определяется кодом ASCII рассматриваемого символа.

Так, код ASCII символа “a” образа равен 97. Соответствующее ему значение элементов таблицы dBM, как это уже было показано на рис. 3, равно единице. Таким образом,

–  –  –

Можно отметить, что при программной реализации элемент массива d с индексом девяносто семь соответствует всем символам “a” в образе “barbarian”. И, таким образом, для всех

–  –  –

символов “a” образа всем соответствующим элементам таблицы dBM при такой записи присваивается значение, равное единице (рис. 3).

Аналогичным образом изменяются значения элементов таблицы dBM, соответствующие символам образа “i”, “r”, “b”.

Вторым этапом работы БМ-алгоритма является собственно сам поиск образа в строке.

При сравнении образа со строкой образ продвигается по строке слева направо. Однако сравнения символов образа и строки выполняются, двигаясь по образу справа налево.

Сравнение образа со строкой происходит до тех пор, пока: 1) не будет рассмотрен весь образ, что говорит о том, что соответствие между образом и некоторой частью строки найдено;

2) не закончится строка, что значит, что вхождений, соответствующих образу, в строке нет;

3) не произойдет несовпадения символов образа и строки, что вызывает сдвиг образа на несколько символов вправо и продолжение процесса поиска.

В том случае, если произошло несовпадение символов, смещение образа по строке определяется значением элемента таблицы dBM. Однако индексом данного элемента является код ASCII символа строки. Подчеркнем, что, несмотря на то что массив dBM формируется на основе

– 131 – Roman Yu. Tsarev, Elena A. Tsareva… Combined String Searching Algorithm

–  –  –

Рис. 4. Процесс работы алгоритма поиска образа в строке Боуера-Мура образа, смещение определяется несовпавшим символом из строки. На рис. 4 показан пример работы БМ-алгоритма, сравниваемые символы подчеркнуты.

На первой итерации произошло несовпадение символа образа “n” и символа строки “u”.

Напомним, что значения всех элементов массива dBM для всех возможных символов на этапе инициализации приравнивается длине образа, т.е. девяти. Поскольку символ “u” в образе не встречается, то значение элемента d[‘u’] при дальнейшем формировании таблицы не менялось и осталось равным девяти. Поэтому образ смещается вправо на девять символов. Если бы произошло совпадение этих двух символов, то далее рассматривался бы предпоследний символ образа и соответствующий ему символ строки и т. д. При сравнивании образа и строки происходит несовпадение символов “n” и “r”. Опять же, определяя смещение по символу строки (d[‘r’]), получаем значение, равное трем. Образ сдвигается на три символа вправо. Так образ постепенно сдвигается по строке до тех пор, пока образ в строке не будет найден или не кончится строка.

Оценка эффективности БМ-алгоритма показывает, что практически всегда алгоритм требует значительно меньше n сравнений. В самых же благоприятных обстоятельствах, когда последний символ образа всегда попадает на несовпадающий символ строки, число сравнений равно n / m [1, 10].

1.3. Комбинация алгоритмов поиска образа в строке Кнута-Морриса-Пратта и Боуера-Мура На основе изложенных алгоритмов поиска образа в строке Кнута-Морриса-Пратта и Боуера-Мура по созданию таблиц для определения сдвига и непосредственно поиску образа в строке был предложен следующий комбинированный алгоритм.

Шаг 1. Создание таблицы dKMP согласно алгоритму поиска образа в строке Кнута-МоррисаПратта.

Шаг 2. Создание таблицы dBM согласно алгоритму поиска образа в строке Боуера-Мура.

Шаг 3. Полагаем начальное значение индекса i, соответствующее положению образа относительно строки.

Шаг 4. Полагаем начальные значения индексов jKMP и jBM, указывающих на начало и конец образа соответственно.

Шаг 5. Сравниваем символ образа с индексом jKMP и соответствующий символ строки, сравниваем символ образа jBM и соответствующий символ строки. Если хотя бы при одном сравнении символы не совпали, то переход на шаг 11.

Шаг 6. Если jKMP меньше jBM, то переход на шаг 9.

– 132 – Roman Yu. Tsarev, Elena A. Tsareva… Combined String Searching Algorithm Шаг 7. Вывод сообщения о том, что образ совпал с частью строки.

Шаг 8. Переход на шаг 15.

Шаг 9. Увеличиваем индекс jKMP на единицу (т.е. переходим к находящемуся правее символу), уменьшаем индекс jBM на единицу (т.е. переходим к находящемуся левее символу).

Шаг 10. Переход на шаг 5.

Шаг 11. Выбираем большее смещение из двух: jKMP – dKMP[ jKMP] и dBM [i + длина образа – jBM].

Шаг 12. Смещаем образ вправо относительно строки, увеличивая значение индекса i на смещение, определенное на шаге 11.

Шаг 13. Если сумма i и длины образа меньше длины строки, то переход на шаг 4.

Шаг 14. Вывод сообщения о том, что искомый образ не найден.

Шаг 15. Остановка.

Комбинированный алгоритм позволяет найти совпадение образа с частью строки при меньшем количестве сдвигов благодаря тому, что на шаге 11 выбирается больший сдвиг из двух, которые могут быть получены от алгоритмов поиска образа в строке Кнута-МоррисаПратта и Боуера-Мура. При этом сами эти алгоритмы гарантируют, что, насколько бы большой ни был сдвиг, никакое совпадение образа с частью строки пропущено не будет.

2. Анализ результатов работы комбинированного алгоритма Комбинированный алгоритм поиска образа в строке, основанный на алгоритмах КнутаМорриса-Пратта и Боуера-Мура, был реализован в рамках компьютерной программы InfoSearch. Данная программа позволяет провести анализ работы алгоритмов Боуера-Мура, Кнута-Морриса-Пратта и комбинированного алгоритма. На рис. 5 представлен интерфейс программы.

–  –  –

Анализ результатов работы рассмотренных алгоритмов поиска образа в строке может быть проиллюстрирован на примере трагедии Уильяма Шекспира «Гамлет». В табл. 2 Roman Yu. Tsarev, Elena A. Tsareva… Combined String Searching Algorithm Таблица 2. Результаты работы алгоритмов поиска образа в строке

–  –  –

Анализ результатов работы рассмотренных алгоритмов поиска образа в строке может быть проиллюстрирован на примере трагедии Уильяма Шекспира «Гамлет». В табл. 2 представлены результаты работы алгоритмов при поиске указанных в первой колонке слов. Данные слова были выбраны в качестве искомых образов случайным образом.

Выполненный анализ показывает, что комбинированному алгоритму, для того чтобы найти вхождение образа в строку, требуется в несколько раз меньше сдвигов, чем алгоритму Кнута-Морриса-Пратта.

Комбинированный алгоритм также показывает лучшие результаты по количеству требуемых сдвигов по сравнению с алгоритмом Боуера-Мура, хотя здесь превосходство выражено не столь сильно, как превосходство комбинированного алгоритма над алгоритмом КнутаМорриса-Пратта.

–  –  –

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

Благодарность Авторы выражают благодарность доценту Ahmad Hassanat, Mu’tah University, Jordan за консультации при изучении алгоритмов поиска образа в строке.

Список литературы [1] Wirth N. Algorithms and Data Structures. Prentice Hall, NJ, 1985.

[2] Faro S., Lecroq T. The exact online string matching problem: A review of the most recent results, ACM Computing Surveys, 2013, 45(2).

[3] Ahmed M., Kaykobad M., Chowdhury R.A. A new string matching algorithm, International Journal of Computer Mathematics, 2003, 80(7), 825–834.

[4] Lecroq T. Fast exact string matching algorithms, Information Processing Letters, 2007, 102(6), 229-235.

[5] Baeza-Yates R.A., Gonnet G.H. A new approach to text searching, Communications of the ACM, 1992, 35(10), 74–82.

[6] Fredriksson K., Grabowski S. Practical and optimal string matching, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2005, 3772 LNCS, 376-387.

[7] He L., Fang B., Sui J. The wide window string matching algorithm, Theoretical Computer Science, 2005, 332(1-3), 391-404.

[8] Hudaib A., Al-Khalid R., Suleiman D., Itriq M., Al-Anani A. A fast pattern matching algorithm with Two Sliding Windows (TSW), Journal of Computer Science, 2008, 4(5), 393-401.

[9] Knuth D., Morris J.H., Pratt V. Fast pattern matching in strings, SIAM Journal on Computing, 1977, 6(2), 323–350.

[10] Boyer R.S., Moore J.S. A fast string searching algorithm, Communications of the ACM, 1977,




Похожие работы:

«Обзор решений Страница Microsoft Desktop Virtualization Обзор решений Microsoft Desktop Virtualization Многие организации переходят на ОС Windows 7 и рассматривают это как возможность поновому взглянуть на способы размещения и управления своими настольными ПК. Эти организации стремятс...»

«Печатное средство массовой информации Комсомольского сельсовета Тамбовского района Тамбовской области ИНФОРМАЦИОННЫЙ БЮЛЛЕТЕНЬ 11 декабря 2015 года № 29 Информация для населения: 1. Информационное письмо администрация Комсомольского сельсовета Тамбовского района Тамбовской области.2. Договор публи...»

«Программа ввода в строй и РИ-502-034 допуска к самостоятельной работе кандидатов на должность старших бортпроводников Департамент обслуживания на борту Стр. 1 из 9 СОГЛАСОВАНО УТВЕРЖДЕНА Начальником отдела сертификации и Начальником управления лицензирования департамента управления лётной эксплу...»

«Google Web Toolkit Принимая на себя страдания Ajax Эдд Бернед Содержание 1. Вступление 1.1. Жизнь до появления GWT 1.2. Что GWT делает для нас 1.3. О книге 2. Начало работы 2.1. Поддерживаемые платформы 2.2. Установка 2.3. Создание сценариев запуска 2.4. Запуск и отладка 3. Hosted и Web режимы 3.1. Hosted режим 3.2. Web-режим 3.3...»

«НГУ ТОП-100 Проекты СИ 4 Формы документов Формы документов Уважаемые представители лабораторий, при личном обращении в службы НГУ, пожалуйста, соблюдайте часы, отведенные для приема посетителей: с 14:00 до 17:00 в рабочие дни. Смета расходов Выплаты Ежемесячная надбавка Разовая премия Пояснения о начислении выплат Закупк...»

«ОБЪЯВЛЕНИЕ ОБ ЭЛЕКТРОННЫХ ЗАКУПКАХ СПОСОБОМ ЗАПРОС ЦЕНОВЫХ ПРЕДЛОЖЕНИЙ N:139467 1. в лице "Восточные МЭС" (наименование заказчика) объявляет о проведении электронных закупок способом запроса ценовых предложений Паста для чистки изоляций среди ОТП (наименование закупки) 2. Перечень лотов №...»

«Средства для стайлинга волос из Японии GATSBY Gatsby — это культовый косметический бренд, запущенный компанией Mandom в 1978 году. Чтобы соответствовать постоянно меняющимся потребительским предпочтениям, за 30 с лишним лет обновление бренда Gatsby,...»

«"УТВЕРЖДЕНО" СОГЛАСОВАНО Приказом № ЗН 2611/12-1 от "26" ноября 2012г. Специализированным депозитарием Генеральный директор Открытое акционерное общество Объединенный ЗАО "Управляющая компания "Основа" специализированный депозитарий /_...»

«ОТЧЕТ Сравнение показателей безопасности полетов гражданской авиации в России, ИКАО и США В настоящей работе оценка уровня безопасности полетов проведена: по количеству катастроф на 100 тыс. часов налета одного и того же класса воздушных судов – самолетов взлетной массой более 10...»








 
2017 www.book.lib-i.ru - «Бесплатная электронная библиотека - электронные ресурсы»

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