Oracle es la leche, eso no creo que haya nadie que pueda negarlo. Sin duda es una de las mejores (si no la mejor) bases de datos del mundo... pero por desgracia para el común de vosotros los humanos, su código es privativo y su precio prohibitivo (y juro que el pareado ha sido espontáneo!).

Pero no desesperéis... no hace falta que recurráis a soluciones inferiores ni nada parecido. Gracias a los Dioses tenemos PostgreSQL, aunque en éste artículo no vamos a hablar de éste genial motor de base de datos, sino de uno de los módulos adicionales que incorpora para realizar búsquedas basandose en la similitud entre los trigramas de una cadena: pg_trgm. Primero vamos con un poco de teoría: ¿qué es un trigrama?
En el contexto en el que estamos hablando, un trigrama se define como una palabra formada por 3 carácteres.

Para obtener éstos 3 carácteres, ésta extensión descompone las cadenas en algo parecido a las sílabas de la palabra (aunque realmente no son sílabas) y si es necesario concatena espacios en blanco delante o detrás de aquellas sílabas que no tengan 3 carácteres de longitud.

Únicamente se utilizan los carácteres alfanuméricos, por lo que puntos, comas, asteriscos, paréntesis o cualquier otro carácter que pudiera contener la cadena que no sea un número o una letra es ignorado.

Se ve mucho más claro con un ejemplo, así que primero vamos a ver qué trigramas forman la palabra pornohardware:

postgres=# select show_trgm('pornohardware');
                            show_trgm                            
-----------------------------------------------------------------
 {"  p"," po",ard,are,dwa,har,noh,oha,orn,por,rdw,"re ",rno,war}
(1 row)

Como puedes ver, la palabra pornohardware está formada por 14 trigramas:
__p, _po, ard, are, dwa, har, noh, oha, orn, por, rdw, re_, rno y war.

Si quisiéramos comparar ésta palabra con otra, por ejemplo, con pornosoftware (no es que esté obsesionado, es para que se note la similitud en la comparación xDDD), los trigramas que forman ésta última serían:

postgres=# select show_trgm('pornosoftware');
                            show_trgm                            
-----------------------------------------------------------------
 {"  p"," po",are,ftw,nos,oft,orn,oso,por,"re ",rno,sof,twa,war}
(1 row)

Es decir:
__p, _po, are, ftw, nos, oft, orn, oso, por, re_, rno, sof, twa, war

De ésta forma, comparando las coincidencias entre los trigramas obtenidos, pg_trgm puede obtener un porcentaje de similitud entre ambas. Y no creas que parece bonito en teoría, pero luego no funciona del todo bien... a la hora de la verdad cumple con creces lo esperado, no solo en la precisión de los resultados sino en eficiencia (obviamente es más costoso que una comparación normal entre cadenas, pero funciona realmente rápido).

Vamos a verlo:

postgres=# select similarity('pornohardware', 'pornosoftware');
 similarity 
------------
        0.4
(1 row)

El resultado que devuelve la función similarity es un número entre 0 y 1, dependiendo de si las cadenas son completamente distintas (0) o completamente iguales (1).

Por tanto, multiplicando el resultado por 100 obtenemos el porcentaje de similitud entre ambas, que en éste caso es de un 40% (pornohardware y pornosoftware son similares al 40%).

Y ahora que más o menos sabemos de qué trata el asunto, vamos al turrón:

Instalación

Con versiones antiguas de PostgreSQL era algo engorrosa la instalación de dicho módulo, ya que había que ejecutar manualmente los comandos SQL que daban de alta en nuestra base de datos las funciones y librerias del módulo, lo que hacía que su mantenimiendo, acctualización o desinstalación no fuera tan limpia como debería.

No voy a explicar la instalación en éstos casos, ya que si a éstas alturas eres uno de esos malditos que continuan usando PostgreSQL 8.x (o incluso versiones anteriores) no solo no mereces ayuda, sino que algún dia (en el Nuevo Orden Mundial, cuando por fin lidere a vuestra raza) te perseguiré y daré caza como a una vulgar alimaña.

