Too Cool for Internet Explorer

MySQL FULL TEXT para humanos

Hora y Fecha: Enero 14, 2007 @ 10:39 pm Autor: Moisés Maciá
Categorías:
1,610 views

En la base de datos MySQL existe una consulta que devuelve filas atendiendo a su relevancia. ¿Pero qué es relevancia? Es un número de coma flotante resultado de la aplicación de una serie de formulas. Conociendo la manera en la que estas formulas funcionan se pueden construir poderosas consultas que devuelvan resultados relevantes para los usuarios de nuestras aplicaciones.

En este artículo voy a comentar como se gestionan los índices FULLTEXT en la base de datos MySQL, versiones 4.1 o superior.

Primero crearemos una tabla de ejemplo:

  1.  
  2. CREATE TABLE quotes (quote CHAR(100),FULLTEXT (quote));
  3.  
  4. INSERT INTO quotes VALUES
  5.   (‘Special times require special socks’),
  6.   (‘Knock three times on the ceiling’),
  7.   (‘Boliauns are weeds’),
  8.   (‘The leprechaun’’s gold’);

Frases extraídas de The Field of Boliauns, un cuento clásico de la cultura Celta.

Algunas de las palabras se repiten varias veces. Otras palabras no formarán parte del indice FULLTEXT debido a que son muy cortas o demasiado frecuentes. Esta base de datos es lo suficientemente compleja para mostrar todos los trucos de las formulas de cálculo de relevancia.

myisam_ftdump

Para ver que es lo que se ha guardado en el indice FULLTEXT utilizaremos el programa myisam_ftdump. Viene con la distribución estándar de la base de datos.

Lo primerro es saber dónde se están guardando físicamente los datos de la tabla con una sentencia SHOW:

  1. SHOW VARIABLES LIKE ‘datadir%’;
+---------------+-----------------------+
| Variable_name | Value                 |
+---------------+-----------------------+
| datadir       | /var/lib/mysql/        |
+---------------+-----------------------+

1 row in set (0.00 sec)

Otra sentencia SELECT para saber el nombre de la base de datos en la que me encuentro:

  1. SELECT DATABASE();
+------------+
| DATABASE() |
+------------+
| db1        |
+------------+

1 row in set (0.01 sec)

Todos estos datos son los que necesito para poder ejecutar myisam_ftdump. Veamos primero las opciones que tiene:

$> myisam_ftdump --help

Use: myisam_ftdump <table_name> <index_num>

  -d, --dump          Dump index (incl. data offsets and word weights).
  -s, --stats         Report global stats.
  -v, --verbose       Be verbose.
  -c, --count         Calculate per-word stats (counts and global weights).
  -l, --length        Report length distribution.
  -h, --help          Display help and exit.
  -?, --help          Synonym for -h.

Veamos que aspecto tiene el volcado del indice:

$> myisam_ftdump /var/lib/mysql/db1/quotes 0 -d
       ca            0.9775171 boliauns
       65            0.9666505 ceiling
      12f            0.9775171 gold
       65            0.9666505 knock
      12f            0.9775171 leprechaun's
        0            0.8148246 require
        0            0.8148246 socks
        0            1.3796179 special
        0            0.8148246 times
       65            0.9666505 times
       ca            0.9775171 weeds

Veamos ahora los pesos por palabra:

$> myisam_ftdump /var/lib/mysql/db1/quotes 0 -c
        1            1.0986123 boliauns
        1            1.0986123 ceiling
        1            1.0986123 gold
        1            1.0986123 knock
        1            1.0986123 leprechaun's
        1            1.0986123 require
        1            1.0986123 socks
        1            1.0986123 special
        2            0.0000000 times
        1            1.0986123 weeds

Claramente se observa que MySQL asocia números a términos, lo que nos queda por ver es qué significan esos números.

Las formulas

Hay tres formulas, y no son para nada complicadas :)

  • peso_local = (log(dtf)+1)/sumdtf * U/(1+0.0115*U)
  • peso_global = log((N-nf)/nf)
  • peso_consulta = peso_local * peso_global * qf
