Binaere Suche

[Christoph Zurnieden]

Hi,

wie geht's an so einem angenehmen sonnigne tag  8-)

Wie soll's mir gehen, der ich doch arbeiten musste? ;-)

ich habe versucht von der "linearen" suchweise auf die "binäre"
suchweise zu wechseln.

Warum?
Du bist Dir darueber im Klarem, das die binaere Suche nur bei sortierten Daten funktioniert (sortiert nach Zeichenwert, also nicht streng lexikalisch)?

• wie soll es auch sein  - ohne erfolg  8-(

Was fuer einen Fehler hast Du festgestellt?

ich wollte jetzt von der "regex" auf "binary" wechseln
(siehe kommentare) oder muss ich noch was dabei achten

Wie gesagt: die Daten muessen sortiert vorliegen. Sodann funktioniert die binaere Suche nur exakt.
searchIt('bar')
findet nur "bar". Findet jedoch z.B. _nicht_ "BAR", "foobar" oder "foobarbaz"!

Vielleicht bist Du Dir auch nicht ganz im Klarem, wie so eine binaere Suche funktioniert?
Als Beispiel diene diese Liste (/usr/share/dict/words)
Aaron
Ababa
aback
abaft
abandon
abandoned
abandoning
abandonment
abandons
abase
abased
abasement
abasements
abases

Wenn Du nun "abaft" ("hinter" wie in "hinter den Sieben Bergen") darin mit der binaeren Methode suchen willst, faengst Du in der Mitte an. Die Liste hat 14 Mitglieder, die Mitte ist demnach 7 "abandoning" (verlassen, fahren lassen). Jetzt stellst Du fest, welches der beiden Worte das "groessere" ist. Das ist in diesem Fall "abandoning". Warum? Alle Buchstaben haben eine numerische Entsprechung, die in einer Zeichentabelle festgehalten ist. Es gibt, wie kann es anders sein, verschiedene Zeichentabellen, die bekanntesten weil verbreitetsten duerften wohl ASCII, Latin-1 und UTF-8 sein. HTML hat normalerweise den Defaultzeichensatz Latin-1. Der ASCII-Zeichensatz ist eine ordentliche Untermenge von Latin-1 und entspricht den ersten 128 Zeichen:
Dec Hex    Dec Hex    Dec Hex  Dec Hex  Dec Hex  Dec Hex   Dec Hex   Dec Hex
  0 00 NUL  16 10 DLE  32 20    48 30 0  64 40 @  80 50 P   96 60 `  112 70 p
  1 01 SOH  17 11 DC1  33 21 !  49 31 1  65 41 A  81 51 Q   97 61 a  113 71 q
  2 02 STX  18 12 DC2  34 22 "  50 32 2  66 42 B  82 52 R   98 62 b  114 72 r
  3 03 ETX  19 13 DC3  35 23 #  51 33 3  67 43 C  83 53 S   99 63 c  115 73 s
  4 04 EOT  20 14 DC4  36 24 $  52 34 4  68 44 D  84 54 T  100 64 d  116 74 t
  5 05 ENQ  21 15 NAK  37 25 %  53 35 5  69 45 E  85 55 U  101 65 e  117 75 u
  6 06 ACK  22 16 SYN  38 26 &  54 36 6  70 46 F  86 56 V  102 66 f  118 76 v
  7 07 BEL  23 17 ETB  39 27 '  55 37 7  71 47 G  87 57 W  103 67 g  119 77 w
  8 08 BS   24 18 CAN  40 28 (  56 38 8  72 48 H  88 58 X  104 68 h  120 78 x
  9 09 HT   25 19 EM   41 29 )  57 39 9  73 49 I  89 59 Y  105 69 i  121 79 y
 10 0A LF   26 1A SUB  42 2A *  58 3A :  74 4A J  90 5A Z  106 6A j  122 7A z
 11 0B VT   27 1B ESC  43 2B +  59 3B ;  75 4B K  91 5B [  107 6B k  123 7B {
 12 0C FF   28 1C FS   44 2C ,  60 3C <  76 4C L  92 5C \  108 6C l  124 7C |
 13 0D CR   29 1D GS   45 2D -  61 3D =  77 4D M  93 5D ]  109 6D m  125 7D }
 14 0E SO   30 1E RS   46 2E .  62 3E >  78 4E N  94 5E ^  110 6E n  126 7E ~
 15 0F SI   31 1F US   47 2F /  63 3F ?  79 4F O  95 5F _  111 6F o  127 7F DEL

abaft      = 97 98 97 102 116
abandoning = 97 98 97 110 100 ...

Wenn man nun die Buchstaben einzeln aufgrund des so bestimmten Wertes vergleicht sind die ersten drei Buchstaben gleich und beim viertem Buchstaben ist das 'n' "groesser" als das 'f', also ist nach dem Prinzip "abandoning" "groesser" als "abaft". Die Liste ist demnach aufsteigend sortiert, von "kleinstem" Wert zum "groesstem". Deshalb kann die binaere Suche davon ausgehen, das "abaft" "oberhalb" von "abandoning" liegt, aber nicht wo genau. Ganz billig wird deshalb der Teil oberhalb von "abandoning" ebenfalls halbiert (krumme Zahlen sind zu runden) und das dort gefundene Wort genauso geprueft bis das Wort gefunden wurde, oder die Liste am Ende ist.

Das ist sehr schnell, selbst in einer Millionen Eintraegen muessen maximal 14 Vergleiche abgearbeitet werden.

Das gibt es aber natuerlich nicht umsonst! Der Preis ist der, das Du nur exakte Begriffe in einer mit einer bekannten Methode sortierten Liste finden kannst. "Exakte Begriffe" bedeutet natuerlich auch, das bei mehreren gleichen Eintraegen nur der erste gefundene ausgegeben wird. Dem kann natuerlich durch etwas Mischkalkulation entgegnet werden. Findet man einen Begriff schaut man oben und unten nach, ob da der gleiche Begriff vorkommt, nimmt den mit und wiederholt das ganze bis keiner mehr uebrig ist, weder oben noch unten ein gleicher Begriff gefunden wurde. Das ist dann im schlimmstem Falle (in der ganzen Liste ist nur ein einziger Begriff) genauso langsam wie eine lineare Suche. Bei einer gut gemischten Liste, z.B. einem Telephonbuch gibt es fuer einige Begriffe sehr viele Eintraege (Mueller) und fuer andere sehr wenige (Finanzamt), der Zeitgewinn ist da schon erheblich.

Man kann die Suchen auch mit Gewinn hintereinanderschalten. Zuerst eine binaere Suche nach dem exaktem Begriff. Wird so nichts gefunden eine Suche mit Regex. Wird mit der binaeren Suche etwas gefunden und es sind teilweise mehrere gleiche Begriffe in der Liste, kommt die lineare Teilsuche zum Einsatz (die Sachen mit oben und unten). Ist die Liste unsortiert geht' nur mit der linearen bzw Regexsuche und einer Sammlung.

Es gibt natuerlich auch noch andere Suchmethoden, aber die sind hier nicht sonderlich relevant.

so short

Christoph Zurnieden