A New Linear-Time Dynamic Dictionary Matching Algorithm

Authors

  • 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

Keywords:

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

Abstract

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