問題タブ [trie]

mmoDonKnuthの教育MMIXアーキテクチャで使用されているオブジェクトファイル形式がどのように機能するかを理解しようとしています。私はMMIXwareを購入していないので、アセンブラーとシミュレーターの読み書きのできるソースファイルから詳細のほとんどを推測する必要があります。

オブジェクト形式は、シンボルテーブルを格納するために特別な三分探索木を使用します。コードを見ると、それがどのように機能するのかよくわかりません。誰かが私にいくつかの詳細を説明してもらえますか？特にツリーがどのようにシリアル化されるかについて。

次のコマンドのみをサポートする必要がある (key,val) アイテムのディクショナリを実装するための計算の複雑さの点で、どのデータ構造が最適ですか。

1. Insert(key)- val=1 のアイテム (key,val) を追加します
2. Increment(key)- 存在する (key,val) の val をインクリメントします
3. Find(key)- (key,val) の val を返します
4. Select(part_of_key)strstr(key,part_of_key)!=NULL-同じタイプの新しいディクショナリの形式の場合、すべての項目 (key,val) のリストを返します (可能であれば新しいメモリを割り当てません)。たとえば、辞書が {(red,3), (blue,4), (green,1)} の場合、Select(re)={(red,3), (green,1)}
5. Max(i)- すべてのアイテムの中で i 番目の最大値を持つアイテムを返します。たとえば、辞書が {(red,3), (blue,4), (green,1)} の場合、Max(1)=青、Max(2)=赤、Max(3)=緑

キーは文字列で、値は正の整数です。ディクショナリ内の項目数は非常に多くなることが予想されます。

2 つの異なるデータ構造の合成に違いないと思います。しかし、それはハッシュ テーブル + 二分木またはトライ + 並べ替えられた配列、または何か他のものである必要がありますか?

膨大な単語リストから読み込んで、後ですばやく検索できるように保存しようとしています。私は最初にトライを使用することを考えましたが、私の実装が素朴であることを認めます。これは基本的に、各キーが異なる文字であるネストされたハッシュテーブルです。現在、単語をトライに挿入するのに永遠に時間がかかります (このプログラムの実行には 20 秒以上かかります)。挿入を改善するために何ができるかについて誰かアイデアがあるかどうか疑問に思っていました。これは宿題のためではありません。

私は、比較的短い時間（15〜20秒未満）でかなりの英語の語彙（〜50,000語）を処理できるVBAトライ構築アルゴリズムを実装しようとしています。私は実際にはC++プログラマーなので（そして、これが実質的なVBA作業を行うのは初めてです）、コンピューター上で約0.5秒でタスクを完了することができる概念実証プログラムを作成しました。ただし、VBAポートをテストするときが来たとき、同じことを行うのにほぼ2分かかりました。これは、私の目的では許容できないほど長い時間です。VBAコードは次のとおりです。

ノードクラスモジュール：

メインモジュール：

私の質問は、単純に、このアルゴリズムを高速化できるかということです。いくつかのソースから、VBACollectionはsほど効率的ではないことがわかったので、代わりにベースの実装Dictionaryを試みましたDictionaryが、さらに悪いメモリ使用量（コンピューターのExcelで使用される500 MB以上のRAM）で完了するのに同じ時間がかかりました）。私が言っているように、私はVBAに非常に慣れていないので、その構文と全体的な機能/制限の両方に関する知識は非常に限られています。そのため、このアルゴリズムが可能な限り効率的であるとは思わないのです。ヒント/提案をいただければ幸いです。

前もって感謝します

注意：コード「corncob_caps.txt」で参照されるレキシコンファイルは、ここから入手できます（「すべてCAPS」ファイルをダウンロードしてください）。

トライデータ構造を使用してスペルチェッカーを実装しようとしています。私は現在、次の概要を持っていますNode：

次に実行したいのは、aを検索しstring、提案されたスペルを返す関数を作成することです。（def correct(self, string)）。検索を実装するために、このトライをどのように実行しますか？rootルートノードを定義し、リスト内の各単語にを使用して、単語のリストをトライにすでに追加したと仮定しadd_itemます。

