問題タブ [suffix-array]

Python で文字列からサフィックス配列を作成する非常に簡単な方法を次に示します。

ただし、「content[a:]」はコンテンツのコピーを作成するため、コンテンツが大きくなると非常に非効率になります。だから、2つの部分文字列をコピーせずに比較する方法があるのだろうか. buffer-builtin を使用しようとしましたが、うまくいきませんでした。

接尾辞配列の C# 実装をどこで見つけることができるかについて、誰か提案はありますか? 車輪の再発明はしたくありません...

一連のサンプルテキストを指定してランダムなテキスト文字列を生成するための効率的なn次マルコフ連鎖法を作成しようとしています。私は現在、マップのいくつかのレイヤーを使用するJava実装を持っていますが、それは不格好です。接尾辞配列は私のニーズにぴったりですが、それがJavaで効率的に実装できるかどうかはわかりません。

CIでは次のようなことをするかもしれません：

Javaでは、のサブストリングを取得するexampleTextかsuffixArray、インデックスの配列に変換する必要があるため、これは厄介になります。

Javaでこれに良いアプローチをするための提案はありますか？

http://portal.acm.org/citation.cfm?id=1813708でアルゴリズムを実装しています。このアルゴリズムは、接尾辞配列を利用して最長の共通部分文字列を見つけます。アルゴリズムには、指定された文字列のセットをセンチネルと呼ばれる文字列区切り文字で連結した文字列のサフィックス配列を構築することが含まれます。たとえば、文字列 a、b、c が与えられた場合、新しい文字列 d が作成されます。これは a$1b$2c$3 で、ここで $1、$2、$3 は各文字列の末尾を示す番兵文字です。センチネル文字は一意で、a、b、c の他のすべての文字よりも辞書順で少なくなければなりません。

私の質問は、Python でのセンチネル キャラクターの表現に関するものです。a、b、および c が ASCII 文字列の場合、これらの文字列を UTF-8 に変換し、それらの範囲を 0 ～ 127 からより高い範囲にシフトして、使用可能な文字が、弦。それが合理的であると思われる場合、範囲が N-127+N (N は提供される文字列の数) になるように Python で文字を再マッピングするための最も効率的なメカニズムは何ですか?

