CompuGlobalHiperMegaNet

He hablado más de una vez del indexer/searcher Sphinx en el blog y de que es una herramienta genial para realizar buscadores de texto completo de alto rendimiento. Si todavía no conoces sphinx echa un ojo a:

• Página oficial de la herramienta
• Instalación de sphinx
• Proceso de creación de un Buscador de wikipedia

Lo que ahora quiero presentar es un stemmer en castellano que desarrollé hace unos meses para sphinx.

¿Qué es un stemmer?

Un stemmer es un algoritmo que realiza un proceso de stemming o lematización por el cual cada palabra es reducida a su lexema o raíz.

Este proceso es realmente útil para aumentar el recall o exhaustividad de un sistema de recuperación de información. Es muy importante tener en cuenta que el stemming es completamente dependiente del idioma en el que está la información a procesar.

Genial, pero ¿Qué es un stemmer?

Imaginemos por un momento que tenemos un directorio de empresas y un buscador asociado. Supongamos que disponemos en base de datos los siguientes registros:

• ID Nombre
• 1 "Fontanería Los rápidos"
• 2 "Perez Fontaneros"
• 3 "El fontanero feliz"

Si no disponemos de una herramienta de lematización, tendríamos los siguientes resultados:

• Consulta ID-resultante
• "fontanería" 1
• "fontaneros" 2
• "fontanero" 3

Esos resultados no sólo serían diferentes entre sí, sino que además estarían incompletos. En cambio si para esos mismo registros de base de datos usamos un stemmer para castellano:

• Consulta ID-resultante
• "fontanería" 1 2 3
• "fontaneros" 1 2 3
• "fontanero" 1 2 3

Creo que ya ha quedado claro la importancia de usar técnicas de stemming.

Sphinx y el stemmer

En este caso en particular, sphinx provee de dos stemmers, uno para inglés y otro para ruso (ya que el desarrollador es ruso). Si queremos realizar un buscador web con sphinx que aplique técnicas de stemming sólo hay una opción: desarrollar el stemmer nosotros mismos.

Después de estudiar un poco como es la parte de lematización en sphinx por dentro se ve que sería suficiente con desarrollar una función en C/C++ que recibida una palabra por parámetro devuelva su lexema y luego integrarlo con un par de directivas y actualización de los makes.

¿Por dónde empezar?. Bueno, pues es importante destacar que hay una persona que se encargó en su día de definir los algoritmos de stemming y es el verdadero referente en el tema. Se llama Martin Porter , el ya nos ha hecho todo el trabajo sucio y nos pone en bandeja la codificación.

Fases del stemmer

• Fase 0: Eliminar pronombres
• Fase 1: Eliminar sufijos estándar
• Fase 2a: Eliminar sufijos verbales que empiecen por y
• Fase 2b: Eliminar otros sufijos
• Fase 3: Eliminar sufijos residuales
• Final: Convertir acentos

Instalación e integración del stemmer con Sphinx

La versión de sphinx para la que se va a explicar todo es la 0.9.7 (la última).

El stemmer en si, es un único fichero sphinxstemes.cpp con la función que realiza la lematización. Pero para integrarlo en sphinx es necesario incluir un par de líneas en 4 archivos:

En el fichero sphinx.h, en la línea 251 esta definido el enum de morfologías. Se debe cambiar por este:

En el fichero sphinx.cpp, línea 8300 aproximadamente, cambiar el método GetWordID por:

En el fichero sphinxutils.cpp, hay que modificar el parser del fichero de configuración. en la línea 419 la función sphConfMorphology debe tener esta pinta:

Por último en el fichero sphinxstem.h, se debe poner la definición de la función de stemming. Añadir

Una vez modificado esto, sólo queda actualizar los make para reconstruir el proyecto. Incluir sphinxstemes en am__objects

y también el cpp en los fuentes

Configuración

Una vez recompilado sphinx con el soporte para el stemmer en castellano, podemos configurar un índice que lo use índicandoselo en el fichero de configuración de esta manera (omitidos los campos que no cambian de una configuración normal):

