cmph Минимальное идеальное хеширование

Я потратил дни, пытаясь заставить библиотеку работать в моей системе. В библиотеке есть несколько алгоритмов, которые генерируют MPHF. Насколько я понимаю минимальную хеш-функцию, когда я хеширую два разных ключа с помощью MPHF, они возвращают два разных идентификатора. Похоже, это не относится к 2 миллионам ключей, которые я сгенерировал (целые числа, читаемые алгоритмом как строка). Я пробовал пару алгоритмов, которые реализует библиотека, но все они приводят к дублированию идентификаторов для многих ключей.

Вот что я написал:

#include <cmph.h>
#include <iostream>
#include <fstream>
#include <bitset>
#include <string>
#include <sstream>
#include <limits.h>

using namespace std;

int main(int argc, char** argv){

    FILE *fp = fopen("keys.txt", "r");
    FILE *read = fopen("keys2.txt", "r");
    ofstream ids("ids2.txt");

    if(!fp || !read || !ids.is_open()){
        cerr<<"Failed to open the file\n";
        exit(1);
    }

    cmph_t* hash = NULL;
    // source of keys
    cmph_io_adapter_t *source = cmph_io_nlfile_adapter(fp);
    cmph_config_t *config = cmph_config_new(source);
    cmph_config_set_algo(config, CMPH_BDZ);
    hash = cmph_new(config);
    cmph_config_destroy(config);

    char *k = (char *)malloc(sizeof(12));

    while(fgets(k, INT_MAX, read) != NULL){
        string key = k;
        unsigned int id = cmph_search(hash, k, (cmph_uint32)key.length());
        ids<<id<<"\n";
    }

    cmph_destroy(hash);
    cmph_io_nlfile_adapter_destroy(source);
    fclose(fp);
    fclose(read);
    ids.close();
}

Разве идентификаторы не должны быть уникальными для каждого отдельного ключа, если алгоритм утверждает, что генерирует минимальную идеальную хеш-функцию? Есть 2048383 ключей. Для моего проекта мне понадобятся идентификаторы для отображения от 0 до 2048382, так как я планирую использовать минимальную идеальную хеш-функцию. Я не уверен, где я ошибаюсь в своем понимании. Пожалуйста помоги.


person truth_seeker    schedule 04.01.2017    source источник


Ответы (1)


Если ваш keys2.txt содержит ключи, которые не были частью набора, который использовался для создания вашего hash, то, по определению mphf, вы получите либо повторяющиеся хэши, либо, возможно, значения за пределами вашего диапазона. Вы должны сохранить все ключи, которые использовались для создания hash, а затем убедиться, что ключ, который был передан в cmph_search, был таким же, как тот, который привел к хэшу/идентификатору, возвращенному cmph_search.

person Pavel P    schedule 24.01.2020