Artigo original: How to use fuzzy string matching with Postgresql

É fato: as pessoas cometem erros de digitação ou simplesmente usam grafias alternativas com frequência.

Seja qual for a causa, de um ponto de vista prático, strings diferentes, mas semelhantes, podem representar desafios para os desenvolvedores de software. Sua aplicação precisa ser capaz de lidar com esses casos extremos inevitáveis.

Veja nomes, por exemplo. Algumas pessoas me chamam de Peter em alguns lugares, de Pete em outros e assim por diante. Há outras variantes e meu nome pode ser representado Assim:

  • "Pete Gleeson"
  • "Peter J Gleeson"
  • "Mr P Gleeson"
  • "Gleeson, Peter"

Isso sem falar em grafias alternativas do meu sobrenome, como "Gleason". Todas essas são variações para apenas uma string – combiná-las entre si programaticamente pode não parecer algo óbvio.

Felizmente, existem soluções por aí.

O nome genérico para essas soluções é 'correspondência de strings por semelhança' (em inglês, fuzzy string matching). O "fuzzy" refere-se ao fato de que a solução não procura uma correspondência perfeita, posição por posição, ao comparar duas strings. Em vez disso, ela permite algum grau de diferença (ou "desvio").

Existem soluções disponíveis nas mais diversas linguagens de programação. Hoje, vamos explorar algumas opções disponíveis no Postgresql (ou 'Postgres') – uma variante do SQL, de código aberto, amplamente utilizada e com alguns recursos adicionais bastante úteis.

Configuração

Primeiro, vejamos se você tem o Postgres instalado em sua máquina.

Em seguida, criamos um banco de dados em seu próprio diretório (chame-o como quiser – para a demonstração, usei o nome 'fuzz-demo'). A partir da linha de comando, digite:

$ mkdir fuzz-demo && cd fuzz-demo
$ initdb .
$ pg_ctl -D . start
$ createdb fuzz-demo

Para a demonstração, usei uma tabela com detalhes sobre artistas no Museu de Arte Moderna de Nova York. Você pode fazer o download do arquivo artists.csv no Kaggle.

Em seguida, iniciamos o psql (um front-end com base no terminal para o Postgresql):

$ psql fuzz-demo

Agora, criamos uma tabela chamada artists:

CREATE TABLE artists (
	artist_id INT,
    name VARCHAR,
    nationality VARCHAR,
    gender VARCHAR,
    birth_year INT,
    death_year INT);

Por fim, usamos a função COPY do Postgresql para copiar o conteúdo do arquivo artists.csv para a tabela:

COPY artists FROM '~/Downloads/artists.csv' DELIMTER ',' CSV HEADER;

Se tudo estiver certo até o momento, você já pode começar a fazer consultas à tabela artists.

SELECT * FROM artists LIMIT 10;

Filtros curinga (wildcards)

Digamos que você se lembre do primeiro nome de uma artista chamada Bárbara, mas não consegue se lembrar bem do segundo nome dela. Começa com 'Hep...', mas você não tem certeza de como termina.

Aqui, você pode usar um filtro e o operador curinga do SQL, %. Esse símbolo representa qualquer número de caracteres não especificados.

SELECT
	* 
FROM artists
WHERE name LIKE 'Barbara%'
AND name LIKE '%Hep%';

A primeira parte do filtro encontra artistas cujo nome começa com 'Bárbara' e termina em qualquer combinação de caracteres.

A segunda parte do filtro encontra artistas cujo nome pode começar e terminar com qualquer combinação de caracteres, mas deve conter as letras 'Hep', nessa ordem.

image-95
O resultado mostra a artista britânica Barbara Hepworth

O que você faria, no entanto, se não lembrasse como soletrar qualquer um dos nomes? Os filtros e os curingas têm um limite.

Usando as trigramas

Felizmente, o Postgres tem uma extensão útil com o nome e tanto: pg_trgm. Você pode habilitá-la a partir do psql usando o comando abaixo:

