お題:8 compress.py

入力されるデータを圧縮して出力するプログラムを作成してください。バイト列の中の繰り返し部分を次のルールを使って圧縮、バイナリ出力します。 文字(0x00〜0xFFの1バイトデータ)の繰り返しがある場合はその文字とくり返される回数を出力します。0x00を反復符号と位置付け、(反復符号)(繰り返される文字)(反復回数)の順に出力します。

  AAAAAA -> 0x00 0x41 0x06

繰り返しではない文字列の場合は(文字列の長さ)(文字列)の順に出力しま。

  ABC -> 0x03 0x41 0x42 0x43

反復回数や文字列の長さが0xFFを越える場合は複数に分割して出力します。

ishimoto at gembook.orgさんのお答え

import sys, re
_rep = re.compile(r"((.)(?:\2)+)",re.DOTALL)
_maxchar = 255

def compress(input):
    out = []

    def emit_rep(f, t, input=input, out=out):
        match_length = t - f
        rep_c = input[f]
        rep_count = match_length / _maxchar
        if rep_count:
            out.extend([chr(0x00), rep_c, chr(_maxchar)] * rep_count)
        if match_length % _maxchar:
            out.extend([chr(0), rep_c, chr(match_length % _maxchar)])

    def emit_norep(f, t, input=input, out=out):
        for pos in range(f, t, _maxchar):
            slen = min(t - pos, _maxchar)
            s = input[pos:pos+slen]
            out.extend([chr(slen), s])

    pos = 0
    while 1:
        m = _rep.search(input, pos)
        if m:
            f, t = m.span()
            if pos != f:
                emit_norep(pos, f)
            emit_rep(f, t)
            pos = t
        else:
            if pos != len(input):
                emit_norep(pos, len(input))
            break
    return "".join(out)
    
sys.stdout.write(compress(sys.stdin.read()))

VED03370 at nifty.ne.jpさんのお答え

MAXLEN=255

def compress(infile, outfile):
    target=infile.read(MAXLEN)
    while target:
        compressing=0
        prev=''
        for i in range(len(target)):
            if compressing and prev!=target[i]:
                outfile.write(str_repeated(prev,i))
                break
            elif not compressing and prev==target[i]:
                if i==1:
                    compressing=1
                elif i>1:
                    i -= 1
                    outfile.write(str_through(target[:i]))
                    break
            prev=target[i]
        else:
            if compressing:
                outfile.write(str_repeated(prev,len(target)))
            else:
                outfile.write(str_through(target))
            target=infile.read(MAXLEN)
            continue
        if i<len(target):
            target=target[i:]+infile.read(i)

def str_repeated(char,cnt):
    return chr(0)+char+chr(cnt)
def str_through(text):
    return chr(len(text))+text

if __name__=='__main__':
    import sys
    compress(sys.stdin,sys.stdout)

takinaka at cp.jp.nec.comさんのお答え

MAXCNT = 255

class Compressor:
    def __init__(self, input=None):
	self.ch = None
	self.cnt = 0
	self.temp = []
	self.list = []
	if input:
	    self.input(input)

    def reduce(self, mode=1):
	mode |= (self.cnt > 1)
	if self.cnt == 1:
	    self.temp.append(self.ch)
	    self.cnt = 0
	while mode and self.temp:
	    n = min(len(self.temp), MAXCNT)
	    self.list.extend([chr(n)]+self.temp[:n])
	    self.temp = self.temp[n:]
	while self.cnt > 0:
	    n = min(self.cnt, MAXCNT)
	    self.list.extend(chr(0)+self.ch+chr(n))
	    self.cnt -= n
	return self

    def inputchar(self, c):
	if c == self.ch:
	    self.cnt += 1
	else:
	    self.reduce(0)
	    self.ch = c
	    self.cnt = 1

    def input(self, str):
	for c in str:
	    self.inputchar(c)
	return self

    def output(self):
	self.reduce()
	return "".join(self.list)

def compress(input):
    return Compressor(input).output()

def compresstolist(input):
    return Compressor(input).reduce().list

if __name__ == '__main__':
    #print compress('abcccd')
    print compresstolist('abcccdeeeedaa')

suzuki at acm.orgさんのお答え

def compress(read, write):
    c_len = 0
    buf = []
    while 1:
        ch = read(1)
        if c_len == 0:
            if ch == '':                # EOF
                if buf: _write_buf(write, buf)
                break
            else:
                if buf and buf[-1] == ch:
                    del buf[-1]
                    if buf: _write_buf(write, buf)
                    c_ch = ch; c_len = 2
                else:
                    if len(buf) == 255:
                        _write_buf(write, buf)
                    buf.append(ch)
        else:
            if ch == '':                # EOF
                _write_compressed(write, c_ch, c_len)
                break
            else:
                if c_ch != ch:
                    _write_compressed(write, c_ch, c_len)
                    c_len = 0
                    buf.append(ch); assert len(buf) == 1
                else:
                    if c_len == 255:
                        _write_compressed(write, c_ch, c_len)
                        c_len = 0
                    c_len += 1

def _write_buf(write, buf):
    assert 2 <= len(buf) <= 255
    write(chr(len(buf)))
    for ch in buf: write(ch)
    del buf[:]

def _write_compressed(write, c_ch, c_len):
    assert 2 <= c_len <= 255
    write('\0'); write(c_ch); write(chr(c_len))

if __name__ == '__main__':
    import sys
    compress(sys.stdin.read, sys.stdout.write)

suzuki at acm.orgさんの高速化バージョン

from __future__ import nested_scopes

def compress(read, write):
    def write_buf():
        assert 0 <= len <= 255
        if len:
            write(chr(len)); write(''.join(buf[:len]))

    def write_compressed():
        assert 1 <= c_len <= 255
        write('\0'); write(c_ch); write(chr(c_len))

    len = c_len = 0
    buf = [None]*255
    while 1:
        chunk = read(0x2000)
        if chunk == '':                 # EOF
            if c_len == 0: write_buf()
            else: write_compressed()
            break
        for ch in chunk:
            if c_len == 0:
                if len and buf[len - 1] == ch:
                    len -= 1; write_buf()
                    c_ch = ch; c_len = 2
                else:
                    if len == 255:
                        write_buf(); len = 0
                    buf[len] = ch; len += 1
            else:
                if c_ch != ch:
                    write_compressed(); c_len = 0
                    buf[0] = ch; len = 1
                else:
                    if c_len == 255:
                        write_compressed(); c_len = 0
                    c_len += 1

if __name__ == '__main__':
    import sys
    compress(sys.stdin.read, sys.stdout.write)