BACHELORARBEIT · 2020. 12. 15. · Als Grundlage für dieses Thema dient das Buch „Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction“

FACHBEREICH 12: INFORMATIK UND MATHEMATIK

Institut für Informatik

BACHELORARBEIT

IMPLEMENTIERUNG EFFIZIENTER ALGORITHMEN FÜR STRING-MATCHING-PROBLEME UNTER VERWENDUNG

VON ERWEITERTEN SUFFIX-ARRAYS IN DER FUNKTIONALEN PROGRAMMIERSPRACHE HASKELL

SOBIA MOHI-UD-DIN

5. Mai 2014

eingereicht bei Prof. Dr. Manfred Schmidt-Schauß

Künstliche Intelligenz / Softwaretechnologie

Erklärung gemäß Bachelor-Ordnung Informatik 2007 §24 Abs. 11

Hiermit bestätige ich, dass ich die vorliegende Arbeit selbstständig verfasst habe und keine anderen Quellen oder Hilfsmittel als die in dieser Arbeit angegebenen verwendet habe.

Limburg, 5. Mai 2014

Sobia Mohi-ud-Din

3

Danksagung

Ich möchte mich an dieser Stelle bei all diejenigen bedanken, die mich während des Studiums und der Anfertigung dieser Bachelorarbeit unterstützt und motiviert haben.

Mein Dank gilt meinen Eltern Ghulam und Shaheda Mohi-ud-Din, sowie meinen Schwestern für die Unterstützung während meines Studiums.

Ein besonderer Dank geht an Dr. David Sabel für die zahlreichen Anregungen und Tipps, sowie für das Korrektur lesen.

4

Inhaltsverzeichnis

1. Zusammenfassung................................................................................................6

2. Einleitung............................................................................................................. 7 2.1 Motivation.............................................................................................. 7 2.2 Aufgabe und Zielsetzung....................................................................... 7 2.3 Überblick................................................................................................ 7

3. Grundlagen.......................................................................................................... 9 3.1 Grundlegende Notationen und Begriffe zu Strings................................ 9 3.2 String Matching-Problem...................................................................... 11 3.2.1 Definition................................................................................ 11 3.3 Suffix Array............................................................................................ 12 3.3.1 Definition................................................................................ 12 3.3.2 Naive Konstruktion & Laufzeit............................................... 13 3.3.3 Effizienter Konstruktions-Algorithmus & Laufzeit................ 13 3.4 Inverses Suffix Array.............................................................................. 16 3.4.1 Definition................................................................................ 16 3.4.2 Konstruktion............................................................................ 16 3.4.3 Laufzeit................................................................................... 17 3.4.4 Komplettes Beispiel................................................................ 17 3.5 LCP-Array.............................................................................................. 18 3.5.1 Definition................................................................................ 18 3.5.2 Naive Konstruktion & Laufzeit............................................... 18 3.5.3 Effiziente Konstruktion........................................................... 19 3.5.4 Laufzeit................................................................................... 22 3.5.5 Nachteil des Algorithmus von Kasai et al. ............................. 22

4. Das String-Matching-Problem............................................................................. 23 4.1 Definition: erweiterte Suffix Array & Grundlagen................................ 23 4.2 Naiver String-Matching-Algorithmus.................................................... 23 4.3 Effiziente String-Matching-Algorithmen............................................... 24 4.3.1 Binäre Suche im Suffix Array................................................. 25 4.3.2 Binäre Suche im Suffix Array mit LCP-Array........................ 28

5. Implementierung in Haskell................................................................................. 35 5.1 Haskell-Code.......................................................................................... 35 5.1.1 LCP-Array (Algorithmus 3.5)................................................. 35 5.1.2 SASEARCH und CMP (Algorithmen 4.4).................................. 37 5.1.3 FINDLEFTMOST (Algorithmus 4.3)........................................... 37 5.1.4 FINDLEFTMOST (Algorithmus 4.5)........................................... 38 5.1.5 Weitere Implementierungen.................................................... 40 5.2 Tests & Diagramme................................................................................ 41

6. Fazit..................................................................................................................... 45

Literaturverzeichnis................................................................................................. 46

5

1. Zusammenfassung

Diese Bachelorarbeit befasst sich mit dem String-Matching-Problem und dessen Lösungen. Beim String-Matching-Problem geht es darum, ein bestimmtes Muster in einer Datei zu finden. Es ist möglich das Problem effizient zu lösen, wenn eine Vorverarbeitung der Dateien vorgenommen wird, indem Index-Datenstrukturen, wie erweiterte Suffix Arrays, erzeugt und gespeichert werden. Die Mustersuche erfolgt anschließend mit Hilfe der erweiterten Suffix Arrays. In dieser Bachelorarbeit werden Algorithmen zur Problemlösung vorgestellt und in der funktionalen Programmiersprache Haskell implementiert und auf ihre Laufzeit und ihren Speicherverbrauch getestet. Zum Schluss kann durch Vergleich zweier Algorithmen festgestellt werden, dass die Nutzung von erweiterten Suffix Arrays vorteilhaft ist, da sie eine schnellere Suche nach dem Muster erlauben.

6

2. Einleitung

2.1 Motivation

In der Informatik gibt es immer neue Herausforderungen effiziente Algorithmen und Datenstrukturen für große Datenmengen zu entwickeln. Die Suche nach bestimmten Daten in einer Datenbank kann sehr lange dauern, wenn z.B. der Algorithmus nicht effizient arbeitet oder die Daten selbst unsortiert vorliegen. D.h. die Entwicklung guter Suchalgorithmen ist ebenso wichtig, wie die Vorverarbeitung der Daten. Beispielsweise wachsen in der Bioinformatik die Daten stetig, z.B. werden immer neue DNA-Sequenzen entschlüsselt und gespeichert, die aber danach unverändert bleiben. Hier ist es sinnvoll einmalig Index-Datenstrukturen, wie erweiterte Suffix Arrays, anzulegen, mit deren Hilfe eine schnelle Datensuche möglich ist.Wenn wir nun die DNA-Sequenzen bzw. die Daten als lange Zeichenketten betrachten, so können wir String-Matching-Algorithmen für die Suche nach bestimmten Zeichenfolgen verwenden. Schon einfache Textverarbeitungsprogramme verfügen über eine Suchoption, mit der nach bestimmten Wörtern im Text gesucht werden kann. D.h. das String-Matching-Problem begegnet uns alltäglich.

2.2 Aufgabe und Zielsetzung

In dieser Bachelorarbeit werden zunächst die erweiterten Suffix Arrays und deren Konstruktions-Algorithmen vorgestellt. Außerdem werden String-Matching Algorithmen gezeigt, die unter Verwendung der erweiterteren Suffix Arrays eine Laufzeit von O(m*log(n)) bzw. O(m+log(n)) erreichen, wobei n die Länge des Eingabestrings S und m die Länge des zu suchenden Musters ist. Die entsprechende Implementierung in der funktionalen Programmiersprache Haskell wird erläutert und auf ihre Laufzeit und Speicherverbrauch getestet. Aus den Testergebnissen sollen die Vorteile ersichtlich werden, die sich durch die Benutzung der erweiterten Suffix Arrays durch den String-Matching Algorithmus ergeben.Als Grundlage für dieses Thema dient das Buch „Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction“ von Enno Ohlebusch [9].

2.3 Überblick

In Kapitel 1 wird eine Zusammenfassung des Themas der Bachelorarbeit gegeben. Die Einleitung in Kapitel 2 zeigt kurz auf, wieso dieses Thema eine wichtige Bedeutung in der Informatik hat und nennt einige Anwendungsbeispiele. In Kapitel 3 werden die Grundlagen verdeutlicht. Zunächst werden grundlegende Notationen eingeführt, die im weiteren Verlauf der Arbeit genutzt werden. Nach der Definition des String-Matching-Problems werden die grundlegenden Datenstrukturen, das Suffix Array, Inverse Suffix Array und das LCP-Array vorgestellt, die in Kapitel 4 als Grundlage dienen. In Kapitel 4 wird das String-Matching-Problem erläutert und einige Algorithmen zur Lösung des Problems gezeigt, die die Datenstrukturen aus Kapitel 3 nutzen. Der Haskell-Code dieser Algorithmen wird in Kapitel 5 erläutert. Anschließend werden die Testläufe und deren Ergebnisse vorgestellt und verglichen.

7

In Kapitel 6 wird ein Fazit gegeben und in Kapitel 7 sind alle Literaturverweise aufgelistet.Die Implementierungen und Textergebnisse sind auf folgenden Link abrufbar: http://www.ki.informatik.uni-frankfurt.de/bachelor/programme/stringmatching/

8

3. Grundlagen

In diesem Kapitel werden zunächst die allgemeinen Datenstrukturen, Begriffe und Notationen zu Strings erörtert. Im Anschluss werden jeweils Suffix Array, Inverses Suffix Array und LCP-Array vorgestellt. Es werden Algorithmen zur Konstruktion und die Laufzeit erklärt.

3.1 Grundlegende Notationen und Begriffe zu Strings

Ein Alphabet ∑ ist eine endliche Menge von Symbolen. Ein Wort oder String über ∑ ist eine endliche Folge a1 ... an von Symbolen aus ∑, d.h. für i=1,...,n : ai ∈ ∑. Das leere Wort, der Länge 0 wird mit ε bezeichnet. ∑* ist die Menge aller Worte, die aus allen Zeichen des Alphabets ∑ gebildet werden können. Das leere Wort gehört auch zu ∑*. Seien S1 und S2 Worte über dem Alphabet ∑, so sei S1S2 die Konkatenation von S1 und S2, d.h. S1S2 entsteht durch Anhängen von S2 an S1. Die Länge eines Strings S bezeichnen wir mit |S|, die induktiv durch |ε|=0 und |aS|=1+|S| für a ∈ ∑ definiert werden kann.

Beispiel 3.1: Sei ∑={a,b}, dann sind S1=abba und S2=aaa Worte über ∑ mit |S1|=4 und |S2|=3, S1S2=abbaaaa und S2S1=aaaabba.

Definition 3.1 (Suffix und Präfix eines Strings)1: Ein String Sa ist ein Suffix eines Strings S, geschrieben als Sa⊐S, genau dann wenn S=TSa für irgendeinen String T = ∑* gilt. Analog ist ein String Sa ein Präfix eines Strings S, geschrieben als Sa⊏S, genau dann wenn S=SaT für irgendeinen String T=∑* gilt.

Das leere Wort ε ist sowohl Suffix als auch Präfix jedes Strings. Beachte, dass für Sa⊐S und Sa⊏S stets gilt |Sa| ≤ |S|. Umgangssprachlich ist Sa für den Fall Sa⊐S eine „Endung“ von S und für den Fall Sa⊏S ist Sa ein „Anfang“ von S.

Beispiel 3.2: ab ist ein Suffix von gtab, geschrieben ab⊐gtab. gt ist ein Präfix von gtab, geschrieben ab⊏gtab.

Für einen String S ∈ ∑* mit |S|=n und 1 ≤ i ≤ n bezeichnen wir mit S[i] das i-te Symbol von S. Mit S[i,j] für i ≤ j bezeichnen wir den Substring S[i]S[i+1]...S[j]. Das leere Wort ist ein Substring jedes anderen Strings.Ein geordnetes Alphabet ist ein Paar (∑,<) wobei ∑ ein Alphabet und < eine totale Ordnung auf ∑ ist. Sei (∑,<) ein geordnetes Alphabet, dann ist eine lexikographische Ordnung < auf Worten S1,S2 ∈ ∑* definiert durch S1 < S2 genau dann, wenn S1 ein Präfix von S2 ist oder wenn es Worte u,v,w ∈ ∑* und Zeichen a,b ∈ ∑ gibt, mit a < b sodass S1=uav und S2=ubw.

Beispiel 3.3: Sei (∑={a,b,c,d},<) ein geordnetes Alphabet, mit a<b<c<d und seien S1=aaaa und S2=aaaabccc, dann gilt: S1 < S2, da S1 ein Präfix von S2 ist. Seien S3=aaaaddd und S4=aaabccc, mit u=aaa, v=ddd und w=ccc, dann gilt: S3 < S4.

9

1 [4] Seite 998.

Sei (∑,<) ein geordnetes Alphabet. Sei w ∈ ∑*, dann sei w$ ein String mit Endsymbol, wobei gelten muss $ ∉ ∑ (d.h. w$ ∈ (∑∪{$})*) und $ < ai für alle ai ∈ ∑.Um die lexikographische Ordnung von zwei Strings S und T zu ermitteln, werden zunächst deren ersten Zeichen miteinander verglichen. Das Zeichen, welches im Alphabet vorher kommt, ist lexikographisch kleiner als das andere. Somit ist auch der String kleiner, als der andere, egal welche Größe er hat. Beispielsweise ist S=aaaaaa lexikographisch kleiner als T=b, da bereits das erste Zeichen von S, also a im Alphabet vor dem b kommt. Sind die ersten Zeichen jedoch identisch, werden die nächsten Zeichen verglichen usw. bis irgendein Zeichen kleiner, als das andere ist oder ein String zu Ende ist. In beiden Fällen ist dieser String kleiner, als der andere. Beispielsweise ist S=aa lexikographisch kleiner als T=aaaa, da die ersten zwei Zeichen zwar identisch sind, aber S kürzer als T. Um aber zu verhindern, dass in solchen Fällen entschieden werden muss, ob ein String bereits zu Ende ist, wird das Endsymbol $ an die beiden Strings angehängt. Da $ immer kleiner, als jedes andere Zeichen im String ist, muss nicht zuerst überprüft werden, ob das nächste zu vergleichende Zeichen existiert oder nicht.

