There is no known algorithm that solves the general case of the Approximate Edit Distance problem, where the edit operations are: insertion, deletion, mismatch, and swap, in time o(nm), where n is the length of the text and m is the length of the pattern. In the effort to study this problem, the edit operations were analyzed independently. Karloff [10] showed an algorithm that approximates the edit distance problem with only the mismatch operation in time O((1/(∈~2))n log~3 m). Amir et. Al. [3] showed that if the only edit operations allowed are swap and mismatch, then the exact edit distance problem can be solved in time O(nm~(1/2) log m). In this paper, we discuss the problem of approximate edit distance with swap and mismatch. We show a randomized O((1/(∈~3))n log~3 m) time algorithm for the problem. The algorithm guarantees an approximation factor of (1 + ∈) with probability of at least 1 -1.
展开▼
