Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Levenshteinalgorithmus - StackOverflow


Mashalla - Di 16.02.10 14:46
Titel: Levenshteinalgorithmus - StackOverflow
Implementierung der Levenshtein-Distanz-Berechnung, Programm schmiert bei der Zuweisung des Ergebnisses mit einem StackOverflow ab ... ich weiß nicht, warum -.-


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:
 
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 - 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. ;-)


Mashalla - 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 - Di 16.02.10 15:04
In den Schleifen steckt der Fehler aber auch noch drin. ;-)


Bergmann89 - 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


Mashalla - 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 - Di 16.02.10 15:13
Vermutlich weil diese Prüfung in den Optionen deaktiviert ist. Kann man aber anschalten. ;-)


Mashalla - Di 16.02.10 16:58
Jo, lag daran. In TDE ist alles standardmäßig deaktiviert wie ich gerade merke ^^ Danke


Mashalla - 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 - Mi 17.02.10 20:49
Die wenigstens Compiler führen eine komplette Static Code Analysis [http://en.wikipedia.org/wiki/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.


jakobwenzel - 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.


Mashalla - Do 18.02.10 00:21
Jo, verstehe. Ganz oder gar nicht und im Falle vom Turbo Delphi Compiler eben gar nicht :)


Horst_H - 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 
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 
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 
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 - 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 - 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 - 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


Gausi - 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. ;-)


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 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!