Gegeben sind zwei Strings u, v ∈ ∑*. Die Funktion lcp(u,v) gibt die Länge des längsten gemeinsamen Präfixes der beiden Strings u und v an.

Beispiel 3.4: Sei ∑={a,b,c,d} und u=aabcc v=aabdd. Dann ist lcp(u,v)=lcp(aabcc,aabdd)= |aab| = 3.

Sei < die lexikographische Ordnung aller Strings über dem Alphabet ∑. Für jeden String u definieren wir

u|m =

Die strikte Ordnung <m auf ∑* ist definiert durch u <m v genau dann, wenn u|m < v|m. Außerdem wird die Ordnung ≤m folgendermaßen definiert: u ≤m v genau dann, wenn u|m < v|m oder u|m = u|m.

Beispiel: 3.5: Sei ∑={a,b,c,d} und u=aabc. Für m=5 ist u|m= aabc. Für m=3 ist u|m = aab. Sei v=aaacd, dann gilt für m=3 v|m = aaa < aab = u|m. Für m=2 gilt u|m = aa = v|m.

Weitere Details zu den Definitionen und Notationen können aus [9] entnommen werden.

10

{u falls |u| ≤ mu[1..m] sonst

3.2 String Matching-Problem

In diesem Kapitel wird das String-Matching Problem erklärt und definiert.

3.2.1 Definition

Bei der Verarbeitung von Texten ist es manchmal nötig eine bestimmte Zeichenfolge zu suchen. Z.B. müssen Textverarbeitungsprogramme in der Lage sein diese Anfrage schnell zu beantworten. Dokumente, Webseiten, DNA-Sequenzen, etc. können als Strings betrachtet werden. Daher wird die Suche in diesen Strings als String-Matching-Problem bezeichnet („Zeichenketten-Suchproblem“2). Es geht darum ein bestimmtes Pattern (Muster) in einem String zu finden.

Das String-Matching-Problem wird (in [9]) folgendermaßen definiert. Gegeben ist ein String S ∈ ∑+ der Länge |S|=n und ein Pattern P ∈ ∑+ der Länge |P|=m. Da P das zu suchende Pattern ist, muss dessen Länge kleiner als die Länge von S sein, d.h. m ≤ n. Wir sagen, dass P in S vorkommt und an Position j+1 beginnt, wenn S[j+1, ... , j+m] = P[1,...,m] gilt. Beim exakten String-Matching Problem ist nach allen Positionen j+1 gefragt, an denen P in S vorkommt.

Beispiel 3.5: Sei ∑={a,b,c}. Gegeben ist ein String S=abbaaabba und ein Pattern P=aaa. S und P sind Worte über ∑. Es gilt: S[4,5,6]=P[1,2,3], d.h. P kommt in S vor, ab der Position 4 (=j+1).

Beim String-Matching Problem gibt es drei Fragestellungen, die beantwortet werden müssen. Gegeben ist ein String S und das Pattern (Muster) P, dann ist die Frage1. ob P in S vorkommt2. wie oft P in S vorkommt3. an welchen Positionen P in S vorkommt.Diese Fragestellungen bezeichnen wir mit 1. Entscheidungsproblem, 2. Zählproblem und 3. Aufzählproblem.

11

2 [4] Seite 997.

3.3 Suffix Array

In diesem Teil wird das Suffix Array vorgestellt. Zunächst wird ein naiver Konstruktions-Algorithmus und die dazugehörige Laufzeit erklärt. Danach wird ein effizienter Algorithmus gezeigt, der das Suffix Array in O(n*log(n)) Zeit konstruiert (n ist Länge des Eingabestrings S).

3.3.1 Definition

Definition 3.2 (Suffix Array)3: Sei S ein String der Länge |S|=n. Für jedes i, 1 ≤ i ≤ n, wird mit Si der i-te Suffix S[i..n] von S bezeichnet. Das Suffix Array von S, geschrieben SAS ist ein Array von Integern von 1 bis n, das die lexikographische Ordnung der n Suffixe von String S wiedergibt, d.h. SSA[1] < SSA[2] < ... <SSA[n] .

Beim Suffix Array (Definition 3.2) handelt es sich um eine Index-Datenstruktur, die verwendet werden kann um bestimmte Zeichen (Pattern) in einem String zu finden. D.h. Suffix Arrays können von String-Matching-Algorithmen verwendet werden, um eine bessere Laufzeit bei der Suche von Pattern zu ermöglichen. Das Anlegen eines Suffix Arrays zu einem bestimmten String (Text, DNA-Sequenz) ist dann sinnvoll, wenn sich diese Daten nicht verändern. Somit ist nur eine einmalige Konstruktion des Suffix Arrays nötig, wenn später oft auf diese zugegriffen wird. Der Vorteil eines Suffix Arrays ist es, dass die Suffixe von S selbst nicht gespeichert werden, sondern nur Integerzahlen, die die lexikographische Ordnung der Suffixe von S wiedergeben. Würde man die sortierten Suffixe selbst in einem Array speichern, so würde dies viel mehr Speicher verbrauchen, als ein Array, das nur die Länge n hat. Für das Speichern der Suffixe benötigt man Platz für ∑ni=1 |si| = ∑ni=1 (n-i+1) = n(n+1)/2 Zeichen. Da das Suffix Array ein Array der Länge n ist und alle Zahlen von 1 bis n genau einmal vorkommen, kann es auch als eine Permutation betrachtet werden.4

Definition (Suffix Array als Permutation) : Gegeben ist ein String S der Länge |S|=n und zwei Integer i und j. S hat n Suffixe Sk für 1 ≤ k ≤ n. Wir sagen, dass i <S j genau dann wenn Si < Sj gilt, d.h. der Suffix Si ist lexikographisch kleiner als Sj. Das Suffix Array ist eine Permutation π von Integerzahlen von 1 bis n, wenn π1 <S π2 <S ... <S πn gilt.

Beispiel 3.6: Für den String S=ctaataatg$ sind die Suffixe folgendermaßen lexikographisch geordnet: S10 < S3 < S6 < S4 < S7 < S1 < S9 < S2 < S5 < S8. D.h. 10 <S 3 <S 6 <S 4 <S 7 <S 1 <S 9 <S 2 <S 5 <S 8. Daraus ergibt sich das Suffix Array SAS=[10,3,6,4,7,1,9,2,5,8].5

12

3 [9] S.60.

4 [5].

5 ebd.

3.3.2 Naive Konstruktion & Laufzeit

Die Konstruktion eines Suffix Arrays kann einfach aber ineffizient sein. Beim naiven Verfahren werden zunächst alle Suffixe des Strings S erzeugt. Wenn |S|=n die Länge des Eingabestrings ist, dann gibt es S1, S2, ... , Sn Suffixe von S. Anschließend werden diese Suffixe lexikographisch, mit Hilfe eines Standard-Sortieralgorithmus, sortiert. Da ein normaler Sortieralgorithmus O(n*log(n)) Vergleiche benötigt und bei jedem Vergleich wiederum O(n) Zeichen verglichen werden müssen, ergibt sich eine Gesamtlaufzeit von O(n2*log(n)) im Worst-Case.

Algorithmus 3.1: Naiver Algorithmus zur Konstruktion eines Suffix Arrays SA eines String S

SUFFIX-ARRAY-NAIV(S) for i ← 1 to n ← length(S) do SuffixArray[i] ← (i, Si) Sortiere SuffixArray nach Si lexikographisch return jeweils i (erstes Element des Tupels) vom SuffixArray

Die Konstruktion wird anhand des Strings in dem Beispiel 3.7 erklärt.

Beispiel 3.7: Die Suffixe von S = „ctaataatg$“ werden sortiert. Die Indizes nach der Sortierung ergeben das Suffix Array.

3.3.3 Effizienter Konstruktions-Algorithmus & Laufzeit

Das Problem bei der naiven Konstruktion eines Suffix Arrays ist, dass bestimmte Eigenschaften der Suffixe nicht genutzt werden. Manber und Myers [8] haben einen Algorithmus zur direkten Konstruktion eines Suffix Arrays entwickelt, der O(n*log(n)) Zeit benötigt und die gewonnen Informationen bei der Sortierung nutzt. Beim Algorithmus 3.2 von Manber und Myers wird eine Form des Bucket Sorts verwendet. In der ersten Phase werden die Suffixe nach dem ersten Zeichen sortiert, indem sie in ein Bucket eingefügt werden. Somit liegen alle Suffixe, deren erstes Zeichen identisch ist, auch im selben Bucket. Diese erste Phase benötigt einen Zeitaufwand von O(n), wenn Bucket-Sort verwendet wird.

13

i Si

1 c t a a t a a t g $2 t a a t a a t g $3 a a t a a t g $4 a t a a t g $5 t a a t g $6 a a t g $7 a t g $8 t g $9 g $10 $

i SSA[i]

10 $3 a a t a a t g $6 a a t g $4 a t a a t g $7 a t g $1 c t a a t a a t g $9 g $2 t a a t a a t g $5 t a a t g $8 t g $

sort

SA (Suffix Array)

i SA[i] SSA[i]

1 10 $2 3 a a t a a t g $3 6 a a t g $4 4 a t a a t g $5 7 a t g $6 1 c t a a t a a t g $7 9 g $8 2 t a a t a a t g $9 5 t a a t g $10 8 t g $

In der zweiten Phase werden die Suffixe jeweils innerhalb der Buckets nach ihrem zweiten Zeichen sortiert und in neue Buckets gespeichert. Somit entstehen immer mehr Buckets, bis jedes Bucket genau einen Suffix enthält. Dieses Verfahren hat jedoch eine quadratische Laufzeit, da es im Worst-Case O(n) Durchläufe gibt, in denen jeweils O(n) Zeichen in die Buckets sortiert werden. Jedoch ist eine bessere Laufzeit möglich, da der Algorithmus Vergleiche spart. Der Trick des Algorithmus ist es, auf die bereits sortierten Suffixe zuzugreifen und deren Sortierung zu Hilfe zu nehmen. In jeder Phase werden die Anzahl der zu vergleichenden Zeichen verdoppelt, d.h. in Phase 3 wird nach den Zeichen 3 und 4, in Phase 4 nach den Zeichen 5,6,7 und 8, usw. sortiert. Somit ist der Algorithmus bereits in ⎡log(n)⎤ Schritten fertig. D.h. nach der Phase i müssen die Suffixe nach den ersten Zeichen 2i sortiert sein und in Phase i+1 sind die Suffixe bereits nach den ersten 2i Zeichen sortiert und es müssen noch die nächsten 2i Zeichen (2i+1, 2i+2, ... , 2i+1) sortiert werden. Die Anzahl der Zeichen, nach dem die Suffixe bereits sortiert sind und die Anzahl der Zeichen, nach denen noch sortiert werden muss, sind identisch. Deshalb kann man die bereits sortierten 2i Zeichen nutzen, um die Suffixe nach den nächsten 2i Zeichen zu sortieren. Man nutzt also die vorige Ordnung und sortiert somit diese Zeichen, sodass keine Zeichenvergleiche nötig sind.6Beispielsweise sei ein Suffix Sn-k+1 mit k > 2i Zeichen. Dann ist der Substring Sn-k+1

[2i+1, ... , l] mit l=min{2i+1, k} auch ein Präfix von Sn-k+1+2j, d.h. Sn-k+1[2i+1, ... , l] = Sn-k+1+2i[1, ... ,l-2i+1]. Da dies für alle Strings gilt, die in Phase i+1 anhand der Zeichen an Position 2i+1, ... ,2i+1 sortiert werden müssen, gibt es für jeden String einen solchen Präfix. Diese Präfixe wurden jedoch bereits in Phase i sortiert und daher lässt sich die entsprechende Ordnung ablesen und direkt übertragen, ohne zeichenweise Vergleiche durchzuführen. Somit benötigt jede Phase O(n) Zeit. Da sich die Anzahl der zu vergleichenden Zeichen verdoppelt, werden nur ⎡log(n)⎤ Durchläufe benötigt. Dadurch ergibt sich eine Gesamtlaufzeit von O(n*log(n)). Hinzu kommt, dass die Suffixe selbst nicht im physikalischen Speicher verschoben werden, sondern nur die Zeiger zu den Suffixen.

Algorithmus 3.2: Manber-Myers Suffix Sortieralgorithmus7

MANBER-MYERS-SUFFIX-SORTING(S ) /* Ausgabe des Suffix Arrays im Array AS */ Führe Bucket Sort über S aus, um das vorsortiere Array As zu erhalten for u ← 0 to ⌈log n⌉ do k ← 2u for v ← 1 to n do i ← AS [v] if (i − k > 0) or (i + k ≤ n + 1) then Bewege suffix Si−k to zum nächsten freien Platz innerhalb des Buckets (in AS ) end if end for end for

14

6 [6], [7].

7 [1] Seite 79.

Beispiel 3.8: Vorgehensweise des Algorithmus von Manber und Myers für S=ctaataatg$.

15

i Si

1 c t a a t a a t g $2 t a a t a a t g $3 a a t a a t g $4 a t a a t g $5 t a a t g $6 a a t g $7 a t g $8 t g $9 g $10 $

B1 SA Si

$ 10 $

a

3 a a t a a t g $

a4 a t a a t g $

a 6 a a t g $a

7 a t g $c 1 c t a a t a a t g $g 9 g $

t2 t a a t a a t g $

t 5 t a a t g $t8 t g $

B1 B2 SA Si

$ - 10 $

aa 6 a a t g $

aa 3 a a t a a t g $

at 7 a t g $at 4 a t a a t g $

c - 1 c t a a t a a t g $g - 9 g $

ta 5 t a a t g $

ta 2 t a a t a a t g $tg 8 t g $

B1 B2 B3 SA Si

$ - 10 $

aa 6 a a t g $

aa 3 a a t a a t g $

at a 4 a t a a t g $at g 7 a t g $

c - 1 c t a a t a a t g $g - 9 g $

ta a 5 t a a t g $

ta a 2 t a a t a a t g $tg - 8 t g $

B1 B2 B3 B4 SA Si

$ - 10 $

aa t a 3 a a t a a t g $

aa t g 6 a a t g $

at a - 4 a t a a t g $at g - 7 a t g $

c - 1 c t a a t a a t g $g - 9 g $

ta at a 2 t a a t a a t g $

ta at g 5 t a a t g $tg - 8 t g $

3.4 Inverses Suffix Array

In diesem Abschnitt wird das Inverse Suffix Array (ISA) vorgestellt und die Konstruktion mithilfe eines Suffix Arrays erklärt. Anschließend wird die Laufzeit begründet und ein Beispiel zur Konstruktion eines ISA gezeigt.

3.4.1 Definition

Definition 3.3 (Inverses Suffix Array): Das Inverse Suffix Array von S, geschrieben ISAS, ist ein Array der Länge |S|=n, sodass für jedes k mit 1 ≤ k ≤ n die Gleichheit ISA[SA[k]]=k gilt.

Das inverse Suffix Array wird auch als Rang-Array bezeichnet, weil ISA[i] den Rang des i-ten Suffixes Si wiedergibt, unter allen n lexikographisch sortierten Suffixen von S. Das bedeutet, wenn ISA[1]=i, dann ist Si der lexikographisch kleinste Suffix und wenn ISA[n]=j, dann ist Sj der lexikographisch größte Suffix von S. Genauer ausgedrückt bedeutet ISA[i]=j, dass der Suffix Si der j-lexikographisch-kleinste Suffix von S ist.8

Das inverse Suffix Array ISA kann ebenfalls, wie das Suffix Array, als eine Permutation der Zahlen von 1 bis n betrachtet werden, wobei n die Länge des dazugehörigen Strings S ist.

3.4.2 Konstruktion

Das Inverse Suffix Array ISAS kann aus dem Suffix Array SAS eines Strings S konstruiert werden. Es gilt ISA[i]=j genau dann, wenn SA[j]=i gilt. Daher ergibt sich die Formel zur Berechnung des ISA: ISA[SA[i]]=i. Außerdem ist erkennbar, dass durch die Biimplikation ebenfalls für SA gilt: SA[ISA[i]]=i. Somit kann das Inverse Suffix Array aus einem Suffix Array und umgekehrt konstruiert werden (Algorithmus 3.3. und 3.4).

Algorithmus 3.3: Inverse Suffix Arrays ISA - Konstruktion mit SA

INVERS-SUFFIX-ARRAY-LINEAR(SA) for i ← 1 to n ← length(SA) do ISA[SA[i]] ← i return ISA

Algorithmus 3.4: Suffix Arrays SA - Konstruktion mit ISA

SUFFIX-ARRAY-LINEAR(ISA) for i ← 1 to n ← length(ISA) do SA[ISA[i]] ← i return SA

16

8 [9] Seite 60.

3.4.3 Laufzeit

Wir betrachten für die Laufzeit nur den Algorithmus 3.3 zur Konstruktion eines ISA, da die Begründung für SA analog ist. Das Suffix Array SA wird genau einmal durchlaufen und der entsprechende Wert in ISA gespeichert. Somit ergibt sich eine lineare Laufzeit O(n) mit |SA|=n.

3.4.4 Komplettes Beispiel

Gegeben ist ein String S=ctaataatg$ und das dazugehörige Suffix Array SAS=[10,3,6,4,7,1,9,2,5,8]. Das Inverse Suffix Array ist ISAS=[6,8,2,4,9,3,5,10,7,1]. Man sieht, dass SA[1]=10 und ISA[10]=1, SA[2]=3 und ISA[3]=2, etc. gilt. Außerdem besagt beispielsweise ISA[5]=9, dass der Suffix S5 den Rang 9 hat, unter allen lexikographisch sortierten Suffixen von S. In Beispiel 3.8 ist zu sehen, dass S5=taatg$ auf Position 9 ist. Weitere Details zum Suffix Array sind in [9] zu finden.

Beispiel 3.9: Suffix Array SA, Inverse Suffix Array ISA und die sortierten Suffixe von S=ctaataatg$

i SA[i] ISA[i] SSA[i]

1 10 6 $2 3 8 a a t a a t g $3 6 2 a a t g $4 4 4 a t a a t g $5 7 9 a t g $6 1 3 c t a a t a a t g $7 9 5 g $8 2 10 t a a t a a t g $9 5 7 t a a t g $10 8 1 t g $

17

3.5 LCP-Array

In diesem Teil wird das LCP-Array und ein Konstruktions-Algorithmus (aus [9]) von Kasai et al. vorgestellt. Anschließend wird die Laufzeit analysiert.

3.5.1 Definition

Definition 3.4 (LCP-Array)9: Das LCP-Array von S ist ein Array der Länge n+1 für |S|=n. Das LCP-Array hat die Grenzwerte LCP[1]= –1 und LCP[n+1]= –1 und für alle i mit 2 ≤ i ≤ n gilt: LCP[i] = |lcp(SSA[i-1], SSA[i])|.

LCP seht für „longest common prefix“ und bedeutet längster gemeinsamer Präfix. Die Funktion lcp(u,v) gibt daher den längsten gemeinsamen Präfix zweier Strings u und v an. Im Gegensatz zum SA oder ISA ist das LCP-Array keine Permutation der Zahlen von 1 bis n. Es gibt die Anzahl der gleichen Anfangs-Zeichen zweier Strings an, weshalb ein LCP-Wert auch mehrmals vorkommen kann.Wenn ein String S und das dazugehörige Suffix Array gegeben ist, kann das LCP-Array daraus berechnet werden. Zunächst benötigt man aber noch eine Information, nämlich das Inverse Suffix Array, welches bereits in Kapitel 3.4 eingeführt wurde. Genau genommen ist die Konstruktion eines ISA der erste Schritt im Algorithmus von Kasai et al.

Beispiel 3.10: (SAS und ISAS und LCP-Array von S=ctaataatg$)

i SA[i] ISA[i] LCP[i] SSA[i]

1 10 6 -1 $2 3 8 0 a a t a a t g $3 6 2 3 a a t g $4 4 4 1 a t a a t g $5 7 9 2 a t g $6 1 3 0 c t a a t a a t g $7 9 5 0 g $8 2 10 0 t a a t a a t g $9 5 7 4 t a a t g $10 8 1 1 t g $

-1

3.5.2 Naive Konstruktion & Laufzeit

Das LCP hat die Länge n+1 mit |S|=n. Naiv kann es konstruiert werden, indem zunächst alle Suffixe von S erzeugt und dann sortiert werden. Das erste und letzte Element im LCP-Array erhalten den Wert –1, d.h. LCP[1] = –1 und LCP[n+1] = –1. Nun werden die Suffixe jeweils mit dem vorherigen Suffix nach gemeinsamen

18

9 [9] Seite 79.

Präfixen verglichen und die Länge im LCP-Array gespeichert. Wird Si mit Si-1 verglichen, so wird die Länge des längsten gemeinsamen Präfixes in LCP[i] eingetragen.Bei dieser Art der Konstruktion wird das LCP-Array direkt aus dem String S konstruiert, wodurch eine Gesamtlaufzeit von O(n2*log(n)) entsteht. Die hohe Laufzeit ergibt sich durch das Sortieren der Suffixe. In jede der O(n*log(n)) Vergleiche des Sortieralgorithmus werden O(n) Zeichen verglichen.

3.5.3 Effiziente Konstruktion

Manber und Mayer [8] haben neben dem Suffix-Array auch das LCP-Array eingeführt, jedoch wurde dieses als Nebenprodukt bei der Konstruktion des Suffix-Arrays erzeugt. Später wurden unabhängig voneinander lineare Algorithmen entwickelt, die das LCP-Array nicht gleichzeitig mit dem Suffix-Array berechneten. Eines davon ist der Algorithmus von Kasai et al., der 2001 vorgestellt wurde und das LCP-Array in linearer Zeit aus dem Suffix Array berechnet.10 Bei diesem Algorithmus folgt die Berechnung des LCP-Array nicht sequentiell, sondern nach der Ordnung des Suffix Arrays.

Algorithmus 3.5: LCP-Array - Konstruktion aus S und SA11

LCP-ARRAY-LINEAR(S, SA) n ← length(S) LCP[1] ← –1 LCP[n+1] ← –1 for i ← 1 to n do ISA[SA[i]] ← i l ← 0 for i ← 1 to n do j ← ISA[i] if j > 1 then k ← SA[j-1] while S[k+ l] = S[i+ l] do l ← l + 1 LCP[j] ← l l ← max{l–1, 0}

Der Algorithmus 3.5 von Kasai et al. benötigt als Eingabe den String und das Suffix Array und erzeugt zunächst das Inverse Suffix Array in der ersten for-Schleife. Die Berechnung des Inversen Suffix Arrays wurde bereits in Kapitel 3.5 beschrieben.In der zweiten for-Schleife werden die Werte für das LCP-Array erzeugt. Die Suffixe werden vom längsten bis zum kleinsten Suffix, also von S1 bis Sn, durchgegangen (j ← ISA[i]). Jeder Suffix wird mit dem lexikographisch vorherigen Suffix verglichen (k ← SA[j-1]). In der while-Schleife werden die gemeinsamen Präfixe

19

10 [2].

11 [9] Seite 80.

} Konstruktion von ISA

