Javaでの短くて単純な接尾辞ツリーの構築/使用アルゴリズムを探しています。私がこれまでに見つけた最高のものは、Semantic Discovery Toolkitを使用することですが、実装は数千行の長さで、いくつかのクラスにまたがっています。理想的には、実装は可能な限り短く、数百行を超えないようにします。
誰かがそのような実装を持っていますか？
9965 次
3 に答える
5
サフィックス ツリーの Java 実装を完了しました。私のブログ エントリでは、サフィックス ツリーの詳細、ライブラリの使用方法、および Subversion と Maven を使用したライブラリのダウンロードとビルドについて説明しています。はい、1 つのクラス ファイルの数行よりも長いですが、十分に文書化されており、実用的な目的で現実の世界で使用するために作成されています。さらに、線形時間の構築に Ukkonen アプローチを使用します。(ここに記載されている実装のほとんどは、少なくとも O(n^2) の実行時間があります。)
于 2011-12-15T20:00:08.623 に答える
1
Karkkainen と Sanders による記事「Simple Linear Work Suffix Array Construction」は、50 行の C++ で終わります。おそらく、LCP 配列を生成する何かも必要になるでしょう。「S と接尾辞配列 POS を指定して、線形時間で LCP 配列を計算する」のグーグル検索。それを見つける必要があります。
于 2010-01-11T18:57:24.077 に答える
0
私のものも使用できますが、これはウッコネンのアルゴリズムではありません。他のすべての単純なアプローチと同様に、二次時間で実行されます。単純なアルゴリズム (短いシーケンスでは問題なく動作する可能性があります) は、せいぜい半日で簡単に作成できることに同意します。
于 2011-03-07T12:50:29.017 に答える