ПРИСКОРЕНИЙ АЛГОРИТМ ПОШУКУ СЛІВ-ОБРАЗІВ У ТЕКСТІ З АДАПТИВНОЮ ДЕКОМПОЗИЦІЄЮ ВИХІДНИХ ДАНИХ
Ключові слова:
слово-образ, розпаралелювання, високопродуктивна обчислювальна система, алгоритм Бойєра-Мура
Анотація
Алгоритми пошуку слів-образів у тексті мають широке застосування - контекстний пошук у базах та банках даних, бібліографічний пошук, пошук фрагменту тексту та його заміна при редагуванні тексту, у задачах стиску даних, алгоритмах прогнозування тощо, що зумовлює актуальність розробки нових алгоритмів, а також вдосконалення та адаптацію існуючих алгоритмів для реалізації на високопродуктивних обчислювачах. Мета дослідження – модифікація алгоритму Бойєра-Мура пошуку слів-образів у тексті для досягнення скорочення часу пошуку тексту завдяки використанню методів паралельних обчислень та декомпозиції вихідних даних. Результати та висновки. В ході роботи вдосконалено існуючий алгоритм Бойєра-Мура пошуку слів-образів у тексті завдяки використанню методів паралельних обчислень та декомпозиції вихідних даних, що призвело до скорочення часу пошуку слів-образів у текстах великого обсягу. Виконано огляд існуючих алгоритмів пошуку слів-образів у тексті, який показав найнижчу трудомісткість алгоритму Бойєра-Мура. Розроблено дві прискорені модифікації алгоритму Бойєра-Мура з простою та адаптивною декомпозицією даних. Аналіз результатів яких показав, що кількість помилкових спрацьовувань при адаптивній декомпозиції прагне до 0, на відміну від простої декомпозиції вхідних даних. Аналіз часу виконання алгоритмів показав, що на маленьких обсягах вихідного тексту, використання паралельних технологій для систем із загальною пам’яттю не є виправданим, оскільки часу на породження паралельних потоків витрачається більше, аніж на компаративні операції.Завантаження
Дані про завантаження поки що недоступні.
Посилання
1. Левин М.П. Параллельное программирование с использованием OpenMP / М.П. Левин. – БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий, 2008. – 120с.
2. Антонов А.С. Параллельное программирование с использованием технологии OpenMP. – М.: МГУ, 2009. – 77 с.
3. Эндрюс Г. Р. Основы многопоточного, параллельного и распределенного программирования / Г.Р. Эндрюс. – М.: Издательский дом "Вильямс", 2003. – 512 с.
4. Миллер Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер. – БИНОМ. Лаборатория знаний, 2006. – 406 с.
5. 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
6. 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
7. 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.
8. Кучук Г.А. Метод мінімізації середньої затримки пакетів у віртуальних з’єднаннях мережі підтримки хмарного сервісу / Г.А. Кучук, А.А. Коваленко, Н.В. Лукова-Чуйко // Системи управління, навігації та зв’язку. – Полтава . ПНТУ, 2017. – Вип. 2(42). – С. 117-120.
9. 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
10. 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
11. 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
12. 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
13. 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
14. 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
15. 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
16. 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
2. Антонов А.С. Параллельное программирование с использованием технологии OpenMP. – М.: МГУ, 2009. – 77 с.
3. Эндрюс Г. Р. Основы многопоточного, параллельного и распределенного программирования / Г.Р. Эндрюс. – М.: Издательский дом "Вильямс", 2003. – 512 с.
4. Миллер Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер. – БИНОМ. Лаборатория знаний, 2006. – 406 с.
5. 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
6. 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
7. 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.
8. Кучук Г.А. Метод мінімізації середньої затримки пакетів у віртуальних з’єднаннях мережі підтримки хмарного сервісу / Г.А. Кучук, А.А. Коваленко, Н.В. Лукова-Чуйко // Системи управління, навігації та зв’язку. – Полтава . ПНТУ, 2017. – Вип. 2(42). – С. 117-120.
9. 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
10. 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
11. 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
12. 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
13. 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
14. 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
15. 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
16. 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
Опубліковано
2019-09-11
Як цитувати
BarkovskaО.Yu. Прискорений алгоритм пошуку слів-образів у тексті з адаптивною декомпозицією вихідних даних / BarkovskaО.Yu., D.I. Pyvovarova, V.S. Serdechnyi, LiashovaА.А. // Системи управління, навігації та зв’язку. Збірник наукових праць. – Полтава: ПНТУ, 2019. – Т. 4 (56). – С. 28-34. – doi:https://doi.org/10.26906/SUNZ.2019.4.028.
Розділ
Інформаційні технології
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
