🧔🏻 🐛 🌳 Pencarian file cepat ☕️ 🤘🏿 👵

Dari seorang penerjemah: Saya memperhatikan terjemahan dari artikel yang sangat tua yang diterbitkan pada 15 Januari 1983. Meskipun usianya sangat mengesankan, artikel itu tampak menarik bagi saya, dan mungkin saja itu akan bermanfaat bagi seseorang saat ini. Ngomong-ngomong, artikel ini direferensikan di bagian man loc (1) help di opennet.ru: https://www.opennet.ru/man.shtml?topic=locate .

Ringkasan

Artikel ini menjelaskan mekanisme pencarian file cepat di UNIX. Ini menggabungkan dua metode kompresi data dengan teknik pencarian baris baru, dan dirancang untuk mencari file sewenang-wenang dengan cepat. Kode, yang diintegrasikan ke dalam utilitas pencari standar, mencari di database yang dibuat sebelumnya, diperbarui setiap hari. Ini membedakannya dari mekanisme biasa untuk mencari kecocokan kunci dengan kandidat, yang dihasilkan dengan cepat dari struktur direktori yang tersebar (pada disk).

Basis data path file adalah daftar yang disandikan secara bertahap, diurutkan secara leksikografis (kadang-kadang disebut file "dikompresi depan"), yang juga mengalami pengkodean bigramic reguler untuk mendapatkan kompresi yang efektif. Rasio kompresi adalah 5 hingga 6 dibandingkan dengan representasi ASCII biasa. Daftar ini dipindai menggunakan pencarian linear yang dimodifikasi, disesuaikan secara khusus untuk pengkodean tambahan, sedangkan waktu tipikal yang dihabiskan oleh algoritma adalah 40-50% lebih sedikit daripada pencarian biasa.

pengantar

Menemukan file dalam sistem komputer, atau jaringan komputer, adalah proses yang kompleks. Pengguna UNIX dapat mengimplementasikannya dalam berbagai cara, dari memanipulasi perintah cd, ls, dan grep, hingga perintah khusus, seperti yang dikembangkan oleh Berkeley whereis dan fleese, dan yang lebih umum menemukan perintah Unix.

Sayangnya, fleece (dari Berkeley) terbatas pada direktori home, dan di mana hanya dapat mencari kode sistem dan dokumentasi yang terletak di tempat-tempat standar.

Cari:

find / -name "*<filename>*" -print

tentu saja, ia dapat mencari file yang sewenang-wenang, tetapi sangat lambat, karena ia menggunakan keturunan rekursif di seluruh sistem file, tanpa ampun tersebar di seluruh disk. Ketidaksabaran mendorong kami untuk mengembangkan alternatif (dalam kaitannya dengan metode "cari dan temukan") mencari jalur ke file.

Perhitungan awal

Mengapa tidak membuat daftar statis semua file dalam sistem dan mencari grep? Sistem khas yang berisi 20.000 file akan berisi 1.000 blok nama file, bahkan jika Anda mempersingkat / usr ke / u. Grep pada sistem PDP-11/70 kami yang tanpa proses memproses 30-40 blok per detik, dan akan membutuhkan setengah menit untuk memindai. Ini tidak dapat diterima untuk perintah yang umum digunakan.

Tetapi jika kita membuat pengorbanan kecil - ketidakmampuan untuk mencari file yang berumur kurang dari satu hari, maka ini tidak akan membuat masalah besar, karena orang yang membuat file seperti itu mungkin dalam jangkauan, atau mungkin file tersebut belum siap menggunakan. File lama yang dibuat oleh grup pengguna lain dengan konvensi penamaan file yang berbeda adalah kandidat pencarian yang paling mungkin.

Kompresi

Untuk mempercepat akses untuk aplikasi, Anda dapat menyarankan menggunakan pencarian biner atau tabel hash, tetapi skema tersebut tidak berfungsi dengan baik untuk perbandingan parsial, jika kami hanya tertarik pada bagian dari nama. Teknik kompresi data yang dipesan, dikenal sebagai pengkodean inkremental, yang digunakan untuk tugas kompresi kamus yang serupa dengan mudah diimplementasikan [Morris / Thompson, 1974]. Dalam hal ini, awalan terpanjang dari nama sebelumnya dihitung. Contohnya:

/usr/src
/usr/src/cmd/aardvark.c
/usr/src/cmd/armadillo.c
/usr/tmp/zoo

dikonversi ke

0/usr/src
8/cmd/aardvark.c
14armadillo.c
5tmp/zoo

Decoding akan sederhana (deklarasi variabel dihilangkan)