Parámetros
  • dtf el número de veces que el término aparece en la fila.
  • sumdtf el sumatorio de (log(dtf)+1) para todos los términos de la misma fila.
  • U el número de términos únicos que hay en la fila.
  • N el número de filas que hay en la tabla.
  • nf el número de filas que contienen el término.
  • qf el número de veces que el término aparece en la consulta.

Por último log(n) hace referencia al logaritmo neperiano de n.

Tomemos por ejemplo la búsqueda de la palabra special sobre la primera fila de la tabla, que myisam_ftdump identifica como fila 0 (cero).

Para la primera formula: (log(dtf)+1)/sumdtf * U/(1+0.0115*U);

dft special aparece dos veces en la fila 0, así que log(dtf()+1) = 0.6931472 + 1 = 1.6931472
sumdft special aparece 2 veces en la fila 0, añadimos log(2)+1
times aparece 1 vez en la fila 0, añadimos log(1)+1
require aparece 1 vez en la fila 0, añadimos log(1)+1
socks aparece 1 vez en la fila 0, añadimos log(1)+1
el cálculo queda sumdtf = log(2)+1 + (log(1)+1)*3 = 4.6931472
U Hay 4 términos únicos en la fila 0, por lo que U/(1+0.115*U) = 4/(1+0.0115*4) = 3.824092

peso_local = 1.6931472 / 4.6931472 * 3.824092 = 1.3796179. El mismo número que sale en el volcado del indice proporcionado por myisam_ftdump.

Para la segunda formula: log((N-nf)/nf);

N Hay 4 filas en la tabla quotes
nf El término special tiene ocurrencias en 1 fila.

peso_global = log((N-nf)/nf) = log(3) = 1.0986123. El mismo número que devuelve myisam_ftdump en el volcado de pesos por palabra.

Para la tercera fórmula: peso_consulta = peso_local * peso_global * qf;

peso_local 1.3796179
peso_global 1.0986123
qf special aparece 1 vez en la consulta.

peso_consulta = 1.3796179 * 1.0986123 * 1 = 1.5156652. Finalmente esta es la relevancia de la consulta sobre la tabla de ejemplo.

Comprobemos el resultado con una consulta del tipo MATCHAGAINST:

  1.  
  2. SELECT ROUND(MATCH(quote) AGAINST (’special’),7) AS score FROM quotes;
+-------------------------------------------+
| score |
+-------------------------------------------+
|                                 1.5156652 |
|                                 0.0000000 |
|                                 0.0000000 |
|                                 0.0000000 |
+-------------------------------------------+

4 rows in set (0.00 sec)

NOTA: MySQL devuelve un número con mayor resolución que mi calculadora casio, así que me ha tocado redondear a 7 decimales para que salgan los cálculos :)

La consulta devuelve una puntuación de 1.5156652 para la primera columna de la tabla, el mismo peso que sale de nuestros cálculos.

Explicación de la fórmula

Observad que el peso local depende de una constante que lo multiplica. Esta constante es un factor de corrección para tratar una alta frecuencia de términos dentro de la fila. Para aclararnos: si un término aparece muchas veces en una fila, el peso crece.

¿Por qué el peso local depende de las veces que el termino aparece en la fila? Piensa en este mismo artículo, los términos MySQL y FULLTEXT aparecen muchas veces. Esto es típico: si una serie de palabras aparecen muchas veces a la fuerza deben ser relevantes.

Observad que el peso global depende de la multiplicación de una inversa, el número de filas menos el número de filas en la que aparece el término. Para aclararnos: si un término aparece en muchas filas, el peso baja.

El peso global baja con la frecuencia de un término en todas las filas de la tabla, esto es así porque se considera un término común. Si una palabra aparece constantemente en todas las filas se convierte en un patrón de búsqueda inútil. Pensad en buscar cosas como artículos, pronombres, etc. son tan frecuentes que los resultados son inservibles.

