Wikipediaのbzip2圧縮アルゴリズムの一部を読んだので意訳して紹介します。 参考にしたソースコードは bzip2-1.0.6 です。 Wikipedia https://en.wikipedia.org/wiki/Bzip2#Initial_run-length_encoding bzip2 ソースコード https://github.com/junkawa/bzip2/tree/master/bzip2-1.0.6 概要 bzip2では、入力データを読み込んだ時( copy_input_until_stop()@bzlib.c → ADD_CHAR_TO_BLOCK() → add_pair_to_block() ) に ランレングス符号化 を行う。 Wikipedia Any sequence of 4 to 255 consecutive duplicate symbols is replaced by the first four symbols and a repeat length between 0 and 251. 4〜255回、同じシンボルが連続した場合、「最初の4シンボル+残りの繰り返し回数」に置き換わる。 Thus the sequence "AAAAAAABBBBCCCD" is replaced with "AAAA\3BBBB\0CCCD", where "\3" and "\0" represent byte values 3 and 0 respectively. "AAAAAAABBBBCCCD"は、"AAAA\3BBBB\0CCCD"に置き換わる。 AAAAAAA (Aが7回)は、最初の4シンボル(AAAA) + 残りの繰り返し回数(3)となる。 BBBB (Bが4回)は、最初の4シンボル(BBBB) + 残りの繰り返し回数(0)となる。 C,Dは連続回数が4回に達しないのでそのままとなる。 ここでは分かりやすさのため、A,B,Cというシンボルを使っているが、実際のbzip2では1シンボルは1バイト(0〜255の値)。 したがって、シンボル7