文字列内の部分文字列を探すための接尾辞配列アプローチについて読んでいました( http://www.codeodor.com/index.cfm/2007/12/24/The-Suffix-Array/1845 )を参照してください。

ここで、SuffixArray はサフィックス配列の実装であり、find_substring は部分文字列の開始位置を検索するためのメソッドです。

私の質問は、部分文字列内の特定の数の不一致を許可しながら、この検索をどのように実装できるかということです。例えば、

不一致は、エラーしきい値と見なすことができます。この場合、「aza」に一致し、「aza」部分文字列の開始位置を返すことができるはずです。また、「abr」には 2 つの不一致があることに注意してください。したがって、最初に返却する必要があります。理想的には、アプローチはすべての可能なオカレンスを返す必要があります。

何か案は？またはそのような問題を解決するための他のアプローチ？ありがとうございました

Burrows and Wheeler の論文からブロック ソート アルゴリズムを読んでいます。これはアルゴリズムのステップです:

S=アブラカダブラとする

N 個の単語 W[0, ... , N - 1] の配列 W を初期化し、W[i] に文字 S'[i, ... , i + k - 1] が含まれるようにします。単語は、k 文字列の辞書式比較と一致します。文字を単語にパックすることには 2 つの利点があります。アラインされたメモリ アクセスを使用して、一度に 2 つのプレフィックスを k バイトずつ比較でき、多くの遅いケースを排除できます。

(注:はk文字が追加されS'たオリジナルです。kは機械語に収まる文字数です (私は 32 ビット マシンを使用しているので、)SEOFk=4

私が間違っている場合は修正してください：

次に、アルゴリズムは、配列にインデックスをS付けることにより、 (V という名前の)のサフィックス配列をソートする必要があると言います。W

にインデックスを付けてサフィックスをソートする方法が完全にはわかりませんW。例: ソートのある時点で、2 つの接尾辞 と を取得iしj、それらを比較する必要があるとします。にインデックスを付けているためW、一度に 4 文字をチェックしています。
最初の 4 文字が両方とも同じであるとします。次に、サフィックスごとに次の 4 文字をチェックする必要があり、W. これは正しいですか？この「文字を言葉に詰め込む」ことは本当にスピードアップするのでしょうか?

ブロックソートを実装しようとしています。これはBurrowsWheelerの論文からのものです。

（この手順の前に、SのV接尾辞配列を作成します）

Q4。[基数ソート]
各サフィックスの最初の2文字をソートキーとして使用して、Vの要素をソートします。これは、基数ソートを使用して効率的に実行できます。

基数ソートでサフィックスをソートしているとのことですが。
これはどのようにアレイVを更新することになっていますか？基数ソートが終了して初めて、接尾辞のソートされた位置を知ることができます。4番目のサフィックスがソート後の最初のサフィックスになるとします。したがって、V [0]=iです。この場合、（私があなたに言ったので）i = 4であることがわかります。しかし、アルゴリズムは、それらの位置を追跡していないので、どのようにしてそれを知るのでしょうか。サフィックスとそのサフィックス番号の両方を含むクラスを作成する必要がありますか？

密接に関連する 2 つのデータ構造は、接尾辞ツリーと接尾辞配列です。私が読んだことによると、サフィックス ツリーは、サフィックス配列よりも高速で、強力で、柔軟性があり、メモリ効率も優れています。ただし、この以前の質問では、サフィックス配列が実際にはより広く使用されているとの回答が最も多くありました。私はこれらの構造のいずれも使用した経験がありませんが、現在のところ、提供される機能 (高速な部分文字列チェックなど) が必要な問題については、常に接尾辞配列よりも接尾辞ツリーを好むようです。

接尾辞ツリーよりも接尾辞配列の方が適しているのはどのような場合ですか?

（ちなみに、この質問は私がリンクしたものに関連していますが、接尾辞配列と接尾辞ツリーの比較にのみ興味があり、試行を完全に除外しているため、正確な重複ではないと思います. ただし、同意しない場合は、この質問を終了するかどうかは理解できます。)

高速な接尾辞配列構築アルゴリズムを探しています。私は、漸近的な複雑さよりも、実装の容易さと生の速度に関心があります (O(n) 時間で接尾辞ツリーを使用して接尾辞配列を構築できることは知っていますが、それには多くのスペースが必要です。明らかに他のアルゴリズムには悪い最悪の場合の Big-O の複雑さですが、実際には非常に高速に実行されます)。副産物として LCP 配列を生成するアルゴリズムは気にしません。自分の目的のためにとにかく必要だからです。

さまざまなサフィックス配列構築アルゴリズムの分類法を見つけましたが、古くなっています。SA-IS、qsufsort、およびBPRについて聞いたことがありますが、それらが互いにどのように比較されるか、さらに優れたアルゴリズムがあるかどうかはよくわかりません。suffix-array フィールドが現在どれほど注目されているかを考えると、他のアルゴリズムが公開されて以来、それらに取って代わっていると思います。「分割」と呼ばれる高速なアルゴリズムを記述した論文に出くわしたことを思い出すようですが、今では一生見つけることができません。

では、現在の最先端技術はどのようなものでしょうか。理想的には、現在の最良のアルゴリズムの短いリスト (可能であればリンク付き) と、それらの相対的な長所と短所の概要を示してください。

2 つの文字列 A と B について、文字列の類似性を、両方の文字列に共通する最長のプレフィックスの長さと定義します。たとえば、文字列 "abc" と "abd" の類似度は 2 ですが、文字列 "aaa" と "aaab" の類似度は 3 です。文字列 S とその接尾辞のそれぞれの類似度の合計を計算します

これが私の解決策です...

接尾辞配列を使用してこの問題を解決するにはどうすればよいでしょうか??