diff options
| author | Bernard Xiong <[email protected]> | 2013-02-21 13:11:10 +0800 |
|---|---|---|
| committer | Bernard Xiong <[email protected]> | 2013-02-21 13:11:10 +0800 |
| commit | 385f682d7bfce81ba281faaffb0a250ab94985b8 (patch) | |
| tree | 94fca413db98390d21dc18938067a7a90e470a6f /components/rtgui/utils/perfect_hash/doc/doc.html | |
| parent | c4bd0023f8da136c5788f47f9a0170a77f627be9 (diff) | |
remove RT-Thread GUI from RT-Thread temporary
Diffstat (limited to 'components/rtgui/utils/perfect_hash/doc/doc.html')
| -rw-r--r-- | components/rtgui/utils/perfect_hash/doc/doc.html | 136 |
1 files changed, 0 insertions, 136 deletions
diff --git a/components/rtgui/utils/perfect_hash/doc/doc.html b/components/rtgui/utils/perfect_hash/doc/doc.html deleted file mode 100644 index 3abb399f32..0000000000 --- a/components/rtgui/utils/perfect_hash/doc/doc.html +++ /dev/null @@ -1,136 +0,0 @@ - - -<h2>Generic Perfect Hash Generator</h2> -<p><em>Ilan Schnell, 2008</em> -</p> -<p>perfect_hash.py provides a perfect hash generator which is not language - specific. That is, the generator can output a perfect hash function for - a given set of keys in any programming language, this is achieved by - filling a given code template. -</p> - -<h3>Acknowledgments:</h3> -<p>This code is derived from A. M. Kuchling's - <a href="http://www.amk.ca/python/code/perfect-hash">Perfect Minimal Hash Generator</a>. -</p> - -<h3>Introduction:</h3> -<p>A perfect hash function of a certain set S of keys is a hash function - which maps all keys in S to different numbers. - That means that for the set S, - the hash function is collision-free, or perfect. - Further, a perfect hash function is called minimal when it maps n keys - to n <em>consecutive</em> integers, usually in the range from 0 to n-1. -</p> -<p>After coming across A. M. Kuchling's Perfect Minimal Hash Generator, - I decided to write a general tool for generating perfect hashes. - It is general in the sense that it can produce perfect hash functions - for almost any programming language. - A given code template is filled with parameters, - such that the output is code which implements the hash function. -</p> -<p>The algorithm the program uses is described in the paper - <a href="http://citeseer.ist.psu.edu/122364.html">"Optimal algorithms for minimal perfect hashing"</a>, - Z. J. Czech, G. Havas and B.S. Majewski. -</p> -<p>I tried to illustrate the algorithm and explain how it works on - <a href="http://ilan.schnell-web.net/prog/perfect-hash/algo.html">this page</a>. -</p> - -<h3>Usage:</h3> -<p>Given a set of keys which are ordinary character string, - the program returns a minimal perfect hash function. - This hash function is returned in the form of Python code by default. - Suppose we have a file with keys: -</p> -<pre><code># 'animals.txt' -Elephant -Horse -Camel -Python -Dog -Cat -</code></pre><p>The exact way this file is parsed can be specified using command line - options, for example it is possible to only read one column from a file - which contains different items in each row. - The program is invoked like this: -</p> -<pre><code># ======================================================================= -# ================= Python code for perfect hash function =============== -# ======================================================================= - -G = [0, 0, 4, 1, 0, 3, 8, 1, 6] - -S1 = [5, 0, 0, 6, 1, 0, 4, 7] -S2 = [7, 3, 6, 7, 8, 5, 7, 6] - -def hash_f(key, T): - return sum(T[i % 8] * ord(c) for i, c in enumerate(str(key))) % 9 - -def perfect_hash(key): - return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % 9 - -# ============================ Sanity check ============================= - -K = ["Elephant", "Horse", "Camel", "Python", "Dog", "Cat"] -H = [0, 1, 2, 3, 4, 5] - -assert len(K) == len(H) == 6 - -for k, h in zip(K, H): - assert perfect_hash(k) == h -</code></pre><p>The way the program works is by filling a code template with the calculated - parameters. The program can take such a template in form of a file and - fill in the calculated parameters, this allows the generation of perfect - hash function in any programming language. The hash function is kept quite - simple and does not require machine or language specific byte level operations - which might be hard to implement in the target language. - The following parameters are available in the template, and will expand to: -</p> -<table> - <tr><th>string</th><th>expands to</th></tr> - <tr><td><code>$NS</code></td><td>the length of S1 and S2</td></tr> - <tr><td><code>$S1</code></td><td>array of integers S1</td></tr> - <tr><td><code>$S2</code></td><td>array of integers S2</td></tr> - <tr><td><code>$NG</code></td><td>length of array G</td></tr> - <tr><td><code>$G</code></td><td>array of integers G</td></tr> - <tr><td><code>$NK</code></td><td>the number of keys, i.e. length of array K and H</td></tr> - <tr><td><code>$K</code></td><td>array with the quoted keys</td></tr> - <tr><td><code>$H</code></td><td>array of integer hash values</td></tr> - <tr><td><code>$$</code></td><td><code>$</code> (a literal dollar sign)</td></tr> -</table> -<p>A literal <code>$</code> is escaped as <code>$$</code>. Since the syntax for arrays is not the - same in all programming languages, some specifics can be adjusted using - command line options. - The section of the built-in template which creates the actual hash function - is: -</p> -<pre><code>G = [$G] - -S1 = [$S1] -S2 = [$S2] - -def hash_f(key, T): - return sum(T[i % $NS] * ord(c) for i, c in enumerate(str(key))) % $NG - -def perfect_hash(key): - return (G[hash_f(key, S1)] + G[hash_f(key, S2)]) % $NG -</code></pre><p>Using code templates, makes this program very flexible. The package comes - with several complete examples for C and C++. There are many choices one - faces when implementing a static hash table: do the parameter lists go into - a separate header file, should the API for the table only contain the hash - values, but not the objects being mapped, and so on. - All these various choices are possible because of the template is simply - filled with the parameters, no matter what else is inside the template. -</p> -<p>Another possible use the program is as a python module. The functions and - classes in <code>perfect_hash.py</code> are documented and have clean interfaces. - The folder <code>example-Python</code> has examples which shows how the module - can be used directly in this way. -</p> - -<h3>Requirement:</h3> -<p>Python 2.5 -</p> - - |
