string - どのような種類のテキストにも接尾辞配列を実際にどのように適用しますか?

Question

私は読んSuffix Arraysでいますが、ビルドするコードは簡単です。bananaしかし、私が見つけたすべてのリソースは、通常、概念を説明するために、通常は簡単な例のテキストを使用しています。
したがって、例のテキストは些細なものであり、接尾辞の配列は ( a、ana、anana、banana、 ) で示されていますがna、nanaこれはあらゆる種類のテキストに適用できることを理解しています。
しかし、テキストにはスペース、改行文字、句読点などが含まれているため、どのように理解できませんか。
では、これはどのような種類のテキストにも当てはまりますか?

Answer 1

より長い文字列の場合、サフィックス配列は次のようになります。

[01] banana split, yum!
[02] anana split, yum!
[03] nana split, yum!
[04] ana split, yum!
[05] na split, yum!
[06] a split, yum!
[07]  split, yum!
[08] split, yum!
[09] plit, yum!
[10] lit, yum!
[11] it, yum!
[12] t, yum!
[13] , yum!
[14]  yum!
[15] yum!
[16] um!
[17] m!
[18] !

次に、それをアルファベット順に並べ替えて、サフィックス配列の一般的な使用法である、最も長く繰り返された部分文字列を見つけることができます。

また、長いテキストで単語の繰り返しパターンを見つけるために同様のことを行ったことを覚えています。各文字を調べる代わりに、スペース文字を区切り文字として使用しました。

[01] if it is true it is true
[02] it is true it is true
[03] is true it is true
[04] true it is true
[05] it is true
[06] is true
[07] true

これは接尾辞配列ではありませんが、アルファベット順にソートすると、単語の繰り返しパターンを見つけることができます。

[01] if it is true it is true
[06] is true
[03] is true it is true
[05] it is true
[02] it is true it is true
[07] true
[04] true it is true

各行をその上の行と比較すると、文字が一致している限り、「本当です」と「それは本当です」が繰り返される単語のパターンであることがわかります。

この方法は、最長反復部分文字列問題と呼ばれる一般的な DNA 研究の問題に着想を得ています: http://en.wikipedia.org/wiki/Longest_repeated_substring_problem

もちろん、遺伝子科学以外の分野でも発生します。