Vyhledání přibližných shod pomocí přibližných řetězcových funkcí

Data z reálného světa zřídka dokonale odpovídají. Jména zákazníků můžou být chybně napsaná, adresy se zkracují jinak nebo popisy produktů zadané nekonzistentně. Funkce porovnávání přibližných řetězců pomáhají najít záznamy, které jsou podobné, ale ne identické, což umožňuje vylepšení kvality dat, detekci duplicit a flexibilnější možnosti vyhledávání.

Vysvětlení konceptů podobnosti řetězců

Přibližné odpovídající algoritmy měří, jak podobné dva řetězce jsou výpočetem rozdílů mezi nimi. Běžně se používají dva primární přístupy:

Editorová vzdálenost (Levenshteinova vzdálenost) spočítá minimální počet operací s jedním znakem (vložení, odstranění, nahrazení) potřebných k transformaci jednoho řetězce na druhý. Nižší hodnoty označují více podobných řetězců.

Skóre podobnosti vyjadřují vztah mezi řetězci jako procento nebo poměr, kde vyšší hodnoty označují větší podobnost.

Podívejte se na tyto příklady:

• "barva" → "barva": vzdálenost upravení = 0 (žádné písmeno nepřidáno)
• database → databaes: edit distance = 2 (prohození 'e' a 's')
• "Microsoft" → "Microsoft": vzdálenost úprav = 1 (vymazání 'o')

Výpočet vzdálenosti úprav pomocí EDIT_DISTANCE

Funkce EDIT_DISTANCE vrátí vzdálenost Levenshtein mezi dvěma řetězci, což je minimální počet úprav potřebných k transformaci jednoho řetězce na druhý. Cílem je najít řetězce, které jsou podobné na základě definované prahové hodnoty.

Následující příklad ukazuje použití EDIT_DISTANCE:

SELECT 
    EDIT_DISTANCE('color', 'colour') AS ColorVariant,     -- Returns 1
    EDIT_DISTANCE('database', 'databaes') AS Typo,        -- Returns 2
    EDIT_DISTANCE('SQL Server', 'SQL Server') AS Exact,   -- Returns 0
    EDIT_DISTANCE('hello', 'world') AS Different;         -- Returns 4

Můžete použít EDIT_DISTANCE k vyhledání záznamů, které můžou být duplicitní nebo shodné, i přes mírné variace:

-- Find customers with similar names to a search term
DECLARE @searchName NVARCHAR(100) = 'Jon Smith';

SELECT 
    CustomerID,
    FirstName,
    LastName,
    FirstName + ' ' + LastName AS FullName,
    EDIT_DISTANCE(@searchName, FirstName + ' ' + LastName) AS EditDistance
FROM SalesLT.Customer
WHERE EDIT_DISTANCE(@searchName, FirstName + ' ' + LastName) <= 3
ORDER BY EDIT_DISTANCE(@searchName, FirstName + ' ' + LastName);

Můžete také najít potenciální duplicitní produkty:

-- Find product pairs with similar names
SELECT 
    p1.ProductID AS Product1ID,
    p1.Name AS Product1Name,
    p2.ProductID AS Product2ID,
    p2.Name AS Product2Name,
    EDIT_DISTANCE(p1.Name, p2.Name) AS EditDistance
FROM SalesLT.Product AS p1
INNER JOIN SalesLT.Product AS p2
    ON p1.ProductID < p2.ProductID
WHERE EDIT_DISTANCE(p1.Name, p2.Name) <= 5
ORDER BY EDIT_DISTANCE(p1.Name, p2.Name);

Měření podobnosti s využitím EDIT_DISTANCE_SIMILARITY

EDIT_DISTANCE_SIMILARITY vrátí normalizované skóre podobnosti mezi 0 a 100, kde 100 představuje identické řetězce. Tato procentuální metrika je srozumitelnější než surová editační vzdálenost, zejména při porovnávání řetězců různých délek:

SELECT 
    EDIT_DISTANCE_SIMILARITY('color', 'colour') AS ColorSimilarity,     -- ~85
    EDIT_DISTANCE_SIMILARITY('database', 'databaes') AS TypoSimilarity, -- ~75
    EDIT_DISTANCE_SIMILARITY('SQL', 'SQL Server') AS PartialMatch,      -- ~30
    EDIT_DISTANCE_SIMILARITY('hello', 'hello') AS Exact;                -- 100

Skóre podobnosti můžete použít k vyhledání přibližných shod s prahovou hodnotou jako v následujícím příkladu:

