この記事は空いていたデータ構造とアルゴリズム Advent Calendar 2020の4日目の記事として執筆いたしました。
テキストデータ圧縮の一種である文法圧縮の実行フローをGoogleのスプレッドシート上で可視化するツール（https://docs.google.com/spreadsheets/d/1gcr5qd2ceu0S38p3n7sdK9GHqt5Uur6R52Qil8A7278/edit#gid=0 ）を作りましたので紹介させていただきます。サポートしている文法圧縮はRePairとRLESPです。似たようなツールとしてはデータ構造を可視化するhttps://github.com/kg86/visds などがあります。
使い方
- こちらのスプレッドシートにアクセスして、自分のGoogle driveにコピーしてください。
- コピーしたスプレッドシートにアクセスして、アドオン>VisGC>VisGCをクリックしてださい。
- クリックすると下図のようなポップアップウィンドウが表示されます。
- 入力文字列（input string）を入力し、データ圧縮方式(compression type) 選び、表示を開始したいスプレッドシート上の行を入力してください。RLESPに関してはalphabet reductionの回数（詳しくはこちら）も指定可能になっています。
- startボタンをクリックすると、可視化されます。
実行例の説明
-
RePairの例です。S_0が入力文字列で、S_1はS_0に最頻出するバイグラムであるabをX_{1}に置き換えた文字列、S_2はS_1に最頻出するバイグラムX_1X_1をX_2に置き換えています。
-
RLESPの例です。アルゴリズムの詳細に関してはこちらをお読みください。S_0が入力文字列、RLE(S_0)はS_0を連長圧縮した文字列、L_0[0]はRLE(S_0)の数値表現、L_0[i] (1 <= i <= 3)はL_0[i - 1]からalphabet reductionによって計算される数列です。S_1はL_0[3]の数列に基づいてS_0のバイグラムもしくはトリグラムをX_iで置き換えた文字列です。RLE(S_1)以降も同様の流れで表示されています。
Texのtabularへの変換
スプレッドシート上でドルマークが埋め込まれていたからお気づきかもしれませんが、Texのtabularへの変換機能もあります。
- 変換したいテーブルを選択。
- アドオン>VisGC>TblToTexをクリック
3. ポップアップウィンドウに変換結果が表示されます。コピーテキストでクリップボードにコピー可能です。
- 以下がTexでコンパイルし、PDF化した結果です。
- スプレッドシート上で文字の色を変更してから、Texに変換するとTexのソースも文字色を反映してくれます。
おわりに
文字はバイト単位で読み込んでいますので、マルチバイト文字を使用している日本語などはうまく表示することできないとおもいます。また、入力文字列としてあまり長い文字列を入力されることを想定していないため、長すぎる文字列を入力するとバグってしまうこともあるとおもいます。Texの変換においては、文字色のみで線の有無やmultirowなどには対応できていません。ソースも見れるようになっていますが、TypeScriptで書いたものが自動的にGoogleAppsScriptが解釈可能なJavaScriptに変換されていますので、読みにくいと思います。こちらにアップロードしておきました。色々問題が山積みではありますが、文法圧縮やデータ圧縮を勉強している方、これから勉強したい方、論文執筆に使いたい方などの手助けになることを願っています。