程序和数据库中的快速拼写不敏感字符串匹配
3.91/5 (10投票s)
可以匹配有拼写错误的字符串。
引言
在我上学的时候，我在使用图书馆搜索引擎时打错了搜索词，然后一条记录被列了出来。然后我注意到这个错别字，并正确地输入了搜索词。这条记录没有被列出。我告诉了图书管理员，并修复了这条记录。这让我开始思考错别字的问题。
在我拜访一位住院的亲戚时，我听到电脑发出一声哔哔声。我瞥了一眼屏幕，注意到我的姓被拼错了。我告诉护士正确的拼写。这些事件表明，错别字可能出现在数据库中，也可能出现在搜索词中。
错别字或印刷错误是由四种类型的错误引起的：插入、删除、替换或易位。由于任何单词都可以通过一系列错别字变成任何其他单词，因此有必要限制这些更改，以便两个单词的差异小于或等于一个错别字，看起来像是尝试键入另一个单词。在下面提供的软件中，这是通过强制规定错别字之间的最小间隔来实现的。
程序中的匹配
Visual Studio 解决方案 TypoMatching.sln 包含三个项目。这是为了让 C++ 中的单元测试能够工作。演示程序在 TypoMatching 中，错别字匹配逻辑在 TypoMatcherLib 中，单元测试在 TypoMatchingUnitTests 中。
接下来要考虑的是 C++ 中使用的三种 string 类型。它们是 C++ 字符串、C 字符串和 MFC 字符串。C++ 字符串可以通过接受 std::string 引用的函数来处理。C 字符串和 MFC 字符串都可以通过接受常量字符串指针的函数来处理。
另一个问题是是否选择了 Unicode。这是通过让主要的匹配函数接受常量字符串指针来处理的，该指针会根据是否定义了 UNICODE 进行调整，并根据此设置定义 C++ 字符串的类型。一旦解决了这些问题，就会得到一个接受 C++ 字符串引用的辅助函数，该函数会调用主匹配函数。
在下面的列表中，在进行了一些准备工作之后，主匹配函数会遍历一对字符串。通过转换为大写进行比较来检查每对字符是否相等。转换为小写或考虑文化或区域差异也可以。如果一对字符不能以这种方式匹配，第一步是确定是否存在一个离当前字符太近的先前错别字。如果没有，则按照一定的顺序查找错别字。
这个顺序是易位、插入、删除和替换。假设一个错别字是易位错误。它也可能看起来像是插入后跟删除，或者删除后跟插入，或者两个替换错别字。由于强制规定了最小错别字间隔以确保差异不大的单词看起来相似，因此选择最佳匹配的错别字类型很重要。上述顺序可以处理这个问题。
如果字符串的末尾没有同时到达，则会检查最终的插入或删除错别字。匹配函数的参数允许检索错别字的数量，并将默认的最小间隔更改为除二以外的值。
bool TypoMatcher(LPCTSTR pszWord1, LPCTSTR pszWord2, int* pnTypos /* = nullptr */,
vector<pair<ETypos, int>>* vTypos /* = nullptr */, int nMinSeparation /* = 2 */)
{
if (pnTypos != nullptr) {
*pnTypos = 0;
}
if (pszWord1 == nullptr || pszWord2 == nullptr) {
return false;
}
int nTypos = 0;
LPCTSTR pszWord1Start = pszWord1, pLastGoodPos1 = nullptr;
TCHAR c1Upper = 0, c2Upper = 0, c1NextUpper = 0, c2NextUpper = 0;
for (; *pszWord1 != _T('\0') && *pszWord2 != _T('\0'); ++pszWord1, ++pszWord2) {
c1Upper = ::_totupper(*pszWord1); // generic for toupper
c2Upper = ::_totupper(*pszWord2);
if (c1Upper != c2Upper) {
if (pLastGoodPos1 != nullptr && pszWord1 - pLastGoodPos1 < nMinSeparation) {
return false;
}
c1NextUpper = ::_totupper(*(pszWord1 + 1));
c2NextUpper = ::_totupper(*(pszWord2 + 1));
if (c1Upper == c2NextUpper && c1NextUpper == c2Upper) { // transposition
AddDetails(vTypos, ETypos::Transposition, pszWord1 - pszWord1Start);
pLastGoodPos1 = pszWord1 + 2;
++pszWord1; ++pszWord2;
}
else if (c1Upper == c2NextUpper) { // insertion
AddDetails(vTypos, ETypos::Insertion, pszWord1 - pszWord1Start);
pLastGoodPos1 = pszWord1;
++pszWord2;
}
else if (c1NextUpper == c2Upper) { // deletion
AddDetails(vTypos, ETypos::Deletion, pszWord1 - pszWord1Start);
pLastGoodPos1 = pszWord1 + 1;
++pszWord1;
}
else { // substitution
AddDetails(vTypos, ETypos::Substitution, pszWord1 - pszWord1Start);
pLastGoodPos1 = pszWord1 + 1;
}
++nTypos;
}
}
// Handles an insertion or a deletion typo at the end of a string.
if (*pszWord1 != _T('\0') || *pszWord2 != _T('\0')) {
if (pLastGoodPos1 != nullptr && pszWord1 - pLastGoodPos1 < nMinSeparation) {
return false;
}
if (*pszWord1 == _T('\0') && *(pszWord2 + 1) == _T('\0')) { // insertion
AddDetails(vTypos, ETypos::Insertion, pszWord1 - pszWord1Start);
++nTypos;
}
else if (*(pszWord1 + 1) == _T('\0') && *pszWord2 == _T('\0')) { // deletion
AddDetails(vTypos, ETypos::Deletion, pszWord1 - pszWord1Start);
++nTypos;
}
else {
return false;
}
}
if (pnTypos != nullptr) {
*pnTypos = nTypos;
}
return true;
} // TypoMatcher
演示程序 Typo Matching 允许通过用户输入来测试错别字匹配。用户可以指定错别字之间的最小间隔。显示的输出是字符串是否匹配，如果匹配则错别字的数量，以及这些错别字类型和位置。请注意，此显示从一开始位置为一。该程序还包括自动测试。
数据库中的匹配
为了在数据库中实现不区分错别字的匹配，有必要编写一个存储函数。存储函数与存储过程不同，因为它必须返回值，并且通过使用 SELECT 语句而不是 CALL 语句来调用。C++ 函数 TypoMatcher() 返回一个布尔结果，并在返回值是 true 时允许检索错别字的数量。在存储函数中，只有一个输出。这在这里是可行的，因为使用返回值 -1 来表示单词不匹配。
下面的列表中的存储函数 TypoMatcher() 是用 MySQL 版本的 SQL 编写的，并使用 MySQL Workbench 进行过测试。遍历单词的循环与 C++ 版本不同，它使用字符位置而不是指针。请注意，SQL 中的字符位置从一开始位置为一。在
DECLARE nWord1Length INT DEFAULT CHAR_LENGTH(TypoWord1);
CHAR_LENGTH() 用于代替 LENGTH() 来计算单词长度，因为它能处理多字节字符。用于访问字符。C++ 行
c1Upper = ::_totupper(*pszWord1);
变成
SET c1Upper = UPPER(SUBSTR(TypoWord1, nWord1Pos, 1));
SUBSTR() 也是多字节安全的。否则，转换非常直接。
下面的列表包含 TypoMatcher() 和用于测试它的 SQL 语句。用于测试的单词与用于 C++ 版本 TypoMatcher() 自动测试的单词相同。测试是通过以下 SQL 语句完成的。
SELECT FindWord, TypoWord, TypoMatcher(FindWord, TypoWord, 2) AS Typos
FROM FindWords, TypoWords HAVING Typos > -1
ORDER BY FindWord, Typos, TypoWord;
TypoMatcher() 的第三个参数是所需的最小错别字间隔。
DROP DATABASE IF EXISTS TypoMatching;
CREATE DATABASE TypoMatching;
USE TypoMatching;
CREATE TABLE TypoWords (
TypoWord VARCHAR(20) NOT NULL
);
INSERT INTO TypoWords VALUES
('matches'),
('Matches'),
('red'),
('care'),
('raed'),
('rads'),
('trenfer'),
('transfrs'),
('spearetion'),
('seepatation'),
('spatation'),
('sdpatation'),
('catch'),
('ingoratjon'),
('lue'),
('xlue'),
('spills'),
('flachljght'),
('flachliht');
CREATE TABLE FindWords (
FindWord VARCHAR(20) NOT NULL
);
INSERT INTO FindWords VALUES
('matches'),
('read'),
('core'),
('transfer'),
('separation'),
('cat'),
('information'),
('blue'),
('spill'),
('flashlight');
DELIMITER $$
CREATE FUNCTION TypoMatcher(TypoWord1 VARCHAR(20), TypoWord2 VARCHAR(20), nMinSeparation INT)
RETURNS INT DETERMINISTIC
BEGIN
DECLARE nTypos INT DEFAULT 0;
DECLARE nLastGoodPos1 INT DEFAULT -10;
DECLARE nWord1Pos INT DEFAULT 1;
DECLARE nWord2Pos INT DEFAULT 1;
DECLARE nWord1Length INT DEFAULT CHAR_LENGTH(TypoWord1);
DECLARE nWord2Length INT DEFAULT CHAR_LENGTH(TypoWord2);
DECLARE c1Upper CHAR;
DECLARE c2Upper CHAR;
DECLARE c1NextUpper CHAR;
DECLARE c2NextUpper CHAR;
WHILE nWord1Pos <= nWord1Length AND nWord2Pos <= nWord2Length
DO
SET c1Upper = UPPER(SUBSTR(TypoWord1, nWord1Pos, 1));
SET c2Upper = UPPER(SUBSTR(TypoWord2, nWord2Pos, 1));
IF c1Upper != c2Upper THEN
IF nWord1Pos - nLastGoodPos1 < nMinSeparation THEN
RETURN -1;
END IF;
SET c1NextUpper = UPPER(SUBSTR(TypoWord1, nWord1Pos + 1, 1));
SET c2NextUpper = UPPER(SUBSTR(TypoWord2, nWord2Pos + 1, 1));
IF c1Upper = c2NextUpper AND c1NextUpper = c2Upper THEN -- transposition
SET nLastGoodPos1 = nWord1Pos + 2;
SET nWord1Pos = nWord1Pos + 1;
SET nWord2Pos = nWord2Pos + 1;
ELSEIF c1Upper = c2NextUpper THEN -- insertion
SET nLastGoodPos1 = nWord1Pos;
SET nWord2Pos = nWord2Pos + 1;
ELSEIF c1NextUpper = c2Upper THEN -- deletion
SET nLastGoodPos1 = nWord1Pos + 1;
SET nWord1Pos = nWord1Pos + 1;
ELSE -- substitution
SET nLastGoodPos1 = nWord1Pos + 1;
END IF;
SET nTypos = nTypos + 1;
END IF;
SET nWord1Pos = nWord1Pos + 1;
SET nWord2Pos = nWord2Pos + 1;
END WHILE;
-- Handles an insertion or a deletion typo at the end of a string.
IF nWord1Pos <= nWord1Length OR nWord2Pos <= nWord2Length THEN
IF nWord1Pos - nLastGoodPos1 < nMinSeparation THEN
RETURN -1;
END IF;
if nWord1Pos = nWord1Length AND nWord2Pos = nWord2Length + 1 THEN -- insertion
SET nTypos = nTypos + 1;
ELSEIF nWord1Pos = nWord1Length + 1 AND nWord2Pos = nWord2Length THEN -- deletion
SET nTypos = nTypos + 1;
ELSE
RETURN -1;
END IF;
END IF;
RETURN nTypos;
END $$
DELIMITER ;
SELECT FindWord, TypoWord, TypoMatcher(FindWord, TypoWord, 2) AS Typos
FROM FindWords, TypoWords HAVING Typos > -1
ORDER BY FindWord, Typos, TypoWord;
结果在下表中
请注意，对于 FindWord 的“read”，错别字的数量为一或二，并且结果按每个 FindWord 的错别字数量排序。当用于数据库搜索时，结果应按错别字数量排序，以便精确匹配优先于只有一个错别字的匹配，然后是错别字更多的匹配。
近似字符串匹配
近似字符串匹配与不区分错别字的字符串匹配不同，前者在要搜索的文本的一部分中查找匹配项，而后者匹配整个文本。从引言中的示例来看，后者在将搜索词与数据库中的单词进行匹配时更有用。
关于近似字符串匹配的维基百科文章概述了各种算法 [1]。其中大多数算法只考虑插入、删除和替换错别字。有些还处理易位错别字。这篇文章指出，可用的算法太慢，无法与数据库一起使用。
在参考文献 2 中，详细介绍了近似字符串匹配的算法。它涉及计算一个差异数组。
TypoMatcher() 可以修改为匹配一个更大的字符串的一部分。当这样使用时，“cat”将匹配“catch”的一部分。当比较单词时，这些单词将不匹配。为了做到这一点，循环后的测试将被修改，以至于不需要第二个字符串结束。更改如下
if (*pszWord1 != _T('\0')) {
if (pLastGoodPos1 != nullptr && pszWord1 - pLastGoodPos1 < nMinSeparation) {
return false;
}
if (*(pszWord1 + 1) == _T('\0')) { // deletion
AddDetails(vTypos, ETypos::Deletion, pszWord1 - pszWord1Start);
++nTypos;
}
else {
return false;
}
}
这个函数将被调用在一个循环中，当发现没有匹配项时，它会一次前进第二个字符串一个字符，并在找到匹配项时报告位置。对于 SQL 版本，这个循环必须是存储函数的一部分。它将返回匹配的起始点，但不会返回错别字的数量。请看下面的列表
DELIMITER $$
CREATE FUNCTION TypoMatcherString(TypoWord1 VARCHAR(20), _
TypoString2 VARCHAR(255), nMinSeparation INT)
RETURNS INT DETERMINISTIC
BEGIN
DECLARE nTypos INT;
DECLARE nLastGoodPos1 INT DEFAULT -10;
DECLARE nWord1Pos INT;
DECLARE nString2Start INT DEFAULT 1;
DECLARE nString2Pos INT;
DECLARE nWord1Length INT DEFAULT CHAR_LENGTH(TypoWord1);
DECLARE nString2Length INT DEFAULT CHAR_LENGTH(TypoString2);
DECLARE c1Upper CHAR;
DECLARE c2Upper CHAR;
DECLARE c1NextUpper CHAR;
DECLARE c2NextUpper CHAR;
outer_while: WHILE nString2Start <= nString2Length DO
SET nWord1Pos = 1;
SET nString2Pos = nString2Start;
SET nTypos = 0;
inner_while: WHILE nWord1Pos <= nWord1Length AND nString2Pos <= nString2Length DO
SET c1Upper = UPPER(SUBSTR(TypoWord1, nWord1Pos, 1));
SET c2Upper = UPPER(SUBSTR(TypoString2, nString2Pos, 1));
IF c1Upper != c2Upper THEN
IF nWord1Pos - nLastGoodPos1 < nMinSeparation THEN
SET nTypos = -1;
LEAVE inner_while;
END IF;
SET c1NextUpper = UPPER(SUBSTR(TypoWord1, nWord1Pos + 1, 1));
SET c2NextUpper = UPPER(SUBSTR(TypoString2, nString2Pos + 1, 1));
IF c1Upper = c2NextUpper AND c1NextUpper = c2Upper THEN -- transposition
SET nLastGoodPos1 = nWord1Pos + 2;
SET nWord1Pos = nWord1Pos + 1;
SET nString2Pos = nString2Pos + 1;
ELSEIF c1Upper = c2NextUpper THEN -- insertion
SET nLastGoodPos1 = nWord1Pos;
SET nString2Pos = nString2Pos + 1;
ELSEIF c1NextUpper = c2Upper THEN -- deletion
SET nLastGoodPos1 = nWord1Pos + 1;
SET nWord1Pos = nWord1Pos + 1;
ELSE -- substitution
SET nLastGoodPos1 = nWord1Pos + 1;
END IF;
SET nTypos = nTypos + 1;
END IF;
SET nWord1Pos = nWord1Pos + 1;
SET nString2Pos = nString2Pos + 1;
END WHILE;
-- Handles a deletion typo at the end of a string.
IF nWord1Pos <= nWord1Length THEN
IF nWord1Pos - nLastGoodPos1 < nMinSeparation THEN
SET nTypos = -1;
ELSEIF nWord1Pos = nWord1Length + 1 THEN -- deletion
SET nTypos = nTypos + 1;
ELSE
SET nTypos = -1;
END IF;
END IF;
IF nTypos = -1 THEN
SET nString2Start = nString2Start + 1;
ELSE
LEAVE outer_while;
END IF;
END WHILE;
IF nTypos = -1 THEN
RETURN -1;
ELSE
RETURN nString2Start;
END IF;
END $$
DELIMITER ;
结果在下表中
请注意，“cat”现在匹配多个项目，而以前不匹配任何项目。它匹配“do catch”，其中单词从第四个位置开始。另请注意，“transfer”现在匹配“transfrs”，而以前不匹配。原因是，当作为单词匹配时，两个错别字太近，而当作为字符串中的单词匹配时，多余的字符将被忽略。
时间复杂度
如果模式字符串有 m 个字符，文本字符串有 n 个字符，则近似字符串匹配的时间复杂度为 O(m * n) [1]。这在所有情况下都适用，因为会计算一个数组来进行匹配。
上面提出的不区分错别字的字符串匹配算法在比较单词时的时间复杂度为 O(min(m, n))，因为循环在其中一个字符串结束或发现两个错别字太近时停止。这应该足够快，可以进行数据库搜索。
当用于查找一个更大的字符串的一部分时，时间复杂度最坏情况为 O(m * n)。但是，由于它会在发现两个错别字太近后停止，因此平均时间复杂度较低。
参考文献
- [1] “Approximate string matching” (2021, Jan. 18). Wikipedia
- {2] Binstock, A., & Rex, J. (1995). Practical Algorithms For Programmers, Addison-Wesley Publishing Company. pp. 148-156. ISBN 0-201-63208-X
历史
- 2021年7月7日：初始版本
- 2021年7月9日：上传演示程序