Комбинированный алгоритм поиска образа в строке
Автор: Царев Р.Ю., Царева Е.А., Черниговский А.С.
Журнал: Журнал Сибирского федерального университета. Серия: Техника и технологии @technologies-sfu
Статья в выпуске: 1 т.10, 2017 года.
Бесплатный доступ
Проблема поиска образа в строке является классической задачей обработки данных. Несмотря на ряд существующих алгоритмов решения задачи, работа в этом направлении продолжается. Предложенный алгоритм развивает теоретические основы задачи поиска образа в строке, комбинируя алгоритмы двух разных классов с прямым и обратным проходом образа, а именно алгоритмы Кнута-Морриса-Пратта и Боуера-Мура. В статье приведен анализ работы предложенного комбинированного алгоритма и сравнение результатов его работы с базовыми алгоритмами, подтверждающее эффективность комбинированного алгоритма поиска образа в строке.
Образ, поиск, обработка данных, комбинированный алгоритм
Короткий адрес: https://sciup.org/146115174
IDR: 146115174 | УДК: 681.3.06 | DOI: 10.17516/1999-494X-2017-10-1-126-135
Combined string searching algorithm
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, confi rming the effi cacy of the combined string search algorithm.
Список литературы Комбинированный алгоритм поиска образа в строке
- Wirth N. Algorithms and Data Structures. Prentice Hall, NJ, 1985.
- Faro S., Lecroq T. The exact online string matching problem: A review of the most recent results, ACM Computing Surveys, 2013, 45(2).
- Ahmed M., Kaykobad M., Chowdhury R.A. A new string matching algorithm, International Journal of Computer Mathematics, 2003, 80(7), 825-834.
- Lecroq T. Fast exact string matching algorithms, Information Processing Letters, 2007, 102(6), 229-235.
- Baeza-Yates R.A., Gonnet G.H. A new approach to text searching, Communications of the ACM, 1992, 35(10), 74-82.
- 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.
- He L., Fang B., Sui J. The wide window string matching algorithm, Theoretical Computer Science, 2005, 332(1-3), 391-404.
- 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.
- Knuth D., Morris J.H., Pratt V. Fast pattern matching in strings, SIAM Journal on Computing, 1977, 6(2), 323-350.
- Boyer R.S., Moore J.S. A fast string searching algorithm, Communications of the ACM, 1977, 20(10), 762-772.
