1

何年にもわたって蓄積した約 600 GB の辞書があり、それらをクリーンアップして並べ替えることにしました。

まず第一に、各ファイルは平均して非常に大きく、サイズは 500MB から 9GB です。私がやりたいことの前提条件は、各辞書をソートすることです。私の最終目標は、すべての辞書ファイル内および全体で 重複する単語を完全に削除することです。

これは、私の辞書のほとんどがカテゴリ別に分類および整理されているためですが、重複が依然として存在することがよくあります。

Load file
     Read each line and put into data structure
     Sort and remove any and all duplicate
Load next file and repeat

Once all files are individually unique, compare against eachother and remove duplicates

辞書 D{1} から D{N} の場合:

1) D{1}からD{N}までを個別に並べ替えます。

2) D{i}内の各単語の一意性を確認します

3) D{i}の各単語について、D{i+1}からD{N}までのすべての単語をチェックします。最初にD{i}内で一意である場合、各単語を削除します。

  • このアルゴリズムを改善するために、一種の「ハッシュ」を使用することを検討しています。リストがソートされるため、おそらく最初の 1 つか 2 つの文字のみをチェックすることによって行われます (たとえば、a、b などで始まる単語のハッシュ開始行の位置)。

4) 保存して終了します。

前の例 (ただし、はるかに小さい):

    Dictionary 1            Dictionary 2            Dictionary 3

    ]a                      0u3TGNdB                2 KLOCK
    all                     avisskriveri            4BZ32nKEMiqEaT7z
    ast                     chorion                 4BZ5
    astn                    chowders                bebotch
    apiala                  chroma                  bebotch
    apiales                 louts                   bebotch
    avisskriveri            lowlander               chorion
    avisskriverier          namely                  PC-Based
    avisskriverierne        silking                 PC-Based
    avisskriving            underwater              PC-Based

したがって、avisskriveri、chorion、bebotch、および PC-Based は、3 つの辞書のそれぞれの内外で繰り返される単語であることがわかります。したがって、最初にD{1}に avisskriveri が表示されるので、それが表示された他のすべてのインスタンスでそれを削除します。次に、D{2}に最初にコリオンが表示され、他のすべてのインスタンスで最初に削除されます。D{3}ではbebotch と PC-Based が複製されているため、1 つのエントリを除いてすべて削除したいと思います (以前に見たことがなければ)。次に、すべてのファイルを保存して閉じます。

後の例:

     Dictionary 1           Dictionary 2            Dictionary 3

     ]a                     0u3TGNdB                2 KLOCK
     all                    chorion                 4BZ32nKEMiqEaT7z
     ast                    chowders                4BZ5
     astn                   chroma                  bebotch
     apiala                 louts                   PC-Based
     apiales                lowlander                   
     avisskriveri           namely              
     avisskriverier         silking                 
     avisskriverierne       underwater                          
     avisskriving

覚えておいてください：私は新しい辞書を作成したくありません.すべての辞書から重複を削除するだけです.

オプション:

  • 各ファイルの一意の単語の量を「ハッシュ」して、プログラムが計算時間を見積もることができるようにします。

  • 目的の最初の文字で始まる最初の単語の位置を指定する方法を指定します。検索が行に「ジャンプ」して、不必要な計算時間をスキップできるようにします。

  • 高性能並列計算のために GPU で実行します。(GPU からデータを取得するのは難しいため、これは問題です)

目標:計算時間とスペースの消費を削減して、機能が制限された標準的なマシンまたはサーバーでこの方法を手頃な価格で利用できるようにします。または、GPU クラスターでリモートで実行する方法を考案します。

tl;dr - 各ファイルのサイズが 1 ～ 9GB の数百のファイル間で一意の単語を並べ替えます。

4

4 に答える 4

1

私は次のようなものから始めます：

#include <string>
#include <set>

int main()
{
    typedef std::set<string> Words;
    Words words;
    std::string word;
    while (std::cin >> word)
        words.insert(word);  // will only work if not seen before
    for (Words::const_iterator i = words.begin(); i != words.end(); ++i)
        std::cout << *i;
}

次に、ちょうど：

cat file1 file2... | ./this_wonderful_program > greatest_dictionary.txt

重複しない単語の数がメモリに収まると仮定すると（特に64ビットで4GBを超える場合は特に、最近のPCで）、これはおそらくI / Oバウンドになるので、順序付けられていないマップに煩わされることはありません。 （二分木）マップなど。マップに挿入する前に、小文字に変換したり、偽の文字を削除したりすることをお勧めします。

