A family of fast constant-space substring search algorithms

Hakonen Harri and Raita Timo: A family of fast constant-space substring search algorithms. In: Acta cybernetica, (14) 2. pp. 239-250. (1999)

[thumbnail of cybernetica_014_numb_002_239-250.pdf]
Cikk, tanulmány, mű

Download (972kB) | Preview


This paper describes a new strategy for searching a substring in a given text. The method is based on the well-known Boyer-Moore algorithm complementing it with a technique called q-slicing, a form of probabilistic 5-gram matching. As a result, we get a family of highly parametric algorithms apt for adaptation to the special properties inherent to the source which generates the input strings. The search procedure is independent of the alphabet size and appropriate for efficient and practical on-line implementations. Simulation results show that they are comparable to the fastest currently known Boyer-Moore variants.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 1999
Volume: 14
Number: 2
ISSN: 0324-721X
Page Range: pp. 239-250
Language: English
Place of Publication: Szeged
Event Title: Conference for PhD Students in Computer Science (1.) (1998) (Szeged)
Related URLs: http://acta.bibl.u-szeged.hu/38508/
Uncontrolled Keywords: Számítástechnika, Kibernetika, Algoritmus
Additional Information: Bibliogr.: p. 249-250. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:26
Last Modified: 2022. Jun. 14. 08:43
URI: http://acta.bibl.u-szeged.hu/id/eprint/12624

Actions (login required)

View Item View Item