1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

最新の接尾辞配列構築program

Last updated at Posted at 2024-01-26

接尾辞配列を高速に構築すると言えば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系圧縮で有名な bzip2DGCA(日本産) を凌ぐ高性能圧縮噐の開発者として、どこぞの界隈ではあまりにも有名。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?