如何快速搜索基于字符串的键/值集合

Question

你好伙伴stackoverflowers!

我有200.000个字符串条目的单词列表,平均字符串长度大约30个字符.这个单词列表是关键,每个键都有一个域对象.我想通过只知道密钥的一部分来找到此集合中的域对象.IE搜索字符串"kov"将例如匹配密钥"stackoverflow".

目前我正在使用三元搜索树(TST),它通常会在100毫秒内找到项目.然而,这对我的要求来说太慢了.可以通过一些小的优化来改进TST实现,我可以尝试平衡树.但我认为这些东西不会给我5x - 10x的速度提升我的目标.我假设这么慢的原因是我基本上必须访问树中的大多数节点.

关于如何提高算法速度的任何想法？我还应该关注其他算法吗？

在此先感谢,奥斯卡

Answer 1

后缀数组和q -gram索引

如果您的字符串在大小上有严格的上限,您可以考虑使用后缀数组:只需使用特殊字符(例如null char)将所有字符串填充到相同的最大长度.然后连接所有字符串并在它们上构建后缀数组索引.

这为您提供了m*log n的查找运行时,其中m是查询字符串的长度,n是组合字符串的总长度.如果这仍然不够好并且你的m具有固定的小长度,并且你的字母Σ的大小受限(比如,Σ<128个不同的字符),你还可以建立一个q -gram索引.这将允许在恒定时间内进行检索.然而,q -gram表需要Σ ^米条目(= 8 MIB中的仅3个字符的情况下,和1吉布为4个字符!).

使索引更小

通过调整哈希函数,可以减小q -gram表的大小(在最好的情况下以指数方式).您可以使用有损哈希函数,而不是为每个可能的q -gram 分配唯一编号.然后,该表必须存储可能的后缀数组索引的列表,而不是仅存储对应于完全匹配的一个后缀数组条目.但这将导致查找不再是常量,因为必须考虑列表中的所有条目.

顺便说一下,我不确定你是否熟悉q -gram索引是如何工作的,因为互联网对这个主题没有帮助.我之前在另一个话题中提到了这一点.因此,我在学士论文中加入了描述和算法.

概念证明

我写了一个非常小的C#概念证明(因为你另有说明你使用过C#).它有效,但由于两个原因它很慢.首先,后缀数组创建只是对后缀进行排序.仅此一项就具有运行时n ² log n.有很多优越的方法.然而,更糟糕的是我SubString用来获取后缀.不幸的是,.NET为此创建了整个后缀的副本.要在实践中使用此代码,请确保使用不会不必要地复制任何数据的就地方法.从字符串中检索q -grams 也是如此.

不构造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);
    }
}

Answer 2

如果您的 trie 键与机器寄存器的大小相当，您会获得任何优势吗？那么，如果您使用的是 32 位机器，您可以一次比较 4 个字符，而不是单独比较每个字符吗？我不知道这会增加你的应用程序的大小有多糟糕。