RLE (16-Bit)

Startseite < Informatik < Algorithmen < Sortieren Komprimieren < RLE < RLE (8-Bit) [ DRUCK , 2004 , 2005 , 2006 , 2007 , 2008 , 2009 ] RLE (16-Bit) RLE (24-Bit) RLE (32-Bit) RLE (alternierend) > Huffman Lempel-Ziv > Suchen / Primzahltest > Datenstrukturen / Software-Engineering / Programmiersprachen / Künstliche Intelligenz > Schach Privates / Inhalt >

RLE (16-Bit)

Implementierung Implementierung des 16-Bit-RLE

Folgende Implementierung unter Delphi 5 ist weitgehend analog zur RLE-8Bit-Implementierung (siehe RLE (8-Bit) ), deshalb habe ich auch weitgehend die Kommentare weggelassen.

Wenn von Analogie die Rede ist, muss man auch hervorheben, wo genau der Unterschied vorhanden ist. Der wesentliche Unterschied liegt darin, dass gleiche Vorkommen von 16Bit-Zeichen komprimiert werden, gleiche Vorkommen von 8Bit-Zeichen werden dagegen nicht komprimiert. Statt den Methoden Try8BitCompress und Decode8 werden hier die Methoden Try16BitCompress und Decode16 verwendet, sonst bleibt alles beim Alten.

Es ist mir durchaus bewusst, dass die folgende Implementierung nicht sehr effizient ist. Mir kommt es hier mehr auf die Semantik bzw. Lesbarkeit an, auch wenn die Effizienz darunter leiden sollte.

Kompression und Dekompression: 16-Bit-RLE


unit URle16Bit;



interface



uses

  Classes;



procedure RLE16Compress(Source, Destination: TMemoryStream);

procedure RLE16Decompress(Source, Destination: TMemoryStream);



implementation



type

  T8Bit = Byte;

  T16Bit = Word;



const

  CodeFlag: T8Bit = $FF; // binär: 1111 1111

  NoCode: T8Bit = $00;   // binär: 0000 0000 aus T8Bit\[1..MaxCount]

  MaxCount: T8Bit = $FE; // binär: 1111 1110









procedure RLE16Compress(Source, Destination: TMemoryStream);



  function Try16BitCompress: Boolean;

  var

    Counting: Boolean;

    Count: T8Bit;

    Try16Bit: packed array[0..2] of T16Bit; // drei 16Bit-Zeichen

    Next16Bit: T16Bit;

  begin

    Result := FALSE;

    // Existenz von drei 16Bit-Zeichen

    if (Source.Size - Source.Position < SizeOf(Try16Bit)) then Exit;

    // Vergleich der drei 16Bit-Zeichen

    Source.ReadBuffer(Try16Bit, SizeOf(Try16Bit));

    Source.Position := Source.Position - SizeOf(Try16Bit);

    if (Try16Bit[0] <> Try16Bit[1]) then Exit;

    if (Try16Bit[1] <> Try16Bit[2]) then Exit;

    // Neuer Rückgabewert: Komprimierversuch gelingt!

    Result := TRUE;

    Source.Position := Source.Position + SizeOf(Try16Bit);

    Count := High(Try16Bit) - Low(Try16Bit) + 1; // Länge der Prüfsequenz



    if (Source.Size - Source.Position >= SizeOf(Next16Bit)) then

      repeat

        Source.ReadBuffer(Next16Bit, SizeOf(Next16Bit));

        Counting := (Try16Bit[0] = Next16Bit);

        if Counting then Inc(Count, 1)

        else Source.Position := Source.Position - SizeOf(T16Bit);

      until (not Counting) or (Count >= MaxCount) or

            (Source.Size - Source.Position < SizeOf(T16Bit));



    Destination.WriteBuffer(CodeFlag, SizeOf(CodeFlag));

    Destination.WriteBuffer(Count, SizeOf(Count));

    Destination.WriteBuffer(Try16Bit[0], SizeOf(Try16Bit[0]));

  end;



  procedure NoCompress;

  var

    Next: T8Bit;

  begin

    if (Source.Size - Source.Position < SizeOf(T8Bit)) then Exit;

    Source.ReadBuffer(Next, SizeOf(Next));

    Destination.WriteBuffer(Next, SizeOf(Next));

    if (Next = CodeFlag) then Destination.WriteBuffer(NoCode, SizeOf(NoCode));

  end;