Hay que tener mucho cuidado con la charset_table, porque es ahí, dónde se definen que caracteres aceptamos para el índice y cuales reconvertimos. El formato U+XX es unicode, y podeis ver unas tablas de códigos en unicode.org.

En la charset_table definida se aceptan los números, los guiones bajos, las letras acentuadas (sólo acentos del castellano) y las letras sin acentuar. Además son convertidas de mayusculas a minúsculas (eso quiere decir la -> ). Una mala configuración de este parámetro puede darnos muchos dolores de cabeza, asi que recomiendo estudiarlo con detenimiento. Por ejemplo, en el caso del búscador de la wikipedia, no se acepta el guión bajo, ya que es el usado en los títulos a modo de espacio.

Si por alguna razon, no quisieramos usar stemming pero si indizar texto en castellano, habría que retocar esta tabla para convertir los caracteres acentuados a su equivalente sin acentuar (más la ñ).

Pruebas del stemmer
En la web de Porter, se da una lista de 28000 palabras y su lematización correcta. El stemmer ha sido probado con esa lista y cotejando el resultado esperado con el obtenido. A excepción de 5 palabras (que debo revisar) todo va igual.

Descarga del stemmer

El stemmer al igual que el proyecto sphinx, es GPL, asi que puedes usarlo con libertad.
Puedes descargarlo de aqui: stemmer-castellano

Donde ver un buscador con el stemmer aplicado

El stemmer se puede ver en buscador de la wikipedia y también en el agregador de blogs agregax, un proyecto muy interesante que lleva a cabo Pau Iglesias (recientemente le hicieron un artículo en El País).

La mayoría de la gente que trabaja con MySQL (ójala fueran todos), sabe que los índices son una parte importantísima del rendimiento en las consultas a base de datos. Para los no conocedores del tema, se pueden crear índices (y se deben...) para que cuando queremos obtener un conjunto de registros, segmentados por algún tipo de condición, estos sean devueltos con un mínimo de rapidez. La regla suele ser que por cada campo de un WHERE se debe tener un índice. Luego se puede estudiar el comportamiento y optimizar estos índices con la maravillosa instrucción EXPLAIN.

A mi juicio, esto tiene una excepción, y son las consultas de texto completo en las que es mejor usar una herramienta externa de consulta de índices de texto completo (fulltext).

No quiero entrar en todo el tema de teoría de índices y demás, pero básicamente se puede resumir en que se reduce un poco el rendimiento de una inserción o actualización en base de datos en pro de la rapidez en consulta.

Generalmente se trabaja con tablas en las que se escribe esporádicamente y se lee muy a menudo de manera que es muy importante mantener esos índices. Hoy me he encontrado el único caso en el que es muchísimo mejor no tener índice alguno en las tablas a utilizar y, aunque es un caso muy particular, no es imposible que ocurra.

Se basa en las siguientes premisas:

• Se debe llebar una o varias tablas con una cantidad de registros muy alta (varios millones)
• Se llenan de seguido, no esporádicamente. No sufren lecturas (SELECT) durante el tiempo de inserción
• Son tablas de caracter transitorio: un script lee una fuente de datos (ficheros) las rellena y cuando ha acabado, serán consultadas y borradas.

En este caso, es imprescindible para el rendimiento que las tablas donde se va a realizar la inserción no tengan índices ( aparte de la clave primaria claro) para que se hagan lo más rápido posible. Una vez finalizado el proceso de inserción, se construyen los índices necesarios, se ejecutan las consultas pertinentes y posteriormente se borran las tablas.

Si medimos el tiempo de ejecución del modelo clásico en fragmentos de 10.000 inserciones se verá que el tiempo para ejecutar esos mismo fragmentos aumenta mucho segun va pasando el tiempo y llenandose la tabla. Sin embargo el modelo de "patada a la teoría" mantiene una buena tasa de inserción constante. Posteriormente el tiempo de creación de índices es despreciable comparado con lo que tardaba la manera original con índices.

