java - 接尾辞配列 nlogn の作成

Question

私は接尾辞配列の作成を学んでおり、最初の文字に従ってすべての接尾辞を並べ替え、次に最初の 2 文字に従って、次に最初の 4 文字というように、考慮される文字数が 2n より小さいことを理解しています。

しかし、最初の 3 文字、次に 9 文字を選択しないのはなぜでしょうか。文字列は同じ文字列の一部であり、異なるランダム文字列ではないため、2 文字のみが考慮されるのはなぜですか?

Answer 1

接尾辞配列の構築アルゴリズムを完全に分析したわけではありませんが、私の考えを共有したいと思います。

私の謙虚な意見では、あなたの質問は次のようなものです。

• コンピューターが情報を 3 進法ではなく 2 進法でエンコードするのはなぜですか?

• 二分探索が範囲を 3 等分するのではなく 2 等分するのはなぜですか?

• 性別が 3 つではなく 2 つあるのはなぜですか。

その理由は、数 2 が特別で、最小の複数数だからです。1 と 2 の差は定性的なものですが、2 と 3 (およびその他の正の整数) の差は定量的なものであるため、劇的ではありません。

その結果、多くのアルゴリズムとデータ構造のバイナリ定式化が最も単純なものであることが判明しましたが、それらの一部は、任意のベースに対してさまざまな程度の複雑さを加えて一般化されている可能性があります。