Самый быстрый поиск строковых ключей для известного набора ключей

Рассмотрим функцию поиска со следующей сигнатурой, которая должна возвращать целое число для заданного строкового ключа:

int GetValue(string key) { ... }

Рассмотрим также, что сопоставления значений ключа, нумерация N, известны заранее, когда записывается исходный код для функции, например:

// N=3
{ "foo", 1 },
{ "bar", 42 },
{ "bazz", 314159 }

Таким образом, действительная (но не идеальная!) реализация для функции для ввода выше:

int GetValue(string key)
{
    switch (key)
    {
         case "foo": return 1;
         case "bar": return 42;
         case "bazz": return 314159;
    }

    // Doesn't matter what we do here, control will never come to this point
    throw new Exception();
}

Также заранее известно, сколько раз (C >= 1) функция будет вызываться во время выполнения для каждого заданного ключа. Например:

C["foo"] = 1;
C["bar"] = 1;
C["bazz"] = 2;

Однако порядок таких вызовов неизвестен. Например. приведенное выше может описывать следующую последовательность вызовов во время выполнения:

GetValue("foo");
GetValue("bazz");
GetValue("bar");
GetValue("bazz");

или любой другой последовательности, если совпадают числа вызовов.

Существует также ограничение M, указанное в любых единицах, наиболее удобное, определяющее верхнюю границу памяти любых таблиц поиска и других вспомогательных структур, которые могут использоваться GetValue (структуры инициализируются заранее, эта инициализация не учитывается сложность функции). Например, M = 100 символов или M = 256 sizeof (ссылка на объект).

Вопрос заключается в том, как написать тело GetValue таким образом, чтобы оно было как можно быстрее - другими словами, суммарное время всех вызовов GetValue (обратите внимание, что мы знаем общий счет за все вышеперечисленное ) минимальна для заданных N, C и M?

Алгоритм может требовать разумного минимального значения для M, например. M >= char.MaxValue. Это может также потребовать, чтобы M был выровнен с некоторой разумной границей - например, чтобы он мог быть только двумя. Также может потребоваться, чтобы M была функцией N определенного вида (например, она может допускать допустимые M = N или M = 2N,... или действительные M = N или M = N ^ 2,... и т.д.).

Алгоритм может быть выражен на любом подходящем языке или в другой форме. Для ограничений производительности во время выполнения для сгенерированного кода предположим, что сгенерированный код для GetValue будет находиться в С#, VB или Java (действительно, любой язык будет работать, если строки обрабатываются как неизменяемые массивы символов, то есть O (1) длину и O (1) индексацию, и никакие другие данные, рассчитанные для них заранее). Кроме того, чтобы упростить это, ответы, которые предполагают, что C = 1 для всех ключей считаются действительными, хотя предпочтительны те ответы, которые охватывают более общий случай.

Некоторые размышления о возможных подходах

Очевидным первым ответом на вышеупомянутое является использование идеального хеша, но общие подходы к нахождению кажутся несовершенными. Например, можно легко создать таблицу для минимального совершенного хэша с использованием хеширования Pearson для данных примера выше, но тогда входной ключ должен быть хэширован для каждого вызова GetValue, а хэш Pearson обязательно сканирует всю входную строку, Но все образцы ключей на самом деле различаются в их третьем символе, поэтому только это может использоваться как вход для хэша вместо всей строки. Кроме того, если M требуется как минимум char.MaxValue, то третий символ сам становится совершенным хешем.

Для другого набора ключей это может быть больше недействительным, но все же возможно уменьшить количество символов, рассмотренных до получения точного ответа. Кроме того, в некоторых случаях, когда минимальный совершенный хеш потребует проверки всей строки, может быть возможно уменьшить поиск до подмножества или иным образом сделать его быстрее (например, менее сложной хэширующей функцией?), Сделав хэш не минимальным (т.е. M > N) - эффективно жертвуя пространством ради скорости.

