Temukan perkiraan kecocokan dengan fungsi string fuzzy

Data dunia nyata jarang cocok dengan sempurna. Nama pelanggan mungkin salah eja, alamat yang disingkat berbeda, atau deskripsi produk dimasukkan secara tidak konsisten. Fungsi pencocokan string fuzzy membantu Anda menemukan rekaman yang serupa tetapi tidak identik, memungkinkan peningkatan kualitas data, deteksi duplikat, dan kemampuan pencarian yang lebih fleksibel.

Memahami konsep kesamaan string

Algoritma pencocokan fuzzy mengukur seberapa mirip dua string dengan menghitung perbedaan di antara mereka. Dua pendekatan utama umumnya digunakan:

Edit jarak (Jarak Levenshtein) menghitung jumlah minimum operasi karakter tunggal (penyisipan, penghapusan, substitusi) yang diperlukan untuk mengubah satu string menjadi string lainnya. Nilai yang lebih rendah menunjukkan string yang lebih mirip.

Skor kesamaan mengekspresikan hubungan antara string sebagai persentase atau rasio, di mana nilai yang lebih tinggi menunjukkan kesamaan yang lebih besar.

Pertimbangkan contoh berikut:

• id-ID: "warna" → "warna dengan 'u' tambahan": jarak edit = 1 (tambah 'u')
• "database" → "databaes": jarak edit = 2 (menukar 'e' dan 's')
• "Microsoft" → "Microsft": edit jarak = 1 (hapus 'o')

Hitung jarak edit dengan EDIT_DISTANCE

Fungsi mengembalikan EDIT_DISTANCE jarak Levenshtein antara dua string, yang merupakan jumlah minimum pengeditan yang diperlukan untuk mengubah satu string ke string lainnya. Tujuannya adalah untuk menemukan string yang serupa berdasarkan ambang yang ditentukan.

Contoh berikut menunjukkan cara menggunakan 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

Anda dapat menggunakan EDIT_DISTANCE untuk menemukan rekaman yang mungkin duplikat atau kecocokan meskipun sedikit variasi:

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

Selain itu, Anda dapat menemukan potensi produk duplikat:

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

Mengukur kesamaan dengan EDIT_DISTANCE_SIMILARITY

EDIT_DISTANCE_SIMILARITY mengembalikan skor kesamaan yang dinormalisasi antara 0 dan 100, di mana 100 mewakili string yang identik. Metrik berbasis persentase ini lebih mudah ditafsirkan daripada jarak edit mentah, terutama saat membandingkan string dengan panjang yang berbeda:

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

Anda dapat menggunakan skor kesamaan untuk menemukan perkiraan kecocokan dengan ambang seperti contoh berikut:

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

Menghitung kesamaan fonetik dengan JARO_WINKLER_DISTANCE

Algoritma Jaro-Winkler dirancang untuk membandingkan nama dan string pendek. Ini memberikan skor yang lebih tinggi untuk string yang cocok dari awal, membuatnya efektif untuk nama orang di mana awalan lebih signifikan:

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

Skor Jaro-Winkler berkisar dari 0 hingga 1, di mana 1 menunjukkan string yang identik. Skor di atas 0,9 biasanya menunjukkan kecocokan yang kuat untuk nama.

Contoh berikut menemukan pelanggan dengan nama yang mirip dengan input pencarian:

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

Pertimbangan performa

Fungsi pencocokan fuzzy memeriksa setiap karakter di kedua string, yang menyebabkan penggunaan komputasi yang intensif. Perbandingan string yang tepat dapat berhenti segera setelah karakter berbeda, dan pencarian terindeks menggunakan traversal pohon B yang efisien. Sebaliknya, algoritma fuzzy harus menghitung skor kesamaan karakter berdasarkan karakter. Untuk tabel dengan 1.000.000 baris, pencarian fuzzy yang tidak optimal mungkin melakukan 1.000.000 perhitungan kesamaan, masing-masing melibatkan puluhan perbandingan karakter.

Kunci untuk pencocokan fuzzy yang efisien adalah mengurangi set kandidat sebelum menerapkan fungsi fuzzy yang mahal. Gunakan kolom terindeks dengan LIKE pola, kecocokan persis pada bidang terkait, atau filter rentang untuk mempersempit hasil terlebih dahulu. Hanya kemudian terapkan pencocokan fuzzy ke set kandidat yang lebih kecil.

Contoh berikut menunjukkan pendekatan pemfilteran progresif ini:

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

Untuk informasi selengkapnya tentang pencocokan string fuzzy, lihat Fungsi String.