Na análise de dados, é bastante comum o uso de joins no SQL e do df.merge() no Pandas para obter correspondências exatas entre registros. Mas qual seria a alternativa quando queremos encontrar strings diferentes, porém semelhantes? É para isso que serve a técnica de fuzzy matching, que veremos a seguir com a biblioteca Python thefuzz.

Aplicações da técnica

A necessidade de encontrar strings semelhantes pode ocorrer em diversos tipos de atividades envolvendo dados.

Suponha que você trabalhe no RH de um banco e precise encontrar cargos com carreiras semelhantes, sem que essa informação já venha na sua base de dados. Nesse caso, seria possível comparar os cargos entre si e agrupar aqueles com similaridade acima de um limiar definido, como por exemplo: "GTE CONTAS PF VAREJO", "AST CONTAS PF VAREJO", "GTE CONTAS PJ VAREJO" e "GTE CONTAS PF ATACADO".

Agora imagine que você trabalha em uma área de CRM e o sistema de registro de leads permite que os nomes das cidades sejam digitados em um campo aberto, sem validação com a lista de cidades brasileiras. Com isso, sua base de dados pode ter registros diferentes que representam a mesma coisa:

Tabela de exemplo com o nome da cidade de São Paulo escrita de maneiras diferentes

Mesmo corrigindo o sistema para incluir essa validação no processo de cadastro, ainda seria necessário tratar os dados para agrupar os registros antigos.

Cálculo da similaridade entre strings

Antes de demonstrar as comparações usando Python, é fundamental entender a métrica principal por trás do cálculo de similaridade: a Distância de Levenshtein.

Distância de Levenshtein

A distância de Levenshtein entre duas strings a e b, definida por lev(a, b), mede a quantidade mínima de edições necessárias para transformar a string a em b. São 3 tipos de edições, e com elas é possível transformar qualquer string em outra:

• Adição: incluir um novo caractere em qualquer posição da string;
• Remoção: remover um caractere existente na string;
• Substituição: trocar um caractere existente por outro caractere arbitrário, na mesma posição.

Para facilitar o cálculo dessa quantidade mínima de edições, o algoritmo recursivo abaixo auxilia com um passo a passo.

Onde:

• |x| é a quantidade de caracteres existente na string x, ex: |carro| = 5
• head(x) é a primeira letra da string x, ex: head(carro) = c
• tail(x) são todas as letras da string x, exceto a primeira, ex: tail(carro) = arro

Apesar de parecer um pouco complicado, vamos calcular a distância para alguns exemplos de strings a seguir.

Tabela com exemplos de cálculo da Distância de Levenshtein

Agora que conhecemos o cálculo da distância, como medir o quão similar uma string é da outra? Existem algumas formas diferentes, e a escolha depende do tipo de aplicação e do resultado esperado.

Tipos de similaridade

A biblioteca thefuzz pode ser instalada com o comando pip install thefuzz e importada no seu Jupyter notebook com from thefuzz import fuzz, process.

Em todos os métodos a seguir, a similaridade é um número de 0 a 100, proporcional ao grau de semelhança entre as strings.

fuzz.ratio()

O método fuzz.ratio() considera o tamanho de cada string e a Distância de Levenshtein entre elas. O resultado é dado pela fórmula:

Pela fórmula, pares de palavras com distâncias iguais podem ter similaridades diferentes dependendo dos seus tamanhos:

(fotografia, fotografado) possuem a mesma distância que (férias, feriado), mas o primeiro par possui uma similaridade de 86 enquanto o segundo par tem uma similaridade igual a 62 devido ao tamanho menor das palavras.

fuzz.partial_ratio()

Esse método apresenta um resultado diferente quando as strings a e b possuem tamanhos diferentes. O método da razão simples é aplicado entre a menor string e as substrings de mesmo tamanho dentro da string maior.

