LZW Komprimierung für texte - zugriffsverletzung

[qwertz543221]

ich habe versucht, texte mit dem sequitur-algorithmus zu komprimieren
dafür soll es eine prozedur quicksort und eine proceudre binarysearch für arrays geben.
das array soll als wörterbuch genutz werden.

wenn ich allerdings versuche den normalen quicksort für zahlen (functioniert) auf arrays anzuwenden habe ich speicherzugriffprobleme.

hat jemand eine idee woran das liegen könnte? - zugriffsverletzungen passieren ja meist bei fehlgeleiteten zeigern...

ps.: im moment nutze ich noch arrays, doch ich habe vor, das hganze zu doppelt verketteten listen umzugestalten. hat das vorteile oder ist es prinzipiell egal?


den bisherigen quelltext findet ihr im anhang



danke für jede konstuktive bemerkung, außer dass meine procedure sequitur heißt (das war die kompression die ich zuerst versucht hatte)

[gammatester]

Zitat von qwertz543221:

danke für jede konstuktive bemerkung, außer dass meine procedure sequitur heißt (das war die kompression die ich zuerst versucht hatte)

Das sollte sich eigentlich von selbst verstehen: Benutzte den Debugger und schalte alle Checks ein, insbesondere Rangecheck, Overflowcheck.

Ich hätte mindestens drei offensichtliche Bugs/Anmerkungen, aber nach dem CRT/RSA-Desaster warte ich lieber erst mal ab, ob überhaupt Fortschritte sichtbar sind.

Gammatester

[Luckie]

Bist du mit Hansa verwandt? Der hat seine Screenshots auch immer in Word Dokumente verpackt. Was soll diese Unsitte?

Der Fehler wird wohl in deinem Quicksort Algorithmus liegen. Warum postets du ihn nicht?

[qwertz543221]

die quicksort-procedure schicke ich später bin zzt noch nicht daheim.
sie soll später noch geändert werden, damit sie auf doppelt verketteten listen läuft.
bisher hat sie aber keine falschen ergebnisse geliefert.

wie soll ich screenshots denn veröffentlichen? - welche methode gibt es noch?

[himitsu]

Zitat von qwertz543221:

wie soll ich screenshots denn veröffentlichen? - welche methode gibt es noch?

vielleicht als Bild? (JPeg, GIF, PNG ...)

[qwertz543221]

Delphi-Quellcode:

unit Unit1;

interface

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

type
dd=record
zahl:longint;
s:string;
end;
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    Button2: TButton;
    Button3: TButton;
    Edit1: TEdit;
    Edit2: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    Button4: TButton;
    Button5: TButton;
    Button6: TButton;
    Edit3: TEdit;
    Label3: TLabel;
    procedure Button6Click(Sender: TObject);
    procedure Button5Click(Sender: TObject);
    procedure Button4Click(Sender: TObject);
    procedure Memo1Change(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
    procedure Button1Click(Sender: TObject);
    procedure write;
    procedure init;
    procedure Quicksort ( l,r: longint);
    function BinSearch(a: array of longint; x: longint): longint;
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;
  ar:array of longint;

implementation

{$R *.dfm}

function tform1.BinSearch(a: array of longint; x: longint): longint;
var
  anfang,ende,pivot:longint;
  fund:Boolean;
begin
if x>a[length(a)-1]
  then
  begin
  result:=-1;
  exit;
  end
  else
  begin
  anfang:= 0; 
  ende:= length(a); 
  fund:= False; 
  Result := -1; 

  while anfang<= ende) and (found=false) do
  begin
    Pivot := ((anfang + ende) div 2)mod length(a);
    if a[Pivot] = x then
    begin
      Found  := True;
      Result := Pivot+1;
    end
    else if a[Pivot] > x then
      ende := Pivot - 1
    else 
      anfang := Pivot + 1;
  end;
  end;
end;


procedure TForm1.Button1Click(Sender: TObject);
var
i,j,x,max:longint;
begin
memo1.Clear;
max:=strtoint(edit1.text);
i:=strtoint(edit2.Text);
setlength(ar,i);
randomize;
j:=0;
while j<i do
begin
x:=random(max)+1;
ar[j]:=x;
memo1.Lines.Add(inttostr(ar[j]));
j:=j+1;
end;
end;

procedure TForm1.Button3Click(Sender: TObject);
begin
memo1.Clear;
edit1.Clear;
edit2.Clear;
end;

procedure tform1.init;
var i:longint;
begin
i:=0;
setlength(ar,strtoint(edit2.text));
while i<length(ar) do
begin
ar[i]:=(strtoint(memo1.Lines[i]));
i:=i+1;
end;
end;


procedure tform1.write;
var i:longint;
 begin
 i:=0;
 memo1.Clear;
while i<length(ar) do
begin
memo1.Lines.add(inttostr(ar[i]));
i:=i+1;
end;
end;

PROCEDURE tform1.Quicksort (l,r: longint);
VAR pivot,b,i,j :  longint;

