A New Linear-Time Dynamic Dictionary Matching Algorithm

In: Computing and Informatics, vol. 32, no. 5

Ch. Khancome - V. Boonjing

Details:

Year, pages: 2013, 897 - 923

Keywords:

Dynamic dictionary matching, static dictionary matching, multiple pattern string matching, inverted index, inverted lists, trie, bit-parallel, hashing table

About article:

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.

How to cite:

ISO 690:

Khancome, C., Boonjing, V. 2013. A New Linear-Time Dynamic Dictionary Matching Algorithm. In Computing and Informatics, vol. 32, no.5, pp. 897-923. 1335-9150.

APA:

Khancome, C., Boonjing, V. (2013). A New Linear-Time Dynamic Dictionary Matching Algorithm. Computing and Informatics, 32(5), 897-923. 1335-9150.