Suchen und mischen
Sequentielle Suche
Die sequentielle Suche, auch als lineare Suche bekannt, ist ein Algorithmus zum Suchen eines bestimmten Werts in einem Array. Der Algorithmus durchläuft das Array elementweise, beginnend beim ersten Element, und vergleicht jeden Wert mit dem gesuchten Wert. Wenn der gesuchte Wert gefunden wird, wird die Suche beendet und der Index des Werts im Array zurückgegeben. Wenn der gesuchte Wert nicht im Array enthalten ist, gibt die Suche eine Fehlermeldung oder einen speziellen Wert (-1) zurück.
Sequentielle Suche
- Lineares Durchlaufen der Folge
- Funktioniert auch bei unsortierten Folgen
public int search(int e, int[] data) {
for (int i = 0; i < data.length; i++) {
if (e == data[i]) {
return i;
}
}
return NOT_FOUND;
}
Die sequentielle Suche ist ein einfacher und verständlicher Algorithmus, der jedoch ineffizient sein kann, da er das Array elementweise durchläuft. Daher hat die sequentielle Suche eine Komplexität von \( \mathcal{O}(n) \), wodurch sie langsamer als eine binäre Suche (\( \mathcal{O}(\log{n}) \)) ist, es sei denn das Array ist klein.
Für nicht sortierte Arrays ist die sequentielle Suche das einzige funktionierende Suchverfahren.
Aufwand
| Fall | Vergleiche |
|---|---|
| bester Fall | 1 |
| schlechtester Fall | n |
| Durchschnitt (erfolgreiche Suche) | (n + 1)/2 |
| Durchschnitt (erfolglose Suche) | n |
Binäre Suche
Die binäre Suche ist ein Algorithmus zum Suchen eines bestimmten Werts in einem sortierten Array. Der Algorithmus funktioniert durch das Teilen des Arrays in immer kleinere Teile, bis der gesuchte Wert gefunden wird oder bis feststeht, dass der Wert nicht im Array enthalten ist.
Binäre Suche
- Folgt dem Prinzip „teile und herrsche“
- Funktioniert bei einer sortierten Folge
- deutlich schneller als lineare Suche
Der Algorithmus beginnt damit, den mittleren Wert des Arrays zu untersuchen. Wenn der gesuchte Wert gleich dem mittleren Wert ist, wird die Suche beendet und der Index des Werts im Array zurückgegeben. Wenn der gesuchte Wert kleiner als der mittlere Wert ist, wird die Suche im linken Teil des Arrays fortgesetzt. Ist er größer, wird die Suche im rechten Teil des Arrays fortgesetzt.
Der Prozess wiederholt sich, bis der gesuchte Wert gefunden wurde oder bis der Suchbereich auf eine leere Liste reduziert wurde, was bedeutet, dass der gesuchte Wert nicht im Array enthalten ist.
public int search(int e, int[] data) {
int u = 0;
int o = data.length - 1;
while (u <= o) {
int m = (u + o) / 2;
if (data[m] == e) {
return m;
}
else if (data[m] > e) {
o = m - 1;
}
else {
u = m + 1;
}
}
return NOT_FOUND;
}
Die binäre Suche ist ein sehr effizienter Algorithmus, da er die Anzahl der zu untersuchenden Werte mit jedem Schritt halbiert. Im Allgemeinen hat die binäre Suche eine Komplexität von \( \mathcal{O}(\log{} n) \), wodurch sie schneller als eine sequentielle Suche (\( \mathcal{O}(n) \)) ist. Es muss jedoch darauf geachtet werden, dass das Array sortiert sein muss, damit die binäre Suche funktioniert.
Aufwand
| Fall | Vergleiche |
|---|---|
| bester Fall | 1 |
| schlechtester Fall | log2(n) |
| Durchschnitt (erfolgreiche Suche) | log2(n) |
| Durchschnitt (erfolglose Suche) | log2(n) |
Mischverfahren
Ein Mischverfahren
- sollte das ursprüngliche Array vollständig durchmischen
- sollte das ursprüngliche Array zufällig durchmischen
- sollte effizient sein, d. h. möglichst wenig Schritte benötigen
- sollte einfach zu implementieren und zu verstehen sein
Direktes Verfahren
Bei einem direkten Ansatz wird zunächst eine aus den Zahlen von 1 bis n bestehende Liste betrachtet. Nach einer Ziehung einer Zufallszahl zwischen 1 und n wird das entsprechende Listenelement als die erste Zahl der Ergebnispermutation notiert und dieses Element anschließend aus der Liste gestrichen. Im nächsten Schritt wird dann eine uniform verteilte Zufallszahl zwischen 1 und n-1 gezogen, das entsprechende Listenelement als zweite Zahl der Ergebnispermutation notiert und dieses Element ebenfalls wieder gestrichen. Dieses Vorgehen wird fortgesetzt, bis schließlich keine Zahl mehr in der Liste vorhanden ist.
Komplexität: \( \mathcal{O}(n^2) \)
function randperm(n)
P = zeroes(n) // Ergebnispermutation mit Nullen initialisieren
N = [1:n] // Feld mit den Zahlen von 1 bis n
for i = 1 to n // Schleife über die Einträge von P
z = random(n-i+1) // Gleichverteilte Zufallszahl zwischen 1 und n-i+1
P(i) = N(z) // Wähle als nächstes die z-te verbleibende Zahl
N = setdiff(N,N(z)) // Entferne diese Zahl aus den verbleibenden Zahlen
end
return P
public void shuffle(int[] data) {
Random rand = new Random();
int n = data.length;
int[] result = new int[n];
var index = new LinkedList<Integer>();
for (int i = 0; i < n; i++) {
index.add(i);
}
for (int i = 0; i < n; i++) {
int z = rand.nextInt(n - i);
result[i] = data[index.get(z)];
index.remove(z);
}
System.arraycopy(result, 0, data, 0, n);
}
Fisher-Yates-Verfahren
Das Fisher-Yates-Verfahren (auch als Knuth-Shuffle bekannt) ist ein Algorithmus zum Mischen von Daten in einem Array oder einer Liste. Der Algorithmus funktioniert in-place, d. h. er benötigt keinen zusätzlichen Speicherplatz.
Fisher-Yates-Algorithmus ist ein sicheres und effizientes Verfahren für das Mischen von Daten und wird häufig in zufälligen Sampling-Anwendungen und Spiele verwendet.
Komplexität: \( \mathcal{O}(n) \)
function randperm(n)
P = [1:n] // Initialisierung mit der identischen Permutation
for i = n downto 2 // Schleife über die Einträge von P
z = random(i) // Gleichverteilte Zufallszahl 1 <= z <= i
swap(P(i), P(z)) // Vertausche die Zahlen an den Stellen i und z
end
return P
end
Der Algorithmus beginnt an der letzten Stelle des Arrays und wählt dort einen zufälligen Index zwischen 0 und der aktuellen Position aus. Der Wert an der aktuellen Position wird dann mit dem Wert an dem zufällig ausgewählten Index getauscht. Dieser Vorgang wird für jede Position im Array von hinten nach vorn wiederholt. Auf diese Weise werden die Werte im Array zufällig gemischt.
private static void shuffle(int[] data) {
Random rand = new Random();
for (int i = 0; i < data.length-1; i++) {
int randomIndexToSwap = rand.nextInt(data.length);
int temp = data[randomIndexToSwap];
data[randomIndexToSwap] = data[i];
data[i] = temp;
}
}
title: “Textsuche” nav_order: 3 —
Textsuche
Brute-Force-Algorithmus
Der Brute-Force-Algorithmus ist ein einfacher Ansatz zur Textsuche, bei dem jedes Zeichen des gesuchten Musters mit jedem Zeichen des Texts verglichen wird. Der Algorithmus überprüft jede mögliche Übereinstimmung des Musters mit dem Text, indem er das Muster Zeichen für Zeichen mit dem Text vergleicht, beginnend von der ersten Stelle. Wenn eine Übereinstimmung gefunden wird, wird die nächste Stelle des Musters und des Texts verglichen. Dieser Prozess wird fortgesetzt, bis entweder das komplette Muster gefunden wurde oder es eine Abweichung zwischen dem Muster und dem Text gibt.
Der Brute-Force-Algorithmus ist einfach zu implementieren und zu verstehen, aber seine Laufzeitkomplexität ist \( \mathcal{O}(n \cdot m) \), wobei n die Länge des Texts und m die Länge des Musters ist. Daher kann der Algorithmus bei großen Texten und Mustern sehr langsam sein.
Um die Effizienz zu verbessern, gibt es andere, schnellere Algorithmen, wie den Knuth-Morris-Pratt-Algorithmus oder den Boyer-Moore-Algorithmus.
Brute-Force-Algorithmus
- vergleicht jedes Zeichen der Suche mit jedem Zeichen des Textes
- Einfach zu implementieren und zu verstehen
- Komplexität: \( \mathcal{O}(n \cdot m) \)
public int search(String haystack, String needle) {
int n = haystack.length();
int m = needle.length();
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (haystack.charAt(i + j) != needle.charAt(j)) {
break;
}
}
if (j == m) {
return i;
}
}
return NOT_FOUND;
}
Boyer-Moore-Algorithmus
Der Boyer-Moore-Algorithmus ist ein effizienter Algorithmus zur Suche von Mustern in Texten. Er basiert auf zwei Techniken: dem Bad-Character-Heuristik und dem Good-Suffix-Heuristik.
Die Bad-Character-Heuristik nutzt die Tatsache aus, dass bei einer Nichtübereinstimmung zwischen dem Suchmuster und dem Text, das nicht übereinstimmende Zeichen im Text dazu verwendet werden kann, um den Vergleich fortzusetzen, ohne dass der Text erneut von vorne gelesen werden muss.
Die Good-Suffix-Heuristik nutzt die Tatsache aus, dass bei einer Nichtübereinstimmung zwischen dem Suchmuster und dem Text, Teile des Suchmusters, die bereits übereinstimmten, dazu verwendet werden können, um den Vergleich fortzusetzen, ohne dass das Suchmuster erneut von vorne gelesen werden muss.
Der Algorithmus arbeitet von hinten nach vorn und vergleicht das Suchmuster mit dem Text, anstatt von vorn nach hinten zu arbeiten, wie es bei anderen Algorithmen der Fall ist. Dies ermöglicht es, die Bad-Character-Heuristik und die Good-Suffix-Heuristik effektiver anzuwenden.
Der Algorithmus berechnet zunächst die Skip-Tabellen für die Bad-Character-Heuristik und die Good-Suffix-Heuristik, die verwendet werden, um die Menge der Zeichen im Text und im Suchmuster zu überspringen, die bei einer Nichtübereinstimmung verglichen werden müssen. Dann wird der Algorithmus die Zeichen im Text von hinten nach vorn vergleichen und die Skip-Tabellen verwenden, um die Menge der Zeichen zu überspringen, die bei einer Nichtübereinstimmung verglichen werden müssen. Wenn eine Übereinstimmung gefunden wird, wird der Algorithmus das nächste Zeichen im Text und im Suchmuster vergleichen, bis entweder das gesamte Suchmuster im Text gefunden wurde oder alle Zeichen im Text verglichen wurden.
Der Boyer-Moore-Algorithmus ist in der Praxis einer der schnellsten Algorithmen für die Textsuche, insbesondere bei großen Texten und langen Suchmustern.
Boyer-Moore-Algorithmus
- sehr schneller Suchalgorithmus
- führt Vorverarbeitung des Suchstrings durch
- gut geeignet für die Suche von kurzen Strings in langen Texten \( \mathcal{O}(n + m) \)
- verschiebt das Suchfenster in größeren Schritten
Boyer-Moore: Verschiebung
Verschiebung bei Nichtübereinstimmung I
Verschiebung bei Nichtübereinstimmung II
public int search(String haystack, String needle) {
char[] text = haystack.toCharArray();
char[] pattern = needle.toCharArray();
int n = text.length;
int m = pattern.length;
if (m == 0) return 0; // Test for empty string
// Initialization, create Map of last position of each character = O(n)
Map<Character, Integer> last = new HashMap<>();
for (char c : text) {
// set all chars, by default, to -1
last.put(c, -1);
}
for (int i = 0; i < m; i++) {
// update last seen positions
last.put(pattern[i], i);
}
//Start with the end of the pattern aligned at index m-1 in the text.
//index into the text
int i = m - 1;
// index into the pattern
int k = m - 1;
while (i < n) {
if (text[i] == pattern[k]) {
// match! return i if complete match; otherwise, keep checking
if (k == 0) {
return i;
}
i--; k--;
}
else { // jump step + restart at end of pattern
//iterate over text
i += m - Math.min(k, 1 + last.get(text[i]));
//move to end of pattern
k = m - 1;
}
}
// not found
return NOT_FOUND;
}
Boyer-Moore-Algorithmus am Beispiel
Knuth-Morris-Pratt-Algorithmus
Der Knuth-Morris-Pratt (KMP) Algorithmus ist ein effizienter Algorithmus zur Suche von Mustern in Texten. Es basiert auf der Erstellung eines „failure-array“ (Fehlerarray), das Informationen über die übereinstimmenden Teilmuster im Suchmuster enthält. Dies ermöglicht es dem Algorithmus, schnell und effizient die Position im Text fortzusetzen, an der die Übereinstimmung fortgesetzt werden kann, anstatt erneut von vorne zu beginnen, wenn eine Nichtübereinstimmung auftritt.
Der Algorithmus beginnt damit, das failure-array zu berechnen, indem er jedes Teilmuster im Suchmuster vergleicht und die Länge des übereinstimmenden Präfixes und Suffixes ermittelt. Dieses failure-array wird dann verwendet, um schnell die Position im Text fortzusetzen, an der die Übereinstimmung fortgesetzt werden kann, wenn eine Nichtübereinstimmung auftritt.
Der Algorithmus vergleicht dann die Zeichen im Text mit denen im Suchmuster von vorne nach hinten und verwendet das failure-array, um die Position im Text fortzusetzen, an der die Übereinstimmung fortgesetzt werden kann, wenn eine Nichtübereinstimmung auftritt. Wenn eine Übereinstimmung gefunden wird, wird das nächste Zeichen im Text und im Suchmuster verglichen, bis entweder das gesamte Suchmuster im Text gefunden wurde oder alle Zeichen im Text verglichen wurden.
Der KMP-Algorithmus hat eine Zeitkomplexität von O(n) , wo n die Länge des Textes ist, da der Algorithmus jedes Zeichen im Text nur einmal vergleicht. Es ist besonders nützlich, wenn es viele Wiederholungen des Musters im Text gibt.
Im Gegensatz zu anderen Algorithmen wie dem Brute-Force-Algorithmus benötigt der KMP-Algorithmus vorab einen Preprocessing-Schritt, um das failure-array zu berechnen.
Knuth-Morris-Pratt
- Führt zuerst eine Präfix-Analyse durch und Berechnet eine next-Tabelle
- Baut auf der Brute-Force-Suche auf, schiebt das Suchmuster aber in größeren Schritten vorwärts
- Komplexität: \( \mathcal{O}(n) \)
Knuth-Morris-Pratt-Algorithmus am Beispiel
public int search(String haystack, String needle) {
int[] lps = computeLPS(needle);
int i = 0, j = 0;
while (i < haystack.length()) {
if (needle.charAt(j) == haystack.charAt(i)) {
i++;
j++;
}
if (j == needle.length()) {
return i - j;
} else if (i < haystack.length() && needle.charAt(j) != haystack.charAt(i)) {
if (j != 0) {
j = lps[j - 1];
} else {
i = i + 1;
}
}
}
return -1;
}
Berechnung der next-Tabelle
public int[] computeLPS(String pattern) {
int[] lps = new int[pattern.length()];
int j = 0;
for (int i = 1; i < pattern.length();) {
if (pattern.charAt(i) == pattern.charAt(j)) {
lps[i] = j + 1;
i++;
j++;
} else {
if (j != 0) {
j = lps[j - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}