大家好，StackOverflow 的朋友们！
我有一个单词列表，包含 200,000 个字符串条目，平均字符串长度约为 30 个字符。这些单词是关键字，对于每个关键字，我都有一个域对象。我想通过只知道关键字的一部分来在此集合中查找域对象。例如，搜索字符串“kov”将匹配关键字“stackoverflow”。
目前，我正在使用三叉搜索树（Ternary Search Tree，TST），通常可以在100毫秒内找到项。但这对我的要求来说还是太慢了。 TST 实现可以通过一些小优化来改进，并且我可以尝试平衡树。但我意识到这些事情并不会使我达到5倍至10倍的速度提升。 我假设之所以如此缓慢是因为我基本上必须访问树中的大多数节点。
有什么想法可以改善算法的速度吗？我应该考虑使用其他算法吗？
谢谢大家， Oskar
如果你的字符串长度有严格的上限，考虑使用后缀数组：将所有字符串都用一个特殊字符（例如空字符）填充到相同的最大长度。然后将所有字符串连接起来，并构建一个后缀数组索引。
这样可以使查询运行时间为m*logn，其中m是查询字符串的长度，n是所有字符串的总长度。如果仍然不够好，并且m具有固定的小长度，并且字母表Σ也很小（比如，Σ<128个不同字符），你还可以构建一个q-gram索引，这将允许在常数时间内检索。但是，q-gram表需要存储Σm个条目（对于只有3个字符的情况，占用8 MiB，对于4个字符则需要1 GiB！）。
通过调整哈希函数，可能可以指数级地减小q-gram表的大小（在最佳情况下）。不是为每个可能的q-gram分配唯一的数字，而是使用有损哈希函数。然后表将必须存储后缀数组索引的可能列表，而不是仅对应于精确匹配的一个后缀数组条目。但这意味着查找不再是常数时间，因为必须考虑列表中的所有条目。
顺便说一下，我不确定你是否熟悉 q-gram索引 的工作原理，因为互联网上对这个主题的信息并不有用。我之前在另一个话题中提到过。因此，在我的学士论文中，我包括了构建的描述和算法。
我写了一个非常小的C#概念验证（因为你表示你也用C#）。它可以工作，但是非常缓慢，原因有两个。首先，后缀数组的创建只是简单地对后缀进行排序。单单这一步就有一个运行时复杂度为n2 log n，而实际上有更好的方法。更糟糕的是，我使用SubString来获取后缀。不幸的是，.NET会为此创建整个后缀的副本。要在实践中使用此代码，请确保使用不会不必要地复制任何数据的原地方法。从字符串中检索q-gram时同样如此。
可能甚至最好不要构造我示例中使用的m_Data字符串。相反，您可以保存对原始数组的引用，并模拟我所有SubString访问，从而在该数组上工作。
尽管如此，很容易看出该实现基本上具有期望恒定时间检索（如果字典表现良好）！这是相当值得称赞的成就，搜索树/trie不可能超越它！
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);
}
}
(root)->f->fo->foo，并且该值将存储在由“foo”节点指向的位置中。您正在搜索键中的任何子字符串，而不仅仅是从键的开头开始的子字符串。因此，您需要将包含该特定子字符串的任何键与节点相关联。在之前给出的foo示例中，您将无法在'f'和'fo'节点下找到foo的值引用。在TST中，如果支持您要执行的类型的搜索，则不仅会在所有三个节点('f'、'fo'和'foo')下找到foo对象，还会在'o'和'oo'下找到它。将搜索树扩展以支持此类索引的效果有几个明显的后果。首先，您刚刚使树的大小爆炸性增长。非常惊人。如果您可以以有效的方式存储并使用它，则您的搜索将花费O(1)的时间。如果您的键保持静态，并且您可以找到一种分区索引的方法，以便您不会在使用它时付出巨大的IO代价，那么这可能会摊销为值得。其次，您将发现搜索小字符串将导致大量命中，这可能使您的搜索无效，除非您将最小长度放在搜索术语上。好处是，您可能还会发现可以通过标记化（如zip压缩所做的那样）或通过压缩不分支的节点（即，如果您有'w'->'o'->'o'->和第一个'o'不分支，则可以将其安全地折叠为'w'->'oo'）。也许甚至可以使用厉害的哈希使事情变得更容易......总之，就像我说的那样，这只是一个猜测。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
如果您的trie键与机器寄存器的大小可比，您会获得任何优势吗？因此，如果您在32位框上，可以一次比较4个字符而不是每个字符单独比较？我不知道这会增加您的应用程序的大小有多糟糕。
是否有可能对键值进行“哈希”？基本上，拥有第二棵树将所有可能的搜索值指向第一棵树中的键列表。
您需要两棵树；第一棵是哈希值到域对象的映射。第二棵树是搜索字符串到哈希值的映射。第二棵树具有多个键到同一个哈希值的映射。
例如： 树1： STCKVRFLW -> 域对象
树2： stack -> STCKVRFLW,STCK over -> STCKVRFLW, VRBRD, VR
因此，在第二棵树上进行搜索会给您提供在第一棵树上搜索的键列表。
选择一个最小的搜索字符串大小（例如四个字符）。遍历您的字符串条目列表，并建立每个四个字符子字符串的字典，映射到出现该子字符串的条目列表。当您进行搜索时，基于搜索字符串的前四个字符进行查找以获取初始集合，然后将该初始集合缩小为仅与完整搜索字符串匹配的条目。
最坏情况下的时间复杂度是O(n)，但只有在您的字符串条目几乎全部相同时才会出现这种情况。查找字典可能会非常大，因此最好将其存储在磁盘上或使用关系数据库 :-)
/编辑：我的一个朋友指出了我构建q-gram表时的一个愚蠢假设。构建可以变得更简单，因此速度更快。我已经编辑了源代码和说明以反映这一点。我认为这可能是最终解决方案。
受Rafał Dowgird对我之前答案的评论的启发，我更新了我的代码。然而，由于它也相当长，我认为这值得一个独立的答案。该代码不是填充现有字符串，而是在原始字符串数组上构建索引。后缀数组存储一对数据而不是单个位置：目标字符串的索引和后缀在该字符串中的位置。结果只需要第一个数字。但是，第二个数字对于构建q-gram表是必要的。
算法的新版本通过遍历后缀数组而不是原始字符串来构建q-gram表。这样可以避免对后缀数组进行二进制搜索。因此，构建的运行时间从O(n * log 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参数。