This research presents inverted lists as a new data structure for the dynamic dictionary matching algorithm. The inverted lists structure, which derives from the inverted index, is implemented by the perfect hashing table. The dictionary is constructed in optimal time and the individual patterns can be updated in minimal time. The searching phase scans the given text in a single pass, even in a worst case scenario. In experimental results, the inverted lists used less time and space than the traditional structures; the searches were processed and showed an efficient linear time.
@article{cai1998,
author = {Chouvalit Khancome; Software Systems Engineering Laboratory, Department of Mathematics and Computer Science, Faculty of Science, King Monkut\'{}s Institute of Technology at Ladkrabang, Bangkok and Veera Boonjing; Software Systems Engineering Laboratory, Department of Mathematics and Computer Science, Faculty of Science, King Monkut\'{}s Institute of Technology at Ladkrabang, Bangkok},
title = {A New Linear-Time Dynamic Dictionary Matching Algorithm},
journal = {Computing and Informatics},
volume = {31},
number = {6},
year = {2013},
language = {en},
url = {http://dml.mathdoc.fr/item/cai1998}
}
Chouvalit Khancome; Software Systems Engineering Laboratory, Department of Mathematics and Computer Science, Faculty of Science, King Monkut´s Institute of Technology at Ladkrabang, Bangkok; Veera Boonjing; Software Systems Engineering Laboratory, Department of Mathematics and Computer Science, Faculty of Science, King Monkut´s Institute of Technology at Ladkrabang, Bangkok. A New Linear-Time Dynamic Dictionary Matching Algorithm. Computing and Informatics, Tome 31 (2013) no. 6, . http://gdmltest.u-ga.fr/item/cai1998/