Komprimierung : Wie geht das?

[NickelM]

@Sherlock : Schwere Kost..aber danke wenn ich mich mal damit befassen will mach ich dass.

Danke an allen nochmal. Habs jetzt kapiert.

[qwertz543221]

ich habe die hier angesprochene runlength-codierung in eifnacher form geschrieben. ist zzt nur für strings, kann aber einfach für streams, also dateien beliebigen formats erweitert werden.

zur besseren komprimierung möchte ich das ganze zuvor mit burrows - wheeler transformieren. ZZt wird noch die gesamte Tabelle im Speicher abgelegt, doch sollte es /auch laut wiki/ genügen nur speicheradressen auf den jeweiligen anfang zu setzen, um den prozess zu beschleunigen und eine kleinere datenmenge verwalen zu müssen.


Der algorithmus in seiner ursprungsform läuft... mir fehlt nur ein ansatz für die o.g. optimierung.(btw möglicherweise nur mit zeigern statt agnzer taBelle, wie ist das zu realisieren??)

Danke für etwaige Anmerkungen und Ergänzungen. Ich hoffe ich konnte einen kleinen anreiz geben,.

Eine kopie des qt hänge ich an

[qwertz543221]

es hat sich im qt ein fehler eingeschlichen, sodass der decoder an manchen stllen falsche codes einliest und dementsprechend keine korrekte umwandlung mehr in unkomprimierten text mehr liefert. Wieso das so ist, kann ich zzt noch nicht sagen, da es bisher nur bei nicht-text-sreams auftritt. bei texten scheint alles zu funktionieren.
Bin noch auf der suche...

[himitsu]

Zitat von qwertz543221:

es hat sich im qt ein fehler eingeschlichen,...

Hast du eventuell vergessen deine Markierung für die Mehrfach-Angaben zu prüfen?
Wen diese im Originaltext vorkommt, dann muß diese ebenfalls kodiert werden, selbst wenn es da keine Mehrfachvorkommen gibt.

[qwertz543221]

das könnte sein... bei strings tritt das trennzeichen (chr(0))im allg nicht auf, da es den string abschließt. daher habe ich dieses zeichen gewählt.

bei anderen streams:

wie muss ich dann vorgehen, falls ich auf das trennzeichen treffe?? bisher habe ich es wie folgt gemacht:

Delphi-Quellcode:

function tform1.rledec(text:ansistring):ansistring;
var c,d:ansistring;
i,j,z:int64;

begin
//text:=base64dec(text);
//text:=strtohex(text);
result:='';
i:=1;

while i<=length(text) do
 begin
 if text[i]=chr(0)
   then
   begin
   c:='';
   j:=i+1;
   while j<=i+2 do
    begin
    c:=c+text[j];
    j:=j+1;
    end;
 // showmessage(c);
   d:=text[j];
   z:=1;
   while z<=strtoint('$'+c) do
    begin
    result:=result+d;
    z:=z+1;
    end;
   i:=i+4;
   end
    else
    begin
    result:=result+text[i];
    i:=i+1;
    end;
  end;
end;

[himitsu]

Zitat von qwertz543221:

wie muss ich dann vorgehen, falls ich auf das trennzeichen treffe??

Man könnte hier
a) sich etwas einfallen lassen, wie man die "originalen" #0 (aka chr(0) ) maskiert, oder

b) man tut einfach so, als wäre diese 0 (irgend)ein sich wiederholendes Zeichen, welches du ja über eine #0-eingeführte Steuersequenz maskierst.
> also füge statt soeiner gefundenen #0 einfach deine Sequenz ein, welche besagt "1-mal die #0"
(falls mehrere nacheinanderfolgene Nullen vorkommen, würde es sogar wieder dem Ursprünglichen Gedanken entsprechen)

PS: das result:=result+chr(0)+inttohex(c,2)+text[i]//+chr(32); könnte man sogar noch weiter komprimieren, indem du es nicht als Text, sondern auch Binär behandelst.

wiederholende Char (X) als #0 + Chr(Count) + X und die einzelne #0 wäre dann #0#1#0 aka #0 + Chr(Count) + Chr(0) // count=1 ebenso mit maximal 255 Fogezeichen, wobei man sogar 256 nutzen könnte, da es die Anzahl 0 nicht gibt (0=1-mal, 1=2-mal ... 255=256-mal)
und es würden maximal immer nur 3 Byte sein, anstatt deinen aktuell mindestens 4 Byte.

[Medium]

Hatte mal eine kleine RLE gebaut mit $FF als Marker. Die "Regeln" waren da dann:

$FF = Marker: Hier nach kommt ein Byte für die Anzahl
$XX = Anzahlbyte
$YY = Byte, dass $XX mal in Folge kommt

