Published January 1, 2017
| Version v1
Publication
Open
Multithreaded Sliding Window Approach to Improve Exact Pattern Matching Algorithms
- 1. University of Jordan
- 2. Hashemite University
Description
In this paper an efficient pattern matching approach, based on a multithreading sliding window technique, is proposed to improve the efficiency of the common sequential exact pattern matching algorithms including: (i) Brute Force, (ii) Knuth-Morris-Pratt and (iii) Boyer-Moore.The idea is to divide the text under-search into blocks, each block is allocated one or two threads running concurrently.Reported experimental results indicated that the proposed approach improves the performance of the well-known pattern matching algorithms, in terms of search time, especially when the searched patterns are located at the middle or at the end of the text.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
في هذه الورقة، يُقترح نهج فعال لمطابقة الأنماط، يعتمد على تقنية النافذة المنزلقة متعددة الخيوط، لتحسين كفاءة خوارزميات مطابقة الأنماط الدقيقة المتسلسلة الشائعة بما في ذلك: (1) القوة الغاشمة، (2) كنوث موريس برات و (3) بوير مور. الفكرة هي تقسيم النص قيد البحث إلى كتل، يتم تخصيص كل كتلة واحدة أو سلسلتين تعملان بشكل متزامن. أشارت النتائج التجريبية المبلغ عنها إلى أن النهج المقترح يحسن أداء خوارزميات مطابقة الأنماط المعروفة، من حيث وقت البحث، خاصة عندما تقع الأنماط التي تم البحث عنها في منتصف النص أو في نهايته.Translated Description (French)
Dans cet article, une approche de correspondance de motifs efficace, basée sur une technique de fenêtre glissante multithreading, est proposée pour améliorer l'efficacité des algorithmes de correspondance de motifs exacts séquentiels communs, notamment : (i) Brute Force, (ii) Knuth-Morris-Pratt et (iii) Boyer-Moore. L'idée est de diviser le texte sous-recherché en blocs, chaque bloc se voyant attribuer un ou deux threads fonctionnant simultanément. Les résultats expérimentaux rapportés ont indiqué que l'approche proposée améliore les performances des algorithmes de correspondance de motifs bien connus, en termes de temps de recherche, en particulier lorsque les motifs recherchés sont situés au milieu ou à la fin du texte.Translated Description (Spanish)
En este documento se propone un enfoque eficiente de coincidencia de patrones, basado en una técnica de ventana deslizante de subprocesos múltiples, para mejorar la eficiencia de los algoritmos comunes de coincidencia de patrones exactos secuenciales que incluyen: (i) Fuerza bruta, (ii) Knuth-Morris-Pratt y (iii) Boyer-Moore. La idea es dividir el texto bajo la búsqueda en bloques, a cada bloque se le asigna uno o dos subprocesos que se ejecutan simultáneamente. Los resultados experimentales informados indicaron que el enfoque propuesto mejora el rendimiento de los algoritmos de coincidencia de patrones bien conocidos, en términos de tiempo de búsqueda, especialmente cuando los patrones buscados se encuentran en el medio o al final del texto.Files
Paper_55-Multithreaded_Sliding_Window_Approach.pdf.pdf
Files
(1.2 MB)
| Name | Size | Download all |
|---|---|---|
|
md5:da1bc29a9a0f36154e7a0b2cfb0efdfe
|
1.2 MB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- نهج النافذة المنزلقة متعددة الخيوط لتحسين خوارزميات مطابقة الأنماط الدقيقة
- Translated title (French)
- Approche de fenêtre coulissante multifilière pour améliorer les algorithmes de correspondance de motifs exacts
- Translated title (Spanish)
- Enfoque de ventana deslizante de subprocesos múltiples para mejorar los algoritmos de coincidencia de patrones exactos
Identifiers
- Other
- https://openalex.org/W2585130792
- DOI
- 10.14569/ijacsa.2017.080155