確率的データ構造・ブルームフィルタについてのまとめ - kakts-log

概要 特定のデータが、ある集合やリストに含まれるかどうかを判定するために線形探索や二分探索などいくつかのサーチアルゴリズムが使われますが、 本稿ではメモリの使用効率、探索の際の計算量が優れているブルームフィルタを用いたアルゴリズムについてまとめます。 ブルームフィルタとは ブルームフィルタとは確率的データ構造の一種で、あるデータが集合に属するかどうかを判定する際に使われます。 特徴としては、メモリの空間消費が少なくすみ、非常に効率的にデータの存在判定ができます。 デメリットとしては、false-positive(偽陽性)によるデータの誤判定の可能性があり、集合に存在しないデータを存在すると誤判定してしまう場合があります。このような誤判定が許されないような状況においては、ブルームフィルタは使えません。 逆に、false-negative(偽陰性)による誤判定はないため、データは実際にあるのに