A New Linear-Time Dynamic Dictionary Matching Algorithm
Keywords:
Dynamic dictionary matching, static dictionary matching, multiple pattern string matching, inverted index, inverted lists, trie, bit-parallel, hashing tableAbstract
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.Downloads
Download data is not yet available.
Downloads
Published
2014-01-20
How to Cite
Khancome, C., & Boonjing, V. (2014). A New Linear-Time Dynamic Dictionary Matching Algorithm. Computing and Informatics, 32(5), 897–923. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/1998
Issue
Section
Articles