0

長い文字列の一部を効率的なツリーのような構造に格納しようとしています。検索しましたが、ほとんどの実装は単語内を検索するためのものです...例を挙げて説明します。 :

/potato/carrot/tomato
/potato/carrot/pea
/potato/lettuce

私の最初の考えは、これはこのように見えるべきだということでした

potato
 - carrot
   -tomato
   -pea
 - lettuce

私が検索した限り、本当に効率的な検索ツリー (DAWG や Tries など) は単語を文字として保存するためのものであり、どのように使用すればよいかわかりません。何か案は？

よろしくお願いします！

編集:永続性に関する限り、ツリーを保存する必要はないので、プログラムが実行されている限りメモリに保持することを考えました。

Edit2:子の格納に関する限り、私はHybridDictionariesを使用することになりました。これは Dictionaries よりも効率的であり、すべてが非常に高速に動作するようになりました。どうもありがとう!

4

2 に答える 2

1

記憶に留めておくには、最近遭遇した次のパターンを使用できます。

class Vegetable : Dictionary<string, List<Vegetable>>

何をしたいか (検索、カウント、並べ替え) に応じて、そのクラス内にヘルパー メソッドを実装できます。

于 2014-03-24T09:08:58.447 に答える
0

DAWG は良い方法だと思います...このプロジェクトを見てください。これは C# にあるいくつかの最適化で行うことができますが、アルゴリズムは数年前に変更されていません。

Dawgシャープ

MakeDawg、FindNodeDepth などのメソッドが含まれています。

「このプログラムは、英小文字 26 文字の行のみで構成されるプレーン テキスト ファイルを使用します。同じ情報を格納する多くのデータ構造よりも効率的なプレフィックスとサフィックスを組み合わせたツリーを生成します。このジェネレーター コードは非常に遅いですが、うまくいきます。数分かかることもあります。最適化する必要があり、アルゴリズムを改善する必要がありますが、プログラムで頻繁に実行されるわけではないため、あまり力を入れていません。」

チュートリアル形式の別の興味深いアプローチがあります。

そして、別の興味深い内訳があります

于 2014-03-24T09:21:28.100 に答える