Repository: barrust/pyprobables

Issue:
Implement an arg controlling error rate of cuckoo filter

Discussion:
codecov-commenter: # [Codecov](https://codecov.io/gh/barrust/pyprobables/pull/86?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Tyler+Barrus) Report
> Merging [#86](https://codecov.io/gh/barrust/pyprobables/pull/86?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Tyler+Barrus) (5e59108) into [master](https://codecov.io/gh/barrust/pyprobables/commit/4b671d563c55c9671b19836de3a15c1e5f08fc58?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Tyler+Barrus) (4b671d5) will **increase** coverage by `0.02%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/barrust/pyprobables/pull/86/graphs/tree.svg?width=650&height=150&src=pr&token=SGjJODewBP&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Tyler+Barrus)](https://codecov.io/gh/barrust/pyprobables/pull/86?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Tyler+Barrus)

```diff
@@            Coverage Diff             @@
##           master      #86      +/-   ##
==========================================
+ Coverage   99.02%   99.04%   +0.02%     
==========================================
  Files          15       15              
  Lines        1533     1567      +34     
==========================================
+ Hits         1518     1552      +34     
  Misses         15       15              
```


| [Impacted Files](https://codecov.io/gh/barrust/pyprobables/pull/86?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Tyler+Barrus) | Coverage Δ | |
|---|---|---|
| [probables/cuckoo/countingcuckoo.py](https://codecov.io/gh/barrust/pyprobables/pull/86/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Tyler+Barrus#diff-cHJvYmFibGVzL2N1Y2tvby9jb3VudGluZ2N1Y2tvby5weQ==) | `98.38% <100.00%> (+0.12%)` | :arrow_up: |
| [probables/cuckoo/cuckoo.py](https://codecov.io/gh/barrust/pyprobables/pull/86/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Tyler+Barrus#diff-cHJvYmFibGVzL2N1Y2tvby9jdWNrb28ucHk=) | `98.38% <100.00%> (+0.15%)` | :arrow_up: |

barrust: @KOLANICH any thoughts on this PR? 

It adds the ability to create, export, and load based on error_rate (export is the same) along with an `error_rate` property to see what the error rate is based on how it was instantiated. 

Patch:
diff --git a/docs/source/quickstart.rst b/docs/source/quickstart.rst
index 68625f4..e3f5d6c 100644
--- a/docs/source/quickstart.rst
+++ b/docs/source/quickstart.rst
@@ -231,6 +231,18 @@ Import a Cuckoo Filter
     >>> ccf2 = CuckooFilter(filepath='war_and_peace.cko')
     >>> print(ccf2.check('fleches'))  # prints True
 
+Cuckoo Filters based on Error Rate
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+To use error rate to initialize a Cuckoo Filter, there are class methods that can be used.
+`init_error_rate()` can be used to initialize a Cuckoo Filter that has not been exported, and
+`load_error_rate()` can be used to load in a previously exported Cuckoo Filter that used error rate
+to determine the parameters.
+
+.. code:: python3
+
+    >>> cko = CuckooFilter.init_error_rate(0.00001)
+    >>> cko.export('war_and_peace.cko')
+    >>> ckf = CuckooFilter.load_error_rate(0.00001)
 
 Other Cuckoo Filters
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
diff --git a/probables/cuckoo/countingcuckoo.py b/probables/cuckoo/countingcuckoo.py
index c04b29d..fbb2306 100644
--- a/probables/cuckoo/countingcuckoo.py
+++ b/probables/cuckoo/countingcuckoo.py
@@ -40,6 +40,7 @@ class CountingCuckooFilter(CuckooFilter):
         "__max_cuckoo_swaps",
         "_cuckoo_capacity",
         "_buckets",
+        "_fingerprint_size",
     ]
 
     def __init__(
@@ -66,6 +67,59 @@ class CountingCuckooFilter(CuckooFilter):
             hash_function,
         )
 
+    @classmethod
+    def init_error_rate(
+        cls,
+        error_rate: float,
+        capacity: int = 10000,
+        bucket_size: int = 4,
+        max_swaps: int = 500,
+        expansion_rate: int = 2,
+        auto_expand: bool = True,
+        hash_function: typing.Optional[SimpleHashT] = None,
+    ):
+        """Initialize a simple Cuckoo Filter based on error rate
+
+        Args:
+            error_rate (float):
+            capacity (int): The number of bins
+            bucket_size (int): The number of buckets per bin
+            max_swaps (int): The number of cuckoo swaps before stopping
+            expansion_rate (int): The rate at which to expand
+            auto_expand (bool): If the filter should automatically expand
+            hash_function (function): Hashing strategy function to use \
+            `hf(key)`
+        Returns:
+            CuckooFilter: A Cuckoo Filter object"""
+        cku = CountingCuckooFilter(
+            capacity=capacity,
+            bucket_size=bucket_size,
+            auto_expand=auto_expand,
+            max_swaps=max_swaps,
+            expansion_rate=expansion_rate,
+            hash_function=hash_function,
+        )
+        cku._error_rate = error_rate
+        cku._fingerprint_size = cku._calc_fingerprint_size()
+        return cku
+
+    @classmethod
+    def load_error_rate(cls, error_rate: float, filepath: str, hash_function: typing.Optional[SimpleHashT] = None):
+        """Initialize a previously exported Cuckoo Filter based on error rate
+
+        Args:
+            error_rate (float):
+            filepath (str): The path to the file to load or None if no file
+            hash_function (function): Hashing strategy function to use \
+            `hf(key)`
+        Returns:
+            CuckooFilter: A Cuckoo Filter object
+        """
+        cku = CountingCuckooFilter(filepath=filepath, hash_function=hash_function)
+        cku._error_rate = error_rate
+        cku._fingerprint_size = cku._calc_fingerprint_size()
+        return cku
+
     def __contains__(self, val: KeyT) -> bool:
         """setup the `in` keyword"""
         if self.check(val) > 0:
diff --git a/probables/cuckoo/cuckoo.py b/probables/cuckoo/cuckoo.py
index ae36bfc..7770443 100644
--- a/probables/cuckoo/cuckoo.py
+++ b/probables/cuckoo/cuckoo.py
@@ -4,7 +4,7 @@
 """
 
 import array
-import os
+import math
 import random
 import typing
 from collections.abc import ByteString
@@ -31,7 +31,7 @@ class CuckooFilter(object):
             finger_size (int): The size of the fingerprint to use in bytes \
             (between 1 and 4); exported as 4 bytes; up to the user to reset \
             the size correctly on import
-            filename (str): The path to the file to load or None if no file
+            filepath (str): The path to the file to load or None if no file
             hash_function (function): Hashing strategy function to use \
             `hf(key)`
         Returns:
@@ -43,10 +43,11 @@ class CuckooFilter(object):
         "__max_cuckoo_swaps",
         "__expansion_rate",
         "__auto_expand",
-        "__fingerprint_size",
+        "_fingerprint_size",
         "__hash_func",
         "_inserted_elements",
         "_buckets",
+        "_error_rate",
     ]
 
     def __init__(
@@ -58,7 +59,7 @@ class CuckooFilter(object):
         auto_expand: bool = True,
         finger_size: int = 4,
         filepath: typing.Optional[str] = None,
-        hash_function: typing.Optional[SimpleHashT] = None,  # this is incorrect
+        hash_function: typing.Optional[SimpleHashT] = None,
     ):
         """setup the data structure"""
         valid_prms = (
@@ -75,11 +76,11 @@ class CuckooFilter(object):
         self._bucket_size = int(bucket_size)
         self._cuckoo_capacity = int(capacity)
         self.__max_cuckoo_swaps = int(max_swaps)
-        self.__expansion_rate = None
+        self.__expansion_rate = 2
         self.expansion_rate = expansion_rate
         self.__auto_expand = True
         self.auto_expand = auto_expand
-        self.__fingerprint_size = 4
+        self._fingerprint_size = 32
         self.fingerprint_size = finger_size
 
         if hash_function is None:
@@ -97,6 +98,61 @@ class CuckooFilter(object):
             msg = "CuckooFilter: failed to load provided file"
             raise InitializationError(msg)
 
+        self._error_rate = float(self._calc_error_rate())
+
+    @classmethod
+    def init_error_rate(
+        cls,
+        error_rate: float,
+        capacity: int = 10000,
+        bucket_size: int = 4,
+        max_swaps: int = 500,
+        expansion_rate: int = 2,
+        auto_expand: bool = True,
+        hash_function: typing.Optional[SimpleHashT] = None,
+    ):
+        """Initialize a simple Cuckoo Filter based on error rate
+
+        Args:
+            error_rate (float):
+            capacity (int): The number of bins
+            bucket_size (int): The number of buckets per bin
+            max_swaps (int): The number of cuckoo swaps before stopping
+            expansion_rate (int): The rate at which to expand
+            auto_expand (bool): If the filter should automatically expand
+            hash_function (function): Hashing strategy function to use \
+            `hf(key)`
+        Returns:
+            CuckooFilter: A Cuckoo Filter object"""
+        cku = CuckooFilter(
+            capacity=capacity,
+            bucket_size=bucket_size,
+            auto_expand=auto_expand,
+            max_swaps=max_swaps,
+            expansion_rate=expansion_rate,
+            hash_function=hash_function,
+        )
+        cku._error_rate = error_rate
+        cku._fingerprint_size = cku._calc_fingerprint_size()
+        return cku
+
+    @classmethod
+    def load_error_rate(cls, error_rate: float, filepath: str, hash_function: typing.Optional[SimpleHashT] = None):
+        """Initialize a previously exported Cuckoo Filter based on error rate
+
+        Args:
+            error_rate (float):
+            filepath (str): The path to the file to load or None if no file
+            hash_function (function): Hashing strategy function to use \
+            `hf(key)`
+        Returns:
+            CuckooFilter: A Cuckoo Filter object
+        """
+        cku = CuckooFilter(filepath=filepath, hash_function=hash_function)
+        cku._error_rate = error_rate
+        cku._fingerprint_size = cku._calc_fingerprint_size()
+        return cku
+
     def __contains__(self, key: KeyT) -> bool:
         """setup the `in` keyword"""
         return self.check(key)
@@ -174,6 +230,11 @@ class CuckooFilter(object):
         """set the self expand value"""
         self.__expansion_rate = int(val)
 
+    @property
+    def error_rate(self) -> float:
+        """float: The error rate of the cuckoo filter"""
+        return self._error_rate
+
     @property
     def auto_expand(self) -> bool:
         """bool: True if the cuckoo filter will expand automatically"""
@@ -187,7 +248,7 @@ class CuckooFilter(object):
     @property
     def fingerprint_size_bits(self) -> int:
         """int: The size in bits of the fingerprint"""
-        return self.__fingerprint_size
+        return self._fingerprint_size
 
     @property
     def fingerprint_size(self) -> int:
@@ -197,7 +258,7 @@ class CuckooFilter(object):
             ValueError: If the size is not between 1 and 4
         Note:
             The size of the fingerprint must be between 1 and 4"""
-        return self.__fingerprint_size // 8
+        return math.ceil(self.fingerprint_size_bits / 8)
 
     @fingerprint_size.setter
     def fingerprint_size(self, val: int):
@@ -207,7 +268,8 @@ class CuckooFilter(object):
             msg = ("{}: fingerprint size must be between 1 and 4").format(self.__class__.__name__)
             raise ValueError(msg)
         # bytes to bits
-        self.__fingerprint_size = tmp * 8  # type: ignore
+        self._fingerprint_size = tmp * 8  # type: ignore
+        self._calc_error_rate()  # if updating fingerprint size then error rate may change
 
     def load_factor(self) -> float:
         """float: How full the Cuckoo Filter is currently"""
@@ -440,3 +502,11 @@ class CuckooFilter(object):
         else:
             msg = "The {} is currently full".format(self.__class__.__name__)
             raise CuckooFilterFullError(msg)
+
+    def _calc_error_rate(self):
+        """calculate error rate based on fingerprint size (bits) and bucket size"""
+        return float(1 / (2 ** (self.fingerprint_size_bits - (math.log2(self.bucket_size) + 1))))
+
+    def _calc_fingerprint_size(self) -> int:
+        """calculate fingerprint size (bits) based on error rate and bucket size"""
+        return int(math.ceil(math.log2(1.0 / self.error_rate) + math.log2(self.bucket_size) + 1))


Test patch:
diff --git a/tests/countingcuckoo_test.py b/tests/countingcuckoo_test.py
index 18046ea..9a9eade 100644
--- a/tests/countingcuckoo_test.py
+++ b/tests/countingcuckoo_test.py
@@ -283,5 +283,115 @@ class TestCountingCuckooFilter(unittest.TestCase):
         self.assertEqual(str(cko), msg)
 
 
+class TestCuckooFilterErrorRate(unittest.TestCase):
+    def test_c_cuckoo_filter_er_default(self):
+        """test cuckoo filter default properties"""
+        cko = CountingCuckooFilter.init_error_rate(0.00001)
+        self.assertEqual(10000, cko.capacity)
+        self.assertEqual(4, cko.bucket_size)
+        self.assertEqual(500, cko.max_swaps)
+        self.assertEqual(2, cko.expansion_rate)
+        self.assertEqual(True, cko.auto_expand)
+        self.assertEqual(3, cko.fingerprint_size)
+        self.assertEqual(20, cko.fingerprint_size_bits)
+        self.assertEqual(0.00001, cko.error_rate)
+
+    def test_c_cuckoo_filter_er_add_check(self):
+        """test adding to the cuckoo filter"""
+        cko = CountingCuckooFilter.init_error_rate(0.00001)
+        cko.add("this is a test")
+        self.assertEqual(cko.elements_added, 1)
+        cko.add("this is another test")
+        self.assertEqual(cko.elements_added, 2)
+        cko.add("this is yet another test")
+        self.assertEqual(cko.elements_added, 3)
+
+        # check
+        self.assertEqual(cko.check("this is a test"), True)
+        self.assertEqual(cko.check("this is another test"), True)
+        self.assertEqual(cko.check("this is yet another test"), True)
+        self.assertEqual(cko.check("this is not another test"), False)
+        self.assertEqual(cko.check("this is not a test"), False)
+
+        # use of `in`
+        self.assertEqual("this is a test" in cko, True)
+        self.assertEqual("this is another test" in cko, True)
+        self.assertEqual("this is yet another test" in cko, True)
+        self.assertEqual("this is not another test" in cko, False)
+        self.assertEqual("this is not a test" in cko, False)
+
+    def test_c_cuckoo_filter_er_export(self):
+        """test exporting a cuckoo filter"""
+        md5sum = "f68767bd97b21426f5d2315fb38961ad"
+        with NamedTemporaryFile(dir=os.getcwd(), suffix=".cko", delete=DELETE_TEMP_FILES) as fobj:
+            cko = CountingCuckooFilter.init_error_rate(0.00001)
+            for i in range(1000):
+                cko.add(str(i))
+            cko.export(fobj.name)
+            md5_out = calc_file_md5(fobj.name)
+            self.assertEqual(md5sum, md5_out)
+
+    def test_c_cuckoo_filter_load(self):
+        """test loading a saved cuckoo filter"""
+        md5sum = "88bc3a08bfc967f9ba60e9d57c21207f"
+        with NamedTemporaryFile(dir=os.getcwd(), suffix=".cko", delete=DELETE_TEMP_FILES) as fobj:
+            cko = CountingCuckooFilter.init_error_rate(0.00001)
+            for i in range(1000):
+                cko.add(str(i))
+                if i % 2 == 1:
+                    cko.add(str(i))
+            cko.export(fobj.name)
+            md5_out = calc_file_md5(fobj.name)
+            self.assertEqual(md5sum, md5_out)
+
+            ckf = CountingCuckooFilter.load_error_rate(error_rate=0.00001, filepath=fobj.name)
+            for i in range(1000):
+                self.assertEqual(ckf.check(str(i)), (i % 2) + 1)
+
+            self.assertEqual(10000, ckf.capacity)
+            self.assertEqual(4, ckf.bucket_size)
+            self.assertEqual(500, ckf.max_swaps)
+            self.assertEqual(2, ckf.expansion_rate)
+            self.assertEqual(True, ckf.auto_expand)
+            self.assertEqual(20, ckf.fingerprint_size_bits)
+            self.assertEqual(3, ckf.fingerprint_size)
+            self.assertEqual(0.00001, ckf.error_rate)
+            self.assertEqual(0.025, ckf.load_factor())
+
+    def test_c_cuckoo_filter_er_bytes(self):
+        """test exporting a cuckoo filter to bytes"""
+        md5sum = "f68767bd97b21426f5d2315fb38961ad"
+        cko = CountingCuckooFilter.init_error_rate(0.00001)
+        for i in range(1000):
+            cko.add(str(i))
+        md5_out = hashlib.md5(bytes(cko)).hexdigest()
+        self.assertEqual(md5sum, md5_out)
+
+    def test_c_cuckoo_filter_er_remove(self):
+        """test removing from the counting cuckoo filter"""
+        cko = CountingCuckooFilter.init_error_rate(0.00001)
+        cko.add("this is a test")
+        self.assertEqual(cko.elements_added, 1)
+        cko.add("this is another test")
+        self.assertEqual(cko.elements_added, 2)
+        cko.add("this is yet another test")
+        self.assertEqual(cko.elements_added, 3)
+        self.assertEqual(cko.unique_elements, 3)
+        cko.add("this is a test")
+        cko.add("this is a test")
+        cko.add("this is a test")
+        self.assertEqual(cko.elements_added, 6)
+        self.assertEqual(cko.unique_elements, 3)
+
+        res = cko.remove("this is another test")
+        self.assertTrue(res)
+        self.assertEqual(cko.elements_added, 5)
+        self.assertEqual(cko.unique_elements, 2)
+
+        self.assertTrue(cko.check("this is a test"))
+        self.assertFalse(cko.check("this is another test"))
+        self.assertTrue(cko.check("this is yet another test"))
+
+
 if __name__ == "__main__":
     unittest.main()
diff --git a/tests/cuckoo_test.py b/tests/cuckoo_test.py
index d662f56..7bda5e3 100644
--- a/tests/cuckoo_test.py
+++ b/tests/cuckoo_test.py
@@ -432,5 +432,88 @@ class TestCuckooFilter(unittest.TestCase):
             self.assertEqual(True, False)
 
 
+class TestCuckooFilterErrorRate(unittest.TestCase):
+    def test_cuckoo_filter_er_default(self):
+        """test cuckoo filter default properties"""
+        cko = CuckooFilter.init_error_rate(0.00001)
+        self.assertEqual(10000, cko.capacity)
+        self.assertEqual(4, cko.bucket_size)
+        self.assertEqual(500, cko.max_swaps)
+        self.assertEqual(2, cko.expansion_rate)
+        self.assertEqual(True, cko.auto_expand)
+        self.assertEqual(3, cko.fingerprint_size)
+        self.assertEqual(20, cko.fingerprint_size_bits)
+        self.assertEqual(0.00001, cko.error_rate)
+
+    def test_cuckoo_filter_er_add_check(self):
+        """test adding to the cuckoo filter"""
+        cko = CuckooFilter.init_error_rate(0.00001)
+        cko.add("this is a test")
+        self.assertEqual(cko.elements_added, 1)
+        cko.add("this is another test")
+        self.assertEqual(cko.elements_added, 2)
+        cko.add("this is yet another test")
+        self.assertEqual(cko.elements_added, 3)
+
+        # check
+        self.assertEqual(cko.check("this is a test"), True)
+        self.assertEqual(cko.check("this is another test"), True)
+        self.assertEqual(cko.check("this is yet another test"), True)
+        self.assertEqual(cko.check("this is not another test"), False)
+        self.assertEqual(cko.check("this is not a test"), False)
+
+        # use of `in`
+        self.assertEqual("this is a test" in cko, True)
+        self.assertEqual("this is another test" in cko, True)
+        self.assertEqual("this is yet another test" in cko, True)
+        self.assertEqual("this is not another test" in cko, False)
+        self.assertEqual("this is not a test" in cko, False)
+
+    def test_cuckoo_filter_er_export(self):
+        """test exporting a cuckoo filter"""
+        md5sum = "3c693508d1a3acd819310fd0c11dc906"
+        with NamedTemporaryFile(dir=os.getcwd(), suffix=".cko", delete=DELETE_TEMP_FILES) as fobj:
+            cko = CuckooFilter.init_error_rate(0.00001)
+            for i in range(1000):
+                cko.add(str(i))
+            cko.export(fobj.name)
+            md5_out = calc_file_md5(fobj.name)
+            self.assertEqual(md5sum, md5_out)
+
+    def test_cuckoo_filter_load(self):
+        """test loading a saved cuckoo filter"""
+        md5sum = "3c693508d1a3acd819310fd0c11dc906"
+        with NamedTemporaryFile(dir=os.getcwd(), suffix=".cko", delete=DELETE_TEMP_FILES) as fobj:
+            cko = CuckooFilter.init_error_rate(0.00001)
+            for i in range(1000):
+                cko.add(str(i))
+            cko.export(fobj.name)
+            md5_out = calc_file_md5(fobj.name)
+            self.assertEqual(md5sum, md5_out)
+
+            ckf = CuckooFilter.load_error_rate(error_rate=0.00001, filepath=fobj.name)
+            for i in range(1000):
+                self.assertTrue(ckf.check(str(i)))
+
+            self.assertEqual(10000, ckf.capacity)
+            self.assertEqual(4, ckf.bucket_size)
+            self.assertEqual(500, ckf.max_swaps)
+            self.assertEqual(2, ckf.expansion_rate)
+            self.assertEqual(True, ckf.auto_expand)
+            self.assertEqual(3, ckf.fingerprint_size)
+            self.assertEqual(20, ckf.fingerprint_size_bits)
+            self.assertEqual(0.00001, ckf.error_rate)
+            self.assertEqual(0.025, ckf.load_factor())
+
+    def test_cuckoo_filter_er_bytes(self):
+        """test exporting a cuckoo filter to bytes"""
+        md5sum = "3c693508d1a3acd819310fd0c11dc906"
+        cko = CuckooFilter.init_error_rate(0.00001)
+        for i in range(1000):
+            cko.add(str(i))
+        md5_out = hashlib.md5(bytes(cko)).hexdigest()
+        self.assertEqual(md5sum, md5_out)
+
+
 if __name__ == "__main__":
     unittest.main()