2

一部のコモディティ ハードウェアで使用するために、 Google N-Gram データセットを取得したいと考えています。問題は、これらの小さなサーバーでは、保存する必要があるデータのサイズを処理できないことです。

このことから、WordNET や検索エンジンなどの他の大きなテキスト ベースのシステムがこの問題をどのように処理するかを考えるようになりました。データを正規化して検索可能な形式にする方法はあるのでしょうか?

N-Gram に戻ると、私の考えは、ID と共に 1-Gram のすべての単語をデータベースに保存することです。次に、その ID を使用して、ソーシャル ネットワークで友達関係を追跡するのと同じ方法で、+2 グラム チェーンに関係を作成します (行として 2 つの ID)。

TABLE Words
{
    id
    word
}

TABLE TWOGRAM
{
    first_word_id
    second_word_id
}

TABLE THREEGRAM
{
    first_word_id
    second_word_id
    third_word_id
}

TABLE FOURGRAM
{
    first_word_id
    second_word_id
    third_word_id
    forth_word_id
}

このすべてのデータをコンパクトな方法で保存するより効率的な方法はありますか?

おそらく、テキストを圧縮する代わりに、単語のペア (またはシーケンス) に対してハッシュを実行して、パスワードと同じように検索可能でありながら、より小さなストレージ サイズを実現できます。

4

2 に答える 2

1

この状況を処理する一般的な方法は、データを小さなブロック（2K行など）にチャンクし、ブロック内のデータを列ごとにグループ化してから、高速圧縮アルゴリズムを使用して変換されたブロックを圧縮することです。節約はかなり重要です。

[編集]要求に応じてもう少し詳しく説明します。ここでの目的は、小さな圧縮データブロックを処理することであるため、メモリ要件を適切なレベルに保つ必要があります。「合理的」はターゲットシステムによって異なるため、256回線、2K、または8Kになる可能性があります。

ただし、各行にはいくつかのフィールドがあります。したがって、直接圧縮しても大幅な節約にはなりません（たとえば、zipは「のみ」x5です）。幸い、これらのフィールド間の分離文字はよく知られているため（0x09）、各フィールドの開始と終了を取得できます。

アイデアは、すべての「フィールド1」、「フィールド2」、「フィールド3」というようにグループ化することです。.csvファイルから抽出されたブロックが2K行の場合、各タイプの2Kフィールドがあることがわかります。

次に、単純な高速圧縮アルゴリズムは、この変換された構造に驚異をもたらします。連続するフィールドには多くの共通点がある傾向があるため、相関は非常に強くなります。このようなデータの場合、10倍の圧縮率は驚くべきことではありません。GoogleN-Gramデータセットはさらに有利になる可能性があります。

目的は、できるだけ多くのデータをメモリに保持して検索することであるため、各ブロックを十分に小さく（約256〜8K）、非常に高速な圧縮/解凍アルゴリズムを使用することをお勧めします。このように、解凍はアルゴリズムの重要でない部分になるのに十分な速さです。たとえば、LZ4のようなものは、約1GB/sの解凍速度を提供します。

検索に関して：検索対象によって異なりますが、正確なNグラムを見つける場合は、辞書式順序で並べ替えられているため、幸運に恵まれます。

この段階では、各ブロックの最初のNグラムをテーブルに格納するだけで十分です。特定のNグラムを検索するときは、それがどのブロックにあるかを見つける必要があります。ブロックの最初のNグラムは必ず<=です。次のブロックのNグラムは必然的に>です。上記のように、ブロックの解凍は、アルゴリズムの重要でない部分である必要があります。

2K行のブロックでも、保存する「ヘッダーNグラム」がたくさんある可能性があるため、簡単なバブル検索は非常に長くなる可能性があります。ツリーまたはピボット検索をお勧めします。

ブロックがロードされた後も、適切なNグラムを見つけるためにブロックを検索する必要があります。以前と同じ戦術を使用できます（N-gramをテーブルにロードし、検索をピボットします）。

于 2011-10-10T15:15:12.997 に答える
0

3,600 億の 1 グラムを各ペアまたは 2 つ以上のグループごとに何度も格納するよりも (単語を 1 回格納してから、より小さな整数を使用して単語を表す方が良い選択のように思えます)。

（以下に見積もりをまとめました。）

ここで整数がより良い選択であるとは断言できません。必要なディスク容量、所有しているディスク容量、余裕のあるディスク容量をより適切に見積もる必要があります。

統計によると、英語の単語の平均の長さは 5.1 文字です。アプリでは、これは 5.1 バイトと同じです。2 つの単語の平均の長さは約 10.2 バイトです。2 つの整数の長さは 8 バイトです。

ファイル番号 71 (ランダムに選択) には、約 6600 万個の 2gram があります。1 エントリあたり 10.2 バイトなので、このファイルのサイズは約 673 MB です。(これは、カウントではなく、単語のみを保存することを前提としています。) 100 個の 2 グラムのファイルの場合、52 から 67 ギガが必要になるはずです (インデックスは無視します)。私たちの深い無知のために 50% を追加します。100 ギガで 2 グラムをカバーします。

カウントを単語で保存すると、このファイルは 1.6 ギガで、そのうち 100 個は約 160 ギガになるはずです。したがって、2 グラムを保存するために 100 から 160 ギガの範囲があります。

インデックスに必要なスペースの見積もりはあなたに任せます。

整数は、1 ワードあたり 2.2 バイト節約されます。ただし、2 つの整数を格納すると、実際のデータを取得するには常に2 つの結合を行う必要があります。(5 グラムに対して 5 つの整数を格納するということは、実際のデータを取得するために5 つの結合が必要になることを意味します。) 単語自体を格納する場合、実際のデータを取得するために結合は必要ありません。

カウントも格納する場合は、個々の単語を使用する代わりに外部キーを ngram に格納することでスペースを節約できます。収納できるので

ngram_id  ngram_text
--
143564    five pounds

1 つのテーブルで、

ngram_id    year    match_count  page_count  volume_count 
--
143564      1999    4            3           3
143564      2000    2            2           1
143564      2001    1            1           1
143564      2002    1            1           1
143564      2003    2            2           2
143564      2004    1            1           1
143564      2005    6            6           5
143564      2006    30           21          17
143564      2007    39           37          26
143564      2008    44           41          28

別の。

その特定の 2gram の場合、テキストは 11 バイト、整数は 4 になります。10 行のそれぞれで 7 バイト、70 バイトが節約されます。実際のデータを取得するには、 1 つの結合が必要です。このアプローチでは、インデックスと外部キーを提供するテーブルを除いて、すべての 2 グラムに対して約 130 ギガを見積もっています。

6,600 万行のファイル 100 個に基づいて、2 グラムを格納するために必要な容量を概算しました。インデックス用のスペースと一般的なストレージ オーバーヘッドを除外します (dbms によっては、かなりの量になる可能性があります)。

                           row_len  gigabytes  joins
----------------------------------------------------
words        with counts     163.2      1,077      0
two integers with counts     128.0        845    2-5

words        without counts   10.2         67      0
two integers without counts    8           53    2-5

one integer  with counts      20          132      1
one integer  without counts    4           26 (for completeness, but not really useful)

最近では、数テラバイトのドライブ アレイはそれほど高価ではありません。これでみんな稼げるの？

于 2011-10-10T18:37:01.117 に答える