Porovnávanie dátových súborov

Diplomová práca

Autor: Michal Linhard

Diplomový vedúci: Tibor Hegedus

Posledná zmena: 14. marec 2007

Náplňou mojej diplomovej práce je vývoj knižnice na vyhľadávanie maximálnych repeatov v reťazcoch. Stránka projektu diffengine je tu: http://michal.linhard.sk/diffengine/

Dokumenty

Názov Posledná zmena Link
Chapter 1 draft + overview 14. marec 2007 pdf
Chapter 2 draft 14. marec 2007 pdf
Chapter 3 draft 14. marec 2007 pdf
Prezentácia na predobhajoby 2. feb. 2007 pdf, odp
Tretia prezentácia pre diplomový seminár 29. nov. 2006 pdf, odp
R3 Štruktúra 21. nov. 2006 pdf, odt
Draft(kapitola 2,3) 3. okt. 2006 pdf
Contents draft 27. sept. 2006 pdf
Druhá prezentácia pre diplomový seminár 27. sept. 2006 pdf, odp
Implementation details 13. sept. 2006 pdf
Interval processing 13. sept. 2006 pdf
Definitions 13. sept. 2006 pdf
Stará verzia náčrtu diplomovky 5. júl 2006 pdf
Prezentácia pre diplomový seminár 29. jún 2006 ppt

News

13-09-2006

Rozhodol som sa, že prácu napíšem v anglickom jazyku, kvôli ťažko prekladateľnej terminológii.

Staré

Najnovší prieskum literatúry ukázal, že prístupy, na ktoré som sa zameral, sú už veľmi dobre popísané v [8], [9]. Tieto články predstavujú optimálne riešenie problému vyhľadania všetkých maximálnych repeatov v rámci jedného reťazca s použitím suffixových polí. Ak rozšírenie algoritmu na vyhľadávanie matchov medzi dvoma súbormi nebude predstavovať signifikantný výsledok, zamyslím sa aj nad inými možnými rozšíreniami.Momentálne sa zamieriavam na štúdium existujúcich riešení a implementácií, najmä [11].

Študovaný materiál

  1. Brenda S. Baker, On finding duplication in strings and software, technical report, AT&T Bell Laboratories, February, 1993 [zdroj] [.ps.gz]
  2. Manber, U., & Myers, G. (1993). Suffix arrays: A new method for on-line string searches. SIAM Journal on Computing, 22(5), 935--948 [zdroj] [.ps]
  3. E. Ukkonen: On-line construction of suffix-trees. Algorithmica 14 (1995), 249-260 [zdroj] [.pdf]
  4. M. Crochemore, W. Rytter: Text Algorithms. Oxford University Press, New York, 1994 [zdroj]
  5. P. Ko and S. Aluru, "Space-efficient linear time construction of suffix arrays," Combinatorial Pattern Matching, pp. 200-210, 2003. [zdroj] [.pdf]
  6. Juha Kärkkäinen and Peter Sanders: Simple linear work suffix array construction, in Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP '03). LNCS 2719, Springer, 2003, pp. 943-955 [zdroj] [.pdf]
  7. S. Kurtz and C. Schleiermacher: REPuter: Fast Computation of Maximal Repeats in Complete Genomes, Bioinformatics, 15(5):426-427, 1999. [zdroj][.pdf]
  8. S. Kurtz, and E. Ohlebusch: Replacing Suffix Trees with Enhanced Suffix Arrays, M.I. Abouelhoda, Journal of Discrete Algorithms, 2:53-86, 2004. [zdroj][.pdf]
  9. M.I. Abouelhoda, S. Kurtz, and E. Ohlebusch: The Enhanced Suffix Array and its Applications to Genome Analysis, In Proceedings of the Second Workshop on Algorithms in Bioinformatics, pages 449-463. Lecture Notes in Computer Science 2452, Springer-Verlag, 2002. [zdroj][.pdf]
  10. R. Dementiev, J. Mehnert, and J. Kärkkäinen: Better External Memory Suffix Array Construction. In Workshop on Algorithm Engineering & Experiments, Vancouver, 2005. [zdroj][.pdf]
  11. Jens Mehnert: External Memory Suffix Array Construction, Diploma Thesis [zdroj][.pdf]
  12. R. Dementiev, L. Kettner, P. Sanders: Stxxl: Standard Template Library for XXL Data Sets. Technical Report 2005/18, Fakultät für Informatik, University of Karlsruhe [zdroj][.pdf]
  13. Stefan Burkhardt, Juha Kärkkäinen: Fast Lightweight Suffix Array Construction and Checking, CPM 2003, LNCS 2676, pp. 55–69, 2003 [.pdf]
  14. Klaus-Bernd Schurmann, Jens Stoye: An Incomplex Algorithm for Fast Suffix Array Construction, Proceedings of the 7th Workshop on Algorithm Engineering and Experiments, 2005 [.pdf]
  15. S. Lee, K. Park, Efficient Implementations of Suffix Array Construction Algorithms, Proceedings of the 15th Australasian Workshop on Combinatorial Algorithms, pp. 64-72, 2004 [.ps]
  16. D. K. Kim, J. S. Sim, H. Park, K. Park, Linear-time construction of suffix arrays, Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching, pp. 186-199, 2003 [.ps]
  17. Juha Kärkkäinen, Peter Sanders and Stefan Burkhardt, Linear work suffix array construction, Journal of ACM, 2005. [.pdf]
  18. Giovanni Manzini, Two space saving tricks for linear time LCP computation, Technical Report TR-INF-2004-02-03-UNIPMN, [.pdf]

Súvisiaci software

Súvisiace linky

Zmeny:

14. marec 2007 - pridanie draftov chapterov 1, 2, 3

2. feb. 2007 - pridanie prezentácie na predobhajoby.

28. Január 2007 - pridanie odkazu na stránku projektu diffengine.

29. november 2006 - pridanie tretej prezentácie pre diplomový seminár

21. november 2006 - úprava R3 Stromu, pridaný obrázok (teraz už skutočného R3 stromu, predtým tam boli iba staré verzie obrázkov)

1. november 2006 - nový R3 Strom 0.5

27. október 2006 - úprava R3 Stromu 0.4

19. október 2006 - nová verzia R3 Stromu 0.4

17. október 2006 - obrázok R3 DAGu

14. október 2006 - nová verzia R3 DAGu

12. október 2006 - pridaný opis R3 DAGu

3. október 2006 - pridaný nový draft

27. septembra 2006 - pridaná druhá prezentácia a náčrt obsahu

13. septembra 2006 - zmena diplomovej práce do anglického jazyka, pridaná literatúra a poznámky

5. júla 2006 - pridané linky a články

29. jún 2006 - úprava cieľa a popisu a pridanie prvej tex verzie

25. marec 2006 - pridaný článok [12]

22. marec 2006 - pridané linky na existujúce implementácie suffix array algoritmov

19. marec 2006 - pridaný odkaz na článok [10]

13. marec 2006 - pridané odkazy na články [7, 8, 9]