Pattern matching by the terms of cache memory limitations
Тип публікації :
Стаття
Дата випуску :
2019
Автор(и) :
Zavadskyi, I. O.
Мова основного тексту :
Англійська
eKNUTSHIR URL :
Випуск :
3
ISSN :
1812-5409
Початкова сторінка :
56
Кінцева сторінка :
59
Цитування :
[APA 7] Zavadskyi, I. O. (2019). Pattern matching by the terms of cache memory limitations. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics, (3), 56–59. https://doi.org/10.17721/1812-5409.2019/3.8
[ДСТУ] Zavadskyi I. O. Pattern matching by the terms of cache memory limitations. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics. 2019. no. 3. P. 56—59. DOI: 10.17721/1812-5409.2019/3.8 (date of access: 25.07.2026).
A few known techniques of exact pattern matching, such as 2-byte read, skip loop, and sliding search windows, are improved and applied to pattern matching algorithms, performing over 256-ary alphabets. Instead of 2-byte read, we offer “1.5-byte read”, i.e. reading more than 8 but less than 16 bits of two sequential bytes of a text at each iteration of a search loop. This allows us to fit the search table into L1 cache memory, which significantly improves the algorithm performance. Also, we introduce the so-called double skip loop instead of single one, resolve problems caused by endianness of a machine, and adopt the sliding windows technique to our algorithms. The experimental results averaged over 500 runs of algorithms on 40 different computers show that our algorithms outperform all other tested methods for all tested pattern lengths.Key words: pattern matching, Boyer-Moore-Horspool, fast search, text search, sliding windows.Pages of the article in the issue: 56 - 59Language of the article: Ukrainian
Файл(и) :![Ескіз]()
Вантажиться...
Формат :
Adobe PDF
Розмір :
1.06 MB
Контрольна сума :
(MD5):1d12a994517f420bf244c523ea05aa5c
Якщо не вказано інше, ця робота розповсюджується на умовах ліцензії Creative Commons Attribution 4.0 International