Observad que el peso local, el peso global y el peso de la consulta es lo único que importa. MySQL no incrementará el peso si dos términos aparecen cerca uno de otro. MySQL tampoco entiende las raíces semánticas, los tiempos verbales ni los plurales, esto es, si buscas weed no te va a hacer los cálculos de relevancia para weeds.

La búsqueda utilizando grafos de proximidad y raíces semánticas (stemming) son algunas de las novedades que están preparando de cara a la versión 5.2 de MySQL. Quizá no tardemos mucho en disfrutar de ellas.

MySQL tiene muchas opciones, incluyendo IN BOOLEAN MODE donde las formulas de arriba se vuelven irrelevantes. El modo booleano básicamente realiza una búsqueda en el histograma de frecuencias de la tabla.

La lista stopword

Algunos términos — los artículos, conjunciones y pronombres son un buen ejemplo — tendrán un peso global igual a cero. MySQL no los indexará ni los tendrá en cuenta en las consultas. Es lo que se conoce como stopwords. MySQL maneja una lista de stopwords por defecto para el idioma inglés, que puede ocasionar más problemas de los que resuelve.

Por ejemplo, supongamos el texto:

Every word she writes is a lie, including “and” and “the”.
It depends on what the meaning of the word “is” is.

Es imposible buscar los términos and and the o is is porque son stopwords. Para devolver resultados deberíamos utilizar el operador LIKE, por ejemplo:

  1.  
  2. SELECT * FROM quotes WHERE quote LIKE ‘%is" is%’;

O bien, utilizar una frase de busqueda que no incluya un stopword, por ejemplo:

SELECT * FROM quotes WHERE MATCH(quote) AGAINST('including and and the');

Otro inconveniente es que los stopwords por defecto pueden ser palabras válidas en otros idiomas distintos del inglés. Por ejemplo Is es el nombre de un río ruso y the es la palabra francesa para referirse al . Definitivamente parece que tenemos que cambiar la dichosa lista …

Hay listas de stopwords en la Universidad de Neuchatel provenientes del estudio de gramáticas y lenguajes del departamento de computación. Hay listas para los idiomas Finlandés, Francés, Alemán, Italiano, Ruso, Español y Sueco.

Para decirle a MySQL que utilice nuestra lista hay que levantar la base de datos con el siguiente parámetro:

#> mysqld --ft_stopword_file=stopword.txt

Podemos comprobar la lista que esta utilizando con una consulta SHOW:

  1. SHOW VARIABLES LIKE ‘ft_stopword_file’;
+------------------+--------------+
| Variable_name    | Value        |
+------------------+--------------+
| ft_stopword_file | stopword.txt |
+------------------+--------------+

1 row in set (0.00 sec)

Algunos trucos

Debido a que la formula final depende del parámetro qf (la frecuencia de un término en la consulta), se puede otorgar un peso extra a un término tan sólo con ponerlo varias veces dentro de la consulta. Si preguntamos a la base de datos por special special en lugar de por special veremos como la relevancia cambia.

Suele ayudar bastante añadir una columna con los términos que uno considere relevantes y asignarle un indice FULLTEXT. Es una idea similar a la folcsonomía (ordenación por etiquetas o tags) que tan de moda está en estos días. Los keywords seleccionados otorgarán un mayor peso a la fila.

En ocasiones las consultas devuelven resultados muy extraños, ejecuta myisam_ftdump. Quizá no te salvará el culo pero los resultados te pueden ayudar a mejorar las estrategias de búsqueda la próxima vez.

Actualmente InnoDB no tiene soporte para los indices FULLEXT: deberás elegir entre tablas con indice FULLEXT o tablas con integridad referencial. Al menos hasta la próxima versión 5.2, dónde está previsto que todos los motores de datos de MySQL respeten la integridad referencial.

