algorithm - 从具有容错性的多个值生成唯一 ID

Question

给定一些值，我想得到一个(非常该死的)独特的结果。

$unique1 = generate(array('ab034', '981kja7261', '381jkfa0', 'vzcvqdx2993883i3ifja8', '0plnmjfys'));
//now $unique1 == "sqef3452y";

我还需要一些非常接近的东西来返回相同的结果。在这种情况下，缺少 20% 的值。

$unique2 = generate(array('ab034', '981kja7261', '381jkfa0', 'vzcvqdx2993883i3ifja8'));
//also $unique2 == "sqef3452y";

我不确定从哪里开始使用这样的算法，但我有一些假设。

1. 我假设给出的值越多，得到的 ID 就越准确——换句话说，使用 20 个值比 5 个好。
2. 我还假设可以计算和调整置信度。

最好有一个权重因子，可以说“值 1 比值 3 更重要”。这将需要一个多维数组而不是一维输入。

我只是在键盘上敲打这些值，但实际上它们可能是短字母数字值或长字母数字值。

Answer 1

您的两个要求似乎有点矛盾。如果数组的最后 20% 不重要(即，如果它等于“0plnmjfys”或为空，您希望获得相同的结果)那么为什么要首先包含它？

第一步是澄清您想消除歧义的内容。如果它不重要，就放弃它。

一旦你决定了这一点，你就必须问问自己，你是否期望两个“接近”的结果具有“接近”的 ID……也就是说，也许你想要

$unique1 = generate(array('ab034', '981kja7261', '381jkfa0', 'vzcvqdx2993883i3ifja8', '0plnmjfys'));
//now $unique1 == "sqef3452y";

$unique1 = generate(array('ab034', '981kja7261', '381jkfa0', 'vzcvqdx2993883i3ifja8', '0plSsa45'));
//now $unique1 == "sqef3452k";

后者比较棘手，因为大多数唯一 ID 生成器使用 hashes (您可能也想查看这些内容)因此两个非常相似的字符串可能会返回截然不同的结果。

如果您想确保唯一性并且不关心结果是否“接近”，只需计算连接字符串的哈希值，或计算每个输入字符串的哈希值并连接哈希码。

如果您想赋予“亲近度”特权，您可以计算最相关部分的哈希值并应用 Soundex algorithm或其他不太相关的部分的类似内容。

请记住，您在这方面有相互冲突的要求:唯一 ID 非常努力地尝试为字符串提供(疯狂地)不同的代码，即使唯一的区别是 1000 个字符的字符串中的一个字符。

Closeness(这个字符串与第二个字符串“大致相同”)试图做完全相反的事情，并希望为两个字符串返回相同的代码:引用维基百科关于 Soundex 算法:

Using this algorithm, both "Robert" and "Rupert" return the same string "R163" while "Rubin" yields "R150". "Ashcraft" and "Ashcroft" both yield "A261".

那么……哪个是哪个？您认为对前 4 个元素(在您的示例中)使用散列并在您的示例中对最不重要的 20% 使用 Soundex 有效吗？

这可能会导致(回到您的示例)类似的结果:

$unique2 = generate(array('ab034', '981kja7261', '381jkfa0', 'vzcvqdx2993883i3ifja8',));
//now $unique2 == "AB67R45-000000";

$unique1 = generate(array('ab034', '981kja7261', '381jkfa0', 'vzcvqdx2993883i3ifja8', '0plSsa45'));
//now $unique2 == "AB67R45-012000";