He intentado reproducir lo que me ha ocurrido hoy en una máquina de desarrollo y ha pasado en varios órdenes de magnitud menor pero aún así se consigue el mismo objetivo en la mitad de tiempo. 1 millon de inserciones (de las cuales la mitad derivan en una insercion adicional) en 250 segundos frente a 600 segundos por el mismo trabajo. Posteriormente la creación de los índices no supera los 60 segundos.

Conclusión: picardía y ganas de enredar acaban en beneficio para el rendimiento.

Continuando el post de instalación de sphinx vamos a ver un ejemplo práctico, que es lo que estamos desenado todos.

He descargado los RFC desde la web del IETF con un script en PHP y algo de expresiones regulares, e insertados en una tabla. En total son unos 4400 documentos con mucho texto para juguetear.

La base de datos tiene una sola tabla bastante simple, aquí está el código SQL para crearla:

El archivo de configuracion se va a mostrar por partes.

Apartado source

Se han definido dos índices, en uno se va a tener en cuenta el título de los RFC y en el otro vamos a hacer un poco el bruto indizando todo el contenido del RFC (llegan a ser 300KB o más) además del título. En el primer source se ve la información de conexión a base de datos y la sentencia sql de construcción del índice.

La sentencia se construye igual que cualquier SELECT de SQL pero con la peculiaridad de que el primer campo a recoger debe ser la clave primaria (recordar que esta DEBE ser un entero único de 32 bits). Todos los campos que aparezcan a continuación serán utilizados para el índice. De momento solo usaremos datos de texto, más adelante se detallará como introducir otro tipo de campos para búsquedas más avanzadas.

El segundo source esta definido mediante una herencia del primero, lo cual nos evita escribir 10 líneas ( los desarrolladores somos vagos y podemos estar un día escribiendo un script para evitar repetir la misma acción 2 veces ). Solo sobreescribe la sentencia SQL y se mantiene el resto.

Apartado index

Cada índice hace referencia a su fuente de datos definida más arriba.


Apartado indexer: simplemente forzamos a 32 megas el máximo usado por el indizador.

Apartado search: se ponen las rutas de los log y el descriptor de proceso. Se define el puerto asociado al demonio y otros parámetros de control. Si no se está seguro de que poner en algun sitio, dejarlo tal cual viene en el fichero esqueleto.

La directiva address es un mecanismo de seguridad, podemos forzar al demonio a que solo conteste las peticiones dirigidas a cierta ip. Si tenemos el script php en la misma máquina que sphinx se puede restringir a la direccion de loopback 127.0.0.1 y nos cubriremos las espaldas por si legan peticiones externas. Si sphinx esta instalado en una máquina diferente al origen de la consulta, pero se dispone de red local se puede asociar el demonio a la ip privada en vez de la pública.

Con esto ya tenemos fichero de configuración listo.

Así que al lio, lanzamos el indexer:

$ bin/indexer --config etc/sphinx.conf --all
indexing index 'rfc'...
collected 4398 docs, 0.2 MB
sorted 0.0 Mhits, 100.0% done
total 4398 docs, 222430 bytes
total 0.297 sec, 749621.68 bytes/sec, 14821.90 docs/sec
indexing index 'rfc2'...
collected 4398 docs, 214.1 MB
sorted 27.6 Mhits, 100.0% done
total 4398 docs, 214094137 bytes
total 22.821 sec, 9381369.37 bytes/sec, 192.72 docs/sec

En var/data estarán ahora los dos índices generados y tendrán dos tamaños bastante diferentes: 200 KB frente a 68 MB. Hay que decir que los índices tan grandes pueden ser habituales pero, al contrario que este caso, lo serán por el hecho de que las tablas indizadas tengan una cantidad de registros bastante alta en vez de tener una media de 150 KB de texto por registro.

$ ls -lh var/data/
total 70M
-rw-r--r-- 1 root root 0 2007-03-23 20:49 rfc2.spa
-rw-r--r-- 1 root root 68M 2007-03-23 20:49 rfc2.spd
-rw-r--r-- 1 root root 79 2007-03-23 20:49 rfc2.sph
-rw-r--r-- 1 root root 1,1M 2007-03-23 20:49 rfc2.spi
-rw-r--r-- 1 root root 0 2007-03-23 20:49 rfc.spa
-rw-r--r-- 1 root root 203K 2007-03-23 20:49 rfc.spd
-rw-r--r-- 1 root root 62 2007-03-23 20:49 rfc.sph
-rw-r--r-- 1 root root 23K 2007-03-23 20:49 rfc.spi

Y ahora lanzamos el demonio searchd:

$ bin/searchd --config etc/sphinx.conf
Sphinx 0.9.7-RC2
Copyright (c) 2001-2006, Andrew Aksyonoff

using config file 'etc/sphinx.conf'...

Llegados a este punto ya estamos en posicion para empezar a lanzar consultas al demonio y para ello usaremos el API PHP.
Un poquito de código:

Con esta función se hace una consulta muy simple basada en la keyword a buscar, el offset de resultados a devolver (para paginar) y un booleano para decidir si consultar el contenido o no. Primero creamos el objeto y se le asocia el servidor y puerto del demonio. A continuación se le indica que queremos obtener 10 resultados a partir del offset $off (0 por omisión), se selecciona el modo de consulta y se lanza la misma.

Los modos de consulta son:

• SPH_MATCH_ALL: el documento devuelto debe contener todas las palabras de la búsqueda
• SPH_MATCH_ANY: el documento devuelto debe contener alguna de las palabras de la búsqueda
• SPH_MATCH_PHRASE: el documento devuelto debe contener todas las palabras de la búsqueda y en el mismo orden

La variable $resultado devuelve bastante información pero de momento nos quedamos con dos elementos:

• $resultado['total_found'] : numero de resultados encontrados para la búsqueda
• $resultado['matches'] : array con los identificadores de documento como índice. Por eso se recuperan las claves con array_keys

Espero que esta guía haya sido de utilidad y que la gente se anime a instalarlo y cacharrear un poco.

Podeis probar la demo. Me gustaría no estar en un hosting compartido ni tener un ping tal alto para que vierais que esto es realmente rápido. Si alguien quiere el ejemplo le puedo facilitar los scripts de construcción de la base de datos, el resto está practicamente en las entradas.

Actualizacion
He cambiado la demo de sitio, porque la gente de dreamhost me tiraba el sphinx (ya decia yo que era demasiado chollo para un plan cutre de hosting compartido instalar un servicio como si nada ). Ahora está en una máquina con buenos recursos. Así que ya no hay excusa, los tiempos deberían ser bastante buenos.

Enlaces de interés

• sphinxsearch: web oficial de la herramienta
• Martin Porter: un referente en la técnica de stemming
• Quien usa SPHINX: un buen argumento para usarlo

Leyendo una entrada un poco antigua de MySQL Performance Blog me encuentro con un documento bastante interesante sobre comparativas de búsquedas de texto completo en MySQL hechas con diferentes sistemas: Lucene, Sphinx, TgSearch y el propio MySQL.

El documento en cuestión no es otro que High Performance Full Text Search for Database Content presentado en la EuroOSCON 2006.

De él extraigo estos gráficos que hablan por si solos (hacer click para ver en un tamaño decente).

Tiempo de ejecución de una consulta booleana

Tiempo de construcción del índice

Tamaño del índice

Tiempo de ejecución de consulta de tipo ‘phrase’'

Tiempo de ejecución de consulta normal

Como siempre sacar los gráficos de contexto es algo muy feo, esto tiene muchos matices y por eso recomiendo la lectura completa del documento. Aún así, hay una cosa en común en todos los resultados y es que SPHINX barre con mucha diferencia a cualquiera de los otros sistemas.

Ya no teneis excusa para instalar SPHINX