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
 
Last modified: 2018-04-05 14:13 by Johannes Fischer
DokuWikiRSS-Feed