Vybrané partie z dátových štruktúr
2-INF-237, LS 2016/17
Vyhľadávanie vzorky v texte: Rozdiel medzi revíziami
(Vytvorená stránka „==Literatúra== * Dan Gusfield (1997) [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521585198 Algorithms on Strings, Trees and Sequences: Computer Science a...“) |
|||
| Riadok 1: | Riadok 1: | ||
| + | ==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 <math>(\log n)^{O(1/\epsilon)}</math> approximation in <math>n^{1+\epsilon}</math> time | ||
| + | |||
| + | Source: Andoni A, Krauthgamer R, Onak K. Polylogarithmic approximation for edit distance and the asymmetric query complexity. FOCS2010, pp. 377-386 [http://web.mit.edu/andoni/www/papers/editQuery-focs.pdf] | ||
| + | |||
| + | Conditional lower bound: If the edit distance can be computed in <math>O(n^{2-\delta})</math> for some constant δ > 0, then the satisfiability of conjunctive normal form (CNF) formulas with N variables and M clauses can be solved in time <math>M^{O(1)}2^{(1-\epsilon)N}</math> for a constant <math>\epsilon > | ||
| + | 0</math>, 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 [http://arxiv.org/pdf/1412.0348v2.pdf] | ||
| + | |||
| + | |||
| + | |||
==Literatúra== | ==Literatúra== | ||
* Dan Gusfield (1997) [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521585198 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. | * Dan Gusfield (1997) [http://www.cambridge.org/uk/catalogue/catalogue.asp?isbn=0521585198 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 [http://compbio.fmph.uniba.sk/vyuka/vvt/poznamky/main-2013-05-20.pdf] (zčasti písané študentami a nedokončené) | * Poznámky z predmetu Vyhľadávanie v texte [http://compbio.fmph.uniba.sk/vyuka/vvt/poznamky/main-2013-05-20.pdf] (zčasti písané študentami a nedokončené) | ||
Verzia zo dňa a času 18:18, 4. apríl 2016
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 
approximation in 
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 
for some constant δ > 0, then the satisfiability of conjunctive normal form (CNF) formulas with N variables and M clauses can be solved in time 
for a constant 
, 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é)
