11.3. Run-Length Encoding¶
- File:
RunLengthEncoding.ml
Run-length encoding is a compression methods that works well with bit-strings with large contiguous segments of repeating 0s and 1s by encoding the lengths of such segments in the interleaved fashion, starting from 0. For instance, the following string:
0000000000000001111111000000011111111111
can be encoded via 4-bit integer representation as follows:
1111011101111011
This encoding means that we have 15 (1111 in binary) 0s, then 7 (0111 in binary) 1s, then 7 0s and finally 11 (0111) ones.
11.3.1. Design Considerations¶
In order to turn this example into an effective data compression method, we need to answer the following questions:
- How many bits do we use for representing the counts?
- What if we encounter a sequence longer that a maximal value of a counter encoding permits?
- What to do about short runs that under-use the length encoding?
We resolve those questions in the following way
- Counts are between 0 and 255, so we use 8-bit representations.
- We make all run lengths less than 256 by including runs of length 0 if needed
- We encode short runs even though doing so might lengthen the output encoding.
11.3.2. Implementation¶
The resulting encoding procedure, which makes use of the previously implemented queue data type, is as follows:
open Queues
open DLLBasedQueue
open BinaryEncodings
open Extlib.IO
let read_next_bit input = try
let bit = read_bits input 1 in
Some bit
with BatInnerIO.No_more_input -> None
It starts by reading the lengths of contiguous interleaving bit sequences from the file input
to a queue:
let compute_lengths input =
let m = 256 in
let q = mk_queue 100 in
let rec read_segments acc b =
if acc >= m - 1 then begin
enqueue q acc;
read_segments 0 (1 - b)
end
else match read_next_bit input with
| Some x ->
if x = b
then read_segments (acc + 1) b
else begin
enqueue q acc;
read_segments 1 (1 - b)
end
| None -> enqueue q acc
in
read_segments 0 0;
queue_to_list q
The obtained list is then used to write the corresponding bytes to the output channel:
let compress_binary_via_rle binary new_binary =
let segments = read_from_binary compute_lengths binary in
let rec loop out segs = match segs with
| [] -> ()
| h :: t -> (write_bits out ~nbits:8 h;
loop out t)
in
write_to_binary loop new_binary segments
The decoder is implemented similarly: the RLE decompression is simply a reversal of the initial compression. Reading 8 bits at a time from the compressed file gives us the list of segment lengths. To write this to the new binary, we just print the given number of alternating 1’s and 0’s in sequence:
let read_next_char input = try
let len = read_bits input 8 in
Some len
with BatInnerIO.No_more_input -> None
let read_lengths input =
let q = mk_queue 100 in
let rec loop _ = match read_next_char input with
| Some l -> (enqueue q l; loop ())
| None -> ()
in
loop ();
queue_to_list q
let rec write_bits_from_length out (l, b) = match l with
| [] -> ()
| h :: t -> begin
for i = 0 to h - 1 do
write_bits out ~nbits:1 b
done;
write_bits_from_length out (t, 1 - b)
end
let decompress_via_rle_into_binary archive new_binary =
let lengths = read_from_binary read_lengths archive in
write_to_binary write_bits_from_length new_binary (lengths, 0)
With the implementation of compression/decompression at place, we can test them on the particular DNA sequences:
let dna_rle_compression_test d =
let dna = "dna.tmp" in
let rle = "dna.rle" in
let dna' = "dna.new" in
write_dna_to_binary dna d;
compress_binary_via_rle dna rle;
decompress_via_rle_into_binary rle dna';
let d' = read_dna_from_binary dna' in
Sys.remove dna;
Sys.remove rle;
Sys.remove dna';
d = d'
let%test _ = dna_rle_compression_test dna_string1
let%test _ = dna_rle_compression_test dna_string2
let%test _ = dna_rle_compression_test dna_string3
let%test _ = dna_rle_compression_test dna_string4