10億年ぶりに日記ではない記事を書きます（しかしタイトルの575(77)性は維持する）。
string attractor を表示するツールを作りました。
string attractor とは以下の論文で提案された概念です。
[1710.10964] At the Roots of Dictionary Compression: String Attractors
string attractors は様々な圧縮データ構造（LZ77、文法圧縮、BWTなど）と相互に変換できるという性質があります。
なので、string attractors を効率的に扱うデータ構造を作ると、string attractors と相互変換できる他のデータ構造もその恩恵を受けられるわけです。
以下の論文は、そのようなデータ構造を提案しています。
[1803.09520] Universal Compressed Text Indexing
具体的には string attractors は文字列中の位置の集合です。
どのような位置かというと、その文字列の任意の部分文字列をとったときに、その部分文字列か、その部分文字列と字面が一致する部分文字列のどれかは必ず string attractor が指す位置が含まれている、というものです。
と書いてもイメージしにくいと思います。私はイメージできませんでした。なので、それを表示するツールを書いたという次第です。
このツールを使うと、 abracadabra に対しては以下の [] のついた位置が string attractor になります。
[a][b][r][a][c][a][d]abra
例えば、部分文字列として末尾4文字 abra をとったとします。
[a][b][r][a][c][a][d] (abra)
この部分文字列には string attarctor は含まれませんが、字面の同じ先頭4文字はすべて string attractor です。
([a][b][r][a]) [c][a][d]abra
string attractors は文字列に対して一意に定まるものではなく、複数ありえます。どの圧縮データ構造から string attractors を作ったかによっていろいろ違いそう（未確認）。
今回の実装では RePair（文法圧縮のひとつ）から string attractors を作っていますが、必ずしもこれが最強の string attractors だ！というわけではありません。
というかこのツールでいろいろ見ていると、この string attractor 無駄なのでは、みたいなのがちらほら。
string attractor ってどんな感じなの、という感覚がまだつかめていないので、しばらくこのツールで遊んでみる予定です。
なお、このツールはあまり効率のよい実装にはなっていません。
Rust の練習も兼ねて書いていたので異様に実装に時間がかかってしまい、効率にまで手が回らなかったのです（Rust 力のなさ）。
あくまで遊び用ということで。
