接尾辞配列を高速に構築すると言えばdivsufsort! 線形時間で構築すると言えばInduced Sorting! などといった内容に違いない! かつてそう言われていた時代があったかどうかは定かではないかもしれません。
そんな歴史的背景はどうでもいいかもしれないとして、最新鋭の構築技法を紹介します。

libsais

名前から分かる通りInduced Sortingの改良版です。Yuta Mori氏が手掛けたsaisに改良を施しまくった傑作です。githubにその全貌が公開されています。作者はあのGRZipIIを生み出したIlya Grebnov氏です。

libcubwt

GPUを動員して高速化を図っています。最悪計算時間はO(n log n)とのことですがlibsaisより概ね数倍高速です。詳細はgithubをご覧下さい。v1.0.0はともかくv1.5.0以降は完全にBurrows-Wheeler transform構築に特化している御様子。他の言語への移植が難しそうな気がします…。

応用

libsaisを利用したfile圧縮program。可読性皆無のごみである事を御了承下さい。ごみになり損ねた奴はココ。ちなみに本家bsc-m03v0.2.1の移植作だったりします。

See the Pen bsc-m03 v0.2.1 by xezz (@xezz) on CodePen.

Ilya Grebnovのその他代表作

BWT系圧縮で有名な bzip2 や DGCA(日本産) を凌ぐ高性能圧縮噐の開発者として、どこぞの界隈ではあまりにも有名。

GRZip(骨董品)
GRZipII(名器)
bsc(超高速)
bsc-m03(高圧縮)
esa-matchfinder(超高速にLZ系列求める)