問題タブ [trie]

問題があります。ファイルパスプレフィックスに基づいてファイルシステムデータをスペース効率よく検索する必要があります。つまり、ソートされたテキストのプレフィックス検索。トライを使ってください、あなたが言う、そして私は同じことを考えました。問題は、他のトリックがなければ、試行はスペース効率が十分ではないということです。

私はかなりの量のデータを持っています：

• ディスク上のプレーンテキストのUnix形式のリストで約450M
• 約800万行
• gzipのデフォルトは31Mに圧縮されます
• bzip2のデフォルトは21Mに圧縮されます

記憶に残っている450M近くの場所で食べたくありません。プレフィックスの形で多くの冗長性があるので、この時点で私はおよそ1億のどこかを使用することを嬉しく思います。

このジョブにはC＃を使用していますが、トライを簡単に実装するには、ファイルの行ごとに1つのリーフノードが必要です。すべてのリーフノードがテキストの最後のチャンクへの何らかの参照（32ビット、文字列の重複を最小限に抑えるための文字列データの配列へのインデックスなど）を必要とし、CLRオブジェクトのオーバーヘッドが8バイトであると仮定します（windbg / SOSを使用して確認） 、テキストストレージがまったくない状態で、構造上のオーバーヘッドに96,000,000バイト以上を費やします。

データの統計属性のいくつかを見てみましょう。トライに詰めた場合：

• 約110万のテキストの合計ユニークな「チャンク」
• テキストファイル内のディスク上の合計約16Mの一意のチャンク
• 平均チャンク長は5.5文字、最大136
• 重複を考慮しない場合、チャンクで合計約5,200万文字
• 内部トライノードの平均は約6.5の子で、最大は44です。
• 約180万の内部ノード。

葉の作成の過剰率は約15％、過剰な内部ノードの作成は22％です-過剰な作成とは、各タイプのノードの最終的な数の割合として、最終的なトライではなく、トライの構築中に作成された葉と内部ノードを意味します。

これがSOSのヒープ分析であり、最も多くのメモリが使用されている場所を示しています。

はDictionary<string,int>文字列チャンクをインデックスにマップするために使用されておりList<string>、トライの構築後に破棄できますが、GCはそれを削除していないようです（このダンプの前にいくつかの明示的な収集が行われました）!gcroot-SOSでは示されていませんルーツはありますが、後のGCで解放されると思います。

MiniList<T>スペースの浪費を回避するためList<T>に、正確なサイズ（つまり、線形成長、O(n^2)追加パフォーマンス）を使用する代わりになります。T[]これは値型であり、InteriorNode子を追跡するために使用されます。これがパイルT[]に追加されます。System.Object[]

したがって、「興味深い」アイテム（でマークされている*）を追加すると、約270Mになります。これは、ディスク上の生のテキストよりも優れていますが、それでも目標に十分に近づいていません。.NETオブジェクトのオーバーヘッドが大きすぎると考え、値型の配列だけを使用してデータを格納する新しい「スリムな」トライを作成しました。

この構造により、データ量が139Mに減少しましたが、読み取り専用操作では依然として効率的にトラバース可能なトライです。そして、それはとても単純なので、私はそれをディスクに簡単に保存して復元し、毎回トライを再作成するコストを回避することができます。

それで、トライよりもプレフィックス検索のためのより効率的な構造のための提案はありますか？私が考慮すべき代替アプローチ？

以下を考えると...

それをどのようにこのトライに変換しますか?

C++ を学習しようとしているときに、非常に基本的なトライを表すクラスを実装しようとしました。私は次のことを思いつきました：

メソッドaddChildは、同じデータを持つ子chがベクターchildrenに存在するかどうかをチェックし、存在しない場合はそこに挿入し、存在する場合は、既存の子へのポインターを返します。

ここで、このコード スニペットを検討します。

secondchildへのポインターしかない場合、何らかの方法でfirstchildまたはtへのポインターを返すことは可能ですか?

私の作業コードのロジックは、現在のオブジェクトの親まで、(下位ノードから上位ノードへ) トライを「上」にトラバースする必要があるため、それが可能かどうかを知りたいです。現在、私は再帰関数を使用して下に移動していますが、他の方法があるかどうか疑問に思っていますか?