Para todos aquellos que utilizan versiones más o menos actuales de PostgreSQL (por ejemplo, 9.x en adelante), la instalación de pg_trgm es muy sencilla:

Primero debemos instalar el paquete contrib correspondiente a la versión de PostgreSQL que estemos utilizando.

Para aquellos hombres que usais La Distribución (o distribuciones basadas en ella), basta con un simple:

sudo apt-get install postgresql-contrib-9.3

Y para aquellos que utilizan Redhat, CentOS y similares bastaría con:

sudo yum install postgresql93-contrib

Ésto siempre y cuando tengais las fuentes adecuadas en vuestros respectivos gestores de paquetes (apt y yum), claro.

Si éste no es vuestro caso, debeis añadir éstos archivos (dependiendo de nuevo de qué distribución useis):

Debian y similares:

deb http://apt.postgresql.org/pub/repos/apt/ wheezy-pgdg main

Redhat/CentOS y similares:

[pgdg93]
name=PostgreSQL 9.3 $releasever - $basearch
baseurl=http://yum.postgresql.org/9.3/redhat/rhel-$releasever-$basearch
enabled=1
gpgcheck=1
gpgkey=file:///etc/pki/rpm-gpg/RPM-GPG-KEY-PGDG-93

[pgdg93-source]
name=PostgreSQL 9.3 $releasever - $basearch - Source
failovermethod=priority
baseurl=http://yum.postgresql.org/srpms/9.3/redhat/rhel-$releasever-$basearch
enabled=0
gpgcheck=1
gpgkey=file:///etc/pki/rpm-gpg/RPM-GPG-KEY-PGDG-93

Una vez instalado el paquete contrib, accedemos a la consola de nuestra base de datos con el comando psql e instalamos la extensión con un sencillo CREATE EXTENSION pg_trgm;:

postgres@natalia:~$ psql
psql (9.3.4)
Type "help" for help.
postgres=# CREATE EXTENSION pg_trgm;
CREATE EXTENSION

Y eso es todo... ya tenemos el módulo pg_trgm instalado en nuestro PostgreSQL.

Si quisiéramos desinstalar la extensión, simplemente bastaría con:

postgres@natalia:~$ psql
psql (9.3.4)
Type "help" for help.
postgres=# DROP EXTENSION pg_trgm;
DROP EXTENSION

Y ahora vamos a ver cómo se usa...

Funciones

Una vez instalado el módulo, dispondremos de 4 nuevas funciones en nuestra base de datos:

  • similarity(text, text)
    Ésta es la principal función que usaremos para comparar las cadenas.
    Recibe 2 parámetros, que son las 2 cadenas que quedemos comparar, y devuelve un número real comprendido entre 0 y 1 según la similitud entre ambas cadenas.
    Si las cadenas con completamente diferentes devolverá 0, y si son completamente iguales, devolverá 1 (por lo que si las cadenas son similares a medias, devolverá 0.5).

  • show_trgm(text)
    Ésta función recibe como parámetro una cadena, y devuelve un array con los trigramas que la forman. Se suele utilizar únicamente para depurar.

  • set_limit(real)
    Con ésta función podemos definir el umbral de similitud que debemos utilizar para considerar 2 cadenas como similares. Recibe como parámetro un número real de (de 0 a 1).
    Por ejemplo, para entender mejor su funcionamiento, si llamamos a ésta función con el parámetro 0.39, significaría que cualquier cadena que al compararla con otra diera un valor superior a éste, sería considerada por el sistema como similar a dicha otra cadena.
    Por lo tanto, según nuestro primer ejemplo al comparar pornohardware y pornosoftware, ambas se considerarían cadenas similares puesto que el resultado de su comparación fué 0.4.

  • show_limit()
    Ésta función únicamente muestra el umbral de similitud actual que hay definido en el sistema, es decir, el que previamente hemos establecido con set_limit(real).

Ejemplos

He escrito éste artículo porque he estado trabajando con éste módulo en el curro éstos últimos dias, y he quedado muy satisfecho con su funcionamiento en el proyecto en el que lo hemos estado utilizando, por lo que quizás es buena idea poner algunos usos reales que hemos hecho de él a modo de ejemplos de utilizacion (cambiando los nombres por cuestiones de privacidad):

