An efficient pruning strategy for approximate string matching over suffix tree

详细信息    查看全文

• 作者：Huan Hu ; Hongzhi Wang ; Jianzhong Li ; Hong Gao
• 关键词：Approximate string matching ; Suffix tree ; Depth ; first ; Backtracking ; Dynamic programming ; Bit ; parallelism
• 刊名：Knowledge and Information Systems
• 出版年：2016
• 出版时间：October 2016
• 年：2016
• 卷：49
• 期：1
• 页码：121-141
• 全文大小：991 KB
• 刊物类别：Computer Science
• 刊物主题：Information Systems and Communication Service
  Business Information Systems
  
• 出版者：Springer London
• ISSN：0219-3116
• 卷排序：49

文摘

Approximate string matching over suffix tree with depth-first search (ASM_ST_DFS), a classical algorithm in the field of approximate string matching, was originally proposed by Ricardo A. Baeza-Yates and Gaston H. Gonnet in 1990. The algorithm is one of the most excellent algorithms for approximate string matching if combined with other indexing techniques. However, its time complexity is sensitive to the length of pattern string because it searches \(m+k\) characters on each path from the root before backtracking. In this paper, we propose an efficient pruning strategy to solve this problem. We prove its correctness and efficiency in theory. Particularly, we proved that if the pruning strategy is adopted, it averagely searches O(k) characters on each path before backtracking instead of O(m). Considering each internal node of suffix tree has multiple branches, the pruning strategy should work very well. We also experimentally show that when k is much smaller than m, the efficiency improves hundreds of times, and when k is not much smaller than m, it is still several times faster. This is the first paper that tries to solve the backtracking problem of ASM_ST_DFS in both theory and practice.