ПРИСКОРЕНИЙ АЛГОРИТМ ПОШУКУ СЛІВ-ОБРАЗІВ У ТЕКСТІ З АДАПТИВНОЮ ДЕКОМПОЗИЦІЄЮ ВИХІДНИХ ДАНИХ
DOI:
https://doi.org/10.26906/SUNZ.2019.4.028Ключові слова:
слово-образ, розпаралелювання, високопродуктивна обчислювальна система, алгоритм Бойєра-МураАнотація
Алгоритми пошуку слів-образів у тексті мають широке застосування - контекстний пошук у базах та банках даних, бібліографічний пошук, пошук фрагменту тексту та його заміна при редагуванні тексту, у задачах стиску даних, алгоритмах прогнозування тощо, що зумовлює актуальність розробки нових алгоритмів, а також вдосконалення та адаптацію існуючих алгоритмів для реалізації на високопродуктивних обчислювачах. Мета дослідження – модифікація алгоритму Бойєра-Мура пошуку слів-образів у тексті для досягнення скорочення часу пошуку тексту завдяки використанню методів паралельних обчислень та декомпозиції вихідних даних. Результати та висновки. В ході роботи вдосконалено існуючий алгоритм Бойєра-Мура пошуку слів-образів у тексті завдяки використанню методів паралельних обчислень та декомпозиції вихідних даних, що призвело до скорочення часу пошуку слів-образів у текстах великого обсягу. Виконано огляд існуючих алгоритмів пошуку слів-образів у тексті, який показав найнижчу трудомісткість алгоритму Бойєра-Мура. Розроблено дві прискорені модифікації алгоритму Бойєра-Мура з простою та адаптивною декомпозицією даних. Аналіз результатів яких показав, що кількість помилкових спрацьовувань при адаптивній декомпозиції прагне до 0, на відміну від простої декомпозиції вхідних даних. Аналіз часу виконання алгоритмів показав, що на маленьких обсягах вихідного тексту, використання паралельних технологій для систем із загальною пам’яттю не є виправданим, оскільки часу на породження паралельних потоків витрачається більше, аніж на компаративні операції.Завантаження
Посилання
Левин М.П. Параллельное программирование с использованием OpenMP / М.П. Левин. – БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий, 2008. – 120с.
Антонов А.С. Параллельное программирование с использованием технологии OpenMP. – М.: МГУ, 2009. – 77 с.
Эндрюс Г. Р. Основы многопоточного, параллельного и распределенного программирования / Г.Р. Эндрюс. – М.: Издательский дом "Вильямс", 2003. – 512 с.
Миллер Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер. – БИНОМ. Лаборатория знаний, 2006. – 406 с.
V. Kharchenko, A. Kovalenko, O. Siora, V. Sklyar, "Security assessment of FPGA-based safety-critical systems: US NRC requirements context", Proceedings of IEEE Information and Digital Technologies Conference (IDT), pp. 132-138, July 2015. DOI: http://doi.org/10.1109/DT.2015.7222963
Kuchuk G., Kovalenko A., Komari I.E., Svyrydov A., Kharchenko V. Improving big data centers energy efficiency: Traffic based model and method. Studies in Systems, Decision and Control, vol 171. Kharchenko, V., Kondratenko, Y., Kacprzyk, J. (Eds.). Springer Nature Switzerland AG, 2019. Pp. 161-183. DOI: http://doi.org/10.1007/978-3-030-00253-4_8
Kharchenko, V., Illiashenko, O., Kovalenko, A., Sklyar, V., Boyarchuk, A. Security informed safety assessment of NPP I&C systems: GAP-IMECA technique. Proc. 22th Int. Conf. on Nuclear Engineering (ICONE), Prague, Republic, 7-11 Jul. 2014, pp. 1-9. doi: http://doi.org/10.1115/ICONE22-31175.
Кучук Г.А. Метод мінімізації середньої затримки пакетів у віртуальних з’єднаннях мережі підтримки хмарного сервісу / Г.А. Кучук, А.А. Коваленко, Н.В. Лукова-Чуйко // Системи управління, навігації та зв’язку. – Полтава . ПНТУ, 2017. – Вип. 2(42). – С. 117-120.
Z. Xiong, "A Composite Boyer-Moore Algorithm for the String Matching Problem," 2010 International Conferenceon Parallel and Distributed Computing, Applicationsand Technologies, Wuhan, 2010, pp. 492-496.doi: 10.1109/PDCAT.2010.58
A. Domínguez, P. P. Carballoand A. Núñez, "Programmable SoC platform for deep packet inspection using enhanced BoyerMoore algorithm," 2017 12th International Symposiumon Reconfigurable Communication-centric Systems-on-Chip (ReCoSoC), Madrid, 2017, pp. 1-8. doi: 10.1109/ReCoSoC.2017.8016159
Y. Jeong, M. Lee, D. Nam, J. Kimand S. Hwang, "High Performance Parallelization of Boyer-Moore Algorithmon ManyCore Accelerators," 2014 International Conference on Cloud and Autonomic Computing, London, 2014, pp. 265-272. doi: 10.1109/ICCAC.2014.20
X. Zhaand S. Sahni, "GPU-to-GPU and Host-to-Host Multipattern String Matching on a GPU," in IEEE Transactionson Computers, vol. 62, no. 6, pp. 1156-1169, June 2013. doi: 10.1109/TC.2012.61
V. Gupta, M. Singhand V. K. Bhalla, "Pattern matching algorithms for intrusion detection and prevention system: A comparative analysis," 2014 International Conferenceon Advancesin Computing, Communications and Informatics (ICACCI), NewDelhi, 2014, pp. 50-54. doi: 10.1109/ICACCI.2014.6968595
Y. Wangand H. Kobayashi, "AnImproved Technology for Content Matching Intrusion Detection System," 2006 Int. Conf. on Software in Telecommunications and Computer Networks, Split, 2006, pp. 238-241. doi: 10.1109/SOFTCOM.2006.329755
V. R. Krishna and P. V. Kumar, "Optimal pattern search for sequence databases," 2010 3rd Int. Conf. on Advanced Computer Theory and Engineering (ICACTE), Chengdu, 2010, pp. V2-654-V2-658. doi: 10.1109/ICACTE.2010.5579518
P. Lin, S. Liu, L. Zhangand P. Huang, "Compressed Patter nMatchingin DNA Sequences Using Multithreaded Technology," 2009 3rd International Conference on Bioinformatics and Biomedical Engineering, Beijing, 2009, pp. 1-4. doi: 10.1109/ICBBE.2009.5162550
