問題タブ [prefix-tree]

任意の長さと数のバイナリ文字列のセット（重複なし）が与えられ、他の文字列のプレフィックスである文字列があるかどうかを調べる必要があります。小さなセットと長さの短い文字列の場合は簡単です。各文字列を読み取ってバイナリ ツリーを構築するだけで、プレフィックスの一致が見つかったときに完了します。ただし、長さが長い文字列が多数ある場合、この方法は効率的ではありません。 . これに適したデータ構造とアルゴリズムは何だろうと思っているだけです。ハフマンツリー？試行 (基数ツリー)? または何か？ありがとう。

dict_free（）関数でメモリの割り当てを解除しようとしましたが、機能せず、理由もわかりません。私は何かが足りないのですか？何が悪いのか理解できません。

編集：dict_free（）でfree（）を呼び出すと、free'dポインターがNULLを指していることがわかりますが、それは起こりません。

これが私のコードです：

私は現在、読み込み時に約 30000 語のテキスト ファイルを読み込み、ゲームプレイ中にすばやく検索できるようにそれらをプレフィックス ツリーに読み込む iOS 用の単語ゲームを作成しています。これはうまく機能しますが、読み込みとツリーの構築プロセスにより、アプリの起動時間がかなり長くなります。現時点では iPhone 4 でテストしていますが、3GS の以前のモデルではかなり遅くなると思います。

アプリを開くときではなく、コンパイル時にこのツリーを作成する方法はありますか? または、あまり理想的ではありませんが、実行時に実行する代わりに、別のプログラムでデータをプリベークし、そのファイルをプロジェクトに追加することは可能でしょうか? どうすればそれを行うことができますか？

非常に一般的なプレフィックス ツリーを作成することで、新しい Scala コレクション フレームワークを学びたかったのです。キーと値がパラメーターである必要があるだけでなく、各ノードで使用されるマップのタイプもパラメーターである必要があります。だから私はこれを試しました：

しかし、これはコンパイルされません:

これは私を混乱させます。ドキュメントから、MapLike には「This」を返す空の値があることがわかります。したがって、children は M[K,PrefixMap[M,K,V]] 型であるため、children.empty もその型である必要があります。

何がうまくいかないのですか、それを修正できますか?

わかりました、これは少しトリッキーなものです。

次のような式ツリーを取得するコードがたくさんあります。

((a + b)/(c + d) + sqrt(e))

プレフィックス形式のベクトル（C ++を使用していますが、アルゴリズムが必要です）に格納されます。

+(/(+(a,b),+(c,d)),sqrt(e))//角かっこは読みやすくするためのものです。各演算子と端末は、ベクトルの要素です。

これで、ORFフォームと呼ばれる式ツリーを表す他の方法があります。

（論文の3ページ目：http：//arxiv.org/ftp/cs/papers/0102/0102027.pdf）

このフォームでは、ツリーを左から右、上から下に読んでいるかのようにツリーを表現します。

((a + b)/(c + d) + sqrt(e))今になる：

+/sqrt++eabcd

私が失敗しているのは、変換できるアルゴリズムを作成することです。

+/sqrt++eabcd// ORF into：
+(/(+(a,b),+(c,d)),sqrt(e))//プレフィックス

これまでに持っているのは、さまざまなレベルでツリーの幅を取得するためのコードだけです。

助けてくれてありがとう！これは私の頭を使っています。ああ、これはパフォーマンスが重要です:(

基本的なプレフィックス ツリーまたは「トライ」を実装しました。トライは次のようなノードで構成されています。

「Apple」、「Ark」、「Cat」という単語をトライに追加するとします。「Ap」や「Ca」などの接頭辞を検索すると、トライの「bool containsPrefix(string prefix)」メソッドが正しく true を返すようになりました。

ここで、"Cat" と "Ark" に対しては true を返しますが、"App" に対しては false を返すメソッド "bool containsWholeWord(string word)" を実装しています (上記の例)。

トライのノードがある種の「endOfWord」フラグを持つのは一般的ですか? これは、検索されている文字列が実際にトライに入力された単語全体であり、単なるプレフィックスではないかどうかを判断するのに役立ちます。

乾杯！

私はこれらのようにいくつかのシーケンスを持っています

C ++でプレフィックスツリーまたはfpツリーなどの効率的な実装がありますか?

ルートを除くプレフィックス ツリーのすべての子を削除する必要があります。私はコードを求めていません。ツリーのすべての子をトラバースして削除するメソッドが必要なだけです。

ウィキペディアの トライについて：

[HashTable との比較] 順序付けられた反復をサポートする試行

ここでまず何を言っているのかよくわかりません。ソートされた反復と同じですか？
さらに、これはこのデータ構造の固有の機能であるはずですか?
つまり、たとえば aHashSetの各ノードの子に aを使用すると、分岐する子を見つけようとするか、ノードのスペースを節約するためにアクセスTrieできます。 おそらく私は間違っているかもしれませんが、私の観点からは、反復をサポートする唯一の方法は、ノードごとにすべてのキーの配列を未使用のままにしておくことです。 このアプローチは悪くないですか？ 最後 にもう 1 つ:O(1)LinkedList
ordered


orderedこれは挿入順序に関連しています（ソートされていません）。各単語を（文字をキーとして使用して）対応するノードに挿入するので、どのようにそれを取得しますか？
誰かが私の心の中でこれらのことをクリアするのを手伝ってくれませんか?
ありがとうございました。

具体的な例を挙げます。

• あなたはアメリカのすべての名のリストを持っています。
• GUIで補完をオートコンプリートしたい。

明らかなことは、基数木を使用して、指定されたプレフィックスの名前のリストを取得することです。ただし、これは周波数情報を考慮していません。したがって、上位5つの結果を最初の字句結果にするのではなく、最も一般的な5つの名前を指定します。

例：プレフィックスの場合dan

私が見逃したトライツリーアルゴリズムはありますか？もちろん、理想的な実装（存在する場合）は、私の頭の中ではpythonです。

更新： Paddy3113が提案したものには概ね満足していますが、私が削減しているファイルの1つである2.6GBファイルをフィードすると、完全に爆発すると言います。詳細を調べると、出力からいくつかの洞察が得られます。

物事の恵みの面であと数日あるので、私はまだキラーソリューションを探しています。それは削減だけでなく、物事のルックアップ側についてもあるからです。