Fast and flexible packed string matching

Basit Öğe Kaydı
dc.authorid0000-0002-4583-6261
dc.contributor.authorFaro, Simone
dc.contributor.authorKülekci, Muhammed O?uzhan
dc.date.accessioned10.07.201910:49:13
dc.date.accessioned2019-07-10T19:36:31Z
dc.date.available10.07.201910:49:14
dc.date.available2019-07-10T19:36:31Z
dc.date.issued2014
dc.departmentİstanbul Medipol Üniversitesi, Mühendislik ve Doğa Bilimleri Fakültesi, Biyomedikal Mühendisliği Bölümü
dc.description.abstractSearching for all occurrences of a pattern in a text is a fundamental problem in computer science with applications in many other fields, like natural language processing, information retrieval and computational biology. In the last two decades a general trend has appeared trying to exploit the power of the word RAM model to speed-up the performances of classical string matching algorithms. In this model an algorithm operates on words of length w, grouping blocks of characters, and arithmetic and logic operations on the words take one unit of time. In this paper we use specialized word-size packed string matching instructions, based on the Intel streaming SIMD extensions (SSE) technology, to design a very fast string matching algorithm. We evaluate our solution in terms of efficiency, stability and flexibility, where we propose to use the deviation in running time of an algorithm on distinct equal length patterns as a measure of stability. From our experimental results it turns out that, despite their quadratic worst case time complexity, the new presented algorithm becomes the clear winner on the average in many cases, when compared against the most recent and effective algorithms known in literature.
dc.identifier.citationFaro, S. ve Külekci, M. O. (2014). Fast and flexible packed string matching. Journal of Discrete Algorithms, 28, 61-72. https://dx.doi.org/10.1016/j.jda.2014.07.003
dc.identifier.doi10.1016/j.jda.2014.07.003
dc.identifier.endpage72
dc.identifier.issn1570-8667
dc.identifier.scopusqualityQ3
dc.identifier.startpage61
dc.identifier.urihttps://hdl.handle.net/20.500.12511/1184
dc.identifier.urihttps://dx.doi.org/10.1016/j.jda.2014.07.003
dc.identifier.volume28
dc.identifier.wosqualityN/A
dc.indekslendigikaynakWeb of Science
dc.indekslendigikaynakScopus
dc.language.isoen
dc.publisherElsevier
dc.relation.ispartofJournal of Discrete Algorithmsen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı
dc.rightsinfo:eu-repo/semantics/openAccess
dc.subjectExact String Matching
dc.subjectExperimental Algorithms
dc.subjectInformation Retrieval
dc.subjectOnline Searching
dc.subjectText Algorithms
dc.titleFast and flexible packed string matching
dc.typeArticle

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim
İsim:
Külekci, Muhammed Oǧuzhan-2014.pdf
Boyut:
401.61 KB
Biçim:
Adobe Portable Document Format
Açıklama:
Tam Metin / Full Text
İndir

Koleksiyon

Scopus İndeksli Yayınlar Koleksiyonu
Makale Koleksiyonu
WoS İndeksli Yayınlar Koleksiyonu