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 回答