問題タブ [suffix-tree]

圧縮されていないサフィックス ツリーを実装しました。文字列内で最も長く繰り返される部分文字列を見つける問題を解決する方法を知りたかったのです。2 つの子を持つ最も深い内部ノードを見つけなければならないことはわかっていますが、これをどのようにコーディングすればよいでしょうか。また、最も長く繰り返される部分文字列が何であるかを知るにはどうすればよいでしょうか。JAVAのコードに興味があります。PlsはJavaの実装を提供します。参考までに、私のTrieNodeは次のようになります

私は、最も長く繰り返された部分文字列を見つけなければならないphpスクリプトに取り組んでいます。このサフィックスツリーのことを見つけました。Ukkonnen のアルゴリズムを実装しようとしていますが、ツリーを拡張するタイミングと方法がわかりません。

ツリーにない新しい文字があっても大丈夫ですが、新しいノードを作成し、そのルートから egde を作成する必要があります。しかし、エッジを分割する必要があるかどうかはどうすればわかりますか?

私はそれのC++実装を見つけ（リンク）、それをphpに変換しようとしましたが、ほとんど良い結果が得られるため、タイプオが含まれていると思います。問題は、修正しない限り修正できないことですそれを完全に理解し...

Suffix-Trees の説明をたくさん読みましたが、中にはあまり深く入っていないものもあれば、2 番目のセンテンスの後で頭が痛くなるものもあります。

これが私が今持っているコードです: Suffix-tree.php (申し訳ありませんが、このエディターはそれを受け入れることができませんでした) 私はこのサイトを使用して結果を確認しました。

アドバイスをいただければ幸いです...

編集: 上記のサイトで見つかった JavaScript のものから書き直しました。ソースへのリンクは次のとおりです: Suffix-Tree v0.1

JavaScript にサフィックス ツリーの優れた実装はありますか? 文字列 (およびセパレーター) を受け取り、適切なサフィックス ツリーを作成するものはありますか?

以下の発言の理由を知っている人はいますか？または、この種の質問をするためのより良いウェブサイトはありますか? 任意のポインタをいただければ幸いです。

パターンが (長さ n) のテキストに k 回出現する場合、そのテキストのサフィックス ツリーで k 回すべてのパターンを検索すると、O(n+k) のコストがかかります。

一連の操作が与えられた場合：

a * b * a * b * a * a * b * a * b

サブストリングの再利用を可能にするために最適なサブディビジョンを取得する方法はありますか。

作る

a * b * a * b * a * a * b * a * b => c * a * c、ここでc = a * b * a * b

そしてそれを見て

a * b * a * b => d * d、ここでd = a * b

全体として、8つの初期操作をここで説明する4つに減らしますか？

（c =（d = a * b）* d）* a * c

もちろん、目標は操作の数を最小限に抑えることです

ある種の接尾辞木を検討しています。

私は特に線形時間ヒューリスティックまたはソリューションに興味があります。'*'演算は、実際には行列の乗算です。

私はそれを読みました：

txt[1..n]で部分文字列pat[1..m]を検索すると、O（m）時間で解決できます（txtの接尾辞木がO（n）時間で構築された後）。

ただし、各ポイントで、取得するブランチを選択する必要があるため、n-aryツリーの場合と同様に、各ノードで、そのノード内のすべての最大n個のポインターと比較して、取得するブランチを決定する必要があります。これは、どういうわけか、このアルゴリズムの複雑さのn要素をもたらさないでしょうか

それでは、O（m）に部分文字列が含まれているとはどういう意味ですか？

ここで何が欠けていますか？

文字列で最も長い回文を見つけようとしていました。力ずくで解決するには O(n^3) 時間かかります。サフィックスツリーを使用した線形時間アルゴリズムがあることを読みました。私は接尾辞ツリーに精通しており、それらを快適に構築できます。構築されたサフィックス ツリーを使用して最長の回文を見つけるにはどうすればよいですか。

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

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

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

私は、文字列の文字サフィックスをツリー構造のノードとして格納するサフィックス トライ (これはサフィックス ツリーとは異なります) を実装しています。このツリー構造では、'$' にヒットするか、またはあなたの検索の終わり。

問題は、このトライを作成すると、大きなテキスト ファイルを使用する場合に Java よりも多くのメモリが消費されることです。データ構造に関してメモリ使用量を削減できる場所はありますか? これは宿題であり、圧縮されたサフィックス トライ (基本的にはサフィックス ツリー) にする必要はありません。

これは私が現在持っている基本的な構造です (本当に必要な場合は、実装の詳細を提供できます)。

// SuffixTrie.java

各ノードは次のとおりです。

各ノードに保持されるデータは次のとおりです。

私が得るエラーは次のとおりです。

ただし、小さなテキスト ファイルの場合は問題なく機能し、生徒にこの課題を与えるのはこれが初めてであるため、インストラクターは接尾辞 trie を使用してこれが実行可能かどうかを知りません..

接尾辞木を作成するには、最悪の場合、文字列のすべての文字が異なる場合、複雑さは次のようになります。

これはO（n ^ 2）です。

ただし、 http：//en.wikipedia.org/wiki/Suffix_treeによると、サフィックスツリーの構築にはO（n）時間がかかります。ここで何が欠けていますか？