⛑️
ランレングス符号化の書き方
配列用
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