q-gram近似匹配优化

Question

我有一张包含300万人记录的表，我想用q-grams（例如姓氏）执行模糊匹配。我创建了一个链接到这个2克的表格，但是在这个数据量上搜索性能不是很好（大约5分钟）。 （1）你可以提出任何方法来提高性能，以避免表扫描（即必须计算搜索字符串和300万姓氏之间的常见q-gram） （2）With q-gram，如果A与B类似，C与B类似，是否意味着C与A相似？

亲切的问候

彼得

Answer 1

我一直在寻找到模糊的字符串匹配最近，所以即使在回答一个废弃问题的风险，在这里不用。希望您觉得这个有帮助。

我想你只对编辑距离小于给定值的字符串感兴趣。而你的Q-克（或正克）这个样子

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

1. 你可以使用位置 Q-克：

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

   位置信息可以用于确定匹配 q-gram确实是一个“很好的匹配”。

   例如，如果您正在寻找 “foobar的”最大编辑距离的2 ，这意味着你只能在 感兴趣的话，其中

   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克由 3.

2. 也各不相同，它可能是到u有用se 编辑距离 与匹配q-克数的关系。 的intution是，由于

   字符串s已LEN（S）-q + 1 Q-克

   和

   单个编辑操作可在最Q Q-克影响，

   我们可以推断，d的编辑距离内

   串s1和s2具有至少 max（len（s1），len（s2）） - q + 1-qk匹配非位置q-gram。

   如果你正在为2的最大编辑距离，匹配 7个字符的字符串（如 “fotocar”）搜索“foobar的” 应至少包含 两种常见的2克。

3. 最后，显而易见的事情是 到筛选长度。两个字符串之间的编辑距离至少为 字符串的长度的差值 。例如，如果您的 阈值为2，并且您搜索 “foobar”，则“foobarbar”不能与 明显匹配。

请参阅http://pages.stern.nyu.edu/~panos/publications/deb-dec2001.pdf了解更多和一些伪SQL。

Answer 2

关于索引DNA Q-克有趣的论文，这样你就不必扫描整个表：

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

Answer 3

你无疑到处都看到了模糊的文字搜索。例如，你输入“stck”，但你实际上是指“堆栈”！有没有想过这个东西是如何工作的？

有很多算法可以进行模糊文本匹配，每种算法都有自己的亲和好。最着名的是编辑距离和qgram。我想今天专注于qgram并实施示例。

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

2-gram表示每个单词都被分解为一组两个字符。 “堆栈”将被分成一组{“st”，“ta”，“ac”，“ck”}或“数据库”将被分成{“da”，“at”，“ta”，“ba ”， “是”， “SE”}。

将单词分解为2-grams后，我们可以在数据库中搜索一组值而不是一个字符串。例如，如果用户输错“stck”，任何对“stck”的搜索都不会匹配“stack”，因为缺少“a”，但2-gram set {“st”，“tc”，“ck”}有2行与2克套装一样！宾果我们发现了一个非常接近的比赛。它与2-gram数据库集没有什么共同之处，与2-gram的“stat”集只有1个共同点，所以我们可以很容易地建议用户他打算输入：第一个“堆栈”或第二个“ ”。

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

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

克表应该聚集在第一个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 

现在让我们查询词 “堆栈”，这将被打破：{ 'ST'， 'TA'， '交流'， '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表是巨大的，数百万的loockups将比完整的索引扫描更昂贵。

Answer 4

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

示例：我们的源表包含一列中的文本条目。 我们创造，我们使用

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. 

这应该在一个循环运行一分为2克的名字一个临时表，其中i = 0和j =源条目的最大尺寸。

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

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

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

这使得大量的比较，但其中大多数是2位整数，这是非常快速的。