16

考虑一个具有以下签名的查找函数，它需要为给定的字符串键返回一个整数：

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(object reference)。

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

该算法可能需要 M 的合理最小值，例如 M >= char.MaxValue。它还可能要求 M 与某个合理的边界对齐——例如，它可能只是 2 的幂。它还可能要求 M 必须是某种 N 的函数（例如，它可能允许有效的 M=N，或 M=2N，...；或有效的 M=N，或 M=N^2， ...; ETC）。

该算法可以用任何合适的语言或其他形式来表达。对于生成代码的运行时性能约束，假设生成的代码GetValue将使用 C#、VB 或 Java（实际上，任何语言都可以，只要字符串被视为不可变的字符数组 - 即 O(1) 长度和 O (1) 索引，并且没有预先为它们计算的其他数据）。此外，为了简化这一点，假设所有键的 C=1 的答案被认为是有效的，尽管那些涵盖更一般情况的答案是首选。

关于可能方法的一些思考

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

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

也可能是传统的散列一开始就不是一个好主意，而且更容易将主体构造GetValue为一系列条件，排列成第一个检查“最可变”的字符（那个在大多数键），并根据需要进行进一步的嵌套检查以确定正确答案。请注意，此处的“方差”可能会受到每个键将被查找的次数的影响 (C)。此外，最好的分支结构应该是什么并不总是很明显 - 例如，可能是“最可变”字符只能让您区分 100 个键中的 10 个，但对于剩余的 90 个键，需要额外检查无需区分它们，不以“最易变”的字符开头。然后，目标是确定完美的检查顺序。

4

8 回答 8

4

您谈到了预计算时的内存限制 - 是否也有时间限制？

我会考虑使用 trie，但不一定要从第一个字符开始。相反，找到最能减少搜索空间的索引，并首先考虑这一点。因此，在您的示例案例（“foo”、“bar”、“bazz”）中，您将采用第三个字符，它会立即告诉您它是哪个字符串。（如果我们知道我们总是会得到一个输入词，我们可以在找到唯一的潜在匹配项后立即返回。）

现在假设没有一个索引可以让你找到一个唯一的字符串，你需要确定之后要查看的字符。从理论上讲，您预先计算 trie 来为每个分支计算出接下来要查看的最佳字符是什么（例如，“如果第三个字符是 'a'，我们需要接下来查看第二个字符；如果是 'o'，我们接下来需要看第一个字符），但这可能需要更多的时间和空间。另一方面，它可以节省很多时间 - 因为已经下降了一个字符，每个分支都可能有一个索引可供选择，该索引将唯一标识最终字符串，但每次都是不同的索引。这种方法所需的空间量取决于字符串的相似程度，并且可能难以提前预测。能够为所有可能的 trie 节点动态地执行此操作会很好，但是当您发现构建空间不足时，请确定“此节点下的所有内容”的单个顺序。（因此，您最终不会在该节点下的每个节点上存储“下一个字符索引”，而只是单个序列。）如果不清楚，请告诉我，我可以尝试详细说明...

如何表示 trie 将取决于输入字符的范围。如果它们都在 'a'-'z' 范围内，那么一个简单的数组的导航速度将非常快，并且对于大多数可用选项都有可能的 trie 节点来说相当有效。稍后，当只有两个或三个可能的分支时，这会浪费内存。我建议使用多态 Trie 节点类，这样您就可以根据有多少子分支构建最合适的节点类型。

这些都不会执行任何剔除 - 目前尚不清楚通过快速剔除可以实现多少。我可以看到它有帮助的一种情况是，当来自一个 trie 节点的分支数量下降到 1（因为删除了一个用尽的分支）时，可以完全消除该分支。随着时间的推移，这可能会产生很大的不同，并且不应该太难计算。基本上，在构建trie 时，您可以预测每个分支将被占用多少次，并且在导航trie 时，您可以在导航时从每个分支的计数中减去一个。