begin

 Source.Position := 0;

 Destination.Clear;



 while (Source.Size - Source.Position >= SizeOf(T8Bit)) do

   if not Try16BitCompress then NoCompress;



 Source.Position := 0;

 Destination.Position := 0;

end;









procedure RLE16Decompress(Source, Destination: TMemoryStream);

var

  CodeCount: T8Bit;

  Next: T8Bit;



  procedure Decode16(Count: T8Bit);

  var

    i: T8Bit;

    MultiNext: T16Bit;

  begin

    Source.ReadBuffer(MultiNext, SizeOf(MultiNext));

    for i := Count downto 1 do

      Destination.WriteBuffer(MultiNext, SizeOf(MultiNext));

  end;



begin

  Source.Position := 0;

  Destination.Clear;



  while (Source.Size - Source.Position >= SizeOf(T8Bit)) do

  begin

    Source.ReadBuffer(Next, SizeOf(Next));

    if (Next = CodeFlag) then

    begin

      Source.ReadBuffer(CodeCount, SizeOf(CodeCount));

      if (CodeCount = NoCode) then Destination.WriteBuffer(Next, SizeOf(Next))

      else Decode16(CodeCount);

    end

    else Destination.WriteBuffer(Next, SizeOf(Next));

  end;



  Source.Position := 0;

  Destination.Position := 0;

end;



end.

⇑ Kompression und Dekompression: 16-Bit-RLE ⇑

Beispiele Beispiele zu 16-Bit-RLE

Text-Beispiel

Das folgende Beispiel ist eine Text-Datei.

Die Zeichenfolge '0D 0A' ist ein Zeilenumbruch.

Klartext (Text)

Zeile	00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15	Text
00 16 32 48 64	48 61 61 61 61 61 61 61 61 61 61 61 61 6C 6C 6F 21 21 21 0D 0A 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 63 68 20 62 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 69 6E 73 21 21 21 21	Haaaaaaaaaaaallo !!!··iiiiiiiiiii iiiiiiiiiiiiiiii ch biiiiiiiiiiii iiiiiiiiins!!!!

Komprimat (Text)

Zeile	00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15	Text
00 16 32	48 FF 06 61 61 6C 6C 6F 21 21 21 0D 0A FF 0D 69 69 69 63 68 20 62 FF 0A 69 69 69 6E 73 21 21 21 21	H•·aallo!!!··•·i iich b•·iiins!!! !

Bitmap-Beispiel

Das folgende Beispiel ist eine 16-Farben-Bitmap-Datei, die ein graues X auf schwarzem Hintergrund repräsentiert. Diese Datei kann fasst auf die Hälfte herunterkomprimiert werden.

Klartext (Bitmap)

