構築法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/19 15:57 UTC 版)
接尾辞配列を構築する最も容易な方法は、効率的な比較ソートを利用することである。この場合、 O ( n log n ) {\displaystyle O(n\log n)} 回の接尾辞の比較が必要になるが、接尾辞の比較は O ( n ) {\displaystyle O(n)} の時間が必要となる。従って全体的な計算時間は O ( n 2 log n ) {\displaystyle O(n^{2}\log n)} となる。より精巧なアルゴリズムでは、部分ソートの結果の重複した比較を避けることで O ( n log n ) {\displaystyle O(n\log n)} に改善できる。接尾辞木から変換する事で O ( n ) {\displaystyle O(n)} で変換する事も出来る。 2009年に Ge Nong らが SA-IS 法を発表した。これにより計算量は O ( n ) {\displaystyle O(n)} 、メモリ使用量は max { 2 n , 4 k } {\displaystyle \max\{2n,4k\}} （kは文字の種類数）となり、100行程度のC言語のプログラムで実装できる。Yuta Mori が論文発表と同時に SA-IS 法の実装を公開しており、論文でも言及されている。
※この「構築法」の解説は、「接尾辞配列」の解説の一部です。
「構築法」を含む「接尾辞配列」の記事については、「接尾辞配列」の概要を参照ください。
ウィキペディア小見出し辞書の「構築法」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 構築法のページへのリンク
