65.9K
CodeProject 正在变化。 阅读更多。
Home

实现语音（“听起来像”）名称搜索，使用 Double Metaphone 第四部分：SQL Server 和高级数据库主题

Adam Nelson
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.95/5 (18投票s)

2003年7月26日

14分钟阅读

viewsIcon

175342

downloadIcon

3112

介绍了基于作者 C++ 实现的 SQL Server 扩展存储过程包装器，并讨论了 Double Metaphone 与关系数据库的通用用法。

摘要

简单的信息搜索——例如姓名查找、单词搜索等——通常使用精确匹配的标准来实现。然而，鉴于同音词（发音相同）单词和姓名的多样性，以及人们容易拼错姓氏的倾向，这种简单的标准常常导致结果不尽如人意，表现为结果集减少、记录丢失（因字母拼写错误或不同的国家/地区拼写方式）。

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

引言

本系列文章讨论了 Double Metaphone 算法在语音搜索姓名数据中的实际应用，使用了作者为 C++、COM（Visual Basic 等）、脚本客户端（VBScript、JScript、ASP）、SQL 和 .NET（C#、VB.NET 以及任何其他 .NET 语言）编写的实现。关于 Double Metaphone 算法本身及其 Phillips 的原始代码的讨论，请参阅 Phillips 发表在 2000 年 6 月 CUJ 上的文章，可在此 处 查看。

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

背景

本系列文章的第一部分讨论了 Double Metaphone 算法、其起源和用法，以及作者的 C++ 实现。虽然本节总结了该文章的关键信息，但仍鼓励读者阅读完整文章，即使读者没有 C++ 经验。

Double Metaphone 算法由 Lawrence Phillips 开发，并发表在 2000 年 6 月的 C/C++ Users Journal 上，属于“语音匹配”或“语音编码”算法类别。这些算法试图检测单词之间的语音（“听起来像”）关系。例如，语音匹配算法应该能够检测到“Nelson”和“Nilsen”之间强烈的语音关系，而“Adam”和“Nelson”之间则没有语音关系。

Double Metaphone 通过给定一个单词来生成一个或可能两个语音键。这些键代表单词的“声音”。典型的 Double Metaphone 键长度为四个字符，因为这往往能在特异性和结果的通用性之间取得理想的平衡。

第一个（主）Double Metaphone 键代表源单词的美式发音。所有单词都有一个主 Double Metaphone 键。

第二个（备用）Double Metaphone 键代表备选的、非美式发音。例如，许多波兰姓氏被“美国化”，从而产生两种可能的发音：原始的波兰语发音和美式发音。因此，Double Metaphone 会为某些单词计算备用键。请注意，绝大多数（粗略估计 90%）单词不会产生备用键，但一旦计算出备用键，它对于匹配单词可能至关重要。

要比较两个单词的语音相似度，需要计算它们各自的 Double Metaphone 键，然后比较每种组合：

  • 单词 1 主键 - 单词 2 主键
  • 单词 1 主键 - 单词 2 备用键
  • 单词 1 备用键 - 单词 2 主键
  • 单词 1 备用键 - 单词 2 备用键

显然，如果给定的单词没有生成上面某个比较中的键，那么涉及该键的比较就不会执行。

根据以上哪个比较匹配，会计算一个匹配强度。如果第一个比较匹配，则两个单词具有很强的语音相似度。如果第二个或第三个比较匹配，则两个单词具有中等语音相似度。如果第四个比较匹配，则两个单词具有极低的语音相似度。根据特定的应用程序要求，可以排除一个或多个匹配级别。

SQL Server 扩展存储过程

在本系列文章的 第二部分和 第三部分中，我们介绍了在 Visual Basic 和 Active Server Pages 中的示例应用程序，它们查询单词和 Double Metaphone 键的 Microsoft Access 数据库以进行语音相似度比较。在这两个应用程序中，所有语音匹配逻辑都存在于应用程序层；也就是说，数据库只是一个“信息 the gopher”，检索由应用程序层生成的特定标准的精确匹配。

