Changeset 35025 in project


Ignore:
Timestamp:
01/15/18 18:11:45 (7 months ago)
Author:
kon
Message:

rel 1.2.0

File:
1 edited

Legend:

Unmodified
Added
Removed
  • wiki/eggref/4/bloom-filter

    r34735 r35025  
    1616=== make-bloom-filter
    1717
    18 <procedure>(make-bloom-filter M MESSAGE-DIGEST-PRIMITIVES [K]) => bloom-filter</procedure>
    19 
    20 Returns a bloom-filter object with {{M}} bits of discrimination and a set of hash
    21 functions built from the supplied {{MESSAGE-DIGEST-PRIMITIVES}}, a list
    22 of {{message-digest-primitive}} objects.
    23 
    24 The number of hashes, {{K}}, is not necessarily the same as the number
    25 of message-digests. A hash (here) is defined as an unsigned 32 bit
    26 integer. Most message-digests return more 32 bits of hash. The actual
    27 length of the hash is divided into 32 bit blocks to get the individual
    28 hashes.
    29 
    30 The argument {{K}} will restrict the actual number of hashes to the
    31 "first" ''K'', no matter how many more the supplied message-digests
    32 create. First in the order of {{MESSAGE-DIGEST-PRIMITIVES}}.
    33 
    34 <procedure>(make-bloom-filter P N MESSAGE-DIGEST-PRIMITIVES) => bloom-filter</procedure>
     18<procedure>(make-bloom-filter M MDPS [K]) --> bloom-filter</procedure>
     19
     20Returns a bloom-filter object with {{M}} bits of discrimination and a set of
     21hash functions built from the supplied {{MDPS}}, a {{(list-of
     22message-digest-primitive)}} objects.
     23
     24The number of hashes, {{K}}, is not necessarily the same as the number of
     25message-digests. A hash (here) is defined as an unsigned 32 bit integer. Most
     26message-digests return more 32 bits of hash. The actual length of the hash is
     27divided into 32 bit blocks to get the individual hashes.
     28
     29The argument {{K}} will restrict the actual number of hashes to the "first"
     30''K'', no matter how many more the supplied message-digests create. First in
     31the order of {{MDPS}}.
     32
     33<procedure>(make-bloom-filter P N MDPS) --> bloom-filter</procedure>
    3534
    3635Returns a bloom-filter object with {{M}} and {{K}} values chosen for the
     
    4039make-bloom-filter.
    4140
     41=== bloom-filter-set!
     42
     43<procedure>(bloom-filter-set! BLOOM-FILTER OBJECT)</procedure>
     44
     45Add the specified {{OBJECT}} to the indicated {{BLOOM-FILTER}}.
     46
     47=== bloom-filter-exists?
     48
     49<procedure>(bloom-filter-exists? BLOOM-FILTER OBJECT) --> boolean</procedure>
     50
     51Is the specified {{OBJECT}} in the indicated {{BLOOM-FILTER}}.
     52
     53=== bloom-filter?
     54=== check-bloom-filter
     55=== error-bloom-filter
     56
     57<procedure>(bloom-filter? OBJ) --> boolean</procedure>
     58<procedure>(check-bloom-filter LOC OBJ [NAM]) --> bloom-filter</procedure>
     59<procedure>(error-bloom-filter LOC OBJ [NAM])</procedure>
     60
     61=== bloom-filter-algorithms
     62
     63<procedure>(bloom-filter-algorithms BLOOM-FILTER) --> (list-of message-digest-primitive)</procedure>
     64
     65The mdps used for the filter.
     66
    4267=== bloom-filter-n
    4368
    44 <procedure>(bloom-filter-n BLOOM-FILTER) => fixnum</procedure>
     69<procedure>(bloom-filter-n BLOOM-FILTER) --> fixnum</procedure>
    4570
    4671The current population - the number of objects added to the filter.
     
    5075=== bloom-filter-m
    5176
    52 <procedure>(bloom-filter-m BLOOM-FILTER) => fixnum</procedure>
     77<procedure>(bloom-filter-m BLOOM-FILTER) --> fixnum</procedure>
    5378
    5479The number of bits of discrimination.
     
    5681=== bloom-filter-k
    5782
    58 <procedure>(bloom-filter-k BLOOM-FILTER) => fixnum</procedure>
     83<procedure>(bloom-filter-k BLOOM-FILTER) --> fixnum</procedure>
    5984
    6085The number of hashes. (See above.)
     
    6287=== bloom-filter-p-false-positive
    6388
    64 <procedure>(bloom-filter-p-false-positive BLOOM-FILTER [N]) => number</procedure>
     89<procedure>(bloom-filter-p-false-positive BLOOM-FILTER [N]) --> number</procedure>
    6590
    6691The probability of a false-positive for the population capacity {{N}},
    6792default is the current population, {{bloom-filter-n}}.
    6893
    69 === bloom-filter-set!
    70 
    71 <procedure>(bloom-filter-set! BLOOM-FILTER OBJECT)</procedure>
    72 
    73 Add the specified {{OBJECT}} to the indicated {{BLOOM-FILTER}}.
    74 
    75 === bloom-filter-exists?
    76 
    77 <procedure>(bloom-filter-exists? BLOOM-FILTER OBJECT) => boolean</procedure>
    78 
    79 Is the specified {{OBJECT}} in the indicated {{BLOOM-FILTER}}.
    80 
    8194=== actual-k
    8295
    83 <procedure>(actual-k MESSAGE-DIGEST-PRIMITIVES) => fixnum</procedure>
    84 
    85 Calculates the actual number of hashes for the
    86 {{MESSAGE-DIGEST-PRIMITIVES}}.
     96<procedure>(actual-k MDPS) --> fixnum</procedure>
     97
     98Calculates the actual number of hashes for the {{MDPS}}.
    8799
    88100=== optimum-size
    89101
    90 <procedure>(optimum-size P N) => (fixnum fixnum)</procedure>
     102<procedure>(optimum-size P N) --> fixnum fixnum</procedure>
    91103
    92104Returns 2 values, an optimal {{M}}, bits of discrimination, and {{K}},
     
    96108=== desired-m
    97109
    98 <procedure>(desired-m P N [K]) => (fixnum fixnum number)</procedure>
     110<procedure>(desired-m P N [K]) --> fixnum fixnum number</procedure>
    99111
    100112Calculates a near-optimal number of bits of discrimination to meet the
     
    109121=== optimum-k
    110122
    111 <procedure>(optimum-k N M) => fixnum</procedure>
     123<procedure>(optimum-k N M) --> fixnum</procedure>
    112124
    113125Optimal count of hashes for the given population size {{N}} and {{M}}
     
    116128=== optimum-m
    117129
    118 <procedure>(optimum-m K N) => fixnum</procedure>
     130<procedure>(optimum-m K N) --> fixnum</procedure>
    119131
    120132Optimal count of bits of discrimination for the given population size
     
    123135=== p-false-positive
    124136
    125 <procedure>(p-false-positive K N M) => number</procedure>
     137<procedure>(p-false-positive K N M) --> number</procedure>
    126138
    127139What is the probability of false positives for the population size {{N}}
     
    130142=== p-random-one-bit
    131143
    132 <procedure>(p-random-one-bit K N M) => number</procedure>
     144<procedure>(p-random-one-bit K N M) --> number</procedure>
    133145
    134146Calculates the probablility of a random set bit for the given number of
     
    166178== Version history
    167179
     180; 1.2.0 : Add missing API.
    168181; 1.1.8 : Pick up the scraps.
    169182; 1.1.7 : Re-flow.
     
    180193== License
    181194
    182 Copyright (C) 2010-2017 Kon Lovett.  All rights reserved.
     195Copyright (C) 2010-2018 Kon Lovett.  All rights reserved.
    183196
    184197Permission is hereby granted, free of charge, to any person obtaining a
Note: See TracChangeset for help on using the changeset viewer.