Vamos fazer passo a passo com as strings a = "portugues" e b = "aportuguesar", sendo |a| = 9 e |b| = 12. Para percorrer a string b sempre mantendo o mesmo tamanho de a, são necessárias 4 iterações.

Tabela com resultados intermediários do cálculo do partial_ratio()

O método sempre retorna o resultado da maior similaridade encontrada, então nesse caso fuzz.partial_ratio("portugues", "aportugesar") será igual a 100.

fuzz.token_sort_ratio()

Antes de detalhar esse método, é importante saber o que é o processo de tokenização. Ele separa as palavras de uma string usando o espaço como delimitador.

a = "vou de carro à praia"
tokens_a = a.split(" ")
 
tokens_a
# ['vou', 'de', 'carro', 'à', 'praia']

O método fuzz.token_sort_ratio() tokeniza as duas strings, ordena os tokens em ordem alfabética, une-os novamente com espaço e aplica o método da razão simples. A seguir, o cálculo usando o método diretamente e de forma manual:

a = "vou de carro à praia"
b = "vou à praia de carro"
 
fuzz.token_sort_ratio(a, b)
# 100
 
tokens_a = a.split(" ")
tokens_a.sort()
join_tokens_a = " ".join(tokens_a)
 
tokens_b = b.split(" ")
tokens_b.sort()
join_tokens_b = " ".join(tokens_b)
 
fuzz.ratio(join_tokens_a, join_tokens_b)
# 100

Como as duas strings possuem exatamente apenas a mesma palavra mas em ordens diferentes, a similaridade é igual a 100 para o método que vimos.

fuzz.token_set_ratio()

É utilizado o método fuzz.ratio() para comparar as duas strings considerando a intersecção dos seus tokens e a diferença de tokens entre elas.

Se os tokens de uma string forem um subconjunto dos tokens da segunda string (mesmo que esta possua outros tokens ausentes na primeira), o resultado será igual a 100.

a = "Marcos de Freitas de Carvalho"
b = "Marcos Freitas de Carvalho"
 
fuzz.token_set_ratio(a, b)
# 100
 
fuzz.token_sort_ratio(a, b)
# 95

Nesse método, o resultado será menor que 100 apenas se ambas as strings contiverem algum token exclusivo. No caso abaixo, a variável a possui a palavra "José" e a variável b possui a palavra "Albuquerque".

a = "Marcos de Freitas de Carvalho José"
b = "Marcos Freitas de Carvalho Albuquerque"
 
fuzz.token_set_ratio(a, b)
# 93

fuzz.partial_token_sort_ratio()

É uma combinação do fuzz.token_sort_ratio() com o fuzz.partial_ratio(). As strings são tokenizadas, ordenadas e unidas novamente, mas a menor delas é comparada às substrings de mesmo tamanho dentro da string maior.

a = "João da Silva"
b = "João Silva"
 
fuzz.partial_token_sort_ratio(a, b)
# 100
 
fuzz.token_sort_ratio(a, b)
# 86

A similaridade nesse caso é igual a 100 devido à primeira string ter sido transformada para a = "da João Silva" e a segunda para b = "João Silva". Como é feita uma comparação parcial (limitada pelo tamanho da menor string), ao final de tudo é como se estivéssemos comparando "João Silva" com "João Silva", 100% similares.

fuzz.partial_token_set_ratio()

É uma combinação do fuzz.token_set_ratio() com o fuzz.partial_ratio().

Se houver pelo menos um token em comum entre as strings, a similaridade será igual a 100. Caso contrário, o método fuzz.partial_ratio() é aplicado considerando a intersecção dos tokens e a diferença entre as strings.

a = "José Antônio de Fonseca"
b = "Marcos Freitas de Carvalho Albuquerque"
c = "Márcia Feitosa"
 
fuzz.partial_token_set_ratio(a, b)
# 100
 
fuzz.partial_token_set_ratio(b, c)
# 69

