고정 된 비트 수 (예 : 슬롯) (m)와 고정 된 해시 함수 수 (k)가 주어지면 이론적 인 오 탐지율 (p)은 어떻게 계산됩니까?블룸 필터 : 위양성 비율 평가
은 위키 http://en.wikipedia.org/wiki/Bloom_filter 따르면, 위양성율 (p)과 항목 (N)의 개수, m = - n * l(p)/(l(2)^2) 주어진다 필요한 비트 수 (m)와 해시 함수 (K)의 최적 수에 주어진다 에 의해 k = m/n * l(2). , p = e(-m/n*(l(2)^2)) 나는 가정 : p = (1 - e(-(k * n/m)))^k
을하지만 위키 백과는 또 다른 식 (p)를 가지고 : 위키 백과 페이지에 주어진 식에
, 나는 내가 다음에 의해 이론적 위양성률 (p)를 평가할 수있을 것 같아요 (k)가 해쉬 함수의 최적 수라고 가정한다.
예를 들어, n = 1000000과 m = n * 2을 취 했으므로 (k)의 최적 값은 1.386이고 이론 위양 긍정 비율 (p)은 이전 공식에 따라 0.382가됩니다. 더 많은 비트가 박제되어
for k = 1, p = .393 and m' = 1941401
for k = 2, p = .399 and m' = 1909344
for k = 3, p = .469 and m' = 1576527
for k = 4, p = .559 and m' = 1210636
: 필요한 비트의 이론적 인 수 (m ')를 고정 (K)에 주어진 이론적 위양성율 (p)를 계산한다,의 함수의 수를 선택하자 계산할 필터를 사용하면 가양 성이 높아집니다. 논리적 인 것 같아.
그러나 fixed (k), (m) 및 (n)이 주어지면 이론적 인 위양성 비율을 얻는 공식은 p = (1 - e(-(k * n/m)))^k이라는 것이 맞습니까?
참고 : 질문은 이미 여기에서 묻습니다 : With fixed number of functions, how can I calculate the size of a Bloom Filter given the probability of false positives?하지만 내 정확한 질문과 일치하는 답변이 없습니다. How many hash functions does my bloom filter need?이 흥미로울 수도 있지만 다시 똑같은 것은 아닙니다.
안부
당신이 명확한 질문을 명시하시기 바랍니다 수 :
내가 블룸 필터에 수학 친절한 튜토리얼을 썼다? AFAICT Wikipedia 페이지를 읽으면서 자신의 질문에 답변했습니다. 따라서 Stackoverflow에서 찾고자하는 것이 명확하지 않습니다. – Kaganar
@ 카가나 (Kaganar) 나는 약간의 질문을 다시 써서 중요한 질문에 중점을 두었다. 댓글 주셔서 감사합니다. – ydroneaud
Wikipedia 기사는 지수 함수를 소개하는 마지막 단계까지 상당히 명료하고 정확합니다. 그 시점에서 나는 친숙하지 않은 근사값을 사용합니다. 기하 급수적 인 기능을 사용하기 전에 단계가 있습니까? – Kaganar