实现语音（“听起来像”）姓名搜索，使用 Double Metaphone 第 I 部分：介绍与 C++ 实现

Adam Nelson

4.91/5 (20投票s)

2003年7月26日

CPOL

15分钟阅读

160580

2872

介绍 Double Metaphone 算法用于姓名的语音比较，并为读者项目提供实用的 C++ 实现。

摘要

简单的信息搜索——例如姓名查找、单词搜索等——通常基于精确匹配的标准。然而，考虑到同音词（发音相同）的多样性以及人们拼写姓氏的倾向，这种简单的标准往往效果不佳，导致搜索结果集减少，记录丢失，因为它们仅在拼写上稍有不同或采用不同的国家/地区拼写。

本系列文章将讨论 Lawrence Phillips 的 Double Metaphone 语音匹配算法，并提供几个实用的实现，可用于各种解决方案，以在数据库和其他集合中创建更实用、更有效的姓名搜索。

引言

在构建执行文本数据搜索的解决方案时，通常希望根据搜索条件的读音来匹配被搜索数据的读音，从而找出与搜索词“听起来像”的记录。这种类型的比较称为“语音匹配”，执行它的算法称为“语音匹配算法”或有时称为“语音编码算法”。

在寻找更好的语音匹配算法方面付出了巨大的努力，但效果参差不齐。最古老、最熟悉的语音匹配算法之一是 Soundex 算法，它在 20 世纪初获得专利，作为一种用于机械打孔卡机的算法。Soundex 根据一个简单的计算生成一个键，该键旨在代表原始单词的读音——或至少是单词的前一部分。

如果有人在包含几条以上记录的解决方案中实现过 Soundex，就会意识到它的局限性。它无法匹配发音相似的单词，却会匹配不恰当的单词。虽然 Soundex 简单且快速，但作为一种通用的语音匹配算法，它实在是不够理想。

1990 年，Lawrence Phillips 在《Computer Language》杂志上发表了 Metaphone 算法。Phillips 的算法考虑了多种英语发音规则，生成了一个更可靠的语音键，代表单词的发音，特别是姓名的发音。虽然比 Soundex 有所改进，但 Metaphone 仍然无法匹配一些明显同音的单词，例如“Bryan”和“Brian”。

最后，在 2000 年 6 月的 C/C++ User's Journal 期刊中，Phillips 发表了 Double Metaphone 语音匹配算法。Double Metaphone 实现了额外的启发式规则来纠正 Metaphone 之前的不足，并生成第二个“备用”键，该键代表姓名的本地发音，而不是美式发音。通过这些增强功能，Phillips 创建了一种足够可靠的语音匹配算法，可以广泛使用。

本系列文章将讨论 Double Metaphone 算法在语音搜索姓名数据中的实际应用，使用作者为 C++、COM（Visual Basic 等）、脚本客户端（VBScript、JScript、ASP）、SQL 和 .NET（C#、VB.NET 和任何其他 .NET 语言）编写的实现。有关 Double Metaphone 算法本身及其原始代码的讨论，请参阅上面的链接。

第一部分介绍了 Double Metaphone 并描述了作者的 C++ 实现及其用法。第二部分讨论了在 Visual Basic 中使用作者的 COM 实现。第三部分演示了如何在 ASP 中以及使用 VBScript 调用 COM 实现。第四部分展示了如何使用作者的扩展存储过程在 SQL Server 中执行语音匹配。第五部分展示了作者的 .NET 实现。最后，第六部分将回顾语音匹配的替代方法，并提供其他资源的链接。

如果只对如何为特定语言实现语音匹配感兴趣，仍然可以从本系列第一部分中的背景信息中受益。

背景

Phillips 的原始 Double Metaphone 实现采用了 C++ 类 MString 的形式，它继承自 MFC 字符串类 CString。用户只需调用 DoubleMetaphone 方法，即可为字符串中的单词生成两个键。第一个（主键）代表该单词按美式发音规则的发音，而第二个（备用键）代表外来单词或姓名的本地发音。备用键可以为空，通常为空，表示没有备用的本地发音。

Metaphone 键的长度为四个字母（短单词为三个）。因此，Metaphone 键代表单词的一部分，特别是前半部分。Phillips 和作者的经验测试证实，四个字母似乎是“魔法长度”，在容错性和匹配相关性之间取得了平衡。

要比较两个单词是否在语音上匹配，需要比较第一个单词的主键和备用键与第二个单词的主键和备用键。如果四个组合中的任何一个（或多个）匹配，则称这两个单词在语音上匹配。相对匹配强度可以通过下表计算：

主键 = 主键	最强匹配
备用键 = 主键	普通匹配
主键 = 备用键	普通匹配
备用键 = 备用键	最弱匹配

根据实现需求，结果可以过滤，只包含特定级别的匹配。

改进的实现

本文介绍的实现采用了 C++ 模板的形式，接受一个模板参数，用于指定生成的键的长度。如上所述，四个字母似乎是理想的，但模板允许程序员进行一些实验。

与 Phillips 的原始代码相比，此实现具有多项优势：

首先，它不基于 MFC；因此，使用模板不需要 MFC 运行时。事实上，它不基于任何 Windows 特定元素；因此，只需一个支持模板的现代编译器即可使用。

其次，它不继承自字符串类。在作者看来，Double Metaphone 实现类所代表的实体应该是 Metaphone 键。这就引出了下一个优势……

第三，它实现了 C++ 的 == 和 != 比较运算符，它们基于 Metaphone 键，因此非常适合用作某些容器类的键，这将在下文更详细地讨论。

第四，由于进行了微小的优化和模板的完全内联特性，与 Phillips 的原始实现相比，此实现计算键的速度大约快 2 倍，这基于简单的测试。

要使用此实现，只需包含头文件

#include "DoubleMetaphone.h"

并通过指定键的长度来实例化基于模板的类，然后将需要编码的单词传递给构造函数或 computeKeys 方法

DoubleMetaphone<4> mphone("Nelson");
//OR:
DoubleMetaphone<4> mphone;
mphone.computeKeys("Nelson");

要从实例中获取主键或备用键，分别调用 getPrimaryKey 和 getAlternateKey。

DoubleMetaphone<4> mphone("Nelson");
cout << mphone.getPrimaryKey() << endl;
cout << mphone.getAlternateKey() << endl;

请注意，如果与实例关联的单词没有备用键，getAlternateKey 将返回 NULL。

为方便用户使用，头文件包含了一个 DoubleMetaphone4 类的类型定义，即 DoubleMetaphone<4>。因此，上面的代码等同于：

如前一节所述，要使用四向比较来比较两个单词的语音相似性，只需实例化两个 DoubleMetaphone 对象，将两个单词分别传递给相应对象的构造函数或 computeKeys 方法，然后进行比较。

DoubleMetaphone<4> mphone1("Nelson");
DoubleMetaphone<4> mphone2("Neilsen");

if (mphone1 == mphone2) {
     cout << "Nelson = Neilsen" << endl;
} else {
     cout << "Nelson != Neilsen" << endl;
}

为了方便起见，头文件包含了一个 DoubleMetaphone4 类的类型定义，即 DoubleMetaphone<4>。因此，上面的代码等同于：

DoubleMetaphone4 mphone1("Nelson");
DoubleMetaphone4 mphone2("Neilsen");
 
if (mphone1 == mphone2) {
     cout << "Nelson = Neilsen" << endl;
} else {
     cout << "Nelson != Neilsen" << endl;
}

实现的实际应用

上一节对实现的接口进行了简要介绍，并说明了如何计算单词的 Metaphone 键。本节将演示一个语音搜索应用程序 Word Lookup 的构建过程，该应用程序可以检索与给定搜索姓名发音相似的所有姓名。

