Komprimierung : Wie geht das?

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:

zusammenfalten · markieren

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.

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:

zusammenfalten · markieren

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;

**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.)

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

zusammenfalten · markieren

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

**Medium**

Habs auch nochmal genauer nachgeschaut, nachdem es mir nach dem Schreiben seltsam vor kam: Ich hab nur Wiederholungen ab >3x kodiert, weil die Kodierung selbst ja schon 3 Byte lang ist. Dadurch wurde beim Counter 0 zu 4. Worst-Case ist bei sowas dann natürlich "FF43FFA0FF6C..." zu kodieren.

Das resultat hatte ich mit der vorgehensweise ( war mein initiales vorgehen) auch... daher müsste man ein nocodeflag einbauen, welches besagt, dass ab da uncodierter text kommt. dies soll sein falls die runs kleiner als die minimal sinvolle länge, oder falls FF im text vorkommt.

Da ich aber nicht in der lage war später wieder flag von text zu unterscheiden, bin ich davon wieder abgekommen...

**himitsu**

Zitat von qwertz543221:

Da ich aber nicht in der lage war später wieder flag von text zu unterscheiden, bin ich davon wieder abgekommen...

jupp, darum muß man die Steuerzeichen, welche so im Text vorkommen können auch irgendwie mit maskieren.
Dann gibt es diese Steuerzeichen quasi nicht mehr als Text und man braucht sie nicht zu unterscheiden.

und stimmt, ab 3 Wiederholungen lohnt es sich hier erst.

hier noch eine Variante mit der Idee den Marker als doppelten Marker zu maskieren ... das erspart dort jeweils nochmal 'nen Byte.
und die 3-Zeichengrenze eingefügt

zusammenfalten · markieren

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) - 1) and (S[i] = S[i + 1]) and (S[i] = S[i + 2]) then begin

      c := S[i];

      a := i + 2;

      while (a < Length(S)) and (S[a] = S[a + 1]) and (a - i < 257) do Inc(a);

      Dec(a, i);

      Delete(S, i, a);

      Insert(#0 + Char(a - 2) + C, S, i);

      Inc(i, 3);

    end else if S[i] = #0 then begin

      Insert(#0#0, S, i + 1);

      Inc(i, 2);

    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]);

      if a = 0 then begin

        Delete(S, i, 1);

        Inc(i);

      end else begin

        Inc(a, 2);

        c := S[i + 2];

        Delete(S, i, 3);

        Insert(StringOfChar(c, a), S, i);

        Inc(i, a);

      end;

    end else Inc(i);

  Result := S;

end;

Und was die Maximal 255 Zeichen angeht, welche man hier Kodieren kann ... klar, man könnte entweder die Längenangabe größer machen (z.B. 2 oder 4 Byte), aber da wäre auch die Komprimierungsrate geringer, da die Steuersequenz dann größer wäre.
oder man verwendet noch eine weitere Sequenz, mit einer größeren Anzahl, aber dafür braucht man auch wieder eine weiteres Steuerzeichen oder man verwendet einen weiteren wert aus der Sequenz1 für die größere Anzahl.

Aber da es selten vorkommt, daß sich ein Zeichen wirklich mal mehr als 255 Mal verfolgt, wird das doch eh zu selten gebraucht, also daß sich er Aufwand von einem weiteren Steuerzeichen lohnt.

hier sieht man, daß alleine die 256er-Grenze schon etwas mehr Aufwand bedarf:

