Research Article Open Access

A Fast Approximate String Searching Algorithm

Mahmoud Mhashi1, Adnan Rawashdeh1 and Awni Hammouri1
  • 1 ,
Journal of Computer Science
Volume 1 No. 3, 2005, 405-412

DOI: https://doi.org/10.3844/jcssp.2005.405.412

Submitted On: 16 February 2005 Published On: 30 September 2005

How to Cite: Mhashi, M., Rawashdeh, A. & Hammouri, A. (2005). A Fast Approximate String Searching Algorithm. Journal of Computer Science, 1(3), 405-412. https://doi.org/10.3844/jcssp.2005.405.412

Abstract

In both approximate and exact string searching algorithms, the shift distance at the skipping step plays a major role in the performance of string matching algorithms. A new algorithm called the Modified Character-Weight Algorithm (MWA) has been developed to test the effect of the shift distance on the performance of approximate string matching. An experiment was performed comparing the performance of the MWA with that of Mhashi’s Character-Weight Algorithm (WA) using English text of size 1,005,077 characters. Using the average number of comparisons and the clock time as evaluation criteria, the MWA algorithm used only about 4% to 15% as many comparisons as the WA algorithm and about 10% to 35% of the clock time.

  • 1,286 Views
  • 1,558 Downloads
  • 0 Citations

Download

Keywords

  • Approximate String Matching
  • Searching
  • Shift Distance
  • Condition Types
  • Character Access