对于某些应用程序来说，这种安排是可取的。它将所有应用程序逻辑保留在应用程序内部，从而便于维护，并且可以轻松迁移到备用数据库平台。事实上，任何比 INNER JOIN 更高级的逻辑通常会被软件设计纯粹主义者移至“业务逻辑”层，这往往是有充分理由的，但有时也仅仅是因为最新的流行开发潮流要求如此。

实际上，某些功能可以从关系数据库本身内部更高效地实现，有时甚至只能在那里实现。总的来说，从一般视角来看，导致这种情况的原因很难预见，但当它们确实出现时，就必须加以解决。这就是为什么需要 SQL Server 实现 Double Metaphone：不是每个人都会需要它，但在某些情况下，它是语音匹配系统的最佳或唯一选择。

使用 XP

SQL Server 扩展存储过程（以下简称 XP）实现为 Win32 DLL。要安装 XP，请将其 DLL 复制到 SQL Server 安装路径下的 *Binn* 目录，然后从 master 数据库运行 sp_addextendedproc。对于 Double Metaphone XP，命令将如下所示：

use master
exec sp_addextendedproc 'xp_metaphone', 'XPMetaphone.dll'

执行此命令后，将有一个新的 XP 可用，它在所有意图和目的上都等同于声明如下的 SQL 存储过程：

create proc xp_metaphone(@word varchar(255), 
                        @primaryKey smallint output,
                        @alternateKey smallint output)

如果您阅读了之前的文章，那么使用此 XP 应该很明显。一个单词被传递到 @word 参数，包含要计算 Double Metaphone 键的单词。两个输出参数被设置为两个 Double Metaphone 键。如果未计算备用键，则 @alternateKey 被设置为 null。请注意，两个键参数都是 smallint；XP 使用无符号短整型优化来计算 Double Metaphone 键。XP 不提供 Double Metaphone 键的文本版本。

要使用 XP，只需像调用任何存储过程一样调用它。在查询键表时，确保执行所有四个可能的键关系。显然，如果您的特定应用程序需要的结果较少，则可以消除较弱的比较。以下是一个查询名为 Words 的表的 SQL 示例：

declare @word varchar(255)
declare @primaryKey smallint
declare @alternateKey smallint

set @word = 'Nelson'
exec master..xp_metaphone @word, @primaryKey output,
@alternateKey output

select
     word
from
     Words
where
     key1 = @primaryKey
     or
     key2 = @primaryKey
     or
     key1 = @alternateKey
     or
     key2 = @alternateKey
order by word

对包含 21,000 个姓名样本数据的表中填充的单词执行上述 SQL：

请注意，Words 表中单词的 Double Metaphone 键已预先计算并存储在 key1 和 key2 列中。这对于可容忍的数据库性能至关重要，因为在搜索时为每个单词计算键将消除数据库优化的任何能力，并导致性能不佳。

实现技巧

本节包含一些关于语音匹配实现的观察，特别是在 SQL Server 中。虽然 SQL Server 是特别针对的，但大多数这些技巧同样适用于任何现代 RDBMS。

做出明智的索引决策

与任何其他数据库搜索一样，索引决策对语音搜索的性能有显著影响。由于语音搜索仅处理语音键列，因此应特别注意优化这些列的查询性能。当然，如果语音键列与需要搜索的其他数据共享一个表，那么必须权衡优化一个查询相对于另一个查询的相对性能增益。与许多数据库优化决策一样，尝试几种不同的配置通常很有用，以确定哪种配置能获得最佳性能。

对于上面查询的示例数据库，它由一个单词表组成，我已在 key1、key2 列集上创建了聚集索引，这会导致表内数据物理存储顺序为 key1，然后是 key2。结果是，当 SQL Server 搜索匹配数据时，使用主 Double Metaphone 键（迄今为止最常见的匹配），所有正在搜索的数据在物理上（在磁盘上）是聚集在一起的，这意味着更快的读取时间和更好的读取缓存利用率。对于一个 21,000 条记录的数据库，这种优化几乎没有区别，但如果扩展到 2,100,000 或 21,000,000 条记录，按语音键聚类将极大地提高语音匹配速度。

