問題タブ [trie]

私は Haskell を学ぶほど賢くないかもしれませんが、最後のチャンスだと思います。ツリーからのエントリの削除の実装に行き詰まりました。Trie のような構造をより具体的にする ( http://en.wikipedia.org/wiki/Trie )。

そのような純粋な関数を実装する方法についてのアドバイス (解決策ではありません!) を探しています。私はあるアルゴリズムについてアイデアを持っていました。単語の各文字に等しい値を「スキップ」してツリー全体をトラバースし、次の文字が見つからない場合はエッジ条件で元のツリーを返すことにより、新しいツリーを再作成します。しかし、文字が別の単語にも属している場合、問題が発生します。

データは次のようになります。

トライ マップとは、ペイロードがハッシュ テーブルではなくトライに格納される連想配列を意味します。

ハッシュ マップ/テーブルを使用している場合、使用するキーは通常文字列です。いくつかのトライベースのマップに対するハッシュマップの利点は何ですか? ハッシュマップの方が速いと読んだことがありますが、一貫したハッシュ関数は (char) 配列の各要素をチェックして最終的なハッシュを確認し、配列を1回反復する必要があるようです。試行では、同様に配列を 1 回だけ反復処理する必要があります。

これは、小さなオブジェクトをエンコードするときに、より多くのメモリを使用するように思えます (キーで小文字のアルファ文字のみを許可する場合でも、ノードごとに 26 個のポインターであり、多くの場合、キーごとに複数のノードです)。サイズ変更について心配する必要はありません。ハッシュ マップが非常に一般的であるのに、トライ マップを見たことがないのはなぜですか?

共通のプレフィックス（ファイルシステムパスに対応しない）を持つ数百万の文字列をメモリ内のSet like構造に格納し、コレクションにクエリを実行してパスが存在するかどうかを確認する必要があります。

例えば

関係するすべての文字列に多くの共通のプレフィックスがあることを考えると、これらを可能な限り効率的に保存したいと思います（メモリ内にあります）。Trieは妥当な候補ですか？

Javaで適切なデータ構造を実装するための推奨事項を探しています。

こんにちは私は試行によって辞書を実装する必要があるプロジェクトを持っています...しかし今私は検索メソッドを実装することができません....私のコードはここにあります

このコードでは、elseステートメントにエラーがあります!!!! ルートを子の1つに置き換えたいのですが、その値はkey（temp）の最初の文字に似ていますが、「elseステートメント」ではこれを実行できません...そしてなぜ値にアクセスできないのですか？子どもたちの？？

これはインタビューで尋ねられました。

答えは、すべての有効な単語のトライを作成することで実行できると思います。その後、正しくないものとして指定された可能性のある有効なパスに基づいて提案を行うことができます。

ユーザーがapfleと入力すると、システムはapの後に有効なパスがappであることを検出し、それがAppleを満足させると言います。

これよりも良い解決策はありますか？おそらく、スペルチェッカーによって実装されたものです。

次の木を想像してみてください。

たとえば、FがAの子孫であるかどうかを照会する方法を探しています（注：FはAの直接の子孫である必要はありません）。これは、この特定の場合に当てはまります。より大きな潜在的な子孫ノードプールに対してテストする必要があるのは、限られた量の潜在的な親ノードのみです。

ノードが潜在的な親プール内のノードの子孫であるかどうかをテストする場合、すべての潜在的な親ノードに対してテストする必要があります。

これが思いついたものです：

• マルチウェイツリーをトライに変換します。つまり、上記のツリーのすべてのノードに次のプレフィックスを割り当てます。

  /li>

• 次に、可能なすべてのプレフィックスサイズのビット配列を予約し、テスト対象の親ノードを追加します。つまり、Cが潜在的な親ノードプールに追加されている場合は、次のようにします。

  /li>

• ノードが潜在的な親ノードの子孫であるかどうかをテストするときは、そのtrieプレフィックスを取得し、最初の「プレフィックス配列」（上記を参照）の最初の文字を検索し、存在する場合は、2番目の「プレフィックス」の2番目のプレフィックス文字を検索します配列」など、つまりFをテストすると次のようになります。

  そうです、FはCの子孫です。

このテストは最悪の場合のO（n）のようです。ここで、n =最大プレフィックス長=最大ツリーの深さです。したがって、最悪のケースは、ツリーを上ってノードを比較するという明白な方法とまったく同じです。ただし、テスト対象のノードがツリーの最下部近くにあり、潜在的な親ノードが最上部にある場合、これははるかに優れたパフォーマンスを発揮します。両方のアルゴリズムを組み合わせると、両方の最悪のシナリオが緩和されます。ただし、メモリのオーバーヘッドが問題になります。

それを行う別の方法はありますか？どんなポインタでも大歓迎です！

配列内の一連の単語を指定して、 Trieデータ構造を実際に作成する Perl コードを作成しました。現在、単語のトラバースと印刷に問題があります。

作成した Datastructure の Dumper 出力も貼り付けます。

トラバーサル ロジックには確かに何かが欠けているため、トラバーサル後の最終的な単語セットは正しくないようです。しかし、トライの作成は問題なく、高速に動作します。誰かがここで私を助けることができますか?

トライの最上位はハッシュです

1. 各ハッシュ項目には文字であるキーがあり、各ハッシュは配列参照を指します。

2. 配列参照には再びハッシュのリストが含まれ、各ハッシュ項目は 1 と同じです

出力に最初の単語が表示される場合。archtopriumweとして登場します。

アーク、アーチ、トップ、アトリウム、畏敬の念を得る必要があります

コード

出力：

文字をCのトライデータ構造に挿入する基本機能を実装しようとしています。何が間違っているのかを理解しようとしていますが、最後の日かそこらで困惑/立ち往生しています。

私が書いたいくつかのコードを次に示します。

私はこれを理解することはできません...

PS checkLetter は、文字がすでにトライ内にあるかどうかをチェックするブール関数です (トライ構造をトラバースすることにより、つまり、トライ = トライ->兄弟)

任意の助けをいただければ幸いです=]

乾杯！

編集: コードを変更して、insertInOrder が値を返すようにしましたが、insert は void 関数であり、void 関数のままにしなければならないため、ノードをトライのヘッドにさらに挿入する方法がわかりません (つまり、ヘッド->子、頭->子->子など)

サフィックス試行用の非常に堅実な C++ ライブラリを知っている人はいますか? ママー以外の？
理想的には、次のことを望ん
でいます。同時実行の概念。
優れたキャッシング動作。
寛容なライセンス。
任意のアルファベットのサポート。

カスタム辞書用のトライベースの単語検出アルゴリズムがあります。エントリにスペースやピリオドなどが含まれている可能性があるため、この辞書では正規表現が脆弱すぎることに注意してください。

ファイルから辞書を読み取り、トライをメモリに格納するローカルC＃アプリにアルゴリズムを実装しました（コンパクトなので、RAMサイズの問題はまったくありません）。ここで、AppHarborなどのクラウドホスト上のMVC 3アプリでこのアルゴリズムを使用したいと思います。さらに、単語の追加/編集を可能にするWebインターフェイスが必要です。

ユーザーがテキストをアップロードするたびにファイルから辞書をロードしてトライを構築することは問題にならないほど高速です（私のラップトップでは1秒未満）。ただし、管理者がWebインターフェイスを介して辞書を編集できるようにする場合は、ユーザーが分析のためにテキストをアップロードしようとしているときに辞書が更新される可能性があるため、注意が必要です。

MVC 3アプリでトライを保存、ロード、更新するための最良の戦略は何ですか？