zusammenfalten · markieren

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) - 1) and (S[i] = S[i + 1]) and (S[i] = S[i + 2]) then begin

      c := S[i];

      a := i + 2;

      while (a < Length(S)) and (S[a] = S[a + 1]) and (a - i < 65536+255) do Inc(a);

      Dec(a, i);

      Delete(S, i, a);

      if a < 255 then begin

        Insert(#0 + Char(a - 2) + C, S, i);

        Inc(i, 3);

      end else begin

        Insert(#0#255 + Char((a - 258) div 256) + Char((a - 258) mod 256) + C, S, i);

        Inc(i, 5);

      end;

    end else if S[i] = #0 then begin

      Insert(#0#0, S, i + 1);

      Inc(i, 2);

    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]);

      if a = 0 then begin

        Delete(S, i, 1);

        Inc(i);

      end else if a < 255 then begin

        Inc(a, 2);

        c := S[i + 2];

        Delete(S, i, 3);

        Insert(StringOfChar(c, a), S, i);

        Inc(i, a);

      end else begin

        a := Ord(S[i + 2]) * 256 + Ord(S[i + 3]) + 258;

        c := S[i + 4];

        Delete(S, i, 5);

        Insert(StringOfChar(c, a), S, i);

        Inc(i, a);

      end;

    end else Inc(i);

  Result := S;

end;

Zitat von himitsu:

Zitat von qwertz543221:

Da ich aber nicht in der lage war später wieder flag von text zu unterscheiden, bin ich davon wieder abgekommen...

jupp, darum muß man die Steuerzeichen, welche so im Text vorkommen können auch irgendwie mit maskieren.
Dann gibt es diese Steuerzeichen quasi nicht mehr als Text und man braucht sie nicht zu unterscheiden.

und stimmt, ab 3 Wiederholungen lohnt es sich hier erst.

hier noch eine Variante mit der Idee den Marker als doppelten Marker zu maskieren ... das erspart dort jeweils nochmal 'nen Byte.
und die 3-Zeichengrenze eingefügt

zusammenfalten · markieren

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) - 1) and (S[i] = S[i + 1]) and (S[i] = S[i + 2]) then begin

      c := S[i];

      a := i + 2;

      while (a < Length(S)) and (S[a] = S[a + 1]) and (a - i < 257) do Inc(a);

      Dec(a, i);

      Delete(S, i, a);

      Insert(#0 + Char(a - 2) + C, S, i);

      Inc(i, 3);

    end else if S[i] = #0 then begin

      Insert(#0#0, S, i + 1);

      Inc(i, 2);

    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]);

      if a = 0 then begin

        Delete(S, i, 1);

        Inc(i);

      end else begin

        Inc(a, 2);

        c := S[i + 2];

        Delete(S, i, 3);

        Insert(StringOfChar(c, a), S, i);

        Inc(i, a);

      end;

    end else Inc(i);

  Result := S;

end;

Und was die Maximal 255 Zeichen angeht, welche man hier Kodieren kann ... klar, man könnte entweder die Längenangabe größer machen (z.B. 2 oder 4 Byte), aber da wäre auch die Komprimierungsrate geringer, da die Steuersequenz dann größer wäre.
oder man verwendet noch eine weitere Sequenz, mit einer größeren Anzahl, aber dafür braucht man auch wieder eine weiteres Steuerzeichen oder man verwendet einen weiteren wert aus der Sequenz1 für die größere Anzahl.

Aber da es selten vorkommt, daß sich ein Zeichen wirklich mal mehr als 255 Mal verfolgt, wird das doch eh zu selten gebraucht, also daß sich er Aufwand von einem weiteren Steuerzeichen lohnt.

hier sieht man, daß alleine die 256er-Grenze schon etwas mehr Aufwand bedarf:

zusammenfalten · markieren

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) - 1) and (S[i] = S[i + 1]) and (S[i] = S[i + 2]) then begin

      c := S[i];

      a := i + 2;

      while (a < Length(S)) and (S[a] = S[a + 1]) and (a - i < 65538) do Inc(a);

      Dec(a, i);

      Delete(S, i, a);

      if a < 255 then begin

        Insert(#0 + Char(a - 2) + C, S, i);

        Inc(i, 3);

      end else begin

        Insert(#0#255 + Char((a - 2) div 256) + Char((a - 2) mod 256) + C, S, i);

        Inc(i, 5);

      end;

    end else if S[i] = #0 then begin

      Insert(#0#0, S, i + 1);

      Inc(i, 2);

    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]);

      if a = 0 then begin

        Delete(S, i, 1);

        Inc(i);

      end else if a < 255 then begin

        Inc(a, 2);

        c := S[i + 2];

        Delete(S, i, 3);

        Insert(StringOfChar(c, a), S, i);

        Inc(i, a);

      end else begin

        a := Ord(S[i + 2]) * 256 + Ord(S[i + 3]) + 2;

        c := S[i + 4];

        Delete(S, i, 5);

        Insert(StringOfChar(c, a), S, i);

        Inc(i, a);

      end;

    end else Inc(i);

  Result := S;

end;

Ich wäre fast der meinung, dass er bei der codierung in eine endlosscleife kommt, jedenfalls wird das programm bei mir nicht terminiert, wenn ich zb ein 270kb bild in den stream lade. bei Textdateien geht es jedoch