[Algorithmus] Binäre Suche für Zeichenketten

[Luckie]

Hat jemand von euch eine Idee, wie man eine binäre Suche für Zeichenketten realisieren könnte? Das Problem ist ja, dass man Zeichenketten ja nicht auf größer oder kleiner vergleichen kann - oder doch?

[Der.Kaktus]

Hallo Micha,

schau mal hier-->Binarysearch

[Luckie]

Äh, ja mir ist auch gerade eingefallen dass man die Vregleiochsoperatoren auch auf Strings anwenden kann. Hat sich also erledigt.

Aber irgendwas stimmt noch nicht:

Delphi-Quellcode:

function TBSearch.Search(SortedStrArray: TStrArray; s: String): Integer;
var
  left              : Integer;
  middle            : Integer;
  right             : Integer;
  found             : Boolean;
  index             : Integer;
begin
  found := False;
  index := -1;
  left := 0;
  right := Length(SortedStrArray);

  while (left <= right) and (not Found) do
  begin
    middle := left + ((right - left) div 2);
    if (SortedStrArray[middle] = s) then
    begin
      index := middle;
      Found := True;
    end;
    if (SortedStrArray[middle] > s) then
      right := middle - 1
    else
      left := middle + 1;
  end;

  result := index;
end;

Suche ich nach einer Zeichenkette, die nicht vorkommt, bekomme ich gleich beim ersten Vergleich

Delphi-Quellcode:

if (SortedStrArray[middle] = s) then

eine AccessViolation. Irgendwas stimmt da nicht.

[Der.Kaktus]

aender mal die Zeile um

Delphi-Quellcode:

 //middle := left + ((right - left) div 2); 
 middle := (left + right) div 2;

[Luckie]

Ändert nichts an der AV. middle hat auch einen gültigen Wert. Wie kann ein Vergleich eine ASV auslösen?

Zitat:

---------------------------
Benachrichtigung über Debugger-Exception
---------------------------
Im Projekt Project1.exe ist eine Exception der Klasse EAccessViolation aufgetreten. Meldung: 'Zugriffsverletzung bei Adresse 0040465B in Modul 'Project1.exe'. Lesen von Adresse 00000012'. Prozeß wurde angehalten. Mit Einzelne Anweisung oder Start fortsetzen.
---------------------------
OK Hilfe
---------------------------

[marabu]

Hallo Michael,

nimm dir ein Beispiel an der Methode TStringList.Find() - deren Implementierung ist best practise, da der Rückgabewert für Index bei Misserfolg die Stelle bezeichnet, an der die Einfügung vorzunehmen wäre.

Freundliche Grüße

[alzaimar]

Der Vergleich führt nicht zur Zugriffsverletzung, sondern der Versuch, auf das Element 'middle' zuzugreifen, welches dann vermutlich außerhalb des Bereiches ist. Ändere mal diese Zeilen;

Delphi-Quellcode:

left := 0;
right := Length(SortedStrArray);

in

Delphi-Quellcode:

left := Low (SortedStrArray);
right := High(SortedStrArray);

[Luckie]

Zitat:

Zitat von alzaimar

Delphi-Quellcode:

left := Low (SortedStrArray);
right := High(SortedStrArray);

Danke, das scheint es gewesen zu sein. Aber darüber muss ich noch mal nachdenken. ;)

@marabu: Hm, wäre eine Option, allerdings nutze ich den Rückgabewert schon, für die Position, wo das Element gefunden wurde und -1 entspricht "nicht gefunden".

[Der.Kaktus]

..so, nun iss der Code wie bei dem Link von "#2" ;-)

[Amateurprofi]

Michael,
vielleicht solltest du das noch etwas optimieren.

Delphi-Quellcode:

var  ...
     relationship : integer;
begin
   ...
   relationship := CompareStr(SortedStrArray[middle], s);
   if relationship < 0 then begin
      // SortedStrArray[middle] < s
   else if relationship=0 then begin
      // SortedStrArray[middle] = s
   else begin
      // SortedStrArray[middle] > s
   end;
   ...
end;

Warum :
Bei deiner Konstruktion vergleichst du in der While-Schleife die Strings (bis auf den letzten Durchlauf) immer zwei Mal.
So, wie oben dargestellt, vergleichst du die Strings immer nur ein Mal und prüfst danach einen Integerwert, was deutlich schneller geht.

[Luckie]

Wäre möglich, aber dann bräuchte ich wieder CompareStr aus der Unit SysUtils.

[Amateurprofi]

Ja und ?
Warum machst du eine binäre Suche ? Um Speicherplatz zu sparen ?
Ich denke du machst sie aus Performancegründen - und dann schreibst du die Routine so, daß sie möglichst viel Zeit benötigt....
No further comments.

[alzaimar]

Zitat:

Zitat von Amateurprofi

und dann schreibst du die Routine so, daß sie möglichst viel Zeit benötigt....
No further comments.

Na nun. Die Performanceunterschiede dürften nicht meßbar sein. Wenn schon schnell, dann bitte FastCode-Routinen

No further comments (WTF :mrgreen: ).

[Woodman]

Zitat:

Zitat von Luckie

Hat jemand von euch eine Idee, wie man eine binäre Suche für Zeichenketten realisieren könnte? Das Problem ist ja, dass man Zeichenketten ja nicht auf größer oder kleiner vergleichen kann - oder doch?

Du suchst nach Boyer-Moore. Hier findest Du ein Beispiel, das ich bei mir erfolgreich implementieren konnte.

Nachtrag: Und hier ist eine Java-Animation zu diesem Algo

[gammatester]

Zitat:

Zitat von Woodman

Du suchst nach Boyer-Moore.

Nicht ganz: Boyer-Moore sucht Patterns in Strings. Hier wird aber ein ganzer String in einer Liste (bzw Array) gesucht. Formal kann man zwar die Listenstrings zusammenhängen (= ein großer String) und den Suchstring als Pattern verwenden. Selbst das gibt aber ein Problem, wenn der Suchstring zB 'abc' ist und in der Liste zB 'abcd' vorkommt.

Gruß Gammatester