查找具有相似字元串值的行

我有一個 Microsoft SQL Server 2012 數據庫表，其中包含大約 700 萬條眾包記錄，主要包含帶有一些相關細節的字元串名稱值。對於幾乎每條記錄，似乎都有十幾個類似的拼寫錯誤記錄，我正在嘗試進行一些模糊匹配來辨識記錄組，例如“Apple”、“Aple”、“Apples”、“Spple”等。這些名稱也可以包含多個單詞，它們之間有空格。

我想出了一個使用編輯距離標量函式的解決方案，該函式返回從 string1 轉換為 string2 所需的擊鍵次數，並使用該函式將表連接到自身。正如您可以想像的那樣，這並沒有表現得那麼好，因為它必須執行數百萬次函式來評估連接。

所以我把它放在一個游標中，所以一次至少只評估一個 string1，這至少會得到結果，但在讓它執行幾週後，它只評估了 150,000 條記錄。有 700 萬要評估，我認為我沒有我的方法需要花費的時間。

我在字元串名稱上放置了全文索引，但是當我沒有正在搜尋的靜態值時，我真的找不到使用全文謂詞的方法。

有什麼想法我可以以不需要幾個月的時間來執行以下操作嗎？

 SELECT t1.name, t2.name
 FROM names AS t1
 INNER JOIN names AS t2
      ON EditDistance(t1.name,t2.name) = 1
      AND t1.id != t2.id

我試過soundex了，但由於名稱可以包含空格和每個值的多個單詞，我得到太多誤報，無法可靠地使用它。

解決了這個問題後，最有效和最高效的方法是創建一個計算 Levenshtein 距離的 CLR 函式。您將能夠將程序集標記為 SAFE（如果您完全關心安全性），它的執行速度比 SOUNDEX() 或任何內置 SQL Server 函式快得多。

這是在數據庫中設置程序集和函式的程式碼，以及在 C# 中實現的 Levenshtein 距離算法的基本版本，來自https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#C#

C＃：

using System;
using System.Security.Cryptography;

namespace LevenshteinDistance
{
   public class LevenshteinDistance
   {
       private int LevenshteinDistance(string a, string b)
       {
           if (string.IsNullOrEmpty(a))
           {
               if (!string.IsNullOrEmpty(b))
               {
                   return b.Length;
               }
               return 0;
           }

           if (string.IsNullOrEmpty(b))
           {
               if (!string.IsNullOrEmpty(a))
               {
                   return a.Length;
               }
               return 0;
           }

           int cost;
           int[,] d = new int[a.Length + 1, b.Length + 1];
           int min1;
           int min2;
           int min3;

           for (int i = 0; i <= d.GetUpperBound(0); i += 1)
           {
               d[i, 0] = i;
           }

           for (int i = 0; i <= d.GetUpperBound(1); i += 1)
           {
               d[0, i] = i;
           }

           for (int i = 1; i <= d.GetUpperBound(0); i += 1)
           {
               for (int j = 1; j <= d.GetUpperBound(1); j += 1)
               {
                   cost = (a[i-1] != b[j-1])? 1 : 0; 

                   min1 = d[i - 1, j] + 1;
                   min2 = d[i, j - 1] + 1;
                   min3 = d[i - 1, j - 1] + cost;
                   d[i, j] = Math.Min(Math.Min(min1, min2), min3);
               }
           }
           return d[d.GetUpperBound(0), d.GetUpperBound(1)];
       }        
   }
}

T-SQL：

use [master];
go

exec sp_configure 'clr enabled', 1;
go
reconfigure with override;
go

use [database_name];
go

-- Drop the function...
if exists (select 1 from sys.objects so where so.[name] = 'LevenshteinDistance')
   drop function dbo.LevenshteinDistance;
go

-- ...then the assembly
if exists (select 1 from sys.assemblies sa where sa.[name] = 'LevenshteinDistance')
   drop assembly [LevenshteinDistance];
go

-- Now load the assembly from an appropriately accessible location
create assembly [LevenshteinDistance]
from
   'd:\LevenshteinDistance.dll'
with
   permission_set = safe;
go

-- Create an asymmetric key from the assembly file
use [master];
go

if not exists (select 1 from sys.asymmetric_keys ak where ak.[name] = 'LevenshteinDistanceKey')
begin
   create asymmetric key LevenshteinDistanceKey
   from executable file = 'd:\LevenshteinDistance.dll';
end
go

-- Create a user to associate with the assembly from the asymmetric key, and then
-- revoke connect access. The login is used to execute the assembly.
use [master];
go

if not exists (select 1 from sys.server_principals sp where sp.[name] = 'LevenshteinDistanceKeyUser')
begin
   create login LevenshteinDistanceKeyUser from asymmetric key LevenshteinDistanceKey;
   revoke connect sql from LevenshteinDistanceKeyUser;
end
go

grant external access assembly to LevenshteinDistanceKeyUser;
go

use [database_name];
go
alter assembly [LevenshteinDistance] with permission_set = safe;
go

-- Create the SQL function which will be called
create function [dbo].LevenshteinDistance
(
   @string1 nvarchar(2048)
   ,@string2 nvarchar(2048)
)
returns nvarchar(max)
as
   external name LevenshteinDistance.[LevenshteinDistance.LevenshteinDistance].LevenshteinDistance;
go

通常我會在這個上選擇 SOUNDEX。問題是您的“Apple”字元串的 soundex 為“A140”，而 Spple 的 Soundex 為“S140”。無論如何，你應該試一試，看看它是否對你有幫助。不過，它確實適用於“Aple”和“Apples”。

https://docs.microsoft.com/en-us/sql/t-sql/functions/soundex-transact-sql

 SELECT SOUNDEX('Apple'), 
        SOUNDEX('Spple'), 
        SOUNDEX('Aple'), 
        SOUNDEX('Apples')

問題是您必須在 where 子句中添加一個函式。對於您的優化器來說，這總是……有趣……

編輯： 差異也應該有用。

引用自：https://dba.stackexchange.com/questions/181566