-- Find products similar to a search term (at least 70% similar)
DECLARE @searchTerm NVARCHAR(100) = 'Mountain Bike Frame';

SELECT 
    ProductID,
    Name,
    EDIT_DISTANCE_SIMILARITY(@searchTerm, Name) AS SimilarityScore
FROM SalesLT.Product
WHERE EDIT_DISTANCE_SIMILARITY(@searchTerm, Name) >= 70
ORDER BY EDIT_DISTANCE_SIMILARITY(@searchTerm, Name) DESC;

Výpočet fonetické podobnosti pomocí JARO_WINKLER_DISTANCE

Algoritmus Jaro-Winkler je určený pro porovnávání názvů a krátkých řetězců. Poskytuje vyšší skóre řetězcům, které se shodují od začátku, takže je efektivní pro jména osob, kde jsou předpony významnější:

SELECT 
    JARO_WINKLER_DISTANCE('MARTHA', 'MARHTA') AS NameTypo,      -- ~0.96
    JARO_WINKLER_DISTANCE('JONES', 'JOHNSON') AS SimilarNames,  -- ~0.83
    JARO_WINKLER_DISTANCE('JOHN', 'JON') AS NameVariant,        -- ~0.93
    JARO_WINKLER_DISTANCE('SMITH', 'SMYTH') AS SpellingVar;     -- ~0.96

Skóre Jaro-Winkler se pohybuje od 0 do 1, kde 1 označuje identické řetězce. Skóre nad 0,9 obvykle označuje silnou shodu pro jména.

Následující příklad najde zákazníky s jmény podobnými hledanému výrazu.

-- Find customers with names similar to a search
DECLARE @searchFirst NVARCHAR(50) = 'John';
DECLARE @searchLast NVARCHAR(50) = 'Smythe';

SELECT 
    CustomerID,
    FirstName,
    LastName,
    JARO_WINKLER_DISTANCE(@searchFirst, FirstName) AS FirstNameScore,
    JARO_WINKLER_DISTANCE(@searchLast, LastName) AS LastNameScore,
    (JARO_WINKLER_DISTANCE(@searchFirst, FirstName) + 
     JARO_WINKLER_DISTANCE(@searchLast, LastName)) / 2 AS CombinedScore
FROM SalesLT.Customer
WHERE JARO_WINKLER_DISTANCE(@searchFirst, FirstName) > 0.85
  AND JARO_WINKLER_DISTANCE(@searchLast, LastName) > 0.85
ORDER BY CombinedScore DESC;

Důležité informace o výkonu

Přibližné odpovídající funkce prověřují každý znak v obou řetězcích, takže jsou výpočetně náročné. Přesné porovnávání řetězců se může zastavit, když se znaky liší, a indexovaná vyhledávání používají efektivní procházení B-stromu. Naproti tomu musí fuzzy algoritmy vypočítat skóre podobnosti po jednotlivých znacích. U tabulky s 1 000 000 řádky může neoptimalizované vyhledávání přibližné řady provádět 1 000 000 výpočtů podobnosti, přičemž každá zahrnuje desítky porovnání znaků.

Klíčem k efektivnímu porovnávání přibližných shod je snížení kandidátské sady před použitím drahých fuzzy funkcí. Pomocí indexovaných sloupců můžete nejprve zúžit výsledky pomocí LIKE vzorů, přesných shod souvisejících polí nebo filtrů rozsahu. Teprve potom použijte přibližné shody na menší kandidátskou sadu.

Následující příklady ukazují tento postup postupného filtrování:

-- Not good: Fuzzy match against entire table
SELECT * FROM LargeCustomerTable
WHERE EDIT_DISTANCE_SIMILARITY('John Smith', FullName) > 70;

-- Better: Pre-filter before fuzzy matching
SELECT * FROM LargeCustomerTable
WHERE FullName LIKE 'J%'  -- First letter filter
  AND EDIT_DISTANCE_SIMILARITY('John Smith', FullName) > 70;

-- Best: Use multiple pre-filters
SELECT * FROM LargeCustomerTable
WHERE FirstName LIKE 'Jo%'
  AND LastName LIKE 'Sm%'
  AND JARO_WINKLER_DISTANCE('John', FirstName) > 0.85
  AND JARO_WINKLER_DISTANCE('Smith', LastName) > 0.85;

Další informace o porovnávání přibližných řetězců naleznete v tématu Řetězcové funkce.