問題タブ [suffix-array]

Rubyで接尾辞配列の実装を見つけ、少し変更しました。これが私が持っているものです：

うまく機能しますが、必要なすべてのサブストリングが見つかりません。例えば

アルゴリズムを変更して、必要なすべてのサブストリングが見つかるようにするにはどうすればよいですか？

プログラミングパールのセクション15.2から

C コードはここで見ることができます: http://www.cs.bell-labs.com/cm/cs/pearls/longdup.c

suffix-array を使用して Python で実装すると、次のようになります。

ステップが非常に遅いことがわかりましたidx.sort。Python は (上記の C コードのように) ポインターではなく値で部分文字列を渡す必要があるため、遅いと思います。

テストしたファイルはここからダウンロードできます

C コードは 0.3 秒で終了します。

しかし、Python コードの場合、私のコンピューターでは決して終了しません (10 分間待って強制終了しました)。

コードを効率的にする方法を知っている人はいますか? (例: 10 秒未満)

私は読んSuffix Arraysでいますが、ビルドするコードは簡単です。bananaしかし、私が見つけたすべてのリソースは、通常、概念を説明するために、通常は簡単な例のテキストを使用しています。
したがって、例のテキストは些細なものであり、接尾辞の配列は ( a、ana、anana、banana、 ) で示されていますがna、nanaこれはあらゆる種類のテキストに適用できることを理解しています。
しかし、テキストにはスペース、改行文字、句読点などが含まれているため、どのように理解できませんか。
では、これはどのような種類のテキストにも当てはまりますか?

次のことを理解するのに苦労しています:
String がありABRACADABRAます。これを例としてグループに分けます: Sはグループに分けられます:

S0 = <S[3i]S[3i + 1]S[3i + 2] for i = 0,1,2...> where<>は配列を表し、S[i] はS位置の文字を表しますi。

私はそれを期待してS0=<S[0]S[4]S[8]S[11]>いましたが、私が読んだ本の「解決策」によると、S0=[ABR][ACA][DAB][RA]それは本質的にそうではありませんS[0]S[3]S[6]S[9]。
では、式の何を間違って読んでいるのS0 = <S[3i]S[3i + 1]S[3i + 2] for i = 0,1,2...>でしょうか?

重要な場合は、サフィックス配列で読んだ章からのものです。数式だけで困っています

私はこの質問の原因である問題の直接的な解決策を望んでいませんが、それはこの1つのリンクです：

したがって、文字列を取り込んで、内部で並べ替えられたセットとして実装されている接尾辞配列に追加します。次に取得するのは、指定された2つの文字列の辞書式順序のリストです。

最小の部分文字列の検索をk-th効率的にするために、このソートされたセットを前処理して、接尾辞とその前身の間にある最長の共通プレフィックスに関する情報を追加し、累積部分文字列の数を把握します。kしたがって、最後の項目の累積部分文字列数よりも大きい場合、それは無効なクエリであることがわかります。

これは、問題定義で指定された制約の小さな入力とランダムな大きな入力（長さ2000の最大50文字列）で非常にうまく機能します。7つのケースのうち4つを渡すことができ、かなり驚いていました。それらすべてを取得します。

それで私はボトルネックを探しに行きました、そしてそれは私を襲いました。これらのような入力の数が多い場合

k番目に小さい部分文字列のクエリは期待どおりに高速ですが、並べ替えられたセットを前処理する方法ではありません...セットの要素間の最長の共通プレフィックスを計算する方法は効率的ではなく、線形O（m）のようになります。これ、私はそれが十分に良いことを期待して最も素朴なことをしました：

接尾辞とその前身は関係がない（つまり、異なる入力文字列からのものである）可能性があるため、このようになります。そのため、力ずくで仕方がないと思いました。

これがその時の質問であり、私が問題を減らすことになった場所です。上記の方法（複数の文字列で構成されている）のように、辞書式順序で並べ替えられた接尾辞のリストを指定します。

最長の共通プレフィックス配列を計算する効率的な方法は何ですか？。

その場合、サブ質問は、私のアプローチでは完全にマークから外れているのでしょうか？その場合は、さらに調査の手段を提案してください。

脚注、私は実装されたアルゴリズムを見せられたくありません、そして私はそう読むように言われることを気にしません、そしてそれでこれらの挑戦を試みている間私がとにかくそれがすることである主題に関する本またはリソース。

受け入れられた答えは、正しい道に私を導くもの、またはそれが失敗した場合になります。広い意味でこれらのタイプの問題を解決する方法を私に教えてくれる何か、本か何か

