4

我的问题：

我正在寻找一种将人的姓名和地址表示为编码 id 的方法。id 应仅包含字母数字字符，防冲突，并以尽可能少的字符数表示。我的第一个想法是简单地使用像 MD5 或 SHA1 这样的加密哈希函数，但这似乎有点矫枉过正（安全性并不重要 - 不需要是单向的），我更愿意找到能产生较短的身份证。有谁知道适合这个问题的现有算法？

换句话说，实现以下函数的最佳方法是什么，以使相同输入的返回值始终相同，不太可能发生冲突，并且 id 小于 20 个字符？

>>> make_fake_id(fname = 'Oscar', lname = 'Grouch', stnum = '1', stname = 'Sesame', zip = '12345')
N1743123734

应用程序上下文（对于那些感兴趣的人）：

这将用于记录链接应用程序。给定一个输入名称和地址，我们在一个非常大的数据库中搜索最佳匹配并返回数据库 id 和其他数据（我们如何做到这一点在这里并不重要）。如果没有匹配项，我需要从搜索输入（实体的名称和地址数据）生成这个伪/生成/派生的 id。每条搜索记录都应该产生一个输出记录，其中要么是真实的（匹配/链接产生的实际数据库 id），要么是这个生成的伪/生成/派生 id。伪 id 将以一个字符（例如 N）作为前缀，以将其与真实 id 区分开来。

4

6 回答 6

5

我知道你对 MD5 和 SHA1 说不，但我认为你还是应该考虑它们。除了经过充分研究的散列算法外，长度还可以为您提供更多防止可能发生的冲突的保护。没有哈希是防冲突的，但加密的通常比你自己想出的更不容易发生冲突。

于 2008-12-01T18:23:58.313 回答
3
  • 使用加密散列是因为它的抗碰撞性，而不是它的其他特性。
  • 使用尽可能多的哈希字节（截断）
  • 转换为字母数字字符
  • 您还可以截断字母数字字符串而不是哈希

一种简单的方法：散列数据，以 base64 编码，删除所有非字母数字字符，截断。

N_HASH_CHARS = 11
import hashlib, re
def digest(name, address):
  hash = hashlib.md5(name + "|" + address).digest().encode("base64")
  alnum_hash = re.sub(r'[^a-zA-Z0-9]', "", hash)
  return alnum_hash[:N_HASH_CHARS]

您应该保留多少个字母数字字符？每个字符为您提供大约 5.95 位的熵 (log(62,2))。11 个字符为您提供 65.5 位的熵，这足以避免前 2**32.7 个用户（约 70 亿）的冲突。

于 2008-12-03T07:03:00.930 回答
0

我同意另一张建议序列号的海报。OTOH，如果您真的，真的真的想做其他事情：

从数据中创建一个 SHA1 哈希，并将其存储在带有序列号字段的表中。

然后，当你得到数据，计算哈希，查表，得到序列号，这就是你的id。如果它不在桌子上，请将其插入。

于 2008-12-02T14:40:02.927 回答
0

我想知道您是否打算将这些 ID“分配”给用户？如果是这样，我希望您的用户讨厌您提出的任何建议；谁会想要“AAAAA01”的用户 ID？

因此，如果这些 id 对用户可见，那么您应该让他们选择他们喜欢的并检查它们的唯一性（简单）。如果它们对用户不可见（例如，内部主键），那么只需使用适当的技术（如 Oracle 序列或 SQL Server 自动编号）按顺序生成它们（也很容易）。

如果这些 id 试图检测注册多次的用户，那么我同意您应该考虑加密哈希，然后对注册数据（姓名、地址等）进行完整比较。但是，为了可用，您需要在计算散列或进行比较之前将数据转换为规范形式（标准化字母大小写、空格、规范街道地址等）。否则，您将基于微不足道的差异而失配。

编辑：现在我根据您的编辑更好地理解了问题空间，我认为您的算法（到目前为止）不太可能捕获大多数匹配项。除了我对输入进行规范化的建议之外，我建议您考虑一种方法，该方法会产生少数可能匹配的排名列表（如果可能，由人工解决），而不是在单个匹配上尝试全有或全无. 换句话说，我推荐一种搜索方法而不是查找方法。

在你的情况下这可行吗？

于 2008-12-01T18:52:35.463 回答
0

一个好的解决方案在某种程度上取决于您的应用程序。你知道有多少用户以及所有用户的集合是什么吗？如果您提供更多详细信息，您将获得更好的帮助。

于 2008-12-01T18:57:48.430 回答
-1

好吧，如果在同一个地址有多个同名的人，你就完蛋了，（不添加代码来检测这一点并添加某种鉴别器）。

但假设不是这个问题，那么完整地址的街道地址和邮政编码部分足以保证那里的唯一性，因此从名称中添加足够的数据应该可以解决这个问题......

您是否有权访问数据库或其他持久性机制，您可以在其中为每个地址生成和维护键值？然后将地址和各个实体保存在两个键控字典结构中，其中键是为每个新的不同地址、遇到的人自动生成的……然后使用自动生成的字母数字键……

You could use AAAAA01  for first person at first address,
              AAAAA02 for second person at first address,
              AAAAB07 for the seventh resident at the second adresss, etc.

如果您没有任何方法来生成和维护这些实体键映射，那么您需要使用完整的街道地址/Zip 和 fullNAme，或者相同的哈希值，尽管哈希值方法生成重复的可能性很小。 ..

于 2008-12-01T18:24:27.860 回答