⛑️

ランレングス符号化の書き方

2023/08/14に公開

配列用

def encode(ary)
  ary.chunk(&:itself).flat_map { |v, a| [v, a.size] }
end

def decode(ary)
  ary.each_slice(2).flat_map { |v, c| [v] * c }
end
a = ["A", "A", "A", "B", "B", "B"]  # => ["A", "A", "A", "B", "B", "B"]
x = encode(a)                       # => ["A", 3, "B", 3]
decode(x)                           # => ["A", "A", "A", "B", "B", "B"]

配列を配列に圧縮する場合はとても簡単に書ける。これは将棋の持駒で順番を維持したまま簡潔な表記にしたい場合にも応用できる。

encode("金金銀銀銀銀歩歩歩歩歩歩歩歩歩".chars).join  # => "金2銀4歩9"

バイナリ用 (バグってる)

バイナリ (または文字列) をバイナリにエンコードするには unpack と pack を仲介するのがわかりやすい。

def encode(str)
  a = str.unpack("C*")
  a = a.chunk(&:itself).flat_map { |v, a| [v, a.size] }
  a.pack("C*")
end

def decode(bin)
  a = bin.unpack("C*")
  a = a.each_slice(2).flat_map { |v, c| [v] * c }
  a.pack("C*")
end
str = "AAABBB"     # => "AAABBB"
bin = encode(str)  # => "A\x03B\x03"
decode(bin)        # => "AAABBB"

ただ1つ問題がある。256 文字以上続くと個数が 0 に戻ってしまう。

str = "A" * 256
bin = encode(str)  # => "A\x00"
decode(bin)        # => ""

バイナリ用 (改良版)

chunk を chunk.with_index の形にしてキーを 255 カウント毎に変えるようにすると 255 文字でいったん打ち切るようになる。

def encode(str)
  a = str.unpack("C*")
  a = a.chunk.with_index { |e, i| [e, i / 255] }
  a = a.flat_map { |(v, _), a| [v, a.size] }
  a.pack("C*")
end
str = "A" * 256
bin = encode(str)         # => "A\xFFA\x01"
decode(bin).truncate(16)  # => "AAAAAAAAAAAAA..."

バイナリ用 (自力版)

chunk を使わないとわりとたいへん。

def encode(str)
  av = str.unpack("C*")
  bin = []
  count = 0
  current = av[0]
  av.each do |e|
    if e != current
      bin.push(current, count)
      current = e
      count = 0
    elsif count == 255
      bin.push(e, count)
      count = 0
    end
    count += 1
  end
  if count > 0
    bin.push(current, count)
  end
  bin.pack("C*")
end
str = "A" * 256
bin = encode(str)         # => "A\xFFA\x01"
decode(bin).truncate(16)  # => "AAAAAAAAAAAAA..."

Discussion