Start Submission Become a Reviewer

Reading: Average time complexity analysis of Commentz-Walter algorithm

Download

A- A+
Alt. Display

Research Articles

Average time complexity analysis of Commentz-Walter algorithm

Authors:

SD Dewasurendra,

University of Peradeniya, LK
About SD

Department of Computer Engineering

 

X close

SM Vidanagamachchi

University of Ruhuna, LK
About SM

Department of Computer Science

 

X close

Abstract

The Commentz-Walter algorithm provides a suffix-based, exact multiple string matching procedure that combines the ideas of both Aho-Corasick and Boyer-Moore string matching algorithms. Aho-Corasick algorithm is known as the fastest exact multiple string matching algorithm with linear worst case time complexity, and Boyer-Moore algorithm utilises a shift based approach in handling mismatches in the matching phase to obtain a usually sub linear time complexity. Due to the complexity of the Commentz-Walter algorithm, a systematic and a comprehensive time complexity analysis has not yet been reported in the literature. In this article, a comprehensive average time complexity analysis of Commentz Walter algorithm is presented and it is used to formally explain empirical results reported elsewhere for exact and limited tolerance string matching. Performance analysis model permits ‘complete’ exploration of the solution space of Commentz-Walter with respect to all relevant parameters. The models developed here could be useful for other researchers to investigate the appropriateness of Commentz-Walter to specific application domains. The analysis method can be extended to cover Aho-Corasick and other string matching algorithms without much difficulty.

How to Cite: Dewasurendra, S. and Vidanagamachchi, S., 2018. Average time complexity analysis of Commentz-Walter algorithm. Journal of the National Science Foundation of Sri Lanka, 46(4), pp.547–557. DOI: http://doi.org/10.4038/jnsfsr.v46i4.8630
Published on 31 Dec 2018.
Peer Reviewed

Downloads

  • PDF (EN)

    comments powered by Disqus