(**************************************************************************) (* *) (* Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre, *) (* Kim Nguyen, Laurent Sartre *) (* *) (* Informatique - MP2I/MPI - CPGE 1re et 2e années. *) (* Cours et exercices corrigés. Éditions Ellipses, 2022. *) (* *) (* https://www.informatique-mpi.fr/ *) (* *) (**************************************************************************) (* Compression par la méthode RLE (Run-Length Encoding) Sur une chaîne de caractères 7 bits seulement. Principe : on utilise le bit de poids fort pour distinguer deux cas de figure - 0xxxxxxx : représente directement le caractère 0xxxxxxx - 1nnnnnnn 0xxxxxxx : représente nnnnnnn occurrences de 0xxxxxxx *) type compressed = string let encode s = let b = Buffer.create 1024 in let emit n c = assert (0 <= n && n <= 127); if n > 1 then Buffer.add_char b (Char.chr (128 + n)); if n > 0 then Buffer.add_char b c in let rec encode n last i = if i = String.length s then emit n last else ( let c = s.[i] in if Char.code c >= 128 then invalid_arg "encode"; if c = last && n < 127 then encode (n+1) last (i+1) else (emit n last; encode 1 c (i+1)) ) in encode 0 '\000' 0; Buffer.contents b let decode s = let b = Buffer.create 1024 in let rec decode i = if i < String.length s then ( let c = s.[i] in let n = Char.code c in if n < 128 then ( Buffer.add_char b c; decode (i + 1) ) else ( let c = s.[i+1] in for _ = 1 to n - 128 do Buffer.add_char b c done; decode (i + 2) ) ) in decode 0; Buffer.contents b