« strtolower y los acentos en php
Mejoras en SearchPedia: el buscador de la wikipedia »

Stemmer en castellano para SPHINX

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:



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:

PLAIN TEXT
CODE:
  1. /// morphology flags
  2. enum ESphMorphology
  3. {
  4.     SPH_MORPH_NONE        = 0,
  5.     SPH_MORPH_STEM_EN         = (1UL<<1),
  6.     SPH_MORPH_STEM_RU_CP1251    = (1UL<<2),
  7.     SPH_MORPH_STEM_RU_UTF8    = (1UL<<3),
  8.     SPH_MORPH_SOUNDEX         = (1UL<<4),
  9.     SPH_MORPH_STEM_ES         = (1UL<<5),
  10.     SPH_MORPH_UNKNOWN         = (1UL<<30)
  11. };


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

PLAIN TEXT
CODE:
  1. DWORD CSphDict_CRC32::GetWordID ( BYTE * pWord )
  2. {
  3.     if ( m_iMorph & SPH_MORPH_STEM_EN )
  4.         stem_en ( pWord );
  5.     if ( m_iMorph & SPH_MORPH_STEM_ES )
  6.         stem_es ( pWord );
  7.     if ( m_iMorph & SPH_MORPH_STEM_RU_CP1251 )
  8.         stem_ru_cp1251 ( pWord );
  9.     if ( m_iMorph & SPH_MORPH_STEM_RU_UTF8 )
  10.         stem_ru_utf8 ( (WORD*)pWord );
  11.     if ( m_iMorph & SPH_MORPH_SOUNDEX )
  12.         stem_soundex ( pWord );
  13.  
  14.     return FilterStopword ( sphCRC32 ( pWord ) );
  15. }


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:

PLAIN TEXT
CODE:
  1. DWORD sphConfMorphology ( const CSphConfigSection & hIndex, bool bUseUTF8 )
  2. {
  3.     if ( !hIndex("morphology") )
  4.         return SPH_MORPH_NONE;
  5.  
  6.     const CSphString & sOption = hIndex["morphology"];
  7.  
  8.     DWORD iMorph = SPH_MORPH_UNKNOWN;
  9.     DWORD iStemRu = ( bUseUTF8 ? SPH_MORPH_STEM_RU_UTF8 : SPH_MORPH_STEM_RU_CP1251 );
  10.  
  11.     if ( sOption=="stem_en" )
  12.         iMorph = SPH_MORPH_STEM_EN;
  13.  
  14.     else if ( sOption=="stem_es" )
  15.         iMorph = SPH_MORPH_STEM_ES;
  16.  
  17.     else if ( sOption=="stem_ru" )
  18.         iMorph = iStemRu;
  19.  
  20.     else if ( sOption=="stem_enru" )
  21.         iMorph = iStemRu | SPH_MORPH_STEM_EN;
  22.  
  23.     else if ( sOption=="soundex" )
  24.         iMorph = SPH_MORPH_SOUNDEX;
  25.  
  26.     else if ( sOption.IsEmpty() || sOption=="none" )
  27.         iMorph = SPH_MORPH_NONE;
  28.  
  29.     return iMorph;
  30. }

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

PLAIN TEXT
CODE:
  1. /// stem lowercase Spanish word
  2. void    stem_es ( BYTE * pWord );

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

PLAIN TEXT
CODE:
  1. am__objects_1 = sphinx.$(OBJEXT) sphinxexcerpt.$(OBJEXT) \
  2.     sphinxquery.$(OBJEXT) sphinxsoundex.$(OBJEXT) \
  3.     sphinxstemen.$(OBJEXT) sphinxstemes.$(OBJEXT) sphinxstemru.$(OBJEXT) \
  4.     sphinxutils.$(OBJEXT) md5.$(OBJEXT) sphinxstd.$(OBJEXT)

y también el cpp en los fuentes

PLAIN TEXT
CODE:
  1. SRC_SPHINX = sphinx.cpp sphinxexcerpt.cpp sphinxquery.cpp sphinxsoundex.cpp sphinxstemen.cpp sphinxstemes.cpp sphinxstemru.cpp sphinxutils.cpp md5.cpp sphinxstd.cpp

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):