バックグラウンド：
私のCSS360グループは、オートコンプリート検索機能を含むAndroidアプリケーションを作成しようとしています。検索するデータは約7000のエントリで構成され、電話自体のSQLiteデータベースに保存されます。最も明白なアプローチは、ユーザーが入力したすべての文字に続いてデータベースの線形検索を実行し、ユーザーのクエリの潜在的なアルファベット拡張である提案のリストを返すことです。ただし、これはかなり非効率的であるように思われるため、より良い代替案を探しています。今日の私のクラスの別の1つで、私のインストラクターはトライのデータ構造について簡単に説明し、辞書全体を格納するためによく使用されると述べました。トライへのエントリは、（通常の古い配列の線形時間とは対照的に）対数時間で取得できます。ですから、これは私たちが使用するのに最適なツールのようです。残念ながら、私たちはすでにこのプロジェクトに頭を悩ませています。私たちの誰も、これを実現する方法についての手がかりを本当に持っていません。これまでにコーディングしたことのある人はすべて、プログラミングの基本を教えるための基本的なコンソールアプリケーションです。私たちは皆、YouTubeビデオを見て、データベースの内容をSQLの経験があるグループの1人とは異なるものにすることで、1週間でAndroidプラットフォームを学ぼうとしています。いくつかのポインタを真剣に使用することができます！YouTubeの動画を見て、データベースの内容をSQLの経験があるグループの1人とは異なるものにすることで、1週間以内にAndroidプラットフォームを習得しようとしています。いくつかのポインタを真剣に使用することができます！YouTubeの動画を見て、データベースの内容をSQLの経験があるグループの1人とは異なるものにすることで、1週間以内にAndroidプラットフォームを習得しようとしています。いくつかのポインタを真剣に使用することができます！

質問：

• トライを作成するときに、構造全体を事前入力することは可能ですか？IE：使用するノードごとにコード行を生成して、プログラムの起動時に構造全体がすでにメモリにあるようにしますか？ここでの私の考えは、これにより、プログラムが開始するたびにデータベースからトライ全体を再生成する必要があるというオーバーヘッドを節約できるということです。もしそうなら、これらの数千行のコードをプログラムに取り込む簡単な方法はありますか？IE：データベースファイルをEclipseにコピーアンドペーストできるJavaコマンドの巨大なテキストファイルに変換するある種のスクリプト？
• ある種の内部リストやデータ構造を使用せずにデータベースを直接検索すると、かなりのオーバーヘッドが発生しますか？データベースから名前をコピーして、プログラム内でオートコンプリート機能を検索する必要がありますか？
• これが技術的に難しすぎて、通常の線形検索に頼らなければならない場合、パフォーマンスは著しく影響を受けますか？
• 現在の計画では、ユーザーが文字を入力するたびにオートコンプリート関数を実行し、関数が戻るのを待ってから入力を続行できるようにする予定です。私たちの誰もがこれまでに書いた唯一のプログラムは、このように同期して機能します。この関数を非同期にするために知っておくべきことは何ですか？私たちの初心者の能力と、私たちがすでに満たさなければならない要件を考えると、これは私たちにとって技術的に難しすぎるでしょうか？

重複の可能性:
Java での標準の Trie ベースのマップ実装はどこにありますか?

Java で Trie を使用したいのですが、使用できる実装はありますか? （探してみましたが見つかりませんでした。）

トライの種類は

キーと値のペアとプレフィックス トライを受け取る関数を書きたいと思います。次に、キーと値のペアが含まれるシンボル テーブルを返すようにします。キーがすでに存在する場合は、古い値が新しい値に置き換えられます。

例：

また、トライを検索して、特定のプレフィックスで始まるキーを見つけられるようにしたいと考えています。例：

Delphiですぐに使用できるトライ[原文のまま]の実装を知っている人はいますか？最適化されたトライはさらに良いでしょう。

前もって感謝します！