Minimal perfect hash function - Алгоритмы

Понадобилось решить следующую задачу: нужно создать фиксированный lookup table для отображения сильно разреженного подмножества ключей в подмножество индексов в таблице, без промежутков.
Задача появилась в контексте перевода Unicode codepoint-ов из верхнего регистра в нижний и обратно (естественно для тех, к которым эти операции применимы), в контексте библиотеки на С++17.

Буду признателен за помощь по следующим пунктам:
1. Помочь разобраться в теории создания минимального идеального хеша. Желательно какой-нибудь туториал, где бы тема детально разбиралаь на пальцах.
2. Либо идея, чем можно было бы заменить такой хеш, не потеряв в скорости.
3. Либо готовое решение для С++, готовая таблица, которую без проблем можно взять и вставить в свой проект

Здравствуйте, Videoman, Вы писали:

V>2. Либо идея, чем можно было бы заменить такой хеш, не потеряв в скорости.
Просто wchar.ToLower или аналог не устроит?
Или просто массив на 2**16 символов?

Здравствуйте, gandjustas, Вы писали:

G>Просто wchar.ToLower или аналог не устроит?
В общем виде, насколько мне известно, поддержка Unicode в С++ отсутствует, из-за чего весь сыр-бор.

G>Или просто массив на 2**16 символов?
Можно поподробнее что за массив 2^16 ?

Здравствуйте, vsb, Вы писали:

vsb>gperf?

Да, первое что советуют gperf. Из документации я не понял как её использовать. Например задача создать constexpr lookup table для фиксированной таблицы UnicodeData.txt, как это сделать с помощью это утилиты?

Здравствуйте, Videoman, Вы писали:

V>Здравствуйте, gandjustas, Вы писали:

G>>Просто wchar.ToLower или аналог не устроит?
V>В общем виде, насколько мне известно, поддержка Unicode в С++ отсутствует, из-за чего весь сыр-бор.
Больше 10 лет присутствует https://en.cppreference.com/w/cpp/string/wide/towlower

G>>Или просто массив на 2**16 символов?
V>Можно поподробнее что за массив 2^16 ?
wchar_t кодирует каждый символ двумя байтами. Это 2**16 разных значений. Для отображения всех символов, кодируемых wchar_t, в другие символы достаточно сделать массив из 2**16 элементов. Это займет не так много памяти.

Здравствуйте, gandjustas, Вы писали:

G>Больше 10 лет присутствует https://en.cppreference.com/w/cpp/string/wide/towlower
Но с Юникодом не работает, только с локалями и древними кодировками.

G>wchar_t кодирует каждый символ двумя байтами. Это 2**16 разных значений. Для отображения всех символов, кодируемых wchar_t, в другие символы достаточно сделать массив из 2**16 элементов. Это займет не так много памяти.
Хорошо, а Unicode это, грубо, таблица из 2^20 которую нужно отобразить на относительно небольшой массив кодов которые могут иметь Lower и Upper case.

Здравствуйте, Videoman, Вы писали:

V>Понадобилось решить следующую задачу: нужно создать фиксированный lookup table для отображения сильно разреженного подмножества ключей в подмножество индексов в таблице, без промежутков.
V>Задача появилась в контексте перевода Unicode codepoint-ов из верхнего регистра в нижний и обратно (естественно для тех, к которым эти операции применимы), в контексте библиотеки на С++17.

А icu никак не может помочь?

Здравствуйте, Stanislav V. Zudin, Вы писали:

SVZ>А icu никак не может помочь?

Буду признателен, если покажешь куда смотреть ?! Пока у меня от ICU глаза разбегаются.

Здравствуйте, Videoman, Вы писали:

SVZ>>А icu никак не может помочь?

V>Буду признателен, если покажешь куда смотреть ?! Пока у меня от ICU глаза разбегаются.

Библиотека непростая, я несколько лет её не трогал, поэтому советчик так себе

