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

Aplicações da técnica

A necessidade de se encontrar strings semelhantes pode ocorrer em diversos tipos de atividades envolvendo dados, como:

Suponha que você trabalhe no RH de um banco e você precisa encontrar cargos com uma carreira semelhante, e que esse tipo de informação já não venha na sua base de dados. Nesse caso seria possível comparar os cargos uns com os outros e agrupar aqueles que tivessem uma similaridade acima do 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 sejam digitados os nomes das cidades em um campo aberto ao invés de se ter uma validação com a lista de cidade brasileiras por trás. Com isso, sua base de dados pode ter diferentes registros que significam na prática a mesma coisa:

cidade	estado
SÃO PAULO	SP
SÃOPAULO	SP
SAO PAULO	SP
S PAULO	SP
SSÃO PAULO	SP

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.

Como calcular a similaridade entre strings

Antes de demonstrar como fazer as comparações usando o 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 disponíveis 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.

a	b	lev(a, b)	edições
carro	cara	2	retirar uma letra “r” e depois substituir o “o” por “a”
fotografia	fotografado	3	retirar a letra “i”, incluir na última posição a letra “d” e incluir na última posição a letra “o”
gte contas	ast contas	3	retirar a letra “e”, incluir na primeira posição a letra “a” e substituir a letra “g” por “s”
férias	feriado	3	substituir a letra acentuada “é” por “e”, substituir a letra “s” por “d” e incluir na última posição a letra “o”

Agora que conhecemos o cálculo da distância, como podemos medir o quão similar uma string é da outra? Existem algumas formas diferentes de fazer isso, e o uso vai depender do tipo de aplicação que você fará e que tipo de resultado você espera.

Tipos de similaridade

A biblioteca thefuzz pode ser instalada de forma simples usando o comando pip install thefuzz em seu ambiente de desenvolvimento Python e importada no seu Jupyter notebook por meio de dois módulos com from thefuzz import fuzz, process.

Para quaisquer métodos explicados a seguir, a similaridade será um número de 0 a 100, onde a similaridade é proporcional à grandeza desse número.

fuzz.ratio()

O método fuzz.ratio() leva em consideração o tamanho de cada uma das strings e a Distância de Levenshtein entre elas, simplesmente. O resultado é o cálculo abaixo.

Olhando a fórmula anterior podemos perceber que pares de palavras com distâncias iguais podem ter similaridades diferentes a depender dos seus tamanhos, como:

(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 do anterior quando as strings a e b possuem tamanhos diferentes, já que 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.

a	substring(b)	partial_ratio(a, substring(b))
portugues	aportugue	89
portugues	portugues	100
portugues	ortuguesa	89
portugues	rtuguesar	78

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() primeiro tokeniza as duas strings, depois ordena ambas em ordem alfabética, depois une os tokens adicionando novamente o espaço como separador e por fim aplica o método da razão simples nas duas strings modificadas. Vamos calcular agora a similaridade por fuzz.token_sort_ratio() usando diretamente o método e de forma manual (transformando as strings para no fim aplicar o fuzz.ratio()).

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 levando em consideração a intersecção dos seus tokens e também na diferença de tokens entre elas.

Caso os tokens de uma string sejam 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 de cálculo o resultado será menor que 100 apenas se ambas as strings contiverem algum token exclusivo, como no caso abaixo onde 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 ao invés de comparar o resultado das duas strings transformadas, 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 único token em comum entre ambas as strings, a similaridade será igual a 100. Caso contrário, o método fuzz.partial_ratio() é aplicado levando em consideração a intersecção dos tokens e também a diferença de tokens 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 existem o token “de” em comum entre elas, e isso é o suficiente para que a similaridade desse método seja igual a 100, não importando os 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 onde seria necessário se comparar um nome de cargo com uma lista com vários nomes de cargos, uma das possibilidades seria criar um laço for e aplicar um dos métodos vistos anteriormente em todos os elementos e salvar esses resultados em outra lista ou dicionário.

Felizmente isso não é necessário, já que a biblioteca thefuzz possui o módulo process que nos permite o calcular a similaridade de uma string com todas as ocorrências de uma lista de strings. Vamos ver agora alguns métodos desse módulo e como aplicá-los.

process.extractBests()

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

• query: string para ser comparada com as demais
• choices: lista (ou dicionário) de strings que serão comparadas com a “query”
• processor: qualquer função de pré-processamento para ser aplicada tanto à “query” quanto a “choices”
• scorer: algum 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 que uma comparação seja retornada
• limit: quantidade dos melhores resultados retornados, sendo possível utilizar o None para retornar todos

Vamos testar agora esse método de algumas formas.

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

Bem similar ao método process.extractBests(), mas nesse caso é retornado apenas a string com maior similaridade. Caso haja um empate, é retornada a primeira ocorrência com a maior similaridade.

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 podemos ver, fuzzy matching é uma técnica poderosa que pode ter diversas aplicações no mundo dos dados e, graças à biblioteca thefuzz, o seu uso é bem simples na linguagem Python.

Talvez a principal dificuldade encontrada seja a de escolher o tipo de similaridade a ser calculada, já que existem inúmeras opções. O recomendado é que sejam testadas primeiramente as similaridades mais simples como fuzz.ratio(), fuzz.partial_ratio() e fuzz.token_sort_ratio() antes de tentar aplicar métodos mais complexos.

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