Ein Suffixarray ist eine einfache Datenstruktur, die das Indizieren und Nachschlagen von Teilzeichenketten ermöglicht. Ein großer Vorteil von Suffixarrays (die durchaus sehr groß werden können) ist, dass sie auf externen Speicher (zum Beispiel Festplatten) ausgelagert werden können und nicht vollständig im Hauptspeicher vorgehalten werden müssen.
In diesen Artikel zeigen wir – in einfacher Art und Weise – wie man das Grundprinzip von Suffixarrays auf eine Wörterbuchsuche anwenden kann.
Problem
Angenommen wir haben ein Deutsch-Englisches Wörterbuch mit folgenden Einträgen:
1. Software : software
2. Softwareentwicklung : software development
3. App-Entwicklung : app development
Eine wichtige Funktion von Wörterbüchern ist das Finden von Wörtern die einen gewissen Zeichenkette enthalten. Wenn man zum Beispiel nach “Entwicklung” sucht, sollen auch Einträge gezeigt werden die “Entwicklung” als Zeichenkette enthalten, wie zum Beispiel “Softwareentwicklung“. Und natürlich sollen diese Begriffe so schnell wir möglich gefunden werden – ohne das gesammte Wörterbuch Zeile für Zeile durchsuchen zu müssen. Dazu eignen sich Suffixarrays.
In fünf Schritten erklären wir, wie man ein Suffixarray aus diesem Wörterbuch aufbaut und wie dieses Array in einer Suchfunktion benutzt werden kann.
Schritt 1: Wörterliste
Als erstes generieren wir eine Wörterliste, die alle einzelnen Wörter enthalten (in Kleinbuchstaben). Wörter, die durch eine “-” verbunden sind, trennen wir auf. Zu jedem Wort merken wir uns die Zeilen in der das Wort vorkam. Diese List sieht dann wie folgt aus:
1. software : 1, 2
2. softwareentwicklung : 1
2. development : 2, 3
3. app : 3
4. entwicklung : 3
Schritt 2: Suffixe
Wir können nur die einzelnen Wörter, die in dieser Wörterliste vorkommen, rückwärts aufschreiben. Das sieht am Beispiel für “softwareentwicklung” wie folgt:
gunlkciwtneerawtfos : 1
Im nächsten Schritt werden alle Suffixe generiert, in dem wir einen Buchstaben nach dem anderen vom Anfang des Wortes entfernen. Auch hier merken wir uns wieder die Zeilennummer. Das Beispiel “softwareentwicklung” sieht dann wie folgt aus:
1. gunlkciwtneerawtfos : 2
2. unlkciwtneerawtfos : 2
3. nlkciwtneerawtfos : 2
4. lkciwtneerawtfos : 2
5. kciwtneerawtfos : 2
6. ciwtneerawtfos : 2
7. iwtneerawtfos : 2
8. wtneerawtfos : 2
9. tneerawtfos : 2
10.neerawtfos : 2
11.eerawtfos : 2
12.erawtfos : 2
13.rawtfos : 2
14.awtfos : 2
15.wtfos : 2
16.tfos : 2
17.fos : 2
18.os : 2
19.s : 2
Für “software”:
1.erawtfos : 1, 2
2.rawtfos : 1, 2
3.awtfos : 1, 2
4.wtfos : 1, 2
5.tfos : 1, 2
6.fos : 1, 2
7.os : 1, 2
8.s : 1, 2
Wie du siehst, kann man diese beiden Listen zusammenfassen, da ja das Wort “software” in “softwarentwicklung” enthalten ist. Daher sind auch alle “software” Suffixe identisch mit den “Softwareentwicklung” Suffixen. Diese zusammengefasste Liste sieht wie folgt aus:
1. gunlkciwtneerawtfos : 2
2. unlkciwtneerawtfos : 2
3. nlkciwtneerawtfos : 2
4. lkciwtneerawtfos : 2
5. kciwtneerawtfos : 2
6. ciwtneerawtfos : 2
7. iwtneerawtfos : 2
8. wtneerawtfos : 2
9. tneerawtfos : 2
10.neerawtfos : 2
11.eerawtfos : 2
12.erawtfos : 1,2
13.rawtfos : 1,2
14.awtfos : 1,2
15.wtfos : 1,2
16.tfos : 1,2
17.fos : 1,2
18.os : 1,2
19.s : 1,2
Für “entwicklung” sieht die das Suffixarray wir folgt aus:
1. gunlkciwtne : 3
2. unlkciwtne : 3
3. nlkciwtne : 3
4. lkciwtne : 3
5. kciwtne : 3
6. ciwtne : 3
7. iwtne : 3
8. wtne : 3
9. tne : 3
10.ne : 3
11.e : 3
Das zusammengefasste Suffixarray für “software”, “softwareentwicklung” und “entwicklung”:
1. gunlkciwtneerawtfos : 2
2. unlkciwtneerawtfos : 2
3. nlkciwtneerawtfos : 2
4. lkciwtneerawtfos : 2
5. kciwtneerawtfos : 2
6. ciwtneerawtfos : 2
7. iwtneerawtfos : 2
8. wtneerawtfos : 2
9. tneerawtfos : 2
10. neerawtfos : 2
11. eerawtfos : 2
12. erawtfos : 1,2
13. rawtfos : 1,2
14. awtfos : 1,2
15. wtfos : 1,2
16. tfos : 1,2
17. fos : 1,2
18. os : 1,2
19. s : 1,2
20. gunlkciwtne : 3
21. unlkciwtne : 3
22. nlkciwtne : 3
23. lkciwtne : 3
24. kciwtne : 3
25. ciwtne : 3
26. iwtne : 3
27. wtne : 3
28. tne : 3
29. ne : 3
30. e : 3
Jetzt können wir diese Liste sortieren.
Schritt 3: Sortieren
Dieses Suffixarray – lexikographisch sortiert – sieht dann wie folgt aus:
1. awtfos : 1,2
2. ciwtne : 3
3. ciwtneerawtfos : 2
4. e : 3
5. eerawtfos : 2
6. erawtfos : 1,2
7. fos : 1,2
8. gunlkciwtne : 3
9. gunlkciwtneerawtfos : 2
10. iwtne : 3
11. iwtneerawtfos : 2
12. kciwtne : 3
13. kciwtneerawtfos : 2
14. lkciwtne : 3
15. lkciwtneerawtfos : 2
16. ne : 3
17. neerawtfos : 2
18. nlkciwtne : 3
19. nlkciwtneerawtfos : 2
20. os : 1,2
21. rawtfos : 1,2
22. s : 1,2
23. tfos : 1,2
24. tne : 3
25. tneerawtfos : 2
26. unlkciwtne : 3
27. unlkciwtneerawtfos : 2
28. wtfos : 1,2
29. wtne : 3
30. wtneerawtfos : 2
Schritt 4: Suchen
Wir wollen alle Zeilen in unserem Wörterbuch suchen, in denen das Wort “Entwicklung” vorkommt – entweder als eigenständiges Wort oder als Teil eines anderen Wortes.
Als erstes normalisieren und invertieren wir “Entwicklung”, d.h. wir such nach “gunlkciwtne” (entwicklung) in dem Suffixarray. Als Suchalgorithmus kann man die Binäre-Suche verwenden.
1: User Suffixarray enthält 30 Einträge. Wir starten die Suche daher in der Mitte, bei Eintrag 15: “lkciwtneerawtfos” (softwarentwickl). Die ist nicht der gesuchte Eintrag und lexikographisch größer als “gunlkciwtne” (entwicklung). D.h wir müssen den Eintrag weiter vorne in unserem Suffix-Array suchen.
2: Die Neue Mitte (zwischen 1 und 15) ist 7. Der Eintrag auf Platz 7 “fos” (sof) ist lexikographisch kleiner als “gunlkciwtne” (entwicklung), d.h. wir müssen den Eintrag zwischen 7 und 15 suchen.
3: Die neue Mitte (7-15) ist 11 und auf Platz 11 finden wir “iwtneerawtfos” (softwareentwi), was größer ist als unser Gesuchter Ausdruck. Wir suchen weiter in der Mitte zwischen 7 und 11, was Platz 9 entspricht.
4: Endlich, auf Platz 9 finden wir einen Eintrag: “gunlkciwtneerawtfos” (Softwareentwicklung), denn dieser Eintrag beginnt mit dem gesuchten Suffix “gunlkciwtne” (entwicklung). Wir fügen Platz 9 zu unserem Suchergebnis hinzu.
4: Als nächstes untersuchen wir die oberen und unteren Nachbarn von Platz 9. Der erste obere Nachbar ist Platz 10. Platz 10 enthält “iwe” und gehöhrt somit nicht zu den Suchergebnissen und fahren mit den unteren Nachbarn fort. Auf Platz 8 findet man “gunlkciwtne” (entwicklung) – den gesuchten Begriff selbst – und damit fügen wir Position 8 zu den Suchergebnissen. Platz 7 (“fos”) gehört nicht zu den Suchergebnissen und damit ist die Suche beendet.
Schritt 5: Presentation
Die Suche nach “gunlkciwtne” (Entwicklung) fand Platz 8 und 9. Platz 8 und 9 verweisen auf die Zeilen 2 und 3 in unserem Wörterbuch:
2. Softwareentwicklung : software development
3. App-Entwicklung : app development
Diese beiden Zeilen sind die einzigen Zeilen in unserem Wörterbuch, die die Zeichenkette “Entwicklung” enthalten.
Fazit
In diesem Artikel zeigten wir, wie das Grundprinzip von Suffixarrays in einer Wörterbuchsuche angewandt werden kann. Mehr zu Suffixarrays und verwandte Datenstrukten wie Suffixbäume) findet man auf Wikipedia.