Komprimierung : Wie geht das?

[qwertz543221]

Danke hat super funktioniert.

Zum besseren einsatz wäre es vlt günstig, vorher burrows wheeler transofrmation anzuwenden, damit auch längere runs zustandekommen
Dazu habe ich eine textversion, die allerdings noch mit der kompletten trasnspositionstabelle arbeitet. eine möglichkeit, das ganze speichersparend auf zeiger umzustellen habe ich noch nicht, da ich nicht weiß, wie ich diese tabelle dann sortieren soll.

[qwertz543221]

zum sortieren( kopiert und verschoben etc) wird, habe ich das - langsame, aber stabile ( reicht für den anfang) - bubblesort genutzt.

ich habe jetzt das ganze versucht, über positions indizes laufen zu lassen, damit nie die gesamte tabelle verändert wird, sondern lediglich indizes geändert werden.(so wird es in wiki ja als evrbesserung dargestellt)

Am ende wird die neue anordnung anhand der vergebenen indizes in eine neue tabelle eingetragen...
... soviel zur idee, in der umsetzung des decoders kommt es dabei zu einem stack-überlauf,falls nicht nur gleiche werte in der tabelle. liegt wohl an einer nicht terminierten schleife???

Delphi-Quellcode:

function tform1.bubblesort(ar: arr):arr;

var i:int64;
c:integer;
br:arr;
begin
i:=1;
mathe:=tmathe.create;
while i<length(ar) do
begin
ar[i].position:=i;
i:=i+1;
end;

i:=1;       //über indizes sortieren
while i<length(ar) do
 begin
 if mathe.Vergleich(ar[i-1].numbers,ar[i].numbers)>0
 then
   begin
   c:=ar[i-1].position;
   ar[i-1].position:=ar[i].position;
   ar[i].position:=c;
   end;
 i:=i+1;
 end;
i:=1;
br:=ar;

while i<length(br) do
begin
ar[i].text:=br[ar[i].position].text;
ar[i].numbers:=br[ar[i].position].numbers;
i:=i+1;
end;

i:=1;     //überprüfen
while i<length(ar)do
 begin
 if vergleich(ar[i-1].numbers,ar[i].numbers)=0
  then bubblesort(ar)
    else i:=i+1;
 end;
 result:=ar;
 end;

[qwertz543221]

ok habe einen fehler gefunden. es läuft jetzt.

Habe nur ein problem des speichers, da der arbeitspeicher voll sein soll - oder ich habe einen stack-überlauf - wie bekomme ich dies beseitigt? (rekursionsporblem??)

Delphi-Quellcode:

function tform1.bubblesort(var ar: arr):arr;

var i,c:int64;

begin
i:=1;
setlength(result,length(ar));

while i<length(ar) do
 begin
 if mathe.Vergleich(ar[i-1].numbers,ar[i].numbers)>0
  then
  begin
  c:=ar[i-1].position;
  ar[i-1].position:=ar[i].position;
  ar[i].position:=c;
  end;
 i:=i+1;
 end;

i:=0;
while i<length(ar) do
 begin
 //showmessage(inttostr(ar[i].position));
 result[i]:=ar[ar[i].position];
 i:=i+1;
 end;

i:=0;
while i<length(result)-1 do
 begin
 if mathe.vergleich(result[i].numbers,result[i+1].numbers)>0
  then 
   begin
   //showmessage(inttostr(i));
   result:=bubblesort(result);
   i:=i+1;
   end;
 i:=i+1;
 end;

 end;

ich denke es wäre vlt besser, mit verketteten listen und zeigern zu arbeiten,(ich hoffe, da hab ich dann kein speicherproblem mehr?) das mit dem array ist nur eine übergangslösung.

[alzaimar]

Bubblesort in rekursiv? Das ist ja mutig.

Wieso nicht einfach so?

Delphi-Quellcode:

For i := low(TheArray) to High (TheArray)-1 do
  For j := i + 1 to High(TheArray) do
    If TheArray[i] > TheArray[j] then
      SwapArrayElements (TheArray, i, j);

Getippt und nicht getestet, und SwapArrayElements solltest Du dann noch selbst auskodieren.

Aber was Du genau sortieren willst, habe ich nicht verstanden.