entwickeltes boyer-moore program läuft nich

[Görly]

hey, nun hab ich mich ja lang genug mit dem kmp algo rumgeschlagen das er endlich annähernd vorführbereit ist. jetz gehts an den boyer-moore algo. ich habe mal ein wenig rumprobiert und bin besher so weit gekommen:

Delphi-Quellcode:

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    bt_neu: TButton;
    bt_ende: TButton;
    Memo1: TMemo;
    Label1: TLabel;
    ed_suche: TEdit;
    Label2: TLabel;
    bt_start: TButton;
    bt_text: TButton;
    Label3: TLabel;
    Memo2: TMemo;
    procedure bt_endeClick(Sender: TObject);
    procedure bt_neuClick(Sender: TObject);
    //function BMsearch(Pat, Txt :string) : Longint;
    procedure bt_startClick(Sender: TObject);
    procedure bt_textClick(Sender: TObject);
 //   procedure bt_textClick(Sender: TObject);

  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.bt_endeClick(Sender: TObject);
begin
close;
end;

procedure TForm1.bt_neuClick(Sender: TObject);
begin
memo1.clear;
memo2.Clear;
ed_suche.clear;
end;


                 //wort ,text
function BMsearch(Pat, Txt :string) : Longint;

 var Postable: array[0..255] of longint;
    Patlen : Longint;   //länge des suchstrings
    txtlen : Longint;   //gesamte länge text(anzahl der zeichen)
    index  : longint;   //um das was sich verschiebt
    patindex : Longint;     //wort das gesucht wurde
    position : longint;    //derzeitige position
    b        : Byte;       // Zähler das zeichenanzahl nicht überschritten wird
                           //aus array 255
     y        : Boolean;   //gesuchtes wort gefunden
     x        : integer;
begin
  if pat = '' then
  begin
     BMsearch := 0;
     exit;
  end;
  x :=0; // kein wort gefunden da Anfang
  Patlen := Length(Pat);
  Txtlen := Length(txt);

  for b  := 0 to 255  do
      postable[b] := -1;
      for patindex := 1 to Patlen  do
          Postable[ord(Pat[Patindex])] := Patindex;

  index := 0;




  while (patindex > 0) and (index <= txtlen - patlen) do
    begin

       Patindex := Patlen;
         while (Pat[Patindex] = txt[index + Patindex]) and
              (patindex > 0) do
            //gefunden ergibt sich aus true
  if  (Pat[Patindex] = txt[index + Patindex]) and (patindex > 0)  then y := true;
     if y = true then x + 1;

          begin Dec(Patindex);
           if Patindex >0 then
              begin
              position := Postable[ord(txt[index + patindex])];


                if position = -1 then inc(index,Patindex)
                else if Position > Patindex then inc (index,1)
                else inc(index,patindex - Position);
              end;

        end;


  if Patindex =0 then BMsearch := index +1 else BMsearch :=0;


  end;
  end;



procedure TForm1.bt_startClick(Sender: TObject);

var
pat,txt : string;
begin
 BMsearch(Pat, Txt);  // Zugriff auf Schleife

end;



procedure TForm1.bt_textClick(Sender: TObject);
begin
 memo1.lines.add
('hallo, wie geht es dir?');
end;

end.

könntet ihr mal drüberschaun und eventuell meinen fehler finden bzw. mir sagen das selbst der ansatz faltsch ist ?
ich habe soweit eigentlich nur noch ein problem mit der ausgabe. ich weis nicht wie ich die mache.

danke euch
greetz görly

[edit=SirThornberry]code-tags durch delphi-tags ersetzt - Mfg, SirThornberry[/edit]

[Gausi]

Woher hast du denn diese Methode? Abgesehen davon, dass da diverse Variablen nicht initialisiert wurden und die Einrückung komplett chaotisch ist, fehlen da mindestens ein paar begins und ends. Die Schleifen und If-Konstrukte laufen irgendwie ins Leere.

Und das wichtigste: Das ist nicht Boyer-Moore, allenfalls eine Variante von Boyer-Moore-Horspool. Da fehlt nämlich die Good-Suffix-Strategie

Hier mal eine Implementierung von mir - die Good-Suffix-Regel ist auskommentiert.

Delphi-Quellcode:

function Search_BM(t,p: String): Integer;
var BC: Array[Char] of Integer;
    j, k, m, n: Integer;
    c: Char;
// j: Durchlaufvariable für das Muster
// k: Durchlaufvariable für den Text
// m: Musterlänge
// n: Textlänge 
begin
  m := Length(p);
  n := Length(t);
  
  // Vorbereitung
  for c := low(char) to High(Char) do BC[c] := m;
  for j := 1 to m do BC[p[j]] := m-j;
  (* GS := PreProcess_BM_GoodSuffix(p); *)

  // Suche
  k := m;
  result := 0;

  while k <= n do
  begin
    j := 0;
    while (j < m) and (p[m-j] = t[k-j]) do
      inc(j);
    if (j = m) then
    begin
      result := k-j + 1;
      break;
      // Falls weitere Vorkommen gesucht werden sollen:
      // statt break:
      // Vorkommen "irgendwie ausgeben"  und
      // k := k + m; //alle nicht überlappenden Vorkommen finden
      // k := k + 1; //alle Vorkommen finden 
    end else
      k := k + (*max( GS[m-j],*) max(1, BC[t[k-j]] - j) (*)*);
  end;