虽然这个解决方案 hardly 代表一个生产级的系统，但它演示了使用 Double Metaphone 进行语音匹配的关键原理，并提供了一个测试环境，可以在其中测试和调整各种参数以适应特定环境。例如，尝试更改 Metaphone 键的长度，并注意这对匹配结果有何影响。或者，尝试使用单词列表而不是姓名；语音匹配对普通单词和姓名的效果一样吗？每次语音匹配的应用都不同；因此，可以合理地预期，在特定应用程序中需要进行一些调整以获得最佳性能。

在实践中，当实现需要语音匹配的解决方案时，不会像上面的代码片段那样比较两个单词的相似性。相反，必须搜索由姓氏或其他候选数据组成的一系列记录，生成一个或多个匹配的记录。

对于本文，上述集合将是 STL multimap 类，其键类型是 STL string 类，包含 Metaphone 语音键（主键或备用键），值类型是 STL string 类，包含姓名。该集合将从 Moby 项目中获取的 21k 个姓名列表中填充。有关此示例应用程序的完整源代码以及姓名列表副本，请下载本文相关的源文件。

选择 STL multimap 类有两个原因：首先，它简单且易于理解；其次，它实现了一个关联容器，将一个键与一个或多个值关联。这一点至关重要，因为目标是将一个键（代表单词发音的 Metaphone 语音键）与多个值（Double Metaphone 生成该键的所有单词）关联起来。

在搜索之前，必须填充容器。为此，从文件中读取单词（每行一个），将每个单词传递给 DoubleMetaphone4 实例上的 computeKeys 方法来计算单词的键，并将条目添加到 multimap 中，将 DoubleMetaphone4 类的键与字符串值类进行映射。

typedef std::multimap<string, string> WordMapType;

WordMapType wordMap;
DoubleMetaphone<METAPHONE_KEY_LENGTH> mphone;
char line[100];
while (!file.eof()) {
     //Read a word from the file
     file.getline(line, 100);
     
     //Compute the Metaphone keys for the word
     mphone.computeKeys(line);
     
     //Add a string object containing the word to the map,
     //with the primary and alternate Metaphone keys as map keys
     string word = line;
     string key = mphone.getPrimaryKey();
     wordMap.insert(WordMapType::value_type(key, word));
     if (mphone.getAlternateKey() != NULL) {
          key = mphone.getAlternateKey();
          wordMap.insert(WordMapType::value_type(key,word));
     }
}
file.close();

在上面的代码片段中，file 是 ifstream 类型，并且已经打开了用于填充映射的姓名列表。当 file 未到达文件末尾时，将一行读入 line，然后将 line 传递给 computeKeys，以计算 line 中单词的 Metaphone 键。然后，将一个条目添加到 wordMap（映射一个 string 到多个 string 实例的 multimap）中，将单词的主 Metaphone 键映射到单词本身。如果单词存在备用键，则将另一个条目放入 wordMap 中，将备用键也映射到单词。

必须记住，multimap 将一个键映射到多个值，因此在循环结束后，对于 multimap 中的任何给定语音键，将有一个或多个单词与该键相关联。因此，在搜索与搜索词听起来像的语音匹配的单词时，使用搜索词的主（以及可能的备用）Metaphone 键来查询 multimap，并且 multimap 中存在于两个键之一或两个键上的所有单词都与搜索词具有一定程度的语音相似性。下面是一个执行任意单词搜索的 Word Lookup 示例应用程序的片段。

typedef std::multimap<string, string> WordMapType;
typedef std::set<string> WordListType;

void phoneticMatch(WordMapType& words, 
                   const string& searchWord, 
                   WordListType& matchingWords) {
     //Compute Metaphone keys for search word
     DoubleMetaphone4 searchKey(searchWord.c_str());
 
     //Search map with primary Metaphone key
     string search2 = searchKey.getPrimaryKey();
     cout << "Searching for [" <<searchWord.c_str() << "]" << endl;
     
     for (WordMapType::iterator iter = words.lower_bound(search2);
            iter != words.upper_bound(search2);
            iter++) {
          matchingWords.insert((*iter).second);
     }
     if (searchKey.getAlternateKey() != NULL) {
          //Alternate key computed for search word, so
          //search map with alt key as well
          string search3 = searchKey.getAlternateKey();
          for (iter = words.lower_bound(search3);
                iter != words.upper_bound(search3);
                iter++) {
              matchingWords.insert((*iter).second);
          }
     }
}