$XX ist maximal $FE, wenn es $FF ist, heisst das, dass ein einzelnes, uncodiertes $FF da sein soll - es ist also dann im unkomprimierten Anteil einfach gedoppelt. Der Preis ist eben, dass man maximal 255 statt 256 in einen Block pressen kann. (Da kein Zeichen 0 mal wiederholt wird, hab ich zum Anzahlbyte immer +1 gezählt.)

[qwertz543221]

das bezieht sich aber schon auf die codierung, oder erst auf die decodierung?

ich nehme mal an ersteres...

bei der decodierung bekomme ich weiterhin eine fehlermeldung, die darauf hinweist, dass falsch gezählt wird.
(exception econverterror zeigt leeren hexwert an)
geändert wie folgt:

Delphi-Quellcode:

function tform1.rleenc(text:ansistring):ansistring; //RLE
var
i,c,k:int64;
begin
result:='';
i:=1;
while i<=length(text) do
begin
c:=1;
while (text[i]=text[i+1])do //and (c<254)do
begin
c:=c+1;
i:=i+1;
end;
//if (text[i]='F')
  //then  result:=result{+'FF'}+inttohex(c,2)+'00'//+chr(32)
//showmessage(inttostr(c));
if (c>4)and (text[i]=chr(0)) //hier geändert f.d. Auftreten des Steuerzeichens!!
  then result:=result+chr(0)+'01'+text[i]//+chr(32);
  else
if (c>4) and (text[i]<>chr(0))
  then  result:=result+chr(0)+inttohex(c,2)+text[i]//+chr(32);
    else
    begin
    k:=1;
    while k<=c do
    begin
    result:=result+text[i];
    k:=k+1;
    end;
    end;
i:=i+1;;
end;
//while length(result) mod 3<>0 do result:=result+'0';
//result:=hextostr(result);
//result:=base64enc(result);
end;

[qwertz543221]

Zitat von Medium:

Hatte mal eine kleine RLE gebaut mit $FF als Marker. Die "Regeln" waren da dann:

$FF = Marker: Hier nach kommt ein Byte für die Anzahl
$XX = Anzahlbyte
$YY = Byte, dass $XX mal in Folge kommt

$XX ist maximal $FE, wenn es $FF ist, heisst das, dass ein einzelnes, uncodiertes $FF da sein soll - es ist also dann im unkomprimierten Anteil einfach gedoppelt. Der Preis ist eben, dass man maximal 255 statt 256 in einen Block pressen kann. (Da kein Zeichen 0 mal wiederholt wird, hab ich zum Anzahlbyte immer +1 gezählt.)

genau dies hatte ich auch schon probiert, aber wie du bereits sagtest, ist hier das problem, maximal $FE zeichen hintereinander codieren zu können, bei vielen gleichen zeichen habe ich dadurch keine "gute" ( was ist bei rle schon gut? ) kompression gehabt. Aus dem grund wollte ich darauf verzichten.

Außerdem hatte ich probleme mit den flags, da ich zwischendurch noch unkomprimierten text unterbringen wollte um zu vermeiden dass FF01XXFF01XX als ergebnis herauskommt.

[himitsu]

Zitat:

(Da kein Zeichen 0 mal wiederholt wird, hab ich zum Anzahlbyte immer +1 gezählt.)

Es wird aber auch kein Zeichen 1-mal wiederholt, also wenn du den Fall von den "einmal Marker" schon mit dem doppeltem Marker abfängst.
(gut, in soeinem Fall spart man sich dann sogar jeweil 1 Byte, wenn der Marker kodiert wird) und wie oft kommt es vor, daß sich ein Zeichen mal mehr als 200 Mal wiederholt, aber selbst wenn, dann hat man damit dann immernoch eine maximale Kompressionsrate von 1/256*3 = 98,8% .

Delphi-Quellcode:

function LauflängenKodierung(S: String): String;
var
  i, a: Integer;
  c: Char;
begin
  i := 1;
  while i <= Length(S) do
    if (i < Length(S)) and (S[i] = S[i + 1]) then begin
      c := S[i];
      a := i + 1;
      while (a < Length(S)) and (S[a] = S[a + 1]) and (a - i < 256) do Inc(a);
      Dec(a, i);
      Delete(S, i, a);
      Insert(#0 + Char(a) + C, S, i);
      Inc(i, 3);
    end else if S[i] = #0 then begin
      Insert(#0#1#0, S, i + 1);
      Inc(i, 3);
    end else Inc(i);
  Result := S;
end;

function LauflängenDekodierung(S: String): String;
var
  i, a: Integer;
  c: Char;
begin
  i := 1;
  while i < Length(S) - 1 do
    if S[i] = #0 then begin
      a := Ord(S[i + 1]);
      c := S[i + 2];
      Delete(S, i, 3);
      Insert(StringOfChar(c, a), S, i);
      Inc(i, a);
    end else Inc(i);
  Result := S;
end;

(ungetestet, da nur so dahingeschrieben)

[edit]
hatte die ersten beiden Parameter beim Inset vertauscht