dieser beiden Suffixe gezählt, durch den Zähler l. Dieser Wert wird anschließend in LCP[j] gespeichert. Die Idee des Algorithmus 3.5 ist es, die Suffixe S1 bis Sn nacheinander abzuarbeiten und für jeden Suffix Si die Länge des längsten gemeinsamen Präfixes mit seinem lexikographischen Vorgänger, d.h. lcp(Si, Sk) zu berechnen. Der lexikographische Vorgänger von Si ist Sk, wobei k = SA[ISA[i]-1]. (k erhält man, indem man j = ISA[i] in k = SA[j-1] einsetzt.) Naiv würde der Algorithmus für jedes Si den LCP mit den dazugehörigen Vorgänger Sk berechnen, indem die beiden Strings von links beginnend zeichenweise verglichen werden. Dieser Ansatz hat quadratische Laufzeit, da O(n) Strings verglichen werden die jeweils O(n) Zeichenvergleiche benötigen. Tatsächlich kommt man aber mit weniger Vergleichen aus:

Kennt man die Länge l des LCP von Si und Sk, so weiß man bereits, dass der LCP von Si+1 und Sk‘, wobei Sk‘ der lexikographische Vorgänger von Si+1 ist, mindestens die Länge l-1 haben muss. Deshalb genügt es für die Berechnung des LCP Si+1 und Sk‘ ab dem l-ten Symbol miteinander zu vergleichen. Wir illustrieren, warum die Länge mindestens l-1 sein muss.

Da lcp(Si, Sk)==l müssen Sk und Si von der Form

Sk =

Si =

mit b1 ≠ c1 sein. D.h. die ersten l Zeichen der beiden Suffixe sind identisch, also haben Si und Sk einen längsten gemeinsamen Präfix der Länge l.Wenn wir nun von Si und Sk das erste Zeichen entfernen ergibt sich:

Sk+1 =

Si+1 =

D.h. offensichtlich haben Sk+1 und Si+1 einen gemeinsamen Präfix der Länge l-1. Der lexikographische Vorgänger Sk‘ von Si+1 muss nicht notwendigerweise Sk+1 sein. Somit liegen zwei Fälle vor: Entweder ist Sk‘=Sk+1 (1) oder Sk‘ liegt zwischen Si+1 und Sk+1, d.h. Sk+1 < Sk‘ < Si+1 (2). Fall (1) ist klar und in Fall (2) muss Sk‘ den Präfix a2a3...al haben, da er sonst nicht zwischen Sk+1 uns Si+1 liegen würde.Der Algorithmus 3.5 berechnet zunächst lcp(Si, Sk)=l. Der nachfolgende Suffix von Si ist Si+1. Um lcp(Si+1,Sk‘) zu berechnen, werden die Zeichen ab dem l-ten Zeichen verglichen, da wir nun wissen, dass die ersten l-1 Zeichen von Si+1 und Sk‘ identisch

