Bloom Filter ile Verimli Set Üyeliği

Bloom filtresi, bir elemanın bir kümenin üyesi olup olmadığını test etmek için tasarlanmış bir veri yapısıdır. Yazım denetimi, veritabanı indeksleme ve hızlı ve bellek açısından verimli bir küme üyeliği testi yöntemi gerektiren ağ yönlendiricileri gibi çeşitli uygulamalarda kullanılır. Bloom filtreleri olasılıklı veri yapılarıdır, yani yanlış pozitifler üretebilir ancak asla yanlış negatifler üretemezler.

Bloom Filter'ı anlatmadan önce hash'i anlayalım. Karma, büyük miktarda veriyi, aynı karma değeri (çarpışma) oluşturan iki veri değerinin küçük bir olasılığı ile sabit boyutlu daha küçük bir karma değerine indirgeme tekniğidir.

uygulama

Bloom filtreleri, tümü başlangıçta 0'a ayarlanmış, N bitlik bir bit dizisi olarak uygulanır. Bit dizisi, kümeyi temsil eder ve her öğe, farklı sağlama işlevleri kullanılarak K kez özetlenir. Ortaya çıkan K hash değerleri, bit dizisindeki karşılık gelen bitleri 1'e ayarlamak için kullanılır.

Üyeliği kontrol etmek için, öğeye K kez tekrar hash uygulanır ve bit dizisindeki sonuçtaki bitler kontrol edilir. Tüm K bitleri 1'e ayarlanırsa, öğe kümenin bir üyesi olarak kabul edilir, ancak öğenin gerçekten kümeye eklenmemiş olması olasıdır ve bu da yanlış bir pozitifle sonuçlanır.

Yanlış pozitif olasılığı, bit dizisinin boyutu, N ve hash fonksiyonlarının sayısı, K ile belirlenir.

Kullanım Örneği

Kullanıcıların benzersiz bir kullanıcı adı ve parola ile kaydolmasına izin veren bir kullanıcı kayıt sistemi tasarlamamız gerektiğini varsayalım. Seçilen bir kullanıcı adının mevcut olup olmadığını kontrol etmek için tüm veritabanını dolaşabilir ve bir eşleşme olup olmadığını kontrol edebiliriz, ancak bu yavaş ve yoğun bellek kullanan bir yöntemdir. Daha iyi bir çözüm, bir Bloom filtresi kullanmaktır.

Bloom filtresi, büyük bir bit dizisi ve bir dizi hash işleviyle başlatılır. Bit dizisi başlangıçta tüm sıfırlara ayarlanır ve karma işlevleri, girdi değerlerini bit dizisi boyunca eşit olarak dağıtmak için seçilir.

Bir kullanıcı kaydolmaya çalıştığında, seçilen kullanıcı adı, bit dizisinde bir dizi dizin oluşturan karma işlevlerinden geçirilir. Sistem daha sonra bu indekslerdeki bitlerin değerini kontrol eder. Tüm bitler bire ayarlanırsa, sistem kullanıcı adının zaten kullanımda olduğunu varsayar ve kaydı reddeder. Bitlerden herhangi biri sıfıra ayarlanırsa, sistem kullanıcı adının kullanımda olmadığını onaylayabilir ve kayıt işlemine devam eder.

Kayıt tamamlandıktan sonra sistem, hash işlevleri tarafından oluşturulan dizinlerdeki bitleri bire ayarlar ve bu da kullanıcı adının artık kullanımda olduğunu gösterir.

Bu, bir kullanıcı adı kayıt sisteminde küme üyeliğini verimli bir şekilde kontrol etmek için bir Bloom filtresinin nasıl kullanılabileceğinin basit bir örneğidir. Küçük bir yanlış pozitif olasılığı olsa da, ikincil bir kontrolün kullanılması bu sınırlamayı etkili bir şekilde azaltabilir ve sonuçların doğruluğunu sağlayabilir.

Örnek

Bir kullanıcı adı kayıt sisteminde Bloom filtresinin örnek bir uygulamasını deneyelim.

10 uzunluğunda bir bit dizisine ve üç hash işlevine sahip bir Bloom Filtresi düşünüyoruz.
Başlangıçta, bit dizisinin tüm bitleri 0 olarak ayarlanır.

Bit Array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

h1("Rohit") = 8
h2("Rohit") = 2
h3("Rohit") = 7

Kayıt tamamlandıktan sonra sistem, hash fonksiyonları tarafından oluşturulan indekslerdeki bitleri bire ayarlar.

Bit Array: [0, 0, 1, 0, 0, 0, 0, 1, 1, 0]

h1("Mohit") = 2
h2("Mohit") = 8
h3("Mohit") = 5

Kayıt tamamlandıktan sonra sistem, hash fonksiyonları tarafından oluşturulan indekslerdeki bitleri bire ayarlar.

Bit Array: [0, 0, 1, 0, 0, 1, 0, 1, 1, 0]

h1("Rahul") = 2
h2("Rahul") = 5
h3("Rahul") = 7

Bu, Bloom Filtreleri kullanılırken meydana gelebilecek yanlış pozitiflere bir örnektir. Bunun üstesinden gelmek için sistem, kullanıcı adının kullanılabilirliğini doğrulamak için veritabanında ikincil bir kontrol gerçekleştirir.

Lehte ve aleyhte olanlar

Bloom filtresinin ana avantajlarından biri alan verimliliğidir. Set öğelerini depolamak için hash tabloları veya ikili arama ağaçları gibi diğer veri yapılarına kıyasla önemli ölçüde daha az bellek kullanır. Diğer bir avantajı da sabit zamanlı çalışmasıdır. Üyelik testinin zaman karmaşıklığı O(K), ister K, kümedeki öğelerin sayısına bakılmaksızın, hash fonksiyonlarının sayısı olsun.

Bununla birlikte, Bloom filtresinin olasılıksal doğası, yanlış pozitiflerin kabul edilemediği uygulamalar için uygun olmadığı anlamına gelir. Bu gibi durumlarda, hash tabloları veya ikili arama ağaçları gibi alternatif veri yapıları kullanılmalıdır.

Bir Bloom filtresinin yanlış pozitif oranı, bit dizisinin boyutu veya hash fonksiyonlarının sayısı artırılarak azaltılabilir. Bununla birlikte, bit dizisinin boyutunu artırmak, filtrenin bellek gereksinimlerini de artıracaktır. Öte yandan, hash fonksiyonlarının sayısının artması, üyelik testinin zaman karmaşıklığını artıracaktır. Alan ve zaman karmaşıklığı arasındaki optimum dengeyi bulmak, Bloom filtrelerini kullanırken önemli bir husustur.

Ortak Kullanımlar

Bloom filtreleri, verimlilikleri ve olasılıksal yapıları nedeniyle çeşitli üst düzey tasarım uygulamalarında kullanılır. Yaygın kullanım durumlarından bazıları şunlardır: -
Web Arama Motorları : Bloom filtreleri, önceden taranmış sayfaların URL'lerini depolamak için kullanılabilir ve arama motorlarının daha önce ziyaret edilmiş sayfaları yeniden taramasını engeller.
Veritabanı indeksleme : Bir veritabanının belirli bir kayıt içerip içermediğini kontrol etmek için Bloom filtrelerini kullanma, tam bir tablo taraması ihtiyacını ortadan kaldırma.
Ağ yönlendirme : Hedef adreslerinin bir dizi yetkili adrese ait olup olmadığını kontrol ederek ağ paketlerini filtreleme.
Yazım denetimi : Bir kelimenin büyük bir sözlükte olup olmadığını kontrol etme.