問題タブ [suffix-tree]

研究プロジェクトの基本的な検索を実装しました。接尾辞木を作成して、検索をより効率的にしようとしています。UkkonenアルゴリズムのC＃実装に興味があります。そのような実装が存在する場合、私は自分自身をローリングする時間を無駄にしたくありません。

次の機能を備えた Generalized Suffix Tree (GST) の Java 実装を探しています。

たとえば 1000 個の文字列から GST を作成した後、これらの 1000 個の文字列のうちいくつの文字列に他の文字列「s」が含まれているかを調べたいと思います。

平均長が 10 の約 100,000 個の候補文字列に検索を適用する必要があるため、検索は静かに高速である必要があります。

接尾辞ツリーを構築するための Ukkonen のアルゴリズムを使用していくつかの作業を行っていますが、線形時間の複雑さについての著者の説明の一部を理解していません。

私はアルゴリズムを学び、それをコーディングしましたが、私が主な情報源として使用している論文 (以下にリンク) は、いくつかの部分で少し混乱しているため、アルゴリズムが線形である理由がよくわかりません。

何か助けはありますか？ありがとう。

Ukkonen の論文へのリンク: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

誰かが「Token Suffix Trees」のチュートリアルを教えてください。

Javaでの短くて単純な接尾辞ツリーの構築/使用アルゴリズムを探しています。私がこれまでに見つけた最高のものは、Semantic Discovery Toolkitを使用することですが、実装は数千行の長さで、いくつかのクラスにまたがっています。理想的には、実装は可能な限り短く、数百行を超えないようにします。

誰かがそのような実装を持っていますか？

遺伝子配列決定の課題の一環として、C++ でサフィックス ツリーを作成しようとしています。

chooseBranch()は、4 つの子のどちらに移動するかを選択する関数であり、このノードが既に存在するかどうかを確認しようとしています。私のノードクラスは次のとおりです。

この if ステートメントは、gdb を使用してバックトラックしたセグメンテーション違反を引き起こしています。

この形式の NULL チェックの何が問題になっていますか? ノードにデータがないかどうかを確認するにはどうすればよいですか?

与えられた単語の辞書と頭文字。単語に文字を連続して追加して、辞書内で可能な限り長い単語を見つけます。任意のインスタンスで、単語は辞書で有効な単語である必要があります。

例: a -> at -> cat -> cart -> chart ....

2 つの非常に大きな文字列があり、それらのLongest Common Substringを見つけようとしています。

1 つはサフィックス ツリーを使用する方法(複雑な実装ですが、非常に複雑であると想定されます) であり、もう 1 つは動的プログラミング方法です(どちらも上記のリンク先の Wikipedia ページで言及されています)。

動的計画法の使用

問題は、動的計画法の実行時間が非常に長いことです (複雑さはO(n*m)で、nとmは 2 つの文字列の長さです)。

私が知りたいこと (接尾辞ツリーの実装にジャンプする前に):共通部分文字列の長さだけを知りたい場合 (共通部分文字列自体ではなく)、アルゴリズムを高速化することは可能ですか?

先週、インターンシップの面接を受け、大規模なデータベースで特定の文字列を検索することについて質問されました。インタビュー中、私はそれについてまったく無知でしたが、「マルチレベルハッシュ」と答えただけで、それが私が知っている唯一のヒントであり、最高の時間効率を持っていました。少しグーグルした後、彼が期待した答えはそれだったと思いますサフィックスツリー。検索中にサフィックスツリーを構築するためのアルゴリズムを見つけ、サフィックスツリーの構築方法に関する研究論文さえありました!! では、特にインタビュー時に、文字列マッチング アルゴリズムのサフィックス ツリーを実装することは本当に可能でしょうか?

誰かがそれに光を当てることができれば素晴らしいでしょう。

前もって感謝します

過去数日間、私はこれを広範囲に調査しました。非常に多くのことを読んだため、これまで以上に混乱しています。大規模なデータセットで最も長い共通部分文字列を見つけるにはどうすればよいですか? アイデアは、このデータ セットから重複するコンテンツを削除することです (長さが異なるため、アルゴリズムを継続的に実行する必要があります)。大規模なデータ セットとは、約 100 MB のテキストを意味します。

サフィックスツリー？サフィックス配列？ラビンカープ？最善の方法は何ですか？そして、私を助けることができるライブラリはそこにありますか?

本当に良い反応を期待して、頭がとても痛いです。ありがとうございました！:-)