Entwickler-Ecke
Open Source Units - Levenshtein - Distanz
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 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]; if (zeile1[j] < min) then min := zeile1[j]; if (zeile2[j-1] < min) then min := zeile2[j-1]; zeile2[j] := min+1 end; 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
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);
FreeAndNil(b); FreeAndNil(b); 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;
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; 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.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2024 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!