Knuth-Morris-Pratt Algorithmus

[Görly]

hey leute, hab mich grad hier angemeldet. ich such seit tagen im netz nach einem programm welches angelehnt an dem knuth-morris-pratt algorithmus in texten sucht. denn ich muss zu di. nen vortrag drüber halten. da gibs nur ein problem: ich bin ein nooob in delphi. hat ijemand von euch schon ein prog der art geschrieben?? oder wäre bereit mir ein leichtes zu schreiben??? bitte bitte helft mir. hab schon den algorythmus gefunden: http://delphi.wikia.com/wiki/Knuth-M...ratt_algorithm. nur weis halt echt nich wie man das alles deklariert und die passende maske bildet.
danke görly

[Luckie]

Bitte gib deinem Thread einen aussagekräftigen Titel, in dem du deinen ersten Beitrag entsprechend editierst. Hilfe sucht hier so ziemlich jeder. :?

[Die Muhkuh]

Hi und herzlich Willkommen!

Zuerst einmal: Hilfe braucht hier jeder, deswegen wäre ein Threadtitel, der zu Deinem Problem passt, sehr wünschenswert. ;)

Zum Problem: Deine Hausaufgaben machen wir hier nicht.

Was hast Du denn schon versucht? Wo klemmt es denn?

Die beiden verlinkten Funktionen musst Du nur abkopieren und ein Aufrufbeispiel steht drunter.

Wenn Du nicht weist, wo Du was deklarieren musst etc. pp. wäre eine Grundlagen-Tutorial sehr empfehlenswert. Dazu gibt es viele auf www.delphi-treff.de

[Klaus01]

Hallo,

suchst Du vielleicht diesen KMP algorythmus?

Grüße
Klaus

[Gausi]

Du hast ja nicht nur den Algorithmus verlinkt, sondern fertige Implementierungen. Mehr als Copy&Paste braucht man nicht.

[Görly]

ich danke erstmal für den link von klaus01. und entschuldigung für den misslungennen titel ich bin sehr unerfahren was foren angeht. is sozusagen der 1.^^
dein link is genial! aber wenn i sonen quelltext übernehme dann muss ich doch ne maske zusammenstellen...nur i kann es wirklich überhaupnich. wenn ihr mir da noch hälfen könntet wär das klasse. ich weis das is schon zu viel verlangt. aber es geht nich anders.
danke an alle

ps: kann ich den titel noch nachträglich ändern?

[mkinzler]

Zitat:

ps: kann ich den titel noch nachträglich ändern?

Ja, sönst würde man dich auch nicht dazu auffordern :zwinker:

[Fussball-Robby]

Zitat:

Zitat von Görly

ps: kann ich den titel noch nachträglich ändern?

Ja, durch einen Klick auf den Edit-Button im 1.Beitrag, genauso wie du gerade deinen letzten Beitrag editiert hast.

Zitat:

Zitat von Görly

aber es geht nich anders.

Natürlich ght es anders. Du guckst dir ein Grundlagen-Tutorial zu Delphi an, überlegst dir, wie du dein Programm aufbauen willst, probierst es aus, und wenn es DANN irgendwo ein Problem gibt, dann kannst du hier fragen. Wir helfen dir gerne, aber ein ganzes Programm schreiben wir nicht. :wink:

Mfg

[Klaus01]

Hallo,

KMP ist doch ein StringMatching Algo.
Er prüft ob ein Teilstring in einem String vorkommt.
Ähnlich wie es die pos Routine in Delphi macht.

Wenn Du die Routine aus meinem Link nimmst,
musst Du ihr lediglich einen String, einen SubString, die Länge des Strings und die Länge
des Substrings übergeben.

Delphi-Quellcode:

s1 := 'einBeliebigerString';
s2 := 'lieb';
i:=Knuth_Morris_Pratt(pchar(s1),pchar(s2),length(s1),length(s2));

