データ構造は、カウントベースの分布モデルを構築するときの長さ5までの長さになります。

Question

テキストから分布モデル（カウントベース）を構築しています。基本的には、各ngram（単語のシーケンス）ごとに、私はカウントを格納しなければなりません。私はカウントに合理的に素早くアクセスする必要があります。 n = 5の場合、技術的に可能なすべての5グラムは（10^4）^ 5ですが、これはあまりにも高い10k語の控えめな見積もりを想定しています。しかし、これらのn-gramの多くの組み合わせはテキストには存在しないので、5d配列の構造は考慮されていません。

各単語がノードであるトライを作成しました。だから、このトライは最大深度5で、本当にワイドになるでしょう。それで私はかなりのメモリを節約できました。しかし、十分なファイルを訓練した後、私はまだメモリが使い果たされています（64GB）。公正であるために、私はここで超効率的なJavaのプラクティスを使用していません。各ノードにはcountという単語のインデックスがintとして格納されます。私は子供を保管するためのHashMapを持っています。最初はリストから始めました。私は子供を追加するたびにそれを並べ替えることを試みたが、私はそこに多くの時間を失っていたので、HashMapに移動した。リストを持っていても、さらにいくつかのファイルを読んだ後にメモリ不足になります。

私は自分の仕事を分割し、各部分をディスクに保存する必要があると思います。しかし、最終的には、私がこれらのデータ構造をマージする必要があります。だから私は前方に行く方法はディスクベースのソリューションだと思うが、どこから何か（何らかの並べ替え）で始まるnグラムにアクセスするファイルを知っている。私が見ているように、トライの問題は、私がそれをマージするところまで行くとあまり効率的ではないということです。私はマージするためにメモリに2つの部分をロードする必要があります。それは本当にうまくいかないでしょう。

どのようなアプローチをお勧めしますか？私は、言語モデル（berkeleylmが使用するもののような）のためのHashMapエンコーディングベースの構造を調べました。しかし、そのユースケースでは、ngramを再構築する必要がないので、ハッシュ値をハッシュ値として保存し、コンテキストとして保存します。後で文脈にアクセスできる必要があります。

提案がありますか？データベースを使用する上での価値はありますか？彼らは記憶がなくてもそれをすることができますか？

Answer 1

私はHashMapを使用しません。かなりメモリを消費しますが、単純なソート済み配列はより良いはずです。バイナリ検索を使用できます。

多分、バイナリプレフィックス - トライを試すこともできます。最初に、単語の文字を1つの文字列にインターリーブするなど、1つの文字列を作成します（ブランクで区切って連結することもできます）。この長いStringはバイナリトライに格納できます。例については、CritBit1Dを参照してください。

多次元ツリーを使用することもできます。多くのツリーは64ビットの数値に制限されていますが、各単語の先頭の8文字のASCII文字を64ビットの整数に冷やしてから5Dキーとして保存します。 5D配列よりもはるかに効率的です。マルチディメンションインデックスは、kd-trees、R-treesまたはquadtreesです。 5グラムカウントとフルグラム（残りの文字を含む）は、各5Dキーに関連付けることができるVALUEに別々に格納することができます。

Javaを使用している場合は、私自身のtreeを試すことができます。これは接頭辞を共有するビットごとの4分木です。これは非常にメモリ効率がよく、大規模なデータセット（1Mエントリ以上）に適しており、 'float'ではなく 'integer'でネイティブに動作します。それはまた、非常に良い最近隣の検索をしています。