cmph/__init__.py
def generate_hash(data, algorithm='chd_ph', hash_fns=(), chd_keys_per_bin=1,
                  chd_load_factor=None, fch_bits_per_key=None,
                  num_graph_vertices=None, brz_memory_size=8,
                  brz_temp_dir=None, brz_max_keys_per_bucket=128,
                  bdz_precomputed_rank=7, chd_avg_keys_per_bucket=4):
    """
    Generates a new Minimal Perfect Hash (MPH)

    Parameters
    ----------
    data : list, array-like, file-like
        The input that is used to generate the minimal perfect hash.

        Be aware, in most cases the input is expected to be distinct, and
        many of the algorithms benefit from the input being sorted.

    algorithm : string, optional
        {chd_ph (default), chd, bmz, bmz8, chm, brz, fch, bdz, bdz_ph}
        The algorithm to use in generating MPH's, choice of:

        chd / chd_ph - Compress Hash and Displace (default)
            (http://cmph.sourceforge.net/chd.html)
            - It is the fastest algorithm to build PHFs and MPHFs in linear
            time.
            - It generates the most compact PHFs and MPHFs we know of.
            - It can generate PHFs with a load factor up to 99 %.
            - It can be used to generate t-perfect hash functions. A
            t-perfect hash function allows at most t collisions in a given
            bin. It is a well-known fact that modern memories are
            organized as blocks which constitute transfer unit. Example of
            such blocks are cache lines for internal memory or sectors for
            hard disks. Thus, it can be very useful for devices that
            carry out I/O operations in blocks.
            - It is a two level scheme. It uses a first level hash function
            to split the key set in buckets of average size determined by
            a parameter b in the range [1,32]. In the second level it uses
            displacement values to resolve the collisions that have given
            rise to the buckets.
            - It can generate MPHFs that can be stored in approximately 2.07
            bits per key.
            - For a load factor equal to the maximum one that is achieved by
            the BDZ algorithm (81 %), the resulting PHFs are stored in
            approximately 1.40 bits per key.

        bdz - BDZ / BPZ algorithm
            (http://cmph.sourceforge.net/bdz.html)
            - It is very simple and efficient. It outperforms all others
            except CHD.
            - It constructs both PHFs and MPHFs in linear time.
            - The maximum load factor one can achieve for a PHF is 1/1.23.
            - It is based on acyclic random 3-graphs. A 3-graph is a
            generalization of a graph where each edge connects 3 vertices
            instead of only 2.
            - The resulting MPHFs are not order preserving.
            - The resulting MPHFs can be stored in only (2 + x)cn bits,
            where c should be larger than or equal to 1.23 and x is a
            constant larger than 0 (actually, x = 1/b and b is a parameter
            that should be larger than 2). For c = 1.23 and b = 8, the
            resulting functions are stored in approximately 2.6 bits per
            key.
            - For its maximum load factor (81 %), the resulting PHFs are
            stored in approximately 1.95 bits per key.

        bmz - Botelho, Menoti and Ziviani algorithm:
            (http://cmph.sourceforge.net/bdz.html)
            - Constructs MPHFs in linear time.
            - It is based on cyclic random graphs. This makes it faster than
            the CHM algorithm.
            - The resulting MPHFs are not order preserving.
            - The resulting MPHFs are more compact than the ones generated by
            the CHM algorithm and can be stored in 4cn bytes, where c is in
            the range [0.93,1.15].

        brz - BRZ algorithm:
            (http://cmph.sourceforge.net/brz.html)
            - A very fast external memory based algorithm for constructing
            minimal perfect hash functions for sets in the order of
            billions of keys.
            - It works in linear time.
            - The resulting MPHFs are not order preserving.
            - The resulting MPHFs can be stored using less than 8.0 bits per
            key.

        chm - Czech, Havas and Majewski algorithm:
            (http://cmph.sourceforge.net/chm.html)
            - Construct minimal MPHFs in linear time.
            - It is based on acyclic random graphs
            - The resulting MPHFs are order preserving.
            - The resulting MPHFs are stored in 4cn bytes, where c is greater
            than 2.

        fch - Fox, Chen and Heath algorithm:
            (http://cmph.sourceforge.net/chm.html)
            - Construct minimal perfect hash functions that require less than
            4 bits per key to be stored.
            - The resulting MPHFs are very compact and very efficient at
            evaluation time
            - The algorithm is only efficient for small sets.
            - It is used as internal algorithm in the BRZ algorithm to
            efficiently solve larger problems and even so to generate MPHFs
            that require approximately 4.1 bits per key to be stored. For
            that, you just need to set the parameters -a to brz and -c to a
            value larger than or equal to 2.6.

    hash_fns : list {jenkins (default), count} optional
        Internal hash functions to use inside MPH generation functions,
        can be multiple fns as a list.

    chd_keys_per_bin : int [1 to 128], optional
        Set the number of keys per bin for a t-perfect hashing function. A
        t-perfect hash function allows at most t collisions in a given bin.
        This parameter applies only to the `chd` and `chd_ph` algorithms.
        Its value should be an integer in the range [1, 128].

        Default is 1

    chd_load_factor : float, optional
        The load factor used in the `chd_ph` algorithm

    fch_bits_per_key : int, optional
        The number of bits per key required in the FCH algorithm

    num_graph_vertices : int, optional
        The number of vertices in the graph for the algorithms BMZ and CHM

    brz_memory_size : int (default 8), optional
        Main memory availability (in MB) used in BRZ algorithm

        Default is 8Mb

    brz_temp_dir : string, optional
        Temporary directory used in BRZ algorithm

    brz_max_keys_per_bucket : int [64 to 175] (default 128), optional
        Used to make the maximal number of keys in a bucket lower than 256.
        In this case its value should be an integer in the range [64,175].
        Default is 128.

    bdz_precomputed_rank : int [3 to 10] (default 7), optional
        For BDZ it is used to determine the size of some precomputed rank
        information and its value should be an integer in the range [3,10].

        Default is 7.

        The larger is this value, the more compact are the resulting
        functions and the slower are them at evaluation time.

    chd_avg_keys_per_bucket : int [1 to 32] (default 4), optional
        For CHD and CHD_PH it is used to set the average number of keys per
        bucket and its value should be an integer in the range [1,32].

        Default is 4.

        The larger is this value, the slower is the construction of the
        functions.

    Returns
    -------
    MPH
        A wrapper object that represents a minimal perfect hash in memory

    Raises
    ------
    ValueError
        If arguments presented are incomplete, or incompatable
    RuntimeError
        If the MPH generation fails
    """

    cfg = _cfg(algorithm, hash_fns, chd_keys_per_bin, chd_load_factor,
               fch_bits_per_key, num_graph_vertices, brz_memory_size,
               brz_temp_dir, brz_max_keys_per_bucket, bdz_precomputed_rank,
               chd_avg_keys_per_bucket)

    with create_adapter(_cmph, ffi, data) as source:
        with _create_config(source, cfg) as config:
            _mph = _cmph.cmph_new(config)
            if not _mph:
                raise RuntimeError("MPH generation failed")
            return MPH(_mph)
