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
- Brenda S. Baker, On finding duplication in strings and
software, technical report, AT&T Bell Laboratories, February, 1993
[zdroj]
[.ps.gz]
- 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]
- E. Ukkonen: On-line construction of suffix-trees. Algorithmica 14
(1995), 249-260 [zdroj]
[.pdf]
- M. Crochemore, W. Rytter: Text Algorithms. Oxford University Press,
New York, 1994 [zdroj]
- P. Ko and S. Aluru, "Space-efficient linear time construction of suffix
arrays," Combinatorial Pattern Matching, pp. 200-210, 2003.
[zdroj] [.pdf]
- 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]
- S. Kurtz and C. Schleiermacher: REPuter: Fast Computation of Maximal
Repeats in Complete Genomes, Bioinformatics, 15(5):426-427, 1999. [zdroj][.pdf]
- 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]
- 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]
- 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]
- Jens Mehnert: External Memory Suffix Array Construction, Diploma
Thesis [zdroj][.pdf]
- 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]
- Stefan Burkhardt, Juha Kärkkäinen: Fast Lightweight Suffix Array Construction
and Checking, CPM 2003, LNCS 2676, pp. 5569, 2003 [.pdf]
- 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]
- 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]
- 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]
- Juha Kärkkäinen, Peter Sanders and Stefan Burkhardt, Linear work suffix
array construction, Journal of ACM, 2005. [.pdf]
- 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]