CMPH——C Minimal Perfect Hashing Library【译】

￡神魔★判官ぃ 2022-03-28 07:14 139阅读 0赞

CMPH - C Minimal Perfect Hashing Library

C最小完美哈希库

翻译：ZH奶酪

博客地址：[http://www.cnblogs.com/CheeseZH][http_www.cnblogs.com_CheeseZH]

动机：

一个完美的hash函数可以讲一个包含n个键的静态集合映射到m个整数而不出现冲突，此时m大于等于n。如果m等于n，这个函数就可以称作最小；

[最小完美哈希函数][Link 1]被广泛的应用在高效存储以及从静态集中快速检索条目，比如自然语言中的词语，程序或者交互系统中的预定义词语，网络搜索引擎中的URLs，或者数据挖掘技术中的条目集合。因此，在信息检索系统、数据库系统、语言翻译系统、电商系统、编译器、操作系统以及其他系统中都有最小完美哈希函数的应用。

目前，由于算法的限制，最小完美哈希函数的用途局限于被hash的键集较小的情况。但是在许多用例中，处理数目庞大的键集是很有必要的。所以，这个项目为免费软件社区提供了一个API，这个API可以处理数十亿的键。

在最小完美哈希函数的各种用途中，最有意义的应用可能是作为数据库的索引结构了。数据库的索引结构中最著名的数据结构应该是B+树。事实上，B+树对那些需要频繁动态插入、删除记录的应用非常适合。但是，对于那些需要不定时修改、有大量数据需要查询的应用，B+树并不是最好的选择，因为部署这个数据结构非常复杂，而且在前沿数据库应用必须的大量键集合上表现并不是很好。

例如，在信息检索领域，处理大量集合是很常见的。仅仅处理一个集合中web页面的id都可能是一个很有挑战的任务。当主存装不下工作集合的web页面的urls时，传统数据库并不能很好的处理，但是最小完美哈希函数可以借助硬盘轻松的处理上一条信息。

由于有许多最小完美哈希函数的应用，实现一个能够时空高效构建这个函数的算法是很重要的。在开源软件世界缺少类似的库已经成了建立CMPH库的重要驱动（gperf有 点不同，因为它设想为较小的键集合建立一个快速完美哈希函数，CMPH库设想为较大的键集合建立最小完美哈希函数）。CMPH库是可移植的LGPLed库，可以用来生成和操作非常高效的最小完美哈希函数。

描述

CMPH库将最新的高效算法封装在一个简单易用、高质量、快速的API中。这个库被设计用来处理主存无法容纳的大量信息。它已经成功的用在了构建用于处理大于1亿信息集合的最小完美哈希函数，并且我们打算将这个数值提升到10亿。尽管还没有类似的库，我们可以提出一些CMPH库的特性：.

· 快速

· 对于比较消耗内存的文档能够在空间上很高效处理

· 多种非常好的算法模型可供选择

· 可以通过适配器模式处理in-disk键集合

· 序列化哈希函数

· 可移植C代码（GNU/Linux、WIN32、OpenBSD、Solaris）

· 面向对象实现

· 易于扩展

· 发行的完好封装的 API兼容二进制(binary compatibility) 。

· 开源

支持的算法：（PHF：完美哈希函数，MPHF：最小完美哈希函数）

· [CHD Algorithm][]:

o 它是线性时间内构建PHFs和MPHFs的最快的算法；

o 它可以生成了我们熟知的最简洁的PHFs和MPHFs；

o 它生成PHFs的负载系数高达99%；

o 它可以用来生成t-完美哈希函数；

一个t-完美哈希函数允许一个存储空间上至多发生t次冲突。众所周知，当今的存储都是以块为单位作为组织转移单元的。 比如内存中的cache线或者硬盘中的扇区都是这种存储块。因此，实现在这种块中的IO操作是非常有用的。

o 它是一个二级设计形式。它使用第一级哈希函数通过参数b\[1,32\]把键集进行均分到buckets中。在第二级，使用转移值来解决在buckets中出现的冲突问题。

o 它生成的MPHFs可以用大约2.07个比特来存储每个key。

o 最大装填因子和BDZ algorithm (81 %)一样, 作为结果的PHFs 大约需要1.40 bits 来存储每个键。

· [BDZ Algorithm][]:

o 它非常简单有效，在下边的各方面表现都很优秀。

o 它在线性时间内构建PHFs和MPHFs。

o 对于PHF最大装填因子可以达到1/1.23。

o 它基于acyclic random 3-graphs. 一个 3-graph 是一个图的派生，每条边连接3个点而不是2个点。

o 生成的MPHFs是不保序的。

o 生成的MPHFs的存储需要(2+x)cn比特，其中c应该大于等于1.23，x是一个大于0的常数（实际上，x = 1/b ，b是一个大于2的参数）。例如c = 1.23 ，b = 8，那么最后每个键大约需要2.6个比特来存储。

o 它最大的装填因子 (81 %), 作为结果的PHFs 大约需要1.95 bits 来存储每个键。

· [BMZ Algorithm][]:

o 构建MPHFs只需要线性时间。

o 它基于cyclic random graphs. 这使它比CHM algorithm更快.

o 生成的MPHFs是不保序的。

o 生成的MPHFs比CHM algorithm 生成的更加紧凑，只需要4cn bytes, c的范围\[0.93,1.15\].

· [BRZ Algorithm][]:

o 一个基于扩展存储的快速算法，构建的MPHFs可以用来处理大约百万数量的键集。

o 工作时间是线性的。

o 作为结果的MPHFs是不保序的。

o 作为结果的 MPHFs需要不到 8.0 bits来存储每个键。

· [CHM Algorithm][]:

o 在线性时间内构建MPHFs。

o 基于acyclic random graphs。

o 作为结果的MPHFs是不保序的。

o 作为结果的MPHFs 存储在4cn bytes空间中, c大于2.

· [FCH Algorithm][]:

o 构建的 MPHFs 需要不到 4 bits 来保存每个键。

o 评估时，作为结果的MPHFs非常简洁、有效。

o 该算法只对较小规模键集有效。

o 它被用作BRZ算法的内置算法用来高效解决更大的问题，尽管如此，它生成的MPHFs需要大约4.1bits来存储每个键。为了达到这个要求，你只需要设置参数 -a为brz，参数-c为一个大于等于2.6的值。

版本更新内容：略

例子：

使用cmph非常简单，请看：

#include <cmph.h>
    #include <string.h>
    // Create minimal perfect hash function from in-memory vector
    int main(int argc, char **argv)
    { 
        
        // Creating a filled vector
        unsigned int i = 0;
        const char *vector[] = {
         "aaaaaaaaaa", "bbbbbbbbbb", "cccccccccc", "dddddddddd", "eeeeeeeeee", 
            "ffffffffff", "gggggggggg", "hhhhhhhhhh", "iiiiiiiiii", "jjjjjjjjjj"};
        unsigned int nkeys = 10;
        FILE* mphf_fd = fopen("temp.mph", "w");
        // Source of keys
        cmph_io_adapter_t *source = cmph_io_vector_adapter((char **)vector, nkeys);
        
        //Create minimal perfect hash function using the brz algorithm.
        cmph_config_t *config = cmph_config_new(source);
        cmph_config_set_algo(config, CMPH_BRZ);
        cmph_config_set_mphf_fd(config, mphf_fd);
        cmph_t *hash = cmph_new(config);
        cmph_config_destroy(config);
        cmph_dump(hash, mphf_fd); 
        cmph_destroy(hash);    
        fclose(mphf_fd);
        
        //Find key
        mphf_fd = fopen("temp.mph", "r");
        hash = cmph_load(mphf_fd);
        while (i < nkeys) {
            const char *key = vector[i];
            unsigned int id = cmph_search(hash, key, (cmph_uint32)strlen(key));
            fprintf(stderr, "key:%s -- hash:%u\n", key, id);
            i++;
        }
        
        //Destroy hash
        cmph_destroy(hash);
        cmph_io_vector_adapter_destroy(source);   
        fclose(mphf_fd);
        return 0;
    }

下载 [vector\_adapter\_ex1.c][vector_adapter_ex1.c]. 这个例子不能再0.6版本下工作。

#include <cmph.h>
    #include <stdio.h>
    #include <string.h>
     // Create minimal perfect hash function from in-disk keys using BDZ algorithm
    int main(int argc, char **argv)
    {   
         //Open file with newline separated list of keys
        FILE * keys_fd = fopen("keys.txt", "r");
        cmph_t *hash = NULL;
        if (keys_fd == NULL) 
        {
          fprintf(stderr, "File \"keys.txt\" not found\n");
          exit(1);
        }    
        // Source of keys
        cmph_io_adapter_t *source = cmph_io_nlfile_adapter(keys_fd);
    
        cmph_config_t *config = cmph_config_new(source);
        cmph_config_set_algo(config, CMPH_BDZ);
        hash = cmph_new(config);
        cmph_config_destroy(config);
       
        //Find key
        const char *key = "jjjjjjjjjj";
        unsigned int id = cmph_search(hash, key, (cmph_uint32)strlen(key));
        fprintf(stderr, "Id:%u\n", id);
        //Destroy hash
        cmph_destroy(hash);
        cmph_io_nlfile_adapter_destroy(source);   
        fclose(keys_fd);
        return 0;
    }

下载 [file\_adapter\_ex2.c][file_adapter_ex2.c] 和 [keys.txt][]. 这个例子在版本0.8以下不能工作。

#include <cmph.h>
      #include <string.h>
      // Create minimal perfect hash function from in-memory vector
      
      #pragma pack(1)
      typedef struct {
          cmph_uint32 id;
          char key[11];
          cmph_uint32 year;
      } rec_t;
      #pragma pack(0)
      
      int main(int argc, char **argv)
      {   
          // Creating a filled vector
          unsigned int i = 0;  
          rec_t vector[10] = {
         {
         1, "aaaaaaaaaa", 1999}, {
         2, "bbbbbbbbbb", 2000}, {
         3, "cccccccccc", 2001},
                      {
          4, "dddddddddd", 2002}, {
         5, "eeeeeeeeee", 2003}, {
         6, "ffffffffff", 2004},
                      {
          7, "gggggggggg", 2005}, {
         8, "hhhhhhhhhh", 2006}, {
         9, "iiiiiiiiii", 2007},
                      {
          10,"jjjjjjjjjj", 2008}};
          unsigned int nkeys = 10;
          FILE* mphf_fd = fopen("temp_struct_vector.mph", "w");
          // Source of keys
          cmph_io_adapter_t *source = cmph_io_struct_vector_adapter(vector, (cmph_uint32)sizeof(rec_t), (cmph_uint32)sizeof(cmph_uint32), 11, nkeys); 
      
          //Create minimal perfect hash function using the BDZ algorithm.
          cmph_config_t *config = cmph_config_new(source);
          cmph_config_set_algo(config, CMPH_BDZ);
          cmph_config_set_mphf_fd(config, mphf_fd);
          cmph_t *hash = cmph_new(config);
          cmph_config_destroy(config);
          cmph_dump(hash, mphf_fd); 
          cmph_destroy(hash);    
          fclose(mphf_fd);
         
          //Find key
          mphf_fd = fopen("temp_struct_vector.mph", "r");
          hash = cmph_load(mphf_fd);
          while (i < nkeys) {
            const char *key = vector[i].key;
            unsigned int id = cmph_search(hash, key, 11);
            fprintf(stderr, "key:%s -- hash:%u\n", key, id);
            i++;
          }
          
          //Destroy hash
          cmph_destroy(hash);
          cmph_io_vector_adapter_destroy(source);   
          fclose(mphf_fd);
          return 0;
      }

这个例子在版本0.8以下不能工作。

Cmph 应用

Cmph既是库的名字，也是包中的应用程序的名字。你可以使用cmph应用程序通过命令行的方式构建最小完美哈希函数。Cmph应用有一些命令选项，但是它可以很容易的创建、查询MPHFs：

$ \# Using the chm algorithm (default one) for constructing a mphf for keys in file keys\_file

$ ./cmph -g keys\_file

$ \# Query id of keys in the file keys\_query

$ ./cmph -m keys\_file.mph keys\_query

其他的选项可以让你设置C API中的大多数参数。下边就是全部的使用帮助：

usage: cmph \[-v\] \[-h\] \[-V\] \[-k nkeys\] \[-f hash\_function\] \[-g \[-c algorithm\_dependent\_value\]\[-s seed\] \]

\[-a algorithm\] \[-M memory\_in\_MB\] \[-b algorithm\_dependent\_value\] \[-t keys\_per\_bin\] \[-d tmp\_dir\]

\[-m file.mph\] keysfile

Minimum perfect hashing tool

\-h 打印这个帮助消息

\-c c值决定:

\* 在BMZ和CHM算法中，c决定图中点的数量

\* 在FCH算法中，c决定每个键需要的存储比特数

\* 在CHD\_PH算法中，c决定装填因子

\-a 算法- 合法参数有：

\* bmz

\* bmz8

\* chm

\* brz

\* fch

\* bdz

\* bdz\_ph

\* chd\_ph

\* chd

\-f 哈希函数(可能多次使用) - 合法参数有：

\* jenkins

\-V 打印版本信息并退出

\-v increase verbosity (可能多次使用)

\-k 键的数量

\-g 生成模式

\-s 随机种子

\-m MPHF文件

\-M 在BRZ算法中，决定可供使用的主存容量（MB）

\-d 在BRZ算法中，临时使用的目录

\-b 这个参数的意义取决于-a选项选择的算法：

\* 在BRZ中，这个参数用来限制bucket中键的最大数量，可取值的范围\[64,175\]。默认是 128.

\* 在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 和 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.

This parameter has no effect for other algorithms.

\-t 为t-完美哈希函数设置每个bin中键的数量。一个t-PHF允许在bin中至多发生t次冲突。. 这个参数仅对CHD 和CHD\_PH 算法有效.取值范围 \[1,128\]. 默认是1

keysfile line separated file with keys

下载地址：

[http://sf.net/projects/cmph][http_sf.net_projects_cmph]

英文地址：[http://cmph.sourceforge.net/index.html][http_cmph.sourceforge.net_index.html]

[http_www.cnblogs.com_CheeseZH]: http://www.cnblogs.com/CheeseZH
[Link 1]: http://cmph.sourceforge.net/concepts.html
[CHD Algorithm]: http://cmph.sourceforge.net/chd.html
[BDZ Algorithm]: http://cmph.sourceforge.net/bdz.html
[BMZ Algorithm]: http://cmph.sourceforge.net/bmz.html
[BRZ Algorithm]: http://cmph.sourceforge.net/brz.html
[CHM Algorithm]: http://cmph.sourceforge.net/chm.html
[FCH Algorithm]: http://cmph.sourceforge.net/fch.html
[vector_adapter_ex1.c]: http://cmph.sourceforge.net/examples/vector_adapter_ex1.c
[file_adapter_ex2.c]: http://cmph.sourceforge.net/examples/file_adapter_ex2.c
[keys.txt]: http://cmph.sourceforge.net/examples/keys.txt
[http_sf.net_projects_cmph]: http://sf.net/projects/cmph
[http_cmph.sourceforge.net_index.html]: http://cmph.sourceforge.net/index.html