14

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

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

  • ディスク上のプレーンテキストの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のヒープ分析であり、最も多くのメモリが使用されている場所を示しています。

 [MT    ]--[Count]----[   Size]-[Class                                          ]
 03563150       11         1584 System.Collections.Hashtable+bucket[]
 03561630       24         4636 System.Char[]
 03563470        8         6000 System.Byte[]
 00193558      425        74788      Free
 00984ac8    14457       462624 MiniList`1+<GetEnumerator>d__0[[StringTrie+Node]]
 03562b9c        6     11573372 System.Int32[]
*009835a0  1456066     23297056 StringTrie+InteriorNode
 035576dc        1     46292000 Dictionary`2+Entry[[String],[Int32]][]
*035341d0  1456085     69730164 System.Object[]
*03560a00  1747257     80435032 System.String
*00983a54  8052746     96632952 StringTrie+LeafNode

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

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

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

class SlimTrie
{
    byte[] _stringData; // UTF8-encoded, 7-bit-encoded-length prefixed string data

    // indexed by _interiorChildIndex[n].._interiorChildIndex[n]+_interiorChildCount[n]
    // Indexes interior_node_index if negative (bitwise complement),
    // leaf_node_group if positive.
    int[] _interiorChildren;

    // The interior_node_index group - all arrays use same index.
    byte[] _interiorChildCount;
    int[] _interiorChildIndex; // indexes _interiorChildren
    int[] _interiorChunk; // indexes _stringData

    // The leaf_node_index group.
    int[] _leafNodes; // indexes _stringData

    // ...
}

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

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

4

3 に答える 3

2

チャンクは110万個しかないため、32ビットではなく24ビットを使用してチャンクにインデックスを付け、スペースを節約できます。

チャンクを圧縮することもできます。おそらくハフマン符号化は良い選択です。また、次の戦略も試してみます。エンコードするシンボルとして文字を使用する代わりに、文字遷移をエンコードする必要があります。したがって、キャラクターが出現する確率を調べる代わりに、状態が現在のキャラクターであるマルコフ連鎖の遷移の確率を調べます。

于 2009-08-31T04:53:38.357 に答える
1

あなたの問題に関連する科学論文をここで見つけることができます（著者の引用：「実験は、gzip、bzip、またはppmdiを介して文字列辞書を圧縮することによって達成可能なものに近いスペース占有内での高速クエリをサポートすることを示しています。」 -しかし残念ながら、論文は支払いのみです）。これらのアイデアを実装するのがどれほど難しいかはわかりません。この論文の著者は、さまざまな圧縮インデックスアルゴリズムの実装（「インデックスコレクション」の下）も見つけることができるWebサイトを持っています。

アプローチを続行したい場合は、Crit-bitツリーとRadixツリーに関するWebサイトを確認してください。

于 2009-08-31T12:18:35.450 に答える
0

オフザウォールのアイデア：トライの代わりにハッシュテーブル。おそらく圧縮されたハッシュと文字列データだけがメモリにあります。

それとも、1ページ読む余裕がありますか？メモリ内のハッシュとファイルの位置のみが、そのハッシュに一致する行を持つ「ページ」を取得します。おそらく、順序付けられた行の数が少ないため、衝突が発生した場合に非常にすばやく検索できます。

于 2009-08-30T23:15:25.010 に答える