Localizar correspondências aproximadas com funções de cadeia de caracteres difusas

12 minutos

Os dados do mundo real raramente correspondem perfeitamente. Os nomes de clientes podem estar com ortografia incorreta, endereços abreviados de forma diferente ou descrições de produto inseridas inconsistentemente. As funções de correspondência de cadeia de caracteres difusas ajudam você a encontrar registros semelhantes, mas não idênticos, permitindo melhorias na qualidade dos dados, detecção duplicada e recursos de pesquisa mais flexíveis.

Entender conceitos de similaridade de cadeia de caracteres

Algoritmos de correspondência difusa medem o quão semelhantes são duas cadeias de caracteres calculando as diferenças entre elas. Duas abordagens primárias são comumente usadas:

A distância de edição (distância levenshtein) conta o número mínimo de operações de caractere único (inserções, exclusões, substituições) necessárias para transformar uma cadeia de caracteres em outra. Valores mais baixos indicam cadeias de caracteres mais semelhantes.

Pontuações de similaridade expressam a relação entre cadeias de caracteres como uma porcentagem ou taxa, em que valores mais altos indicam maior semelhança.

Considere estes exemplos:

"color" → "colour": distância de edição = 1 (inserir 'u')
"banco de dados" → "databaes": distância de edição = 2 (trocar 'e' com 's')
"Microsoft" → "Microsft": distância de edição = 1 (excluir 'o')

Observação

A correspondência difusa é computacionalmente cara em comparação com a correspondência exata. Use-o estrategicamente, normalmente em conjuntos de candidatos que foram pré-filtrados usando outros critérios.

Calcular a distância de edição com `EDIT_DISTANCE`

A EDIT_DISTANCE função retorna a distância levenshtein entre duas cadeias de caracteres, que é o número mínimo de edições necessárias para transformar uma cadeia de caracteres na outra. A meta é localizar cadeias de caracteres semelhantes com base em um limite definido.

O exemplo a seguir demonstra como usar 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

Você pode usar EDIT_DISTANCE para localizar registros que podem ser duplicados ou correspondentes, apesar de pequenas variações:

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

Além disso, você pode encontrar possíveis produtos duplicados:

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

Dica

A distância máxima de edição significativa depende do comprimento da cadeia de caracteres. Para cadeias de caracteres curtas (5 a 10 caracteres), uma distância de edição de 1 a 2 indica semelhança. Para cadeias de caracteres mais longas, você pode permitir distâncias de 3 a 5.

Medir a similaridade com `EDIT_DISTANCE_SIMILARITY`

EDIT_DISTANCE_SIMILARITY retorna uma pontuação de similaridade normalizada entre 0 e 100, em que 100 representa cadeias de caracteres idênticas. Essa métrica baseada em porcentagem é mais fácil de interpretar do que a distância de edição bruta, especialmente ao comparar cadeias de caracteres de comprimentos diferentes:

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

Você pode usar pontuações de similaridade para encontrar correspondências aproximadas com um limite como o seguinte exemplo:

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

Calcular a semelhança fonética com `JARO_WINKLER_DISTANCE`

O algoritmo Jaro-Winkler foi projetado especificamente para comparar nomes e cadeias de caracteres curtas. Ele fornece pontuações mais altas para cadeias de caracteres que correspondem desde o início, tornando-o particularmente eficaz para nomes de pessoas em que os prefixos são mais significativos:

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

A pontuação Jaro-Winkler varia de 0 a 1, em que 1 indica cadeias de caracteres idênticas. Uma pontuação acima de 0,9 normalmente indica uma correspondência forte para nomes.

O exemplo a seguir localiza clientes com nomes semelhantes a uma entrada de pesquisa:

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

Observação

Jaro-Winkler é otimizado para cadeias de caracteres curtas, como nomes. Para cadeias de caracteres mais longas, como endereços ou descrições, EDIT_DISTANCE_SIMILARITY geralmente fornece melhores resultados.

Considerações sobre desempenho

As funções de correspondência difusa examinam cada caractere em ambas as cadeias de caracteres, tornando-as computacionalmente intensivas. A comparação exata de strings pode parar assim que os caracteres diferirem, e pesquisas indexadas usam um percurso eficiente da árvore B. Por outro lado, algoritmos difusos devem calcular pontuações de similaridade caractere por caractere. Para uma tabela com um milhão de linhas, uma pesquisa difusa não otimizada pode executar um milhão de cálculos de similaridade, cada um envolvendo dezenas de comparações de caracteres.

A chave para uma correspondência difusa eficiente é reduzir o conjunto de candidatos antes de aplicar as funções difusas caras. Use colunas indexadas com LIKE padrões, correspondências exatas em campos relacionados ou filtros de intervalo para restringir os resultados primeiro. Só então aplique correspondência difusa ao conjunto de candidatos menor.

Os exemplos a seguir mostram essa abordagem de filtragem progressiva:

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

Importante

Funções de correspondência de cadeia de caracteres difusa, como EDIT_DISTANCE, EDIT_DISTANCE_SIMILARITYe JARO_WINKLER_DISTANCE estão disponíveis no SQL Server 2025 e posterior, banco de dados SQL do Azure e bancos de dados SQL no Microsoft Fabric. Verifique a documentação da sua plataforma para a disponibilidade de funcionalidades específicas.

Para obter mais informações sobre correspondência de cadeia de caracteres difusa, consulte Funções de Cadeia de Caracteres.

Comentários

Esta página foi útil?