20

a1 a2 a3 ... al b1 ... bm

a1 a2 a3 ... al c1 ... cn

a2 a3 ... al b1 ... bm

a2 a3 ... al c1 ... cn

l

l - 1

sind (l ← max{l–1, 0}). Durch diese Vorgehensweise vermeidet der Algorithmus 3.5 unnötige Vergleiche, was in dem folgenden Lemma verdeutlicht wird.

Lemma 3.112: Es gilt LCP[ISA[i]] ≥ LCP[ISA[i-1]] – 1 für 2 ≤ i ≤ n.

Beweis Lemma 3.1 Sei l = LCP[ISA[i–1]]. Klar ist, dass für l = 0 und l = 1 das Lemma wahr ist: LCP[ISA[i]] ≥ –1 und LCP[ISA[i]] ≥ 0.Sei also l ≥ 2. Sei Sk der Suffix von S, der vor dem Suffix Si–1 in SA steht, für k = SA[ISA[SA[i–1]]–1].Da LCP[ISA[i–1]] = l, gilt |lcp(Sk,Si–1)| = l und S[k, ... , k+l–1] = S[i-1, ... , i+l–2] und S[k+l] ≠ S[i+l–1], d.h. die ersten l Positionen der Suffixe sind gleich. Daraus folgt, dass die beiden Suffixe ohne das erste Zeichen die ersten l–1 Zeichen gleich haben. Ohne das erste Zeichen gilt: S[k+1, ... , k+l–1] = S[i, ... , i+l–2] und S[k+l] ≠ S[i+l–1] bzw. |lcp(Sk,Si-1)| = l–1. Außerdem ist Sk+1 lexikographisch kleiner als Si, weil Sk lexikographisch kleiner ist als Si–1 und S[k] = S[i–1]. Somit liegt Sk+1 vor Si im Suffix Array. Wegen |lcp(Sk,Si–1)| = l –1 gilt, dass alle Suffixe zwischen Sk+1 und Si (wenn es überhaupt eines gibt) einen gemeinsamen Präfix der Länge l–1 haben. Daher gilt: LCP[ISA[i]] ≥ l–1. Durch Einsetzen von l = LCP[ISA[i–1]] ergibt sich das oben genannte Lemma 3.1: LCP[ISA[i]] ≥ LCP[ISA[i–1]] – 1. ▢ Der Algorithmus verwendet dieses Lemma, um unnötige Zeichenvergleiche zu überspringen. Wenn beispielsweise bei der Berechnung des LCP-Arrays l = LCP[ISA[i–1]] bekannt ist, dann können l–1 Zeichenvergleiche ausgelassen werden. Denn wenn zwei Suffixe die im Suffix Array aufeinander folgen einen Präfix der Länge n haben, so haben die Suffixe ohne das erste Zeichen eine Präfix mindestens der Länge l–1. Daher müssen diese Zeichen nicht noch einmal verglichen werden.Aus diesem Grund kommt auch die lineare Laufzeit des Algorithmus zustande.

Beispiel 3.11: Arbeitsweise des Algorithmus 3.5

i SA[i] ISA[i] LCP[i] SSA[i]

1 10 6 -1 $2 3 8 ? a a t a a t g $3 6 2 1 a a t g $4 4 4 a t a a t g $5 7 9 a t g $6 1 3 c t a a t a a t g $7 9 5 0 g $8 2 10 0 t a a t a a t g $9 5 7 4 t a a t g $10 8 1 t g $

-1

21

12 [9] Seite 80.

Der Algorithmus hat die LCP-Werte für die Suffixe S1 S2 S3 und S4 berechnet, d.h. die zweite for-Schleife wurde schon bis i=4 durchlaufen. Für den nächsten Durchlauf haben wir l=0 und i=5, d.h. nun wird der Suffix S5=taatg$ mit dem lexikographischen Vorgänger verglichen. Außerdem berechnen wir j=ISA[5]=9 und k=SA[9-1]=2. D.h. Sk=taataatg$ ist der Vorgänger S5. Diese beiden Suffixe, werden zeichenweise in der while-Schleife verglichen. Sk und S5 haben einen gemeinsamen Präfix er Länge 4, sodass LCP[9]=4 ist, da l=4. Für i=6, also dem Suffix S6=aatg$ haben wir nun l=3, d.h. der Suffix Sk=aataatg$ ist der lexikographische Vorgänger von S6 (, mit j=ISA[6]=2 und k=SA[j-1]=3). Diese beiden Suffixe werden nun ab dem l-ten Zeichen, also ab dem 3. Zeichen miteinander verglichen. Dies geschieht in der while-Schleife des Algorithmus. Für S6[4]=g und Sk[4]=a erhalten wir einen Missmatch, sodass hier die Schleife abgebrochen wird und der Wert l=3 in LCP[2] eingefügt wird. usw.

3.5.4 Laufzeit

In der ersten for-Schleife wird das Inverse Suffix Array berechnet. In Kapitel 3.4.3 wurde die Laufzeit O(n) bereits erklärt. Genau wie die erste for-Schleife, wird auch die zweite n mal durchlaufen. Auch die while-Schleife innerhalb der zweiten for-Schleife hat eine lineare Laufzeit. Die while-Schleife wird summiert über alle Durchläufe höchsten 2n-mal durchlaufen und somit sind auch nur 2n Zeichenvergleiche nötig, damit das LCP-Array in O(n) Zeit berechnet wird.

Beweis, dass while-Schleife höchstens 2n mal ausgeführt wird13

In der while-Schleife endet jeder Vergleich, wenn zwei unterschiedliche Zeichen verglichen werden, d.h. ein Miss-Match erfolgt. Insgesamt werden n-1 solche negative Vergleiche gemacht. Wenn eine Position p mit p=i+l und S[k+1]=S[i+l] in einem Vergleich vorkommt, so wird das Zeichen S[p] in den nächsten Vergleichen der Suffixe übersprungen. Daher sind höchstens n Vergleiche nötig. ▢

3.5.5 Nachteil des Algorithmus von Kasai et al.

Der Nachteil des Algorithmus von Kasai et al. ist der hohe Speicherverbrauch bei der Konstruktion des LCP-Arrays. Der Speicherbedarf liegt bei 13n Bytes. Dieser kann zwar etwas reduziert werden, wenn man das Inverse Suffix Array mit den Werten des LCP überschreibt, jedoch sind immer noch 9n Bytes nötig.14

22

13 [9] Seite 81.

14 [2] Seite 22.

4. Das String-Matching-Problem

In diesem Kapitel werden Lösungsansätze für das in Kapitel 3.2 vorgestellte String-Matching-Problem aufgeführt. Zunächst wird die naive Lösung und die Laufzeit vorgestellt. Danach werden zwei weitere Algorithmen erklärt, die mit den erweiterten Suffix Arrays arbeiten. Anschließend werden deren Laufzeiten bestimmt. Außerdem enthält das Kapitel zu jedem vorgestellten Algorithmus Beispiele zur Veranschaulichung der Funktionsweise.

4.1 Definition: erweiterte Suffix Array & Grundlagen

Die in Kapitel 3 vorgestellten Arrays werden verwendet, um eine effiziente Laufzeit für Algorithmen zu ermöglichen, die das String-Matching Problem lösen.

Definition 4.1 (erweitertes Suffix Array):15

Das Suffix Array, erweitert durch LCP-Array, nennt man erweitertes Suffix- Array (enhanced Suffix Array).

Im String-Matching Problem geht es darum, herauszufinden, ob ein bestimmtes Pattern P als Substring in einem großen String S vorkommt.Dabei gibt es drei Fragestellungen: Das Entscheidung-, Zähl- und Aufzählproblem. Man erkennt, dass die Lösung des Aufzählproblems auch die beiden anderen Fragestellungen beantworten kann. Wir gehen davon aus, dass die Lösung des Aufzählproblem als Liste mit den Werten ausgegeben wird, die alle Positionen s enthält, ab denen das Pattern als Substring in S vorkommt. Die Länge der Liste gibt die Lösung des Zählproblems an. Für das Entscheidungsproblem kann „True“ als Lösung angegeben werden, wenn die besagte Liste nicht leer ist, ansonsten wird ein „False“ die Antwort sein. Daher werden wir im weiteren Verlauf nur das Aufzählproblem betrachten, da es die Lösung für die anderen beiden Fragestellungen enthält.

4.2 Naiver String-Matching-Algorithmus

Der naive String-Matching-Algorithmus [4] geht jedes Zeichen des Strings S durch und überprüft, ob das gegebene Pattern P ab dieser Position mit dem Substring in S übereinstimmt. Wenn dies der Fall ist, wird diese Position ausgegeben. Falls keine Übereinstimmung mit einem Zeichen des Pattern und dem des Teilstrings festgestellt wird, wird der Substring ab der nächsten Position in S betrachtet usw.Wenn n die Länge von S ist und m die Länge von P, d.h. |S|=n und |P|=m, dann gibt es n-m+1 mögliche Werte von s, die darauf überprüft werden müssen, ob die Bedingung P P[1, ... ,m] == S[s+1, ... ,s+m] erfüllt ist.

Der naive Algorithmus 4.1 geht jedes Zeichen im String S durch und überprüft, ob das Pattern P ab dieser Position mit dem folgenden Teilstring in S übereinstimmt. Fall ja, so wird diese Position ausgegeben. D.h. es werden alle möglichen n–m+1 mögliche Werte von s überprüft, ob die Bedingung P[1, ... ,m] == S[s+1, ... ,s+m]

23

15 [9] Seite 79.

erfüllt ist. Bei diesem Algorithmus wird jede Position explizit betrachtet, daher ergibt sich eine Worst-Case Laufzeit von O((n–m+1)m).Wenn wir einen String S=an (d.h. der String S besteht aus n a‘s) und ein Pattern P=am haben, dann gibt es n-m+1 mögliche Werte für s. Außerdem muss die for-Schleife jedes mal n Zeichenvergleiche ausführen, um festzustellen, ob das Pattern mit dem folgenden Substring von S übereinstimmt. Daher ergibt sich eine Laufzeit von Θ((n-m+1)m). Dass diese Laufzeit sehr schlecht ist, erkennt man, wenn man für m=⎣n/2⎦ wählt. Damit ergibt sich durch Einsetzen eine Laufzeit von Θ(n2). Bei diesem Algorithmus findet keine Vorverarbeitung der Strings S statt, sodass die Laufzeit gleich der Matching-Zeit ist.Es ist erkennbar, dass der naive Algorithmus keine optimale Lösung für das String-Matching-Problem ist, da bei sehr großen Strings die Laufzeit zu hoch wird. Abgesehen von der Laufzeit hat dieser Algorithmus den Nachteil, dass die während der Überprüfung des Pattern P erhaltenen Informationen über den String S später nicht berücksichtig und verworfen werden, wenn die nächste Position betrachtet wird. Beispielsweise haben wir ein Pattern P=aaab und wissen bereits, dass s=0 eine gültige Position in S ist. Dann ist klar, dass 1, 2, 3 keine gültigen Positionen für s sein können, ab dem P als Substring vorkommen kann, weil S[4]=b ist.

Algorithmus 4.1: Naive String-Matching-Algorithmus

NAIVE-STRING-MATCHER(S, P) n ← length(S) m ← length(P) for s ← 0 to n – m do if P[1, ... ,m] == S[s+1, ... ,s+m] print „Das Muster tritt auf ab Position:“ s

Beispiel 4.1: Arbeitsweise des naiven Algorithmus 4.1

Gegeben ist der String S=acadac und das Pattern P=ada. Das Pattern wird ab jeder Position in S überprüft, ob der folgende Substring übereinstimmt. Die graumarkierten Zeichen stellen die bereits auf Gleichheit überprüften Zeichen dar. Die gezackte Linie steht für ein Miss-Match, worauf der Zeichenvergleich mit dem Pattern abgebrochen wird und zur nächsten Position in s gewechselt wird. In diesem Beispiel werden wir in s = 3 fündig. Ab dieser Position finden wir einen Teilstring der mit dem Pattern identisch ist.

4.3 Effiziente String-Matching-Algorithmen

Der erste naive Algorithmus für das String-Matching-Problem ergab eine schlechte Laufzeit, die bei sehr großen Strings nachteilig ist. Für große Datenmengen, die sich

24

a c a d a c a c a d a c a c a d a c

a d as = 0

a d as = 1 s = 3

a d as = 4 ...

