Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Approximate Swap and Mismatch Edit Distance
verfasst von : Yair Dombb, Ohad Lipsky, Benny Porat, Ely Porat, Asaf Tsur
Erschienen in: String Processing and Information Retrieval
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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(\frac{1}{\epsilon^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(n\sqrt{m} \log m)$
.
In this paper, we discuss the problem of
approximate edit distance with swap and mismatch
. We show a randomized
$O(\frac{1}{\epsilon^3}n \log n \log^3 m)$
time algorithm for the problem. The algorithm guarantees an approximation factor of (1 +
ε
) with probability of at least
$1-\frac{1}{n}$
.