블룸 필터의 원리는 매우 간단합니다. 정수 키로 문자열을 해시 한 다음 0으로 시작하는 매우 긴 비트 시퀀스를 선택 하고이 위치에서 0을 키에서 1으로 변경하는 것입니다. 다음에 문자열이 들어 오면 해시 후 값 키가 있고이 비트의 값도 1 인 경우 문자열이 존재 함을 의미합니다.
위의 방법을 따르면 해시 알고리즘과 다르지 않으며 여전히 해시 알고리즘의 복제가 있습니다.
블룸 필터는 문자열을 여러 키로 해시하므로 책을 따라갈 것입니다.
먼저 16 억 바이너리 상수를 생성 한 다음 16 억 바이너리 비트를 모두 0으로 설정하십시오. 각 문자열에 대해 8 개의 다른 랜덤 생성기 (F1, F2, ..., F8)를 사용하여 8 개의 정보 지문 (F1, F2, ..., F8)을 생성합니다. 그런 다음 임의의 숫자 생성기 G를 사용 하여이 8 개의 정보 지문을 8 자연 숫자 G1, G2, ..., G8에 1 ~ 16 억으로 매핑합니다. 이제이 8 위치의 모든 바이너리 비트를 1로 변경하십시오.이 방법으로 블룸 필터가 제작됩니다.
그렇다면 문자열이 이미 존재하는지 여부를 감지하는 방법은 무엇입니까?
이제 8 개의 임의 번호 생성기 (F1, F2, ..., F8)를 사용 하여이 문자열의 8 개의 정보 지문 S1, S2, ..., S8을 생성 한 다음이 8 개의 정보 지문을 블룸 필터의 8 바이너리 비트, 즉 T1, T2, ..., T8에 해당합니다. 문자열이 존재하면 분명히 T1, T2, ..., T8에 해당하는 이진 비트는 1이어야합니다. 이것은 문자열이 이미 존재하는지 여부를 결정하는 방법입니다.
실제로 블룸 필터는 해시 알고리즘의 확장입니다. 그것은 본질적으로 해시이기 때문에 분명히 단점이있을 것입니다. 다시 말해, 분명히 잘못 판단 할 것입니다. 문자열이 나타나지 않았지만 블룸 필터 판단이 나타났습니다. 가능성은 매우 작지만 존재합니다.
그렇다면이 확률을 줄이는 방법은 무엇입니까? 우선, 8 개의 정보 지문이 16 개의 오류로 확장되면 확률이 확실히 감소 될 것이지만, 이런 식으로 블룸 필터가 저장할 수있는 문자열의 수도 1 회 감소한다는 것을 고려해야합니다. 또한 우수한 해시 함수를 선택하면 매우 우수한 해시 함수를 포함하여 문자열에 대한 많은 유형의 해시 방법이 있습니다.
청동 필터는 주로 악성 URL을 필터링하는 데 사용됩니다. 모든 악성 URL은 청동 필터에 구축 된 다음 URL에 의해 사용자에게 액세스됩니다. 악의적 인 URL이면 사용자에게 알립니다. 이런 식으로, 우리는 종종 판단 오류가있는 일부 URL에 대한 화이트리스트를 설정 한 다음 존재하는 것으로 판단되는 URL과 화이트리스트의 URL과 일치 할 수 있습니다. 그들이 화이트리스트에 있다면, 그들은 석방 될 것이다. 물론,이 화이트리스트는 너무 크거나 너무 크지도 않으며 블룸 필터 오류의 확률은 매우 작습니다. 관심있는 독자는 블룸 필터의 오류율을 확인할 수 있습니다.
다음은 Bloom 필터의 Java 버전의 소스 코드입니다.
import java.util.bitset; /** * * @author xkey */public class bloomfilter {private static final int default_size = 2 << 24; 블룸 필터 개인 정적 최종 int [] seeds = {3,5,7, 11, 13, 31, 37, 61}; private static simplehash [] func = new Simplehash [seeds.length]; public static void addValue (String value) {for (simplehash f : func) // 문자열 값을 8 개 이상의 정수로 해시 한 다음이 정수 비트의 비트에서 1으로 변경 (f.hash (value), true); } public static void add (문자열 값) {if (value! = null) addValue (value); } public static boolean은 (문자열 값) {if (value == null) return false; 부울 ret = true; (simplehash f : func) // 실제로 여기에서 모두 실행할 필요가 없습니다. 그냥 ret == false를 한 번, 문자열이 포함되지 않습니다. ret = ret && bits.get (f.hash (value)); Ret Ret; } public static void main (String [] args) {String value = "www.vevb.com"; for (int i = 0; i <seeds.length; i ++) {func [i] = new SimpleHash (default_size, seeds [i]); } add (값); System.out.println (contains (value)); }} class simpleHash {// 이것은 c ++ private int 캡의 구조와 동일합니다. 개인 int 씨앗; public simplehash (int cap, int seed) {this.cap = cap; this.seed = 종자; } public int hash (문자열 값) {// stand 해시, 좋은 해시 함수 int result = 0을 선택하는 것이 매우 중요합니다. int len = value.length (); for (int i = 0; i <len; i ++) {result = seed * result+value.charat (i); } return (CAP -1) & 결과; }} 요약 : Bloom Filter는 해싱 알고리즘의 혁신이며 공간이 거의없고 오류율이 낮습니다. 요컨대,이 혁신적인 아이디어는 학습 할 가치가 있으며 비트와 같은 데이터 유형을 사용합니다.
Bloom 필터의 Java 구현 방법은 내가 공유 한 모든 컨텐츠입니다. 나는 당신이 당신에게 참조를 줄 수 있기를 바랍니다. 그리고 당신이 wulin.com을 더 지원할 수 있기를 바랍니다.