BEGIN
   IF l < r THEN
   BEGIN
      pivot := Ar[random(r-l) + l+1];
      i := l-1;
      j := r+1;
         while i<j do
         begin
      REPEAT i := i+1 UNTIL pivot <= ar[i];
      //while (pivot>ar[i])do i:=i+1;
            REPEAT j := j-1 UNTIL pivot >= ar[j];
            b:=Ar[i];
            Ar[i]:=Ar[j];
            Ar[j]:=b
      //UNTIL i >= j;
      end;

      Ar[j]:=Ar[i];
      Ar[i]:=b;

      Quicksort(l,i-1);
      Quicksort(i,r)
   END;
END;



procedure TForm1.Button2Click(Sender: TObject);
var s,t:cardinal;
begin
s:=gettickcount;
init;
bubblesort;
t:=gettickcount;
showmessage(inttostr(t-s));
end;

procedure TForm1.Memo1Change(Sender: TObject);
begin
edit2.Text:=inttostr(memo1.lines.Count);
end;

procedure TForm1.Button4Click(Sender: TObject);
var s,t:cardinal;
begin
s:=gettickcount;
init;
quicksort(0,length(ar));;
t:=gettickcount;
showmessage(inttostr(t-s));
end;

procedure TForm1.Button5Click(Sender: TObject);
begin
write;
end;

procedure TForm1.Button6Click(Sender: TObject);
var x:longint;
begin
x:=strtoint(edit3.Text);
init;
quicksort(0,length(ar));
showmessage(inttostr(binsearch(ar,x)));
end;

end.

[p80286]

Hallo Qwertz543221,

wenn Du Deinen Source etwas sinnvoll formatiert hättest, wäre es etwas einfacher da durchzusteigen.

Und auch wenn Du den Namen einer globalen Variablen änderst, dann bleibt sie doch eine.
(Und jetzt hab auch ich verstanden warum sie so bäh bäh sind!)

Und viel wichtiger ich hab da erst einmal nichts zu LZW gefunden.
(Naja ich lese auch nicht gerne Basic-Sourcen)

[edit]
das da oben kann gar nicht kompiliert werden!
und das strtoint(edit1.text); ist zumindestens sehr optimistisch!
Gruß
K-H

[qwertz543221]

hallo

was meinst du mit sinnvoll formatieren? zwischen den fkts und prods sind abschnitte
deklarationen findest du ganz oben und im wesentlichen sind es nur drei prods - binsearch, quicksort, write - von denen ich ausging, dass die titel sich selbst erklären: binäre suche, quicksort und eine ausgabeprozedur.

Der rest sind die aufrufe dieser durch buttons. das war eigentlich alles was im code steht.


zum inhalt des codes:
luckie:

Zitat:

#3|Verfasst am: 21.08.2009, 13:08 Titel: Re: LZW Komprimierung für texte - zugriffsverletzung

Der Fehler wird wohl in deinem Quicksort Algorithmus liegen. Warum postets du ihn nicht?

dazu habe ich die notwendigen teile eingestellt, denn wie luckie schreibt, ist er der meinung, dass die fehler im qs- algorithmus versteckt seien.



an luckie (und die anderen):
und - habe ich einen gravierenden fehler in den qs- teil eingebaut?, bisher konnte ich keinen entdecken, aber zwei augen sehen meist nicht genug

[gammatester]

Zitat von qwertz543221:

an luckie (und die anderen):
und - habe ich einen gravierenden fehler in den qs- teil eingebaut?, bisher konnte ich keinen entdecken, aber zwei augen sehen meist nicht genug;)

Vielleicht solltest Du den Code (wie oben schon 'mal frech vorgeschlagen wurde) erst einmal so schreiben, daß man ihn compilieren kann. Wenn Du ihn nur selbst benutzt, mußt Du ihn ja auch nicht vernünftig formatieren (ist nur was für Schwächlinge). Dann kanst Du auch den Debugger benutzen und feststellen, was die Zugriffsverletzungen erzeugt. Kleiner Hinweis: ein Fehler in einer Prozedur kann durch falschen Code oder durch falschen Aufruf erzeugt werden.

Gammatester

[qwertz543221]

Zitat:

Wenn Du ihn nur selbst benutzt, mußt Du ihn ja auch nicht vernünftig formatieren (ist nur was für Schwächlinge).

das hat mir jetzt leider nicht gesagt, was an der formatierung genau falsch ist

und... polemik hilft keinem




hier die angezeigte fehlermeldung(zugriffsverletzung)
"zugriffsverletzung bei adresse 00403F30 im modul 'prj1.exe'. lesen von adresse 0000000A."



ps. was ist an globalen variablen verkehrt?



beim debuggen ist folgendes
[quote]
program Project1;

uses
Forms,
Unit1 in 'Unit1.pas' {Form1};

{$R *.res}

begin
Application.Initialize;
Application.CreateForm(TForm1, Form1);
Application.Run;
end.
{/quote]


im aufruf stack

00403568 notify nondelphiexception +$1C