q-gram近似匹配优化

Question

我有一个包含300万人记录的表,我希望使用q-gram(例如姓氏)进行模糊匹配.我已经创建了一个2-gram链接表,但是在这个数据卷上搜索性能不是很好(大约5分钟).

我基本上有两个问题:(1)你能否提出任何提高性能的方法来避免表格扫描(即必须计算搜索字符串和300万个姓氏之间的常见q-gram)(2)q-gram,如果A类似于B和C类似于B,它是否意味着C类似于A？

亲切的问候

彼得

Answer 1

我最近一直在研究模糊字符串匹配,所以即使冒着回答废弃问题的风险,也就是这样.希望您觉得这个有帮助.

我想你只对编辑距离小于给定值的字符串感兴趣.你的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,

   我们可以推断出这一点

   串s1和d的编辑距离S2内具有至少最大(LEN(S1),LEN(S2)) - Q + 1-QK匹配的非位置Q-克.

   如果您正在搜索最大编辑距离为2的"foobar",则匹配的7个字符的字符串(例如"fotocar")应包含至少两个常用的2克.

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

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

Answer 2

你肯定已经看到了模糊的文本搜索.例如,您键入"stck",但实际上您的意思是"堆栈"!曾经想知道这些东西是如何工作的？

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

基本上,qgrams是最适合关系数据库的模糊字符串匹配算法.这很简单.qgram中的"q"将被替换为2克或3克甚至4克的数字.

2克意味着每个单词都被分成一组两个字符克."堆栈"将被分成一组{"st","ta","ac","ck"}或"数据库"将分为{"da","at","ta","ba" ", "是", "SE"}.

一旦单词被分成2-gram,我们就可以在数据库中搜索一组值而不是一个字符串.例如,如果用户输入错误"stck",则任何搜索"stck"将不匹配"stack",因为"a"缺失,但2-gram set {"st","tc","ck"}有2行与2克堆栈一样!Bingo我们找到了一个非常接近的比赛.它与2-gram数据库集没有任何共同之处,与2-gram"stat"集合只有1个共同点,因此我们可以轻松地向用户建议他打算输入:第一个"堆栈"或第二个,"明星" ".

现在让我们使用Sql Server实现它:假设一个假设的单词数据集.你需要在2个图和单词之间建立多对多的关系.

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使用一堆聚集索引搜索(或loockups)来运行此查询.它应该是自然的选择,但有时统计信息可能已损坏或过时,SqlServer可能会认为完整扫描更便宜.如果它不知道左侧表的基数,通常会发生这种情况,例如SqlServer可能会认为@word表是庞大的,并且数百万个loockup将比完整索引扫描更昂贵.