pythonのcursesを使ってBPEをインタラクティブに出力


TUI (テキストユーザーインタフェース) を作成するためのライブラリcursesを利用して、BPEの学習経過をいい感じに出力します。

全体のコードはgistにアップロードしています。
:arrow_right:  [bpe_curses.py](https://gist.github.com/shihono/f1a113ec00e076acbd448f0406976050)

# 環境

- macOS Catalina
- Python3.7.3
- iTerm2 (3.3.7)

# BPE

(cursesについてだけ知りたい人は読み飛ばしてください)

## BPEとは

バイトペア符号化(Byte Pair Encoding)はニューラル機械翻訳のトークナイザである[Sentencepiece](https://github.com/google/sentencepiece)にも用いられている手法です。
初出は [Neural Machine Translation of Rare Words with Subword Units](https://arxiv.org/abs/1508.07909) (ACL2016) で、実装も論文中に記載されています。

例えば、 `lower`, `newer`, `wider` のような単語があった場合、頻度の高い `e r` を一つのシンボル `er` として扱うことで、語彙数を削減できます。

このように、NLPではサブワード分割アルゴリズムとして有名ですが、そもそもはデータ圧縮手法であり、[バイト対符号化 (Wikipedia)](https://ja.wikipedia.org/wiki/バイト対符号化) にもその原理が紹介されています。

今回は、論文のコードに基づいて、その圧縮経過を出力します。

## BPE実装の概要

BPEの実装については、論文のコードをそのまま利用し、型ヒントを追加するだけに留めています。

実装は大きく二つ、関数 `get_status()` と `merge_vocab()` で成り立っています。

- `get_status` はvocab辞書を受け取り、wordの組み合わせの頻度を調べます。
   - [`defaultdict`](https://docs.python.org/ja/3.9/library/collections.html#collections.defaultdict)を使っているのは、keyにない組み合わせも扱うためです。

```python
  def get_stats(vocab: Dict) -> DefaultDict:
    pairs = collections.defaultdict(int)
    for word, freq in vocab.items():
        symbols = word.split()
        for i in range(len(symbols)-1):
            pairs[symbols[i], symbols[i+1]] += freq
    return pairs
```

- `merge_vocab` では、`get_status`で調べた組み合わせの中で、最も頻度の高い組み合わせを、ひとつのwordとして扱うためにmergeします。

```python
def merge_vocab(pair: List, v_in: Dict) -> Dict:
    v_out = {}
    bigram = re.escape(' '.join(pair))
    p = re.compile(r'(?<!<\S)' + bigram + r'(?!\S)')
    for word in v_in:
        w_out = p.sub(''.join(pair), word)
        v_out[w_out] = v_in[word]
    return v_out
```

今回は `merge_vocab` 後の単語の状態遷移を表示することにします。


# Curses

## Curses とは

> curses ライブラリは、VT100s や Linux コンソール、さまざまなプログラムが提供するエミュレーション端末といったテキストベースの端末（ターミナル）のために、端末に依存しないスクリーン描画や、キーボードの処理を提供します。
[Python で Curses プログラミング](https://docs.python.org/ja/3/howto/curses.html)より

cursesはpythonの標準モジュールです。(windows版には含まれていないようですが。。)
cursesを利用すれば、簡単にCUIアプリっぽいものが作れます。

例えば、pythonのdemoにある[life.py](https://github.com/python/cpython/blob/3.8/Tools/demo/life.py)はターミナル上で[ライフゲーム](https://ja.wikipedia.org/wiki/ライフゲーム)ができるコードです。
![lifepy.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/185967/2017d8f0-bef6-c29e-5fb9-6976b945c2cf.gif)


## Cursesの使い方

cursesで状態遷移の表示を実装していきます。

### wrapper を使おう
[Python で Curses プログラミング](https://docs.python.org/ja/3/howto/curses.html) で説明されている通り、エラー処理や初期化の煩雑さを避けるため、`curses.wrapper()` 関数を使います。

```python
import curses

def main(stdscr):
	# stdscrでcursesの処理を呼び出す

if __name__ == '__main__':
    curses.wrapper(main)
```


### 基本的な動作

基本的な処理の流れは以下のようになります。

- `stdscr.addstr(str)`: 現在の位置にテキスト `str` を追加
- `stdscr.refresh()`:  ディスプレイを更新
	- `addstr` したテキストを表示する
-  `stdscr.getkey()`: キー入力を受け付ける
	- 待ち状態の役割(ないとプログラムがそのまま終了する)

```python
for i in range(10):
    stdscr.addstr('{}\n'.format(i))
    stdscr.refresh()
    stdscr.getkey()
```

上記のようなコードの場合は数字を表示して待ち状態を繰り返します。


### 画面からのはみ出しエラーを防ぐ

画面の高さよりも長い範囲に表示しようとすると、エラーになります。

エラーを防ぐためには、最初に現在のディスプレイの大きさを取得しておいて、ディスプレイの範囲外を指定しないよう工夫が必要です。 `getmaxyx()` で大きさを取得できます。

```python
stdscr_y, stdscr_x = stdscr.getmaxyx()
```

### 表示の工夫

そのままだと味気ないので、表示を工夫してみます。

今回は文字をmergeした場合、単語を太字にします。
具体的には、`addstr` に属性情報 `curses.A_BOLD` を追加します。

他にも、色をつけたり、点滅させたりもできます。実際の、[属性とカラー](https://docs.python.org/ja/3/howto/curses.html#attributes-and-color) の属性と実行結果は以下のようになります。

```python
stdscr.addstr('This is A_BOLD\n', curses.A_BOLD)
stdscr.addstr('This is A_BLINK\n', curses.A_BLINK)
stdscr.addstr('This is A_DIM\n', curses.A_DIM)
stdscr.addstr('This is A_STANDOUT\n', curses.A_STANDOUT)
stdscr.addstr('This is A_REVERSE\n', curses.A_REVERSE)
stdscr.addstr('This is A_UNDERLINE\n\n', curses.A_UNDERLINE)
# 背景と文字色を指定する
curses.init_pair(1, curses.COLOR_RED, curses.COLOR_WHITE)
stdscr.addstr("This is curses.init_pair(1, curses.COLOR_RED, curses.COLOR_WHITE)\n", curses.color_pair(1))
```
<img width="759" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/185967/22d6efae-66e1-2884-c205-382d8c16677a.png">

※表示がわかりやすいように、結果出力のiTermの設定を `Dark Background` にしています。


# 出力結果

以上を加味して作成した[bpe_curses.py](https://gist.github.com/shihono/f1a113ec00e076acbd448f0406976050)を実行すると、以下のように、キーを叩くたびにmergeして更新された結果が出力されます。

![bpe_sample.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/185967/366fc3d7-9e2b-90d8-07c4-98f220c0b063.gif)


文字が小さくて少しわかりにくいですが、 **太字** がmergeされたペアが含まれる単語です。最初は `e` と `r` が最頻なペアのため、`newer` と `wider` が太字になっています。(2行目)

また、10回mergeを繰り返すことで、一番左に表示されている語彙数が減っているのがわかります。(14→6)


今回インタラクティブである必要性があまりなかった気がしますが、cursesはキー入力を受け取ったりできるので、工夫次第では様々な活用できる気がします。
GUIを実装するより楽なので、ちょっとした出力を見せるのに良いかもしれません。

# 参考

- ドキュメント
   - curses https://docs.python.org/ja/3/library/curses.html
   - Python で Curses プログラミング https://docs.python.org/ja/3/howto/curses.html
- Pythonで、cursesモジュールを使う https://torina.top/detail/437/