über die Zeit nicht verändern, aber oft genutzt werden, kann eine Vorverarbeitung hilfreich sein, um die Laufzeit des String-Matching-Algorithmus zu verringern. Der Aufwand für die Vorverarbeitung ist zwar etwas hoch, jedoch lohnt sich dieser, wenn später ganz oft darauf zugegriffen wird. In Kapitel 3 wurden das Suffix Array, Inverse Suffix Array und LCP-Array vorgestellt. Diese können für einen Text bzw. String S erzeugt und gespeichert werden. Im folgenden werden zwei Algorithmen vorgestellt, die diese Datenstrukturen nutzen, um eine bessere Laufzeit für String-Matching-Algorithmen zu erreichen. In Kapitel 4.3.1 wird gezeigt, wie durch die Verwendung von Suffix Arrays eine Laufzeit von O(m*log(n)) erreicht werden kann. In Kapitel 4.3.2 wird gezeigt, dass eine Laufzeit von O(m+log(n)) möglich ist, wenn neben dem Suffix Array auch das LCP-Array verwendet wird. Diese Algorithmen und Definitionen sind aus [9] übernommen und erklärt worden.

4.3.1 Binäre Suche im Suffix Array

Um alle Vorkommen eines Pattern P im String S zu suchen, kann man dieses Pattern im Suffix Array von S suchen. Dabei sucht man alle Suffixe, die das P als Präfix haben. Findet man anstelle von SA[i] ein Suffix, dass P als Präfix hat, so kann der Wert s=SA[i] ausgegeben werden, dabei gibt es die Position in S an, ab dem P als Substring vorkommt. Der Vorteil im Suffix Array zu suchen liegt darin, dass die Suffixe lexikographisch sortiert sind, d.h. SSA[1] < SSA[2] < ... < SSA[n] (mit n=|SA|). Deshalb ist es möglich mit binärer Suche nach dem Pattern in SA zu suchen.

Um den dazugehörigen Algorithmus zu verstehen, werden wir zwei Variablelp = min({i|P≤SSA[i]}∪{n+1}) und rp = max({i|SSA[i]≤P}∪{0}) definieren.

Lemma 4.1: Ein Pattern P kommt in S vor, genau dann, wenn das Intervall [lp, ... ,rp] nicht leer ist. Falls dies der Fall ist, dann sind die Postionen, ab denen das Pattern P vorkommt, genau SA[lp], SA[lp+1], ... ,SA[rp].

Beispiel 4.2: Gegeben sind S=aaabaaacaa$, P=aa und das Suffix Array von S ISAS=[11,10,9,1,5,2,6,3,7,4,8]. Dann sind lp=3 and rp=7. Da das Intervall [lp, ... ,rp] nicht leer ist, sind alle Positionen, ab denen P als Substring in S vorkommt, folgende: SA[3]=9, SA[4]=1, SA[5]=5, SA[6]=2, SA[7]=6 (d.h. SA[lp], SA[lp+1], ... , SA[rp]).

i SA[i] SSA[i]

1 11 $2 10 a $3 9 a a $4 1 a a a b a a a c a a $5 5 a a a c a a $6 2 a a b a a a c a a $7 6 a a c a a $8 3 a b a a a c a a $9 7 a c a a $10 4 b a a a c a a $11 8 c a a $

25

Der Algorithmus 4.2 berechnet lp und rp durch binäre Suche. FINDLEFTMOST und FINDRIGHTMOST benötigen jeweils O(log(n)) Zeit für die binäre Suche, wobei jedes mal O(m) Zeichen verglichen werden (für n=|S| und m=|P|). Daher ergibt sich eine Worst-Case Laufzeit von O(m*log(n)) um das Intervall [lp, ... ,rp] zu finden. Algorithmus 4.2: String-Matching-Algorithmus mit binärer Suche

