問題タブ [suffix-array]

このリンクで見つかったサフィックス配列の特定の O(NlogN) 実装を調べています: https://sites.google.com/site/indy256/algo/suffix_array
コアコンセプトは理解できますが、実装は理解できます全体として問題です。

cnt[] 配列の使用とそれが便利な場所について疑問に思っています。どんなポインタも役に立ちます。

ありがとう。

Rubyの文字列に似たプレフィックスの始まりの数を数えようとしています。例えば; 入力 "ababaa" は 11 を出力する必要があります。

以下のコードまでは、ネストされたループを使用して上記のそれぞれを配列として処理していますが、Ruby は現在、最初の配列オブジェクト「ababaa」のカウントのみを出力しているように見えます。

解決しました、ありがとう:)

私は遠くまで調べましたが、まだ問題を解決できません。「ary」配列の最初の反復後に (最終的な、ネストされた) 配列が壊れて、その出力を返すだけのようです。

Java 7より前のバージョンでは、次のことを簡単に実行できました。

ただし、Java 7 では、substring メソッドは新しい文字列を返します。したがって、消費されるスペースO(n^2)はn、文字列の長さです。

Java 7以降のバージョンで同じことを行うための迅速かつ簡単な方法はありますか?

私はスティーブン・ハリムとフェリックス・ハリムによる本「競争力のあるプログラミング3」を読んでいます

Strings の章を読んでいます。接尾辞配列の構築アルゴリズムを理解しようとしています。基数ソートの部分がわかりません。（ただし、基数ソートとカウントソートの仕組みは理解しています）

ここに本からのコードがあります

誰か、countingSort() 関数のこれらの行で何が起こっているのか説明してもらえますか?

貴重な時間をありがとうございました。

最長の繰り返し部分文字列を返すプログラムを作成しようとしています。私はほとんど解決策を手に入れましたが、何らかの理由で、彼が LRS を見つけるのに忙しいときに、私の strcmp がエラーを出します。エラーが発生する理由と、これを解決する方法を誰かに説明してもらえますか?

コード：

私が書いている圧縮テストベッドの BWT ステージ (通常の文字列の並べ替えを使用) の実装に成功しました。BWT を適用してから逆 BWT 変換を適用すると、出力が入力と一致します。ここで、サフィックス配列を使用して BW インデックス テーブルの作成を高速化したいと考えました。接尾辞配列作成用の 2 つの比較的単純でおそらく高速な O(n) アルゴリズム、DC3とSA-ISを見つけました。どちらも C++/C ソース コードに付属しています。ソースを使用してみました (すぐに使える SA-IS ソースのコンパイルもここにあります) が、適切なサフィックス配列/BWT インデックス テーブルを適切に取得できませんでした。これが私がやったことです：

1. T=入力データ、SA=出力サフィックス配列、n=Tのサイズ、K=アルファベットサイズ、BWT=BWTインデックステーブル

2. 私は 8 ビット バイトで作業していますが、どちらのアルゴリズムもゼロ バイトの形式の一意のセンチネル/EOF マーカーを必要とします (DC3 には 3、SA-IS には 1 が必要です)。したがって、すべての入力データを 32 ビット整数に変換し、すべてのシンボルを 1 ずつ並べ、センチネルの 0 バイトを追加します。Tです。

3. 整数出力配列 SA (DC3 の場合はサイズ n、KA-IS の場合は n+1) を作成し、アルゴリズムを適用します。ソート BWT 変換と同様の結果が得られますが、一部の値は奇数です (UPDATE 1 を参照)。また、両方のアルゴリズムの結果はわずかに異なります。SA-IS アルゴリズムは先頭に過剰なインデックス値を生成するため、すべての結果を 1 つのインデックス分左にコピーする必要があります (SA[i]=SA[i+1])。

4. 接尾辞配列を適切な BWT インデックスに変換するには、接尾辞配列の値から 1 を減算し、モジュロを実行して、BWT インデックスを取得する必要があります (これに従って): BWT[i]=(SA[i]-1)%n .

これは、SA アルゴリズムをフィードして BWT に変換するための私のコードです。多かれ少なかれ、論文から SA 構築コードを差し込むだけでよいはずです。

私は何を間違っていますか？

更新 1
「ヤバダバド」/「これはテストです」のような短い量のテスト テキスト データにアルゴリズムを適用する場合。/ "abaaba" または大きなテキスト ファイル (カンタベリー コーパスのalice29.txt ) で問題なく動作します。実際には toBWT() 関数は必要ありません。
完全な 8 ビット バイト アルファベット (実行可能ファイルなど) を含むファイルのバイナリ データにアルゴリズムを適用すると、正しく動作しないようです。アルゴリズムの結果を通常の BWT インデックスの結果と比較すると、先頭に誤ったインデックス (私の場合は 4) があることに気付きました。インデックスの数 (ちなみに?) は、アルゴリズムの再帰の深さに対応します。インデックスは、元のソース データで最後に 0 が発生した場所を指しています (T を構築するときにそれらを 1 に変換する前)...

UPDATE 2
通常の BWT 配列とサフィックス配列をバイナリ比較すると、さらに異なる値があります。公平な並べ替えは必ずしも標準的な並べ替えと同じである必要はないため、これは予想されるかもしれませんが、配列によって変換された結果のデータは同じである必要があります。そうではない。

UPDATE 3
両方のアルゴリズムが「失敗」するまで、単純な入力文字列を変更しようとしました。「これはテストです」という文字列の 2 バイトを変更した後。255 または 0 (746869732069732061 20 74657374 2E h から 746869732069732061 FF 74657374 FF h まで、最後のバイトを変更する必要があります!) インデックスと変換された文字列はもはや正しくありません。また、文字列の最後の文字を文字列に既に出現している文字に変更するだけでも十分なようです。たとえば、「これはテストです」7468697320697320612074657374 73 h 次に、変換された文字列の 2 つのインデックスと 2 つの文字が交換されます (通常の並べ替え BWT と SA を使用する BWT を比較)。

データを 32 ビットに変換するプロセス全体が少し厄介だと思います。誰かが 256 文字のアルファベットの文字列から直接サフィックス配列を生成するためのより良い解決策 (紙、さらにはソース コード) を持っていれば、私は幸せです。