Algorithms with Python

• 2007/06/25
  • バイナリレンジコーダの修正にともない、評価結果を修正

●プログラムリスト１

# coding: utf-8
#
# lzrc0.py : LZSS 符号 + バイナリレンジコーダ (order-0)
#
#            Copyright (C) 2007 Makoto Hiroi
#
import time, sys, getopt, os.path
from rangecoder2 import *

# 定数
MIN_LEN = 4
MAX_LEN = 256
POS_BITS = 16

# スライド窓
class Slide:
    def __init__(self, file):
        self.file = file
        self.size = 1 << POS_BITS
        self.limit = self.size * 2
        self.next = [None] * self.size
        self.ht = {}
        self.too_many_flag = {}
        self.buff = [0] * (self.limit + MAX_LEN)
        self.data_size = self.fread(0, self.limit + MAX_LEN)
        self.match_len = 0
        self.match_pos = 0

    # データ入力
    def fread(self, start, size):
        for i in xrange(size):
            c = getc(self.file)
            if c is None: return i
            self.buff[start + i] = c
        return size

    # データ移動
    def move_data(self, to, from_, size):
        for n in xrange(size):
            self.buff[to + n] = self.buff[from_ + n]

    # スライド窓の更新
    def update(self, rp):
        if self.data_size < self.limit + MAX_LEN: return rp
        # buffer update
        self.move_data(0, self.size, self.size + MAX_LEN)
        n = self.fread(self.size + MAX_LEN, self.size)
        self.data_size = self.size + MAX_LEN + n
        # hash update
        for k, v in self.ht.items():
            if v < self.size:
                del self.ht[k]
            else:
                self.ht[k] = v - self.size
        #
        for x in xrange(self.size):
            v = self.next[x]
            if v == None or v < self.size:
                self.next[x] = None
            else:
                self.next[x] = v - self.size
        self.too_many_flag.clear()
        return rp - self.size

    # ハッシュ関数
    def hash_value(self, rp):
        value = 0
        for x in xrange(MIN_LEN):
            value = (value << 8) + self.buff[rp + x]
        return value

    # データの挿入
    def insert(self, rp):
        value = self.hash_value(rp)
        if value in self.ht:
            self.next[rp & (self.size - 1)] = self.ht[value]
        else:
            self.next[rp & (self.size - 1)] = None
        self.ht[value] = rp

    # データの探索
    def search(self, rp):
        b = self.buff
        value = self.hash_value(rp)
        limit = rp - self.size
        self.match_len = 0
        self.match_pos = 0
        offset = 0
        while value in self.too_many_flag:
            if offset >= MAX_LEN - MIN_LEN or len(b) - (rp + offset) < MIN_LEN:
                offset = 0
                value = self.hash_value(rp)
                break
            offset += 1
            value = self.hash_value(rp + offset)
        #
        while True:
            count = 0
            if value in self.ht:
                n = self.ht[value]
            else:
                n = None
            while n is not None and n - offset >= limit:
                count += 1
                if b[rp + self.match_len] == b[n + self.match_len - offset]:
                    x = 0
                    while x < MAX_LEN:
                        if b[rp + x] != b[n + x - offset]: break
                        x += 1
                    if self.match_len < x:
                        self.match_len = x
                        self.match_pos = n - offset
                        if x == MAX_LEN: break
                n = self.next[n & (self.size - 1)]
            if count > 256: self.too_many_flag[value] = True
            if self.match_len >= offset + MIN_LEN or offset == 0: break
            # 再検索
            offset = 0
            value = self.hash_value(rp)
        # データの終端をチェック
        if self.match_len >= self.data_size - rp:
            self.match_len = self.data_size - rp

# 出現頻度表の初期化
def init_freq():
    global freq_flag, freq_code, freq_pos, freq_len
    freq_flag = AlphaFreq(2)
    freq_code = Freq2(256)
    freq_len = GammaFreq(MAX_LEN - MIN_LEN + 1)
    freq_pos = GammaFreq(1 << POS_BITS)


# LZRC 符号の符号化
def encode(fin, fout):
    init_freq()
    rc = RangeCoder(fout, ENCODE)
    s = Slide(fin)
    rp = 0
    while rp < s.data_size:
        s.search(rp)
        if s.match_len < MIN_LEN:
            num = 1
            freq_flag.encode(rc, 0)
            freq_code.encode(rc, s.buff[rp])
        else:
            num = s.match_len
            freq_flag.encode(rc, 1)
            freq_len.encode(rc, num - MIN_LEN)
            freq_pos.encode(rc, rp - s.match_pos - 1)
        for _ in xrange(num):
            s.insert(rp)
            rp += 1
            if rp >= s.limit: rp = s.update(rp)
    rc.finish()