Analisando as strings a e b, percebemos que existe o token "de" em comum entre elas, o que é suficiente para que a similaridade desse método seja igual a 100, independentemente dos outros elementos.

Já na comparação das strings b e c, a menor delas possui duas palavras semelhantes a duas palavras da maior string, resultando em uma similaridade de 69.

Comparações em lotes

Voltando ao exemplo de comparar um nome de cargo com uma lista de cargos, uma opção seria criar um laço for e aplicar um dos métodos vistos anteriormente em todos os elementos.

Felizmente isso não é necessário, já que a biblioteca thefuzz possui o módulo process, que calcula a similaridade de uma string com todas as ocorrências de uma lista. A seguir, alguns métodos desse módulo.

process.extractBests()

É possível passar os seguintes argumentos para esse método:

• query: string a ser comparada com as demais
• choices: lista (ou dicionário) de strings para comparação
• processor: função de pré-processamento aplicada tanto à "query" quanto a "choices"
• scorer: método específico para calcular a similaridade, como fuzz.ratio()
• score_cutoff: número de 0 a 100 que define a similaridade mínima para retorno
• limit: quantidade dos melhores resultados retornados (None para retornar todos)

Exemplos de uso:

cargo_comparavel = "GTE CONTAS PF VAREJO"
 
lista_cargos = [
    "AST CONTAS PF VAREJO",
    "GTE CONTAS PJ VAREJO", 
    "GTE CONTAS PF ATACADO",
    "CAIXA VAREJO",
    "AGENTE COMERCIAL PF VAREJO",
    "CONSULTOR SEGUROS PJ VAREJO"
]
 
process.extractBests(cargo_comparavel, lista_cargos, limit=None)
#[('GTE CONTAS PJ VAREJO', 95),
# ('AST CONTAS PF VAREJO', 90),
# ('CAIXA VAREJO', 86),
# ('GTE CONTAS PF ATACADO', 78),
# ('AGENTE COMERCIAL PF VAREJO', 74),
# ('CONSULTOR SEGUROS PJ VAREJO', 60)]
 
process.extractBests(cargo_comparavel, lista_cargos, score_cutoff=80, limit=None)
#[('GTE CONTAS PJ VAREJO', 95),
# ('AST CONTAS PF VAREJO', 90),
# ('CAIXA VAREJO', 86)]
 
process.extractBests(cargo_comparavel, lista_cargos, scorer=fuzz.partial_token_set_ratio, limit=3)
#[('AST CONTAS PF VAREJO', 100),
# ('GTE CONTAS PJ VAREJO', 100),
# ('GTE CONTAS PF ATACADO', 100)]

process.extractOne()

Similar ao método process.extractBests(), mas retorna apenas a string com maior similaridade. Em caso de empate, é retornada a primeira ocorrência.

cargo_comparavel = "GTE CONTAS PF VAREJO"
 
lista_cargos = [
    "AST CONTAS PF VAREJO",
    "GTE CONTAS PJ VAREJO", 
    "GTE CONTAS PF ATACADO",
    "CAIXA VAREJO",
    "AGENTE COMERCIAL PF VAREJO",
    "CONSULTOR SEGUROS PJ VAREJO"
]
 
process.extractOne(cargo_comparavel, lista_cargos, scorer=fuzz.partial_token_set_ratio)
# ('AST CONTAS PF VAREJO', 100)

Como visto, fuzzy matching é uma técnica poderosa com diversas aplicações no mundo dos dados. Graças à biblioteca thefuzz, seu uso é simples em Python.

A principal dificuldade costuma ser a escolha do tipo de similaridade, já que existem diversas opções. O recomendado é testar primeiro as similaridades mais simples, como fuzz.ratio(), fuzz.partial_ratio() e fuzz.token_sort_ratio(), antes de partir para métodos mais complexos.

Já conhecia essa técnica ou sabe de alguma aplicação em que ela poderia ser útil?