Но начать стоит с u_toupper.

Тут кой-какой пример имеется: https://github.com/unicode-org/icu/blob/main/icu4c/source/samples/ustring/ustring.cpp

Здравствуйте, Videoman, Вы писали:

vsb>>gperf?

V>Да, первое что советуют gperf. Из документации я не понял как её использовать. Например задача создать constexpr lookup table для фиксированной таблицы UnicodeData.txt, как это сделать с помощью это утилиты?

Ну вот пример для русских букв, кодировка UTF-8, думаю там всё очевидно.

test.gperf

%struct-type
struct chars { char *c1; char *c2; };
%define slot-name c1
%%
"\xd0\x90", "\xd0\xb0"
"\xd0\xb0", "\xd0\x90"
"\xd0\x91", "\xd0\xb1"
"\xd0\xb1", "\xd0\x91"
"\xd0\x92", "\xd0\xb2"
"\xd0\xb2", "\xd0\x92"
"\xd0\x93", "\xd0\xb3"
"\xd0\xb3", "\xd0\x93"
"\xd0\x94", "\xd0\xb4"
"\xd0\xb4", "\xd0\x94"
"\xd0\x95", "\xd0\xb5"
"\xd0\xb5", "\xd0\x95"
"\xd0\x81", "\xd1\x91"
"\xd1\x91", "\xd0\x81"
"\xd0\x96", "\xd0\xb6"
"\xd0\xb6", "\xd0\x96"
"\xd0\x97", "\xd0\xb7"
"\xd0\xb7", "\xd0\x97"
"\xd0\x98", "\xd0\xb8"
"\xd0\xb8", "\xd0\x98"
"\xd0\x99", "\xd0\xb9"
"\xd0\xb9", "\xd0\x99"
"\xd0\x9a", "\xd0\xba"
"\xd0\xba", "\xd0\x9a"
"\xd0\x9b", "\xd0\xbb"
"\xd0\xbb", "\xd0\x9b"
"\xd0\x9c", "\xd0\xbc"
"\xd0\xbc", "\xd0\x9c"
"\xd0\x9d", "\xd0\xbd"
"\xd0\xbd", "\xd0\x9d"
"\xd0\x9e", "\xd0\xbe"
"\xd0\xbe", "\xd0\x9e"
"\xd0\x9f", "\xd0\xbf"
"\xd0\xbf", "\xd0\x9f"
"\xd0\xa0", "\xd1\x80"
"\xd1\x80", "\xd0\xa0"
"\xd0\xa1", "\xd1\x81"
"\xd1\x81", "\xd0\xa1"
"\xd0\xa2", "\xd1\x82"
"\xd1\x82", "\xd0\xa2"
"\xd0\xa3", "\xd1\x83"
"\xd1\x83", "\xd0\xa3"
"\xd0\xa4", "\xd1\x84"
"\xd1\x84", "\xd0\xa4"
"\xd0\xa5", "\xd1\x85"
"\xd1\x85", "\xd0\xa5"
"\xd0\xa6", "\xd1\x86"
"\xd1\x86", "\xd0\xa6"
"\xd0\xa7", "\xd1\x87"
"\xd1\x87", "\xd0\xa7"
"\xd0\xa8", "\xd1\x88"
"\xd1\x88", "\xd0\xa8"
"\xd0\xa9", "\xd1\x89"
"\xd1\x89", "\xd0\xa9"
"\xd0\xaa", "\xd1\x8a"
"\xd1\x8a", "\xd0\xaa"
"\xd0\xab", "\xd1\x8b"
"\xd1\x8b", "\xd0\xab"
"\xd0\xac", "\xd1\x8c"
"\xd1\x8c", "\xd0\xac"
"\xd0\xad", "\xd1\x8d"
"\xd1\x8d", "\xd0\xad"
"\xd0\xae", "\xd1\x8e"
"\xd1\x8e", "\xd0\xae"
"\xd0\xaf", "\xd1\x8f"
"\xd1\x8f", "\xd0\xaf"