Los lenguajes ideográficos como el Chino, el Japonés y el Indú carecen de delimitadores entre palabras, escriben todo seguido sin espacios. Esto representa un impedimento enorme en el estudio de todo lo que se ha comentado en el articulo, por esa razón no hay soporte FULLEXT en estos idiomas.

Existe un motor de datos para MySQL que incorpora muchas más funcionalidades en el campo de las búsquedas FULLEXT, entre ellas el soporte para lenguajes ideográficos, grafos de proximidad y stemming. Actualmente está en intensivo desarrollo y no hay paquetes para instalarlo fácilmente: Sphinx.

Espero que este artículo os ayude a mejorar la precisión de vuestras búsquedas y se traduzca en mejores aplicaciones para los usuarios.





« Anterior post: Cook up websites fast with CakePHP, IV | Próximo post: ¿Qué pasa al juntar Linux, Beryl y un WiiMote? »

13 Comentarios para “MySQL FULL TEXT para humanos”

programame.net
14 de Enero de 2007 a las 11:01 pm    

MySQL fulltext para humanos…

En la base de datos MySQL existe una consulta que devuelve filas atendiendo a su relevancia. ¿Pero qué es relevancia? Es un número de coma flotante resultado de la aplicación de una serie de formulas. Conociendo la manera en la que estas formulas f…

Cheli
15 de Enero de 2007 a las 1:57 pm    

La hostia, buenísimo como de costumbre.

Cheli

Guti
15 de Enero de 2007 a las 6:15 pm    

Muy explicativo.
Felicidades!

meneame.net
16 de Enero de 2007 a las 1:42 pm    

MySQL Full Text para humanos…

En la base de datos MySQL existe una consulta que devuelve filas atendiendo a su relevancia. ¿Pero qué es relevancia? Es un número de coma flotante resultado de la aplicación de una serie de formulas. Conociendo la manera en la que estas formulas f…

Portu
16 de Enero de 2007 a las 4:05 pm    

Si necesitas un minimo de eficiencia en consultas de texto completo generalmente deberás recurrir a herramientas como SPHINX: un indexador y buscador de texto completo para MySQL (y postgresql) con un rendimiento espectacular. Escrito en C++, tiene APIs en Phyton, PHP, Perl (y para otros lenguajes existen otras alternativas de uso).

http://www.sphinxsearch.com

Moisés Maciá
16 de Enero de 2007 a las 9:02 pm    

Todavía no he probado Sphinx. En parte porque con MySQL me vale y por otro lado me da pereza compilar todo el sistema.

Cuando Debian empaquete le daré un visazo :)

CH
17 de Enero de 2007 a las 3:45 am    

Creo que también puede ser de su interés: http://www.mysqlya.com.ar/

Saludos

Andrew Aksyonoff
22 de Enero de 2007 a las 12:56 am    

Moises,

thanks for mentioning Sphinx :)

indeed there might be no binary packages for different systems yet, but installing it from source on modern Linux distros should actually be as easy as doing ./configure && make install

So if your database grows to 1M+ records and MySQL builtin FT starts to crawl, do try to take a look :)

(disclaimer: I do not read Spanish and had to use Google Translate, so my comment might sound irrelevant)

Moisés Maciá
22 de Enero de 2007 a las 1:04 am    

Thanks for your reply!!. Debian and apt makes me too lazy but I’ll try sphinx, althought i will have to compile it :)

compuglobal
26 de Marzo de 2007 a las 6:58 pm    

Ya existe un manual en castellano para instalar sphinx. http://www.compuglobalhipermega.net/mysql/instalacion-configuracion-sphinx/

compuglobal
12 de Mayo de 2007 a las 9:11 pm    

Soy yo otra vez.

He desarrollado un ejemplo completo de buscador de wikipedia hecho con sphinx. Esta descrito todo el proceso de creación para que podais verlo.

Un saludo

Carlos Magaña
8 de Octubre de 2007 a las 1:24 am    

Buenísimo, me ha acalrado muchas dudas con respecto al fulltext.


Bad Behavior has blocked 503 access attempts in the last 7 days.