Структура данных для поиска строки фиксированной длины

Question

У меня есть куча строк в качестве ключей.Что-то вроде ...

AAAA ABBA ACEA ALFG
...
...
ZURF [AAA _JFS aKDJ

Все они являются уникальной комбинацией любых 4 символов и имеют одинаковую длину.Есть сотни тысяч таких.Я хочу выполнить поиск и получить значение, связанное с каждой строкой.

В настоящее время она реализована в виде хэш-таблицы, но основной проблемой являются коллизии (я реализовал все стратегии в Wiki).

Я думаю реализовать это как префиксное дерево.Хотя, учитывая параметры (уникальные, фиксированной длины), мне интересно, есть ли готовая структура данных, о которой я не могу думать, которая лучше всего подходит для этого ...

РЕДАКТИРОВАТЬ: Кроме того, все возможные комбинации заполняются один раз файлом данных.После этого поиск происходит на скорости соединения.

Answer 1

Поскольку вы знаете все строки заранее, вы можете использовать gperf для генерации совершенной хеш-функции , в которой нет коллизий. Например, с четырьмя входными строками AAAA ABBA ACEA ALFG он сгенерировал следующую хеш-функцию (используя командную строку gperf -L ANSI-C input.txt):

static unsigned int
hash (register const char *str, register unsigned int len)
{
  static unsigned char asso_values[] =
    {
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12,  7,  2,  5, 12, 12,
      12, 12, 12, 12, 12, 12,  0, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
      12, 12, 12, 12, 12, 12
    };
  return len + asso_values[(unsigned char)str[1]];
}

const char *
in_word_set (register const char *str, register unsigned int len)
{
  static const char * wordlist[] =
    {
      "", "", "", "",
      "ALFG",
      "",
      "ABBA",
      "", "",
      "ACEA",
      "",
      "AAAA"
    };

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

      if (key <= MAX_HASH_VALUE && key >= 0)
        {
          register const char *s = wordlist[key];

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

Для чего требуется поиск по одной таблице, сравнение длины и сравнение строк. Если вы точно знаете, что слово, которое вы хэшируете, является одним из ваших исходных слов, тогда вы можете пропустить сравнение строк.

Увеличение входного размера с 4 до 10000 случайно сгенерированных строк увеличивает хеш-функцию до 4-х просмотров таблиц плюс сравнение длины и сравнение строк. Но, поскольку при сравнении строк необходимо хранить каждую исходную строку, это приводит к очень большой таблице в скомпилированном объектном файле (1,4 МБ). Если вам не нужно сравнивать строки, вы можете опустить эту таблицу.

Answer 2

Хеш-таблица, даже с коллизиями, превзойдет все остальное, и вы можете настроить ее для уменьшения коллизий.

Answer 3

Сначала переведите каждую строку в целое число.Если ваш алфавит содержит 64 символа (например), вы можете использовать 4 * 6 = 24-битные целые числа в качестве ключей.

Теперь, если используется более половины возможных ключей (как вы говорите, естьсотни тысяч из них), может быть, самое простое решение подойдет: просто создайте массив, получите доступ к нему по индексу (целое число, выведенное из строки).

Если возможно, реализуйте это с помощью одного выделения памяти.Это может даже сэкономить память (память теряется из-за 100 000 небольших выделений).