ค้นหาการจับคู่โดยประมาณด้วยฟังก์ชันสตริงคลุมเครือ

ข้อมูลในโลกแห่งความเป็นจริงไม่ค่อยตรงกันอย่างสมบูรณ์แบบ ชื่อลูกค้าอาจสะกดผิด ที่อยู่ย่อต่างกัน หรือป้อนคําอธิบายผลิตภัณฑ์ไม่สอดคล้องกัน ฟังก์ชันการจับคู่สตริงแบบคลุมเครือช่วยให้คุณค้นหาเรกคอร์ดที่คล้ายกันแต่ไม่เหมือนกัน ซึ่งช่วยให้สามารถปรับปรุงคุณภาพข้อมูล การตรวจหารายการที่ซ้ํากัน และความสามารถในการค้นหาที่ยืดหยุ่นยิ่งขึ้น

ทําความเข้าใจแนวคิดความคล้ายคลึงกันของสตริง

อัลกอริทึมการจับคู่แบบคลุมจะวัดว่าสตริงสองตัวมีความคล้ายคลึงกันเพียงใดโดยการคํานวณความแตกต่างระหว่างสตริงทั้งสอง มักใช้สองแนวทางหลัก:

ระยะการแก้ไข (ระยะทาง Levenshtein) นับจํานวนขั้นต่ําของการดําเนินการอักขระเดียว (การแทรก การลบ การแทนที่) ที่จําเป็นในการแปลงสตริงหนึ่งเป็นอีกสตริงหนึ่ง ค่าที่ต่ํากว่าบ่งชี้ว่าสตริงที่คล้ายกันมากขึ้น

คะแนนความคล้ายคลึงกัน แสดงความสัมพันธ์ระหว่างสตริงเป็นเปอร์เซ็นต์หรืออัตราส่วน โดยที่ค่าที่สูงขึ้นบ่งชี้ถึงความคล้ายคลึงกันมากขึ้น

พิจารณาตัวอย่างเหล่านี้:

• "color" → "color": แก้ไขระยะทาง = 1 (แทรก 'u')
• "ฐานข้อมูล" → "databaes": แก้ไขระยะทาง = 2 (สลับ 'e' และ 's')
• "Microsoft" → "Microsft": แก้ไขระยะทาง = 1 (ลบ 'o')

คํานวณระยะการแก้ไขด้วย EDIT_DISTANCE

ฟังก์ชันส่งคืน EDIT_DISTANCE ระยะห่าง Levenshtein ระหว่างสองสตริง ซึ่งเป็นจํานวนการแก้ไขขั้นต่ําที่จําเป็นในการแปลงสตริงหนึ่งเป็นอีกสตริงหนึ่ง เป้าหมายคือการค้นหาสตริงที่คล้ายกันตามเกณฑ์ที่กําหนดไว้

ตัวอย่างต่อไปนี้สาธิตวิธีใช้ 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

คุณสามารถใช้ EDIT_DISTANCE เพื่อค้นหาระเบียนที่อาจซ้ํากันหรือตรงกันแม้จะมีการเปลี่ยนแปลงเล็กน้อย:

-- 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);

นอกจากนี้ คุณยังสามารถค้นหาผลิตภัณฑ์ที่ซ้ํากันได้:

-- 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);

วัดความคล้ายคลึงกันด้วย EDIT_DISTANCE_SIMILARITY

EDIT_DISTANCE_SIMILARITY ส่งกลับคะแนนความคล้ายคลึงกันที่ทําให้เป็นมาตรฐานระหว่าง 0 ถึง 100 โดยที่ 100 แสดงถึงสตริงที่เหมือนกัน เมตริกตามเปอร์เซ็นต์นี้ตีความได้ง่ายกว่าระยะการแก้ไขดิบ โดยเฉพาะอย่างยิ่งเมื่อเปรียบเทียบสตริงที่มีความยาวต่างกัน

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

คุณสามารถใช้คะแนนความคล้ายคลึงกันเพื่อค้นหาการจับคู่โดยประมาณที่มีเกณฑ์ดังตัวอย่างต่อไปนี้:

-- 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;

คํานวณความคล้ายคลึงกันทางการออกเสียงด้วย JARO_WINKLER_DISTANCE

อัลกอริทึม Jaro-Winkler ออกแบบมาสําหรับการเปรียบเทียบชื่อและสตริงสั้น โดยให้คะแนนที่สูงขึ้นกับสตริงที่ตรงกันตั้งแต่เริ่มต้น ทําให้มีประสิทธิภาพสําหรับชื่อบุคคลที่มีคํานําหน้ามีความสําคัญมากกว่า:

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

คะแนน Jaro-Winkler มีตั้งแต่ 0 ถึง 1 โดยที่ 1 หมายถึงสตริงที่เหมือนกัน คะแนนที่สูงกว่า 0.9 โดยทั่วไปบ่งชี้ว่าชื่อตรงกัน

ตัวอย่างต่อไปนี้พบลูกค้าที่มีชื่อคล้ายกับการป้อนข้อมูลการค้นหา:

-- 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;

ข้อควรพิจารณาเกี่ยวกับประสิทธิภาพการทำงาน

ฟังก์ชันการจับคู่แบบคลุมจะตรวจสอบอักขระทุกตัวในทั้งสองสตริง การเปรียบเทียบสตริงที่แน่นอนสามารถหยุดได้ทันทีที่อักขระต่างกัน และการค้นหาที่จัดทําดัชนีจะใช้การสํารวจ B-tree ที่มีประสิทธิภาพ ในทางตรงกันข้ามอัลกอริทึมคลุมเครือต้องคํานวณคะแนนความคล้ายคลึงกันทีละอักขระ สําหรับตารางที่มีแถว 1,000,000 แถว การค้นหาแบบคลุมเครือที่ไม่ได้ปรับให้เหมาะสมอาจทําการคํานวณความคล้ายคลึงกัน 1,000,000 รายการ โดยแต่ละรายการเกี่ยวข้องกับการเปรียบเทียบอักขระหลายสิบตัว

กุญแจสําคัญในการจับคู่แบบคลุมเครืออย่างมีประสิทธิภาพคือการลดชุดผู้สมัครก่อนที่จะใช้ฟังก์ชันคลุมเครือที่มีราคาแพง ใช้คอลัมน์ที่จัดทําดัชนีที่มี LIKE รูปแบบ การจับคู่แบบตรงทั้งหมดในฟิลด์ที่เกี่ยวข้อง หรือตัวกรองช่วงเพื่อจํากัดผลลัพธ์ให้แคบลงก่อน จากนั้นใช้การจับคู่แบบคลุมเครือกับชุดผู้สมัครที่เล็กกว่าเท่านั้น

ตัวอย่างต่อไปนี้แสดงวิธีการกรองแบบโปรเกรสซีฟนี้:

-- 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;

สําหรับข้อมูลเพิ่มเติมเกี่ยวกับการจับคู่สตริงแบบคลุมซาก โปรดดู ฟังก์ชันสตริง