Cómo utilizar la coincidencia de cadenas difusas con Postgresql

Es un hecho: la gente comete errores tipográficos o simplemente usa ortografías alternativas con frecuencia.

Cualquiera sea la causa, desde un punto de vista práctico, diferentes variantes de cadenas similares pueden plantear desafíos para los desarrolladores de software. Su aplicación debe ser capaz de manejar estos inevitables casos extremos.

Tomemos nombres, por ejemplo. Me llamo Peter en algunos lugares, Pete en otros. Entre otras variantes, mi nombre se puede representar por:

  • "Pete Gleeson"
  • "Peter J Gleeson"
  • "Sr. P Gleeson"
  • "Gleeson, Peter"

Y eso sin mencionar la ortografía alternativa de mi apellido, como "Gleason". Todas estas variaciones diferentes para una sola cadena; hacerlas coincidir mediante programación puede no parecer obvio.

Afortunadamente, existen soluciones.

El nombre genérico de estas soluciones es "coincidencia de cadenas difusas". El 'difuso' se refiere al hecho de que la solución no busca una coincidencia perfecta posición por posición al comparar dos cadenas. En cambio, permiten cierto grado de desajuste (o "confusión").

Hay soluciones disponibles en muchos lenguajes de programación diferentes. Hoy, exploraremos algunas opciones disponibles en Postgresql (o 'Postgres'), un dialecto SQL de código abierto ampliamente utilizado con algunas características complementarias muy útiles.

Configurar

Primero, asegúrese de tener Postgres instalado en su máquina.

Luego, cree una nueva base de datos en su propio directorio (puede llamarlo como quiera, aquí lo llamé 'fuzz-demo'). Desde la línea de comando:

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

Para esta demostración, utilicé una tabla con detalles sobre artistas en el Museo de Arte Moderno. Puede descargar el archivo Artists.csv de Kaggle.

A continuación, puede iniciar psql (un front-end basado en terminal para Postgresql):

$ psql fuzz-demo

Ahora, cree una tabla llamada artists:

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

Finalmente, puede usar la función COPIA de Postgresql para copiar el contenido de Artists.csv en la tabla:

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

Si todo ha funcionado hasta ahora, debería poder comenzar a consultar la tabla de artistas.

SELECT * FROM artists LIMIT 10;

Filtros comodín

Supongamos que recuerda el nombre de pila de una artista llamada Bárbara, pero no recuerda bien su segundo nombre. Comenzó con 'Hep ...', pero no estás seguro de cómo terminó.

Aquí, puede utilizar un filtro y el operador comodín de SQL %. Este símbolo representa cualquier número de caracteres no especificados.

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

La primera parte del filtro encuentra artistas cuyo nombre comienza con 'Barbara' y termina con cualquier combinación de caracteres.

La segunda parte del filtro busca artistas cuyo nombre puede comenzar y terminar con cualquier combinación de caracteres, pero debe contener las letras 'Hep' en ese orden.

Pero, ¿qué pasa si no está seguro de la ortografía de cualquiera de los nombres? Los filtros y los comodines solo te llevarán hasta cierto punto.

Usar trigramas

Afortunadamente, Postgres tiene una extensión útil con el nombre pegadizo pg_trgm. Puede habilitarlo desde psql usando el siguiente comando:

CREATE EXTENSION pg_trgm;

Esta extensión trae consigo algunas funciones útiles para la coincidencia de cadenas difusas. El principio subyacente es el uso de trigramas (que suenan como algo salido de Harry Potter).

Los trigramas se forman rompiendo una cadena en grupos de tres letras consecutivas. Por ejemplo, la cadena "hola" estaría representada por el siguiente conjunto de trigramas:

  • "h", "él", "hola", "ell", "llo", "lo"

Al comparar qué tan similar es el conjunto de trigramas entre dos cadenas, es posible estimar qué tan similares son en una escala entre 0 y 1. Esto permite una coincidencia difusa, estableciendo un umbral de similitud por encima del cual se considera que las cadenas coinciden.

SELECT * FROM artists WHERE SIMILARITY(name,'Claud Monay') > 0.4 ;

¿Quizás quieras ver los cinco primeros partidos?

SELECT * FROM artists ORDER BY SIMILARITY(name,'Lee Casner') DESC LIMIT 5;

El umbral predeterminado es 0,3. En %este caso, puede utilizar el operador como forma abreviada de nombres de coincidencia aproximada con una coincidencia potencial:

