Stemming es el proceso de encontrar la raíz de una palabra para una palabra de origen dada. La raíz de una palabra no es necesariamente la misma que la raíz morfológica de la palabra .
La tarea de encontrar la raíz de una palabra ha sido un problema de larga data en informática . La primera publicación sobre este tema data de 1968 . Stemming se utiliza en los motores de búsqueda para expandir la consulta de búsqueda del usuario , es parte del proceso de normalización del texto .
Una forma específica de resolver el problema de encontrar la base de las palabras se llama algoritmo de lematización , y una implementación específica es lematizador .
El primer stemmer publicado fue escrito por Julie Beth Lovins en 1968 [1] . Este documento se destaca por su fecha de publicación temprana y ha tenido una gran influencia en el trabajo posterior en el campo.
El lematizador fue escrito más tarde por Martin Porter y publicado en 1980. Este lematizador ha sido muy utilizado y se ha convertido en el algoritmo estándar de facto para textos en inglés. El Dr. Porter recibió el Premio Strix en el año 2000 por su trabajo sobre derivación y recuperación de información.
Se han escrito y distribuido libremente muchas implementaciones del algoritmo de derivación de Porter; sin embargo, muchas de estas implementaciones contienen fallas difíciles de encontrar. Como resultado, estos algoritmos no funcionaron en todo su potencial. Para eliminar este tipo de error, Martin Porter lanzó una implementación gratuita oficial del algoritmo alrededor del año 2000. Continuó este trabajo durante los años siguientes, desarrollando Snowball , un marco para crear algoritmos de lematización y lematizadores mejorados en inglés, así como lematizadores para varios otros idiomas.
Hay varios tipos de algoritmos de derivación que difieren en términos de rendimiento, precisión y cómo se superan ciertos problemas de derivación.
Un lematizador simple busca una forma flexiva en una tabla de búsqueda . Las ventajas de este enfoque son su simplicidad, velocidad y facilidad de manejo de excepciones. Las desventajas incluyen que todas las formas flexivas deben enumerarse explícitamente en la tabla: las palabras nuevas o desconocidas no se procesarán incluso si son correctas (por ejemplo, iPads ~ iPad) y también el problema es que la tabla de búsqueda puede ser muy grande. Para idiomas con morfología simple como el inglés, los tamaños de las tablas son pequeños, pero para idiomas altamente flexivos (como el turco), una tabla puede tener cientos de posibles formas de flexión para cada raíz.
Las tablas de búsqueda utilizadas en lematizadores generalmente se generan de forma semiautomática. Por ejemplo, para la palabra en inglés "run", se generarán automáticamente las formas "running", "runs", "runned" y "runly". Las dos últimas formas son construcciones válidas, pero es poco probable que aparezcan en un texto en inglés normal.
El algoritmo de búsqueda puede usar el marcado previo a la partición para evitar este tipo de error de lematización , cuando se asignan diferentes palabras al mismo lema (overstemming) [2] .
Los algoritmos de truncamiento de terminación no utilizan una tabla de búsqueda, que consta de formas flexivas y relaciones de forma raíz. En cambio, generalmente se almacena una lista más pequeña de "reglas", que utilizan los algoritmos, dada la forma de la palabra, para encontrar su raíz [3] . Algunas reglas de ejemplo se ven así:
Los algoritmos de truncamiento de terminación son mucho más eficientes que los algoritmos de fuerza bruta . Para desarrollar tales algoritmos, se necesita un programador que sea bastante versado en lingüística , en particular en morfología , y que también sea capaz de codificar "reglas de truncamiento". Los algoritmos de truncamiento de terminación son ineficaces para las excepciones (p. ej., 'corrió' y 'ejecutó'). Las soluciones obtenidas mediante los algoritmos de truncamiento de terminaciones se limitan a aquellas partes del discurso que tienen terminaciones y sufijos conocidos, con algunas excepciones. Esta es una limitación seria, ya que no todas las partes del discurso tienen un conjunto de reglas bien definido. La lematización intenta eliminar esta limitación.
También se pueden implementar algoritmos de truncamiento de prefijos. Sin embargo, no todos los idiomas tienen prefijos y sufijos.
Criterios adicionales para algoritmosLos algoritmos de truncamiento de terminación pueden variar en los resultados por una variedad de razones. Una de estas razones es la peculiaridad del algoritmo: si la palabra a la salida del algoritmo debe ser una palabra real en el idioma dado. Algunos enfoques no requieren la presencia de la palabra en el léxico del idioma correspondiente . Además, algunos algoritmos mantienen una base de datos de todas las raíces morfológicas conocidas que existen como palabras reales. Estos algoritmos verifican la presencia de un término en la base de datos para tomar una decisión. Como regla general, si no se encuentra el término, se toman acciones alternativas. Estas acciones alternativas pueden utilizar criterios ligeramente diferentes para tomar una decisión. Un término que no existe puede servir como regla de truncamiento alternativa.
Puede ser que se apliquen dos o más reglas de truncamiento al mismo término de entrada, creando ambigüedad sobre qué regla aplicar. El algoritmo puede determinar la prioridad de ejecución de dichas reglas (con la ayuda de una persona o de forma estocástica). O el algoritmo puede rechazar una de las reglas si da como resultado un término inexistente, mientras que el otro no. Por ejemplo, para el término en inglés "amistosos", el algoritmo puede determinar el sufijo "ies", aplicar la regla adecuada y devolver el resultado "amistosos". Lo más probable es que el término "amigo" no se encuentre en el léxico y, por lo tanto, esta regla será rechazada.
Una de las mejoras en los algoritmos de truncamiento de sufijos es el uso de sufijos y sustitución de sufijos. Al igual que la regla de truncamiento, la regla de sustitución reemplaza un sufijo o termina con uno alternativo. Por ejemplo, puede haber una regla que reemplace "ies" con "y". Dado que las reglas de truncamiento conducen a un término inexistente en el léxico, las reglas de sustitución resuelven este problema. En este ejemplo, "amistosos" se convierte en "amistoso" en lugar de "amistoso".
Normalmente, la aplicación de estas reglas es cíclica o recursiva. Después de la primera aplicación de la regla de sustitución para este ejemplo, el algoritmo selecciona la siguiente regla para el término "amigable", como resultado de lo cual se identificará y reconocerá la regla de truncamiento del sufijo "ly". Así, el término "amistosos" pasa a ser el término "amigos" mediante la regla de sustitución, que, tras aplicar la regla del truncamiento, pasa a ser el término "amigo".
Este ejemplo ayuda a demostrar la diferencia entre un método basado en reglas y un método de fuerza bruta . Usando una búsqueda exhaustiva, el algoritmo buscará el término "amigos" en un conjunto de cientos de miles de formas de palabras flexivas e idealmente encontrará la raíz correspondiente "amigo". En un método basado en reglas, las reglas se ejecutan secuencialmente, dando como resultado la misma solución. Lo más probable es que el método basado en reglas sea más rápido.
En lingüística, los términos más comunes para los afijos son sufijo y prefijo. Además de los enfoques que manejan sufijos o terminaciones, algunos también manejan prefijos. Por ejemplo, para una palabra en inglés indefinidamente , este método determinará que la construcción "in" al comienzo de la palabra es un prefijo y puede eliminarse para obtener la raíz de la palabra. Muchos de los métodos mencionados anteriormente también utilizan este enfoque. Por ejemplo, el algoritmo de truncamiento de terminaciones puede manejar tanto sufijos y terminaciones como prefijos, en cuyo caso se llamará de manera diferente y seguirá este enfoque. En una publicación se pueden encontrar investigaciones sobre afijos lematizadores para varios idiomas europeos ( Jongejan et al 2009 ).
Un enfoque más complejo para resolver el problema de determinar la raíz de una palabra es la lematización . Para comprender cómo funciona la lematización, debe saber cómo se crean las diferentes formas de una palabra. La mayoría de las palabras cambian cuando se usan en diferentes formas gramaticales . El final de la palabra se reemplaza por un final gramatical, y esto conduce a una nueva forma de la palabra original. La lematización realiza la transformación inversa: reemplaza la terminación gramatical por un sufijo o la terminación de la forma inicial [4] .
La lematización también incluye determinar la parte del discurso de una palabra y aplicar diferentes reglas de normalización para cada parte del discurso. La definición de la parte del discurso ocurre antes de intentar encontrar la raíz, porque para algunos idiomas las reglas de derivación dependen de la parte del discurso de una palabra dada.
Este enfoque depende en gran medida de la definición exacta de la categoría léxica (parte del discurso). Aunque existe una superposición entre las reglas de normalización para algunas categorías léxicas, especificar la categoría incorrecta o no determinar la categoría correcta anula la ventaja de este enfoque sobre el algoritmo de truncamiento. La idea principal es que si el lematizador puede obtener más información sobre la palabra que se está procesando, entonces puede aplicar reglas de normalización más precisas.
Enfoque de reglas de ondulación descendenteLas reglas de ondulación se diseñaron originalmente para adquirir conocimientos y mantener sistemas basados en reglas. En este enfoque, el conocimiento se adquiere con base en el contexto actual y se agrega gradualmente. Las reglas se crean para clasificar los casos que se ajustan a un contexto particular.
A diferencia de las reglas de clasificación estándar, las reglas Ripple-down usan excepciones a las reglas existentes, por lo que los cambios solo están relacionados con el contexto de la regla y no afectan a otros. Las herramientas de adquisición de conocimientos lo ayudan a encontrar y modificar reglas en conflicto. Aquí hay un ejemplo simple de una regla Ripple-down :
if a ^ b then c except if d then e else if f ^ g then h
Esta regla se puede interpretar de la siguiente manera: “si a y b son verdaderas, entonces decidimos c , excepto cuando d no es verdadera. Si d es verdadera (excepción), entonces tomamos una decisión e . Si a y b no son verdaderas, entonces pasamos a otra regla y decidimos h si f y g son verdaderas". Esta forma de reglas resuelve muy bien el problema de la lematización [5] .
Para crear una excepción a una regla, el algoritmo primero debe determinar la palabra que indujo la excepción dada. Después de eso, se determinan las diferencias entre las dos palabras. La condición de excepción de la regla coincidirá con estas diferencias.
Los algoritmos estocásticos están asociados con la determinación probabilística de la raíz de una palabra. Estos algoritmos construyen un modelo probabilístico y se entrenan utilizando una tabla de correspondencia entre la raíz y las formas flexivas. Este modelo suele presentarse en forma de reglas lingüísticas complejas, de naturaleza similar a las reglas utilizadas en los algoritmos de truncamiento y lematización. La derivación se realiza introduciendo formas modificadas para entrenar el modelo y generando una forma raíz de acuerdo con el conjunto interno de reglas del modelo, excepto que las decisiones relacionadas con la aplicación de la regla o secuencia de reglas más adecuada, así como la elección de la raíz de la palabra, se aplican sobre la base de que la palabra correcta resultante tendrá la probabilidad más alta (las palabras incorrectas tienen la probabilidad más baja).
Algunos algoritmos de lematización son estocásticos en el sentido de que una palabra puede pertenecer a varias partes del discurso con diferentes probabilidades. Estos algoritmos también pueden tener en cuenta las palabras circundantes, llamadas contexto. Las gramáticas libres de contexto no tienen en cuenta ninguna información adicional. En cualquier caso, después de asignar una probabilidad a cada posible parte de la oración, se selecciona la parte de la oración con mayor probabilidad, así como las reglas correspondientes para obtener una forma normalizada.
Algunos algoritmos de derivación utilizan el análisis de N-gramas para seleccionar una raíz apropiada para una palabra [6] .
Stemming basado en un corpus de textosUna de las principales desventajas de los lematizadores clásicos (como el lematizador de Porter) es que a menudo no distinguen entre palabras con sintaxis similar pero significados completamente diferentes. Por ejemplo, "noticias" y "nuevo" se reducirán a la raíz "nuevo" como resultado de la derivación, aunque estas palabras pertenecen a diferentes categorías léxicas. Otro problema es que algunos algoritmos de derivación pueden ser adecuados para un corpus y causar demasiados errores en otro. Por ejemplo, las palabras "stock", "stocks", "stocking", etc. tendrán un significado especial en los textos del diario The Wall Street Journal . La idea principal de la lematización basada en corpus es crear clases de equivalencia para las palabras de lematizadores clásicos y luego "romper" algunas palabras combinadas en función de su aparición en el corpus. También ayuda a prevenir las conocidas colisiones del algoritmo de Porter, como "política/policía", ya que la posibilidad de que estas palabras aparezcan juntas es bastante baja [7] .
Dichos algoritmos utilizan una base de datos de raíces (por ejemplo, un conjunto de documentos que contienen las raíces de las palabras). Estas raíces no corresponden necesariamente a palabras ordinarias; en la mayoría de los casos, la raíz es una subcadena (por ejemplo, en inglés, "brows" es una subcadena en las palabras "browse" y "browsing"). Para determinar la raíz de una palabra, el algoritmo intenta relacionarla con las raíces de la base de datos, aplicando varias restricciones, por ejemplo, en la longitud de la raíz buscada en la palabra en relación con la longitud de la palabra misma (por ejemplo, ejemplo, el prefijo corto "ser", que es la base de tales palabras, como "ser", "estado" y "ser" no formaría la base de "al lado").
Los enfoques híbridos utilizan dos o más de los métodos descritos anteriormente. Un ejemplo simple es el algoritmo del árbol de sufijos , que al comienzo de su trabajo utiliza tablas de búsqueda para obtener datos iniciales mediante una búsqueda exhaustiva. Sin embargo, en lugar de almacenar todo el complejo de relaciones entre palabras para un idioma en particular, se usa una tabla de búsqueda para almacenar una pequeña cantidad de "excepciones frecuentes" (por ejemplo, para el idioma inglés "ran => run"). Si la palabra no está en la lista de exclusión, se aplican algoritmos de truncamiento final o lematización para obtener el resultado.
Si bien la mayor parte de la actividad científica temprana en esta área se centró en el inglés (principalmente utilizando el algoritmo de derivación de Porter), el trabajo posterior se ha dedicado a muchos otros idiomas [8] [9] [10] [11] [12] .
El hebreo y el árabe todavía se consideran idiomas difíciles de aprender en términos de lematización. Los algoritmos de derivación en inglés son bastante triviales (solo surgen problemas ocasionales, por ejemplo, la palabra "dries" es la tercera persona singular del tiempo presente del verbo "dry", o la palabra "axes" es el plural de "axe" y " eje"); pero los lematizadores se vuelven más difíciles de diseñar cuando se elige un idioma de destino más complejo, es decir, un idioma con morfología y ortografía más complejas. Por ejemplo, los lematizadores para el idioma italiano son más complejos que los lematizadores para el inglés (debido a la gran cantidad de formas de flexión de los verbos), las implementaciones para el idioma ruso son aún más difíciles (una gran cantidad de declinaciones de sustantivos), para el hebreo son aún más complejos (debido a la morfología no concatenativa), la escritura sin vocales y la necesidad de algoritmos de truncamiento de prefijos: las raíces de las palabras hebreas pueden tener dos, tres o cuatro caracteres, pero no más), y así sucesivamente.
Los algoritmos de derivación multilingüe aplican las reglas morfológicas de dos o más idiomas al mismo tiempo.
El idioma ruso pertenece al grupo de idiomas sintéticos de flexión, es decir, idiomas en los que predomina la formación de palabras utilizando afijoscombinando varios significados gramaticales a la vez (por ejemplo, tipo : la terminación é indica al mismo tiempo el género singular, masculino y caso nominativo), por lo que este lenguaje permite utilizar algoritmos de derivación. El idioma ruso tiene un cambio morfológico complejo de palabras, que es una fuente de errores cuando se usa la lematización. Como solución a este problema, junto con los clásicos algoritmos de derivación, se pueden utilizar algoritmos de lematización que llevan las palabras a la forma básica inicial.
Consideremos las implementaciones más populares de lematizadores basadas en varios principios y que permiten el procesamiento de palabras inexistentes para el idioma ruso.
Stemmer PorterLa idea principal del lematizador de Porter es que hay un número limitado de sufijos de formación de palabras, y la lematización de palabras se produce sin usar ninguna base de raíz: solo un conjunto de sufijos existentes y reglas establecidas manualmente.
El algoritmo consta de cinco pasos. En cada paso, se corta un sufijo de formación de palabras y se verifica que la parte restante cumpla con las reglas (por ejemplo, para las palabras rusas, la raíz debe contener al menos una vocal). Si la palabra resultante cumple las reglas, se produce la transición al siguiente paso. Si no, el algoritmo elige otro sufijo para el recorte. En el primer paso, se corta el sufijo formador máximo, en el segundo, la letra "i", en el tercero, el sufijo formador de palabras, en el cuarto, los sufijos de formas superlativas, "ь". y uno de los dos "n" [13] .
Este algoritmo a menudo trunca la palabra más de lo necesario, lo que dificulta obtener la raíz correcta de la palabra, por ejemplo, cama-> techo (en este caso, la parte que realmente no cambia es cama , pero el lematizador elige el morfema más largo para supresión). Además, el lematizador de Porter no se adapta a todos los tipos de cambios en la raíz de la palabra (por ejemplo, vocales dejadas y fluidas).
StemkaEste algoritmo de derivación (analizador) fue desarrollado por Andrey Kovalenko en 2002. Se basa en un modelo probabilístico: el analizador analiza las palabras del texto de entrenamiento en pares "las dos últimas letras de la raíz" + "sufijo", y si ese par ya está presente en el modelo, su peso aumenta , de lo contrario, se agrega al modelo. Después de eso, la matriz de datos resultante se clasifica en orden descendente de peso y los modelos, cuya probabilidad es inferior a 1/10000, se cortan. El resultado, un conjunto de terminaciones potenciales con condiciones en los caracteres anteriores, se invierte para facilitar la exploración de formas de palabras "de derecha a izquierda" y se presenta como una tabla de transición de un autómata finito. Al analizar, la palabra se escanea de acuerdo con las tablas de transición construidas. También se agregó una regla especial al algoritmo, que establece que la raíz invariable debe contener al menos una vocal [14] .
El analizador presentado está disponible en los textos fuente y puede ser utilizado en forma libre con la condición de referencia a la fuente [15] [16] .
Mi talloEl stemmer MyStem fue desarrollado por Ilya Segalovich en 1998. Ahora es propiedad de Yandex [17] . En el primer paso, utilizando el árbol de sufijos en la palabra de entrada, se determinan los posibles límites entre la raíz y el sufijo, después de lo cual, para cada raíz potencial (comenzando con la más larga), la búsqueda binaria en el árbol de raíces verifica su presencia en el diccionario o encontrar las raíces más cercanas a él (por una medida de proximidad es la longitud de la "cola" común). Si la palabra es una palabra del diccionario, el algoritmo termina; de lo contrario, continúa con la siguiente partición.
Si la variante de la raíz no coincide con ninguna de las raíces del diccionario "más cercanas", significa que la palabra analizada con esta variante de la raíz no está en el diccionario. Luego, con base en la raíz, el sufijo y el modelo existentes de la raíz del vocabulario "más cercano", se genera un modelo hipotético para cambiar la palabra dada. Se recuerda la hipótesis, y si ya se ha construido antes, aumenta su peso. Si la palabra nunca se encontró en el diccionario, la longitud de la raíz general requerida se reduce en uno, el árbol se escanea en busca de nuevas hipótesis. Cuando la longitud de la "cola" común llega a 2, la búsqueda se detiene y las hipótesis se clasifican por productividad: si el peso de la hipótesis es cinco o más veces menor que el peso más grande, dicha hipótesis se elimina. El resultado del trabajo del lematizador es el conjunto resultante de hipótesis para una palabra inexistente o una hipótesis para una palabra del diccionario [18] .
El despalillador se puede utilizar con fines comerciales; las excepciones son: la creación y distribución de spam, la optimización de motores de búsqueda de sitios y el desarrollo de productos y servicios similares a los servicios y productos de Yandex [17] . Los códigos fuente no se distribuyen [19] . Para instalar, simplemente descargue y descomprima el archivo [20] .
Hay dos tipos de errores en los algoritmos de lematización: overstemming y understemming . Overstemming es un error del primer tipo , cuando las palabras flexivas se atribuyen erróneamente a un lema. Understemming es un error del segundo tipo , cuando las formas morfológicas de una palabra se atribuyen a lemas diferentes. Los algoritmos de derivación intentan minimizar ambos errores, aunque la reducción de un tipo de error puede aumentar el otro [21] .
Consideremos estos tipos de errores en el trabajo del algoritmo de derivación de Porter. caso de error de overstemming : este algoritmo hará coincidir las palabras "universal", "universidad" y "universo" con la raíz "univers"; aunque estas palabras son etimológicamente diferentes, sus significados modernos se refieren a diferentes áreas, por lo que no es correcto tratarlas como sinónimos. Caso de error de comprensión : el algoritmo de Porter emparejará palabras derivadas del mismo lema con diferentes raíces y, por lo tanto, las atribuirá a diferentes lemas: "alumno" → "alumno", "alumni" → "alumni", "alumna" / " alumnae" → "alumna" (estas palabras conservaron características latinas en su morfología, pero estos casi sinónimos no fueron combinados por un lematizador).
Stemming se utiliza como un método aproximado para agrupar palabras con significados básicos similares. Por ejemplo, el texto que menciona "narcisos" probablemente esté estrechamente relacionado con el texto que menciona "narciso" (sin la "s"). Pero en algunos casos, las palabras con la misma raíz tienen significados idiomáticos que casi no están relacionados: la búsqueda de un usuario de documentos que contengan "marketing" también arrojará documentos que mencionan "markets" pero no contienen "marketing" (que, muy probablemente, no satisfacer las necesidades de información del usuario).
Stemming es bastante común en los motores de búsqueda . Sin embargo, relativamente pronto se reconoció que la eficacia del stemming en los motores de búsqueda para el idioma inglés era muy limitada, y esto llevó a los jóvenes investigadores en el campo de la recuperación de información a comprender que el stemming no es de aplicación general [22] [23] . En los motores de búsqueda, en lugar de derivaciones, se puede utilizar un enfoque basado en la búsqueda de N-gramas , en lugar de derivaciones. Además, estudios recientes han demostrado grandes beneficios en la búsqueda de N-gramas para idiomas distintos al inglés [24] [25] .
Cuando se analizan áreas temáticas usando stemming, se construyen diccionarios de estas áreas [26] .
Muchas empresas comerciales han estado utilizando lematización desde al menos la década de 1980 y han desarrollado lematizadores algorítmicos y léxicos para muchos idiomas [27] [28] .
Se compararon los despalilladores bola de nieve con los comerciales. Los resultados han sido mixtos [29] [30] .
El motor de búsqueda de Google lleva utilizando stemming desde 2003 [31] . Anteriormente, una búsqueda de "peces" no devolvía resultados que contuvieran "pesca".