Возможно, также, что традиционное хеширование не является такой хорошей идеей для начала, и проще структурировать тело GetValue как серию условных обозначений, устроенных так, что первая проверяет символ "самый переменный" (тот, который зависит от большинства ключей), с дополнительными вложенными проверками, если необходимо, чтобы определить правильный ответ. Обратите внимание, что на "дисперсию" здесь может влиять количество просмотров каждой клавиши (C). Кроме того, не всегда легко понять, какова должна быть лучшая структура ветвей - может быть, например, что "самый переменный" символ позволяет вам отличить 10 ключей из 100, но для остальных 90 эта одна дополнительная проверка нет необходимости различать их, и в среднем (учитывая C) количество проверок на ключ больше, чем в другом решении, которое не начинается с "самого переменного" символа. Цель состоит в том, чтобы определить совершенную последовательность проверок.

Ответы

Ответ 1

Вы можете использовать поиск Boyer, но я думаю, что Trie будет гораздо более эффектным методом. Вы можете изменить Trie, чтобы свернуть слова, когда вы делаете число попаданий для нулевого ключа, таким образом уменьшая количество поисков, которые вам нужно будет делать дальше по линии, которую вы получаете. Самое большое преимущество, которое вы получите, это то, что вы выполняете поиск массивов для индексов, что намного быстрее, чем сравнение.

Ответ 2

Вы говорили о ограничении памяти, когда дело доходит до предкомпета - есть ли также ограничение по времени?

Я бы рассмотрел trie, но тот, где вы не обязательно начинали с первого персонажа. Вместо этого найдите индекс, который больше всего сократит пространство поиска, и рассмотрим это в первую очередь. Таким образом, в вашем примере ( "foo", "bar", "bazz" ) вы берете третьего символа, который сразу же сообщит вам, какая строка была. (Если мы знаем, что нам всегда будет дано одно из входных слов, мы можем вернуться, как только мы найдем уникальный потенциальный матч.)

