CMPH——C Minimal Perfect Hashing Library【译】

动机：

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

最小完美哈希函数被广泛的应用在高效存储以及从静态集中快速检索条目，比如自然语言中的词语，程序或者交互系统中的预定义词语，网络搜索引擎中的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. 这个例子不能再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 和 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

本文转自ZH奶酪博客园博客，原文链接：http://www.cnblogs.com/CheeseZH/archive/2012/12/20/2826635.html，如需转载请自行联系原作者