test_gperf.c

/* C code produced by gperf version 3.0.3 */
/* Command-line: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/gperf test.gperf  */
/* Computed positions: -k'1-2' */

#line 2 "test.gperf"
struct chars { char *c1; char *c2; };

#define TOTAL_KEYWORDS 66
#define MIN_WORD_LENGTH 2
#define MAX_WORD_LENGTH 2
#define MIN_HASH_VALUE 2
#define MAX_HASH_VALUE 132
/* maximum key range = 131, duplicates = 0 */

#ifdef __GNUC__
__inline
#else
#ifdef __cplusplus
inline
#endif
#endif
static unsigned int
hash (str, len)
     register const char *str;
     register unsigned int len;
{
  static unsigned char asso_values[] =
    {
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133,  64,  10,
       59,  54,  49,  44,  39,  34,  29,  24,  19,  14,
        9,   4, 127,   2, 117,   0, 112, 107, 102,  97,
       92,  87,  82,  77,  72,  67,  62,  57,  52,  47,
       42,  37,  32,  27,  22,  17,  12,   7,   2, 125,
      120, 115, 110, 105, 100,  95,  90,  85,  80,  75,
       70,  65,  60,  55,  50,  45,  40,  35,  30,  25,
       20,  15, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133,   5,   0,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133, 133, 133, 133, 133,
      133, 133, 133, 133, 133, 133
    };
  return len + asso_values[(unsigned char)str[1]] + asso_values[(unsigned char)str[0]];
}

