Levenshteinalgorithmus - StackOverflow

Mashalla · Verfasst: Di 16.02.10 14:46

Implementierung der Levenshtein-Distanz-Berechnung, Programm schmiert bei der Zuweisung des Ergebnisses mit einem StackOverflow ab ... ich weiß nicht, warum -.-

Delphi-Quelltext

markieren

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:

function IsSpellingCorrect(FVoc, FUser: AnsiString): Integer;
  var
    I, J, X, Y: Integer;
    Res: array of array of Integer;
  begin
    X := Length(FVoc);
    Y := Length(FUser);

    // Tabelle erstellen
    SetLength(Res, X, Y);
    for I := 0 to X - 1 do
      Res[I, 0] := I;   // Elemente löschen

    for J := 0 to Y - 1 do
      Res[0, J] := J;   // Elemente einfügen

    for J := 1 to Y - 1 do
    begin
      for I := 1 to X - 1 do
      begin
        if FVoc[I] = FUser[J] then
          Res[I, J] := Res[I-1, J-1]   // Diagonal laufen
        else
          Res[I, J] := Min(Res[I-1, J] + 1, Res[I, J-1] + 1, Res[I-1, J-1] + 1);
      end;
    end;
    Result := Res[X-1, Y-1]; 
  end;

Algo korrigiert, falls jmd braucht

Gausi · Verfasst: Di 16.02.10 14:51

Du setzt die Größe des Arrays auf X mal Y, greifst aber auch auf das Element mit Index X/Y zu. Das letzte Element in einem Array hat aber den Index X-1 bzw. Y-1. ;-)

_________________
Oel ngati kameie.

Mashalla · Verfasst: Di 16.02.10 14:59

Selber Fehler trotz Korrektur, gleiche Stelle ...

Aber danke für den Hinweis, die Zuweisung war so natürlich falsch

Gausi · Verfasst: Di 16.02.10 15:04

In den Schleifen steckt der Fehler aber auch noch drin. ;-)

_________________
Oel ngati kameie.

Bergmann89 · Verfasst: Di 16.02.10 15:05

Hey,

also ich kann mir jetz auch nich richtig erklären, warum er den Stack voll packt, aber hast dus schonma mit nem größeren Stack versucht? Vlt ist er ja wirklich einfach voll. Muss ja nich die Folge einer Endlosschleife sein...

MfG Bergmann

_________________
Ich weiß nicht viel lern aber dafür umso schneller^^

Mashalla · Verfasst: Di 16.02.10 15:11

Ach klar ... hatte nur 4 Stunden Schlaf und vorher ne Klausur xD

Warum kommt eigentlich keine Fehlermeldung, wenn ich einen Wert an eine Stelle im Array schreiben will und das Array nicht die erforderliche Länge hat?

Gausi · Verfasst: Di 16.02.10 15:13

Vermutlich weil diese Prüfung in den Optionen deaktiviert ist. Kann man aber anschalten. ;-)

_________________
Oel ngati kameie.

Mashalla · Verfasst: Di 16.02.10 16:58

Jo, lag daran. In TDE ist alles standardmäßig deaktiviert wie ich gerade merke ^^ Danke

Mashalla · Verfasst: Mi 17.02.10 20:39

Habe jetzt übrigens die ganzen nativen Exceptions vom Debugger behandeln lassen, erhalte jetzt aber auch erst zur Laufzeit eine Zugriffsverletzung, wenn ich auf einen Arrayindex außerhalb der Grenze zugreife. Sollte da nicht der Compiler eingreifen?

Kha · Verfasst: Mi 17.02.10 20:49

Die wenigstens Compiler führen eine komplette Static Code Analysis durch

. In offensichtlichen Fällen wie deinem wäre es vielleicht noch machbar, aber generell ist das weder trivial noch vom Zeitaufwand her bei jedem Kompilieren akzeptabel.

_________________
>λ=
Bis 10.9. im Urlaub

jakobwenzel · Verfasst: Mi 17.02.10 20:51

Wenn du ein Array fester Länge hast und auf einen konstanten Index zugreifst sollte er schon meckern, aber in diesem Fall wäre das mit mehr Aufwand verbunden.

_________________
I thought what I'd do was, I'd pretend I was one of those deaf-mutes.

Mashalla · Verfasst: Do 18.02.10 00:21

Jo, verstehe. Ganz oder gar nicht und im Falle vom Turbo Delphi Compiler eben gar nicht

Horst_H · Verfasst: Do 18.02.10 09:57

Hallo,

Wie oft machen Strings als Wertparameter Aerger....
Probiere mal const oder var vor den zu uebergebenden Strings, dann werden diese nicht auf dem Stack erzeugt.

Delphi-Quelltext

markieren

1:	function IsSpellingCorrect(CONST FVoc, FUser: AnsiString): Integer;

alternativ, aber schlechter, außer man ändert wirklich was an den Strings, in der letzten Zeilen die neu geschaffenen Strings FVoc, FUser loeschen

Delphi-Quelltext

markieren

1:
2:
3:
4:

    Result := Res[X-1, Y-1]; 
    FVoc :='';
    FUser :='';
  end;

Das MIN mit drei eingabedaten arbeitet kannte ich noch nicht.

Delphi-Quelltext

markieren

1:
2:
3:

Res[I, J] := Min(Res[I-1, J] + 1, Res[I, J-1] + 1, Res[I-1, J-1] + 1);
aber ueberall ein +1 macht keinen Sinn
Res[I, J] := Min( Res[I-1, J], Res[I, J-1] , Res[I-1, J-1] ) +1;

Gruß Horst

Mashalla · Verfasst: Do 18.02.10 10:06

Die Min-Funktion ist selbst programmiert, standardmäßig funktioniert die nur mit 2 Parametern und ich arbeite in meinem Fall mit den Parametern weiter, deswegen hatte ich keine konstanten Parameter verwendet

Horst_H · Verfasst: Do 18.02.10 10:16

Hallo,

Zitat:

nd ich arbeite in meinem Fall mit den Parametern weiter, deswegen hatte ich keine konstanten Parameter verwendet

Bezieht sich auf die Strings?

Gruß Horst

Kaaaafffeeeee...

Horst_H · Verfasst: Do 18.02.10 13:38

Hallo,

wieso ist jetzt ein beantwortet Haekchen dran?
Aber, weder Delphi noch freepascal, fordern unmäßig Stackspeicher an.
Also war es ein fasch benannter Zugriffsfehler oder der Teil, der den Fehler produziert, liegt woanders.

Gruß Horst

Einloggen, um Attachments anzusehen!

Gausi · Verfasst: Do 18.02.10 14:03

Nun, es sieht so aus, als wäre die Fehlermeldung "Stackoverflow" in diesem Fall auf ein wildes Überschreiben des Speichers zurückzuführen, was durch die falschen Array-Grenzen verursacht wurde. Ein Schreiben jenseits der Arraygrenzen kann alles mögliche an Fehlern zur Folge haben.

Das war dann hier wohl kein wirklicher Stackoverflow, sah aber so aus. ;-)

_________________
Oel ngati kameie.