SuffixArray
Less than 1 minute
SuffixArray
Enhanced Suffix Array
Sentence Piece読んでいるとなんかSAの他にLとかRが出てきて何これ？ってなるので調べたら、どうもこれはEnhanced Suffix Arrayというものらしい。
元論文はこれか。
Replacing suffix trees with enhanced suffix arrays - ScienceDirect
アイデアとしては、Suffix Arrayに追加のテーブルを幾つか持つ事で、Suffix Treeと同じアルゴリズム的性能を実現する、というもの。 Suffix Treeの効率的な保持方法と解釈する事が出来る。
追加のテーブルとしてはlcptableが基本。＞LCP array - Wikipedia
Suffix Tree
PngNote1
Suffix Array
PngNote2
Repeat分析
MUMなど。
lcpインターバルツリー
アルゴリズム4.1、インターバルのレポート
より大きなlcpがでてくる都度スタックにpushしていき、より小さいlcpに出会ったらその一つ手前までをスタックトップのインターバルとして確定させていく。
Fig. 2に従いインターバルツリーを上から出力していこうと思うとこんなアルゴリズムになると思う。
アルゴリズム4.4 ボトムアップトラバース
lcpテーブルを順番に見ていってスタックを使うだけで、ツリーのトラバースをしたのと同じ結果が得られる。 インターバルが確定した時にはその子どものリストを持つ形の処理は全てこれで行える。