针对已知密钥集的最快可能的字符串键查找

Question

考虑具有以下签名的查找函数,该签名需要返回给定字符串键的整数:

int GetValue(string key) { ... }

此外,在编写函数的源代码时,事先知道编号为N的键值映射,例如:

// N=3
{ "foo", 1 },
{ "bar", 42 },
{ "bazz", 314159 }

因此,上述输入的函数的有效(但不完美!)实现将是:

int GetValue(string key)
{
    switch (key)
    {
         case "foo": return 1;
         case "bar": return 42;
         case "bazz": return 314159;
    }

    // Doesn't matter what we do here, control will never come to this point
    throw new Exception();
}

事先还知道每个给定密钥在运行时调用该函数的次数(C> = 1).例如:

C["foo"] = 1;
C["bar"] = 1;
C["bazz"] = 2;

但是,此类呼叫的顺序尚不清楚.例如,上面可以描述运行时的以下调用序列:

GetValue("foo");
GetValue("bazz");
GetValue("bar");
GetValue("bazz");

或者任何其他序列,只要呼叫计数匹配.

还有一个限制M,在任何最方便的单位中指定,定义任何查找表的上限内存和其他可以使用的辅助结构GetValue(结构预先初始化;初始化不计入复杂性的功能).例如,M = 100个字符,或M = 256个sizeof(对象引用).

问题是,如何编写GetValue尽可能快的主体- 换句话说,所有GetValue调用的总时间(注意我们知道总数,每个上面的所有内容)是最小的,对于给定的N,C和M？

该算法可能需要M的合理最小值,例如M> = char.MaxValue.它也可能要求M与某个合理的边界对齐 - 例如,它可能只是2的幂.它还可能要求M必须是某种N的函数(例如,它可以允许有效的M = N,或者M = 2N,...;或者有效的M = N,或者M = N ^ 2, ......;等).

该算法可以用任何合适的语言或其他形式表达.对于生成的代码的运行时性能约束,假设生成的代码GetValue将在C#,VB或Java中(实际上,任何语言都可以,只要字符串被视为不可变的字符数组 - 即O(1)长度和O (1)索引,而不提前计算其他数据).此外,为了简化这一点,假设所有密钥的C = 1的答案被认为是有效的,尽管那些涵盖更一般情况的答案是优选的.

关于可能的方法的一些思考

上面显而易见的第一个答案是使用完美的哈希,但找到一个的通用方法似乎并不完美.例如,可以使用Pearson散列为上面的示例数据轻松生成最小完美散列的表,但是每次调用时都必须对输入键进行散列GetValue,并且Pearson散列必须扫描整个输入字符串.但是所有样本键的第三个字符实际上都不同,因此只能将其用作哈希的输入而不是整个字符串.此外,如果要求M至少是char.MaxValue,那么第三个字符本身就变成了完美的哈希.

对于不同的一组键,这可能不再是真的,但是仍然可以在给出精确答案之前减少所考虑的字符数量.此外,在最小完美散列需要检查整个字符串的某些情况下,有可能通过使散列非最小化来减少对子集的查找,或者使其更快(例如,不太复杂的散列函数？) (即M> N) - 为了速度而有效地牺牲空间.

它也可能是传统的散列开始并不是一个好主意,并且更容易构造GetValue一系列条件的主体,这样安排首先检查"变量最大"的字符(一个变化的字符)大多数键),根据需要进一步嵌套检查以确定正确的答案.请注意,此处的"方差"可能会受到每个键被查找的次数的影响(C).此外,分支的最佳结构应该是什么并不总是显而易见的 - 例如,"大多数变量"字符只能让你区分100个中的10个键,但对于剩下的90个那个额外的检查没有必要区分它们,并且平均而言(考虑到C)每个键的检查次数多于不以"变量"字符开头的不同解决方案.然后,目标是确定完美的检查顺序.

Answer 1

您可以使用Boyer搜索，但我认为Trie是一种更有效的方法。您可以修改 Trie 来折叠单词，因为您将键的命中计数设为零，从而减少了您必须执行的搜索次数。您将获得的最大好处是您正在对索引进行数组查找，这比比较快得多。