上記が不明確であるか、どこかで失敗した場合は申し訳ありませんが、私はかなり経験が浅く、作業コードなしで記憶から書いています。

次の操作をすばやくサポートするデータ構造を見つけようとしています。

• 文字列を追加します (存在しない場合は追加し、存在する場合は単語のカウンターをインクリメントします)
• 指定された文字列をカウントします (文字列で検索してからカウンターを読み取ります)

ハッシュテーブルとトライの間で議論しています。私の理解では、衝突を回避する限り、ハッシュ テーブルの検索と追加は高速です。事前に自分の入力がわからない場合は、試してみたほうがよいでしょうか?

（これは現時点ではかなり仮説的なものなので、提供できる詳細はあまりありません。）

各行に 1 つずつ、ランダムな (英語の) 単語のフラット ファイルがあります。各単語の出現回数をカウントする効率的なプログラムを作成する必要があります。ファイルは大きい (おそらく 1GB 程度) ですが、すべてに十分な RAM があります。それらは永続的なメディアに保存されているため、読み取り速度が遅いため、一度だけ直線的に読み取る必要があります。

私の頭の中で思いついた2つのアイデアは、単語でハッシュを使用することでした=>いいえ。発生の、またはいいえのトライ。終了ノードでのオカレンスの数。ハッシュ配列に十分な RAM がありますが、トライのルックアップは同じか高速になると考えています。

どのようなアプローチが最適でしょうか?

一意の文字列を保持するために、C++ マップに多くの文字列を格納する必要があり、文字列の重複が発生した場合は、カウンター (pair.second) をインクリメントするだけです。私は c++ マップを使用しましたが、この状況によく合います。処理が30ギガまでなくなったので、これをメモリではなくファイルに保持しようとしています。

この場合、 map よりも高速な tri にも遭遇しました。ファイルに裏打ちされたトライの実装を知っている人はいますか? 私が探しているものに似たTrie実装に出くわしましたが、バグがないようには見えません..

java.util.TreeSetを使用して高速プレフィックスルックアップを実行するためにいくつかのJavaコードを使用していますが、代わりにscalaのTreeSetを使用できますか？または別の解決策？

ファイルシステムに 1 つのディレクトリがあり、そこには多数のサブディレクトリとファイルがあるとします。このディレクトリ内のサブディレクトリとファイルの数は、数万に上ります。端末でさえ、このディレクトリの内容を表示しようとすると、かなりの遅延が発生することに慣れているでしょう。

私はかなりの数の場所でこのソリューションを見てきました: コンテンツのトップレベルのリストをトライスタイルのディレクトリ構造にソートします。たとえば、元のリストが [000000.txt ... 999999.txt] の場合、ファイル 012345.txt にアクセスするには、./0/1/2/3/4/ にアクセスします。 012345.txt .

私が見つけることができなかったのは、この種の構造を生成するための短くて甘いスクリプトです。何かが存在しますか、それとも自分で書く必要がありますか? 私はそれが次のように動作することを望みます:

休暇中、私の家族はボグルをプレイするのが大好きです。問題は、私はボグルでひどいです。それで、私はどんな優れたプログラマーでもすることをしました：私のために遊ぶためのプログラムを書きました。

アルゴリズムの中核となるのは単純な接頭辞trieであり、各ノードはdict次の文字への参照です。

これはtrie:add実装です：

そして、残りの部分と、それがどのように使用されているかの例（下部）をここで見ることができます：

http://gist.github.com/263513

さて、これはErlangでの私の最初の本格的なプログラムであり、おそらくそれには多くの問題があることを知っています…しかし、私の当面の懸念は、800メガバイトのRAMを使用することです。

だから、私は何をしているのですか-間違っていますか？そして、どうすればそれを少し間違えないようにすることができますか？

こんにちは私は英語からスペイン語の単語辞書のトライ構造を作成しようとしています。

これが私がこれまでに持っているものです：

ここからどこへ行けばいいのかわからない。どんな助けでもいただければ幸いです。ありがとう！