def generate_hash(data, algorithm='chd_ph', hash_fns=(), chd_keys_per_bin=1,
                  chd_load_factor=None, fch_bits_per_key=None,
                  num_graph_vertices=None, brz_memory_size=8,
                  brz_temp_dir=None, brz_max_keys_per_bucket=128,
                  bdz_precomputed_rank=7, chd_avg_keys_per_bucket=4):
    """
    Generates a new Minimal Perfect Hash (MPH)

    Parameters
    ----------
    data : list, array-like, file-like
        The input that is used to generate the minimal perfect hash.

        Be aware, in most cases the input is expected to be distinct, and
        many of the algorithms benefit from the input being sorted.

    algorithm : string, optional
        {chd_ph (default), chd, bmz, bmz8, chm, brz, fch, bdz, bdz_ph}
        The algorithm to use in generating MPH's, choice of:

        chd / chd_ph - Compress Hash and Displace (default)
            (http://cmph.sourceforge.net/chd.html)
            - It is the fastest algorithm to build PHFs and MPHFs in linear
            time.
            - It generates the most compact PHFs and MPHFs we know of.
            - It can generate PHFs with a load factor up to 99 %.
            - It can be used to generate t-perfect hash functions. A
            t-perfect hash function allows at most t collisions in a given
            bin. It is a well-known fact that modern memories are
            organized as blocks which constitute transfer unit. Example of
            such blocks are cache lines for internal memory or sectors for
            hard disks. Thus, it can be very useful for devices that
            carry out I/O operations in blocks.
            - It is a two level scheme. It uses a first level hash function
            to split the key set in buckets of average size determined by
            a parameter b in the range [1,32]. In the second level it uses
            displacement values to resolve the collisions that have given
            rise to the buckets.
            - It can generate MPHFs that can be stored in approximately 2.07
            bits per key.
            - For a load factor equal to the maximum one that is achieved by
            the BDZ algorithm (81 %), the resulting PHFs are stored in
            approximately 1.40 bits per key.

        bdz - BDZ / BPZ algorithm
            (http://cmph.sourceforge.net/bdz.html)
            - It is very simple and efficient. It outperforms all others
            except CHD.
            - It constructs both PHFs and MPHFs in linear time.
            - The maximum load factor one can achieve for a PHF is 1/1.23.
            - It is based on acyclic random 3-graphs. A 3-graph is a
            generalization of a graph where each edge connects 3 vertices
            instead of only 2.
            - The resulting MPHFs are not order preserving.
            - The resulting MPHFs can be stored in only (2 + x)cn bits,
            where c should be larger than or equal to 1.23 and x is a
            constant larger than 0 (actually, x = 1/b and b is a parameter
            that should be larger than 2). For c = 1.23 and b = 8, the
            resulting functions are stored in approximately 2.6 bits per
            key.
            - For its maximum load factor (81 %), the resulting PHFs are
            stored in approximately 1.95 bits per key.

        bmz - Botelho, Menoti and Ziviani algorithm:
            (http://cmph.sourceforge.net/bdz.html)
            - Constructs MPHFs in linear time.
            - It is based on cyclic random graphs. This makes it faster than
            the CHM algorithm.
            - The resulting MPHFs are not order preserving.
            - The resulting MPHFs are more compact than the ones generated by
            the CHM algorithm and can be stored in 4cn bytes, where c is in
            the range [0.93,1.15].

        brz - BRZ algorithm:
            (http://cmph.sourceforge.net/brz.html)
            - A very fast external memory based algorithm for constructing
            minimal perfect hash functions for sets in the order of
            billions of keys.
            - It works in linear time.
            - The resulting MPHFs are not order preserving.
            - The resulting MPHFs can be stored using less than 8.0 bits per
            key.

        chm - Czech, Havas and Majewski algorithm:
            (http://cmph.sourceforge.net/chm.html)
            - Construct minimal MPHFs in linear time.
            - It is based on acyclic random graphs
            - The resulting MPHFs are order preserving.
            - The resulting MPHFs are stored in 4cn bytes, where c is greater
            than 2.

        fch - Fox, Chen and Heath algorithm:
            (http://cmph.sourceforge.net/chm.html)
            - Construct minimal perfect hash functions that require less than
            4 bits per key to be stored.
            - The resulting MPHFs are very compact and very efficient at
            evaluation time
            - The algorithm is only efficient for small sets.
            - It is used as internal algorithm in the BRZ algorithm to
            efficiently solve larger problems and even so to generate MPHFs
            that require approximately 4.1 bits per key to be stored. For
            that, you just need to set the parameters -a to brz and -c to a
            value larger than or equal to 2.6.

    hash_fns : list {jenkins (default), count} optional
        Internal hash functions to use inside MPH generation functions,
        can be multiple fns as a list.

    chd_keys_per_bin : int [1 to 128], optional
        Set the number of keys per bin for a t-perfect hashing function. A
        t-perfect hash function allows at most t collisions in a given bin.
        This parameter applies only to the `chd` and `chd_ph` algorithms.
        Its value should be an integer in the range [1, 128].

        Default is 1

    chd_load_factor : float, optional
        The load factor used in the `chd_ph` algorithm

    fch_bits_per_key : int, optional
        The number of bits per key required in the FCH algorithm

    num_graph_vertices : int, optional
        The number of vertices in the graph for the algorithms BMZ and CHM

    brz_memory_size : int (default 8), optional
        Main memory availability (in MB) used in BRZ algorithm

        Default is 8Mb

    brz_temp_dir : string, optional
        Temporary directory used in BRZ algorithm

    brz_max_keys_per_bucket : int [64 to 175] (default 128), optional
        Used to make the maximal number of keys in a bucket lower than 256.
        In this case its value should be an integer in the range [64,175].
        Default is 128.

    bdz_precomputed_rank : int [3 to 10] (default 7), optional
        For BDZ it is used to determine the size of some precomputed rank
        information and its value should be an integer in the range [3,10].

        Default is 7.

        The larger is this value, the more compact are the resulting
        functions and the slower are them at evaluation time.

    chd_avg_keys_per_bucket : int [1 to 32] (default 4), optional
        For CHD and CHD_PH it is used to set the average number of keys per
        bucket and its value should be an integer in the range [1,32].

        Default is 4.

        The larger is this value, the slower is the construction of the
        functions.

    Returns
    -------
    MPH
        A wrapper object that represents a minimal perfect hash in memory

    Raises
    ------
    ValueError
        If arguments presented are incomplete, or incompatable
    RuntimeError
        If the MPH generation fails
    """

    cfg = _cfg(algorithm, hash_fns, chd_keys_per_bin, chd_load_factor,
               fch_bits_per_key, num_graph_vertices, brz_memory_size,
               brz_temp_dir, brz_max_keys_per_bucket, bdz_precomputed_rank,
               chd_avg_keys_per_bucket)

    with create_adapter(_cmph, ffi, data) as source:
        with _create_config(source, cfg) as config:
            _mph = _cmph.cmph_new(config)
            if not _mph:
                raise RuntimeError("MPH generation failed")
            return MPH(_mph)
