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

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, например, М> = 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, и хэш Пирсона обязательно сканирует всю входную строку , Но все примеры ключей на самом деле различаются по своему третьему символу, так что только они могут использоваться в качестве ввода для хеша вместо всей строки. Кроме того, если требуется, чтобы M было не менее char.MaxValue, то третий символ сам по себе становится идеальным хешем.

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

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

Answer 1

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

Answer 2

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

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

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

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

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

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

Answer 3

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

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

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

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

Вам потребуется внести 2 изменения в алгоритм KMP:

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

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

Answer 4

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

Answer 5

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

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 6

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

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 7

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

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

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

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

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 8

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

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

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