Bagaimana menemukan garis duplikat di banyak file besar?

9

Saya punya ~ 30k file. Setiap file berisi ~ 100 ribu baris. Garis tidak mengandung spasi. Baris-baris di dalam file individual diurutkan dan digandakan gratis.

Tujuan saya: Saya ingin mencari semua semua duplikat garis di dua atau lebih file dan juga nama-nama file yang berisi entri digandakan.

Solusi sederhana adalah ini:

cat *.words | sort | uniq -c | grep -v -F '1 '

Dan kemudian saya akan lari:

grep 'duplicated entry' *.words

Apakah Anda melihat cara yang lebih efisien?

Lars Schneider
sumber

Jawaban:

13

Karena semua file input sudah diurutkan, kami dapat melewati langkah penyortiran yang sebenarnya dan hanya digunakan sort -muntuk menggabungkan file-file tersebut.

Pada beberapa sistem Unix (setahu saya hanya Linux), mungkin cukup untuk dilakukan

sort -m *.words | uniq -d >dupes.txt

untuk mendapatkan garis duplikat yang ditulis ke file dupes.txt.

Untuk menemukan file apa yang berasal dari baris ini, Anda dapat melakukannya

grep -Fx -f dupes.txt *.words

Ini akan menginstruksikan grepuntuk memperlakukan garis dalam dupes.txt( -f dupes.txt) sebagai pola string tetap ( -F). grepjuga akan mengharuskan seluruh baris cocok dengan sempurna dari awal hingga selesai ( -x). Ini akan mencetak nama file dan baris ke terminal.

Non-Linux Unices (atau bahkan lebih banyak file)

Pada beberapa sistem Unix, 30000 nama file akan diperluas ke string yang terlalu panjang untuk dilewatkan ke satu utilitas (artinya sort -m *.wordsakan gagal Argument list too long, yang terjadi pada sistem OpenBSD saya). Bahkan Linux akan mengeluh tentang ini jika jumlah file jauh lebih besar.

Menemukan korban penipuan

Ini berarti bahwa dalam kasus umum (ini juga akan bekerja dengan banyak lebih dari hanya 30.000 file), seseorang harus "chunk" penyortiran:

rm -f tmpfile
find . -type f -name '*.words' -print0 |
xargs -0 sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh 

Atau, buat tmpfiletanpa xargs:

rm -f tmpfile
find . -type f -name '*.words' -exec sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh {} +

Ini akan menemukan semua file di direktori saat ini (atau di bawah) yang namanya cocok *.words. Untuk sepotong nama-nama ini berukuran tepat, ukuran yang ditentukan oleh xargs/ find, itu menggabungkan mereka bersama-sama ke dalam tmpfilefile yang diurutkan . Jika tmpfilesudah ada (untuk semua kecuali chunk pertama), file ini juga digabungkan dengan file lain di chunk saat ini. Bergantung pada panjang nama file Anda, dan panjang maksimum yang diperbolehkan dari sebuah baris perintah, ini mungkin memerlukan lebih dari 10 kali jalan skrip internal ( find/ xargsakan melakukannya secara otomatis).

shSkrip "internal" ,

if [ -f tmpfile ]; then
    sort -o tmpfile -m tmpfile "$@"
else
    sort -o tmpfile -m "$@"
fi

gunakan sort -o tmpfileuntuk menghasilkan tmpfile(ini tidak akan menimpa tmpfilebahkan jika ini juga merupakan input untuk sort) dan -muntuk melakukan penggabungan. Di kedua cabang, "$@"akan diperluas ke daftar nama file yang dikutip secara individual yang diteruskan ke skrip dari findatau xargs.

Kemudian, jalankan uniq -dpada tmpfileuntuk mendapatkan semua baris yang diduplikasi:

uniq -d tmpfile >dupes.txt

Jika Anda menyukai prinsip "KERING" ("Don't Repeat Yourself"), Anda dapat menulis skrip internal sebagai

if [ -f tmpfile ]; then
    t=tmpfile
else
    t=/dev/null
fi

sort -o tmpfile -m "$t" "$@"

atau

t=tmpfile
[ ! -f "$t" ] && t=/dev/null
sort -o tmpfile -m "$t" "$@"

Dari mana mereka berasal?

Untuk alasan yang sama seperti di atas, kami tidak dapat menggunakan grep -Fx -f dupes.txt *.wordsuntuk menemukan dari mana duplikasi ini berasal, jadi alih-alih kami gunakan findlagi:

find . -type f -name '*.words' \
    -exec grep -Fx -f dupes.txt {} +

Karena tidak ada pemrosesan "rumit" yang harus dilakukan, kami dapat meminta greplangsung dari -exec. The -execpilihan mengambil perintah utilitas dan akan menempatkan nama-nama yang ditemukan dalam {}. Dengan +di bagian akhir, findakan menempatkan argumen {}sebanyak menggantikan shell saat ini mendukung dalam setiap doa utilitas.

Agar benar - benar benar, orang mungkin ingin menggunakan keduanya

find . -type f -name '*.words' \
    -exec grep -H -Fx -f dupes.txt {} +

atau

find . -type f -name '*.words' \
    -exec grep -Fx -f dupes.txt /dev/null {} +

untuk memastikan bahwa nama file selalu termasuk dalam keluaran dari grep.

Variasi pertama digunakan grep -Huntuk selalu menampilkan nama file yang cocok. Variasi terakhir menggunakan fakta yang grepakan menyertakan nama file yang cocok jika lebih dari satu file diberikan pada baris perintah.

Ini penting karena potongan terakhir dari nama file yang dikirim grepdari findmungkin sebenarnya hanya berisi nama file tunggal, dalam hal grepini tidak akan menyebutkannya dalam hasilnya.


Materi bonus:

Membedah perintah find+ xargs+ sh:

find . -type f -name '*.words' -print0 |
xargs -0 sh -c '
    if [ -f tmpfile ]; then
        sort -o tmpfile -m tmpfile "$@"
    else
        sort -o tmpfile -m "$@"
    fi' sh 

find . -type f -name '*.words'hanya akan menghasilkan daftar nama path dari direktori saat ini (atau di bawah) di mana setiap nama path adalah dari file biasa ( -type f) dan yang memiliki komponen nama file di akhir yang cocok *.words. Jika hanya direktori saat ini yang akan dicari, seseorang dapat menambahkan -maxdepth 1setelah ., sebelumnya -type f.

-print0akan memastikan bahwa semua nama path yang ditemukan dikeluarkan dengan karakter \0( nul) sebagai pembatas. Ini adalah karakter yang tidak valid di jalur Unix dan memungkinkan kita untuk memproses nama path meskipun mengandung karakter baris baru (atau hal-hal aneh lainnya).

findpipa hasilnya ke xargs.

xargs -0akan membaca \0daftar nama path yang telah direvisi dan akan mengeksekusi utilitas yang diberikan berulang kali dengan potongan-potongan ini, memastikan bahwa utilitas dieksekusi dengan argumen yang cukup untuk tidak menyebabkan shell mengeluh tentang daftar argumen yang terlalu panjang, sampai tidak ada input lagi dari find.

Utilitas yang dipanggil oleh xargsadalah shdengan skrip yang diberikan pada baris perintah sebagai string menggunakan -cbenderanya.

Ketika menggunakan sh -c '...some script...'argumen berikut, argumen akan tersedia untuk skrip $@, kecuali argumen pertama , yang akan ditempatkan di $0(ini adalah "nama perintah" yang dapat Anda temukan misalnya topjika Anda cukup cepat). Inilah sebabnya kami menyisipkan string shsebagai argumen pertama setelah akhir skrip aktual. String shadalah argumen dummy dan bisa berupa kata tunggal (beberapa tampaknya lebih suka _atau sh-find).

Kusalananda
sumber
Di akhir skrip shell pertama Anda, apa gunanya fi' sh?
dan
@danielAzuelos Ini fiadalah akhir dari ifpernyataan dalam shskrip shell "internal" . The 'ujung bahwa script shell (seluruh naskah adalah string tunggal dikutip). Ini shakan diteruskan ke skrip internal di $0(bukan bagian dari $@, yang akan berisi nama file). Dalam contoh ini, shstring itu sebenarnya adalah kata apa saja . Jika meninggalkan shpada akhirnya, nama file pertama akan diteruskan $0dan tidak akan menjadi bagian dari pemrosesan yang dilakukan skrip shell internal.
Kusalananda
8

Baris-baris di dalam file individual diurutkan dan digandakan gratis.

Yang berarti Anda mungkin menemukan beberapa kegunaan untuk sort -m:

 -m, --merge
        merge already sorted files; do not sort

Alternatif lain yang jelas untuk melakukan ini adalah sederhana awkuntuk mengumpulkan garis-garis dalam array, dan menghitungnya. Tetapi seperti yang dikomentari @dave_thompson_085 , 3.000 juta baris (atau betapapun banyaknya yang unik) kemungkinan akan membutuhkan sejumlah besar memori untuk disimpan, sehingga mungkin tidak bekerja dengan baik.

ilkkachu
sumber
3

Dengan awk Anda bisa mendapatkan semua baris berulang di semua file dalam satu perintah singkat:

$ awk '_[$0]++' *.words

Tapi itu akan mengulangi garis jika garis ada 3 kali atau lebih.
Ada solusi untuk mendapatkan hanya duplikat pertama:

$ awk '_[$0]++==1' *.words

Itu harus cukup cepat (jika pengulangan sedikit) tetapi akan memakan banyak memori untuk menjaga semua baris dalam memori. Mungkin, tergantung pada file dan pengulangan yang sebenarnya, coba dengan 3 atau empat file terlebih dahulu.

$ awk '_[$0]++==1' [123]*.words

Jika tidak, Anda dapat melakukan:

$ sort -m *.words | uniq -d

Yang akan mencetak baris berulang uniq.

Ishak
sumber
2
+1 untuksort -m * | uniq -d
Jeff Schaller
awk dapat menghindari pengulangan dengan 'x[$0]++==1'tetapi memang membutuhkan banyak memori; jika garis 3G mengatakan 1G nilai berbeda, dan jika penafsir Anda perlu mengatakan 50 byte untuk entri entri pemetaan pemetaan string (mungkin pendek) ke nilai uninit, itu 50GB. Untuk input yang diurutkan, Anda dapat melakukannya uniq -dsecara manual dengan awk '$0==p&&n++==1;$0!=p{p=$0;n=1}'tetapi mengapa repot?
dave_thompson_085
@ dave_thompson_085 Terima kasih untuk konsep ==1, ide bagus.
Isaac
Dengan asumsi 30000 file dengan masing-masing 100000 baris 80 karakter dan tidak ada duplikat , ini akan diperlukan awkuntuk menyimpan 2,4E11 byte (223 GiB).
Kusalananda
sort -m *.words | uniq -dbekerja hebat! Setelah proses saya menjalankan grepuntuk menemukan file yang berisi entri yang digandakan. Apakah Anda melihat cara untuk mencetak setidaknya satu nama file yang berisi entri yang digandakan?
Lars Schneider
3

Solusi sort+ yang dioptimalkan uniq:

sort --parallel=30000 *.words | uniq -d
  • --parallel=N - ubah jumlah jenis yang dijalankan bersamaan N
  • -d, --repeated - hanya cetak garis duplikat, satu untuk setiap grup
RomanPerekhrest
sumber