Generates a new Minimal Perfect Hash (MPH)

    Parameters
    ----------
    data : list, array-like, file-like
        The input that is used to generate the minimal perfect hash.

        Be aware, in most cases the input is expected to be distinct, and
        many of the algorithms benefit from the input being sorted.

    algorithm : string, optional
        {chd_ph (default), chd, bmz, bmz8, chm, brz, fch, bdz, bdz_ph}
        The algorithm to use in generating MPH's, choice of:

        chd / chd_ph - Compress Hash and Displace (default)
            (http://cmph.sourceforge.net/chd.html)
            - It is the fastest algorithm to build PHFs and MPHFs in linear
            time.
            - It generates the most compact PHFs and MPHFs we know of.
            - It can generate PHFs with a load factor up to 99 %.
            - It can be used to generate t-perfect hash functions. A
            t-perfect hash function allows at most t collisions in a given
            bin. It is a well-known fact that modern memories are
            organized as blocks which constitute transfer unit. Example of
            such blocks are cache lines for internal memory or sectors for
            hard disks. Thus, it can be very useful for devices that
            carry out I/O operations in blocks.
            - It is a two level scheme. It uses a first level hash function
            to split the key set in buckets of average size determined by
            a parameter b in the range [1,32]. In the second level it uses
            displacement values to resolve the collisions that have given
            rise to the buckets.
            - It can generate MPHFs that can be stored in approximately 2.07
            bits per key.
            - For a load factor equal to the maximum one that is achieved by
            the BDZ algorithm (81 %), the resulting PHFs are stored in
            approximately 1.40 bits per key.

        bdz - BDZ / BPZ algorithm
            (http://cmph.sourceforge.net/bdz.html)
            - It is very simple and efficient. It outperforms all others
            except CHD.
            - It constructs both PHFs and MPHFs in linear time.
            - The maximum load factor one can achieve for a PHF is 1/1.23.
            - It is based on acyclic random 3-graphs. A 3-graph is a
            generalization of a graph where each edge connects 3 vertices
            instead of only 2.
            - The resulting MPHFs are not order preserving.
            - The resulting MPHFs can be stored in only (2 + x)cn bits,
            where c should be larger than or equal to 1.23 and x is a
            constant larger than 0 (actually, x = 1/b and b is a parameter
            that should be larger than 2). For c = 1.23 and b = 8, the
            resulting functions are stored in approximately 2.6 bits per
            key.
            - For its maximum load factor (81 %), the resulting PHFs are
            stored in approximately 1.95 bits per key.

        bmz - Botelho, Menoti and Ziviani algorithm:
            (http://cmph.sourceforge.net/bdz.html)
            - Constructs MPHFs in linear time.
            - It is based on cyclic random graphs. This makes it faster than
            the CHM algorithm.
            - The resulting MPHFs are not order preserving.
            - The resulting MPHFs are more compact than the ones generated by
            the CHM algorithm and can be stored in 4cn bytes, where c is in
            the range [0.93,1.15].

        brz - BRZ algorithm:
            (http://cmph.sourceforge.net/brz.html)
            - A very fast external memory based algorithm for constructing
            minimal perfect hash functions for sets in the order of
            billions of keys.
            - It works in linear time.
            - The resulting MPHFs are not order preserving.
            - The resulting MPHFs can be stored using less than 8.0 bits per
            key.

        chm - Czech, Havas and Majewski algorithm:
            (http://cmph.sourceforge.net/chm.html)
            - Construct minimal MPHFs in linear time.
            - It is based on acyclic random graphs
            - The resulting MPHFs are order preserving.
            - The resulting MPHFs are stored in 4cn bytes, where c is greater
            than 2.

        fch - Fox, Chen and Heath algorithm:
            (http://cmph.sourceforge.net/chm.html)
            - Construct minimal perfect hash functions that require less than
            4 bits per key to be stored.
            - The resulting MPHFs are very compact and very efficient at
            evaluation time
            - The algorithm is only efficient for small sets.
            - It is used as internal algorithm in the BRZ algorithm to
            efficiently solve larger problems and even so to generate MPHFs
            that require approximately 4.1 bits per key to be stored. For
            that, you just need to set the parameters -a to brz and -c to a
            value larger than or equal to 2.6.

    hash_fns : list {jenkins (default), count} optional
        Internal hash functions to use inside MPH generation functions,
        can be multiple fns as a list.

    chd_keys_per_bin : int [1 to 128], optional
        Set the number of keys per bin for a t-perfect hashing function. A
        t-perfect hash function allows at most t collisions in a given bin.
        This parameter applies only to the `chd` and `chd_ph` algorithms.
        Its value should be an integer in the range [1, 128].

        Default is 1

    chd_load_factor : float, optional
        The load factor used in the `chd_ph` algorithm

    fch_bits_per_key : int, optional
        The number of bits per key required in the FCH algorithm

    num_graph_vertices : int, optional
        The number of vertices in the graph for the algorithms BMZ and CHM

    brz_memory_size : int (default 8), optional
        Main memory availability (in MB) used in BRZ algorithm

        Default is 8Mb

    brz_temp_dir : string, optional
        Temporary directory used in BRZ algorithm

    brz_max_keys_per_bucket : int [64 to 175] (default 128), optional
        Used to make the maximal number of keys in a bucket lower than 256.
        In this case its value should be an integer in the range [64,175].
        Default is 128.

    bdz_precomputed_rank : int [3 to 10] (default 7), optional
        For BDZ it is used to determine the size of some precomputed rank
        information and its value should be an integer in the range [3,10].

        Default is 7.

        The larger is this value, the more compact are the resulting
        functions and the slower are them at evaluation time.

    chd_avg_keys_per_bucket : int [1 to 32] (default 4), optional
        For CHD and CHD_PH it is used to set the average number of keys per
        bucket and its value should be an integer in the range [1,32].

        Default is 4.

        The larger is this value, the slower is the construction of the
        functions.

    Returns
    -------
    MPH
        A wrapper object that represents a minimal perfect hash in memory

    Raises
    ------
    ValueError
        If arguments presented are incomplete, or incompatable
    RuntimeError
        If the MPH generation fails