上面的代码片段包含 phoneticMatch 函数的实现，该函数是 Word Lookup 示例应用程序的一部分，用于在 multimap 中搜索与搜索词 searchWord 在语音上匹配的所有单词。所有匹配的单词都放在一个 STL set matchingWords 中，供调用者使用。

显然，考虑到产生的复杂结果，搜索过程非常简单。首先，创建一个带有搜索词的 DoubleMetaphone4 实例，从而计算搜索词的 Metaphone 键。接下来，一个 for 循环遍历与搜索词的主 Metaphone 键关联的单词，将每个匹配的单词放入结果 set matchingWords 中。（对于不熟悉 STL multimap 的人来说，lower_bound 返回一个指向与键关联的第一个值的迭代器，而 upper_bound 返回一个指向最后一个值的后面一个位置的迭代器；因此，遍历这两个 iterator 之间的范围会得到与给定键关联的所有值。）最后，如果搜索词存在备用 Metaphone 键，则将与该备用键关联的所有单词也放入结果 set 中。

Word Lookup 的最后一个组件是 computeMatchLevel 函数。这个简单的函数实现了上一节表格中描述的结果评分技术。它简单地确定搜索词的哪个 Metaphone 键与候选词的哪个 Metaphone 键匹配，返回一个匹配分数，从 1（强，主-主匹配）到 3（最弱，备用-备用匹配）。在 Word Lookup 中，computeMatchLevel 为每个匹配搜索词的单词调用。computeMatchLevel 返回的分数以及匹配的单词一起打印到控制台，让用户了解匹配的强度。

int computeMatchLevel(const string& searchWord, 
                   const string& candidateWord) {
     DoubleMetaphone4 searchWordMphone(searchWord.c_str());
     DoubleMetaphone4 candidateWordMphone(candidateWord.c_str());
     
     if (strcmp(searchWordMphone.getPrimaryKey(), 
                 candidateWordMphone.getPrimaryKey()) == 0) {
          //Primary-Primary match, that's level 1 (strongest)
          return 1;
     }
     
     if (searchWordMphone.getAlternateKey() != NULL) {
          if (strcmp(searchWordMphone.getAlternateKey(), 
                      candidateWordMphone.getPrimaryKey()) == 0) {
              //Alternate-Primary match, that's level 2 (normal)
              return 2;
          } 
     }
     
     if (candidateWordMphone.getAlternateKey() != NULL) {
          if (strcmp(searchWordMphone.getPrimaryKey(), 
                      candidateWordMphone.getAlternateKey()) == 0) {
              //Primary-Alternate match, that's level 2 (normal)
              return 2;
          } 
     }
     
     if (searchWordMphone.getAlternateKey() != NULL &&
          candidateWordMphone.getAlternateKey() != NULL) {
          if (strcmp(searchWordMphone.getAlternateKey(), 
                      candidateWordMphone.getAlternateKey()) == 0) {
              //Alternate-Alternate match, that's level 3 (minimal)
              return 3;
          } 
     }
 
     return 0;
}

在尝试 Word Lookup 应用程序时，经常会遇到有效性可疑的匹配；然而，这些匹配几乎总是得分为 3，这表明 Double Metaphone 算法认为它们仅是远距离匹配。这对于实践者来说是令人鼓舞的，因为它意味着可以通过限制结果到某个匹配级别来调整用于搜索语音匹配的网络的宽度，并且有合理的把握不会拒绝有效匹配。

无符号短整数优化

虽然前面各节中的实现技术非常有效且相当高效，但敏锐的读者可能会对 multimap 类在单词搜索中隐式执行的大量字符串比较感到困扰。此外，虽然 21,000 个单词列表所需的内存很小，但将列表扩展到几十万甚至数百万，由于用于存储单词本身以及这些单词的语音键的 STL string 类实例数量众多，将会产生显著的内存占用。

