☰

テキストファイルから重複行を削除する方法は？

tag-icon • tag-icon files text-processing large-files
テキストファイルから重複行を削除する方法は？

各行の正確なレプリカが約100個含まれる巨大な（最大2GiB）テキストファイルがあります（私の場合、ファイルはCSVに似たデータテーブルなので役に立ちません）。

私にとって必要なのは、元のシーケンス順序を維持しながら（可能な限り大幅なパフォーマンスを向上させるために犠牲にすることができます）、すべての重複エントリを削除することです。その結果、各行は一意です。 100本の同じ行がある場合（通常は重複する行はファイル全体に広がっていて近隣ではありません）、そのうちの1つだけが残ります。

私はこの機能を実装するためにScalaでプログラムを作成しました（Scalaがわからない場合はJavaの使用を検討してください）。しかし、これをより速く実行できるCで書かれたより速い基本ツールがありますか？

更新：awk '!seen[$0]++' filenameこのソリューションは、ファイルが2GiB以下に近いと正常に動作するように見えましたが、8GiBファイルをクリーンアップしようとすると、もう機能しません。 4GiB RAMを搭載したMacと4GiB RAMと6GiBスワップを搭載した64ビットWindows 7 PCでは、メモリ不足で終わりがないようです。このような経験を考えると、私は4GiB RAMを搭載したLinuxで試すことに熱心ではありませんでした。

答え1

awk#bash(Freenode)で見られる解決策:

awk '!seen[$0]++' filename

ファイルをその場で編集するには、次のコマンドを使用できます（この拡張を実装するGNU awkバージョンを使用している場合）。

awk -i inplace '!seen[$0]++' filename

答え2

実行を除いて多くのメモリを必要としない標準ユーティリティを使用する簡単な（明白ではありませんが）方法があり、ほとんどsortの実装には大容量ファイルに対する特定の最適化（良い外部ソートアルゴリズム）があります。この方法の利点は、専用ユーティリティ内のすべての行に対してのみループを実行し、解釈された言語内のすべての行に対してループを実行しないことです。

<input nl -b a -s : |           # number the lines
sort -t : -k 2 -u |             # sort and uniquify ignoring the line numbers
sort -t : -k 1n |               # sort according to the line numbers
cut -d : -f 2- >output          # remove the line numbers

すべての行が空白以外の文字で始まる場合は、一部のオプションを省略できます。

<input nl | sort -k 2 -u | sort -k 1n | cut -f 2- >output

大量の反復の場合、各行の単一のコピーのみをメモリに保存する方法は、より良いパフォーマンスを発揮します。いくつかの説明オーバーヘッドで非常にきれいなawkスクリプトがあります（すでに出版社：enzotib):

<input awk '!seen[$0]++'

それほど簡潔ではありません。!seen[$0] {print} {seen[$0] += 1}つまり、まだ表示されていない場合は、現在の行を印刷してからその行seenのカウンタをインクリメントします（初期化されていない変数または配列要素の数値はゼロです）。

長い行の場合は、各行の検閲できないチェックサム（暗号化ダイジェストなど）のみを維持してメモリを節約できます。たとえば、SHA-1では、各ラインには20バイトと継続的なオーバーヘッドのみが必要です。しかし、ダイジェスト計算はかなり遅いです。 CPUが高速で（特にダイジェストを計算するためのハードウェアアクセラレータを備えたCPU）、ファイルサイズに比べてメモリが多くなく、行が十分に長い場合にのみこのアプローチが有効です。 1行あたりのチェックサムを計算するための基本的なユーティリティはありません。 Perl / Python / Ruby / ...の解釈オーバーヘッドを取るか、専用のコンパイラを書く必要があります。

<input perl -MDigest::MD5 -ne '$seen{Digest::MD5::md5($_)}++ or print' >output

答え3

sort -u big-csv-file.csv > duplicates-removed.csv

出力ファイルがソートされます。

答え4

gawk -i inplace '!a[$0]++' SOME_FILE [SOME_OTHER_FILES...]

このコマンドは、順序を維持しながら重複した行をフィルタリングし、ファイルを適切な場所に保存します。

すべての一意の行のキャッシュを維持し、各行を一度だけ印刷してこれを行います。

正確なアルゴリズムは次のように分類できます。

  1. 現在の行を変数に保存$0
  2. 連想配列にaキーがあることを確認し$0、そうでない場合はキーを生成し、その値を次のように初期化します。0
  3. キー値を比較し、0trueの場合は現在の行を印刷します。
  4. 鍵の価値を高める1
  5. 次の行を取得して手順1に進みます。 EOFに達するまで

または疑似コードとして：

while read $line
do
    $0 := $line
    if not a.has_key($0) :
        a[$0] := 0
    if a[$0] == 0 :
        print($line)
    a[$0] := a[$0] + 1
done

注：このコマンドには2013年以上のGNU AWKバージョン4.1が必要です。

関連情報