代码之家 › 专栏 › 技术社区 › Alex

字符串比较算法,相关性,两个字符串有多“相似”

comparison string algorithm

Alex · 技术社区 · 14 年前

我有两个相同数据的信息源(公司),我可以通过一个唯一的ID(合同号)连接在一起。第二个不同的源的存在是因为这两个源是手动独立更新的。所以我有一个还有一家公司姓名在两张桌子里。

我得想出个办法算法这会比较在两个表中 身份证件 ,并按一个变量对所有公司进行排序,该变量指示字符串的不同程度(以突出显示最不同的字符串,并将其放在列表的顶部)。

我看了简单的Levenshtein距离计算算法,但它在字母级,所以我仍然在寻找更好的东西。

JSC "Foo" 这与 Foo JSC. ,但我在数据库中真正要找的是一对不同的字符串,比如 SomeLongCompanyName JSC JSC OtherName

3 回复 | 直到 14 年前

TonyK 14 年前

怎么样:
1用空格替换所有标点符号。
2将字符串拆分为空格分隔的单词。
三。将<=4个字符的所有单词移到末尾,按字母顺序排序。
4列文施坦。

Thomas Mueller 14 年前

作为另一种选择,或者除了Levenshtein距离之外,您可以使用 Soundex . 它不是很好,但是可以用来索引数据(这在使用Levenshtein时是不可能的)。

Alex 14 年前

谢谢你们的建议。我使用了4个索引,它们是levenshtein距离除以两个单词的长度之和(相对距离),如下所示:

将单词序列分开,去掉非单词字符,按升序排序,以空格作为分隔符,由结果组成的字符串。
包含在引号之间的字符串(如果不存在此类字符串,则取原始字符串)
由每个单词的首字母顺序组成的字符串。

作为回报,每个值都是1到1000之间的整数值。结果值是以下各项的乘积:
X1^E1 * X2^E2 * X3^E3 * X4^E4
其中X1..X4是索引,E1..E4是用户提供的首选项,其中有价值(重要)是每个索引。为了使结果保持在1..1000的合理值内,对向量(E1..E4)进行归一化。

结果令人印象深刻。整个程序的运行速度比我预期的要快得多(在C#for Microsoft SQL Server 2008中将其构建为CLR程序集)。正确选取E1..E4后,整个数据库中非空值的最大索引(最大差异)为765。直到大约300年,几乎没有匹配的公司名称。大约有200家公司有类似的名字,有些公司的名字是相同的,但写的方式非常不同,有缩写、附加词等。当它减少到100个或更少时,几乎所有的记录都包含相同的名字,但写的略有不同,到30个,只有顺序或标点符号可能会有所不同。
完全有效,结果比我预期的好。

我写道 a post on my blog ,以共享此库,以防其他人需要它。