Noch ein Edit: Tu dir selbst einen Gefallen, und lies nicht den deutschen Wikipedia-Artikel zu diesem Algorithmus. Die Good-Suffix-Regel ist dort unvollständig, und bei dieser Beschreibung des Algos ist die Laufzeit von O(n) im Worst-Case falsch (die ist dann nämlich O(nm)). Diesen Wiki-Artikel kann man komplett in die Tonne kloppen. Der englische ist schon besser - und da steht ne Qualitätswarnung bei.

[Görly]

also doch wie ichs geahnt habe... danke für die schnelle antwort. ist der qullcode so wie du ihn geposted hast vollständig?(Good-Suffix-Regel ) nich das ich ihn nur komplett kopiern will...aber wie schon gesagt ich hab mich mit dem kmp algo auseinandersetzen müssen und der rest meiner gruppe(noch 2) haben diesen algo. hier erwischt. war vllt vorhin schlecht beschrieben. also i weis ja wie ihr zum thema hausaufgaben steht . doch kann ich ihn angesichts dieser umstände so verwenden?

[Gausi]

Abgesehen davon, dass eben die Good-Suffix-Regel hier fehlt, ist das ein funktionierender Suchalgorithmus, den man zur Boyer-Moore-Familie zählen kann.

Beispiel für die Good-Suffix-Regel:

Code:

Text   : und da abraham abrakadabra sprach, ...
               X====     
Muster : abrakadabra
               (====) (da kommt "abra" wieder vor)
Verschiebung:   abrakadabra

[Görly]

ok dann erstmal danke soweit . werden morgen unser bestes dran setzen auch dieser prog fertig zu bekommen und dann werd i die beiden mal dazu bewegen sich hier auch selbst anzumelden um eventuelle fragen gleich selbst zu stellen.

ach und nebenbei...ist es ok wenn ich immer selbst ein forum aufmache um solche fragen wie diese zu stellen(nachdem ich bei der suche nichts passendes gefunden habe)?

mfg görly

[grenzgaenger]

sag mal für was brauchste das? hab mal 'n test laufen lassen der KMP ist um den faktor 20 langsamer als der standard POS.

wenn du nicht 'n akademischen kramladen machen willst .. würd ich dir raten die ausgelieferten routinen ggf. zu optimieren und das andere zeugs zu lassen wo es ist, im nirwana...

GG

[Gausi]

Bist du sicher, dass deine Implementierung von KMP den Text ganz durchsucht hat, und nicht (wie pos) beim ersten Treffer aufgehört hat? Bei meinen Tests ist KMP um den Faktor 2-3 schneller. Selbst eine einfache Implementierung des "naiven Verfahrens" ist schneller als pos.
KMP ist aber wirklich eher theoretisch interessant, weil das einer der ersten Stringsuche-Algorithmen ist, die eine linare Worst-Case Laufzeit haben. Gegen einen anständig programmierten Boyer-Moore-Horspool oder Sunday kann es nichts ausrichten - zumindest nicht dann, wenn die gesuchten Substrings eine gewisse Länge überschreiten (so 5-10 Zeichen vielleicht).

Pos ist natürlich dann schneller, wenn man in sehr kurzen Texten sucht - dann schlägt die Vorbereitungszeit für KMP durch. Aber ansonsten ist pos was die Performance angeht, ab Texten von 50kb deutlich allen anderen Verfahren unterlegen. Und wenn man in vielen kurzen Texten sucht (z.B. ne Stringlist zeilenweise durchsucht), kann man die Vorbereitung für kmp einmal machen und nur die Suchphase wiederholen.

Zwei Beispiele:

10mb DNS-Sequenz, 300 Zeichen langes Muster. pos: ca. 200ms, kmp: ca. 70ms, "akademischer Kramladen-Algorithmus": knapp 4ms. [edit: hier ist die Einheit natürlich ms, nicht µs]

10kb langer Text, 15 Zeichen langes Muster. pos: 70µs, kmp: 63µs, "anderer akademischer Kramladen-Algorithmus": knapp 7µs.

[Görly]

also die geschwindigkeit spielt bis jetz nur in sofern ne rolle das ich sie angeben muss(messen muss(dazu bräucht ich auch vllt noch einmal ein geschultes auge?! ich poste einfach mal meinen bisherigen versuch im kmp topic)). aber die lehrerin is absolut unfähig sich durchzusetzen und von daher muss das prog nich unbedingt perfekt sein, heißt reicht erstmal für den anfang(von der geschw. her). aber das prob. das es beim 1. erfolg aufhört ist mir schon aufgefallen und wäre genial, wäre es behoben(bei vorschlägen wie oben erwähnt im kmp-topic mal guckn).
weiter zu boyer-moore @gausi ich hab heute mal deinen quellcode eingefügt und da sagte mir das program hinter end else in der letzten zeile:  k := k + (*max( GS[m-j],*) max(1, BC[t[k-j]] - j) (*)*); folgenden fehler:[Fehler] Unit1.pas(59): Undefinierter Bezeichner: 'max'. was muss ich da ändern?

danke görly

[Medium]

Cursor auf "max" platzieren, F1 drücken, darüber ermitteln in welcher Unit die Funktion deklariert ist, und diese dann in deine uses-Liste mit aufnehmen. 1. Schritt beim Standardvorgehen bei dieser Meldung durch kopierten Code. F1 ist ohnehin eine sehr geniale Taste.

[alzaimar]

Zitat von Gausi:

..."anderer akademischer Kramladen-Algorithmus": knapp 7µs.

Könntest Du den mal vorstellen?