Комбинированный алгоритм поиска образа в строке
Автор: Царев Р.Ю., Царева Е.А., Черниговский А.С.
Журнал: Журнал Сибирского федерального университета. Серия: Техника и технологии @technologies-sfu
Статья в выпуске: 1 т.10, 2017 года.
Бесплатный доступ
Проблема поиска образа в строке является классической задачей обработки данных. Несмотря на ряд существующих алгоритмов решения задачи, работа в этом направлении продолжается. Предложенный алгоритм развивает теоретические основы задачи поиска образа в строке, комбинируя алгоритмы двух разных классов с прямым и обратным проходом образа, а именно алгоритмы Кнута-Морриса-Пратта и Боуера-Мура. В статье приведен анализ работы предложенного комбинированного алгоритма и сравнение результатов его работы с базовыми алгоритмами, подтверждающее эффективность комбинированного алгоритма поиска образа в строке.
Образ, поиск, обработка данных, комбинированный алгоритм
Короткий адрес: https://sciup.org/146115174
IDR: 146115174 | DOI: 10.17516/1999-494X-2017-10-1-126-135
Список литературы Комбинированный алгоритм поиска образа в строке
- 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.
