类似于Soundex、Metaphone等功能的数值变换算法

Question

我正在为个人记录搜索实现概率匹配。作为其中的一部分，我计划在完成任何得分之前执行阻塞操作。目前，有许多很好的转换字符串的选项，以便可以存储并搜索字符串，使用类似的字符串相互匹配(如soundex、metaphone等)。

然而，对于纯粹的数值，我很难找到类似的东西。例如，如果能够阻止一个社会保险号码，而没有从结果中移除掉或有转置数字的数字，那就太好了。123456789应该有123456780或213456789的阻塞结果。

现在，当然有一些方法可以简单地比较两个数值来确定它们有多相似，但是当数据库中有上百万个数字时，我能做些什么呢？显然，比较它们都是不切实际的(这肯定会使阻塞点失效)。

更好的是，上面这三个SSN可以以某种方式转换为存储的其他值。纯粹的例子，想象这三个数字在这个神奇的转变之后最终变成了AAABBCCC。然而，类似于987654321的是ZZZYYYYXX，123547698将是AAABCCBC或类似的东西。

那么，我的问题是，数字值是否有一个很好的转换，就像字母值的存在一样？或者，除了一些高复杂度或低性能的SQL或逻辑之外，还有其他可能有意义的方法吗？

Answer 1

首先要认识到的是，社会保障数字基本上是一串数字。你真的想像对待字符串而不是数字一样对待它们。

需要认识到的第二件事是，您的阻塞函数将从一个记录映射到一个字符串列表，这些字符串标识有价值的比较项集。

下面是一些Python代码，可以让您开始工作。(我知道您要求Java，但我认为Python是明确的，您没有给我足够的钱来用Java :P编写它)。其基本思想是获取输入记录，以多种方式模拟粗化(获取阻塞键)，然后按这些阻塞键上的任意匹配进行分组。

import itertools

def transpositions(s):
  for pos in range(len(s) - 1):
    yield s[:pos] + s[pos + 1] + s[pos] + s[pos + 2:]

def substitutions(s):
  for pos in range(len(s)):
    yield s[:pos] + '*' + s[pos+1:]

def all_blocks(s):
  return itertools.chain([s], transpositions(s), substitutions(s))

def are_blocked_candidates(s1, s2):
  return bool(set(all_blocks(s1)) & set(all_blocks(s2)))

assert not are_blocked_candidates('1234', '5555')
assert are_blocked_candidates('1234', '1239')
assert are_blocked_candidates('1234', '2134')
assert not are_blocked_candidates('1234', '1255')