Fuzzy Search — Buscando texto por aproximação

Published in

datenworks

6 min readOct 14, 2019

Já se deparou com o desafio de buscar e (ter que) encontrar um tema de interesse em documentos ou qualquer outra fonte de texto livre? Em muitos casos, a qualidade da busca depende do termo aplicado à busca. Em vários outros, o que estamos buscando não está descrito exatamente como especificamos na busca. Problemas dos mais variados podem impedir que você encontre um documento que tenha relevância com a busca. Um dos mais comuns envolve erros de digitação (palavras escritas de maneira um pouco diferente, erros ortográficos ou soletração incorreta, etc.)

Neste post, vamos abordar o uso da técnica Fuzzy Search e como solucionar problemas reais utilizando tecnologia open-source baseada em linguagem de programação Python.

Qual o problema?

Vamos imaginar que você/sua empresa atua em pesquisa de conteúdo na internet e você está buscando referências para a palavra “Motorola” em um bloco de texto, que pode ser um artigo, documento oficial, postagem em rede social ou qualquer outra origem e formato👇

O Motoróla Moto G7 Plus apresenta uma série de atualizações em relação aos aparelhos da geração anterior, como a presença do moderno sistema operacional Android 9 Pie, que além de tudo é um software extremamente leve, já que a motoróla não realiza muitas personalizações no software de seus smartphones, impedindo que aplicativos inúteis fiquem ocupando a memória do smartphone com dados desnecessários.

Com o texto em mãos, você quer buscar (e encontrar) a palavra “Motorola” no texto. Um simples script Python poderia fazer o trabalho 👇

text = """
O motorola Moto G7 Plus apresenta uma série de atualizações em relação aos aparelhos da geração anterior, como a presença do moderno sistema operacional Android 9 Pie, que além de tudo é um software extremamente leve, já que a motorola não realiza muitas personalizações no software de seus smartphones, impedindo que aplicativos inúteis fiquem ocupando a memória do smartphone com dados desnecessários.
"""query = "Motorola"
print("Found: {}".format(query in text))

O que você acha que será impresso como resultado da expressão "Motorola" in text ?

Found: False

Nesse tipo de comparação de strings, o texto de origem e a sentença em busca são comparadas em exatidão. Ou seja, mesmo que Motorola e motorola queiram dizer a mesma coisa, para a máquina, são coisas distintas.

Situações como essa podem ocorrer com certa frequência e em vários cenários, principalmente quando baseados em edição humana da informação. Já imaginou, por exemplo, associar o registro de uma empresa aos seus colaboradores usando uma chave como company_name ?! 😮. Em casos assim, é necessário aplicar processos mais robustos de comparação de sentenças de texto.

Fuzzy String Matching

No campo da computação, o que se define como Fuzzy Match é a técnica que permite encontrar padrões em texto por aproximação, ao invés de exatidão. Lidando com dados/informações do mundo digital em formato texto livre, o uso dessa técnica é bem amplo e tem várias aplicações presentes no cotidiano das pessoas, como verificadores ortográficos. No cenário de dados, é aplicado em processos de mineração de texto de várias origens, como social media, além de deduplicação de registros que não possuem um atributo chave (comparação por nomes).

Levenshtein Distance

Lá em 1965, o cientista russo Vladimir Levenshtein já estudava uma teoria sobre como medir o quão “distante” duas sentenças de texto estariam entre si. Como resultado, um algoritmo foi formulado para informar o número mínimo de operações de edição (inserção, remoção ou substituição de caracteres) necessárias para igualar uma sentença à outra. Nascia a Levenshtein Distance, um dos métodos mais maduros e difundidos no mercado.

Pra dar uma idéia mais prática sobre como essa distância é calculada, abaixo a função Python que implementa o algoritmo 👇 (você pode encontrar implementações em outras linguagens aqui)

def get_levenshtein_distance(word1, word2):
    """
    https://en.wikipedia.org/wiki/Levenshtein_distance
    :param word1:
    :param word2:
    :return:
    """
    word2 = word2.lower()
    word1 = word1.lower()
    matrix = [[0 for x in range(len(word2) + 1)] for x in range(len(word1) + 1)]

    for x in range(len(word1) + 1):
        matrix[x][0] = x
    for y in range(len(word2) + 1):
        matrix[0][y] = y

    for x in range(1, len(word1) + 1):
        for y in range(1, len(word2) + 1):
            if word1[x - 1] == word2[y - 1]:
                matrix[x][y] = min(
                    matrix[x - 1][y] + 1,
                    matrix[x - 1][y - 1],
                    matrix[x][y - 1] + 1
                )
            else:
                matrix[x][y] = min(
                    matrix[x - 1][y] + 1,
                    matrix[x - 1][y - 1] + 1,
                    matrix[x][y - 1] + 1
                )

    return matrix[len(word1)][len(word2)]

