Welche Skalierung haben gesuchte Daten sind im Array?
nominal:
Nur Vergleich auf Gleichheit, keine natürliche Ordnung oder Zahlbegriff.
ordinal:
Es gibt Größenvergleiche und damit eine Sortierung, aber kein Zahlbegriff.
kardinal:
Es gibt Größenvergleiche und Zahlbegriff.
Unsortiert oder nominal führt (zunächst) zur linearen Suche.
Ordinale und kardinale Werte können sortiert werden für binäre Suche.
Kardinale Größen können modelliert werden für interpolierende Suche.
Ein Beispiel für eine nominal skalierte Datenmenge wäre die Menge der Farben. Es gibt keine natürliche Ordnung der Farben, und es gibt auch keinen natürlichen Zahlenbegriff, der die Farben beschreibt. Ein weiteres Beispiel ist eine Liste von Wohnorten.4
Ein Beispiel für eine ordinale skalierte Datenmenge wäre die Menge der Kleidergrößen (S,M,L,XL,...). Es gibt eine natürliche Ordnung der Kleidergrößen, aber es gibt keinen natürlichen Zahlenbegriff, der die Kleidergrößen beschreibt. Ein weiteres Beispiel ist die Bewertung von Filmen auf einer Skala von 1 bis 5 Sternen.
Laufzeit ist \(O(\log(n))\), genauer im Schnitt \(\log_2(n)-1\) Zugriffe.
Effizientere Suche bei linearer Verteilung
In diesem Beispiel gehen wir davon aus, dass die Werte im Wesentlichen linear verteilt sind. Das bedeutet, dass die Differenz zwischen zwei aufeinanderfolgenden Werten immer gleich ist.
Sei beispielsweise ein Array a mit folgenden Werten geben (Auszug):
Index i
Wert
i = 10
a[i = 10] = 20.0
...
...
i = 30
49.5
...
...
i = 50
87.2
...
...
i = 70
151.3
...
...
i = 90
169.9
...
...
i = 110
220.0
...
...
i = 130
251.2
Wenn man jetzt exemplarisch die Paare: \((i = 10, a[i] = 20.0)\), und \((i = 110, a[i] = 220)\) betrachtet, dann kann man zu dem Schluss kommen, dass die Funktion \(f(x) = 2.0\cdot x\) eine Approximation der Verteilung der Werte ist. Würde man also nach dem Wert \(a[i] = y = 170\) suchen wollen, dann wäre es gut als erstes den Wert von a[85] zu überprüfen, \(170 = 2\cdot x \rightarrow \frac{170} {2} = 85 = i\).
Effizientere Suche bei exponentieller Verteilung
In diesem Beispiel gehen wir davon aus, dass die Werte im Wesentlichen exponentiell verteilt sind. Das bedeutet, dass die Differenz zwischen zwei aufeinanderfolgenden Werten immer größer wird.
Sei beispielsweise ein Array a mit folgenden Werten geben (Auszug):
index i
a[i]
0
0
...
...
20
5
...
...
50
25
...
...
70
75.7
...
...
90
110
...
...
110
380
...
...
125
579.5
...
...
130
794
Wenn man jetzt exemplarisch die Paare: \((i = 20, a[i] = 5.0)\), und \((i = 130, a[i] = 794)\) betrachtet, und eine lineare Approximation durchführt, dann könnte man zu dem Schluss kommen, dass die Funktion \(f(x) = 6.1\cdot x\) eine gute Approximation ist.
Würde man eine quadratische Approximation mit Hilfe von Lagrange durchführen, zum Beispiel mit den Werten \((i = 20, a[i] = 5.0)\), \((i = 90, a[i] = 110)\) , und \((i = 130, a[i] = 794)\). Dann wäre der Fehler zwischen der realen Verteilung und der angenommen deutlich geringer, da die quadratische Funktion die Werte besser approximiert.
In diesem Fall Fall wäre die Funktion: \(p(x) = \frac{39}{275}x^2 - \frac{141}{10}x + \frac{2533}{11}\)
In diesem Fall können wir die Position des Wertes 650 im Array besser abschätzen (durch die Aufstellung der Umkehrfunktion und dann einsetzen von 650): \(\approx 123\).
Approximation der Verteilung
Interpolation mit Lagrange-Polynomen
Speichert unser Array kardinal skalierte Daten, so können diese modelliert werden. Das einfachste Prinzip ist die Polynominterpolation mittels Lagrange-Polynomen.
Das Ziel ist es, ein Polynom \(p(x)\) zu finden, das eine Funktion \(f(x)\) an einer gegebenen Menge von Punkten \((x_1, y_1), \dots, (x_n, y_n)\)exakt interpoliert. Das heißt:
\begin{equation*}
p(x_i) = y_i \quad \text{für alle } i = 1, \dots, n
\end{equation*}
Sind \(n\) Tupel \((x_n ,y_n ) \in \mathbb{R}^2\) reeller Zahlen gegeben mit \(x_l \neq x_m\) für \(l \neq m\).
Das Lagrange-Interpolationspolynom hat dann höchstens den Grad \(n-1\) und es gilt \(p(x_i ) = y_i\) für alle \(i= 1,...,n\).
Wenn zwei Punkte gegeben sind, ist das Lagrange Polynom somit:
Der Grad unseres Lagrange-Polynoms ist immer um 1 kleiner als die Anzahl der gegebenen Punkte (die Terme des Basispolynom sind nur für \(j \neq i\) definiert). Das bedeutet, dass wir für zwei Punkte ein lineares Polynom erhalten, für drei Punkte ein quadratisches Polynom, für vier Punkte ein kubisches Polynom, und so weiter. Weiterhin stellt die Konstruktion sicher, dass wir durch alle gegebenen Punkte gehen.
Übung
Bestimme p(2)
Bestimmen Sie direkt \(p(2)\) für das quadratische Polynom mit den Eigenschaften:
Eine binäre Suche würde in diesem Fall mit der Position \({40+20 \over 2} = 30\) beginnen.
Interpolierende Suche - quadratische Approxi.
Interpolierende Suche - Vergleich
Auf gleichverteilten Daten hat die lineare Interpolationssuche O(log log n).
Auf anderen Verteilungen ist lineare Interpolation oft schlechter als binäre Suche.
Quadratische Interpolation hat ein erweitertes Modell und schlägt binäre Suche häufig.
Lineare interpolierende Suche
1 AlgorithmlinearInterpolatingSearch(A,needle) 2 lower:=1// index auf das kleinste Element 3 upper:=length(A)// index auf das größte Element 4 vL:=A[lower] 5 ifvL==needlethenreturnlower 6 vU:=A[upper] 7 ifvU==needlethenreturnupper 8 whileupper>lowerdo 9 pos:=round(lower·(needle−vU)/(vL−vU)+10 upper·(needle−vL)/(vU−vL))11 pos:=max(lower+1,min(upper-1,pos))12 value:=A[pos]13 ifvalue==needlethenreturnpos14 elseifvalue<needlethen15 lower:=max(pos,lower+1),vL=A[lower]16 else17 upper:=min(pos,upper-1),vU=A[upper]18 returnnil
Die Korrektur von pos in Zeile 11 (pos:=max(lower+1,min(upper-1,pos))) stellt sicher, dass pos immer strikt zwischen lower und upper liegt. Dies ist insbesondere deswegen notwendig, weil die Interpolation nicht immer exakt ist. Stellen Sie sich zum Beispiel vor, dass die Daten polynomiell skaliert sind und sie (in Unkenntnis der echten Verteilung) die lineare Interpolationssuche verwenden. In diesem Fall kann es zu folgender Situation kommen:
Die Werte im Array seien: [0, 4, 16, 36, 64, 100, 144, 196] (zu Grunde liegt die Funktion \(4x^2\)) und Sie suchen nach dem Wert 194.
Im ersten Schritt würde die lineare Interpolationssuche den Wert 194 auf Position 7 schätzen, was nutzlos wäre, aber erst einmal kein Problem verursachen würde. Da der Wert 194 aber nicht im Array enthalten ist, würde die Suche den Wert für die obere Grenze um eins korrigieren. Jetzt würde die lineare Interpolation aber mit den Werten des Arrays an Stelle 0 und 6 erfolgen (A[0] = 0 und A[6] = 144). Das Ergebnis wäre die 2. Funktion (blau) und der Wert 194 würde auf Position 8 geschätzt, was außerhalb des Arrays liegt.
Folgen die Werte im Array einer logarithmisch Verteilung, dann würde die umgekehrte Situation eintreten, d. h. es könnte am unteren Ende des Arrays zu einem ähnlichen Problem kommen, da dann die Werte oberhalb der geraden liegen würden.
Wenn der berechnete Index außerhalb des Bereichs ist, dann kann der Algorithmus auch einfach nil zurückgeben, da der Wert dann nicht im Array enthalten ist.
Exponentielle Suche im sortierten (unbeschränkten) Array
Die Idee ist erst mit einer exponentiellen Schrittweite zu springen, um dann mit einer binären Suche den Wert zu finden. Die Laufzeit ist \(O(\log(i))\) wobei \(i\) die Position des gesuchten Wertes ist. Die Laufzeit ist also \(O(\log(n))\).
Übung
Wer sucht, der findet 5?
Folgende Werte sind vom Array A bekannt:
\(A[1] = -27,\; A[15] = 13,\; A[29] = 29\)
Gesucht wird der potentielle Index des Wertes 5. Welcher Index i sollte als nächstes untersucht werden bei binärer, linearer oder quadratisch interpolierender Suche?
Gesucht wird der potentielle Index des Wertes -1. Welcher Index i sollte als nächstes untersucht werden bei binärer, linearer oder quadratisch interpolierender Suche?
Implementieren Sie den Algorithmus für die exponentiell interpolierende Suche in einer Programmiersprache Ihrer Wahl. (Ggf. müssen Sie noch die passende binäre Suche implementieren).
Gegeben sei die folgende Funktion, die als Generator fungiert. (\(x\) sei eine natürliche Zahl).
Sind die Daten nominal skaliert, oder sagt die Ordnung der Werte im Array nichts über die Zugriffshäufigkeit aus, so können Arrays auf Basis der Zugriffe sortiert werden.
Erfordert prinzipiell eine lineare Suche, die es gilt soweit möglich zu beschleunigen.
Anwendung(-sgebiete):
Cache-Zugriffe, Verwaltung von virtuellem Speicher
Wenn Werte häufiger verlangt werden als andere, so besitzen die Anfragen eine Wahrscheinlichkeitsverteilung.
Die Verteilung wird durch Abzählen angenähert, da sie nicht bekannt ist. Darauf basierend werden die Werte entsprechend sortiert.
Strategien zur Anordnung
Strategien zur Anordnung - Diskussion
Die FC-Regel erfordert das Mitführen der Häufigkeit der Werte. Die MF-Regel und die T-Regel sind einfacher zu implementieren, da sie nur die Reihenfolge der Werte im Array verändern.
Für MF-Regel und T-Regel gibt es worst-case Aufrufsequenzen, die immer zu den schlechtesten Laufzeiten führen.
Die MF-Regel nimmt eher starke Änderungen vor und reagiert schnell.
Die T-Regel nimmt eher schwache Änderungen vor und ist stabiler.
Übung
A = [1,2,3,4,5] selbstanordnend sortieren
Das Array A=[1,2,3,4,5] soll selbstanordnend sortiert werden. Die gesuchten Werte sind: 1,2,3,2,3,2,1,5. Bestimmen Sie die Anordnung des Arrays nach jedem Zugriff für die Sortierungen nach MF-Regel, T-Regel und FC-Regel. Füllen Sie die nachfolgende Tabelle aus:
Das Array A=[1,2,3,4,5,6] soll selbstanordnend sortiert werden. Danach werden die folgenden Werte in der angegebenen Reihenfolge gesucht: 5,1,6,2,3,6,5. Bestimmen Sie die Anordnung des Arrays nach jedem Zugriff für die Sortierungen nach MF-Regel, T-Regel und
FC-Regel. Füllen Sie die nachfolgende Tabelle aus:
Beispiel bei einfacher Suche nach aaab in aaaaaaaab:
a a a a a a a a b
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
a a a b̶
a a a b̶
a a a b̶
a a a b̶
a a a b̶
a a a b
Sind so viele Vergleiche notwendig?
Knuth-Morris-Pratt Verfahren - Grundlagen
Das Verfahren von Knuth-Morris-Pratt vermeidet unnötige Vergleiche, da es zunächst die Suchwortteile auf den größten Rand, also das größte Prefix, das auch Postfix ist, untersucht.
Beispiel/Idee
Text 010110101
Gesucht/Muster 010101
Übereinstimmung ✓✓✓✓✗
Beobachtungen:
Wir haben an Stelle 5 ein Mismatch.
Wenn wir im Text das Muster um eine Stelle nach rechts verschoben suchen, so haben wir garantiert wieder ein Mismatch.
Beim Mismatch an Stelle 5 kann das Muster „nur“ um 3 Stellen nach rechts verschoben werden.
Beim Mismatch an Stelle 5 kann das Muster um 4 Stellen nach rechts verschoben werden.
Wie weit wir das Muster verschieben können, hängt also vom Rand des Teils des Musters ab, der bereits übereinstimmt.
Beispiel
Das Wort \(aufkauf\) hat die echten Präfixe und Postfixe:
\(\{p^{(k)} : 0 \leq k <n\}=\{\varepsilon ,a,au,auf,aufk,aufka,aufkau\}\)
\(\{q^{(k)} : 0 \leq k <n\}=\{\varepsilon ,f,uf,auf,kauf,fkauf,ufkauf\}\)
und die Ränder:
\(\{r^{(k)} : 0 \leq k <n\}= \{\varepsilon ,auf\}\).
Das bedeutet, dass wenn \(aufkauf\) erkannt wurde, die letzten drei Buchstaben schon den nächsten Treffer einleiten können, wie beispielsweise in \(aufkaufkauf\).
Das KMP-Verfahren fängt nicht immer von vorne an, sondern prüft, ob ein Rand eines Präfixes \(- \varepsilon \) ausgenutzt werden kann. Dazu werden die entsprechenden größten Ränder bestimmt.
Beispiel: ananas
Präfixe \(\setminus \{\varepsilon \}\)
Größter Rand
Länge des Randes
a
ε
0
an
ε
0
a̲na̅
a
1
a̲n̲a̅n̅
an
2
a̲n̲a̲̅n̅a̅
ana
3
ananas
ε
0
Beispiel: axaaxax
Präfixe \(\setminus \{\varepsilon \}\)
Größter Rand
Länge des Randes
a
ε
0
ax
ε
0
a̲xa̅
a
1
a̲xaa̅
a
1
a̲x̲aa̅x̅
ax
2
a̲x̲a̲a̅x̅a̅
axa
3
a̲x̲aaxa̅x̅
ax
2
Die Idee ist also, dass wir beim Musterabgleich nach einem Mismatch, wenn der übereinstimmende
Teil einen Rand hat, beim Abgleich des Musters an einer späteren Stelle - basierend auf der Größe des Randes - weitermachen können. Wir müssen also nicht immer das ganze Muster von vorne anfangen zu vergleichen.
Übung
Ränder und Randlängen bestimmen
Bestimmen Sie die Ränder und die Längen der \(Präfixe - \varepsilon \) für die Worte:
1 AlgorithmComputePrefixFunction(needle) 2 m=length(needle) 3 seiB[1...m]einArray// Array für die Längen der Ränder der Teilworte 4 B[1]=0 5 j=0// j ist die Länge des Randess 6 fori=2,...,mdo 7 j=j+1 8 whilej>0andneedle[j]≠needle[i]do 9 ifj>1then10 j=B[j-1]+111 else12 j=013 B[i]=j14 returnB
Komplexität: \(O(m)\)
1 AlgorithmKMP(text,needle) 2 n=length(text),m=length(needle) 3 B=ComputePrefixFunction(needle) 4 q=0// Anzahl der übereinstimmenden Zeichen 5 R=[]// Ergebnisliste der Indizes der Übereinstimmungen 6 fori=1,...,ndo 7 whileq>0andneedle[q+1]≠text[i]do 8 q=B[q]// ... die nächsten Zeichen stimmen nicht überein 9 ifneedle[q+1]==text[i]then10 q=q+1// Übereinstimmung11 ifq==mthen12 Rappend(i-m+1)13 q=B[q]// Suche nach nächster Übereinstimmung14 returnR
Komplexität: \(O(n+m)\)
Details ComputePrefixFunction
Die Funktion \(ComputePrefixFunction\) berechnet die größten Werte der Präfixe für das Suchwort \(needle\) der Länge \(m\) und gibt diese als Array (\(B\)) zurück.
Das Array \(B\) enthält somit die größten Ränder der Präfixe \(needle[1,...,i]\).
(Der Wert von \(B[1]\) ist immer 0, da es keinen Rand gibt.)
Beispiel für eine KMP-Textsuche
Gesucht wird ananas in saansanananas
s a a n s a n a n a n a s
i ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
1 a̶
...
3 a n̶
...
5 a n a̶
...
11 a n a n a s̶ Beim Auftreten des Mismatch (ln 7) ist
... q=5 und wird auf p[5]=3 (ln 8) gesetzt
13 a n a n a s
Übung
KMP-Algorithmus
Bestimmen Sie die Randlängen der Muster und stellen Sie die Teilschritte bei der Durchführung des KMP-Algorithmus zur Suche des Wortes/Muster im Text dar.
Stellen Sie insbesondere die Fälle dar in denen ein Mismatch auftritt.
Der Algorithmus vergleicht das Muster (Pattern) von rechts nach links mit dem Text.
Viele andere Algorithmen führen die Vergleiche von links nach rechts durch.
Der Boyer-Moore-Algorithmus nutzt dies aus, indem er die Verschiebung des Musters anhand des letzten Zeichens des Musters und des Textes vornimmt.
Wird beispielsweise das Wort Banane im Text Orangen,␣Ananas␣und␣Bananen gesucht, so wird zunächst die Sprungtabelle für das verwendete Alphabet in Bezug auf das Suchwort (Banane mit Länge 6) bestimmt:
Zeichen im Text
␣
,
A
B
O
a
d
e
g
n
r
s
u
Sprung
6
6
6
5
6
2
6
0
6
1
6
6
6
O r a n g̲ e̲ n , ␣ A n̲ a̲ n a̲ s ␣̲ u n d ␣ B̲ a̲ n̲ a̲ n̲ e̲ n̲
B a n a n̶̲ e̶̲
B a n a n e̶̲
B a n a n e̶̲
B a n a n e̶̲
B a n a n e̶̲
B a n a n e̶̲
B a n a n e̶̲
B̲ a̲ n̲ a̲ n̲ e̲
B a n a n e̶̲
Komplexität
Im guten und häufigen Fall erreicht das Verfahren \(O(\frac{n}{m})\), aber in speziellen Fällen ist auch \(O(n·m)\) möglich.
Bei der Sprungtabelle handelt es sich um eine Tabelle, die für jedes Zeichen des Alphabets des Textes die Verschiebung des Musters angibt, wenn das Zeichen im Text mit dem Muster nicht übereinstimmt. Die Zeichen A, O, d, g, r, s, u, , und das Leerzeichen haben die größte Verschiebung, da sie nicht im Muster vorkommen. Das Zeichen e hat die kleinste Verschiebung, da es das letzte Zeichen des Musters ist. Das Zeichen n hat eine Verschiebung von 1, da es im Muster als vorletztes Zeichen vorkommt, das Zeichen a hat eine Verschiebung von 2, da das späteste Vorkommen an drittletzer Stelle ist, und das Zeichen B hat eine Verschiebung von 5, da es nur einmal vorkommt und das erste Zeichen des Musters ist.
Ist das Array sortiert, so ist die Suche nach dem n-ten Element trivial und hat eine Laufzeit von \(O(1)\).
Ist das Array nicht sortiert, so ist die Suche nach dem n-ten Element nicht trivial.
Wir unterscheiden:
wird das Array (im Folgenden) auch noch sortiert gebraucht, so ist es am effizientesten dieses erst zu sortieren, um dann das n-te Element auszulesen. Die Laufzeit beträgt dann - mit der Wahl eines geeigneten Sortierverfahrens - \(O(n \log n)\).
Ist eine Sortierung nicht erforderlich/gewünscht, so können wir mit Hilfe von Teile-und-Herrsche-Verfahren das n-te Element auch effizienter bestimmen.
Suche nach dem n-ten Element mittels Quickselect
1 AlgorithmQuickselect(A,k)// gesucht ist das k größte Element 2 iflength(A)==1thenreturnA[0] 3 pivot:=A[length(A)-1]// ein bel. Element als Pivot (hier das letzte) 4 lows:=[]// Elemente kleiner als Pivot 5 highs:=[]// Elemente größer als Pivot 6 pivotsCount:=0// Anzahl der Pivot-Elemente 7 forxinAdo// Partitionierung ... 8 ifx<pivotthenlows.append(x) 9 elseifx>pivotthenhighs.append(x)10 elsepivotsCount:=pivotsCount+111 12 ifk<length(lows)then13 returnQuickselect(lows,k)14 elseifk<length(lows)+pivotsCountthen15 returnpivot// das k-te Element ist ein Pivot-Element16 else17 returnQuickselect(highs,k-len(lows)-pivotsCount)
Beispielanwendung: Bestimmung des Medians
1 AlgorithmFindMedian(A)// A ist _nicht sortiert_2 n=length(A)3 ifn%2==1then// d. h. wir haben eine ungerade Anzahl von Elementen in A4 returnQuickselect(A,floor(n/2))5 else// gerade Anzahl von Elementen in A6 left=Quickselect(A,floor(n/2)-1)7 right=Quickselect(A,floor(n/2))8 return(left+right)/2
Übung
n-te Element bestimmen
Bestimmen Sie den Median für das Array A = [23,335,2,24,566,3,233,54,42,6,667,7,5,7,7]. Wenden Sie dazu den Algorithmus FindMedian (inkl. Quickselect-Algorithmus) an.
Geben Sie weiterhin nach jeder Partitionierung im Quickselect Algorithmus den aktuellen Zustand an (d. h. nach Zeile 11 in Quickselect).
Zur Bestimmung der Komplexität kann man entweder das Master Theorem anwenden oder die Anzahl der Schritte für die Partitionierung bestimmen und die Summe der Schritte aufstellen.
Geometrische Reihen
Die Summenformel für eine geometrische Reihe (\(S_n = a + ar + ar^2 + \dots + ar^{n-1}\)) lautet:
\begin{equation*}
S_n = a \cdot \frac{1-r^n}{1-r}\quad \text{für}\quad r \neq 1
\end{equation*}
Mit:
\(S_n\):
Summe der ersten \(n\) Glieder der geometrischen Reihe.
\(a\):
Das erste Glied der Reihe.
\(r\):
Der Quotient (Verhältnis aufeinanderfolgender Glieder).
\(n\):
Die Anzahl der Glieder.
Für \(n\) gegen unendlich und \(|r| < 1\) gilt somit:
\begin{equation*}
S = \frac{a}{1-r} \quad \text{für}\quad |r| < 1
\end{equation*}