# 符号化
def encode_file(name1, name2):
    size = os.path.getsize(name1)
    infile = open(name1, "rb")
    outfile = open(name2, "wb")
    putc(outfile, (size >> 24) & 0xff)
    putc(outfile, (size >> 16) & 0xff)
    putc(outfile, (size >> 8) & 0xff)
    putc(outfile, size & 0xff)
    if size > 0: encode(infile, outfile)
    infile.close()
    outfile.close()

# LZRC 符号の復号
def decode(fin, fout, size):
    init_freq()
    rc = RangeCoder(fin, DECODE)
    rp = 0
    buff = [0] * (1 << POS_BITS)
    while size > 0:
        if freq_flag.decode(rc):
            num = freq_len.decode(rc) + MIN_LEN
            pos = freq_pos.decode(rc) + 1
            pos = rp - pos
            if pos < 0: pos += len(buff)
            for _ in xrange(num):
                c = buff[pos]
                putc(fout, c)
                buff[rp] = c
                pos += 1
                rp += 1
                if pos >= len(buff): pos = 0
                if rp >= len(buff): rp = 0
        else:
            num = 1
            c = freq_code.decode(rc)
            putc(fout, c)
            buff[rp] = c
            rp += 1
            if rp >= len(buff): rp = 0
        size -= num

# 復号
def decode_file(name1, name2):
    infile = open(name1, "rb")
    outfile = open(name2, "wb")
    size = 0
    for _ in xrange(4):
        size = (size << 8) + getc(infile)
    if size > 0: decode(infile, outfile, size)
    infile.close()
    outfile.close()

#
def main():
    eflag = False
    dflag = False
    opts, args = getopt.getopt(sys.argv[1:], 'ed')
    for x, y in opts:
        if x == '-e' or x == '-E':
            eflag = True
        elif x == '-d' or x == '-D':
            dflag = True
    if eflag and dflag:
        print 'option error'
    elif eflag:
        encode_file(args[0], args[1])
    elif dflag:
        decode_file(args[0], args[1])
    else:
        print 'option error'

#
s = time.clock()
main()
e = time.clock()
print "%.3f" % (e - s)

●プログラムリスト２

# coding: utf-8
#
# lzrc1.py : LZSS 符号 + バイナリレンジコーダ (order-1)
#
#            Copyright (C) 2007 Makoto Hiroi
#
import time, sys, getopt, os.path
from rangecoder2 import *

# 定数
MIN_LEN = 6
MAX_LEN = 256
POS_BITS = 16

# スライド窓
class Slide:
    def __init__(self, file):
        self.file = file
        self.size = 1 << POS_BITS
        self.limit = self.size * 2
        self.next = [None] * self.size
        self.ht = {}
        self.too_many_flag = {}
        self.buff = [0] * (self.limit + MAX_LEN)
        self.data_size = self.fread(0, self.limit + MAX_LEN)
        self.match_len = 0
        self.match_pos = 0

    # データ入力
    def fread(self, start, size):
        for i in xrange(size):
            c = getc(self.file)
            if c is None: return i
            self.buff[start + i] = c
        return size

    # データ移動
    def move_data(self, to, from_, size):
        for n in xrange(size):
            self.buff[to + n] = self.buff[from_ + n]

    # スライド窓の更新
    def update(self, rp):
        if self.data_size < self.limit + MAX_LEN: return rp
        # buffer update
        self.move_data(0, self.size, self.size + MAX_LEN)
        n = self.fread(self.size + MAX_LEN, self.size)
        self.data_size = self.size + MAX_LEN + n
        # hash update
        for k, v in self.ht.items():
            if v < self.size:
                del self.ht[k]
            else:
                self.ht[k] = v - self.size
        #
        for x in xrange(self.size):
            v = self.next[x]
            if v == None or v < self.size:
                self.next[x] = None
            else:
                self.next[x] = v - self.size
        self.too_many_flag.clear()
        return rp - self.size

    # ハッシュ関数
    def hash_value(self, rp):
        value = 0
        for x in xrange(MIN_LEN):
            value = (value << 8) + self.buff[rp + x]
        return value

    # データの挿入
    def insert(self, rp):
        value = self.hash_value(rp)
        if value in self.ht:
            self.next[rp & (self.size - 1)] = self.ht[value]
        else:
            self.next[rp & (self.size - 1)] = None
        self.ht[value] = rp

    # データの探索
    def search(self, rp):
        b = self.buff
        value = self.hash_value(rp)
        limit = rp - self.size
        self.match_len = 0
        self.match_pos = 0
        offset = 0
        while value in self.too_many_flag:
            if offset >= MAX_LEN - MIN_LEN or len(b) - (rp + offset) < MIN_LEN:
                offset = 0
                value = self.hash_value(rp)
                break
            offset += 1
            value = self.hash_value(rp + offset)
        #
        while True:
            count = 0
            if value in self.ht:
                n = self.ht[value]
            else:
                n = None
            while n is not None and n - offset >= limit:
                count += 1
                if b[rp + self.match_len] == b[n + self.match_len - offset]:
                    x = 0
                    while x < MAX_LEN:
                        if b[rp + x] != b[n + x - offset]: break
                        x += 1
                    if self.match_len < x:
                        self.match_len = x
                        self.match_pos = n - offset
                        if x == MAX_LEN: break
                n = self.next[n & (self.size - 1)]
            if count > 256: self.too_many_flag[value] = True
            if self.match_len >= offset + MIN_LEN or offset == 0: break
            # 再検索
            offset = 0
            value = self.hash_value(rp)
        # データの終端をチェック
        if self.match_len >= self.data_size - rp:
            self.match_len = self.data_size - rp

