Suffix Array向きのソートアルゴリズム

Suffix Arrayのソートアルゴリズムは以前当ブログで紹介したSAIS(参考)など、Suffix Arrayの性質を生かしたものが多い。そして一般にSuffix Arrayはバイト単位でインデックスを与えるので、これを前提としている場合が多い。大抵の場合はそれでOKなのだが、問題がある場合がある。

それは、インデックスをUTF8の文字単位で与えたい場合や、単語単位で与えたい場合。この場合、大抵のSuffix Array向けソートアルゴリズムが使えない。そこで重要になってくるのが文字列に対する高速ソートアルゴリズム。これならばインデックスが飛び飛びでも使えるので汎用性がある(Suffix Arrayに特化した手法が使えないので速度面では劣るかもしれないが。)
例えば、SUFARY(参考)で使われているmultikey-qsortという方法は古くからある方法だがシンプルかつ高速で、とても優秀な方法だと思う。
簡単に説明すると、クイックソートの各ステップで文字列比較ではなく先頭の文字比較をする。こうすると、先頭文字が同じものはソートされないので、文字列はピボットより「小さい」「大きい」「同じ」の3グループに分かれる。この「同じもの」グループは、2番目の文字を先頭文字とみなして再帰でソートする。基数ソートっぽい手法。この辺はSAISと似ている。
詳しくは以下の論文を参照。1st autherは珠玉のプログラミングのBentley先生。かっこいい。

Fast Algorithm for Sorting and Searching Strings
J. L. Bentley, R. Sedgewick

↓名著。手元においておきたい一冊。