A new approach to the edit distance with block swaps using DAWG
Phuoc-Hoang-Tuong-Lan Do, Sung‐Ryul Kim · 2015
Edit Distance with Block Swaps is an idea that used to improve the efficiency of the Edit Distance algorithm. A version of this method was introduced by Davuth and Kim, in that paper the blocks are found by seeking the diagonal and cut point by a look-up table. The limit of this method is that it only supports up to three blocks and the theoretic running time for finding the blocks in the worst case is quadratic. In this paper, we use the directed acyclic word graph (DAWG) to find the blocks in a linear time. And with unlimited block supported, we have a better approximate comparison for strings that are seem to be similar in the meaning but different when using Edit Distance. We also suggest several data structures to deal with the blocks in term of intervals processing. Moreover, we propose some methods to estimate the efficiency of the swapping method. Our experiment on the Snort rule set also shows that with the DAWG applied, the number of compared rules is reduced dramatically.