Perlなどプログラムを使って、重複する行を抜き出すプログラムが欲しい。


やりたいことは、
OldFile.txt
NewFile.txt
の2つのテキストファイルがあります。
この2つのファイルを比較して、OldFile.txtに記載が無く、NewFile.txtのみに書かれている行をOut.txtファイルに書き出すプログラムです。下記のスクリプトで数GB程度であれば問題なく動くのですが、ファイルのサイズが、OldFile,NewFile共に、それぞれ50GB程度、10億行程度(1行は長くても300byte)となると当然ですがメモリを膨大に消費し上手く動きません。また、一時ファイルを作るタイプも作ってみたのですが、コードが悪いようで何十時間も演算していますのでお手上げです。
素早く動作する方法をすぐ使えるスクリプト(外部ソフト組込み可)と共に教えて下さい。とりあえず、すぐにテストできるよう、スクリプトの提示は必須でお願い致します。

$file1 = "OldFile.txt";
$file2 = "NewFile.txt";
open (IN, "<$file1");
for (<IN>){
$hash{$_} = 1;
}
close(IN);

open (IN2, "<$file2");
for (<IN2>){
unless($hash{$_} == 1){
open(WR,">>Out.txt");
print WR $_;
close(WR);
}
}
close(IN2);

環境
Core i5 メモリ 12GB Windows 7 x64 ActivePerl

回答の条件
  • 1人5回まで
  • 13歳以上
  • 登録:2012/04/01 00:56:25
  • 終了:2012/04/01 12:05:37

回答(1件)

id:jaga3 No.1

jaga3回答回数3ベストアンサー獲得回数02012/04/01 01:53:16

この課題、巨大なデータに対する高速な検索および比較は本質的に難しいものです。
ここでソースコードがぱっと出てくるようなものではないですよ。

そのデータ規模だとPerlに向いている処理ではありません。
そしてそれなりの容量のメモリ、高速なストレージがないと高速に処理を行えません。

単純に考えて1G行に対応する32bitハッシュキーだけでも2GBになるので、これを連想マップとして保持するとしたら10GB以上は消費するのではないでしょうか。
メモリに乗せないで処理するとなると、ディスクへ検索用インデックスを保存しておいて読み込むことになるので、SSDを使用するなどの工夫が必要でしょう。
メモリを多く使用するので、32bitOSの4GBでは不足だと思います。64bitOSで処理した方が良いでしょうね。

私ならば以下の戦略を検討します。

* split/sort/uniq/diff

Linuxのコマンドを使います。
ファイルAをsplitで100個以上に分割。各ファイルをsort。sort -m で分割したファイルをマージソートして1つのファイルに結合。uniqで重複行削除。
ファイルBに対してもsplit/sort/sort -m/uniqを実行。
生成された2つのファイルをdiffで比較。
分割数はメモリ使用量を見て調整します。ファイル内容によってはメモリを大量に消費するかもしれません。

* メモリ上でハッシュキー検索

ファイルAの各行のハッシュキーを計算してメモリへ保存。ファイルBの各行のハッシュキーを計算してメモリ上を検索。検索にヒットしなかった行をまとめてファイルAを読み込みながら再確認。メモリは少なくとも32GBは必要でしょう。
言語はC/C++で。

* KVS

KVSやNoSQLと呼ばれているデータベースを使用して、ファイルAの各行を保存。ファイルBの各行をキーとして1G回の問い合わせをする。ディスクはSSD。

* RDBMS

MySQL、PostgreSQLなどのRDBMSへファイルAの各行とファイルBの各行を別々のテーブルに保存。差分を問い合わせる。ディスクはSSD。

id:j4mika

回答いただきありがとうございます。
なかなか難しいようですね・・・

2012/04/01 12:04:29
  • id:j4mika
    ポイントについては、動作確認の取れた方のみに配分致します。
  • id:windofjuly
    うぃんど 2012/04/01 05:46:28
    perlにはテキスト比較のためのモジュールがいくつかあります(下記、一例)

    それぞれ長所も短所もあるので、
    どれが一番早いかは実データがないと判りませんが、
    とりあえず使いやすさ優先順にいくつか例をあげておきます

    (1)Text-Diff Algorithm-Diffのラッパー
    http://search.cpan.org/~ovid/Text-Diff/
    ソースコード http://cpansearch.perl.org/src/OVID/Text-Diff-1.41/lib/Text/Diff.pm

    (2)String-Diff-0.04
    http://search.cpan.org/~yappo/String-Diff-0.04/
    ソースコード http://cpansearch.perl.org/src/YAPPO/String-Diff-0.04/lib/String/Diff.pm

    (3)Algorithm-Diff
    http://search.cpan.org/~nedkonz/Algorithm-Diff-1.15/
    ソースコード http://cpansearch.perl.org/src/NEDKONZ/Algorithm-Diff-1.15/lib/Algorithm/Diff.pm

    モジュールやcpanの使い方から説明しなければならないとなると時間的に無理かもしれないし、
    1ファイルが50GBにもなるテキストファイルでやったことはないので、コメントにしておきます
  • id:j4mika
    回答いただきありがとうございます。
    モジュールについてはいくつか試したことがありますが、よく分からないエラー(多分メモリ問題)が発生してうまくいっていません。容量が大きいですので、明示的にそれが書いてあるような物でないと難しいようです。
  • id:mjy
    これは計算量が爆発するタイプの問題ではないですよね。
    単にOldFile.txtがhashに乗り切らないということですから。

    hashに乗せるのを1000万行くらいにして一度試されてはいかがですか。
    それで結果ファイルが出来たら、
    次はOldFile.txtの次の1000万行を、その結果ファイルと比較すればいいので、最初程は時間がかかりませんよね。
    結果ファイルはNewFile.txtより小さいですから。

    これを100回で10億行と比較できるので、現実的な時間で終わると思います。
    私ならpythonでset型を使い上記の手順でやります。
  • id:j4mika
    コメントありがとうございます。
    質問をキャンセルして、もう一度動作について見直して、丁度、全く同じ方法を思いつき行っているところでした。とりあえず、目処が立つ所まで来ました。良くありそうな話ですので、簡単に動く物が転がっていればと思ったのですけどね・・・

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません