在 .NET 中实现 SoundEx

• 下载源文件 - 136 Kb

引言

每个计算机科学家都听说过 SoundEx。 它可能是最臭名昭著的文本处理/搜索算法。 SoundEx 承诺很多——匹配发音相似的单词，但实际上，最多只能提供大量不准确的匹配。 尽管 SoundEx 已获得专利，但由于对该算法的理解不足或试图提高其准确性，也出现了一些变体。 因此，本文介绍了用 C# 和 .Net 编写的 SoundEx 的四种流行实现，以便您可以在自己的数据集上执行您自己的基准测试。

SoundEx 最初的发明是为了找到姓氏的替代拼写。 问题源于美国人口普查报告中的拼写错误，因此 SoundEx 算法偏向于英语名称。 还有一些针对某些西欧语言的变体，但总的来说，该算法从未被认为是所有模糊文本匹配的万能药。

大多数 SoundEx 算法都是以下内容的变体

• 保留姓名的第一个字母
• 删除所有元音，以及 h、y（第一个字母除外）
• 用数字 1 替换 b, f, p, v
• 用数字 2 替换 c, g, j, k, q, s, x, z
• 用数字 3 替换 d 和 t
• 用 4 替换 l，用 5 替换 m 和 n，用 6 替换 r
• 最后，通过截断转换为 4 个字符的代码，例如 {字母}{数字}{数字}{数字}

一些算法除了分组和相邻字母规则外，还有其他规则。

实现细节

几个相同的算法的实现意味着策略模式，因此创建了一个名为 ISoundEx 的公共基类。 四个实现是

• Miracode - 1910 年修改后的 SoundEx
• Simplified - 1800 年代后期原始的 SoundEx
• KnuthEd2 - The Art of Computer Programming 中的 SoundEx 算法
• SQLServer - SQL Server 的 SoundEx 变体

每个都实现了 GenerateSoundEx() 和 ValidateAlgorithm()。 ISoundEx 的虚拟成员是 EncodeChar()，它提供了 SoundEx 指定的基本字符到数字的映射。

protected virtual string EncodeChar(char c) {
	// C# will re-order this list and produce a look-up list from it
	// C# will do all the work we would otherwise do by building arrays of values
	switch(Char.ToLower(c)) {
		case 'b':
		case 'f':
		case 'p':
		case 'v':
			return "1";
		case 'c':
		case 'g':
		case 'j':
		case 'k':
		case 'q':
		case 's':
		case 'x':
		case 'z':
			return "2";
		case 'd':
		case 't':
			return "3";
		case 'l':
			return "4";
		case 'm':
		case 'n':
			return "5";
		case 'r':
			return "6";
		default:
			return string.Empty;
	}
}

对 MSIL 的一个补充

C# 如何编译 switch 语句，例如 EncodeChar() 本身就可以是一篇文章。 为了演示它应用的优化，请查看下面的 CIL 反汇编。

.method family hidebysig newslot virtual
        instance string  EncodeChar(char c) cil managed
{
  // Code size       176 (0xb0)
  .maxstack  2
  .locals ([0] string CS$00000003$00000000,
           [1] char CS$00000002$00000001)
  IL_0000:  ldarg.1
  IL_0001:  call       char [mscorlib]System.Char::ToLower(char)
  IL_0006:  stloc.1
  IL_0007:  ldloc.1
  IL_0008:  ldc.i4.s   98
  IL_000a:  sub
  IL_000b:  switch     (
                        IL_0076,
                        IL_007e,
                        IL_0086,
                        IL_00a6,
                        IL_0076,
                        IL_007e,
                        IL_00a6,
                        IL_00a6,
                        IL_007e,
                        IL_007e,
                        IL_008e,
                        IL_0096,
                        IL_0096,
                        IL_00a6,
                        IL_0076,
                        IL_007e,
                        IL_009e,
                        IL_007e,
                        IL_0086,
                        IL_00a6,
                        IL_0076,
                        IL_00a6,
                        IL_007e,
                        IL_00a6,
                        IL_007e)
  IL_0074:  br.s       IL_00a6
  IL_0076:  ldstr      "1"
  IL_007b:  stloc.0
  IL_007c:  br.s       IL_00ae
  IL_007e:  ldstr      "2"
  IL_0083:  stloc.0
  IL_0084:  br.s       IL_00ae
  IL_0086:  ldstr      "3"
  IL_008b:  stloc.0
  IL_008c:  br.s       IL_00ae
  IL_008e:  ldstr      "4"
  IL_0093:  stloc.0
  IL_0094:  br.s       IL_00ae
  IL_0096:  ldstr      "5"
  IL_009b:  stloc.0
  IL_009c:  br.s       IL_00ae
  IL_009e:  ldstr      "6"
  IL_00a3:  stloc.0
  IL_00a4:  br.s       IL_00ae
  IL_00a6:  ldsfld     string [mscorlib]System.String::Empty
  IL_00ab:  stloc.0
  IL_00ac:  br.s       IL_00ae
  IL_00ae:  ldloc.0
  IL_00af:  ret
} // end of method ISoundEx::EncodeChar