Nuestro cliente disponía de una base de datos de clientes suyos (muy depurada a lo largo de los años, con información sobre localización, nombres, teléfonos, etc. de cada uno de ellos). Pero por motivos que no vienen al caso, le había llegado una segunda base de datos de clientes (mucho más desorganizada, con clientes duplicados, registros nulos, etc) de la que necesitaban obtener los clientes que ya tuvieran en su otra base de datos.

Su intención era relacionar aquellos clientes de la base de datos sucia con los de su base de datos limpia, y ésto no podía hacerse comparando de forma tradicional los nombres de los clientes o cualquier otro dato similar puesto que en la segunda base de datos había registros cuyos nombres estaban incorrectamente escritos, había faltas de ortografía en algunos campos, etc, etc.

La utilización de pg_trgm supuso la solución a éste problema, ya que pudimos comparar de forma automática cada registro de la base de datos sucia con los registros limpios y ordenados de la base de datos limpia, y listar éstos últimos ordenados en función de su similitud.

Después de varias pruebas, concluimos que necesitábamos establecer un umbral muy alto para estar seguros de que 2 clientes eran iguales.. por lo que después de unos cuantos intentos, asumimos que aquellos cuyos nombres nos dieran una similitud mayor al 0.75 eran en realidad el mismo cliente sin lugar a dudas (para el resto de clientes que no conseguíamos enlazar de forma automática e inequívoca mediante ésta comparación, utilizábamos otros sistemas... pero creo que el ejemplo es perfectamente válido para entender el funcionamiento de pg_trgm).

Antes de probar con pg_trgm lo intentamos a través del menor valor dado por la distancia Levenshtein, por comparación de las claves Soundex de las cadenas a buscar, etc, etc... y de todo lo que intentamos, éste genial módulo fué lo que mejor resultado dió.

Hicimos tambien comparaciones entre la dirección, el tipo de cliente y algunos otros datos... hasta que al final pudimos relacionar la inmensa mayoría de los clientes de la segunda base de datos con la primera con una altísima precisión, y simplemente utilizando querys parecidas a ésta:

SELECT 
    id, 
    name, 
    address, 
    city, 
    region, 
    similarity('Empresa 1 S.A.', name) AS similarity 
FROM 
    clients_clean
WHERE 
    similarity('Empresa 1 S.A.', name) > 0.34 
ORDER BY 
    similarity DESC;

Donde comparábamos al cliente Empresa 1 S.A. (obtenido de la base de datos sucia) con todos los clientes de la base de datos limpia, obteniendo algo parecido a ésto:

   id   |      name      |   address   |  city  |  region  | similarity 
--------+----------------+-------------+--------+----------+------------
 169058 | empresa 1, SA  | ATOCHA, 100 | Madrid | MADRID   |   0.733333
 175138 | empresarios sa | PZA. MAYOR  | Aviles | ASTURIAS |   0.450021
 ...

Índices con pg_rgm

Aparte de los usos que acabamos de ver, se puede utilizar también pg_trgm para crear índices con los trigramas de las cadenas almacenadas en la tabla, de forma que podamos hacer búsquedas con el operador LIKE y sus comodines %, pero de forma mucho más eficiente que con éste.

Para crear uno de éstos índices, debe hacerse así:

CREATE INDEX idx_names ON table1 USING GIN (name gin_trgm_ops);

No obstante, y dado que el número de trigramas que forman las cadenas es grande (véase el comienzo del artículo), éstos índices tienden a crecer mucho cuanto más y más grandes sean las cadenas que almacenamos en la tabla donde definamos el índice, por lo tanto, aunque su uso es aconsejable si nos preocupa el rendimiento y utilizamos búsquedas de tipo LIKE, no debemos abusar de ellos si no queremos conseguir el efecto contrario y comprometer el rendimiento de nuestra base de datos.

Espero que os resulte tan útil e interesante como a mi!

Alaaaaaaaaaaaaaaaaaaaaaa

Referencias