Hai, habrozhiteli! Algoritma adalah jantung dan jiwa dari ilmu komputer. Anda tidak dapat melakukannya tanpa mereka, mereka ada di mana saja - mulai dari perutean jaringan dan perhitungan genomik hingga kriptografi dan pembelajaran mesin. "Algoritma Sempurna" akan mengubah Anda menjadi seorang profesional sejati yang akan menetapkan tugas dan menyelesaikannya dengan baik dalam kehidupan maupun dalam sebuah wawancara saat mempekerjakan perusahaan IT mana pun.
Dalam buku kedua, Tim Rafgarden, guru algoritma, berbicara tentang pencarian grafik dan aplikasinya, algoritma pencarian jalur terpendek, dan penggunaan dan implementasi beberapa struktur data: tumpukan, pohon pencarian, tabel hash, dan filter Bloom.
Posting ini menyajikan kutipan dari Bloom Filter: The Basics.
Tentang apa buku ini
Bagian kedua dari buku "Algoritma Sempurna" adalah kursus pengantar tentang dasar-dasar literasi pada tiga topik berikut.
Pencarian grafik dan aplikasi . Grafik memodelkan sejumlah jenis jaringan yang berbeda, termasuk jalan, komunikasi, jejaring sosial dan jaringan ketergantungan antar tugas. Grafik bisa rumit, tetapi ada beberapa primitif yang sangat cepat untuk berbicara tentang struktur grafik. Kita akan mulai dengan algoritma pencarian grafik linear-waktu, dari aplikasi mulai dari analisis jaringan hingga membangun urutan operasi.
Jalur terpendek . Dalam masalah jalur terpendek, tujuannya adalah untuk menghitung rute terbaik di jaringan dari titik A ke titik B. Tugas ini memiliki aplikasi yang jelas, seperti menghitung rute lalu lintas, dan juga tampak tersembunyi dalam banyak tugas universal lainnya. Kami akan menggeneralisasi salah satu algoritma pencarian grafik kami dan datang ke algoritma pencarian jalur terpendek Dijkstra yang terkenal.
Struktur data . Buku ini akan menjadikan Anda pengguna berpendidikan tinggi dari beberapa struktur data berbeda yang dirancang untuk mendukung serangkaian objek yang berkembang dengan kunci terkait. Tujuan utamanya adalah untuk mengembangkan intuisi tentang struktur data mana yang tepat untuk aplikasi Anda. Bagian tambahan memberikan pedoman untuk menerapkan struktur data ini dari awal.
Pertama, kami membahas tumpukan yang dapat dengan cepat mengidentifikasi objek yang disimpan dengan kunci terkecil, dan juga berguna untuk menyortir, mengimplementasikan antrian prioritas, dan mengimplementasikan algoritma Dijkstra yang hampir linier-temporal. Pohon pencarian mempertahankan urutan kunci lengkap pada objek yang disimpan dan mendukung jangkauan operasi yang lebih luas. Tabel hash dioptimalkan untuk operasi pencarian ultra cepat dan tersebar luas dalam program modern. Kami juga melihat filter Bloom, kerabat dekat dari tabel hash, yang menggunakan lebih sedikit ruang karena kesalahan acak.
Anda dapat membiasakan diri dengan isi buku ini secara lebih rinci di bagian "Kesimpulan", yang melengkapi setiap bab dan mengidentifikasi poin-poin terpenting. Bagian-bagian buku, ditandai dengan tanda bintang, adalah yang paling canggih dalam hal tingkat informasi yang disajikan. Jika buku ini dirancang untuk pengenalan topik yang dangkal, maka pembaca dapat mengabaikannya tanpa kehilangan integritas tulisannya.
Topik dibahas dalam tiga bagian lainnya . Bagian pertama buku “Algoritma Sempurna. Fundamentals ”mencakup notasi asimptotik (notasi O-besar dan kerabat dekatnya), algoritma“ divide and conquer ”dan teorema relasi perulangan utama - metode utama, pengurutan cepat secara acak dan analisisnya, serta algoritma seleksi linear-temporal. Bagian ketiga berkaitan dengan algoritma serakah (perencanaan, pohon spanning minimal, pengelompokan, kode Huffman) dan pemrograman dinamis (masalah ransel, penyelarasan urutan, jalur terpendek, pohon pencarian optimal). Bagian keempat dikhususkan untuk kelengkapan NP, apa artinya bagi perancang algoritma, dan strategi untuk memecahkan masalah yang tidak dapat larut secara komputasi, termasuk analisis heuristik dan pencarian lokal.
12.5. Filter Bloom: Dasar-Dasarnya
Filter Bloom adalah kerabat dekat dari tabel hash. Mereka sangat kompak, tetapi secara berkala membuat kesalahan. Bagian ini menjelaskan bagaimana filter Bloom baik dan bagaimana mereka diterapkan, sementara bagian 12.6 menetapkan kurva kompromi antara jumlah ruang yang digunakan oleh filter dan tingkat kesalahannya.
12.5.1. Operasi yang didukung
Alasan keberadaan filter Bloom pada dasarnya sama dengan hash table: operasi penyisipan dan tampilan super cepat, berkat itu Anda dapat dengan cepat mengingat apa yang Anda lihat dan apa yang tidak. Mengapa kita harus direpotkan oleh struktur data yang berbeda dengan rangkaian operasi yang sama? Karena filter Bloom lebih disukai daripada tabel hash dalam aplikasi di mana ruang bernilai beratnya dalam emas, dan kesalahan acak bukan halangan untuk transaksi.
Seperti tabel hash dengan pengalamatan terbuka, filter Bloom jauh lebih mudah untuk diterapkan dan bayangkan dalam pikiran ketika mereka hanya mendukung operasi Sisipkan dan Lihat (dan tanpa operasi Hapus). Kami akan fokus pada kasus ini.
FILTER BLOOM: OPERASI YANG DIDUKUNG
Lihat: dengan kunci k, kembalikan "ya" jika k sebelumnya dimasukkan ke dalam filter Bloom, dan "tidak" sebaliknya.
Tempel: tambahkan kunci baru k ke filter Bloom.
Filter Bloom sangat efisien secara spasial; biasanya, mereka mungkin hanya membutuhkan 8 bit per sisipan. Ini cukup sulit dipercaya, karena 8 bit sama sekali tidak cukup untuk mengingat bahkan kunci 32-bit atau pointer ke objek! Karena alasan ini, operasi tampilan di filter Bloom hanya mengembalikan jawaban "ya" / "tidak", sementara di tabel hash, operasi ini mengembalikan pointer ke objek yang diinginkan (jika ditemukan). Itulah sebabnya operasi Sisipkan sekarang hanya menerima kunci, dan bukan objek (penunjuk ke).
Tidak seperti semua struktur data lain yang kami pelajari, filter Bloom bisa salah. Ada dua jenis kesalahan: false negative ketika operasi View mengembalikan "false" bahkan jika kunci yang diminta telah dimasukkan sebelumnya, dan pernyataan palsu (atau pemicu) ketika operasi View mengembalikan "true", meskipun kunci yang diminta belum dimasukkan di masa lalu . Pada bagian 12.5.3 kita akan melihat bahwa filter Bloom dasar tidak pernah menderita negatif palsu, tetapi mereka dapat memiliki "elemen hantu" dalam bentuk pernyataan palsu. Bagian 12.6 menunjukkan bahwa frekuensi klaim palsu dapat dikontrol dengan menyesuaikan penggunaan ruang secara tepat. Implementasi khas filter Bloom mungkin memiliki tingkat kesalahan sekitar 1% atau 0,1%.
Waktu eksekusi untuk operasi Sisipkan dan Lihat secepat di tabel hash. Dan yang lebih baik lagi, operasi ini dijamin akan dilakukan dalam waktu yang konstan, terlepas dari penerapan filter Bloom dan data1. Namun, implementasi dan kumpulan data memengaruhi tingkat kesalahan filter.
Untuk merangkum keuntungan dan kerugian filter Bloom atas tabel hash:
FILTER BLOOM TERHADAP TABEL HASH
1. Kelebihan: lebih efektif secara spasial.
2. Kelebihan: operasi permanen-waktu yang dijamin untuk setiap kumpulan data.
3. Kekurangan: tidak dapat menyimpan pointer ke objek.
4. Kontra: penghapusan lebih kompleks dibandingkan dengan tabel hash dengan kopling.
5. Kekurangan: probabilitas pernyataan nol salah.
Daftar indikator untuk filter Bloom dasar adalah sebagai berikut.
Tabel 12.4. Filter Bloom Dasar: operasi yang didukung dan waktu pelaksanaannya. Tanda belati (†) menunjukkan bahwa operasi Tampilan memiliki probabilitas klaim palsu yang dapat dikontrol tetapi tidak nol
Filter Bloom harus digunakan sebagai pengganti tabel hash dalam aplikasi di mana keunggulannya penting dan kerugiannya tidak menjadi penghalang untuk transaksi.
KAPAN MENGGUNAKAN FILTER BLOOM
Jika aplikasi memerlukan pencarian cepat dengan serangkaian objek yang berkembang secara dinamis, ruang sepadan dengan bobotnya dalam emas dan sejumlah kecil klaim palsu yang dapat diterima, maka filter Bloom biasanya merupakan struktur data yang disukai.
12.5.2. Aplikasi
Selanjutnya, ada tiga kegunaan dengan pemindaian berulang, di mana menghemat ruang bisa menjadi penting, dan pernyataan palsu tidak menjadi penghalang untuk transaksi.
Pemeriksa ejaan. Kembali pada tahun 1970-an, filter Bloom digunakan untuk mengimplementasikan pemeriksa ejaan - pemeriksa ejaan. Pada tahap pra-pemrosesan, setiap kata dalam kamus dimasukkan ke dalam filter Bloom. Ejaan dokumen turun ke satu operasi. Lihatlah kata dalam dokumen, tandai setiap kata yang operasi ini mengembalikan "tidak".
Dalam lampiran ini, pernyataan palsu sesuai dengan kata yang tidak valid yang diterima oleh pemeriksa ejaan secara tidak sengaja. Kesalahan seperti itu tidak membuat pemeriksa ejaan ideal. Namun, pada awal 1970-an, ruang bernilai emas, jadi menggunakan filter Bloom pada saat itu adalah strategi win-win.
Kata sandi yang dilarang . Aplikasi lama yang masih berlaku hingga hari ini melacak kata sandi terlarang - kata sandi yang terlalu umum atau terlalu mudah ditebak. Awalnya, semua kata sandi terlarang dimasukkan ke dalam filter Bloom; kata sandi terlarang tambahan dapat dimasukkan kemudian, sesuai kebutuhan. Ketika pengguna mencoba untuk mengatur atau mengatur ulang kata sandi, sistem mencari kata sandi yang diusulkan di filter Bloom. Jika pencarian mengembalikan "ya", maka pengguna diminta untuk mencoba lagi dengan kata sandi yang berbeda. Di sini, pernyataan palsu diterjemahkan menjadi kata sandi yang kuat, yang ditolak oleh sistem.
Asalkan tingkat kesalahan tidak terlalu tinggi, katakan tidak lebih dari 1% atau 0,1%, ini tidak terlalu menjadi masalah. Dari waktu ke waktu, beberapa pengguna perlu satu upaya tambahan untuk menemukan kata sandi yang dapat diterima oleh sistem.
Router internet . Sejumlah aplikasi Bloom filter yang menakjubkan saat ini berlangsung jauh di Internet, di mana paket data melewati router dengan kecepatan streaming. Ada banyak alasan mengapa router mungkin ingin dengan cepat mengingat apa yang dilihatnya di masa lalu. Misalnya, router mungkin ingin menemukan alamat IP sumber dari paket dalam daftar alamat IP yang diblokir, melacak konten cache untuk menghindari tampilan cache palsu, atau menyimpan statistik yang membantu mengidentifikasi penolakan serangan jaringan layanan. Tingkat kedatangan paket membutuhkan tampilan super cepat, dan memori router yang terbatas membuat ruang bernilai emas. Aplikasi ini dikelola secara langsung oleh Bloom Filter.
12.5.3. Implementasi
Melihat ke dalam filter Bloom, Anda dapat melihat implementasi yang elegan. Struktur data mendukung string n-bit atau, sama, sebuah array A dengan panjang n di mana setiap elemen adalah 0 atau 1. (Semua elemen diinisialisasi ke nol.) Struktur ini juga menggunakan fungsi hash m h1, h2, ..., hm , sementara masing-masing memetakan semesta U dari semua kunci yang mungkin ke set {0, 1, 2, ..., n - 1} dari posisi dalam array. Parameter m sebanding dengan jumlah bit yang digunakan oleh filter Bloom untuk penyisipan, dan, sebagai aturan, adalah konstanta kecil (misalnya, 5).
Setiap kali kunci dimasukkan ke filter Bloom, masing-masing fungsi hash menetapkan flag, mengatur bit array A ke 1 yang sesuai.
BLOOM FILTER: INSERT (ON KEY)
for i = 1 to m do A[hi(k)] := 1
Misalnya, jika m = 3 dan h1 (k) = 23, h2 (k) = 17 dan h3 (k) = 5, memasukkan k menyebabkan bit ke-5, 17 dan 23 dari array diatur sama 1 (Gbr. 12.5).
Dalam operasi Lihat, filter Bloom mencari sidik jari yang mungkin tetap ada pada sisipan k.
FILTER BLOOM: LIHAT (KEY KEY)
for i = 1 to m do if A [hi (k)] = 0 then return «» return «»
Sekarang kita dapat melihat mengapa filter Bloom tidak dapat menderita negatif palsu. Ketika kunci k dimasukkan, bit m yang sesuai diatur ke 1. Selama masa hidup filter Bloom, bit dapat mengubah nilainya dari 0 ke 1, tetapi tidak sebaliknya. Jadi, m bit ini tetap 1 selamanya. Setiap operasi Lihat k berikutnya dijamin untuk mengembalikan jawaban ya yang benar.
Kita juga bisa melihat bagaimana pernyataan palsu muncul. Misalkan m = 3 dan empat tombol k1, k2, k3, k4 memiliki nilai hash berikut:
Misalkan kita memasukkan k1, k2, k3 dan k4 ke dalam filter Bloom (Gambar 12.6). Ketiga sisipan ini menghasilkan total sembilan bit yang diatur ke 1, termasuk tiga bit dalam sidik jari kunci k1 (5, 17, dan 23). Pada titik ini, filter Bloom tidak lagi dapat membedakan apakah kunci k1 dimasukkan atau tidak. Bahkan jika k1 tidak dimasukkan ke dalam filter, pencarian akan mengembalikan "ya", yang merupakan pernyataan salah.
Secara intuitif, kita dapat mengasumsikan bahwa dengan peningkatan ukuran n filter Bloom, jumlah overlay di antara sidik jari kunci yang berbeda akan berkurang, yang, pada gilirannya, mengarah pada sejumlah kecil pernyataan salah. Tetapi tujuan utama filter Bloom adalah untuk menghemat ruang. Apakah ada jalan tengah di mana n dan frekuensi pernyataan palsu secara bersamaan kecil? Jawabannya tidak jelas dan memerlukan beberapa analisis matematika yang dilakukan di bagian selanjutnya.
»Informasi lebih lanjut tentang buku ini dapat ditemukan di
situs web penerbit»
Isi»
KutipanUntuk diskon 20% Khabrozhiteley pada kupon -
AlgoritmaSetelah pembayaran versi kertas buku, sebuah buku elektronik dikirim melalui email.