基本上，C# 编译器已重新排列了 switch 语句中的字符，使它们按照 Unicode 代码点升序排列。 它为缺少的字母添加了额外的 'case' 条目，作为一种填充。 CIL switch 语句是一个查找表。 执行 switch 时堆栈顶部的 value 被用作跳转到标签列表的基于零的索引。 这为我们提供了一个很好的优化查找表，而无需我们过于努力！

回到 SoundEx

ISoundEx.ValidateAlgorithm() 提供了针对该名称的已知 SoundEx 代码测试各种名称的方法。

字典查找

该代码还提供了一种加载单词或姓氏词典并执行快速有效的相似单词查找的方法。 CustomDictionary 使用以下代码将单词添加到内部查找表中

public void AddWord(string s) {
	if(_oAllWords.ContainsKey(s)==false) {
		string zSoundEx=_oSoundExAlgorithm.GenerateSoundEx(s);

		// Add the word to the list of all words and associate
		// a SoundEx value with it
		_oAllWords.Add(s, zSoundEx);

		// Create a new SoundEx group
		if(_oAllSoundEx.ContainsKey(zSoundEx)==false) {
			_oAllSoundEx.Add(zSoundEx,new StringCollection());
		}
		// Now add the string into the collection of all strings
		// with the same SoundEx
		((StringCollection)_oAllSoundEx[zSoundEx]).Add(s);
	}
}

_oAllWords 是一个 StringDictionary，其中包含字典中所有单词的唯一列表及其 SoundEx 代码。 _oAllSoundEx 是一个 HashTable，其中包含所有 SoundEx 值的唯一列表。 HashTable 中的每个条目都包含一个包含该 SoundEx 的单词的 StringCollection。 因此，我们在 SoundEx 代码和具有该 SoundEx 的单词之间建立了一个双向链接。

提供了两个文本文件。 第一个文件是来自所有 Unix 系统的 /usr/dict/words 数据库。 由于这是一个常用英语单词列表，而不是姓氏，它显示了 SoundEx 对于这些单词来说有多么不合适。 第二个文件是 OldPend Surnames 2002-01.txt，它是来自 Old Pendleton 数据库的超过 15,000 个唯一姓氏的列表。 这是一个数据库，其中个人的家族起源于南卡罗来纳州的老彭德尔顿地区，可以从 oldpendleton.homestead.com 获取。 这提供了更好的 SoundEx 匹配，但仍然显示了该算法的准确性有多么低。

结论

从上面的屏幕截图可以看出，结果有所不同。 那些绝不能被认为是相关的名称被返回，相反，那些应该相关的名称未能被返回。 Knuth 的例子是“Rogers”和“Rodgers”，“Sinclair”和“St. Clair”，它们失败了。

在 SoundEx 引入后的 120 年中，已经发明了其他类似的匹配算法。 Metaphone 是其中之一，它应该可以在此处呈现的代码结构中轻松实现。

最后，如果您打算在商业应用程序中使用 SoundEx，请注意它的陷阱。