Anfrage an Christoph Zurnieden zwecks user-interface.html

[mehmet]

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

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

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

ich habe folgende sachen gemacht:

bezugnehmend von der datei ui-string-search.js (auszug):
..
function doSearch(needle, haystack, method){
  switch(method){
    case "regex"  : return linearSearchRegex(needle, haystack);
    case "exact"  : return linearSearchExact(needle, haystack);
    case "first"  : return linearSearchExactFirst(needle, haystack);
    case "binary" : return binarySearch(needle, haystack);
    default       : return -1;
  }
}
..

habe ich die datei ui-user.js (auszug) kommentiert:

...
function searchIt(_Item){
  var Item = _Item;
  var res  = new Array();
  var len  = 0;
  clearHits();
  res = doSearch(Item, pieces, "regex");
//  res = doSearch(Item, pieces, "exact");
//  res = doSearch(Item, pieces, "first");
//  res = doSearch(Item, pieces, "binary");
  if(res){
   ...

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

dank dir im voraus
gruss
mehmet

[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

[mehmet]

hallo christoph,

poo..
ich muss erst das ganze verdauen  8-)

noch eine frage bitte
kann man zwischen klein und großschreibung ignorieren?
die scripts akzeptieren nur exakte eingaben
zb soll nach "Hallo" gesucht werden
könnte man "haLLO" oder "HALLO" oder "hallo" etc..
suchen lassen

achso, was für andere möglichkeiten kannst du mir den für telefonbücher empfehlen

herzliche grüsse aus kölle
mehmet

[Christoph Zurnieden]

Hi,

poo..
ich muss erst das ganze verdauen  8-)

Ich haette noch ein AlkaSeltzer uebrig ... ?

noch eine frage bitte
kann man zwischen klein und großschreibung ignorieren?
die scripts akzeptieren nur exakte eingaben
zb soll nach "Hallo" gesucht werden
könnte man "haLLO" oder "HALLO" oder "hallo" etc..
suchen lassen

Ja, durch vorherige Bearbeitung der Liste und des Suchwortes. Entweder beides gross oder beides klein schreiben. Wenn Du Grosskleinschreibung bei der Ausgabe behalten willst musst Du dann aber eine zweite Liste fuehren (ist bei deiner kurzen Telephonliste ja kein Problem). Eine zum Suchen und eine zur Ausgabe.

achso, was für andere möglichkeiten kannst du mir den für telefonbücher empfehlen

Wenn es so kurz ist wie Deines: bleib einfach bei der Regexsuche, ist das bequemste.

so short

Christoph Zurnieden

[mehmet]

hallo christoph,

Ja, durch vorherige Bearbeitung der Liste und des Suchwortes. Entweder beides gross oder beides klein schreiben. Wenn Du Grosskleinschreibung bei der Ausgabe behalten willst musst Du dann aber eine zweite Liste fuehren (ist bei deiner kurzen Telephonliste ja kein Problem). Eine zum Suchen und eine zur Ausgabe.

gute idee, dank dir

Wenn es so kurz ist wie Deines: bleib einfach bei der Regexsuche, ist das bequemste.

dumme frage! was ist, wenn die datei gross wird (gross/klein)
jetzt nicht mit meinem bsp

gruss
mehmet

[Christoph Zurnieden]

Hi,

Wenn es so kurz ist wie Deines: bleib einfach bei der Regexsuche, ist das bequemste.

dumme frage! was ist, wenn die datei gross wird (gross/klein)

Solche Spielereien mit Javascript eignen sich nicht wirklich fuer groessere Sachen, sowas sollte man schon nach Moeglichkeit auf den Server auslagern, ab einer gewissen Groesse sogar eine ausgewachsene DB in Betracht ziehen.

Aber es geht natuerlich auch mit Javascript. Ich hatte das in meinem Aufsatz mit Iframes geloest, aber da Frames als "deprecated" (missbilligt, abgelehnt) gelten waere die Ausfuehrung ueber DOM vorzuziehen. Ist auch technisch einfacher und viel eleganter.
Die lange Liste wird einfach in mundgerechte Stuecke geteilt, z.B. ganz willkuerlich alphabetisch. Jedes Stueck muss allerdings ein vollstaendig definiertes Javascript-Array sein. Aus der Datei 'liste.js'

  
var foobar = new Array("aa","ae","ba","be","ca","ce");  

Werden so die Dateien listea.js

  
var foobar = new Array("aa","ae");  

listeb.js:

  
var foobar = new Array("ba","be");  

und listec.js:

  
var foobar = new Array("ca","ce");  

Fuer die Suche nimmst Du dann den ersten Buchstaben des Suchwortes, bastelst daraus den Dateinamen und aenderst den Pfad im Scripttag per DOM.
Es koennte sein, das es die Datei nicht gibt, Du in meinem Beispiel 'listed.js' aufrufen moechtest. Am einfachsten ist es daher eine Liste der vorhandenen Dateien zu fuehren (hier reichen auch die Buchstaben) und dagegen zu pruefen.
Ist die Liste recht lang (New Yorker Telephonbuch) koennen auch mehrere Buchstaben genommen werden. Ist die Dateiliste auch zu lang kann diese auf dem gleichem Weg behandelt werden.

Grundsaetzliches Probem dabei ist natuerlich, das eine Regexsuche zwar funktioniert, sie jedoch _jede_ Datei laden muss und durchsuchen. Sinnvoll ist daher nur eine binaere Suche ueber sortierte Daten. (eine tatsaechlich funktionierende Methode waere z.B. ein Suffixtree der gesamten Liste, aber das waere dann in Javascript wirklich ein klein wenig beklopft ;-)

so short

Christoph Zurnieden

[mehmet]

dank dir christoph

gruss

mehmet