FINDLEFTMOST(S, P, SA) FINDRIGHTMOST(S, P, SA) n ← length(S) n ← length(S) m ← length(P) m ← length(P) l ← 1 l ← 1 r ← n r ← n if P ≤m SSA[1] then if P <m SSA[1]then return 1 return 0 if P >m SSA[n] then if P ≥m SSA[n][ then return n+1 return n while r–l > 1 do while r–l > 1 do mid ← ⎣(l+r)/2⎦ mid ← ⎣(l+r)/2⎦ if P ≤m SSA[mid] then if P ≥m SSA[mid] then r ← mid l ← mid else else l ← mid r ← mid return r return l

Beispiel 4.3: Arbeitsweise des Algorithmus 4.2 FINDLEFTMOST(S, P, SA).

Wir suchen im Suffix Array des Strings S=aaabaaaca$ das Pattern P=aa, mit n=|S|=11 und m=|P|=2. Zunächst werden l=1 und r=11 gesetzt und die äußersten Suffixe mit P verglichen. Falls P lexikographisch kleiner oder gleich als die ersten m Zeichen des ersten Suffixes ins SA ist, wird eine 1 ausgegeben. Ist P lexikographisch größer als die ersten m Zeichen des letzten Suffix in SA, so wird n+1 ausgegeben. In unserem Beispiel kommt keiner der beiden Fälle vor. Da die Suffixe lexikographisch sortiert sind, wird durch diesen Schritt vorher überprüft, ob das Pattern in S

26

l = 1i SA[i] SSA[i]

1 11 $2 10 a $3 9 a a $4 1 a a a b a a a c a a $5 5 a a a c a a $6 2 a a b a a a c a a $7 6 a a c a a $8 3 a b a a a c a a $9 7 a c a a $10 4 b a a a c a a $11 8 c a a $r = 11

1

2

3

überhaupt existieren kann. Danach wird P mit dem mittleren Suffix verglichen, ob folgende Bedingung erfüllt ist: P ≤m SSA[1], mit mid = ⎣(l+r)/2⎦. In diesem Fall ist mid=6 und SSA[6][1,2]=aa. Da P=SSA[6][1, 2] wird r=mid gesetzt. Nun wird mit dem selben Verfahren weitergemacht, bis die Zeiger (l und r) sich überholt haben (d.h. wenn r–l >1 nicht mehr gilt). Bei jedem Durchlauf der while-Schleife wird das Intervall halbiert, bis r=3 gefunden ist.

Algorithmus 4.3: Verbesserter String-Matching-Algorithmus mit binärer Suche

FINDLEFTMOST(S, P, SA) FINDRIGHTMOST(S, P, SA) n ← length(S) n ← length(S) l ← 1 l ← 1 r ← n r ← n (hl, fl) ← CMP(P, SSA[l], 0) (hl, fl) ← CMP(P, SSA[l], 0) if fl ≤ 0 then if fl < 0 then return 1 return 0 (hr, fr) ← CMP(P, SSA[r], 0) (hr, fr) ← CMP(P, SSA[r], 0) if fr > 0 then if fr ≥ 0 then return n+1 return n while r–l>1 do while r–l>1 do mid ← ⎣(l+r)/2⎦ mid ← ⎣(l+r)/2⎦ (c, fc) ← CMP(P, SSA[mid], min{hl,hr}) (c, fc) ← CMP(P, SSA[mid], if fc ≤ 0 then if 0 ≤ fc then (hr, r) ← (c, mid) (hl, l) ← (c, mid) else else (hl, l) ← (c, mid) (hr, r) ← (c, mid) return r return l

Algorithmen 4.4: Zusätzliche Funktionen CMP und SASEARCH

CMP(w, sa, c) SASEARCH(S, P, SA) v ← sa$ lp ← FINDLEFTMOST(S, P, SA) while c < min{|w|,|v|} do rp ← FINDRIGHTMOST(S, P, SA) if w[c+1] < v[c+1] then if lp ≤ rp then return (c,–1) for j ← lp to rp do else print „Das Muster tritt auf if w[c+1] > v[c+1] then ab Position SA[j]=“ s return (c,1) else else print „P kommt nicht in S vor“ c ← c+1 return (c,0)

27

min{hl,hr})

Jedoch kann die praktische Laufzeit des Algorithmus 4.2 verbessert werden, wenn wir neben lp und rp die Längen der längsten gemeinsamen Präfixe von den Suffixen SSA[lp] und SSA[rp] berechnen. Alle Suffixe zwischen lp und rp haben den gleichen Präfix der Länge min{hl,hr}. P und SSA[mid] (mit mid = ⎣(l+r)/2⎦) haben daher einen gemeinsamen Präfix der Länge min {hl,hr}. Dieser gemeinsame Präfix kann beim Vergleich von P und SSA[mid] übersprungen werden, wodurch man unnötige Zeichenvergleiche spart. Dieser verbesserte Algorithmus 4.3 benötigt für diese Vorgehensweise noch eine zusätzliche Funktion CMP (in Algorithmen 4.4). CMP(w,v‘,q) vergleicht zwei Strings w und v (v=v‘$) ab der Position q miteinander. D.h., dass w und v einen gemeinsamen Präfix der Länge q haben. Die Ausgabe ist ein Tupel (c,fc), welches folgende Bedingungen erfüllt:- c ist die Länge des längsten gemeinsamen Präfixes von w und v und c ≥ q.- Falls w ein Präfix von v ist, dann ist fc=0- Ansonsten, wenn w kein Präfix von v ist, dann gilt w[c+1] ≠ v[c+1], da v mit $

endet und daher kein Präfix von w sein kann. Es müssen dann zwei Fälle betrachtet werden:

- Falls w[c+1] < v[c+1], dann ist fc= –1- Falls w[c+1] > v[c+1], dann ist fc= 1.

Zusammenfassend gilt für w=P und v= SSA[i] mit 1 ≤ i ≤ n –1 falls P<SSA[i]

fc = 0 falls P ein Präfix von SSA[i]

+1 falls P>SSA[i]

sodass fc≤0 wenn P ≤ SSA[i][1, ... ,i] und 0≤fc wenn SSA[i][1, ... ,i] ≤ P.

Durch die Nutzung vom CMP werden im verbesserten binären Algorithmus unnötige Vergleiche gespart, sodass die praktische Laufzeit verbessert wird. Die Worst-Case Laufzeit bleibt jedoch wie vorher O(m*log(n)).

Die Funktion SASEARCH in Algorithmen 4.4 ruft FINDLEFTMOST und FINDRIGHTMOST auf und gibt alle Positionen des Intervalls [lp, ... ,rp] aus. Die Laufzeit ist linear, da SA[j] mit lp ≤ j ≤ rp höchstens n=|SA| mal aufgerufen wird. Daher beträgt die Laufzeit O(n).

Nimmt man nun alle Algorithmen zusammen, erhält man eine Gesamtlaufzeit von O(m*log(n)) im worst-case. Die lineare Laufzeit von CMP und SASEARCH braucht man nicht zu betrachten, da die obere Schranke der Laufzeit von FINDLEFTMOST und FINDRIGHTMOST bestimmt wird. D.h. die Laufzeit hängt von diesen beiden Funktionen ab. Jedoch wird hier die Berechnung des Suffix Arrays von S nicht berücksichtigt. Wir gingen nämlich davon aus, dass das Suffix Array bereits gegeben ist und wir nur noch darauf zugreifen müssen. Würde die Konstruktion des Suffix Arrays hinzu kommen würde sich die Laufzeit auf O(n*log(n)) leicht verschlechtern, da m ≤ n.

4.3.2 Binäre Suche im Suffix Array mit LCP-Array

Die Lösung des String-Matching-Problems mit der binären Suche im Suffix Array wurde auch von Manber und Myers [8] vorgestellt. Sie zeigten aber auch, dass die in

28

{

Kapitel 4.3.1 genannte Laufzeit weiter verbessert werden kann. Dies geschieht durch die Nutzung des LCP-Arrays. Auch hier gehen wir davon aus, dass das Suffix Array und LCP-Array bereits vorliegen und dem Algorithmus als Eingabe übergeben werden. Daher wird deren Laufzeit bei der Konstruktion nicht berücksichtigt. Algorithmus 4.5: FINDLEFTMOST - Diese Implementierung benötigt weniger Zeichenvergleiche

FINDLEFTMOST(S, P, SA, LCP) n ← length(S) l ← 1 r ← n (hl, fl) ← CMP(P, SSA[l], 0) if fl ≤ 0 then return 1 (hr, fr) ← CMP(P, SSA[r], 0) if fr > 0 then return n+1 while r–l>1 do mid ← ⎣(l+r)/2⎦ (c, fc) ← CMP(P, SSA[mid], min{hl,hr}) if hl ≥ hr then lcpl ← |lcp(SSA[l],SSA[mid])| if lcpl > hl then (c, fc) ← (hl, 1) else if lcpl = hl then (c, fc) ← cmp(P, SSA[mid], hl) else (c, fc) ← (lcpl, –1) else lcpr ← |lcp(SSA[mid],SSA[r])| if lcpr > hr then (c, fc) ← (hr, –1) else if lcpr = hr then (c, fc) ← cmp(P, SSA[mid], hr) else (c, fc) ← (lcpr, 1) if fc ≤ 0 then (hr, r) ← (c, mid) else (hl, l) ← (c, mid) return r

Wir legen als Eingabe einen String S der Länge n=|S| und ein Pattern P der Länge m=|P| fest. Hinzu kommt das dazugehörige Suffix Array SA der Länge n und das LCP-Array der Länge n+1. Die Suffixe liegen lexikographisch sortiert vor, da das Suffix Array gegeben ist, das diese Sortierung angibt. Der Algorithmus 4.5

29

verwendet, wie der vorherige Algorithmus 4.3, die Funktion CMP, um Zeichenvergleiche ab einer bestimmten Position durchzuführen. Außerdem wird die Funktion lcp(u,v) verwendet, die den längsten gemeinsamen Präfix der Strings u und v angibt. Im folgenden betrachten wir nur FINDLEFTMOST, da FINDRIGHTMOST (Algorithmus 4.6) analog dazu ist. Wir sehen, dass zunächst (wie bei Algorithmus 4.3) die Variablen n, l und r bestimmt werden. Die Zeiger l und r befinden sich an den äußersten Suffixen im Suffix Array. Zu Beginn wird überprüft, ob das gesuchte Pattern überhaupt in S vorkommt. Dazu werden die äußersten Suffixe mit P verglichen. Ist P lexikographisch kleiner als oder gleich (fl ≤ 0) die ersten m Zeichen des ersten Suffixes oder lexikographisch größer, als die ersten m Zeichen des letzten Suffixes, kommt P in S nicht vor. Daher wird für r der Wert 1 oder n+1 ausgegeben. Falls dieser Fall nicht eintritt, wird die while-Schleife aufgerufen, in der die eigentliche binäre Suche im Suffix Array stattfindet. Dazu wird vor jedem Durchlauf überprüft, ob die Zeiger sich überholt haben oder nicht (r-l>1). Solange dies nicht geschieht, wird mit der binären Suche fortgefahren. Zunächst wird der mittlere Wert mid bestimmt. Falls hr ≥ hr ist, wird in der linken Hälfte des Suffix Arrays nach dem Pattern gesucht, ansonsten in der rechten. hl gibt die Länge des längsten gemeinsamen Präfix von SSA[l] und P an, d.h. hl = |lcp(SSA[l], P)| und hr = |lcp(SSA[r], P)|. Somit nähert der Algorithmus sich dem Pattern an und verwirft immer eine Hälfte des Suffix Arrays. Nach diesem Schritt wird der längste gemeinsame Präfix lcp(SSA[l], SSA[mid]) berechnet (bzw. lcp(SSA[r], SSA[mid])).

Lemma 4.2: Gegeben ist ein String S der Länge n und dessen LCP-Array, sodass |lcp(SSA[i], SSA[j])| = LCP[RMQLCP(i+1,j)] = mini<k≤j{LCP[k]} für alle 1 ≤ i < j ≤ n gilt.16

Das Lemma 4.2 besagt, dass die Berechnung des lcp von zwei Suffixen SSA[i] und SSA[j] genau der kleinste Wert im LCP-Array in dem Intervall LCP[i+1, ... ,j] ist. Sei l = |lcp(SSA[i], SSA[j])|, dann sind die ersten l Zeichen jedes Suffix zwischen SSA[i] und SSA[j] identisch. Dies ist nur möglich, wenn auch jeweils die benachbarten Suffixe einen lcp-Wert von mindestens l haben. d.h. l ist der kleinste Wert im LCP-Array im Intervall i+1 bis j.

Beispiel 4.4: Seien SSA[i], SSA[j] und m=|SSA[i]|, n=|SSA[j]|. Wenn lcp(SSA[i],SSA[j])=l, dann müssen alle Suffixe, die dazwischen liegen, denselben Präfix haben. D.h. die Werte im LCP-Array in dem Intervall i+1 bis j haben ebenfalls einen Wert von mindestens l.

SSA[i] =

SSA[j] =

30

16 [9] Seite 84.

a1 a2 a3 ... al b1 ... bm

a1 a2 a3 ... al c1 ... cn

l

. . .

. .

. . .

. .

Als Beispiel nehmen wir den String S = aaabaaacaa$ der Länge 11. Wir berechnen lcp(SSA[3], SSA[7]) = 2. Man sieht, dass alle Suffixe, die zwischen den beiden Suffixen SSA[3] und SSA[7] liegen einen gemeinsamen Präfix „aa“ der Länge 2 haben. Die LCP-Werte im Intervall 4 (=i+1) bis 7 (=j) sind größer oder gleich l.

i SA[i] LCP[i] SSA[i]

1 11 -1 $2 10 0 a $3 9 1 a a $4 1 2 a a a b a a a c a a $5 5 3 a a a c a a $6 2 2 a a b a a a c a a $7 6 2 a a c a a $8 3 1 a b a a a c a a $9 7 1 a c a a $10 4 0 b a a a c a a $11 8 0 c a a $12 -1

Um nun den kleinsten Wert in einem Intervall zu suchen, kann die Funktion RMQ verwendet werden (|lcp(SSA[i], SSA[j])| = LCP[RMQLCP(i+1,j)]).

Theorem 4.1: Gegeben ist ein Array A. Nach einem Vorverarbeitungsschritt, der lineare Zeit und linearen Speicher benötigt, kann die Anfrage RMQ(i,j) in konstanter Zeit beantwortet werden.17

Das Theorem 4.1 besagt, dass eine RMQ-Abfrage in konstanter Zeit möglich ist, wenn das LCP-Array dementsprechend vorher bearbeitet wurde. Diese kann direkt nach der Konstruktion des LCP-Array einmalig erfolgen und abgespeichert werden, da der Speicherbedarf sich nicht erhöht. Dieses bearbeitete LCP-Array wird anschließend dem String-Matching-Algorithmus übergeben. Der Algorithmus 4.5 spart somit weitere Schritte, wodurch sich die Laufzeit verbessert.

Nachdem nun die Werte von hl und lcpl (bzw. hr und lcpr) bestimmt wurden, wird das Pattern P mit dem mittleren Suffix SSA[mid] verglichen. Der Algorithmus 4.5 verwendet aber folgendes Lemma 4.4. Dieses Lemma zeigt, dass es in manchen Fällen möglich ist zu bestimmen, ob ein bestimmter String lexikographisch kleiner als ein anderer ist, ohne weitere Zeichen miteinander vergleichen zu müssen.

Lemma 4.3: Seien u,v und w Strings, wobei u lexikographisch kleiner ist als v. Wenn |lcp(u,v)| < |lcp(u,w)|, dann ist w auch lexikographisch kleiner als v.18

31

17 [9] Seite 53.

18 [9] Seite 123.

Beweis Sei k = |lcp(u,v)|. Da u < v gilt, dass das (k+1)-te Zeichen von u kleiner als das (k+1)-te Zeichen von v ist. Zudem folgt die Ungleichung |lcp(u,v)| < |lcp(u,w)|, da das (k+1)-te Zeichen von u mit dem (k+1)-ten Zeichen von w übereinstimmt. D.h. wir haben u[1, ... , k] = v[1, ... , k] = w[1, ... , k] und u[k+1] = w[k+1] < v[k+1]. ▢

Beispiel 4.5: Gegeben ist das folgende LCP-Array des Strings S = aaabaaacaa$. Es gilt |lcp(SSA[4],SSA[6])|<|lcp(SSA[4],SSA[5])| und u ist lexikographisch kleiner als v, wenn entsprechend dem Lemma 4.3 u=SSA[4]=aaabaaacaa$, v=SSA[6]=aabaaacaa$ und w=SSA[5]=aaacaa$ gewählt sind. Wir berechnen k =|lcp(u,v)|=2, d.h. dass die ersten beiden Zeichen von u und v sind identisch. Da u lexikographisch kleiner als v ist, ist das 3.(=k+1) Zeichen von u lexikographisch kleiner als das 3. Zeichen von v (u[2+1]=a < b= v[2+1]). Damit die Ungleichung |lcp(u,v)|<|lcp(u,w)| gilt, muss |lcp(u,w)| mindestens k+1 ergeben. D.h. das 3. Zeichen von v muss mit dem 3. Zeichen von w übereinstimmen (u[2+1]=a=w[2+1]). Damit ergibt sich, dass w auch lexikographisch kleiner als v ist.

i SA[i] LCP[i] SSA[i]

1 11 -1 $2 10 0 a $3 9 1 a a $4 1 2 a a a b a a a c a a $5 5 3 a a a c a a $6 2 2 a a b a a a c a a $7 6 2 a a c a a $8 3 1 a b a a a c a a $9 7 1 a c a a $10 4 0 b a a a c a a $11 8 0 c a a $12 -1

Dieses Lemma wird im Algorithmus verwendet, um zu entscheiden, ob das Pattern P lexikographisch kleiner oder größer als der Suffix SSA[mid] ist, um im nächsten Schritt entweder im nächsten Intervall weiterzusuchen, oder P mit dem aktuellen Suffix zu vergleichen. Im folgenden gehen wir alle Möglichkeiten durch für hl ≥ hr, da der Fall hl < hr analog ist.

Fall 1: lcpl = |lcp(SSA[l], SSA[mid])| > |lcp(SSA[l], P)| = hl

Es gilt SSA[l] < P. Wenn wir gemäß dem Lemma 4.3 u = SSA[l], v = P und w = SSA[mid] wählen folgt, dass SSA[mid] < P ist. Zudem gilt auch |lcp(SSA[mid],P)| = |lcp(SSA[l],P)|. Daher wird l auf den Wert mid gesetzt und hl bleibt unverändert.

Fall 2: lcpl = |lcp(SSA[l], SSA[mid])| = |lcp(SSA[l], P)| = hl

In diesem Fall wissen wir, dass die ersten hl Zeichen von P und SSA[mid] übereinstimmen. Um aber die nachfolgenden Zeichen miteinander zu vergleichen, wird die Funktion CMP(P,SSA[mid],hl) aufgerufen.

32

= u= w= v

Fall 3: lcpl = |lcp(SSA[l], SSA[mid])| < |lcp(SSA[l], P)| = hl

Es gilt SSA[l]<SSA[mid]. Wenn wir gemäß dem Lemma 4.3 u = SSA[l], v = SSA[mid] und w = P wählen folgt, dass P < SSA[mid] ist. Zudem gilt auch |lcp(SSA[mid],P)| = |lcp(SSA

[l],P)|. Daher wird r auf den Wert mid und hr auf lcpl gesetzt. (Der neue hr-Wert ist immer größer als der vorherige.)

Der Algorithmus 4.5 spart viele Zeichenvergleiche. Die Werte von hr und hl werden während der binären Suche nicht kleiner, sondern nur größer, je mehr Zeichen mit dem gesuchten Pattern übereinstimmen. Die Funktion CMP überspringt immer die ersten hl bzw. hr Zeichen, sodass in der binären Suche höchsten m=|P| Zeichenvergleiche durchgeführt werden. Die binäre Suche benötigt O(log(n)) Zeit, wodurch sich eine Gesamtlaufzeit von O(m+log(n)) im Worst-Case ergibt.19

Wir sehen, dass das String-Matching-Problem in O(m+log(n)) Zeit gelöst werden kann, wenn wir erweiterte Suffix Arrays verwenden. Diese müssen aber zunächst konstruiert, vorbearbeitet und gespeichert werden. Dieser Aufwand ist jedoch gering, wenn nachfolgend sehr oft String-Matching durchgeführt wird.

33

19 [9] Seite 123.

Algorithmus 4.6: FINDRIGHTTMOST - benötigt weniger Zeichenvergleiche

FINDRIGHTMOST(S, P, SA, LCP) n ← length(S) l ← 1 r ← n (hl, fl) ← CMP(P, SSA[l], 0) if fl < 0 then return 0 (hr, fr) ← CMP(P, SSA[r], 0) if fr ≥ 0 then return n while r–l>1 do mid ← ⎣(l+r)/2⎦ (c, fc) ← CMP(P, SSA[mid], min{hl,hr}) if hl ≥ hr then lcpl ← |lcp(SSA[l],SSA[mid])| if lcpl > hl then (c, fc) ← (hl, 1) else if lcpl = hl then (c, fc) ← cmp(P, SSA[mid], hl) else (c, fc) ← (lcpl, –1) else lcpr ← |lcp(SSA[mid],SSA[r])| if lcpr > hr then (c, fc) ← (hr, –1) else if lcpr = hr then (c, fc) ← cmp(P, SSA[mid], hr) else (c, fc) ← (lcpr, 1) if fc ≥ 0 then (hl, l) ← (c, mid) else (hr, r) ← (c, mid) return l

34

5. Implementierung in Haskell

Für diese Bachelorarbeit wurden die wichtigsten Algorithmen aus den vorherigen Kapiteln in der funktionalen Programmiersprache Haskell20 implementiert und auf Laufzeit und Speicherverbrauch getestet. Im diesem Kapitel wird der Haskell-Code für das LCP-Array, SASEARCH, CMP und jeweils 2 verschiedenen FINDLEFTMOST vorgestellt und erklärt. Anschließend werden die Testergebnisse der zwei String-Matching-Algorithmen (aus den Kapiteln 4.3.1 und 4.3.2) miteinander verglichen.

5.1 Haskell-Code

5.1.1 LCP-Array (Algorithmus 3.5)

Der Algorithmus 3.5 kann in zwei Abschnitte unterteilt werden. Im ersten Abschnitt wird das Inverse Suffix Array konstruiert und im zweiten das LCP-Array. Als Datenstruktur für S, SA, ISA und LCP wurde Data.Map 21 (Map hat den Typ Map k a) verwendet, da der Zugriff und andere Operationen darauf entweder in O(log(n)) oder in konstanter Zeit erfolgen, da die Einträge in einer Baumstruktur gespeichert werden.

Code 5.1: Inverses Suffix Array ISA

create_ISA :: Ord k => Map k Integer -> Map Integer k -> Integer -> Map k Integer

create_ISA isa sa i = if i > (toInteger ((size sa))) then isa else create_ISA (insert (sa!i) i isa) sa (i+1)

Code 5.1 zeigt die Funktion create_ISA die als Eingabe eine leere Map (isa), einen Suffix Array (sa) und einen Wert i erwartet, der am Anfang den Wert 1 hat und bei jedem rekursiven Aufruf um 1 erhöht wird. Dieser Wert dient einerseits als Abbruchbedingung der Rekursion, da im Fall i > (toInteger ((size sa))) das Inverse Suffix Array ausgegeben wird. Andererseits ist i der Wert, der mit dem Index (sa!i) in ISA abgespeichert wird.Die Funktion insert erwartet einen Index, einen Wert (i) und eine Map, in der der Wert zusammen mit dem Index gespeichert wird. Der Typ von insert ist insert :: Ord k => k -> a -> Map k a -> Map k a. Beispielaufrufe: Aus SA = [3,6,4,7,1,9,2,5,8] wird ISA = [5,7,1,3,8,2,4,9,6] konstruiert. empty ist eine leere Map die der Funktion create_ISA übergeben wird.

*Main> sa fromList [(1,3),(2,6),(3,4),(4,7),(5,1),(6,9),(7,2),(8,5),(9,8)] *Main> create_ISA empty sa 1 fromList [(1,5),(2,7),(3,1),(4,3),(5,8),(6,2),(7,4),(8,9),(9,6)]

35

20 http://haskell.org (zuletzt besucht 2.5.2014)

21 https://hackage.haskell.org/package/containers-0.4.0.0/docs/Data-Map.html (zul. besucht 2.5.2014)

Im zweiten Abschnitt wird das LCP-Array konstruiert. Die Funktion create_LCP in Code 5.2 erwartet als Eingabe zwei Variablen i und l, den String S (s), SA (sa) und ISA (isa) und ein leeres LCP-Array (lcp). Wie bei create_ISA gibt es auch hier ein i, welches als Abbruchbedingung dient, da bei i=0 die Rekursion stoppt und das LCP-Array ausgeben wird. l ist eine Zahl, die angibt wie viele Zeichen der aktuelle Suffix mit seinem lexikographischen Vorgänger gemeinsam hat. create_LCP verwendet zwei Hilfsfunktionen comp und maxi. comp vergleicht den String s ab Position (k+l) und (i+l) miteinander. comp ruft sich rekursiv auf und erhöht l um 1, wenn auch die nächsten Zeichen identisch sind. Die Ausgabe von comp ist l. maxi wird eine Zahl l übergeben und gibt die größere Zahl aus, entweder (l-1) oder 0.Die Funktion create_LCP ruft sich rekursiv auf, bis bei i=0 lcp ausgegeben wird. ineu erhöht sich bei jedem Durchlauf um 1 und wird für die Berechnung von j verwendet. Ist j größer als 1 wird der Suffix Sj betrachtet (sa!(j-1)). D.h. alle Suffixe werden vom größten bis zum kleinsten durchlaufen. Mit comp wird der aktuelle Suffix mit dem lexikographischen Vorgänger verglichen und das Ergebnis wird mit dem Index i in lcp gespeichert.

Code 5.2: Inverse Suffix Array ISA

create_LCP :: (Eq a1, Num a, Ord a) => Integer -> Map Integer a1 -> Map a Integer -> Map Integer a -> Map a Integer -> Integer -> Map a Integer

create_LCP 0 s sa isa lcp l = lcp create_LCP i s sa isa lcp l = create_LCP (i-1) s sa isa lcpneu lneu where ineu = (toInteger (size sa))+1 - i j = isa!ineu lcpneu = if j > 1 then insert j (comp s (sa!(j-1)) l ineu) lcp else lcp lneu = maxi (lcpneu!j)

comp :: (Eq a, Num k, Ord k) => Map k a -> k -> k -> k -> k comp s k l i = if s!(k+l) == s!(i+l) then comp s k (l+1) i else l

maxi :: (Num a, Ord a) => a -> a maxi l = maximum [(l-1),0]

Beispielaufruf: Das LCP-Array vom String S=ctaataatg$ wird zunächst mit dem Wert (-1) an Position 1 und n+1 (mit n=|S|) erzeugt. Danach wird create_LCP aufgerufen.

*Main> let lcp_empty = fromList [((toInteger 1),-1),((toInteger (size sa)+1),-1)] *Main> lcp_empty fromList [(1,-1),(10,-1)] *Main> let s = fromList (zip [1..] "ctaataatg$") *Main> s fromList [(1,'c'),(2,'t'),(3,'a'),(4,'a'),(5,'t'),(6,'a'),(7,'a'),(8,'t'),(9,'g'),(10,'$')] *Main> create_LCP 9 s sa isa lcp_empty 0 fromList [(1,-1),(2,3),(3,1),(4,2),(5,0),(6,0),(7,0),(8,4),(9,1),(10,-1)]

36

5.1.2 SASEARCH und CMP (Algorithmen 4.4)

Code 5.3: SASEARCH und CMP

sasearch :: (Ord a, Ord t) => Map t a -> Map Integer a -> Map Integer t -> [t] sasearch s p sa = if l_p <= r_p then [ sa!x | x <- [l_p..r_p] ] else [] where l_p = findleftmost s p sa r_p = findrightmost s p sa

comp :: (Eq a, Num k, Ord k) => Map k a -> k -> k -> k -> k cmp w v c = if (c < toInteger ( minimum [size w, size v])) then if w!(c+1) < v!(c+1) then (c,-1) else if w!(c+1) > v!(c+1) then (c,1) else cmp w v (c+1) else (c,0)

sasearch hat als Eingabe den String s, das Pattern p und das Suffix Arrays sa. Die Funktion berechnet lp (l_p) und rp (r_p) und gibt alle Werte von SA[lp, ... ,rp] aus. cmp ist eine rekursive Funktion und vergleicht zwei Strings w und v miteinander ab der Position c. Als Ausgabe wird ein Tupel (c,a), mit a ∈ {-1,0,1} ausgegeben, wobei c mitzählt, wie viele Zeichen bei beiden Strings identisch sind, d.h. c erhöht sich bei jedem positiven Zeichenvergleich um 1. Der Wert a hängt davon ab, ob das zuletzt verglichene Zeichen von w kleiner, größer als oder gleich das Zeichen von v ist. Bei einem Miss-Match wird die Rekursion abgebrochen und das Ergebnis ausgegeben.

Beispielaufruf: Gegeben sind w = aababc, v = aabacb und c = 2. Wir gehen davon aus, dass bereits bekannt ist, dass die ersten beiden Zeichen von w und v identisch sind, daher wurde c = 2 gewählt.

*Main> let w=fromList (zip [1..] "aababc") *Main> let v=fromList (zip [1..] "aabacb$") *Main> let c=2 *Main> cmp w v 2 (4,-1)

5.1.3 FINDLEFTMOST (Algorithmus 4.3)

findrightmost wurde analog zu findleftmost implementiert. Daher wird nur der Code von findleftmost erklärt (Code 5.4).findleftmost benötigt als Eingabe S, P und SA. Im „where“-Block werden die Variablen r, l, h_l, f_r und h_r, f_r berechnet. Die Werte f_l und f_r geben an, ob das gesuchte Pattern P in S vorkommt oder nicht. Ist eine der beide Bedingungen

37

(f_l <= 0) und (f_r > 0) erfüllt wird direkt 1 oder r+1 ausgegeben. Ist dies nicht der Fall, wird binsearchleft aufgerufen, das die eigentliche binäre Suche im Suffix Array SA durchführt. binsearchleft entspricht der while-Schleife im Algorithmus 4.3 und ist eine rekursive Funktion. Bei jedem Durchlauf wird ein neuer mid-Wert berechnet und das Pattern mit dem Suffix SSA[mid] verglichen ((c,f_c)= cmp p (suffix s (sa!mid)) (minimum[h_l,h_r])). Das Ergebnis des Vergleichs (c,f_c) wird genutzt um zu entscheiden ob die binäre Suche im linken oder rechten Teil des SA fortgesetzt wird. D.h. ist f_c <= 0 wird binsearchleft mit neuen (h_r,r)-Werten aufgerufen. Die neuen Werte sind genau (c,mid). Das bedeutet, dass der rechte Teil von SA nicht mehr betrachtet wird und im linken Teil nach dem Pattern gesucht wird. Falls die Bedingung (f_c <= 0) nicht erfüllt ist, wird im rechten Teil weitergesucht und (h_l,l) mit (c,mid) ersetzt und binsearchleft aufgerufen. Die Rekursion endet, wenn (r-l)>1 nicht mehr wahr ist, d.h. r hat l überholt. binsearchleft gibt den Wert r zurück.

Code 5.4: FINDLEFTMOST (Algorithmus 4.3)

findleftmost :: (Ord a, Ord a1) => Map a1 a -> Map Integer a -> Map Integer a1 -> Integer findleftmost s p sa = if (f_l <= 0) then 1 else if (f_r > 0) then r+1 else binsearchleft (h_l,l) (h_r,r) s p sa where r = toInteger (size s) - 1 l = 1 (h_l,f_l) = cmp p (suffix s (sa!l)) 0 (h_r,f_r) = cmp p (suffix s (sa!r)) 0

binsearchleft :: (Integral a2, Ord a, Ord a1) => (Integer, a2) -> (Integer, a2) -> Map a1 a -> Map Integer a -> Map a2 a1 -> a2 binsearchleft (h_l,l) (h_r,r) s p sa = if (r-l) > 1 then if f_c <= 0 then binsearchleft (h_l,l) (c,mid) s p sa else binsearchleft (c,mid) (h_r,r) s p sa else r where mid = div (l+r) 2 (c,f_c) = cmp p (suffix s (sa!mid)) (minimum[h_l,h_r])

5.1.4 FINDLEFTMOST (Algorithmus 4.5)

findrightmost wurde analog zu findleftmost implementiert. Daher wird folgenden nur findleftmost erklärt. Im Gegensatz zur vorigen findleftmost-Funktion arbeitet diese mit weniger Zeichenvergleiche und hat eine Eingabe mehr: das LCP-Array, dessen Implementierung in Kapitel 5.1.1 vorgestellt wurde. Abgesehen davon haben beide findleftmost identische Funktion.

38

Code 5.5: FINDLEFTMOST (Algorithmus 4.5)

findleftmost :: (Ord a1, Ord a) => Map a a1 -> Map Integer a1 -> Map Integer a -> SegTree -> Integer

findleftmost s p sa lcp = if (f_l <= 0) then 1 else if (f_r > 0) then r+1 else binsearchleft (h_l,l) (h_r,r) s p sa lcp where r = toInteger (size s) - 1 l = 1 (h_l,f_l) = cmp p (suffix s (sa!l)) 0 (h_r,f_r) = cmp p (suffix s (sa!r)) 0

binsearchleft :: (Integral a1, Ord a, Ord a2) => (Integer, a1) -> (Integer, a1) -> Map a a2 -> Map Integer a2 -> Map a1 a -> SegTree -> a1

binsearchleft (h_l,l) (h_r,r) s p sa lcp = if (r-l) > 1 then if (h_l >= h_r) then if (lcp_l > h_l) then hf (h_l,1) else if lcp_l == h_l then hf (cmp p v h_l) else hf (lcp_l, -1) else if (lcp_r > h_r) then hf (h_r,-1) else if (lcp_r == h_r) then hf (cmp p v h_r) else hf (lcp_r,1) else r where mid = div (l+r) 2 lcp_l = rmqLinear l mid lcp_r = rmqLinear mid r -- Hilfsfunktionen: v = suffix s (sa!mid) hf (c,f_c) = if (f_c <= 0) then binsearchleft (h_l,l) (c,mid) s p sa lcp else binsearchleft (c,mid) (h_r,r) s p sa lcp rmqLinear i j = minimum [lcp!k | k <- [i+1..j]]

suffix :: (Enum k, Num k, Ord k, Ord a1) => Map a1 a -> a1 -> Map k a suffix s i = fromList (zip [1..] (snd (unzip (toList (filterWithKey (\k _ -> k >= i) s)))))

binsearchleft (Code 5.5) führt die binäre Suche im Suffix Array aus. Die Hilfsfunktion hf übernimmt die Entscheidung ob im rechten oder linken Teil des

39

Suffix Arrays weitergesucht wird. rmqLinear gibt den kleinsten Wert vom LCP-Array LCP[i+1, ... ,j] aus. suffix s i ist eine Hilfsfunktion die einen String s und eine Zahl i erwartet und den Suffix Si von S ausgibt. Hierbei muss der Index neu eingefügt werden, da dieser sonst ab dem Wert i aufsteigt. filterWithKey filtert alle Einträge, die einen Index (key) kleiner oder gleich i haben. toList ändert Map zu einer Liste um, d.h. aus der Form fromList [(1,a1),(2,a2),...,(n,an)] wird [(1,a1),(2,a2),...,(n,an)]. Dies ist nötig, da die folgenden Funktionen nur auf Listen arbeiten und nicht auf Map angewendet werden können. unzip teilt die Tupel in dieser Liste in zwei Listen. Eine Liste enthält die Indizes und eine die Werte, d.h. aus [(1,a1),(2,a2),...,(n,an)] wird ([1,2,...,n],[a1,a2,...,an]). snd gibt das zweite Element aus und mit zip [1..] wird die Liste mit den neuen Indizes ab 1 aufsteigend verknüpft. Anschließenden wird fromList an dieser Liste drangehängt, damit der Typ Map vollständig wird und anschließend ausgegeben wird.binsearchleft arbeitet genau wie der Algorithmus 4.5. Die while-Schleife wurde durch die rekursive Funktion binsearchleft umgesetzt und bricht ab, sobald die Bedingung (r-l) > 1 eintrifft. Dann wird der Wert r ausgegeben.

5.1.5 Weitere Implementierungen

Die Funktion rmqLinear die in Code 5.5 vorgestellt wurde benötigt im Worst-Case lineare Zeit, wodurch sich die Gesamt-Laufzeit des Algorithmus verschlechtert. Gemäß dem Theorem 4.1 kann RMQ auch in konstanter Zeit beantwortet werden, wenn das Array dementsprechend vorverarbeitet wurde. Daher wurde in der eigentlichen Implementierung das LCP-Array nach der Konstruktion zu einer Baumstruktur umgewandelt und SASEARCH übergeben. Dafür wurde im eigentlichen Code eine andere RMQ-Funktion aus [9] übernommen. Auch für die Konstruktion des Suffix Arrays wurde der Haskell-Code aus dem Buch „Pearl“ [3] übernommen, der das Suffix Array in O(n*log(n)) Zeit berechnet. Der übernommene Code berechnet normalerweise das Inverse Suffix Array. Durch die Veränderung der ranktails-Funktion konnte auch das Suffix Array (ranktail) ausgegeben werden.

Code 5.6: Haskell-Code für die SA-Konstruktion wurde aus Pearl... übernommen. ranktail wurde zu ranktails verändert, damit das Suffix Array ausgegeben wird.

-- SA ranktail :: Ord a => [a] -> [Int] ranktail xs = ((concat.applyUntil (all single) (repartitions (n+1)).psort.zip[1..]) xs) where n = length xs

-- ISA ranktails :: Ord a => [a] -> [Int] ranktails xs = (resort n.concat.label.applyUntil (all single) (repartitions n).psort.zip [0..]) xs where n = length xs

Die Gesamtfunktion stringmatch erwartet als Eingabe einen String s_str' und ein Pattern p_str. stringmatch ist für die Vorverarbeitung der Eingabestrings verantwortlich. Zuerst wird s_str' ein Dollar-Symbol bzw. irgendein Symbol

40

drangehängt, welches kleiner als alle anderen Zeichen sein muss. Danach werden s_str und p_str in eine Map umgewandelt und das dazugehörige Suffix Array und LCP-Array konstruiert, die dann der Funktion sasearch übergeben werden. Die Ausgabe von stringmatch ist eine Liste von Zahlen, die die Positionen angeben, ab dem das p_str im String s_str' vorkommt.

Code 5.7: stringmatch für den Algorithmus 4.5

stringmatch :: [Char] -> [Char] -> [Integer] stringmatch s_str' p_str = sasearch s p sa lcp where ---Vorverarbeitung s_str = s_str' ++ [dollar_symbol] s = fromList (zip [1..] s_str) p = fromList (zip [1..] p_str) -- SA sa_list = tail (Prelude.map toInteger (ranktail s_str)) sa = fromList (zip [1..] sa_list) -- ISA i = toInteger (size sa) isa = create_ISA empty sa 1 -------- > LCP-Array erstellen: lcp_empty = fromList [((toInteger 1),-1),((toInteger (size sa) +1),-1)] lcp = create_LCP i s sa isa lcp_empty 0

Die Funktion stringmatch für den Algorithmus 4.3 berechnet das Inverse Suffix Array und das LCP-Array nicht. Der Funktion sasearch werden nur s, p und sa übergeben.

Beispielaufruf: Der Funktion stringmatch werden zwei Strings S und P übergeben. Die Ausgabe ist eine Liste von Zahlen, die die Position angeben, ab dem das Pattern P im String S vorkommt.

*Main> stringmatch "Hallo Welt!" "ll" [3] *Main> stringmatch "Hallo Welt! Hallo Welt? Hallo Welt!" "ll" [27,3,15]

5.2 Tests & Diagramme

Die Testumgebung für die implementierten Algorithmen war ein Mac OS X 10.6.8 mit 2.3 GHz Intel Core i5 Prozessor und 4 GB RAM (1333 MHz DDR3). Die Testaufrufe wurden mit Optimierung im Compiler22 ausgeführt.Die Implementierung von den Algorithmen 4.3 und 4.5 wurde mit verschiedenen Eingabewerten getestet. Als Eingabe wurden verschiedene Stringgrößen und Patterngrößen gewählt.

41

22 Es wurde der Glasgow Haskell Compiler http://haskell.org/ghc verwendet.

Da die Vorverarbeitungszeit der Eingabestrings mitgezählt wird, muss die Patternsuche so oft geschehen, dass die Zeit der Vorverarbeitung im Vergleich zur Suchzeit des Patterns sehr gering ist. Daher wurde für jeden Testaufruf 1000 Patternsuche festgelegt.Die Algorithmen erhielten zufällig erzeugte Strings S der Länge 25,1000,2000, ... ,10000 und Pattern der Länge bis zu 3072 als Eingabe. Dabei wurde die Verarbeitungszeit und der Speicherverbrauch ausgegeben und die Ergebnisse der Algorithmen 4.3 und 4.5 miteinander verglichen. Die Datei, die den Algorithmus 4.3 enthält nennen wir search(.hs) und für Algorithmus 4.5 verwenden wir bettersearch(.hs).Diagramm 5.1 zeigt für die die Patternlänge m=2 und verschiedenen n-Werten, wie viel Zeit und Speicher beide Implementierungen benötigen. Die x-Achse gibt die verschiedenen Größen von String n an. Die Achse gibt die Zeit und die MB an, die das Programm benötigt, bis das Ergebnis ausgegeben wird. Je höher der entsprechende Balken ist, desto mehr Zeit bzw. MB wurde für das Pattern-Matching benötigt. In Diagramm 5.1 sehen wir, dass die Zeitbalken von search und bettersearch bei den selben Eingaben für n unterschiedliche Höhen haben. bettersearch benötigt immer weniger Zeit für die Berechnung im Vergleich zu search. Dabei ist aber der Speicherverbrauch von bettersearch immer etwas höher als bei search. D.h. bettersearch arbeitet eindeutig schneller und findet das Pattern in kürzerer Zeit als search. Der höhere Speicherverbrauch von bettersearch lässt sich dadurch erklären, dass es zusätzliche Daten abgespeichert. bettersearch legt zusätzlich eine LCP-Array an, dessen Konstruktion 13n Bytes benötigt (Kapitel 3.5.5)

Diagramm 5.1: Das zu suchende Pattern hat die Länge 2. Die x-Achse gibt die Größe des Eingabestrings S an. Die y-Achse zeigt die Höhe des Zeit- und Speicherverbrauchs für search und bettersearch.

0102030405060708090

100

25 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

m = 2

Zeit

(s)

n

Zeit bettesearch Zeit search MB bettersearch MB search

42

Die Diagramme 5.2 und 5.3 zeigen für eine Patternlänge von 512 und 3072 ähnliche Ergebnisse wie Diagramm 5.1. Auch hier benötigt bettersearch weniger Zeit für die Patternsuche, jedoch ist der Speicherverbrauch höher als bei search. Eine weitere Beobachtung ist, dass der Speicherverbrauch bei allen 3 Testfällen (Diagramme 5.1, 5.2 und 5.3) fast gleich bleibt und sich kaum vergrößert. Beispielsweise wurde bei n=10000 die 25 MB Grenze nie überschritten. Das liegt daran, dass der Speicherverbrauch hauptsächlich von der Länge n des Eingabestrings S abhängig ist. Denn S wird immer vorverarbeitet, indem Index-Datenstrukturen erzeugt und abgespeichert werden. Für das Pattern P wird keine Index-Datenstruktur angelegt.

Diagramm 5.2: Zeit und Speicherverbrauch für Patternlänge m = 512.

0102030405060708090

100

25 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

m = 512

Zeit

(s)

n

bettesearch search

0

5

10

15

20

25

25 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

m = 512

Spe

iche

rver

brau

ch (M

B)

n

bettersearch search43

Diagramm 5.3: Zeit und Speicherverbrauch für Patternlänge m = 3072.

0102030405060708090

100

25 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

m = 3072Ze

it (s

)

n

bettesearch search

0

5

10

15

20

25

25 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

m = 3072

Spe

iche

rver

brau

ch (M

B)

n

bettersearch search

44

6. Fazit

Ein Beispiel wo sehr oft nach bestimmten Daten gesucht wird, sind Suchmaschinen, wie Google, Yahoo, etc. Da sich aber bei diesen die Daten täglich ändern und neue hinzukommen, ist die Anlegung von Index-Datenstrukturen sogar nachteilig. Bei jeder kleinsten Veränderung der Daten müsste die zeitaufwändige Vorverarbeitung erfolgen. Daraus kann geschlossen werden, dass die Daten nicht nur häufig genutzt werden müssen, sondern auch über sehr lange Zeit unverändert bleiben müssen, damit sich der hohe Aufwand für die Vorverarbeitung der Daten auszahlt. Beispielsweise bleiben in der Bioinformatik, wie an Anfang erwähnt, DNA-Sequenzen, die entschlüsselt und gespeichert wurden unverändert. Auf diese Daten wird später aber sehr oft zugegriffen. Hier ist es sinnvoll erweiterte Suffix Arrays zu konstruieren und mit den eigentliche Daten abzuspeichern. Die Laufzeit für den effizienten String-Matching-Algorithmus (Algorithmus 3.5) ist O(m+log(n)). Diese Laufzeit zeigt ihre Vorteile bei großen Datensätzen, da dann die Laufzeit von String-matching im Vergleich zu anderen Algorithmen kürzer ist.In dieser Bachelorarbeit wurde gezeigt, dass die Konstruktion von erweiterten Suffix Arrays mit effizienten Algorithmen möglich ist. String-Matching-Algorithmen konnten diese Index-Datenstrukturen nutzen, um eine bessere Laufzeit zu erzielen. Die Testergebnisse in Kapitel 5 haben dies bestätigt und gezeigt, dass mit erweiterten Suffix Arrays die Laufzeit immer besser ist, als nur mit der Nutzung eines Suffix Arrays. Daraus kann man schließen, dass es sinnvoll sein kann speichereffiziente Index-Datenstrukturen anzulegen, damit später der Zugriff auf die Dateien viel schneller erfolgt. Die in Kapitel 5 imperativ formulierten Algorithmen ließen sich relativ einfach und mit wenig Quelltext in der funktionalen Programmiersprache Haskell umsetzen. Die Laufzeit mag durch Verwendung einer solchen Programmiersprache leichte Einbußen haben, was aber durch die Kürze und Verständlichkeit des Programmcodes aufgewogen wird.

45

Literaturverzeichnis

[1] Donald A. Adjeroh, Tim Bell, Amar Mukherjee: The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching, Springer Verlag, 2008, ISBN-13: 978-0-387-78908-8, Kapitel 4

[2] Timo Beller: Konstruktion des LCP-Arrays aus der Burrows-Wheeler-Transformierten, Diplomarbeit, Universität Ulm, 27. Juli 2011

[3] Richard Bird: Pearls of Functional Algorithm Design, Cambridge University Press, September 2010, ISBN: 978-0-521-51338-8 (hardback), Kapitel 14

[4] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen - Eine Einführung (3. A.). Oldenbourg Verlag München 2010, ISBN: 978-0-486-59002-9, pp. I-XX, 1-1319, Kapitel 32, S. 997-1001

[5] Roberto Grossi: A quick tour on suffix arrays and compressed suffix arrays. Theor. Comput. Sci. 412(27): 2964-2973 (2011)

[6] Marek Karadžic: Konstruktion von Suffixarrays in linearer Zeit, HU-Berlin, 2005, http://www2.informatik.hu-berlin.de/Forschung_Lehre/wbi/teaching/sose05/se_bioinfo/arbeiten/SuffixArraysLinearTime.pdf (zuletzt besucht am 2. Mai 2014)

[7] N. Jesper Larsson, Kunihiko Sadakane: Faster suffix sorting. Theor. Comput. Sci. 387(3): 258-272 (2007)

[8] Udi Manber, Eugene W. Myers: Suffix Arrays: A New Method for On-Line String Searches. SIAM J. Comput. 22(5): 935-948 (1993)

[9] Enno Ohlebusch: Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag 2013, ISBN 978-3000413162, pp. 1-604

[10] RMQ in Haskell-Code, https://www.hackerrank.com/rest/contests/hindley-mi lne r- f eb14 / cha l l enges / r ange -min imum-que ry /hacke r s / au to t ake r /download_solution, zuletzt besucht am 1. Mai 2014

46

Documents

BACHELORARBEIT · 2020. 12. 15. · Als Grundlage für dieses Thema dient das Buch „Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction“