Error Tree: A Tree Structure for Hamming & Edit Distances & Wildcards Matching

Abstract

Error Tree is a novel tree structure that is mainly oriented to solve the approximate pattern matching problems, Hamming and edit distances, as well as the wildcards matching problem. The input is a text of length $n$ over a fixed alphabet of length $\Sigma$, a pattern of length $m$, and $k$. The output is to find all positions that have $\le$ $k$ Hamming distance, edit distance, or wildcards matching with $P$. The algorithm proposes for Hamming distance and wildcards matching a tree structure that needs $O(n\frac{lo{g}_{\Sigma }^{k}n}{k!})$ words and takes $O(\frac{m^k}{k!}+occ$)($O(m+\frac{lo{g}_{\Sigma }^{k}n}{k!}+occ$) in the average case) of query time for any online/offline pattern, where $occ$ is the number of outputs. As well, a tree structure of $O(2^{k}n\frac{lo{g}_{\Sigma }^{k}n}{k!})$ words and $O(\frac{m^k}{k!}+3^{k}occ$)($O(m+\frac{lo{g}_{\Sigma }^{k}n}{k!}+3^{k}occ$) in the average case) query time for edit distance for any online/offline pattern.