PLAIN TEXT
CODE:
  1. index x
  2. {
  3.         morphology              = stem_es
  4.         charset_type            = utf-8
  5.         charset_table            = 0..9, A..Z->a..z, _, a..z, U+C9->U+E9, U+C1->U+E1, \
  6.                                    U+DA->U+FA, U+D1->U+F1, U+D3->U+F3, U+CD->U+ED, U+E1, \
  7.                                    U+E9, U+FA, U+F1, U+F3, U+ED
  8. }



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).

This entry was posted on Sábado, Mayo 26th, 2007 at 23:26 pm and is filed under Motores de búsqueda, MySQL. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

10 Responses to “Stemmer en castellano para SPHINX”

  1. jmrrva Says:
    Mayo 29th, 2007 at 19:16 pm

    Hola,

    Una tonteria: Has tenido en cuenta el rollo de los acentos? Muchas veces no se acentua, por error ortografico o porque el texto esta en mayusculas.

    fastidiándole -> fastid
    fastidiandole -> fastid

    Salu2

  2. mike Says:
    Mayo 30th, 2007 at 8:11 am

    Una palabra en mayúsculas también debe acentuarse.

  3. CompuGlobalHiperMegaNet Says:
    Mayo 30th, 2007 at 8:29 am

    En la parte con stemmer, la lematización hace su trabajo reduciendo la palabra a su lexema teniendo en cuenta los acentos (de hecho algunas palabras no se lematizan igual si no tiene acento, sobre todo algunas conjugaciones). Una vez reducida la palabra a su lexema se convierten los acentos a sus equivalentes sin acentuar (fase final).

    La mayúsculas se convierten a minúsculas directamente desde sphinx, ya que semánticamente no ofrecen nada.

    Un saludo

  4. javi Says:
    Mayo 30th, 2007 at 11:58 am

    La lástima de estos stemmers es que es bastante complicado afinar al 100%. En la aplicación searchpedia que das basada en el stemmer quizás no sea tan crítico pero en otras ese nivel de acierto sí es necesario.
    Un ejemplo en el que el corte no funciona correctamente, entre otros, es pena.
    Si no estoy equivocado pena lo resumirá a pen e identificará a igual nivel de similitud todas las palabras que tengan ese lexema.
    Esto hace que buscar pena en la searchpedia devuelva como 5 primeros resultados:
    1.- Pena de muerte
    2.- Pene
    3.- Pena de muerte (desambiguación)
    4.- Pen Pen
    5.- Pena
    En principio no parece un mal resultado, ya que 1,3,5 están directamente relacionados, aunque el término exacto de búsqueda aparezca en quinta posición. Este es un comportamiento que también se da en el stemmer que he utilizado para java utilizando una implementación de snowball en castellano.

    El problema es que en caso de necesitar buscar este término en contenido de artículos sin un filtro previo tendríamos bastantos artículos no relevantes entre los primeros.

    El objetivo es obtener un mecanismo de reducción de palabras para el índice que resuma todo lo posible pero que no identifique palabras claramente diferentes. Quizás lo optimo, aunque el stemmer te resuelva un alto número de casos, es implementar un mecanismo que sea mezcla de algoritmo de reducción+diccionario.
    Otra opción es utilizar un lematizador.
    El objetivo de un lematizador, es encontrar el lema de una palabra p, esto es, buscar la palabra l del diccionario que te explica p. Por ejemplo para p=jardineros, l=jadinero el problema es que jardín quedaría fuera de la búsqueda. Quizás estos resultados, en caso de querer considerarlos se deberían tratar mediante el uso de familias de palabras, pero es complejo.

    Si a partir de jardinero quieres obtener jardín se necesita el mecanismo que te devuelva la raiz de la palabra (Lexematizador? o stemmer ). De todas formas esto es reducir demasiado la información para una búsqueda porque en el ejemplo que has propocionado de fontanería y fontanero también podrías incluir fontana o incluso fuente si consideras las irregularidades(como en puede y poder o árbol y arbóreo) todo esto hace que se expanda mucho más el problema de los homógrafos en las búsquedas, ya que si este problema se da entre palabras, se da mucho más entre lexemas, con lo que la aparición de resultados no relevantes en una búsqueda puede aumentar.

    Yo de momento en el mecanismo que estoy utilizando en mi apliación de búsqueda utilizo un stemmer, aunque he eliminado algunas de las reducciones que me proporcionaba snowball y he añadido alguna otra(si no estoy equivocado implementa tambien el algoritmo de Porter) los resultados como en tu caso bastante correctos, El problema es que tiene deficiencias difíciles de afrontar.

    Si consideramos los dos errores de las búsquedas:
    1.- Obtener resultados no relevantes respecto a la cadena de búsqueda c.
    2.- Omitir resultados relevantes respecto a la cadena de búsqueda c.

    El uso de un Stemmer o \’Lexematizador\’ reduce 2 a cambio de aumentar 1.
    Un Lematizador reduciría tambien 2(aunque muchísimo menos que un stemmer) pero apenas aumentaría 1.
    Dependiendo de la cantidad de documentos resultado de la búsqueda y de la funcionalidad que queremos dar podemos considerar cual de estos errores es más importante y, por tanto, decidir que tipo de reductor de palabras será mejor en cada caso.

    Realmente es todavía un problema bastante abierto.

    Un saludo.

  5. Pau Iglesias Says:
    Mayo 31st, 2007 at 8:17 am

    Muy buen trabajo, Jose. En cuanto pueda actualizaré a la última versión del stemmer en agregax.

  6. ricardo galli Says:
    Diciembre 20th, 2007 at 1:00 am

    Hola Jose,
    adapté tu código para que funcione en el último snapshot del Sphinx (0.9.8-svn-r985). Lo compilé y está funcionando en el buscado de Menéame (http://meneame.net).

    El patch lo puedes bajar en mnm.uib.es/gallir/tmp/sphinx-0.9.8-svn-r985-ES.patch

    ¿Qué te parece? (dejé el código tal cuál, si lo ves bien se puede enviar el parche para que lo incluyan en la versión oficial después de arreglar un poco la estética).

    Gracias por el curro.

  7. CompuGlobalHiperMegaNet Says:
    Diciembre 20th, 2007 at 14:44 pm

    Revisaré un poco el parche y su funcionamiento con sphinx 0.9.8 y publicaré la versión definitiva estos días.

    Muchas gracias por el feedback.

    Un saludo

  8. Mateo Says:
    Marzo 15th, 2008 at 19:55 pm

    CompuGlobalHiperMegaNet puedes poner el tutorial para la versión 0.9.8 ?

    Gracias!

  9. victor Says:
    Marzo 25th, 2008 at 18:20 pm

    Un estupendo tutorial!!. Tienes info acerca de qué es lo que hay que cambiar para la versión 0.98?. No se pueden identificar algunas partes. Muchas gracias de todas formas por tu ayuda.

  10. Miguel Says:
    Abril 4th, 2008 at 22:47 pm

    Para 0.9.8 no hace falta ya que este puede utilizar libstemmer de C el cual es el mismo y es muy facil de utilizar de integrar.

    Considera estos pasos para una instalacion empezando de nada:
    1. baja sphinx a tu ordenador
    2. tar -xzf
    3. cd sphinx-0.9.8/
    4. wget http://snowball.tartarus.org/dist/libstemmer_c.tgz
    5. tar -xzf libstemmer_c.tgz
    6. ./configure –with-libstemmer

    En este caso se declara el stemmer como libstemmer_spanish en la configuracion de sphinx (sphinx.conf).

Leave a Reply

This is a captcha-picture. It is used to prevent mass-access by robots. (see: www.captcha.net)

Debes leer y teclear los 5 caracteres entre 0..9 y A..F, y enviar la respuesta.

  

No puedo leer esto. Por favor, generar un