Теперь, полагая, что нет ни одного индекса, который приведет вас к уникальной строке, вам нужно определить персонажа, который будет выглядеть после этого. В теории вы прекоммутируете trie, чтобы выработать для каждой ветки то, что оптимальный персонаж должен смотреть на следующий (например, "если третий символ был" a ", нам нужно посмотреть на второго символа следующего, если это" o ", мы нужно посмотреть на первый символ следующего), но это потенциально занимает гораздо больше времени и пространства. С другой стороны, это может сэкономить много времени - потому что, спустившись на один символ, каждая ветвь может иметь индекс для выбора который однозначно идентифицирует окончательную строку, но каждый раз будет отличаться от этого. Объем пространства, требуемый этим подходом, будет зависеть от того, насколько похожи строки, и может быть трудно предсказать заранее. Было бы неплохо иметь возможность динамически сделайте это для всех трех узлов, которые вы можете, но затем, когда вы обнаружите, что у вас закончилось пространство для строительства, определите единый порядок для" всего, что под этим node ". (Таким образом, вы не можете сохранить" следующий индекс символа "на каждом node под node, только одна последовательность.) Сообщите мне я Это не понятно, и я могу попытаться разработать...

Как вы представляете trie, будет зависеть от диапазона входных символов. Если они все находятся в диапазоне "a" - "z", тогда простой массив будет невероятно быстрым для навигации и разумно эффективным для трех узлов, где есть возможности для большинства доступных опций. Позже, когда есть только две или три возможных ветки, это становится бесполезным в памяти. Я бы предложил полиморфный класс Trie node, так что вы можете построить наиболее подходящий тип node в зависимости от того, сколько подсетей есть.

Ничто из этого не выполняет отбраковку - неясно, сколько можно добиться, быстро отбраковав. Одна из ситуаций, когда я вижу, что это помогает, - это когда число ветвей от одного trie node падает до 1 (из-за удаления ветки, которая исчерпана), эта ветка может быть полностью устранена. Со временем это может иметь большое значение и не должно быть слишком сложно вычислить. В основном, когда вы строите trie, вы можете предсказать, сколько раз будет выполняться каждая ветка, и по мере того, как вы перемещаете trie, вы можете вычесть ее из этого количества на каждую ветку, когда будете перемещаться по ней.

Это все, что я придумал до сих пор, и это не совсем полная реализация, но я надеюсь, что это поможет...

Ответ 3

Здесь возможен подход для определения наименьшего подмножества символов для целевой хэш-процедуры:

пусть:
k - количество отдельных символов по всем вашим ключевым словам
c - максимальная длина ключевого слова
n - количество ключевых слов
в вашем примере (более короткие слова с пробелами):

"foo "
"bar "
"bazz"

k = 7 (f, o, b, a, r, z,), c = 4, n = 3

Мы можем использовать это, чтобы вычислить нижнюю границу для нашего поиска. Нам нужно как минимум log_k (n) символов однозначно идентифицировать ключевое слово, если log_k (n) >= c, вам нужно будет использовать ключевое слово целиком, и нет причин для продолжения.

Затем устраните один столбец за раз и проверьте, осталось ли еще n различных значений. Используйте отдельные символы в каждом столбце в качестве эвристики для оптимизации поиска:

2 2 3 2
f o o .
b a r .
b a z z

Сначала удалите столбцы с наименьшими отдельными символами. Если у вас есть столбцы <= log_k (n), вы можете остановиться. При желании вы можете рандомизировать бит и устранить 2-й наименьший отличительный столбец или попытаться восстановить, если исключенный столбец дает меньше n разных слов. Этот алгоритм примерно равен O (n!) В зависимости от того, сколько вы пытаетесь восстановить. Это не гарантировало найти оптимальное решение, но это хороший компромисс.

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

Ответ 4

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

Сведение к минимуму означает сокращение их до минимума, которым они должны быть, своего рода создание.

Например, если у вас были строки: "alfred", "bob", "bill", "joe", я бы сбил их до "a", "bi", "bo", "j".

Затем поместите их в непрерывный блок памяти, например:

char *table = "a\0bi\0bo\0j\0"; // last 0 is really redundant..but
char *keys[4];
keys[0] = table;
keys[1] = table + 2;
keys[2] = table + 5;
keys[3] = table + 8;

В идеале компилятор сделает все это для вас, если вы просто пойдете:

keys[0] = "a";
keys[1] = "bi";
keys[2] = "bo";
keys[3] = "j";

Но я не могу сказать, верно это или нет.

Теперь вы можете выполнить поиск этой таблицы, а ключи как можно короче. Если вы нажмете на конец ключа, вы соответствуете. Если нет, то следуйте стандартным алгоритмам bsearch.

Цель состоит в том, чтобы собрать все данные вместе и сохранить код дословно битным, чтобы все это соответствовало кэшу CPU. Вы можете напрямую обрабатывать ключ из программы, без предварительной обработки или добавления чего-либо.

Для достаточно большого количества ключей, которые достаточно распределены, я думаю, что это будет довольно быстро. Это зависит от количества задействованных строк. Для меньших чисел накладные расходы на вычисления хэш-значений и т.д. Больше, чем поиск чего-то подобного. Для больших значений это того стоит. Просто все эти числа зависят от алгоритмов и т.д.

Это, однако, вероятно, самое маленькое решение в плане памяти, если это важно.

Это также имеет преимущество простоты.

Addenda:

У вас нет спецификаций на входах за пределами "строк". Там также нет дискуссии о том, сколько строк вы ожидаете использовать, их длину, их общность или частоту использования. Возможно, все они могут быть получены из "источника", но не планируются дизайнером алгоритма. Вы просите алгоритм, который создает что-то вроде этого:

inline int GetValue(char *key) {
    return 1234;
}

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

Любой дизайн, следующий за "сжатием каждого возможного бита производительности", должен знать больше о входах, чем "любые и все строки". Это пространство проблемы просто слишком велико, если вы хотите, чтобы это было максимально возможным для любого условия.

Алгоритм, который обрабатывает строки с очень длинными идентичными префиксами, может отличаться от того, который работает на полностью случайных строках. Алгоритм мог бы сказать: "Если ключ начинается с" a ", пропустите следующие 100 символов, так как они все" есть ".

Но если эти строки исходят от людей, и они используют длинные строки одних и тех же букв и не сходят с ума, пытаясь сохранить эти данные, тогда, когда они жалуются, что алгоритм плохо работает, вы отвечаете, что "вы делаете глупые вещи, не делайте этого". Но мы не знаем источник этих строк.

Итак, вам нужно выбрать проблемное пространство для нацеливания на алгоритм. У нас есть всевозможные алгоритмы, которые якобы делают то же самое, потому что они обращаются к различным ограничениям и работают лучше в разных ситуациях.

Хеширование дорого, выкладка хэшмапов стоит дорого. Если не хватает данных, есть лучшие методы, чем хеширование. Если у вас большой бюджет памяти, вы можете создать огромный конечный автомат, основанный на N состояниях за node (N - ваш размер набора символов, который вы не укажете, - BAUDOT? 7-бит ASCII? UTF-32?). Это будет работать очень быстро, если только объем памяти, потребляемой штатами, не разбивает процессорный кэш или не выдавливает другие вещи.

Вы могли бы генерировать код для всего этого, но вы можете зайти в пределы ограничения размера кода (вы не говорите, на каком языке: например, Java имеет ограничение на байты кода 64 Кбайт).

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

Ответ 5

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

const int POSSIBLE_CHARCODES = 256; //256 for ascii //65536 for unicode 16bit
struct LutMap {
    int value;
    LutMap[POSSIBLE_CHARCODES] next;
}
int GetValue(string key) {
    LutMap root = Global.AlreadyCreatedLutMap;
    for(int x=0; x<key.length; x++) {
        int c = key.charCodeAt(x);
        if(root.next[c] == null) {
            return root.value;
        }
        root = root.next[c];
    }
}

Ответ 6

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

foo  = 0x666F6F (hex value)
bar  = 0x626172
bazz = 0x62617A7A

Последний столбец, присутствующий во всех из них, по-разному. Проанализируйте далее:

foo  = 0xF = 1111
bar  = 0x2 = 0010
bazz = 0xA = 1010

Бит-сдвиг вправо дважды, отбрасывая переполнение, вы получаете отличное значение для каждого из них:

foo  = 0011
bar  = 0000
bazz = 0010

Бит-сдвиг вправо дважды, добавив переполнение в новый буфер:   foo = 0010   bar = 0000   bazz = 0001

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

Ответ 7

Вы посмотрели TCB. Возможно, используемый алгоритм может использоваться для извлечения ваших значений. Это очень похоже на проблему, которую вы пытаетесь решить. И по опыту я могу сказать, что tcb - один из самых быстрых поисков ключей для ключей, которые я использовал. Это постоянное время поиска, независимо от количества сохраненных ключей.

Ответ 8

Рассмотрите возможность использования алгоритма Кнута-Морриса-Пратта.

Предварительно обработать данную карту в большой строке, как показано ниже

String string = "{foo:1}{bar:42}{bazz:314159}";
int length = string.length();

Согласно времени предварительной обработки KMP для string будет выполняться O(length). Для поиска с любым словом/клавишей выполняется сложность O(w), где w - длина слова/ключа.

Вам понадобится сделать 2 модификации алгоритма KMP:

  • Клавиша
  • должна быть указана в объединенном string
  • вместо того, чтобы возвращать true/false, он должен разобрать номер и вернуть его

Пожелайте, чтобы он дал хорошие подсказки.