Die Routine schaut jetzt ob 'lieb' in dem String 'einBeliebigerString' enthalten ist.

Wie die Routine arbeitet kannst Du dem zweiten Link entnehmen.

Grüße
Klaus

[Görly]

verstehe ich das richtig?: ich muss also das was du gerade geschrieben hast als eingebe verfassen? oder muss ich das zu der routine hinzufügen? :gruebel:

[mkinzler]

Das ist ein Beispiel für den Aufruf

[Görly]

den link den du(klaus) mir als erstes geschickt hattest, wie binde ich den ein? unter nem button? oder gilt dieser allgemein?

[Fussball-Robby]

Zitat:

Zitat von Görly

den link den du(klaus) mir als erstes geschickt hattest, wie binde ich den ein? unter nem button? oder gilt dieser allgemein?

Das ist eine Funktion. Die kommt in den Implementations-Teil. Nicht ins OnClick eines Buttons, damit diese Funktion allgemein verwendet werden kann, und nicht nur vom Button. Das Beispiel, welches Klaus gezeigt hat, also der Aufruf der Funktion, der muss in einen Button.

Mfg

[Görly]

danke :thumb:

[Görly]

genial :party: es funktioniert! er gibt mir jetz die stelle in zahlenform an, an welcher das gesuchte wort beginnt. genial zur erklährung im vortrag wäre wenn er mir nochmal den text in dem gesucht wird anzeigt und das gefundenne wort farbig markiert. ist das möglich bzw. wie?

also es reicht wenn er nur die stelle markiert die er mir bisher als zahl angibt. ansonsten wäre es sicherlich zu kompliziert.

[Klaus01]

dazu kannst Du die TRichtext Komponente nehmen.
In der Forumsuche sollte zu finden sein, wie ein Wort/TeilWort
markiert werden kann.

Grüße
Klaus

[grenzgaenger]

Zitat:

Zitat von Klaus01

Hallo,

KMP ist doch ein StringMatching Algo.
Er prüft ob ein Teilstring in einem String vorkommt.
Ähnlich wie es die pos Routine in Delphi macht.

Wenn Du die Routine aus meinem Link nimmst,
musst Du ihr lediglich einen String, einen SubString, die Länge des Strings und die Länge
des Substrings übergeben.

Delphi-Quellcode:

s1 := 'einBeliebigerString';
s2 := 'lieb';
i:=Knuth_Morris_Pratt(pchar(s1),pchar(s2),length(s1),length(s2));

Die Routine schaut jetzt ob 'lieb' in dem String 'einBeliebigerString' enthalten ist.

Wie die Routine arbeitet kannst Du dem zweiten Link entnehmen.

Grüße
Klaus

mhhh... hab den auch mal probiert...

Delphi-Quellcode:

s1 := 'einBeliebigerString';
s2 := 'ein';
i:=Knuth_Morris_Pratt(pchar(s1),pchar(s2),length(s1),length(s2));

nicht gefunden... :gruebel: :gruebel: :gruebel:

[Klaus01]

Guten Abend,

der verlinkte Code ist anscheinend nicht ganz o.k.
Er findet nur Teilwörter mit der Länge 2 und auch nur dann
wenn sie nicht am Anfang des zu durchsuchenden Strings stehen.

Das mit der Teilwortlänge von 2 habe ich unten berichtigt.
Weiter besteht das Problem, dass kein Teilwort gefunden wird
wenn es im zu durchsuchenden String am Anfang steht.
Grüße
Klaus

Delphi-Quellcode:

function kmp(const target,pattern: pchar;const LTarget, lPattern: Integer):Integer;
var
  step : array[0..255] of Integer;
  i,j : Integer;

begin
  result := -1;
  i:=0;
  j := -1;
  if lTarget * lPattern = 0 then
    exit;
  step[0] := -1;

  repeat
    begin
      if ( j = -1) or (pattern[i] = pattern[j]) then
        begin
          inc(i);
          inc(j);


          if pattern[j] = pattern[i] then
            step[i] :=step[j]
          else
            step[i] := j;
        end
      else
        j:=step[j];
    end;
  until i >= lPattern -1;  // hier ein > eingefügt
  j:=  -1;
  i:=0;
  while i < lTarget do
    begin
      if (j = -1) or (pattern[j] = target[i]) then
        begin
          inc(i);
          inc(j);
          if j >= lPattern then
            begin
              result := i-j+1;
              exit;
            end;
        end
      else
        j:= step[j];
    end;
end;

[Görly]

Ich habs jetz in der Hilfe gefunden aber diese ist nicht wirklich vollständig auf dem rechner vorhanden; der begriff ist zwar vorhanden aber die implentierungsweise zum Fettschreiben fehlt irgendwie. Hab dann auch den Eintrag im Forum angeguckt (http://www.delphipraxis.net/internal...en+hervorheben) aber ich verstehe nicht wirklich wie ich den einbauen muss.

[Klaus01]

Hallo,

vielleicht ist es hier etwas anschaulicher erklärt.

Ansonsten einfach TRichEdit auf die Form ziehen.
Mit RichEdit1.Text:= den Text übergeben.

Grüße
Klaus

[alzaimar]

Hier noch ein paar gute Links:
1. Schrittweise Demonstration
2. Definition, Erklärung, Implementierung, Live-Demo

[Görly]

eine programdarstellung wie sie im 1. link erfolgt wäre natürlich wahnsinn zur verdeutlichung des kmp algorithmus. aber duch die umschreibung meines programms ist das nich zu schaffen, oder? :gruebel:

mfg görly

[Gausi]

Eine Suchanimation ist auch mit Delphi machbar, allerdings ist das nicht mal eben gemacht. Für einen Vortrag hab ich mal ein kleines Programm geschrieben, was einige der gängigen Suchalgorithmen animiert und "gegeneinander antreten lässt". Knuth-Morris-Pratt ist da auch dabei.

Ich hab für hier mal ein kleines Label eingebaut, damit du nicht schummeln kannst :mrgreen:

[alzaimar]

:thumb:

[omata]

@Gausi: Ein echt geiles Programm :thumb:

[Görly]

ou du bist n held :thumb: ! geniale sache. aber die lehrerin würd mir eh niemals abkaufen das ich das allein geschrieben hätte :-D hast ja gesehen wo meine probleme anfangen :zwinker: !

ein riesen dankeschön.

mal nebenbei, wie lange hast du gebraucht das prog. zu schreiben? und wie lange brauch man um solche erfahrung in sachen delphi zu erlangen. bin jetz auch voll im delphi-fieber :-D

greetz görly

[Gausi]

Wie lange ich dafür gebraucht habe, weiß ich nicht mehr. War aber nicht übermäßig lang - das ist auch mehr so nebenbei entstanden. Irgendwo hier schwirrt auch ein Thread mit ner frühen Version des Programms rum, was man da noch durch Mausbewegungen zum Absturz bringen konnte - Threadprogrammierung mit Bitmaps ist etwas doof. :stupid:

(Und vielleicht kann es ja auch der nächste Vortragende gebrauchen - wo Knuth-Morris-Pratt vorkommt, ist Boyer-Moore meistens nicht weit weg. :lol:)

[Görly]

na wirst es nich glauben ich muss beides erklähren daher bin ich so wahnsinnig begeistert! :bounce1:

[Görly]

so wie gesagt das program ist ja fertig. soweit is das klasse. nur mir ist aufgefallen das wenn ich ein wort mehrmals im satz habe und dieses suche er mir nur die stelle des anfangsbuchstaben von 1. wort ausgibt. dazu kommt das ich bei diesem program automatisch die zeit messen lassen muss das hab ich wie folglich im quellcode zu sehen ist auch schon hinbekommen. doch da der satz nicht ausreichend lang ist gibt mir dieser zähler keinen wert aus, wenn ich nich vorher einen haltepunkt im quellcode festlege. meine lehrerin war der meinung das sei nicht anders lösbar und da dachte ich frag ich euch nochmal :zwinker: !
schauts euch einfach mal an:

Delphi-Quellcode:

unit Unit1;

interface

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

type
  TForm1 = class(TForm)
    Edit1: TEdit;
    Edit2: TEdit;
    Button1: TButton;
    Label1: TLabel;
    Label2: TLabel;
    Button2: TButton;
    Button3: TButton;
    Button4: TButton;
    Label3: TLabel;
    Edit3: TEdit;
    procedure Button1Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button4Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}
