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

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

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

РЕДАКТИРОВАНИЕ/: мой друг просто указал на глупое предположение в моей конструкции таблицы q-грамма. Конструкция может быть сделана намного более простым †“и следовательно, намного быстрее. Я отредактировал исходный код и объяснение для отражения этого. Я думаю, что это могло бы быть конечное решение .

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

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

Уведомление, что, как мое первое решение, использование 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 аргумент в пользу конструктора.