SELECT * FROM artists WHERE name % 'Andrey Deran';

Quizás solo tenga una idea de una parte del nombre. El %operador le permite comparar con elementos de una matriz, por lo que puede hacer coincidir con cualquier parte del nombre. La siguiente consulta usa la STRING_TO_ARRAYfunción de Postgres para dividir los nombres completos de los artistas en matrices de nombres separados.

SELECT * FROM artists WHERE 'Cadinsky' % ANY(STRING_TO_ARRAY(name,' '));

Algoritmos fonéticos

Otro enfoque para la coincidencia de cadenas difusas proviene de un grupo de algoritmos llamados algoritmos fonéticos.

Estos son algoritmos que usan conjuntos de reglas para representar una cadena usando un código corto. El código contiene la información clave sobre cómo debería sonar la cadena si se lee en voz alta. Al comparar estos códigos abreviados, es posible hacer coincidir cadenas que se escriben de manera diferente pero suenan igual.

Postgres viene con una extensión que le permite hacer uso de algunos de estos algoritmos. Puede habilitarlo con el siguiente comando:

CREATE EXTENSION fuzzystrmatch;

One example is an algorithm called Soundex. Its origins go back over 100 years - it was first patented in 1918 and was used in the 20th century for analysing US census data.

Soundex works by converting strings into four letter codes which describe how they sound. For example, the Soundex representations of 'flower' and 'flour' are both F460.

The query below finds the record which sounds like the name 'Damian Hurst'.

SELECT * FROM artists WHERE nationality IN ('American', 'British') AND SOUNDEX(name) = SOUNDEX('Damian Hurst');

Another algorithm is one called metaphone. This works on a similar basis to Soundex, in that it converts strings into a code representation using a set of rules.

The metaphone algorithm will return codes of different lengths (unlike Soundex, which always returns four characters). You can pass an argument to the METAPHONE function indicating the maximum length code you want it to return.

SELECT artist_id, name, METAPHONE(name,10) FROM artists WHERE nationality = 'American' LIMIT 5;

Because both metaphone and Soundex return strings as outputs, you can use them in other fuzzy string matching functions. This combined approach can yield powerful results. The example below finds the five closest matches for the name Si Tomlee.

SELECT * FROM artists WHERE nationality = 'American' ORDER BY SIMILARITY( METAPHONE(name,10), METAPHONE('Si Tomlee',10) ) DESC LIMIT 5;

Here, a trigram-only approach would not have helped much, as there is little overlap between 'Cy Twombly' and 'Si Tomlee'. In fact, these only have a SIMILARITY score of 0.05, even though they sound similar when read aloud.

Due to their historical origins, neither of these algorithms works well with names or words of non-English language origin. However, there are more internationally-focused versions.

One example is the double metaphone algorithm. This uses a more sophisticated set of rules for producing metaphones. It can provide alternative encodings for English and non-English origin strings.

As an example, see the query below. It compares the double metaphone outputs for different spellings of Spanish artist 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');

Going the distance

Finally, another approach to fuzzy string matching in Postgres is to calculate the 'distance' between strings. There are several ways to do this. Postgres provides functionality to calculate the Levenshtein distance.

At a high level, the Levenshtein distance between two strings is the minimum number of edits required to transform one string into the other. Edits are considered at the character level, and can include:

  • substitutions,
  • deletions, and
  • insertions

For example, the Levenshtein distance between the words 'bigger' and 'better' is 3, because you can transform 'bigger' into 'better' by substituting 'igg' for 'ett'.

Meanwhile, the Levenshtein distance between 'biggest' and 'best' is also 3, because you can transform 'biggest' into 'best' by deleting the letters 'igg'.

See below for a query which finds the artists with the smallest Levenshtein distances from the name 'Freda Kallo'.

SELECT *, LEVENSHTEIN(name, 'Freda Kallo') FROM artists ORDER BY LEVENSHTEIN(name, 'Freda Kallo') ASC LIMIT 5

Thanks for reading!

Hopefully this overview of fuzzy string matching in Postgresql has given you some new insights and ideas for your next project.

There are of course other methods for fuzzy string matching not covered here, and in other programming languages.

For example, if you use Python, take a look at the fuzzywuzzy package. Or if you prefer R, you can use the inbuilt agrep() function, or try out the stringdist package.