Vyhľadávanie vzorky v texte

Theoretical results for edit distance computation

Exact algorithm O(mn) or improved by logarithimc factor.

Approximation algorithm: For strings of length n and every fixed ε > 0 compute $(\log n)^{{O(1/\epsilon )}}$ approximation in $n^{{1+\epsilon }}$ time

Source: Andoni A, Krauthgamer R, Onak K. Polylogarithmic approximation for edit distance and the asymmetric query complexity. FOCS2010, pp. 377-386 [1]

Conditional lower bound: If the edit distance can be computed in $O(n^{{2-\delta }})$ for some constant δ > 0, then the satisfiability of conjunctive normal form (CNF) formulas with N variables and M clauses can be solved in time $M^{{O(1)}}2^{{(1-\epsilon )N}}$ for a constant $\epsilon >0$, which would violate Strong Exponential Time Hypothesis (SETH).

Source: Backurs A, Indyk P. Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). STOC2015, pp. 51-58 [2]

Literatúra

• Dan Gusfield (1997) Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press. Prezenčne v knižnici so signatúrou I-INF-G-8.
• Poznámky z predmetu Vyhľadávanie v texte [3] (zčasti písané študentami a nedokončené)