到目前为止，这就是我想出的全部内容，而且它并不完全是一个完整的实现——但我希望它会有所帮助......

于 2011-07-29T20:05:56.283 回答
4

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

于 2011-07-16T02:49:54.927 回答
0

表的二分查找真的那么糟糕吗？我将获取潜在字符串列表并“最小化”它们，对它们进行排序，最后对它们的块进行二进制搜索。

通过最小化，我的意思是将它们减少到它们需要的最低限度，一种自定义的词干。

例如，如果您有以下字符串：“alfred”、“bob”、“bill”、“joe”，我会将它们分解为“a”、“bi”、“bo”、“j”。

然后将它们放入连续的内存块中，例如：

char *table = "a\0bi\0bo\0j\0"; // last 0 is really redundant..but
char *keys[4];
keys[0] = table;
keys[1] = table + 2;
keys[2] = table + 5;
keys[3] = table + 8;

理想情况下，如果您只需执行以下操作，编译器就会为您完成所有这些工作：

keys[0] = "a";
keys[1] = "bi";
keys[2] = "bo";
keys[3] = "j";

但我不能说这是真的还是假的。

现在您可以搜索该表，并且键尽可能短。如果您击中键的末尾，则匹配。如果没有，则遵循标准的 bsearch 算法。

目标是将所有数据紧密结合在一起，并使代码保持精简，以使其全部适合 CPU 缓存。您可以直接从程序处理密钥，无需预处理或添加任何内容。

对于合理分布的相当大量的密钥，我认为这会非常快。这实际上取决于所涉及的字符串数量。对于较小的数字，计算哈希值等的开销不仅仅是搜索这样的东西。对于更大的值，这是值得的。这些数字是多少取决于算法等。

但是，如果这很重要的话，这可能是内存方面最小的解决方案。

这也有简单的好处。

附加物：

除了“字符串”之外，您没有任何关于输入的规范。也没有讨论您希望使用多少字符串、它们的长度、它们的共性或使用频率。这些也许都可以从“源”派生，但不是算法设计者计划的。您正在要求一种创建如下内容的算法：

inline int GetValue(char *key) {
    return 1234;
}

对于一个碰巧一直只使用一个键的小程序，一直到为数百万个字符串创建完美哈希算法的东西。这是一个相当高的要求。

任何追求“尽可能提高性能”的设计都需要比“任何和所有字符串”更多地了解输入。如果您希望它在任何情况下都尽可能快，那么这个问题空间就太大了。

处理具有极长相同前缀的字符串的算法可能与处理完全随机字符串的算法完全不同。该算法可以说“如果密钥以“a”开头，则跳过接下来的 100 个字符，因为它们都是 a 的。

但是，如果这些字符串是由人类提供的，并且他们使用相同字母的长字符串，并且没有疯狂地试图维护这些数据，那么当他们抱怨算法性能不佳时，你会回答“你是做傻事，不要那样做”。但我们也不知道这些字符串的来源。

因此，您需要选择一个问题空间来定位算法。我们有各种各样的算法，表面上做同样的事情，因为它们解决了不同的约束并且在不同的情况下工作得更好。

散列很昂贵，布置散列图很昂贵。如果没有足够的数据，还有比散列更好的技术。如果您有大量内存预算，您可以根据每个节点的 N 个状态创建一个巨大的状态机（N 是您的字符集大小 - 您没有指定 - BAUDOT？7 位 ASCII？UTF-32？） . 这将运行得非常快，除非状态消耗的内存量会破坏 CPU 缓存或挤出其他东西。

您可能会为所有这些生成代码，但您可能会遇到代码大小限制（您也没有说什么语言——例如，Java 有 64K 方法字节码限制）。

但是您没有指定任何这些约束。因此，很难获得满足您需求的性能最高的解决方案。

于 2011-07-16T05:13:22.923 回答
0