# 出現頻度表の初期化
def init_freq():
    global freq_flag, freq_code, freq_pos, freq_len
    freq_flag = [AlphaFreq(2), AlphaFreq(2)]
    freq_code = [Freq2(256) for _ in xrange(256)]
    freq_len = GammaFreq(MAX_LEN - MIN_LEN + 1)
    freq_pos = GammaFreq(1 << POS_BITS)


# LZRC 符号の符号化 (order-1)
def encode(fin, fout):
    init_freq()
    rc = RangeCoder(fout, ENCODE)
    s = Slide(fin)
    rp = 0
    c0 = 0
    f0 = 0
    while rp < s.data_size:
        s.search(rp)
        if s.match_len < MIN_LEN:
            num = 1
            freq_flag[f0].encode(rc, 0)
            freq_code[c0].encode(rc, s.buff[rp])
            f0 = 0
        else:
            num = s.match_len
            freq_flag[f0].encode(rc, 1)
            freq_len.encode(rc, num - MIN_LEN)
            freq_pos.encode(rc, rp - s.match_pos - 1)
            f0 = 1
        for _ in xrange(num):
            c0 = s.buff[rp]
            s.insert(rp)
            rp += 1
            if rp >= s.limit: rp = s.update(rp)
    rc.finish()

# 符号化
def encode_file(name1, name2):
    size = os.path.getsize(name1)
    infile = open(name1, "rb")
    outfile = open(name2, "wb")
    putc(outfile, (size >> 24) & 0xff)
    putc(outfile, (size >> 16) & 0xff)
    putc(outfile, (size >> 8) & 0xff)
    putc(outfile, size & 0xff)
    if size > 0: encode(infile, outfile)
    infile.close()
    outfile.close()

# LZRC 符号の復号 (order-1)
def decode(fin, fout, size):
    init_freq()
    rc = RangeCoder(fin, DECODE)
    rp = 0
    c0 = 0
    f0 = 0
    buff = [0] * (1 << POS_BITS)
    while size > 0:
        if freq_flag[f0].decode(rc):
            num = freq_len.decode(rc) + MIN_LEN
            pos = freq_pos.decode(rc) + 1
            pos = rp - pos
            if pos < 0: pos += len(buff)
            for _ in xrange(num):
                c = buff[pos]
                putc(fout, c)
                c0 = c
                buff[rp] = c
                pos += 1
                rp += 1
                if pos >= len(buff): pos = 0
                if rp >= len(buff): rp = 0
            f0 = 1
        else:
            num = 1
            c = freq_code[c0].decode(rc)
            putc(fout, c)
            c0 = c
            buff[rp] = c
            rp += 1
            if rp >= len(buff): rp = 0
            f0 = 0
        size -= num

# 復号
def decode_file(name1, name2):
    infile = open(name1, "rb")
    outfile = open(name2, "wb")
    size = 0
    for _ in xrange(4):
        size = (size << 8) + getc(infile)
    if size > 0: decode(infile, outfile, size)
    infile.close()
    outfile.close()

#
def main():
    eflag = False
    dflag = False
    opts, args = getopt.getopt(sys.argv[1:], 'ed')
    for x, y in opts:
        if x == '-e' or x == '-E':
            eflag = True
        elif x == '-d' or x == '-D':
            dflag = True
    if eflag and dflag:
        print 'option error'
    elif eflag:
        encode_file(args[0], args[1])
    elif dflag:
        decode_file(args[0], args[1])
    else:
        print 'option error'

#
s = time.clock()
main()
e = time.clock()
print "%.3f" % (e - s)

●プログラムリスト３

# coding: utf-8
#
# lztrc.py : LZT coding + Binary Range Coder
#
#          Copyright (C) 2007 Makoto Hiroi
#
import time, sys, getopt, os.path
from rangecoder2 import *

# 定数
DIC_BITS = 13
DIC_SIZE = 1 << DIC_BITS
HEAD = 0

