A family of fast constant-space substring search algorithms

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

Előnézet

Cikk, tanulmány, mű cybernetica_014_numb_002_239-250.pdf Letöltés (972kB) | Előnézet

Absztrakt (kivonat)

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.

Mű típusa:	Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe:	Acta cybernetica
Dátum:	1999
Kötet:	14
Szám:	2
ISSN:	0324-721X
Oldalak:	pp. 239-250
Nyelv:	angol
Kiadás helye:	Szeged
Konferencia neve:	Conference for PhD Students in Computer Science (1.) (1998) (Szeged)
Befoglaló mű URL:	http://acta.bibl.u-szeged.hu/38508/
Kulcsszavak:	Számítástechnika, Kibernetika, Algoritmus
Megjegyzések:	Bibliogr.: p. 249-250. ; összefoglalás angol nyelven
Szakterület:	01. Természettudományok 01. Természettudományok > 01.02. Számítás- és információtudomány
Feltöltés dátuma:	2016. okt. 15. 12:26
Utolsó módosítás:	2022. jún. 14. 08:43
URI:	http://acta.bibl.u-szeged.hu/id/eprint/12624

Bővebben:

Tétel nézet