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位整數，這是非常快速的。