fp = fopen(COMPRESSED_FILELIST, "r");
while((count = (getc(fp) & 0177)) != EOF) {
    for(p = path + count; (*p++ = getc(fp)) < 0200; )
        ; /*overlay old path with new*/
    ungetc(*--p, fp);
    *p-- = NULL;
    if(math(path, name) == YES)
        puts(path);
}

di mana matematika adalah fungsi yang menentukan apakah nama substring terkandung dalam string path .

Faktanya, karena daftar yang disandikan adalah sekitar lima kali lebih pendek dari yang tidak disandikan, dan penguraiannya sangat sederhana, program ini berjalan tiga hingga empat kali lebih cepat daripada grep pada file teks.

Bahkan lebih cepat

Pendekatan ini sudah berguna, tetapi masih ada ruang untuk perbaikan lebih lanjut. (Catatan: kode ini digunakan dalam utilitas find. Tidak perlu membebani UNIX dengan perintah lain [dan halaman manual] ketika kita dapat meningkatkan program serupa yang ada. Untungnya, tidak ada panggilan panggilan dengan dua argumen, dan kita dapat mengisi kekosongan tanpa embellishment :

find name

Perhatikan bahwa kode di atas masih mencari daftar yang belum dibuka, meskipun dalam memori, bukan pada disk. Ini dapat dihindari dengan membandingkan string dengan substring di arah yang berlawanan. Biarkan namend arahkan ke karakter terakhir dari nama string , dan ganti matematika dengan:

for(s = p, cutoff = path + count; s > cutoff; s--) {
    if(*s == namend) { /*quick first char check*/
        for(p = namend - 1, q = s - 1; *p != NULL; p--, q--)
            if(*q != *p)
                break;
        if(*p == NULL) {
            puts(path);
            break;
        }
    }
}

Ini lebih mudah dipahami dengan melihat tiga kasus. Jika substring sepenuhnya berada di sebelah kanan cutoff , perbandingan akan berakhir dengan sukses. Jika tumpang tindih, cutoff menjadi "lunak" dan perbandingan berlanjut. Jika substring terletak sepenuhnya di sebelah kiri cutoff , maka kecocokan akan terungkap untuk baris sebelumnya, yang berarti bahwa kami tidak dapat melakukan pencarian ini! Secara teknis, cutoff dapat dipindahkan ke jalur segera setelah perbandingan dilakukan. Kondisi ini dihilangkan di atas.

Peralatan dua tingkat

Anda dapat menghindari memperlambat pencarian yang disebabkan oleh pemrosesan karakter pola pencarian . Dalam melakukannya, kami memproses bagian dari nama yang tidak mengandung metakarakter dan menggunakan fungsi lambat rekursif amath dalam menemukan . Yaitu,

puts(path)

menjadi

if(globchars == NO | amatch(path, name))
    puts(path);

di mana gumpalan diatur jika nama berisi karakter meta. Contoh menggunakan pola pencarian untuk perintah orang sederhana :

vtroff -man 'find '*man*'"$1"'.[1-9]

Perbaikan lebih lanjut

Kode produksi utilitas penemuan meningkatkan rasio kompresi 20-25% dengan mengganti kombinasi dua karakter paling umum dengan kode ASCII yang tidak dapat dicetak. ".c" dan ".P" sangat umum.

Algoritme lain yang menerapkan trade-off lainnya antara waktu dan ukuran data, seperti algoritma Huffman [Reghbati, 1981], tidak terlihat menjanjikan: mereka hanya mengganti batas kinerja I / O dengan batas kinerja.

Metode pencarian sub-linear Boyer-Moore [Boyer, 1977] atau metode model makro [Storer / Szymanski, 1982] dapat digunakan.

Sebagai kesimpulan, perlu dicatat bahwa kami memindai 19.000 nama file dalam beberapa detik, menggunakan 180 blok dan kode C yang sesuai pada dua halaman.

Referensi

Boyer, RS Algoritma Pencarian String Cepat, Commun. ACM, Vol. 20, No. 10, Oktober 1977.
Morris, R. dan Thompson, K. Webster's Second on Head of a Pin, Memo Teknis yang tidak dipublikasikan, Laboratorium Bell, Murray Hill, NY, 1974.
Reghbati, HK Tinjauan Teknik Kompresi Data, Komputer, Vol. 14, Tidak. 4, April 1981.
Storer, JA dan Szymanski, Kompresi Data TG melalui Pergantian Tekstual, J. ACM, Vol. 29, No. 4, Oktober 1982.

Pencarian file cepat