不幸的是，由于显而易见的原因，每个表只能有一个聚集索引。因此，在许多情况下，聚集索引可能已经存在于某个同样性能关键的列上。在这种情况下，非聚集索引通常比没有好。另一种带有附加好处的替代方案在下一个技巧中描述。

保持现有的应用程序表不变

在构建新应用程序时，将 Double Metaphone 集成到数据库架构中相对容易。然而，当向现有应用程序添加语音匹配时，修改架构可能是不可取或被禁止的选项。此外，即使正在构建新应用程序，通过将 Metaphone 键和语音匹配的其他伪影与架构的其余部分混合，也存在着被用于语音匹配的技术可能不合适的重大风险。语音匹配研究仍在继续，因此几乎可以肯定在短期内会发布改进的算法，因此，任何考虑语音匹配的人都有必要尽可能地将特定算法的选择与应用程序的不可变部分解耦。

为此，创建单独的表来包含语音键数据，并通过后者的主键与原始表相关联，这是非常有意义的。例如，如果 Customers 表包含客户列表，则可以创建一个 CustomerPhoneticKeys 表，其中包含每个客户姓名的语音键以及客户 ID，该 ID 指向 Customers 表。这还解决了上一个技巧中关于要求在语音键列上创建聚集索引的问题：可以在 CustomerPhoneticKeys 表的语音键列上创建聚集索引，从而获得聚集索引的性能优势，而无需修改基础表。

在执行包含语音标准的搜索时，只需与语音键表 JOIN，并将语音匹配标准添加到 WHERE 子句中。

使用触发器更新语音键

无论语音键数据存储在哪里，保持语音键数据更新仍然至关重要。如果语音匹配被添加到现有应用程序中，这可能会带来重大问题，因为应用程序层在向数据库提交更新时不会计算更新的语音键。即使在构建具有语音功能的应用程序时，根据约束条件，在应用程序级别计算更新的语音数据也可能是不希望的或不可行的。

幸运的是，SQL Server 允许程序员编写在表事件（插入、更新和删除）发生时调用的“钩子”。通过编写一个调用 Double Metaphone XP 并自动更新语音键数据的触发器，可以确保获得最新的语音键，而无需额外的编程。例如，要更新我的 Words 测试表的语音键，我可以创建以下触发器（感谢 Diego Mijelshon 在本文前一个修订版中指出了我的触发器代码中的简单错误）：

create trigger trigger_OnUpdateWords
on Words
for insert,update
as

if update(word)
begin
    --word is being updated; recompute phonetic keys accordingly
    declare @word varchar(255)
    declare @primaryKey smallint
    declare @alternateKey smallint

    --create a cursor to update each row from the "inserted" 
    --table (slow but generally applicable)
    declare words_cursor cursor local read_only forward_only
    for
        select distinct word from inserted
    
    open words_cursor

    fetch next from words_cursor into @word

    --For each updated word, compute the new dbl 
    --metaphone keys, and apply them
    while @@FETCH_STATUS = 0
    begin
        exec master..xp_metaphone @word, 
              @primaryKey output, 
              @alternateKey output

        --Update the phonetic keys also
        update Words 
        set 
            key1 = @primaryKey, 
            key2 = @alternateKey 
        where 
            word = @word

        fetch next from words_cursor into @word
    end

    close words_cursor
    deallocate words_cursor
end

如果任何记录插入到 Words 表中，或对 Words 表执行更新，则会执行此触发器。如果 word 列受到影响，则会重新计算语音键，并再次使用新键更新 Words 表。由于此更新不会更改 word 列，因此触发器不会导致无限递归，尽管触发器会因更新而再次被调用。因此，必须启用 SQL Server 的“递归触发器”DB 选项才能使此触发器正常工作。

显然，如果实现了上一个技巧，并且语音键位于单独的表中，那么触发器将不会更新它正在监视的表，而是更新包含要保持最新的语音键的表。在这种情况下，则无需启用递归触发器。

现在有了这个触发器，就可以随意插入和更改 Words 表中的单词，并确信语音键将始终是最新的。

在 SELECT 语句中计算匹配分数

