后缀数组和q -gram 索引
如果您的字符串对大小有严格的上限，您可能会考虑使用后缀数组：只需使用特殊字符（例如空字符）将所有字符串填充到相同的最大长度。然后连接所有字符串并在它们之上建立一个后缀数组索引。
这为您提供了m * log n的查找运行时间，其中m是查询字符串的长度，n是组合字符串的总长度。如果这仍然不够好并且您的m具有固定的小长度，并且您的字母 Σ 的大小受到限制（例如，Σ < 128 个不同的字符），您可以另外构建一个q -gram index。这将允许在恒定时间内检索。但是，q -gram 表需要 Σ m个条目（在 3 个字符的情况下 = 8 MiB，4 个字符的情况下为 1 GiB！）。
使索引更小
可以通过调整散列函数来减小q -gram 表的大小（在最好的情况下是指数的）。您可能会使用有损散列函数，而不是为每个可能的q -gram分配唯一编号。然后，该表必须存储可能的后缀数组索引列表，而不是仅存储一个与精确匹配相对应的后缀数组条目。但是，这将需要查找不再是恒定的，因为必须考虑列表中的所有条目。
顺便说一句，我不确定您是否熟悉q -gram索引的工作原理，因为 Internet 对这个主题没有帮助。我之前在另一个主题中提到过这一点。因此，我在我的学士论文中包含了构造的描述和算法。
概念证明
我已经编写了一个非常小的 C# 概念证明（因为您另外声明您使用 C#）。它可以工作，但是由于两个原因它非常慢。首先，后缀数组创建只是对后缀进行排序。仅此一项就有运行时n 2 log n。有很多优越的方法。SubString然而，更糟糕的是我用来获取后缀的事实。不幸的是，.NET 为此创建了整个后缀的副本。要在实践中使用此代码，请确保使用不会不必要地复制任何数据的就地方法。从字符串中检索q -gram 也是如此。
不构造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);
}
}