2 つの文字列の最長の共通部分文字列を見つけたい場合、時間/空間の複雑さの点でどのアプローチがより効率的でしょうか: DP の接尾辞配列を使用しますか?

DP は、O(m*n) 時間の複雑さで O(m*n) スペースを発生させます。サフィックス配列アプローチの時間の複雑さはどうなりますか?

1) 接尾辞 O(m) + O(n) を計算する 2) それらを並べ替える O(m+n log2(m+n)) 3) m+n-1 文字列の最も長い共通接頭辞を見つける? [#of comparisons の計算方法がわからない]

接尾辞配列を使用すると、部分文字列を使用してさらに多くのことを実行できます (部分文字列の検索など)。ただし、この場合、残りの機能は必要ないため、DP はより簡単でクリーンなアプローチと見なされますか? 2 つの文字列を比較する場合に使用する必要がありますか?

また、文字列が 2 つ以上ある場合はどうなるでしょうか。

入力: 2 つの文字列 A と B。

出力: 繰り返され、重複しない部分文字列のセット

繰り返されるすべての文字列を見つける必要があり、それぞれが両方の (!) 文字列に少なくとも 1 回出現する必要があります。たとえば、

A = "xyabcxeeeyabczeee" および B = "yxabcxabee".

この場合、有効な出力は {"abcx","ab","ee"} になりますが、文字列 A でのみ発生するため、"eee" ではありません。

この問題は、「超極大反復」の問題と非常に関連していると思います。定義は次のとおりです。

最大反復ペア : S 内の同一のサブストリング alpha と beta のペアで、alpha と beta をいずれかの方向に拡張すると 2 つの文字列の等価性が失われるようなものです。トリプレット (位置 1、位置 2、長さ) として表されます。

最大繰り返し : 「S の最大ペアで発生する S の部分文字列」。例: S の abc = xabcyiiizabcqabcyrxar。注: 多数の最大反復ペアが存在する可能性がありますが、最大反復の限られた数しか存在できません。

超極大反復 「他の極大反復の部分文字列として決して発生しない極大反復」 例: abcy in S = xabcyiiizabcqabcyrxar.

すべての超極大反復を見つけるためのアルゴリズムは、「文字列、ツリー、およびシーケンスのアルゴリズム」で説明されていますが、接尾辞ツリーについてのみです。

1.) DFS を使用してすべての左多様なノードを見つける

S の各位置 i に対して、S(i-1) は左文字 i と呼ばれます。T(S) の葉の左文字は、その葉が表すサフィックス位置の左文字です。T(S) の内部ノード v は、v のサブツリー内の少なくとも 2 つの葉が異なる左文字を持つ場合、左多様化と呼ばれます。

2.) これらのノードに定理 7.12.4 を適用する:

左多様な内部ノード v は、v のすべての子が葉であり、それぞれが別個の左文字を持っている場合に限り、超最大反復 a を表します

文字列 A と B の両方を連結する必要があり、ステップ 2 で v の葉をチェックするときに、文字列 A と B から少なくとも 1 つの別個の左側の文字が必要であるという追加の制約も課す必要があります。これは、それらの位置を A の長さと比較します。位置 (左の文字) > 長さ (A) の場合、左の文字は A にあり、そうでない場合は B にあります。

サフィックス + lcp 配列でこの問題を解決するのを手伝ってくれませんか?

接尾辞配列についてhttp://en.wikipedia.org/wiki/Suffix_arrayをチェックアウトしました。
O(n long) のスペースが必要で、アルファベットのサイズはシグマです。必要なスペースは O(ブログ シグマ) ビットになりますか?

両方のアイデアが得られない..

接尾辞配列について私が知っていることは次のとおりです。
サフィックス配列は、整数 n の整数配列です。では、O(n)*8 バイトかかるのでしょうか。1 つの整数として 8 バイトが必要です。そして、配列自体には O(n) バイトが必要ですか? n 個の文字があるとします。

これは Suffix Arrayの実装です。ウィキペディアの記事の構成における私の質問は、最悪の場合 o(n) として与えられます

だから私の構築では：

1. stl sort を使用して文字列のすべての接尾辞をソートしています。最悪の場合、これは少なくとも O(nlogn) になる可能性があります。したがって、ここでは O(n) 構造に違反しています。
2. 2 つ目は、O(n) が与えられた最長共通プレフィックス配列の構築です。しかし、O(n^2) での実装だと思います。

したがって、最初のもの、つまりソート用

• カウント ソートを使用すると、O(n) に減少する可能性があります。カウント ソートを使用すると、それは正しいですか?私の理解は正しいですか?私の理解が間違っている場合は教えてください

• そして、O(n) 時間で LCP を見つける方法はありますか?