O importante aqui não é aprofundar os detalhes sobre o algoritmo, mas dar uma visão sobre a complexidade de aproximação entre dois textos (palavras, sentenças, etc). Se você necessita ou deseja buscar texto por aproximação, não seria muito eficiente desenvolver (ou aplicar) o mesmo algoritmo puro em todos os seus projetos. Ao invés disso, há implementações disponíveis como pacotes open source em várias linguagens e plataformas, para reuso em escala em seus projetos. Vamos explorar uma das opções 👇

O pacote FuzzyWuzzy

Se você está desenvolvendo soluções usando Python e precisa buscar texto por aproximação, já existe um pacote prontinho pra uso: O fuzzywuzzy !

Pra começar, vamos instalar o fuzzywuzzy via PyPi usando pip:

$ pip install fuzzywuzzy

Opcionalmente, você pode instalar a versão que utiliza o pacote python-Levenshtein (melhor performance)

$ pip install fuzzywuzzy[speedup]

Depois de instalado, vamos ao código (via Python Shell)!

>>> from fuzzywuzzy import fuzz
>>> from fuzzywuzzy import process

A forma mais básica de utilizar ofuzzywuzzy é através da função ratio, que vai apurar a similaridade entre duas sentenças de texto, utilizando o algoritmo disponível para calcular a “distância” entre tais sentenças. Para testar, basta chamar a função informando as sentenças 👇

>>> fuzz.ratio("This is my first sentence","This is my first sentence.")
98

Executando o código acima, o resultado será 98, o que significa que a sentença "This is my first sentence" é 98% semelhante à sentença "This is my first sentence.".

“98%?! Só por causa da pontuação?!” 😑

Qualquer caractere que faça parte da sentença é comparado para gerar a distância/similaridade final entre os termos, incluindo caracteres especiais. Pra lidar melhor com isso, há a função partial_ratio, que apura o mesmo resultado mas permite buscar o melhor comparativo usando partes (ou substrings) de cada sentença 👇

>>> fuzz.partial_ratio("This is my first sentence","This is my first sentence.")
100

Execute o código acima e o resultado será 100! Neste caso, a função partial_ratio procura por uma parcial dentro do texto maior e que seja o mais compatível possível com o texto menor. Neste caso, a primeira sentença (sem o ponto) está “contida” na segunda e maior sentença (a diferença é apenas o ponto :D)

Há situações onde os termos (palavras ou tokens) são os mesmos entre as sentenças, mas a ordem dos termos pode variar. Veja o exemplo:

>>> fuzz.ratio("São Clemente ganhou o Carnaval", "São Clemente o Carnaval ganhou")
77

Consegue perceber que as frases querem dizer a mesma coisa mas, dada a ordem diferente de termos, o resultado não é exato?

Agora experimente a função token_sort_ratio e veja o resultado:

>>> fuzz.token_sort_ratio("São Clemente ganhou o Carnaval", "São Clemente o Carnaval ganhou")
100

Bem melhor, não? 😄

E se houver termos repetidos? A função token_set_ratio lida bem com esses casos:

>>> fuzz.ratio("São Clemente ganhou o Carnaval", "São Clemente ganhou ganhou o Carnaval")
90
>>> fuzz.token_set_ratio("São Clemente ganhou o Carnaval", "São Clemente ganhou ganhou o Carnaval")
100

Pra finalizar, uma das ferramentas mais poderosas do fuzzywuzzy está no módulo process, que permite aproximar um conjunto de opções a um determinado termo de busca, indicando quais opções mais se aproximam e suas respectivas “distâncias” do termo de interesse. Vejam o exemplo:

>>> options = ["Futbol Club Barcelona", "Real Madrid Club de Fútbol", "Valencia Club de Fútbol", "Real Sociedad de Fútbol"]
>>> process.extract("real futbol", options, limit=2)
[('Futbol Club Barcelona', 86), ('Real Madrid Club de Fútbol', 86)]

Acima, queremos saber quais as melhores opções que se aproximam do termo real futbol, solicitando que apenas as 2 (duas) melhores fossem destacadas (através do parâmetro limit). Se apenas a melhor opção é interessante, basta usar a função extractOne 👇

>>> process.extractOne("real", options)
('Real Madrid Club de Fútbol', 90)

Para “casa”…

Se você se interessou pelo tema, deseja explorar um pouco mais a ferramenta, testar variações e outras abordagens, acesso nosso Github, baixe o python notebook deste post e divirta-se!

[1] Susan Li (2018–10–12). Natural Language Processing for Fuzzy String Matching with Python - https://towardsdatascience.com/natural-language-processing-for-fuzzy-string-matching-with-python-6632b7824c49

[2] Francisco Javier Carrera Arias (2019–02–06). Fuzzy String Matching in Python - https://www.datacamp.com/community/tutorials/fuzzy-string-python

[3] Yash Agarwal (2018–05–02). Soundex and Levenshtein distance in Python - https://medium.com/@yash_agarwal2/soundex-and-levenshtein-distance-in-python-8b4b56542e9e