在 第一部分的 Word Lookup 示例应用程序中，一个简单的 C 函数根据搜索单词的哪个语音键匹配结果单词的哪个语音键，计算搜索结果中单词的匹配分数。在 SQL 中执行语音匹配时，可以在行内执行此计算；如有必要，可以通过结果匹配分数对结果进行限制。考虑此 SQL：

declare @word varchar(255)
declare @primaryKey smallint
declare @alternateKey smallint

set @word = 'Nelson'

exec master..xp_metaphone @word, 
              @primaryKey output,
              @alternateKey output

select 
word,
(
case 
     when key1 = @primaryKey then 
     1--Strong match

     when key2 = @primaryKey then
     2--Normal match

     when key1 = @alternateKey then
     2--Normal match

     when key2 = @alternateKey then
     3--Minimal match

     else
     4--No match
end
) as matchScore
from Words
where
     key1 = @primaryKey
     or
     key2 = @primaryKey
     or
     key1 = @alternateKey
     or
     key2 = @alternateKey
order by word
go

关键在于使用 CASE 语句，根据一组条件中的哪一个为真，将一个列评估为不同的值。通过在 WHERE 子句中使用相同的表达式，可以轻松地将结果限制为最低匹配分数。

将搜索逻辑包装在存储过程中

在构建数据库应用程序时，通常会诱惑从应用程序代码内部动态构建 SQL 查询，以执行所需的插入、更新、删除和选择操作。不幸的是，这有几个问题：

首先，它非常低效。在大多数语言中构建动态字符串成本很高，需要多次内存分配和复制。一旦构建了动态字符串并将其传递给数据库，就需要解析和验证查询，然后计算查询计划。所有这些都需要大量时间。

其次，它很难修改。数据库中的任何更改都需要修改应用程序层代码。这不属于解耦。

第三，它可能不安全。如果不小心，攻击者可以将数据库命令插入到搜索字符串中，然后这些命令将被执行。根据数据库的不同，这些命令可能导致数据丢失或安全泄露。

第四，它代码丑陋且烦人。

另一方面，存储过程没有这些问题（除了第四个问题，可能取决于个人偏好）。

虽然这些论点在一般情况下是有效的，但对于需要语音匹配功能的应用程序，可以提出一个更有说服力的论点：语音匹配逻辑完全包含在数据库中，而这可以说是它应该在的地方。

例如，通过存储过程暴露 Words 表：

create procedure sp_MatchWords (@word varchar(255))
as
declare @primaryKey smallint
declare @alternateKey smallint

exec master..xp_metaphone @word, 
              @primaryKey output,
              @alternateKey output

select word from Words
where
     key1 = @primaryKey
     or
     key2 = @primaryKey
     or
     key1 = @alternateKey
     or
     key2 = @alternateKey
order by word
go

现在，从应用程序中，只需执行此 SQL：

exec sp_MatchWords 'Nelson'

来执行语音搜索。请注意，没有提及 Double Metaphone、语音键或任何其他信息，除了搜索标准。语音匹配的细节已被抽象到数据存储本身，而在许多情况下，这是合适的设计。

虽然上面已经说过，但应该重申：通过将语音搜索包装在存储过程中，并使用存储过程或触发器自动更新语音键，*应用程序中的任何其他地方都不需要语音匹配支持*。如果您不控制应用程序代码，或者应用程序代码将有多个版本来满足不同的需求或平台，这一点尤其有吸引力。

结论

本文介绍了 Double Metaphone XP 以及在 SQL Server 和一般关系数据库中构建语音匹配功能的几个技巧。现在，读者应该能够根据自己的具体需求设计和构建语音匹配系统。

继续阅读 第五部分，了解 Double Metaphone 的 .NET 实现，最后是 第六部分，其中将对替代的语音匹配技术进行概述，并提供其他资源和实现的链接。

历史

  • 2003 年 7 月 22 日首次发布
  • 2003 年 7 月 22 日 修正触发器代码（感谢 Diego Mijelshon）
  • 2003 年 7 月 31 日 在系列文章之间添加了超链接
  • 2003 年 7 月 31 日 修正匹配分数计算算法的笔误（感谢 David Walker）

文章系列

© . All rights reserved.