Suffix Array for Large Alphabet
| Thesis title in Czech: | Suffixové pole pro velkou abecedu |
|---|---|
| Thesis title in English: | Suffix Array for Large Alphabet |
| Academic year of topic announcement: | 2006/2007 |
| Thesis type: | diploma thesis |
| Thesis language: | angličtina |
| Department: | Department of Software Engineering (32-KSI) |
| Supervisor: | RNDr. Jan Lánský, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 30.04.2007 |
| Date of assignment: | 30.04.2007 |
| Date and time of defence: | 14.05.2007 00:00 |
| Date of electronic submission: | 14.05.2007 |
| Date of proceeded defence: | 14.05.2007 |
| Opponents: | Mgr. Martin Senft, Ph.D. |
| Guidelines |
| Motivation for the work is Burrows-Wheeler Transform as part of syllable
compression of large blocks of XML files. The results apply to construction of suffix arrays for files with high average match length. Focus of the work is to compare known algorithms and based on the findings propose algorithm to be used. |
| References |
| 1) Micheal Burrows and David. J. Wheeler, A block-sorting lossless data compression algorithm, Research Report. 124, Digital systems Research, Palo Alto, California, May 1994.
2) Julian Seward, On the Performance of BWT Sorting Algorithms, , Microsoft Research, St George House, Guildhall Street, Cambridge CB2 3NH, UK 3) Julian Seward, Space-time tradeoffs in the Inverse B-W Transform, , Microsoft Research, St George House, Guildhall Street, Cambridge CB2 3NH, UK 4) Kunihiko Sadakane, A fast algorithm for making suffix arrays and for Burrows-Wheeler transformation, Proceedings of the IEEE Data Compression Conference, 1998 5) Juha Kärkkäinen and Peter Sanders, Simple linear work suffix array construction, Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP\'03). LNCS 2719, Springer, (2003) 943-955 |