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

Ответ 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, он должен разобрать номер и вернуть его

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