更新履歴

2004/01/07 　O(N) 構築アルゴリズム三種追加（Ko &Alulu, Kim & al., Karkkainen & Sanders)

Suffix Arrayは、最近注目を集めているデータ構造です。その理由として、

(1)大規模なデータに対して、高速に検索、情報抽出を行うことができる
(2)BWTとしてデータ圧縮に用いることができる。

ことが挙げられます。(1)に関しては自然言語処理において、膨大な量のコーパスから情報（例えば、単語の出現回数など）を調べるときににSuffix Arrayを用いると非常に高速に求めることができます。 膨大な量のコーパスに基づいた自然言語処理が盛んになってきている今、Suffix Arrayが注目を集めています。

また、ゲノム情報を調べるバイオインフォマティクスにおいても、ここの配列と似ている部分（例えばCCAG）を調べるといった場合においても、Suffix Arrayを用いることで非常に高速に検索することができます。

また、(2)のBWTは、現在の非歪みデータ圧縮では最も性能が良い圧縮法の一つとして知られています。詳細については私が昔書いたもの「blocksorting」を参照してください。

ここでは、Suffix Arrayの概念、構築法についてまとめてみました。

その他の話題

Suffix Arraysに関しては現時点（2004年１月）でも研究が各方面で活発になされていていますが、
Phong VoによるLarsson Sadakane法を改良した方法、群馬大の儘田さんによる、二段階sortを
さらに拡張して、４つに分けてソートする方法（おそらくこの方法が実用上、現時点では最速？）が考えられています。
また、Suffix Arrays構築から、更新、利用などにも研究が広まってきています。

また、M.HiroiさんによるSuffix Arrayの解説、サンプルプログラムも非常に充実しています。みてみてください。こちら

もし、内容に間違い、質問、またこの部分をさらに調べて欲しい、最新情報がある、ということがあれば、

または　mail (VZV05226@nifty.com）Daisuke Okanohara　まで