幸运的是，存在一种替代方案。在其 2000 年的 CUJ 文章中，Phillips 提出将四字符 Metaphone 键表示为四个四位半字节，共同组成一个 16 位无符号短整数。由于一个四位半字节可以表示从十六进制 0 到十六进制 f（十进制 0-15）的值，并且 Metaphone 算法仅产生 12 个字符的键，因此可以为每个字符分配一个数值等价物，从而将一个键表示为“字符串”的半字节，打包成 16 位整数。

虽然 Phillips 未在其 MString 类中实现此优化，但我已在 ShortDoubleMetaphone 类中实现它，该类是 DoubleMetaphone4 的子类——也就是说，它继承自通过将键长度指定为 4 给 DoubleMetaphone 模板得到的类。将 ShortDoubleMetaphone 派生自 DoubleMetaphone4 而不是将其设为具有可变键长度的另一个模板的原因应该很明显；大于 4 的键长度无法用 16 位短整数表示，而小于 4 的键长度不够精确，会导致大量弱匹配。

ShortDoubleMetaphone 的使用几乎与 DoubleMetaphone4 相同；事实上，由于它是 DoubleMetaphone4 的子类，因此可以以完全相同的方式使用它，尽管这样做不会实现无符号短整数优化的好处。

ShortDoubleMetaphone 增加了两个方法：getPrimaryShortKey 和 getAlternateShortKey。顾名思义，它们返回一个代表各自键的无符号短整数值。getAlternateShortKey 返回 METAPHONE_INVALID_KEY（0xffff）来指示备用键的缺失。使用这些方法以及无符号短整数类型代替字符串等价物，是将基于 DoubleMetaphone 的实现转换为基于 ShortDoubleMetaphone 的实现的全部要求。

虽然这里没有讨论，但源文件包含了一个 Word Lookup 示例版本，该版本使用 ShortDoubleMetaphone 而不是 DoubleMetaphone。除了查找速度提高 50%-150%（取决于数据）之外，两个版本之间的行为没有显着差异。

结论

本文探讨了语音匹配问题，介绍了 Double Metaphone 算法作为一种解决方案，并演示了在实际应用程序中使用 Double Metaphone 的 DoubleMetaphone 模板类实现。虽然这些信息对于开发语音匹配系统很重要，但它缺少一些重要的信息：如何将这项技术应用于存储大部分需要语音搜索信息的关联数据库系统；以及如何从其他现代编程语言中使用 Double Metaphone。

本文不解决这些问题，主要是因为目标是简单地介绍语音匹配、Double Metaphone 以及 C++ 中的实现。鼓励读者继续阅读本系列文章，以进一步探索 Double Metaphone 的应用，以及使用关系数据库和其他编程语言进行语音匹配的示例。第二部分介绍了一个 COM 组件实现的 Double Metaphone，该组件可从 Visual Basic、Visual FoxPro、Delphi 和任何其他 COM 兼容语言调用。第二部分还介绍了与关系数据库进行语音匹配，并包含了一个相应的 Visual Basic 示例应用程序。第三部分演示了如何在 ASP 和 VBScript 中使用 COM 实现，包括与数据库进行语音搜索。第四部分介绍了作者的 SQL Server 扩展存储过程，该过程允许从 SQL 内部计算 Double Metaphone 键。第四部分还讨论了关系数据库语音匹配解决方案的优化。第五部分探讨了作者的 .NET Double Metaphone 实现，并包含了一个与关系数据库进行语音搜索的示例。最后，第六部分通过对替代语音匹配技术的检查以及对其他资源和 Double Metaphone 实现的链接，结束了 Double Metaphone 的讨论。

历史

2003 年 7 月 22 日首次发布
2003 年 7 月 31 日在系列文章之间添加了超链接

实现语音（“听起来像”）姓名搜索，使用 Double Metaphone 第 I 部分：介绍与 C++ 实现

摘要

引言

背景

改进的实现

实现的实际应用

无符号短整数优化

结论

历史

文章系列