我认为这一切都是为了找到正确的哈希函数。只要事先知道键值关系是什么，就可以进行分析，尝试找到满足自己需求的哈希函数。以您提供的示例为例，将输入字符串视为二进制整数：

foo  = 0x666F6F (hex value)
bar  = 0x626172
bazz = 0x62617A7A

所有这些中存在的最后一列在每个中都不同。进一步分析：

foo  = 0xF = 1111
bar  = 0x2 = 0010
bazz = 0xA = 1010

向右移位两次，丢弃溢出，你会为它们中的每一个得到一个不同的值：

foo  = 0011
bar  = 0000
bazz = 0010

再次向右移位两次，将溢出添加到新缓冲区： foo = 0010 bar = 0000 bazz = 0001

您可以使用它们来查询静态 3 条目查找表。我认为这个高度个人化的散列函数需要 9 个非常基本的操作来获得半字节 (2)、位移 (2)、位移和加法 (4) 和查询 (1)，并且很多这些操作都可以通过巧妙的装配使用进一步压缩。这可能比考虑运行时信息要快。

于 2011-07-30T00:15:09.567 回答
0

你想要的是一个查找表的查找表。如果内存成本不是问题，您可以全力以赴。

const int POSSIBLE_CHARCODES = 256; //256 for ascii //65536 for unicode 16bit
struct LutMap {
    int value;
    LutMap[POSSIBLE_CHARCODES] next;
}
int GetValue(string key) {
    LutMap root = Global.AlreadyCreatedLutMap;
    for(int x=0; x<key.length; x++) {
        int c = key.charCodeAt(x);
        if(root.next[c] == null) {
            return root.value;
        }
        root = root.next[c];
    }
}
于 2011-07-28T18:02:29.373 回答
0

你看过TCB吗？也许那里使用的算法可用于检索您的值。这听起来很像您要解决的问题。根据经验，我可以说 tcb 是我使用过的最快的密钥库查找之一。这是一个恒定的查找时间，与存储的键数无关。

于 2011-07-30T07:18:21.753 回答
0

考虑使用Knuth-Morris-Pratt 算法。

预处理给定的映射到一个大字符串，如下所示

String string = "{foo:1}{bar:42}{bazz:314159}";
int length = string.length();

根据 KMP 的预处理时间，string将花费O(length). 使用任何单词/键进行搜索都会很O(w)复杂，w单词/键的长度在哪里。

您将需要对KMP算法进行 2 处修改：

  • 键应按顺序出现在连接中string
  • 而不是返回真/假，它应该解析数字并返回它

希望它能给一个很好的提示。

于 2011-07-31T20:18:20.040 回答
0

这是确定哈希例程目标的最小字符子集的可行方法：

让：
k 是所有关键字中不同字符的数量
c 是最大关键字长度
n 是
示例中的关键字数（填充较短的关键字 w/空格）：

"foo "
"bar "
"bazz"

k = 7 (f,o,b,a,r,z, ), c = 4, n = 3

我们可以使用它来计算搜索的下限。我们至少需要 log_k(n) 个字符来唯一标识一个关键字，如果 log_k(n) >= c 那么您将需要使用整个关键字并且没有理由继续。

接下来，一次删除一列并检查是否还有 n 个不同的值剩余。使用每列中不同的字符作为启发式来优化我们的搜索：

2 2 3 2
f o o .
b a r .
b a z z

首先消除具有最低不同字符的列。如果您还有 <= log_k(n) 列，您可以停止。或者，您可以随机化一点并消除第二低的不同 col，或者如果消除的 col 导致少于 n 个不同的单词，则尝试恢复。该算法大致为 O(n!)，具体取决于您尝试恢复的程度。不能保证找到最佳解决方案，但这是一个很好的权衡。

一旦你有了你的字符子集，继续使用通常的例程来生成一个完美的哈希。结果应该是最佳的完美哈希。

于 2011-07-16T02:51:27.077 回答