Cari file yang diurutkan dengan efisien

Saya memiliki file besar yang berisi satu string di setiap baris. Saya ingin dapat dengan cepat menentukan apakah string ada di file. Idealnya, ini akan dilakukan dengan menggunakan algoritma tipe biner chop.

Beberapa Googling mengungkapkan lookperintah dengan -bflag yang menjanjikan untuk menemukan dan mengeluarkan semua string yang diawali dengan awalan yang diberikan menggunakan algoritma pencarian biner. Sayangnya, tampaknya tidak berfungsi dengan benar dan mengembalikan hasil nol untuk string yang saya tahu ada di file (mereka dikembalikan dengan benar oleh greppencarian yang setara ).

Adakah yang tahu utilitas atau strategi lain untuk mencari file ini secara efisien?

Ada perbedaan mendasar antara grepdan look:

Kecuali dinyatakan sebaliknya, grepakan menemukan pola bahkan di suatu tempat di dalam garis. Untuk lookstatus halaman manual:

lihat - garis tampilan dimulai dengan string yang diberikan

Saya tidak menggunakan lookterlalu sering, tetapi itu berfungsi dengan baik pada contoh sepele yang baru saja saya coba.

Mungkin sedikit terlambat menjawab:

Sgrep akan membantu Anda.

Sgrep (sort grep) mencari file input yang diurutkan untuk baris yang cocok dengan kunci pencarian dan menampilkan baris yang cocok. Saat mencari file besar sgrep jauh lebih cepat daripada grep Unix tradisional, tetapi dengan batasan yang signifikan.

• Semua file input harus diurutkan file biasa.
• Kunci pengurutan harus dimulai pada awal baris.
• Kunci pencarian hanya cocok di awal baris.
• Tidak ada dukungan ekspresi reguler.

Anda dapat mengunduh sumber di sini: https://sourceforge.net/projects/sgrep/?source=typ_redirect

dan dokumen-dokumen di sini: http://sgrep.sourceforge.net/

Cara lain:

Saya tidak tahu seberapa besar file tersebut. Mungkin Anda harus mencoba paralel:

/programming/9066609/fastest-possible-grep

Saya selalu melakukan grep dengan file yang ukuran> 100GB, itu berfungsi dengan baik.

Anda dapat memotong file menjadi beberapa bagian dan kemudian hanya mengambil bagian yang Anda inginkan:

for line in $(cat /usr/share/dict/american-english | tr '[:upper:]' '[:lower:]' | sort | uniq)
do
    prefix=$(echo $line | md5sum - | cut -c 1-2)
    mkdir -p $prefix
    echo $line | gzip >> $prefix/subwords
done

maka pencarian akan terlihat seperti:

    prefix=$(echo $word | md5sum - | cut -c 1-2)
    zgrep -m 1 -w word $prefix/subwords

Ini melakukan dua hal:

1. baca dan tulis file terkompresi. Ini umumnya lebih cepat untuk meletakkan beban pada cpu (sangat cepat) daripada disk (sangat lambat)
2. hash hal untuk mendapatkan distribusi yang kurang lebih sama, Anda dapat menggunakan hash yang lebih pendek atau lebih lama seperti yang Anda inginkan untuk mengurangi ukuran masing-masing bagian (tapi saya akan merekomendasikan menggunakan subdirektori bersarang jika Anda melakukannya)

sgrep mungkin bekerja untuk Anda:

sudo apt-get install sgrep
sgrep -l '"needle"' haystack.txt

Halaman proyek http://sgrep.sourceforge.net/ mengatakan:

Sgrep menggunakan algoritma pencarian biner, yang sangat cepat, tetapi membutuhkan input yang diurutkan.

Namun untuk penyisipan, saya pikir tidak ada solusi yang lebih baik daripada menggunakan database: /programming/10658380/shell-one-liner-to-add-a-line-to-a-sorted-file/ 33859372 # 33859372

Jika Anda menginginkannya sangat cepat (O (1) cepat), Anda dapat membuat hash set untuk melihatnya. Saya tidak dapat menemukan implementasi yang akan membiarkan saya menyimpan hash yang sudah dibangun dalam sebuah file dan menyelidikinya tanpa harus membaca seluruh file ke dalam memori, jadi saya menggulung sendiri .

Bangun hash set ( -b/ --build):

./hashset.py --build string-list.txt strings.pyhashset

Periksa set hash ( -p/ --probe):

./hashset.py --probe strings.pyhashset \
    'Is this string in my string list?' 'What about this one?'

... atau dengan string untuk mencari input standar:

printf '%s\n' 'Is this string in my string list?' 'What about this one?' |
./hashset.py --probe strings.pyhashset

Anda dapat meredam output --probedengan opsi -q/ --quietjika Anda hanya tertarik pada status keluar:

if ./hashset.py --quiet --probe strings.pyhashset ...; then
    echo 'Found'
else
    echo 'Not found'
fi

Untuk opsi lebih lanjut lihat deskripsi penggunaan yang dapat diakses melalui -h/ --helpopsi atau READMEfile yang menyertainya .