LZ78圧縮をpythonで実装した

この記事は、 大阪工業大学 [Advent Calendar 2021](https://adventar.org/calendars/6716)の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クラスの実装
圧縮する配列を保存するためのクラスを定義
###イニシャライザ
```python:FileArrayClass
class FileArray:
    def __init__(self, array):
        self.size = len(array)
        self.array = array
```
`size`：圧縮する配列の長さを保存
`array`：圧縮する配列を保存

##Wordクラスの実装
圧縮に使用する辞書の単語を定義
###イニシャライザ
```python: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クラスの実装
圧縮に使用する辞書の定義
###イニシャライザ
```python: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が代入される。

###辞書に単語を追加する関数
```python: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個目の登録がされた時に一番古い単語を削除する。
強制的に登録するため外部から参照されないよう”プライベート関数”にしている。（参照できないわけではない）

###辞書に登録するか否かを判定する関数
```python: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`を返却、そうでなければ検索に一致した単語の辞書番号を返却する

###辞書を作成する関数
```python: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を使用した

```bash
% pip install tqdm
```

###辞書を出力する関数
```python: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する

##エンコード関数
```python
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`に圧縮するバイト長を入力して使用する。

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

```bash
% python3 main.py test1.txt
100%|██████████████████████████████████████████████████| 1911/1911 [00:00<00:00, 93712.40it/s]                    
1911 -> 1574 | 0.8236525379382522
```
1911バイトのデータが1574バイトに圧縮できた

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

https://github.com/GenichiMaruo/Experiments