Cuckoo Filter๏ผBetter Than Bloom
Last updated
Last updated
ๅธ้่ฟๆปคๅจๆ็ผบ็น๏ผๆฏๅฆไธๆฏๆๅ ้คๆไฝใๆฅ่ฏขๆ็ๅผฑ๏ผๅ ไธบๅคไธช้ๆบๅๅธๅฝๆฐๆขๆต็ๆฏbitๆฐ็ปไธญๅคไธชไธๅ็็น๏ผๆไปฅไผๅฏผ่ดไฝCPU็ผๅญๅฝไธญ็
ไน๏ผๆๅฐฑๆฏๆฏไฝ ๅผ๏ผ
Cukoo่งฃๅณไบ่ฟไธช้ฎ้ข๏ผ็จๆดไฝ็็ฉบ้ดๅผ้่งฃๅณไบๅธ้่ฟๆปคๅจไธ่ฝๅ ้คๅ
็ด ็้ฎ้ข
supports adding and removing items dynamically ๏ผๅจๆ็ๆทปๅ ๅๅ ้คๅ ็ด ๏ผ
higher lookup performance, even when close to full ๏ผๆด้ซ็ๆฅๆพๆง่ฝ๏ผๅณไฝฟๅจๆฅ่ฟๆปก็ๆ ๅตไธ๏ผ
easier to implement than alternatives such as the quotient filter ๏ผๆฏ่ตทๅ่ฟๆปคๅจๅฎๆดๅฎนๆๅฎ็ฐ๏ผ
less space if the target false positive rate is less than 3% ๏ผๅฆๆ่ฆๆฑ่ฏฏๅค็ไฝไบ3%๏ผๅฎๆฏๅธ้่ฟๆปคๅจๆๆดไฝ็็ฉบ้ดๅผ้๏ผ
ๆๅๅง็ๅธ่ฐท้ธๅๅธๆนๆณๆฏไฝฟ็จไธคไธชๅๅธๅฝๆฐๅฏนไธไธชkey่ฟ่กๅๅธ๏ผๅพๅฐๆกถไธญ็ไธคไธชไฝ็ฝฎ๏ผๆญคๆถ
ๅฆๆไธคไธชไฝ็ฝฎ้ฝไธบไธบ็ฉบๅๅฐkey้ๆบๅญๅ
ฅๅ
ถไธญไธไธชไฝ็ฝฎ
ๅฆๆๅชๆไธไธชไฝ็ฝฎไธบ็ฉบๅๅญๅ ฅไธบ็ฉบ็ไฝ็ฝฎ
ๅฆๆ้ฝไธไธบ็ฉบ๏ผๅ้ๆบ่ธขๅบไธไธชๅ ็ด ๏ผ่ธขๅบ็ๅ ็ด ๅ้ๆฐ่ฎก็ฎๅๅธๆพๅฐ็ธๅบ็ไฝ็ฝฎ
ๅฝ็ถๅๅฆๅญๅจ็ปๅฏน็็ฉบ้ดไธ่ถณ๏ผ้ฃ่ๆฏ่ธขๅบไนไธๆฏๅๆณ๏ผๆไปฅไธ่ฌไผ่ฎพ็ฝฎไธไธช่ธขๅบ้ๅผ๏ผๅฆๆๅจๆๆฌกๆๅ ฅ่กไธบ่ฟ็จไธญ่ฟ็ปญ่ธขๅบ่ถ ่ฟ้ๅผ๏ผๅ่ฟ่กๆฉๅฎนใ
ๆข่จไน๏ผ
ๅฎๆไธคไธช hash ่กจ๏ผ่ฎฐไธบ T1๏ผT2ใ
ไธคไธช hash ๅฝๆฐ๏ผ่ฎฐไธบ h1๏ผh2ใ
ๅฝไธไธชไธๅญๅจ็ๅ ็ด ๆๅ ฅ็ๆถๅ๏ผไผๅ ๆ นๆฎ h1 ่ฎก็ฎๅบๅ ถๅจ T1 ่กจ็ไฝ็ฝฎ๏ผๅฆๆ่ฏฅไฝ็ฝฎไธบ็ฉบๅๅฏไปฅๆพ่ฟๅปใ
ๅฆๆ่ฏฅไฝ็ฝฎไธไธบ็ฉบ๏ผๅๆ นๆฎ h2 ่ฎก็ฎๅบๅ ถๅจ T2 ่กจ็ไฝ็ฝฎ๏ผๅฆๆ่ฏฅไฝ็ฝฎไธบ็ฉบๅๅฏไปฅๆพ่ฟๅปใ
ๅฆๆ่ฏฅไฝ็ฝฎไธไธบ็ฉบ๏ผๅฐฑๆๅฝๅไฝ็ฝฎไธ็ๅ ็ด ่ธขๅบๅป๏ผ็ถๅๆๅฝๅๅ ็ด ๆพ่ฟๅปๅฐฑ่กไบใ
ไนๅฏไปฅ้ๆบ่ธขๅบไธคไธชไฝ็ฝฎไธญ็ไธไธช๏ผๆปไนไผๆไธไธชๅ ็ด ่ขซ่ธขๅบๅปใ
่ขซ่ธขๅบๅป็ๅ ็ด ๆไนๅๅข๏ผ
่ฟ็ง็ฑปไผผไบๅฅๅจ็่งฃๅณๆนๅผ็ๆฏๅฏ่ก๏ผไฝๆฏๆปๆฏๆๅบ็ฐๅพช็ฏ่ธขๅบๅฏผ่ดๆพไธ่ฟ x ็้ฎ้ขใ
ๆฏๅฆไธๅพไธญ็(b)
ๅฝ้ๅฐ่ฟ็งๆ
ๅตๆถๅ๏ผ่ฏดๆๅธ่ฐท้ธ hash ๅทฒ็ปๅฐไบๆ้ๆ
ๅต๏ผๅบ่ฏฅ่ฟ่กๆฉๅฎน๏ผๆ่
hash ๅฝๆฐ็ไผๅใๆไปฅ๏ผไฝ ๅๆฌกๅป็ไผชไปฃ็ ็ๆถๅ๏ผไฝ ไผๆ็ฝ้้ข็ MaxLoop ็ๅซไนๆฏไปไนไบใ
่ฟไธช MaxLoop ็ๅซไนๅฐฑๆฏไธบไบ้ฟๅ
็ธไบ่ธขๅบ็่ฟไธช่ฟ็จๆง่กๆฌกๆฐๅคชๅค๏ผ่ฎพ็ฝฎ็ไธไธช้ๅผใ
๏ผa๏ผ(b)ๅฑ็คบไบไธไธชๅบๆฌ็ๅธ่ฐท้ธๅๅธ่กจ็ๆๅ
ฅๆไฝ๏ผๆฏ็ฑไธไธชๆกถๆฐ็ป็ปๆ๏ผๆฏไธชๆๅ
ฅ้กน้ฝๆ็ฑๆฃๅๅฝๆฐh1(x)ๅh2(x)็กฎๅฎ็ไธคไธชๅ้ๆกถ๏ผๅ
ทไฝๆไฝไธๆไธญๅทฒ็ปๆ่ฟฐใ
่ๅบๆฌ็ๅธ่ฐท้ธ่ฟๆปคๅจไนๆฏ็ฑไธคไธชๆ่ ๅคไธชๅๅธๅฝๆฐๆๆ๏ผๅธ่ฐท้ธ่ฟๆปคๅจ็ๅธ่ฐท้ธๅๅธ่กจ็ๅบๆฌๅไฝ็งฐไธบๆก็ฎ๏ผentry๏ผใ ๆฏไธชๆก็ฎๅญๅจไธไธชๆ็บน๏ผfingerprint๏ผใ
ๆ็บนๆ็ๆฏไฝฟ็จไธไธชๅๅธๅฝๆฐ็ๆ็nไฝๆฏ็นไฝ๏ผn็ๅ
ทไฝๅคงๅฐ็ฑๆ่ฝๆฅๅ็่ฏฏๅค็ๆฅ่ฎพ็ฝฎ๏ผ่ฎบๆไธญ็ไพๅญไฝฟ็จ็ๆฏ**8 bits**็ๆ็บนๅคงๅฐใ
ๆฅ่ฏขๆฐๆฎ็ๆถๅ๏ผๅฐฑๆฏ็็ๅฏนๅบ็ไฝ็ฝฎไธๆๆฒกๆๅฏนๅบ็โๆ็บนโไฟกๆฏ๏ผ
ๅ ้คๆฐๆฎ็ๆถๅ๏ผไนๅชๆฏๆนๆ่ฏฅไฝ็ฝฎไธ็โๆ็บนโ่ๅทฒ๏ผ
็ฑไบๆฏๅฏนๅ ็ด ่ฟ่ก hash ่ฎก็ฎ๏ผ้ฃไนๅฟ ็ถไผๅบ็ฐโๆ็บนโ็ธๅ็ๆ ๅต๏ผไนๅฐฑๆฏไผๅบ็ฐ่ฏฏๅค็ๆ ๅตใ
ๆฒกๆๅญๅจๅๆฐๆฎ๏ผๆไปฅ็บ็ฒไบๆฐๆฎ็ๅ็กฎๆง๏ผไฝๆฏๅชไฟๅญไบๅ ไธช bit๏ผๅ ๆญคๆๅไบ็ฉบ้ดๆ็ใ
ๅ้ข็(a)ใ(b)ๅพ็ฎๅ๏ผ่ฟๆฏไธคไธช hash ๅฝๆฐ๏ผไฝๆฏๆฒกๆ็จไธคไธชๆฐ็ปๆฅๅญๆฐๆฎ๏ผๅฐฑๆฏๅบไบไธ็ปดๆฐ็ป็ๅธ่ฐท้ธ hash ๏ผๆ ธๅฟ่ฟๆฏ่ธขๆฅ่ธขๅป๏ผ้็นๅจไบ(c)๏ผๅฏนๆฐ็ป่ฟ่กไบๅฑๅผ๏ผไปไธ็ปดๅๆไบไบ็ปด๏ผๆฏไธไธชไธๆ ๏ผๅฏไปฅๆพ 4 ไธชๅ ็ด ไบ๏ผ็ฉบ้ดๅฉ็จ็้ฃๅ๏ผ
_็ผบ็น_่ฏฆ่ง่ฎบๆ็ฌฌๅ ญ่orๆฌๆไธ้ข
ๆๅ ฅๆฏ้็น๏ผไธๆด็ด ็ๅธ่ฐท้ธๅๅธไธๅใ้ฆๅ ๏ผๆไปฌๅๅฟไธไธๅธ่ฐท้ธ hash๏ผๅฎๅญๅจ็ๆฏๆๅ ฅๅ ็ด ็ๅๅงๅผ๏ผๆฏๅฆ x๏ผx ไผ็ป่ฟไธคไธช hash ๅฝๆฐ๏ผๅฆๆๆไปฌ่ฎฐๆฐ็ป็้ฟๅบฆไธบ L๏ผ้ฃไนๅฐฑๆฏ่ฟๆ ท็๏ผ
p1 = hash1(x) % L
p2 = hash2(x) % L
ๅธ่ฐท้ธ่ฟๆปคๅจ้ๅไบไธคไธชๅนถไธ็ฌ็ซ็ๅๅธๅฝๆฐ:
ๅ ่ฏดๆ็บน๏ผๅ ทไฝ็ๆ็บนๆฏ้่ฟๅๅธๅฝๆฐๅไธๅฎ้็ๆฏ็นไฝ:
f = fingerprint(x)
ไธ้ขๆฏๅๅธๅฝๆฐ๏ผ
i1 = h1(x) = hash(x) ้่ฟๆไธชๅๅธๅฝๆฐ่ฎก็ฎๅบๆฅ
i2 = h2(x) = i1 โ hash(f) ไฝฟ็จ็ฌฌไธไธช็ดขๅผๅๆ็บน็ๅๅธๅไบไธไธชๅผๆๆไฝ
i1ใi2ๅณ่ฎก็ฎๅบๆฅไธคไธชๆกถ็็ดขๅผใ่ฟ่กๅผๆๆไฝๆฏๅ ไธบๅผๆๆไฝ็็นๆง๏ผๅไธบ0ไธๅไธบ1๏ผไธ0ๅไปปไฝๆฐๅผๆๆฏ่ฟไธชๆฐ็ๆฌ่บซใๅผๆ่ฟ็ฎ็กฎไฟไบไธไธช้่ฆ็ๆง่ดจ๏ผไฝ็ฝฎ i2 ๅฏไปฅ้่ฟไฝ็ฝฎ i1 ๅ i1 ไธญๅญๅจ็โๆ็บนโ่ฎก็ฎๅบๆฅ๏ผๅณ๏ผๅจๆกถไธญ่ฟ่ตฐไธไธช้ฎ๏ผๆไปฌ็ดๆฅ็จๅฝๅๆกถ็็ดขๅผiๅๅญๅจๅจๆกถไธญ็ๆ็บน่ฎก็ฎๅฎ็ๅค็จๆกถใ
ๅ ไธบไฝฟ็จ็ๅผๆ่ฟ็ฎ๏ผๆไปฅ่ฟไธคไธชไฝ็ฝฎๅ ทๆๅฏนๅถๆงใ
ๅช่ฆไฟ่ฏ hash(xโs fingerprint) !=0๏ผ้ฃไนๅฐฑๅฏไปฅ็กฎไฟ h2!=h1๏ผไนๅฐฑๅฏไปฅ็กฎไฟ๏ผไธไผๅบ็ฐ่ชๅทฑ่ธข่ชๅทฑ็ๆญปๅพช็ฏ้ฎ้ขใ
ไธบไปไนไธ็ดๆฅ็จ็ดขๅผ1ๅๆ็บนๅๅผๆๆไฝ๏ผๅ ไธบๆ็บนไธ่ฌๅชๆฏkeyๆ ๅฐๅบๆฅ็ๅฐ้bitไฝ็ฝฎ๏ผ้ฃไนๅๅฆไธ่ฟ่กๅๅธๆไฝ๏ผๅฝๆ็บน็ๆฏ็นไฝไธๆดไธชๆกถๆฐ็ป็ธๆฏๅพๅฐๆถ๏ผ้ฃไนๅค็จไฝ็ฝฎไฝฟ็จโi โ ๆ็บนโ๏ผๅฐ่ขซๆพ็ฝฎๅฐ็ฆปๆกถi1ๅพ่ฟ็ไฝ็ฝฎ๏ผๆฏๅฆไฝฟ็จๅ
ซไฝ็ๆ็บนๅคงๅฐ๏ผๆๅคๅช่ฝๆนๅi1็ไฝๅ
ซไฝ๏ผๆไปฅไนๅฐฑๆฏไธคไธชๅ้้็ไฝ็ฝฎๆๅค็ธๅทฎ256๏ผไธๅฉไบๅๅๅ้
ใ
ๆไปฅ๏ผๅฏนโๆ็บนโ่ฟ่กๅๅธๅค็ๅฏ็กฎไฟ่ขซ่ธขๅบๅป็ๅ ็ด ๏ผๅฏไปฅ้ๆฐๅฎไฝๅฐๅๅธ่กจไธญๅฎๅ จไธๅ็ๅญๅจๆกถไธญ๏ผไป่ๅๅฐๅๅธๅฒ็ชๅนถๆ้ซ่กจๅฉ็จ็ใ
่ฟๆไธช้ฎ้ข๏ผ
ๅฎๆฒกๆๅฏนๆฐ็ป็้ฟๅบฆ่ฟ่กๅๆจก๏ผ้ฃไนๅฎๆไนไฟ่ฏ่ฎก็ฎๅบๆฅ็ไธๆ ไธๅฎๆฏ่ฝๅจๆฐ็ปไธญ็ๅข๏ผ
่ฟไธชๅฐฑๅพ่ฏดๅฐๅธ่ฐท้ธ่ฟๆปคๅจ็ๅฆๅคไธไธช้ๅถไบ๏ผ
ๅ ถๅผบๅถๆฐ็ป็้ฟๅบฆๅฟ ้กปๆฏ 2 ็ๆๆฐๅ๏ผไบ่ฟๅถไธๅฎๆฏ่ฟๆ ท็๏ผ10000000...๏ผnไธช0๏ผใ
่ฟไธช้ๅถๅธฆๆฅ็ๅฅฝๅคๅฐฑๆฏ๏ผ่ฟ่กๅผๆ่ฟ็ฎๆถ๏ผๅฏไปฅไฟ่ฏ่ฎก็ฎๅบๆฅ็ไธๆ ไธๅฎๆฏ่ฝๅจๆฐ็ปไธญ็ใ
่ฟไธช้ๅถๅธฆๆฅ็ๅๅคๅฐฑๆฏ๏ผ
ๅธ่ฐท้ธ่ฟๆปคๅจ๏ผๆๆฏๆๅ ้คๆไฝใ
ๅธ้่ฟๆปคๅจ๏ผๆไธ้่ฆ้ๅถ้ฟๅบฆไธบ 2 ็ๆๆฐๅใ
ๅธ่ฐท้ธ่ฟๆปคๅจ๏ผๆๆฅๆพๆง่ฝๆฏไฝ ้ซใ
ๅธ้่ฟๆปคๅจ๏ผๆไธ้่ฆ้ๅถ้ฟๅบฆไธบ 2 ็ๆๆฐๅใ
ๅธ่ฐท้ธ่ฟๆปคๅจ๏ผๆ็ฉบ้ดๅฉ็จ็ไน้ซใ
ๅธ้่ฟๆปคๅจ๏ผๆไธ้่ฆ้ๅถ้ฟๅบฆไธบ 2 ็ๆๆฐๅใ
ๅธ่ฐท้ธ่ฟๆปคๅจ๏ผๆ็ฆๆญปไบ๏ผCNM๏ผ
็ปๅฎไธไธช้กนx๏ผ็ฎๆณ้ฆๅ ๆ นๆฎไธ่ฟฐๆๅ ฅๅ ฌๅผ๏ผ่ฎก็ฎx็ๆ็บนๅไธคไธชๅ้ๆกถใ็ถๅ่ฏปๅ่ฟไธคไธชๆกถ๏ผๅฆๆไธคไธชๆกถไธญ็ไปปไฝ็ฐๆๆ็บนๅน้ ๏ผๅๅธ่ฐท้ธ่ฟๆปคๅจ่ฟๅtrue๏ผๅฆๅ่ฟๆปคๅจ่ฟๅfalseใๆญคๆถ๏ผๅช่ฆไธๅ็ๆกถๆบขๅบ๏ผๅฐฑๅฏไปฅ็กฎไฟๆฒกๆๅ้ดๆง
ๆ ๅๅธ้่ฟๆปคๅจไธ่ฝๅ ้ค๏ผๅ ๆญคๅ ้คๅไธช้กน้่ฆ้ๅปบๆดไธช่ฟๆปคๅจ๏ผ่่ฎกๆฐๅธ้่ฟๆปคๅจ้่ฆๆดๅค็็ฉบ้ดใ
ๅธ่ฐท้ธ่ฟๆปคๅจๅฐฑๅ่ฎกๆฐๅธ้่ฟๆปคๅจ๏ผๅฏไปฅ้่ฟไปๅๅธ่กจๅ ้ค็ธๅบ็ๆ็บนไป่ๅ ้คๆๅ ฅ็้กน๏ผๅ ถไปๅ ทๆ็ฑปไผผๅ ้ค่ฟ็จ็่ฟๆปคๅจๆฏๅธ่ฐท้ธ่ฟๆปคๅจๆดๅคๆใ
ๅ ทไฝๅ ้ค็่ฟ็จไนๅพ็ฎๅ๏ผๆฃๆฅ็ปๅฎ้กน็ไธคไธชๅ้ๆกถ๏ผๅฆๆไปปไฝๆกถไธญ็ๆ็บนๅน้ ๏ผๅไป่ฏฅๆกถไธญๅ ้คๅน้ ๆ็บน็ไธไปฝๅฏๆฌใ
**ๅ ้คไธๅฎ็พ๏ผๅญๅจ่ฏฏๅ ็ๆฆ็ใ**ๅ ้ค็ๆถๅๅชๆฏๅ ้คไบไธไปฝๆ็บนๅฏๆฌ๏ผๅนถไธ่ฝ็กฎๅฎๆญคๆ็บนๅฏๆฌๆฏ่ฆๅ ้ค็key็ๆ็บนใๅๆถ่ฟไธช้ฎ้ขไนๅฏผ่ดไบๅ้ณๆง็ๆ ๅตใ
**ๆๅ ฅๅคๆๅบฆๆฏ่พ้ซใ**้็ๆๅ ฅๅ ็ด ็ๅขๅค๏ผๅคๆๅบฆไผ่ถๆฅ่ถ้ซ๏ผๅ ไธบๅญๅจๆกถๆปก๏ผ่ธขๅบ็ๆไฝ๏ผๆไปฅ้่ฆ้ๆฐ่ฎก็ฎ๏ผไฝ็ปผๅๆฅ่ฎฒๅคๆๅบฆ่ฟๆฏๅธธๆฐ็บงๅซใ
ๅญๅจ็ฉบ้ด็ๅคงๅฐๅฟ ้กปไธบ2็ๆๆฐ็้ๅถ่ฎฉ็ฉบ้ดๆ็ๆไบๆๆฃใ
ๅไธไธชๅ ็ด ๆๅคๆๅ ฅkbๆฌก๏ผ๏ผkๆๅๅธๅฝๆฐ็ไธชๆฐ๏ผbๆ็ๆกถไธญ่ฝ่ฃ ๆ็บน็ไธชๆฐไนๅฏไปฅ่ฏดๆฏๆกถ็ๅฐบๅฏธๅคงๅฐ๏ผไธไธชไธๆ ่ฝๆพๅ ไธชๅ ็ด ๏ผ๏ผๅฆๆๅธ่ฐท้ธ่ฟๆปคๅจๆฏๆๅ ้ค๏ผๅๅฟ ้กปๅญๅจๅไธ้กน็ๅคไธชๅฏๆฌใ ๆๅ ฅๅไธ้กนkb+1ๆฌกๅฐๅฏผ่ดๆๅ ฅๅคฑ่ดฅใ ่ฟ็ฑปไผผไบ่ฎกๆฐๅธ้่ฟๆปคๅจ๏ผๅ ถไธญ้ๅคๆๅ ฅไผๅฏผ่ด่ฎกๆฐๅจๆบขๅบใ
ๆฏๅฆ 2 ไธช hash ๅฝๆฐ๏ผไธไธชไบ็ปดๆฐ็ป๏ผๅฎ็ๆฏไธชไธๆ ๆๅคๅฏไปฅๆๅ ฅ 4 ไธชๅ ็ด ใ้ฃไนๅฏนไบๅไธไธชๅ ็ด ๏ผๆๅคๆฏๆๆๅ ฅ 8 ๆฌกใ
ไพๅฆไธ้ข่ฟ็งๆ ๅต๏ผ
why ๅทฒ็ปๆๅ ฅไบ 8 ๆฌกไบ๏ผๅฆๆๅๆฌกๆๅ ฅไธไธช why๏ผๅไผๅบ็ฐๅพช็ฏ่ธขๅบ็้ฎ้ข๏ผ็ดๅฐๆๅคงๅพช็ฏๆฌกๆฐ๏ผ็ถๅ่ฟๅไธไธช falseใ
ๆไน้ฟๅ ่ฟไธช้ฎ้ขๅข
ๆไปฌ็ปดๆคไธไธช่ฎฐๅฝ่กจ๏ผ่ฎฐๅฝๆฏไธชๅ ็ด ๆๅ ฅ็ๆฌกๆฐๅฐฑ่กไบใ
่ฝ็ถ้ป่พ็ฎๅ๏ผไฝๆฏๆณๆณๆฐๆฎ้ๅคง็ๆ ๅฝข๏ผ่ฟไธช่กจ็ๅญๅจ็ฉบ้ดๅๆไน็ฎๅข๏ผemmmmmm
ๆกถ็ๅฐบๅฏธ๏ผ
ๆฏๆๆฏไธชๆกถ่ฝๆพ็ๆ็บนไธชๆฐ๏ผไฟๆๅธ่ฐท้ธ่ฟๆปคๅจ็ๆปๅคงๅฐ๏ผๆกถๆฐ็ป๏ผไธๅ๏ผไฝๆนๅๆกถ็ๅคงๅฐ๏ผไธ่ฟฐไพๅญไฝฟ็จ็ๆฏๅคงๅฐไธบ4๏ผไผๅฏผ่ดไธคไธชๅๆ๏ผ
(1) ่พๅคง็ๆกถๅฏไปฅๆ้ซ่กจ็ๅฉ็จ็(ๅณb่ถๅคงๅ้ณๆง็่ถๅคง) ๏ผไฝฟ็จk=2ไธชๅๅธๅฝๆฐๆถ๏ผๅฝๆกถๅคงๅฐb=1๏ผๅณ็ดๆฅๆ ๅฐๅๅธ่กจ๏ผๆถ๏ผ่ด่ฝฝๅ ๅญฮฑไธบ50%๏ผไฝไฝฟ็จๆกถๅคงๅฐb=2ใ4ๆ8ๆถๅๅๅซไผๅขๅ ๅฐ84%ใ95%ๅ98%ใ
(2) ่พๅคง็ๆกถ้่ฆ่พ้ฟ็ๆ็บนๆ่ฝไฟๆ็ธๅ็ๅ้ณๆง็(ๅณb่ถๅคงf่ถๅคง)ใ ไฝฟ็จ่พๅคง็ๆกถๆถ๏ผๆฏๆฌกๆฅๆพ้ฝไผๆฃๆฅๆดๅค็ๆก็ฎ๏ผไป่ๆๆดๅคง็ๆฆ็ไบง็ๆ็บนๅฒ็ชใ
ๆไปฅ่ฆๅบไบไปฅไธๅฏปๆพไธไธชๆๅ้็ๆกถๅคงๅฐ
่ดดไธไธช