Zeile	00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15	Text
000 016 032 048 064 080 096 112 128 144 160 176 192 208 224 240 256 272 288 304 320 336 352 368 384 400 416 432 448 464 480 496 512 528 544 560 576 592 608 624	42 4D 76 02 00 00 00 00 00 00 76 00 00 00 28 00 00 00 20 00 00 00 20 00 00 00 01 00 04 00 00 00 00 00 00 02 00 00 CE 0E 00 00 CE 0E 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 80 00 00 80 00 00 00 80 80 00 80 00 00 00 80 00 80 00 80 80 00 00 C0 C0 C0 00 80 80 80 00 00 00 FF 00 00 FF 00 00 00 FF FF 00 FF 00 00 00 FF 00 FF 00 FF FF 00 00 FF FF FF 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 77 77 00 00 00 00 00 00 00 00 77 77 00 00 00 00 77 77 00 00 00 00 00 00 00 00 77 77 00 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 00 77 77 77 77 77 77 77 77 77 77 00 00 00 00 00 00 77 77 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 00 00 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 00 00 00 00 00 00 00 77 77 77 77 77 77 77 77 77 77 00 00 00 00 00 00 77 77 77 77 77 77 77 77 77 77 00 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 77 77 77 77 00 00 00 00 00 00 77 77 77 77 00 00 00 77 77 00 00 00 00 00 00 00 00 77 77 00 00 00 00 77 77 00 00 00 00 00 00 00 00 77 77 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00	BMv·······v···(· ·· ··· ········· ······•···•····· ············•··• ···••·•···•·•·•• ··•••·•••···•··• ···••·•···•·•·•• ··•••··········· ················ ········ww······ ··ww····ww······ ··ww···wwww····· ·wwww··wwww····· ·wwww··wwwww···· wwwww··wwwww···· wwwww···wwwww··w wwww····wwwww··w wwww·····wwwwwww www······wwwwwww www·······wwwwww ww········wwwwww ww·········wwwww w··········wwwww w··········wwwww w··········wwwww w·········wwwwww ww········wwwwww ww·······wwwwwww www······wwwwwww www·····wwwww··w wwww····wwwww··w wwww···wwwww···· wwwww··wwwww···· wwwww··wwww····· ·wwww··wwww····· ·wwww···ww······ ··ww····ww······ ··ww············ ················ ······

Komprimat (Bitmap)

Zeile	00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15	Text
000 016 032 048 064 080 096 112 128 144 160 176 192 208 224 240 256 272 288 304 320 336 352 368 384 400 416 432	42 4D 76 02 FF 03 00 00 76 00 00 00 28 00 00 00 20 00 00 00 20 00 00 00 01 00 04 FF 03 00 00 02 00 00 CE 0E 00 00 CE 0E FF 08 00 00 80 00 00 80 00 00 00 80 80 00 80 00 00 FF 03 00 80 80 00 00 C0 C0 C0 00 80 80 80 00 00 00 FF 00 00 00 FF 00 00 00 00 FF 00 FF 00 00 FF 00 00 00 FF 03 00 FF FF 00 00 00 FF 00 FF 00 FF 00 FF 11 00 00 00 77 77 FF 04 00 00 77 77 00 00 00 00 77 77 FF 04 00 00 77 77 00 00 00 77 77 77 77 FF 03 00 00 77 77 77 77 00 00 77 77 77 77 FF 03 00 00 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 00 FF 05 77 77 FF 03 00 00 FF 05 77 77 FF 03 00 00 00 FF 04 77 77 FF 04 00 00 FF 04 77 77 FF 04 00 00 00 FF 03 77 77 FF 05 00 00 FF 03 77 77 FF 05 00 00 FF 03 77 77 FF 05 00 00 FF 03 77 77 FF 04 00 00 00 FF 04 77 77 FF 04 00 00 FF 04 77 77 FF 03 00 00 00 FF 05 77 77 FF 03 00 00 FF 05 77 77 00 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 77 00 00 00 00 77 77 77 77 77 00 00 77 77 77 77 FF 03 00 00 77 77 77 77 00 00 77 77 77 77 FF 03 00 00 77 77 77 77 00 00 00 77 77 FF 04 00 00 77 77 00 00 00 00 77 77 FF 04 00 00 77 77 FF 11 00 00	BMv·•···v···(··· ··· ······•···· ··•···•·•···•··• ···••·•··•··••·· •••·•••···•···•· ···•·•··•···•··• •···•·•·•·•····w w•···ww····ww•·· ·ww···wwww•···ww ww··wwww•···wwww ··wwwww····wwwww ··wwwww····wwwww ···wwwww··wwwww· ···wwwww··wwwww· ····•·ww•···•·ww •····•·ww•···•·w w•····•·ww•···•· ww•···•·ww•···•· ww•····•·ww•···• ·ww•····•·ww•··· •·ww·····wwwww·· wwwww····wwwww·· wwwww···wwwww··· ·wwwww··wwwww··· ·wwwww··wwww•··· wwww··wwww•···ww ww···ww•···ww··· ·ww•···ww•···

Unrealistisches Beispiel

Das folgende Beispiel ist eine Text-Datei mit 220 a's gefolgt von 2 Blanks gefolgt von 300 b's gefolgt von 2 Blanks gefolgt von 220 c's

Dieses Beispiel ist recht unrealistisch; derartige Dateien sind selten!

Klartext (unrealistisch)

Zeile	00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15	Text
000 016 032 048 064 080 096 112 128 144 160 176 192 208 224 240 256 272 288 304 320 336 352 368 384 400 416 432 448 464 480 496 512 528 544 560 576 592 608 624 640 656 672 688 704 720 736	61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 61 20 20 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 62 20 20 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63 63	aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaa aaaaaaaaaaaa bb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbbbbbbbb bbbbbbbbbb cccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccccccccccc cccccccc

Komprimat (unrealistisch)

Zeile	00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15	Text
00	FF 6E 61 61 20 20 FF 96 62 62 20 20 FF 6E 63 63	•naa ••bb •ncc

Startseite Sitemap Downloads Hilfe Impressum