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

Question

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

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 будет в C#, VB или Java (на самом деле, любой язык подойдет, если строки обрабатываются как неизменяемые массивы символов - то есть длина O(1) и индексирование O(1), и никакие другие данные для них не вычисляются заранее)). Также, чтобы немного упростить это, ответы, которые предполагают, что C=1 для всех ключей, считаются действительными, хотя те ответы, которые охватывают более общий случай, являются предпочтительными.

Размышления о возможных подходах

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

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

Answer 3

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

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

Например, если бы у вас были строки: "Альфред", "Боб", "Билл", "Джо", я бы выбил их "А", "Би", "Бо", "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.

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

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

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

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

Дополнения:

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

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

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

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

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

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

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

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

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

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

Answer 4

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

позволять:
k будет количество отдельных символов по всем вашим ключевым словам
может быть максимальная длина ключевого слова
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-е наименьшее различающееся col или попытаться восстановить, если исключенное col приводит к менее чем n отдельным словам. Этот алгоритм примерно O(n!) В зависимости от того, сколько вы пытаетесь восстановить. Не гарантировано найти оптимальное решение, но это хороший компромисс.

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

Answer 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];
    }
}

Answer 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 очень простых операций, чтобы получить nibble (2), bit-shift (2), bit-shift и add (4) и query (1), и многие из этих операций могут быть сжато дальше благодаря умному использованию сборки. Это может быть быстрее, чем принимать во внимание информацию во время выполнения.

Answer 7

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

Answer 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 следует проанализировать число и вернуть его

Жаль, что это может дать хорошие советы.