CREATE EXTENSION pg_trgm;

Essa extensão traz algumas funções úteis para correspondência de strings semelhantes. O princípio subjacente é o do uso de trigramas (que, sim, parecem com algo saído de Harry Potter).

As trigramas são formadas pela quebra de uma string em grupos de três letras consecutivas. Por exemplo, a string "hello" seria representada pelo seguinte conjunto de trigramas:

  • " h", " he", "hel", "ell", "llo", "lo "

Ao comparar a semelhança do conjunto de trigramas entre duas strings, é possível estimar se elas são semelhantes em uma escala entre 0 e 1. Isso permite a correspondência por similaridade (em inglês, fuzzy matching), definindo um limite de similaridade acima do qual as strings são consideradas correspondentes.

SELECT
	*
FROM artists
WHERE SIMILARITY(name,'Claud Monay') > 0.4 ;
image-99
O resultado é Claude Monet (escrito corretamente)

Talvez você queira ver as cinco melhores correspondências:

SELECT 
	*
FROM artists
ORDER BY SIMILARITY(name,'Lee Casner') DESC
LIMIT 5;
image-108
A correspondência mais próxima é a de Lee Krasner, seguido de Lee Chesney

O limite padrão é 0.3. Você pode usar o operador % nesse caso como uma abreviação para nomes correspondentes por semelhança comparados a uma possível correspondência correta:

SELECT
	*
FROM artists
WHERE name % 'Andrey Deran';
image-100
O resultado traz dois artistas, incluindo um certo Andre Derain

Talvez você só tenha uma ideia de uma parte do nome. O operador % permite comparar com elementos de um array para que você possa fazer a correspondência com qualquer parte do nome. A próxima consulta usa a função STRING_TO_ARRAY do Postgres para dividir os nomes completos dos artistas em arrays de nomes separados.

SELECT
	*
FROM artists
WHERE 'Cadinsky' % ANY(STRING_TO_ARRAY(name,' '));
image-101
O resultado traz duas linhas, incluindo a de Vasily Kandinsky

Algoritmos fonéticos

Outra abordagem para correspondência de strings similares vem de um grupo de algoritmos chamados algoritmos fonéticos.

Esses são algoritmos que usam conjuntos de regras para representar uma string usando um código curto. O código contém as principais informações sobre como a string deve soar se lida em voz alta. Ao comparar esses códigos curtos, é possível combinar strings que são escritas de modo diferente, mas soam iguais.

O Postgres vem com uma extensão que permite que você faça uso de alguns desses algoritmos. Você pode habilitá-la com o seguinte comando:

CREATE EXTENSION fuzzystrmatch;

Um exemplo é um algoritmo chamado Soundex. Suas origens remontam a mais de 100 anos – foi patenteado pela primeira vez em 1918 e foi usado no século 20 para analisar dados do censo dos EUA.

O Soundex funciona convertendo strings em códigos de quatro letras que descrevem como elas soam. Por exemplo, as representações do Soundex de 'flor' (em inglês, flower) e 'farinha' (em inglês, flour) são ambas F460.

A consulta abaixo encontra o registro que soa como o nome 'Damian Hurst'.

SELECT
	*
FROM artists
WHERE nationality IN ('American', 'British')
AND SOUNDEX(name) = SOUNDEX('Damian Hurst');
image-102
O resultado inclui o artista britânico Damien Hirst (escrito corretamente)

Outro algoritmo conhecido é o do metafone. Ele funciona de maneira semelhante ao Soundex, na medida em que converte strings em uma representação de código usando um conjunto de regras.

O algoritmo do metafone retornará códigos de diferentes comprimentos (ao contrário do Soundex, que sempre retorna quatro caracteres). Você pode passar um argumento para a função METAPHONE indicando o código de comprimento máximo que você deseja que ele retorne.

SELECT
	artist_id,
    name,
    METAPHONE(name,10)