struct chars *
in_word_set (str, len)
     register const char *str;
     register unsigned int len;
{
  static struct chars wordlist[] =
    {
      {""}, {""},
#line 18 "test.gperf"
      {"\321\221", "\xd0\x81"},
      {""},
#line 70 "test.gperf"
      {"\321\217", "\xd0\xaf"},
      {""},
#line 66 "test.gperf"
      {"\321\215", "\xd0\xad"},
#line 7 "test.gperf"
      {"\320\221", "\xd0\xb1"},
      {""},
#line 55 "test.gperf"
      {"\320\250", "\xd1\x88"},
      {""},
#line 64 "test.gperf"
      {"\321\214", "\xd0\xac"},
#line 42 "test.gperf"
      {"\321\201", "\xd0\xa1"},
      {""},
#line 53 "test.gperf"
      {"\320\247", "\xd1\x87"},
      {""},
#line 62 "test.gperf"
      {"\321\213", "\xd0\xab"},
#line 17 "test.gperf"
      {"\320\201", "\xd1\x91"},
      {""},
#line 51 "test.gperf"
      {"\320\246", "\xd1\x86"},
      {""},
#line 60 "test.gperf"
      {"\321\212", "\xd0\xaa"},
#line 38 "test.gperf"
      {"\320\277", "\xd0\x9f"},
      {""},
#line 49 "test.gperf"
      {"\320\245", "\xd1\x85"},
      {""},
#line 58 "test.gperf"
      {"\321\211", "\xd0\xa9"},
#line 36 "test.gperf"
      {"\320\276", "\xd0\x9e"},
      {""},
#line 47 "test.gperf"
      {"\320\244", "\xd1\x84"},
      {""},
#line 56 "test.gperf"
      {"\321\210", "\xd0\xa8"},
#line 34 "test.gperf"
      {"\320\275", "\xd0\x9d"},
      {""},
#line 45 "test.gperf"
      {"\320\243", "\xd1\x83"},
      {""},
#line 54 "test.gperf"
      {"\321\207", "\xd0\xa7"},
#line 32 "test.gperf"
      {"\320\274", "\xd0\x9c"},
      {""},
#line 43 "test.gperf"
      {"\320\242", "\xd1\x82"},
      {""},
#line 52 "test.gperf"
      {"\321\206", "\xd0\xa6"},
#line 30 "test.gperf"
      {"\320\273", "\xd0\x9b"},
      {""},
#line 41 "test.gperf"
      {"\320\241", "\xd1\x81"},
      {""},
#line 50 "test.gperf"
      {"\321\205", "\xd0\xa5"},
#line 28 "test.gperf"
      {"\320\272", "\xd0\x9a"},
      {""},
#line 39 "test.gperf"
      {"\320\240", "\xd1\x80"},
      {""},
#line 48 "test.gperf"
      {"\321\204", "\xd0\xa4"},
#line 26 "test.gperf"
      {"\320\271", "\xd0\x99"},
      {""},
#line 37 "test.gperf"
      {"\320\237", "\xd0\xbf"},
      {""},
#line 46 "test.gperf"
      {"\321\203", "\xd0\xa3"},
#line 24 "test.gperf"
      {"\320\270", "\xd0\x98"},
      {""},
#line 35 "test.gperf"
      {"\320\236", "\xd0\xbe"},
      {""},
#line 44 "test.gperf"
      {"\321\202", "\xd0\xa2"},
#line 22 "test.gperf"
      {"\320\267", "\xd0\x97"},
      {""},
#line 33 "test.gperf"
      {"\320\235", "\xd0\xbd"},
      {""},
#line 40 "test.gperf"
      {"\321\200", "\xd0\xa0"},
#line 20 "test.gperf"
      {"\320\266", "\xd0\x96"},
      {""},
#line 31 "test.gperf"
      {"\320\234", "\xd0\xbc"},
      {""}, {""},
#line 16 "test.gperf"
      {"\320\265", "\xd0\x95"},
      {""},
#line 29 "test.gperf"
      {"\320\233", "\xd0\xbb"},
      {""}, {""},
#line 14 "test.gperf"
      {"\320\264", "\xd0\x94"},
      {""},
#line 27 "test.gperf"
      {"\320\232", "\xd0\xba"},
      {""}, {""},
#line 12 "test.gperf"
      {"\320\263", "\xd0\x93"},
      {""},
#line 25 "test.gperf"
      {"\320\231", "\xd0\xb9"},
      {""}, {""},
#line 10 "test.gperf"
      {"\320\262", "\xd0\x92"},
      {""},
#line 23 "test.gperf"
      {"\320\230", "\xd0\xb8"},
      {""}, {""},
#line 8 "test.gperf"
      {"\320\261", "\xd0\x91"},
      {""},
#line 21 "test.gperf"
      {"\320\227", "\xd0\xb7"},
      {""}, {""},
#line 6 "test.gperf"
      {"\320\260", "\xd0\x90"},
      {""},
#line 19 "test.gperf"
      {"\320\226", "\xd0\xb6"},
      {""}, {""},
#line 69 "test.gperf"
      {"\320\257", "\xd1\x8f"},
      {""},
#line 15 "test.gperf"
      {"\320\225", "\xd0\xb5"},
      {""}, {""},
#line 67 "test.gperf"
      {"\320\256", "\xd1\x8e"},
      {""},
#line 13 "test.gperf"
      {"\320\224", "\xd0\xb4"},
      {""}, {""},
#line 65 "test.gperf"
      {"\320\255", "\xd1\x8d"},
      {""},
#line 11 "test.gperf"
      {"\320\223", "\xd0\xb3"},
      {""}, {""},
#line 63 "test.gperf"
      {"\320\254", "\xd1\x8c"},
      {""},
#line 9 "test.gperf"
      {"\320\222", "\xd0\xb2"},
      {""}, {""},
#line 61 "test.gperf"
      {"\320\253", "\xd1\x8b"},
      {""},
#line 5 "test.gperf"
      {"\320\220", "\xd0\xb0"},
      {""}, {""},
#line 59 "test.gperf"
      {"\320\252", "\xd1\x8a"},
      {""},
#line 68 "test.gperf"
      {"\321\216", "\xd0\xae"},
      {""}, {""},
#line 57 "test.gperf"
      {"\320\251", "\xd1\x89"}
    };

  if (len <= MAX_WORD_LENGTH && len >= MIN_WORD_LENGTH)
    {
      unsigned int key = hash (str, len);

      if (key <= MAX_HASH_VALUE)
        {
          register const char *s = wordlist[key].c1;

          if (*str == *s && !strcmp (str + 1, s + 1))
            return &wordlist[key];
        }
    }
  return 0;
}