function knuth_morris_pratt(const target, pattern : PChar; const lTarget, lPattern : integer) : integer;
var
        step : array[0..255] of integer;
        i,
        j    : integer;
        begin
        result := -1;
        if ltarget * lpattern = 0 then exit;
        i := 0;
        j := -1;
        step[0] := -1;

        repeat
        if (j = -1) or (pattern[i] = pattern[j]) then
        begin
        inc(i);
        inc(j);
        if pattern[j] = pattern[i] then step[i] := step[j] else step[i] := j;
        end else j := step [j];
        until i = lpattern -1;
        j := -1;
        i := 0;

        while i < ltarget do
        begin
        if (j=-1) or (pattern[j] = target[i]) then
        begin
        inc(i);
        inc(j);
        if j >= lpattern then
        begin
        result := i-j+1;
        exit;
        end;
        end else j := step[j];
        end;
        end;


procedure TForm1.Button1Click(Sender: TObject);
var i, t:integer; s1,s2:string;
begin
  t := gettickcount;

s1:=edit1.Text;
s2:=edit2.Text;
i:=knuth_morris_pratt(pchar(s1),pchar(s2),length(s1),length(s2));
label2.Caption:=inttostr(i);

Edit3.Text := floattostrf((gettickcount-t)*0.001,fffixed,10,2);
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
  edit1.Text:= '';
  edit2.Text:= '';
  label2.Caption:= '';
end;

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

procedure TForm1.Button4Click(Sender: TObject);
begin
edit1.text:= 'hallo liebe info freune! info mit frau müller macht sp.-spa.-sp (ach scheiß drauf, macht auf jeden fall iwas)';
edit2.Text:= 'frau müller';
end;

end.

[Schorschi5566]

Hallo DP,

der Thread ist ja schon etwas älter, aber ich beschäftige mich gerade mit Boyer-Moore & Co. :wink:

Habe mal die Fehler im KMP von oben behoben und die Funktion auf die Verwendung mit Strings umgeschrieben. Sollte jetzt auch am Textanfang funktionieren...vielleicht kann's ja der Eine oder Andere gebrauchen.

Delphi-Quellcode:

function TToolBox.PosKMP(const sSearch, sText : String) : Integer;
var
  step : array[1..1024] of Integer;
  i, j , lTarget, lPattern: Integer;
begin
  lTarget := Length(sText);
  lPattern := Length(sSearch);
  result := 0;
  if lTarget * lPattern = 0 then
    Exit;
  i := 1;
  j := 0;
  step[1] := 0;

  repeat
    if (j = 0) or (sSearch[i] = sSearch[j]) then
    begin
      inc(i);
      inc(j);
      if sSearch[j] = sSearch[i] then
        step[i] := step[j]
      else
        step[i] := j;
    end
    else
      j := step[j];
  until i >= lPattern - 1;

  j := 1;
  i := 1;

  while i <= lTarget do
  begin
    if (j = 0) or (sSearch[j] = sText[i]) then
    begin
      inc(i);
      inc(j);
      if j > lPattern then
      begin
        Exit(i - j + 1);
      end;
    end
    else
      j := step[j];
  end;
end;