編集：

一意の単語がメモリに収まらない場合、または個々の入力を並べ替えてからマージすることに頑固に決心している場合は、sort各ファイルでunixコマンドを使用sort -mして、事前に並べ替えられたファイルを効率的にマージできます。UNIX / Linuxを使用していない場合でも、sort（たとえばCygwin for Windowsから）のポートを見つけることができます。OSに同等のプログラムがあるか、sortソースコードをコンパイルしてみてください。このアプローチは、sortすべてを（おそらくメモリ内で）ソートするために1回の呼び出しを要求するというtb-の提案とは少し異なることに注意してください-それがどれほどうまくいくかはわかりませんので、試して比較するのが最善です。

于 2013-01-31T06:23:30.220 に答える
1

その300GB以上の規模では、Hadoopまたはその他のスケーラブルなストアの使用を検討することをお勧めします。そうしないと、独自のコーディングを通じてメモリの問題に対処する必要があります。他のより直接的な方法（UNIXスクリプト、小さなC / C ++プログラムなど）を試すこともできますが、データに大量の重複する単語がない限り、メモリが不足する可能性があります。

補遺

達成しようとしていることに非常に近いように見えるmemcachedに出くわしました。ただし、最も古い値を破棄しないように微調整する必要がある場合があります。今は確認する時間がありませんが、分散ハッシュテーブルで検索する必要があります。

于 2013-01-31T06:25:56.243 に答える
1

辞書がアルファベット順に 1 行ずつ、1 行に 1 語であると仮定すると (ほとんどの辞書と同様)、次のようなことができます。

Open a file stream to each file.
Open a file stream to the compiled list file.
Read 1 entry from each file and put it onto a heap, priority queue, or other sorted data structure.
while you still have entries
    find & remove the first entry, storing the word (it is not necessary to store the file)
    read in the next entry from that file, if one exists
    find & remove any duplicates of the stored entry
    read in the next entry for each of those files, if one exists
    write the stored word to your compiled list file
Close all of the streams

この効率は O(n*m*log(n)) のようなもので、スペース効率は O(n) です。ここで、n はファイル数、m はエントリの平均数です。

エントリ (文字列) をファイル ポインター/参照とペアにし、文字列の格納によって並べ替えるデータ型を作成する必要があることに注意してください。また、ポップする前に覗くことができるデータ構造も必要です。

実装について質問がある場合は、私に尋ねてください。

効率のより徹底的な分析:

スペース効率はかなり簡単です。データ構造を埋め、着るアイテムごとに 1 つ脱ぐので、O(n) のままです。

計算効率はより複雑です。各エントリを考慮するため、ループ自体は O(n*m) であり、n*m エントリがあります。それらの c パーセントが有効になりますが、それは一定であるため、気にしません。

次に、プライオリティ キューへの追加と削除は両方向で log(n) であるため、検索と削除は 2*log(n) です。

各エントリを追加および削除するため、n*m の追加および削除が得られるため、O(n*m*log(n)) になります。この場合、実際にはシータかもしれないと思いますが、まぁ。

于 2013-01-31T06:30:20.500 に答える
1

私の知る限り、巧妙な方法で悪用できるパターンはありません。したがって、生の並べ替えを行いたいと思います。

利用可能なクラスター ファームがないと仮定しましょう (その場合、他のことを行うことができます)。

次に、可能な限り最も簡単な方法であるコマンド ライン ツールから始めますsort。

ソート -u inp1 inp2 -o ソート済み

これにより、出力ファイルが重複せずに並べ替えinp1られます(u = 一意)。通常、Sort は、限られた量のメモリを処理できる、カスタマイズされたマージソート アルゴリズムを使用します。したがって、メモリの問題で実行しないでください。 少なくとも 600 GB (サイズの 2 倍) の空きディスク容量が必要です。 2 つの入力ファイルだけで、所要時間と何が起こるかをテストする必要があります。私のテストでは問題は見られませんでしたが、別のデータと afs サーバーが使用されていました (かなり遅いですが、一部の HPC ファイルシステム プロバイダーとしてはより優れたエミュレーションです)。inp2sorted

$ ll
2147483646 big1
2147483646 big2

$ time sort -u big1 big2 -o bigsorted
1009.674u 6.290s 28:01.63 60.4% 0+0k 0+0io 0pf+0w

$ ll
2147483646 big1
2147483646 big2
 117440512 bigsorted
于 2013-02-02T16:08:49.660 に答える