test.c

#include <stdio.h>
#include <string.h>
#include "test_gperf.c"

int main(int argc, char *argv[]) {
  if (argc < 2) return 1;
  struct chars *c = in_word_set(argv[1], strlen(argv[1]));
  if (c == 0) return 1;
  printf("%s %s", c->c1, c->c2);
  return 0;
}

Здравствуйте, vsb, Вы писали:

vsb>Ну вот пример для русских букв, кодировка UTF-8, думаю там всё очевидно.

А еcли: struct chars { int c1; int c2; };
Так он может?

Здравствуйте, Videoman, Вы писали:

vsb>>Ну вот пример для русских букв, кодировка UTF-8, думаю там всё очевидно.

V>А еcли: struct chars { int c1; int c2; };
V>Так он может?

Не думаю, он всё же со строками работает. Просто в строку преобразуй int и всё. Если у тебя не UTF-8, то там надо документацию почитать, чтобы с нулевыми символами правильно работало.

Здравствуйте, vsb, Вы писали:

vsb>Не думаю, он всё же со строками работает. Просто в строку преобразуй int и всё. Если у тебя не UTF-8, то там надо документацию почитать, чтобы с нулевыми символами правильно работало.

Жалко, что нельзя такое сделать по "прямому", в идеале мне нужно map<int, int>. У меня не UTF-8, у меня уже готовые codepoint-ы и нули там естественно есть. Ещё бы конечно хотелось бы простой пошаговый туториал, который бы объяснял принципы и как можно создать идеальную хеш функцию по заранее определенному множеству значений.

Здравствуйте, Videoman, Вы писали:

V>Здравствуйте, vsb, Вы писали:

vsb>>Не думаю, он всё же со строками работает. Просто в строку преобразуй int и всё. Если у тебя не UTF-8, то там надо документацию почитать, чтобы с нулевыми символами правильно работало.

V>Жалко, что нельзя такое сделать по "прямому", в идеале мне нужно map<int, int>. У меня не UTF-8, у меня уже готовые codepoint-ы и нули там естественно есть. Ещё бы конечно хотелось бы простой пошаговый туториал, который бы объяснял принципы и как можно создать идеальную хеш функцию по заранее определенному множеству значений.

Кажется, если спрашивать для любого домена и требовать совсем плотный кодомен, то общее решение будет сложновато.

Нельзя ли указать какое-нибудь свойство, которое облегчит задачу? Например, домен можно в цикле пройти за пару часов на компе?

Кстати, если задача только в toUpper, то есть смысл посмотреть в icu, она с юникодовскими последовательностями лучше дружит, чем тот же винапи или дотнет.

От:	Videoman	https://hts.tv/
Дата:	12.03.23 10:53
Оценка:

От:	gandjustas	http://blog.gandjustas.ru/
Дата:	12.03.23 12:13
Оценка:

	От:	vsb
	Дата:	12.03.23 13:24
	Оценка:

От:	Videoman	https://hts.tv/
Дата:	12.03.23 19:09
Оценка:

От:	Videoman	https://hts.tv/
Дата:	12.03.23 19:12
Оценка:

	От:	Stanislav V. Zudin
	Дата:	12.03.23 20:19
	Оценка:	+1

	От:	no_ise
	Дата:	14.03.23 13:17
	Оценка: