Как быстро искать строковую коллекцию ключей / значений

Получите ли вы какое-либо преимущество, если бы ваши trie-ключи были сопоставимы с размером машинного регистра? Итак, если вы используете 32-битный бокс, вы можете сравнивать 4 символа одновременно, а не каждый символ по отдельности? Я не знаю, насколько сильно это увеличило бы размер вашего приложения.

Массив суффиксов и индекс q-граммы

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

Это дает вам время выполнения поиска мм> * log п, где мм> - длина вашей строки запроса, а п - общая длина ваших объединенных строк. Если этого все еще недостаточно, и ваш мм> имеет фиксированную небольшую длину, а ваш алфавит Σ ограничен по размеру (скажем, Σ <128 различных символов), вы можете дополнительно создать q-граммовый индекс. Это позволит получить в постоянное время. Однако для таблицы q-граммы требуется Σ^m записей (= 8 МиБ в случае всего 3 символа и 1 ГиБ для 4 символов!).

Уменьшение индекса

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

Кстати, я не уверен, знакомы ли вы с как работает индекс q-грамм, поскольку Интернет не помогает в этой теме. Я уже упоминал об этом ранее в другой теме. Поэтому я включил описание и алгоритм построения в свой диплом бакалавра.

Доказательство концепции

Я написал очень небольшое доказательство концепции на C# (поскольку вы иначе заявили, что работали с C#). Он работает, но работает очень медленно по двум причинам. Во-первых, создание массива суффиксов просто сортирует суффиксы. Только это имеет журнал времени выполнения п²п. Есть гораздо более совершенные методы. Но хуже всего то, что я использую SubString для получения суффиксов. К сожалению, .NET создает для этого копии всего суффикса. Чтобы использовать этот код на практике, убедитесь, что вы используете методы на месте, которые без необходимости не копируют данные. То же самое верно и для извлечения q-граммов из строки.

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

Тем не менее, легко видеть, что эта реализация, по сути, ожидала получения постоянного времени (если словарь ведет себя хорошо)! Это настоящее достижение, которое невозможно превзойти ни одним деревом поиска!

class QGramIndex {
    private readonly int m_Maxlen;
    private readonly string m_Data;
    private readonly int m_Q;
    private int[] m_SA;
    private Dictionary<string, int> m_Dir = new Dictionary<string, int>();

    private struct StrCmp : IComparer<int> {
        public readonly String Data;
        public StrCmp(string data) { Data = data; }
        public int Compare(int x, int y) {
            return string.CompareOrdinal(Data.Substring(x), Data.Substring(y));
        }
    }

    private readonly StrCmp cmp;

    public QGramIndex(IList<string> strings, int maxlen, int q) {
        m_Maxlen = maxlen;
        m_Q = q;

        var sb = new StringBuilder(strings.Count * maxlen);
        foreach (string str in strings)
            sb.AppendFormat(str.PadRight(maxlen, '\u0000'));
        m_Data = sb.ToString();
        cmp = new StrCmp(m_Data);
        MakeSuffixArray();
        MakeIndex();
    }

    public int this[string s] { get { return FindInIndex(s); } }

    private void MakeSuffixArray() {
        // Approx. runtime: n^3 * log n!!!
        // But I claim the shortest ever implementation of a suffix array!
        m_SA = Enumerable.Range(0, m_Data.Length).ToArray();
        Array.Sort(m_SA, cmp);
    }

    private int FindInArray(int ith) {
        return Array.BinarySearch(m_SA, ith, cmp);
    }

    private int FindInIndex(string s) {
        int idx;
        if (!m_Dir.TryGetValue(s, out idx))
            return -1;
        return m_SA[idx] / m_Maxlen;
    }

    private string QGram(int i) {
        return i > m_Data.Length - m_Q ?
            m_Data.Substring(i) :
            m_Data.Substring(i, m_Q);
    }

    private void MakeIndex() {
        for (int i = 0; i < m_Data.Length; ++i) {
            int pos = FindInArray(i);
            if (pos < 0) continue;
            m_Dir[QGram(i)] = pos;
        }
    }
}

Пример использования:

static void Main(string[] args) {
    var strings = new [] { "hello", "world", "this", "is", "a",
                           "funny", "test", "which", "i", "have",
                           "taken", "much", "too", "far", "already" };

    var index = new QGramIndex(strings, 10, 3);

    var tests = new [] { "xyz", "aki", "ake", "muc", "uch", "too", "fun", "est",
                         "hic", "ell", "llo", "his" };

    foreach (var str in tests) {
        int pos = index[str];
        if (pos > -1)
            Console.WriteLine("\"{0}\" found in \"{1}\".", str, strings[pos]);
        else
            Console.WriteLine("\"{0}\" not found.", str);
    }
}

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

Вам понадобятся 2 дерева; 1-й - это хеш-значение для объекта домена. 2-е дерево - это строки поиска по хеш-значению. второе дерево имеет несколько ключей к одному и тому же хеш-значению.

Пример дерево 1: STCKVRFLW -> объект домена

дерево 2: стек -> STCKVRFLW, STCK над -> STCKVRFLW, VRBRD, VR

Таким образом, использование поиска по 2-му дереву дает вам список ключей для поиска по 1-му дереву.

Вот вам ВАГ. Я НИ В КОЕМ СЛУЧАЕ Кнуттианец в моем алгоритме подкован

Итак, наивный Trie кодирует строковые ключи, начиная с корня дерева и перемещаясь вниз по ветвям, которые соответствуют каждой букве в ключе, начиная с первой буквы ключа. Таким образом, ключ «foo» будет отображен на (root)->f->fo->foo, а значение будет сохранено в месте, на которое указывает узел «foo».

Вы ищете ЛЮБУЮ подстроку в ключе, а не только подстроки, которые начинаются с начала ключа.

Итак, что вам нужно сделать, это связать узел с ЛЮБЫМ ключом, который содержит эту конкретную подстроку. В примере с foo, который я приводил ранее, вы НЕ нашли бы ссылку на значение foo под узлами 'f' и 'fo'. В TST, который поддерживает тот тип поиска, который вы хотите выполнить, вы не только найдете объект foo во всех трех узлах ('f', 'fo' и 'foo'), вы также найдете его. также под «o» и «oo».

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

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

С другой стороны, вы также можете обнаружить, что вы можете сжать дерево с помощью токенизации (как это делает сжатие zip) или путем сжатия узлов, которые не разветвляются вниз (например, если у вас есть 'w' -> 'o' -> ' o '-> и первое' o 'не разветвляется, вы можете смело свернуть его до' w '->' oo '). Может, даже идиотский хеш может упростить задачу ...

Во всяком случае, WAG, как я уже сказал.

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

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

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

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

В новой версии алгоритма таблица q-грамм строится путем обхода массива суффиксов вместо исходных строк. Это сохраняет двоичный поиск в массиве суффиксов. Следовательно, время выполнения конструкции снижается с О (п * log п) до О (п) (где п - размер массива суффиксов).

Обратите внимание, что, как и в моем первом решении, использование SubString приводит к появлению множества ненужных копий. Очевидное решение - написать метод расширения, который создает легкую оболочку вместо копирования строки. Затем сравнение необходимо немного изменить. Это оставлено читателю в качестве упражнения. ;-)

using Position = System.Collections.Generic.KeyValuePair<int, int>;

class QGramIndex {
    private readonly int m_Q;
    private readonly IList<string> m_Data;
    private Position[] m_SA;
    private Dictionary<string, int> m_Dir;

    public QGramIndex(IList<string> strings, int q) {
        m_Q = q;
        m_Data = strings;
        MakeSuffixArray();
        MakeIndex();
    }

    public int this[string s] { get { return FindInIndex(s); } }

    private int FindInIndex(string s) {
        int idx;
        if (!m_Dir.TryGetValue(s, out idx))
            return -1;
        return m_SA[idx].Key;
    }

    private void MakeSuffixArray() {
        int size = m_Data.Sum(str => str.Length < m_Q ? 0 : str.Length - m_Q + 1);
        m_SA = new Position[size];
        int pos = 0;
        for (int i = 0; i < m_Data.Count; ++i)
            for (int j = 0; j <= m_Data[i].Length - m_Q; ++j)
                m_SA[pos++] = new Position(i, j);

        Array.Sort(
            m_SA,
            (x, y) => string.CompareOrdinal(
                m_Data[x.Key].Substring(x.Value),
                m_Data[y.Key].Substring(y.Value)
            )
        );
    }

    private void MakeIndex() {
        m_Dir = new Dictionary<string, int>(m_SA.Length);

        // Every q-gram is a prefix in the suffix table.
        for (int i = 0; i < m_SA.Length; ++i) {
            var pos = m_SA[i];
            m_Dir[m_Data[pos.Key].Substring(pos.Value, 5)] = i;
        }
    }
}

Использование такое же, как в другом примере, за исключением обязательного аргумента maxlen для конструктора.

Чтобы запросить большой набор текста эффективным способом, вы можете использовать концепцию Edit Distance / Prefix Edit Distance.

Edit Distance ED(x,y): minimal number of transfroms to get from x to y

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

Преимущество метода индексации Qgram заключается в том, что он поддерживает Нечеткий поиск.

Одним из возможных подходов к адаптации индекса QGram является построение перевернутого индекса с использованием Qgrams. Там мы храним все слова, которые состоят из определенной Qgram (вместо хранения полной строки вы можете использовать уникальный идентификатор для каждой строки).

col : colmbia, colombo, gancola, tacolama

Затем при запросе мы вычисляем количество общих Qgram между текстом запроса и доступными терминами.

Example: x = HILLARY, y = HILARI(query term)
Qgrams
$$HILLARY$$ -> $$H, $HI, HIL, ILL, LLA, LAR, ARY, RY$, Y$$
$$HILARI$$ -> $$H, $HI, HIL, ILA, LAR, ARI, RI$, I$$
number of q-grams in common = 4

Для терминов с большим количеством общих Qgrams мы вычисляем ED / PED по запросу, а затем предлагаем термин конечному пользователю.

вы можете найти реализацию этой теории в следующем проекте. Не стесняйтесь задавать любые вопросы. https://github.com/Bhashitha-Gamage/City_Search

Чтобы узнать больше о Edit Distance, Prefix Edit Distance Qgram index, пожалуйста, посмотрите следующее видео профессора д-ра Ханны Баст https://www.youtube.com/embed/6pUg2wmGJRo (Урок начинается с 20:06)