FROM artists
WHERE nationality = 'American'
LIMIT 5;
image-103
O metafone de cada artista é produzido

Como o metafone e o Soundex retornam strings como resultado, você pode usá-las em outras funções de correspondência de strings similares. Essa abordagem combinada pode produzir resultados poderosos. O exemplo abaixo encontra as cinco correspondências mais próximas para o nome Si Tomlee.

SELECT
	*
FROM artists
WHERE nationality = 'American'
ORDER BY SIMILARITY(
	METAPHONE(name,10),
    METAPHONE('Si Tomlee',10)
    ) DESC
LIMIT 5;
image-104
O melhor resultado é o do artista americano Cy Twombly

Aqui, uma abordagem apenas de trigrama não teria ajudado muito, já que há pouca sobreposição entre 'Cy Twombly' e 'Si Tomlee'. Na verdade, eles têm apenas uma pontuação de SIMILARITY (em português, similaridade) de 0,05, embora soem semelhantes quando lidos em voz alta (em inglês).

Devido às suas origens históricas, nenhum desses algoritmos funciona bem com nomes ou palavras de origem não inglesa. No entanto, existem versões mais focadas para o mercado internacional.

Um exemplo é o algoritmo de metafone duplo. Ele usa um conjunto mais sofisticado de regras para produzir metafones, podendo fornecer codificações alternativas para strings de origem inglesa e não inglesa.

Como exemplo, veja a consulta abaixo. Ele compara os resultados de metafone duplo para diferentes grafias do artista espanhol Joan Miró:

SELECT
	'Joan Miró' AS name, 
    DMETAPHONE('Joan Miró'),
    DMETAPHONE_ALT('Joan Miró')
UNION SELECT
	'Juan Mero' AS name,
    DMETAPHONE('Juan Mero'),
    DMETAPHONE_ALT('Juan Mero');
image-106
Both the correct spelling and misspelling produce JNMR and ANMR as metaphones
image-106
Tanto a escrita correta quanto a incorreta produzem JNMR e ANMR como metafones

Indo mais longe

Finalmente, outra abordagem para a correspondência de strings similares no Postgres é calcular a "distância" entre as strings. Existem várias maneiras de se fazer isso. O Postgres fornece uma funcionalidade para calcular a distância de Levenshtein.

Em um nível mais alto, a distância de Levenshtein entre duas strings é o número mínimo de edições necessárias para transformar uma string na outra. As edições são consideradas no nível dos caracteres e podem incluir:

  • substituições,
  • exclusões e
  • inserções

Por exemplo, a distância de Levenshtein entre as palavras "bigger" e "better" (maior e melhor em português, respectivamente) é de 3, porque você pode transformar "bigger" em "better" substituindo "igg" por "ett".

Já a distância de Levenshtein entre 'biggest' e 'best' ("o maior" e "o melhor" em português, respectivamente) também é 3, porque você pode transformar 'biggest' em 'best' excluindo as letras 'igg'.

Veja abaixo uma consulta que encontra os nomes de artistas com as menores distâncias de Levenshtein para o nome 'Freda Kallo'.

SELECT
	*,
    LEVENSHTEIN(name, 'Freda Kallo')
FROM artists
ORDER BY LEVENSHTEIN(name, 'Freda Kallo') ASC
LIMIT 5
image-107
A artista mexicana Frida Kahlo é a correspondência mais próxima, seguida por Fred Niblo, Fred Taylor e Frank Gallo

Obrigado pela leitura!

Espero que esta visão geral da correspondência de strings similares no Postgresql tenha dado a você novos sugestões e ideias para seu próximo projeto.

É claro que existem outros métodos para correspondência de strings similares não abordados aqui, incluindo em outras linguagens de programação.

Por exemplo, ao usar o Python, dê uma olhada no pacote fuzzywuzzy. Se preferir a linguagem R, você pode usar a função agrep() integrada ou testar o pacote stringdist.