接尾辞配列についてhttp://en.wikipedia.org/wiki/Suffix_arrayをチェックアウトしました。
O(n long) のスペースが必要で、アルファベットのサイズはシグマです。必要なスペースは O(ブログ シグマ) ビットになりますか?
両方のアイデアが得られない..
接尾辞配列について私が知っていることは次のとおりです。
サフィックス配列は、整数 n の整数配列です。では、O(n)*8 バイトかかるのでしょうか。1 つの整数として 8 バイトが必要です。そして、配列自体には O(n) バイトが必要ですか? n 個の文字があるとします。
実際、圧縮技術が使用されていないと仮定すると、接尾辞配列は整数の配列です。ただし、整数は正確に 8 バイトを必要としません。
整数を格納するには何ビットが必要ですか? 答えは、整数の範囲によって異なります。範囲が [0,2) の場合、つまり、表現したい数値が 0 と 1 だけである場合、その整数を格納するには 1 ビットが必要です。
範囲が [0,4) の場合、つまり 0、1、2、および 3 を表したい場合、2 つのビットが必要です。00、01、10、および 11 は、表すために使用できる 2 つのビットの 4 つの可能な組み合わせです。 4 つの異なる数字。
範囲が最大 8 つの数値の場合は 3 ビットが必要で、最大 16 の場合は 4 ビットが必要です。一般的に言えば、R の異なる数値の範囲の場合、ceil(log 2 (R)) ビットが必要です。
サフィックス配列には何ビット必要ですか? テキストの長さは N 文字と仮定します。この場合、接尾辞配列の長さも N であり、その整数のそれぞれはテキスト位置を参照します。つまり、各整数の範囲は [0,N) です。したがって、各整数を格納するには ceil(log 2 (N)) ビットが必要です。合計で N 個の整数があるため、必要な合計スペースは N ceil(log 2 (N)) ビットです (テキスト自体に使用されるスペースは含まれません)。 ）。
(しかし、サフィックス配列に関する最近の研究の多くは、それらの圧縮に関するものであることに注意してください。つまり、O(N) ビットのみを使用する方法 (これは簡潔な表現と呼ばれます)、またはさらに少ない、つまり o(N) ビット (真の圧縮) を使用する方法を見つけることです。上記の単純な計算は、圧縮技術がまったく使用されていない標準的なケースにのみ適用されます。)
(また、実際には、多くの実装では単にunsigned intor またはこのようなものを使用して整数を表し、N*sizeof(int)*CHAR_BITサイズ要件をビット単位で取得することにも注意してください。)