LZ78圧縮をpythonで実装した

この記事は、 大阪工業大学 Advent Calendar 2021の24日目の記事です。

#はじめに
LZ78圧縮アルゴリズム面白そうだったので軽い気持ちで実装してみた。
突貫工事でプログラムを作ったので不備があればコメント頂けると嬉しい。

#LZ78とは
結果から出すと、ababccccccabcという文字列を0a0b1b0c4c5c3cという変換を行う。
まず、f(n)=(重複する単語の辞書番号,新規１文字)というルールで先頭から順に辞書に追加。
ただし重複する単語がなければ辞書番号には0が入れられる。
最終的にf1=(0,a),f2=(0,b),f3=(1,b),f4=(0,c),f5=(4,c),f6=(5,c),f7=(3,c)
という辞書が完成すれば先頭から順に数字と文字を取り出して終了する。
結果的に辞書の単語は先頭からa, b, ab, c, cc, ccc, abcという文字列が登録される。

解凍の手順は例えばf3=(1,b)を元の文字列に戻す場合f1+'b'であることからf1が参照される。
f1=(0,a)の参照値が0よりこれ以上参照されない。よってf1='a'が分かり、これを代入してf3='ab'と戻すことができる。

#pythonでの実装
今回のプログラムでは辞書の単語の絶対参照ではなくその単語の位置からの相対参照を使用し、参照範囲を255個までに設定した。

##FileArrayクラスの実装
圧縮する配列を保存するためのクラスを定義
###イニシャライザ

FileArrayClass

class FileArray:
    def __init__(self, array):
        self.size = len(array)
        self.array = array

size：圧縮する配列の長さを保存
array：圧縮する配列を保存

##Wordクラスの実装
圧縮に使用する辞書の単語を定義
###イニシャライザ

WordClass

class Word:
    def __init__(self, word, last_word_relative_pos, create_id):
        self.word = word
        self.newnum = word[len(word)-1]
        self.last_word_relative_pos = last_word_relative_pos
        self.create_id = create_id

クラス変数の説明
last_word_relative_pos：重複する単語の辞書番号を保存する
create_id：登録する単語の辞書番号を保存する変数
word：単語の文字列を保存する。高速化のために使用
newnum：単語の配列長を保存する。高速化のために使用

##Dictionaryクラスの実装
圧縮に使用する辞書の定義
###イニシャライザ

DictionaryClass

class Dictionary:
    def __init__(self,length):
        self.words = []
        self.search_words = []
        self.words_count = 0
        self.size = (2 ** (8 * length))-1

クラス変数の説明
words：複数単語をリスト形式で保存
search_words：単語の参照を行うために使用する。最大255個の単語を保存
words_count：辞書登録されている単語の数を保存
size：参照する範囲を保存。今回は255が代入される。

###辞書に単語を追加する関数

DictionaryClass

    def __add_word(self, word, last_word_relative_pos):
        word_obj = Word(word, last_word_relative_pos, self.words_count)
        self.search_words.insert(0, word_obj)
        if self.words_count >= self.size:
            del self.search_words[self.size]
        self.words.append(word_obj)
        self.words_count += 1

受け取ったwordを参照用辞書のリストに.insertで追加、本体の辞書に.appendで追加する。参照用の辞書は256個目の登録がされた時に一番古い単語を削除する。
強制的に登録するため外部から参照されないよう”プライベート関数”にしている。（参照できないわけではない）

###辞書に登録するか否かを判定する関数

DictionaryClass

    def check_and_add_word(self, word, id):
        pos = next((wd for wd in self.search_words if wd.word==word), None)
        if pos == None:
            self.__add_word(word, id)
            return 0
        else:
            return self.words_count - pos.create_id

入力されたwordが辞書に登録されていなければ__add_word関数に送り0を返却、そうでなければ検索に一致した単語の辞書番号を返却する

###辞書を作成する関数

DictionaryClass

    def create_dictionary(self, filearray):
        word = []
        created_id = 0
        for i in tqdm(range(filearray.size),bar_format='{l_bar}{bar:50}{r_bar}{bar:-10b}'):
            word.append(filearray.array[i])
            created_id = self.check_and_add_word(word, created_id)
            if created_id == 0:
                word = []

1. FileArrayクラスのオブジェクトfilearrayを受け取り
2. １文字ずつ取得し単語を作成
3. 辞書に登録可能か判定
4. 登録できれば新規に単語を作り直す
5. 2~4をfilearray.arrayの配列長さ分繰り返し

これによって辞書が作成される。
時間がかかる処理のため進捗確認のためのプログレスバーをコンソールに表示させた。
プログレスバー表示にはtqdmを使用した

% pip install tqdm

###辞書を出力する関数

DictionaryClass

    def export_dictionary(self):
        export_array = []
        for i in range(self.words_count):
            export_array.extend([self.words[i].last_word_relative_pos,self.words[i].newnum])
        return export_array

符号に使用するデータのみを取得して返却用のリストに追加し、終了後にreturnする

##エンコード関数

def encode(array, length):
    filearray = FileArray(array)
    dictionary = Dictionary(length)
    dictionary.create_dictionary(filearray)
    presarray = dictionary.export_dictionary()
    a = len(array)
    b = len(presarray)
    print(a,'->',b,'|',b/a)
    return presarray

arrayに圧縮前の配列、lengthに圧縮するバイト長を入力して使用する。

#エンコード結果
試しに日本国憲法前文が書かれたテキストファイルを圧縮した結果

% python3 main.py test1.txt
100%|██████████████████████████████████████████████████| 1911/1911 [00:00<00:00, 93712.40it/s]                    
1911 -> 1574 | 0.8236525379382522

1911バイトのデータが1574バイトに圧縮できた

#おわりに
githubに今回の圧縮プログラムのリポジトリを公開しているのでぜひ使ってみてください
説明を省いた解凍のプログラムもおまけで付いてます
RustのAI開発については少々お待ちを