Entwickler-Ecke :: Thema anzeigen - Levenshtein

Pepp3r - Do 15.12.11 18:31
Titel: Levenshtein - Distanz

Hier mein Lückenfüllerprojekt "Levenshtein". Kein großes Ding, aber vielleicht wird es ja mal jemand brauchen.
Das Programm berechnet die minimale benötigte Anzahl an Operationen um den String1 in den Strin2 zu überführen.
In der Praxis kommt der Levenshtein-Algorithmus bei Suchvorgängen (zB google o.ä.) zum Einsatz.
http://de.wikipedia.org/wiki/Levenshtein-Distanz

Gruß
Pepp3r

Pepp3r - Fr 16.12.11 16:32

Hatte leider nen kleinen Fehler. Wurde verbessert. Hier vollständige Unit:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:

unit Levenshtein;

interface

uses
  classes, SysUtils, Variants;

type
  TLevenshtein = Class
    private
    protected
      zeile1: Array of Byte;
      zeile2: Array of Byte;
      m: Byte;
      a, b: String;
    public
      constructor create(text1, text2: String);
      destructor free;
      function calc: Integer;
  end;

implementation

uses
  Unit1;

constructor TLevenshtein.create(text1, text2: String);
var
  i: Byte;
begin
  a := text1;
  b := text2;
  m := length(a);
  setlength( zeile1, m+1);
  setlength( zeile2, m+1);
  for i := 1 to m do
    zeile1[i] := i;
end;

destructor TLevenshtein.free;
begin
  setlength(zeile1, 0);
  setlength(zeile2, 0);
end;

function TLevenshtein.calc: Integer;
var
  i, j, k: Byte;
  min: Byte;
begin
    // rechnen
    for i := 1 to length(b) do
    begin
      zeile1[0] := i-1;
      zeile2[0] := i;
      for j := 1 to m do
      begin
        if (a[j] = b[i]) then
        begin
          zeile2[j] := zeile1[j-1];
          continue;
        end;
        min := zeile1[j-1];
        // Minimum finden
        if (zeile1[j] < min) then
          min := zeile1[j];
        if (zeile2[j-1] < min) then
          min := zeile2[j-1];
        // Operation addieren
          zeile2[j] := min+1
      end;
      // Zeilen überführen
      for k := 0 to m do
        zeile1[k] := zeile2[k];
    end;
    result := zeile1[m];
end;

end.

Anwendungsbeispiel:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

procedure TForm1.Button1Click(Sender: TObject);
begin
  levenshtein := TLevenshtein.create(Edit1.Text, Edit2.Text);
  Label2.Caption := (inttostr(levenshtein.calc));
  Levenshtein.free;
end;

Gruß
Pepp3r

glotzer - Fr 16.12.11 16:43

Zitat:

destructor free;

Der destructor heißt IMMER Destroy, das muss

Delphi-Quelltext

1:	destructor Destroy; override;

heißen.

Pepp3r - Fr 16.12.11 17:17

Moderiert von Narses: Komplett-Zitat des letzten Beitrags entfernt.

Wieso?

Nersgatt - Fr 16.12.11 17:45

Weil die Klasse, von der Du Deine Klasse ableitest, evtl. noch irgendwelche Arbeiten (z.B. Aufräumen) im Destructor machen muss. Daher ist es auch wichtig, nicht nur Overridezu verwenden, sondern im eigenen Destructor auch inherited aufzurufen.
Und auch wenn Du Deine Klasse nicht explizit von einer anderen ableitest, sie wird immer mindestens von TObject abgeleitet.

baka0815 - Di 20.12.11 12:53

Man ruft bei einem Objekt zwar die Free-Funktion auf um das Objekt freizugeben, diese hingegen ruft den eigentlichen Desturktor Destroy auf.

Wenn du deinen Destruktor jetzt anders nennst, funktioniert z.B. FreeAndNil nicht mehr. Außerdem macht die Free-Funktion noch eine Prüfung ob das freizugebende Objekt nil, und somit bereits freigegeben, ist. Dies ist beides nicht mehr (uneingeschränkt) möglich, wenn der Destruktor anders heißt.

bummi - Di 20.12.11 13:02

@baka0815

wie kommst Du darauf?

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

var
 b:TButton;
begin
  b:=TButton.Create(self);
  {
  b.Free; 
  b.Free; // das knallt
  }

  FreeAndNil(b);
  FreeAndNil(b); // das geht
end;

aber das hat mit dem Destruktor nur bedingt zu tun, das knallt ebenfalls

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

var
 b,c:TButton;
begin
  b:=TButton.Create(self);
  c := b;
  FreeAndNil(b);
  FreeAndNil(c);
end;

baka0815 - Di 20.12.11 14:06

Wenn er den Destruktor Free nennt, funktioniert FreeAndNil noch, da dies das Free aufruft. Ein anderer Name, wie z.B. Destruktor würde dann nicht mehr funktionieren, bzw. der eigene Destruktor halt nicht aufgerufen.

Blup - Di 03.01.12 18:57

"Free" ist eine normale Methode von TObject, noch nicht einmal virtual.
Es gibt eigentlich kaum einen Grund diese zu verdecken.
FreeAndNil ruft immer diese Methode von TObject auf und interessiert sich überhaupt nicht für einen nachträglich hinzugefügten Destructor gleichen Namens.
Deshalb ist es wichtig "Destroy" zu überschreiben:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

procedure TObject.Free;
begin
  if Self <> nil then
    Destroy;
end;

// Damit funktioniert so etwas ohne Fehler
var
  b: TObject;
begin
  b := nil;
  b.Free; 
end;

Falls man tatsächlich einen Destructor mit anderem Namen braucht, sollte man sicherstellen, das auch Destroy weiterhin ordentlich funktioniert.

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:

destructor TMyObject.Destroy; {override}
begin
  MyDestroy;
end;
 
destructor TMyObject.MyDestroy;
begin
  {...}
  inherited Destroy;
end;

Für TLevenshtein muss aber weder Destroy überschrieben, noch ein neuer Destructor hinzugefügt werden. Jeder Destructor (auch der von TObject) enthält unsichtbaren Code, der String-, Array- und Interface-Member bzw. den dadurch belegten Speicher automatisch freigibt.