PG SACABench
Das bekannteste und wohl am besten erforschte Problem der Algorithmik ist das Sortieren eines Felds von Zahlen. Dieses Problem kann auf Strings übertragen werden: sortiere alle Suffixe eines Strings in lexikographischer Reihenfolge, z. B. a, ana, bana und na für den String bana. Eine solche Sortierung ist der grundlegende Schritt vieler wichtiger Textindizes. Ziel dieser Projektgruppe ist die praktische Analyse und Verbesserung von bestehenden Algorithmen zur Suffixsortierung.
News
- Das Blockseminar findet am 05.04.2018 und 06.04.2018 jeweils von 9:00 Uhr bis 16:00 Uhr statt. Der Raum wird noch bekannt gegeben.
- Das erste Treffen findet am 31.01.2018 von 13:00 Uhr bis 15:00 Uhr im Raum OH12 3.030 statt.
- Themen für die erste Seminarphase hinzugefügt.
- Die PG kommt zustande. Weitere Informationen folgen ab dem 22.02.2018.
Die Einzelpräsentation findet am 20.12.2017 um 16:00 Uhr um Raum OH14 202 statt.
Seminarthemen
| Autoren | Titel | |
|---|---|---|
| 6. | Nong et al. | Two efficient algorithms for linear time suffix array construction |
| 7. | Nong | Practical linear-time O(1)-workspace suffix sorting for constant alphabets |
| 12. | Goto | Optimal Time and Space Construction of Suffix Arrays and LCP Arrays for Integer Alphabets |
| 5. | Fischer/Kurpicz | Dismantling DivSufSort |
| 4. | Manzini/Ferragina | Engineering a lightweight suffix array construction algorithm |
| 1. | Larsson/Sadakane | Faster suffix sorting |
| 2. | Schürmann/Stoye | An incomplex algorithm for fast suffix array construction |
| 3. | Baier | Linear-time suffix sorting - A new approach for suffix array construction |
| 8. | Maniscalco/Puglisi | An efficient, versatile approach to suffix sorting |
| 9. | Kärkkäinen/Sanders | Simple linear work suffix array construction |
| 10. | Nong/Zhang | Optimal lightweight construction of suffix arrays for constant alphabets |
| 11. | Dementiev et al. | Better external memory suffix array construction |