7

我有一个包含 300 万个人记录的表，我想在其上使用 q-grams 执行模糊匹配（例如姓氏）。我已经创建了一个 2 克表链接到这个，但是在这个数据量（大约 5 分钟）上搜索性能不是很好。

我基本上有两个问题：（1）你能建议任何方法来提高性能以避免表扫描（即必须计算搜索字符串和 300 万个姓氏之间的常见 q-gram）（2）使用 q-gram，如果 A与 B 相似，C 与 B 相似，是否意味着 C 与 A 相似？

亲切的问候

彼得

4

4 回答 4

10

您肯定已经到处看到模糊文本搜索。例如，您键入“stck”，但实际上是“stack”！有没有想过这些东西是如何工作的？

有很多算法可以进行模糊文本匹配，每种算法都有自己的优缺点。最著名的是编辑距离和qgram。我今天想专注于 qgrams 并实现一个示例。

基本上 qgrams 是最适合关系数据库的模糊字符串匹配算法。这很简单。qgram 中的“q”将被替换为 2-gram 或 3-gram 甚至 4-gram 之类的数字。

2-gram 意味着每个单词都被分成一组两个字符的gram。"Stack" 将被分解为一组 {"st", "ta", "ac", "ck"} 或 "database" 将被分解为 {"da","at","ta","ab ","ba","as","se"}.

一旦单词被分解成 2-gram，我们就可以在数据库中搜索一组值而不是一个字符串。例如，如果用户输入错误的“stck”，任何对“stck”的搜索都不会匹配“stack”，因为缺少“a”，但是 2-gram set {"st","tc","ck"} 有 2 行与 2-gram 堆栈相同！宾果游戏我们发现了一个非常接近的匹配。它与 2-gram 的数据库集没有任何共同之处，而与 2-gram 的“stat”集只有 1 个共同点，因此我们可以很容易地向用户建议他要键入的内容：第一个“stack”或第二个“star” ”。

现在让我们使用 Sql Server 来实现它：假设一个假设的单词数据集。您需要在 2grams 和单词之间建立多对多关系。

CREATE TABLE Grams(twog char(2), wordId int, PRIMARY KEY (twog, wordId))

Grams 表应该聚集在第一个 twog 上，然后是 wordId 以提高性能。当您查询一个单词（例如堆栈）时，您将克数放在一个临时表中。首先让我们创建几百万个虚拟记录。

--make millions of 2grams
 DECLARE @i int =0
 WHILE (@i<5000000)
 BEGIN
-- a random 2gram
 declare @rnum1 char = CHAR(CAST(RAND()*28 AS INT)+97)
 declare @rnum2 char = CHAR(CAST(RAND()*28 AS INT)+97)
 INS... INTO Grams (twog, wordId) VALUES ( @rnum1 + @rnum2, CAST(RAND()*100000 AS int))
 END

现在让我们查询单词“stack”，它将被分解为：{'st','ta','ac','ck'} 两克。

DECLARE @word TABLE(twog char(2)) -- 'stack'
 INS... INTO @word VALUES ('st'), ('ta'), ('ac'), ('ck')

select wordId, count(*) from @word w inner join Grams g ON w.twog = g.twog
 GROUP BY wordId

您应该确保 Sql Server 使用一堆聚集索引查找（或查找）来运行此查询。这应该是自然的选择，但有时统计数据可能已损坏或过时，SqlServer 可能会决定全面扫描更便宜。如果它不知道左侧表的基数，通常会发生这种情况，例如 SqlServer 可能会假设@word 表很大，并且数百万个查找将比全索引扫描更昂贵。

于 2011-09-21T05:54:32.647 回答
6

我最近一直在研究模糊字符串匹配，所以即使冒着回答一个被遗弃的问题的风险，这里也可以。希望您觉得这个有帮助。

我想您只对编辑距离小于给定值的字符串感兴趣。你的 q-gram（或 n-gram）看起来像这样

2-grams for "foobar": {"fo","oo","ob","ba","ar"}

  1. 您可以使用位置q-gram：

    "foobar": {("fo",1),("oo",2),("ob",3),("ba",4),("ar",5)}

    位置信息可用于确定匹配的 q-gram 是否真的是“良好匹配”。

    例如，如果您正在搜索最大编辑距离为 2 的“foobar”，这意味着您只对以下单词感兴趣

    2-gram "fo" exists in with position from 1 to 3 or
2-gram "oo" exists in with position from 2 to 4 or
... and so on

    字符串“barfoo”没有得到任何匹配，因为其他匹配的 2-gram 的位置相差 3。

  2. 此外，使用编辑距离和匹配 q-gram 计数之间的关系可能很有用。直觉是，因为

    一个字符串 s 有 len(s)-q+1 个 q-gram

    和

    单个编辑操作最多可以影响 q 个 q-gram，

    我们可以推断出

    在 d 的编辑距离内的字符串 s1 和 s2 至少有 max(len(s1),len(s2))-q+1-qk 匹配非位置 q-gram。

    如果您要搜索最大编辑距离为 2 的“foobar”，则匹配的 7 个字符的字符串（例如“fotocar”）应至少包含两个常见的 2-gram。

  3. 最后，显而易见的事情是按长度过滤。两个字符串之间的编辑距离至少是字符串长度的差异。例如，如果您的阈值为 2，并且您搜索“foobar”，则“foobarbar”显然无法匹配。

有关更多信息和一些伪 SQL，请参见http://pages.stern.nyu.edu/~panos/publications/deb-dec2001.pdf。

于 2010-03-04T07:32:57.070 回答
2

关于索引 DNA q-gram 的有趣论文，因此您不必扫描整个表：

www.comp.nus.edu.sg/~atung/publication/qgram_edit.pdf

于 2010-08-05T13:19:18.453 回答
0

我有一个简单的改进，它不会消除扫描，但如果你只使用 2 克或 3 克，它会加快速度：用数字替换字母。大多数 SQL 引擎在比较数字时工作得更快。

示例：我们的源表在一列中包含文本条目。我们创建一个临时表，在其中使用 2-gram 拆分名称

SELECT SUBSTRING (column, 1,2) as gram, 1 as position FROM sourcetable
UNION  
SELECT SUBSTRING (column, 2,2) as gram, 2 as position FROM sourcetable
UNION
SELECT SUBSTRING (column, 3,2) as gram, 3 as position FROM sourcetable

etc.

这应该在 i=0 和 j=源条目的最大大小的循环中运行。

然后我们准备一个映射表，其中包含所有可能的 2 字母gram，并包含一个名为 gram_id 的 IDENTITY (1,1) 列。我们可以在英语词典中按频率对克进行排序，并消除最不常见的克（如“kk”或“wq”）——这种排序可能需要一些时间和研究，但它会将最小的数字分配给最频繁的克，这如果我们可以将克数限制为 255，那么将提高性能，因为我们可以为 gram_id 使用 tinyint 列。

然后我们从第一个临时表重建另一个临时表，我们使用 gram_id 而不是 gram。这成为主表。我们在 gram_id 列和 position 列上创建索引。

然后当我们必须将一个文本字符串与主表进行比较时，我们首先将文本字符串拆分为 2-gram，然后将 2-gram 替换为它们的 gram_id（使用映射表），并将它们与其中的一个进行比较主表

这进行了很多比较，但其中大多数是 2 位整数，这非常快。

于 2018-01-08T13:44:48.957 回答