##### LZT 符号 #####

# 双方向リストによるキュー
# 0 がヘッダ, 1 - 255 はダミー
class Queue:
    def __init__(self):
        self.prev = [None] * DIC_SIZE
        self.next = [None] * DIC_SIZE
        self.prev[HEAD] = HEAD
        self.next[HEAD] = HEAD

    # 最後尾に追加
    def insert(self, x):
        last = self.prev[HEAD]
        self.prev[x] = last
        self.next[x] = HEAD
        self.next[last] = x
        self.prev[HEAD] = x

    # 削除
    def delete(self, x):
        p = self.prev[x]
        q = self.next[x]
        self.next[p] = q
        self.prev[q] = p

    # 巡回
    def traverse(self):
        n = self.next[HEAD]
        while n != HEAD:
            yield n
            n = self.next[n]

# 辞書
class Dic:
    def __init__(self):
        self.sym = [None] * DIC_SIZE
        self.parent = [None] * DIC_SIZE
        self.child = [0] * DIC_SIZE
        self.ht = {}
        for x in xrange(256): self.sym[x] = x
        self.num = 256

    # 探索
    def search(self, n, c):
        key = (n, c)
        if key in self.ht: return self.ht[key]
        return None

    # 葉を探す
    def search_leaf(self, q):
        for x in q.traverse():
            if self.child[x] == 0: return x
        return None

    # 削除
    def delete(self, n):
        p = self.parent[n]
        c = self.sym[n]
        del self.ht[(p, c)]
        self.child[p] -= 1

    # 挿入
    def insert(self, q, p, c):
        if self.num == DIC_SIZE:
            n = self.search_leaf(q)
            q.delete(n)
            self.delete(n)
        else:
            n = self.num
            self.num += 1
        self.sym[n] = c
        self.parent[n] = p
        self.child[n] = 0
        self.child[p] += 1
        self.ht[(p, c)] = n
        q.insert(n)

    # 辞書番号のチェック
    def check_code(self, q, n):
        if self.num == DIC_SIZE:
            return self.search_leaf(q) != n
        return n < self.num
    
    # 出力
    def output(self, q, n, fout):
        if self.parent[n] is None:
            putc(fout, n)
            return n, 1
        else:
            m, i = self.output(q, self.parent[n], fout)
            putc(fout, self.sym[n])
            q.delete(n)
            q.insert(n)
            return m, i + 1

# LZT 符号の符号化
def encode(fin, fout):
    rc = RangeCoder(fout, ENCODE)
    freq = GammaFreq(DIC_SIZE)
    dic = Dic()
    que = Queue()
    p = getc(fin)
    while True:
        c = getc(fin)
        if c is None:
            freq.encode(rc, p)
            break
        q = dic.search(p, c)
        if q is None:
            freq.encode(rc, p)
            dic.insert(que, p, c)
            p = c
        else:
            que.delete(q)
            que.insert(q)
            p = q
    rc.finish()

# LZT 符号の復号
def decode(fin, fout, size):
    rc = RangeCoder(fin, DECODE)
    freq = GammaFreq(DIC_SIZE)
    que = Queue()
    dic = Dic()
    p = freq.decode(rc)
    c, i = dic.output(que, p, fout)
    size -= i
    while size > 0:
        q = freq.decode(rc)
        if dic.check_code(que, q):
            c, i = dic.output(que, q, fout)
            dic.insert(que, p, c)
        else:
            dic.insert(que, p, c)
            c, i = dic.output(que, q, fout)
        p = q
        size -= i

# 符号化
def encode_file(name1, name2):
    size = os.path.getsize(name1)
    infile = open(name1, "rb")
    outfile = open(name2, "wb")
    putc(outfile, (size >> 24) & 0xff)
    putc(outfile, (size >> 16) & 0xff)
    putc(outfile, (size >> 8) & 0xff)
    putc(outfile, size & 0xff)
    if size > 0: encode(infile, outfile)
    infile.close()
    outfile.close()

# 復号
def decode_file(name1, name2):
    infile = open(name1, "rb")
    outfile = open(name2, "wb")
    size = 0
    for _ in xrange(4):
        size = (size << 8) + getc(infile)
    if size > 0: decode(infile, outfile, size)
    infile.close()
    outfile.close()

#
def main():
    eflag = False
    dflag = False
    opts, args = getopt.getopt(sys.argv[1:], 'ed')
    for x, y in opts:
        if x == '-e' or x == '-E':
            eflag = True
        elif x == '-d' or x == '-D':
            dflag = True
    if eflag and dflag:
        print 'option error'
    elif eflag:
        encode_file(args[0], args[1])
    elif dflag:
        decode_file(args[0], args[1])
    else:
        print 'option error'

#
s = time.clock()
main()
e = time.clock()
print "%.3f" % (e - s)