Embed Size (px)
Citation preview
1
Tema 3.Operaciones sobre el texto
Sistemas de Gestión Documental
2
Introducción No todas las palabras son igualmente
importantes en un texto para representar su significado.
Es necesario considerar un preprocesamiento del texto antes de indexarlo.
El preprocesamiento debe determinar los términos que deben ser índices.
Durante el preprocesamiento, se realizarán algunas operaciones sobre el texto de forma adicional, para mejorar la indexación.
3
Introducción Las operaciones principales que
podemos encontrar son: Análisis léxico Eliminación de palabras vacías Stemming Selección de términos índice Construcción de estructuras de
categorización de términos (tesauros, ...)
4
Introducción No obstante, el preprocesamiento puede
acarrear situaciones no deseadas: Buscamos el patrón “la casa de Pedro”. Si no
hemos indexado palabras vacías, no podremos recuperar textos con este patrón.
La recuperación puede ser más difícil de entender para el usuario si se aplica preprocesamiento.
Algunos sistemas (buscadores web) no realizan preprocesamiento, sacrificando rendimiento por velocidad y simplicidad en las tareas de búsquedas.
5
Preprocesamiento
DocumentoAcentos,
espacios, etc.Palabrasvacias
Grupos denombres
Stemming Indexación
Reconocimientode estructura
Full text
textoTexto +estructura
estructura
índices
6
Análisis léxico Consiste en convertir una secuencia de
caracteres en una secuencia de palabras. Las palabras serán los candidatos a índices. La separación de palabras vendrá dada por:
Espacios en blanco Dígitos Guiones Signos de puntuación Distinción de mayúsculas y minúsculas
7
Análisis léxico Los números (dígitos) no son buenos candidatos a
índices: son muy vagos en significado. Sin embargo, hay casos en los que pueden ser
importantes: Los dígitos pueden aparecer combinados con caracteres,
por ejemplo, 256 a.c. Las fechas pueden ser importantes. Los números de una tarjeta de crédito pueden ser
importantes ...
La solución puede ser no considerar secuencias de dígitos, a no ser que sigan expresiones regulares.
8
Análisis léxico La consideración de guiones presenta
también problemas: Se puede separar una palabra que contenga guiones
en palabras componentes (state-of-the-art = state of the art).
Pero hay palabras en las que los guiones son relevantes (B-49).
Existe la posibilidad de que un guión enlace dos partes de una misma palabra (fin de línea).
La solución puede ser aplicar una regla general, y considerar las excepciones.
9
Análisis léxico Los signos de puntuación se suelen
eliminar del texto. Existen casos en los que los signos de
puntuación forman parte de la palabra (236 a.c.) La eliminación de los signos, en estos casos,
no presenta excesivos problemas en el rendimiento de la consulta.
Aún así, hay casos en los que la eliminación de los signos de puntuación puede llevar a confusiones.
10
Análisis léxico La distinción de mayúsculas y
minúsculas no debería afectar al rendimiento de la consulta.
Lo habitual es convertir todo el texto a mayúsculas o minúsculas.
A pesar de ello, existen escenarios en los que conviene distinguir entre ambas.
11
Análisis léxico La implementación de estas operaciones
sobre el texto no son difíciles de realizar. No obstante, habrá que tener cuidado
en la tarea, puesto que pueden afectar a la recuperación y al tiempo empleado.
Se pueden obviar estas tareas, si bien no está comprobado que la no utilización de las mismas sea producente o contraproducente.
12
Palabras vacías Las palabras que son muy frecuentes en
los documentos no ayudan a discriminar. Dentro de este conjunto se hallan
palabras que carecen de significado por ellas mismas, como artículos, preposiciones, conjunciones, etc.
La eliminación de estas palabras reducirá el tamaño de la estructura del índice empleado (por ejemplo –40%).
13
Palabras vacías Algunos verbos, adverbios y
adjetivos pueden estar incluidos en las listas de palabras vacías, aunque tengan significado.
La eliminación de este tipo de palabras puede llevar a, por ejemplo, no poder encontrar “ser o no ser, esa es la cuestión”.
14
él ésta éstas éste éstos última últimas último últimos aañadió aún actualmente adelante además afirmó agregó ahíahora al algún algo alguna algunas alguno algunos alrededorambos ante anterior antes apenas aproximadamente aquí asíaseguró aunque ayer bajo bien buen buena buenas bueno buenoscómo cada casi cerca cierto cinco comentó como con conocerconsideró considera contra cosas creo cual cuales cualquiercuando cuanto cuatro cuenta da dado dan dar de debedeben debido decir dejó del demás dentro desde después dicedicen dicho dieron diferente diferentes dijeron dijo diodonde dos durante e ejemplo el ella ellas ello ellosembargo en encuentra entonces entre era eran esesa esas ese eso esos está están esta estaba estabanestamos estar estará estas este esto estos estoy estuvo exexiste existen explicó expresó fin fue fuera fueron gran grandesha había habían haber habrá hace hacen hacer hacerlo haciahaciendo han hasta hay haya he hecho hemos hicieronhizo hoy hubo igual incluso indicó informó junto la ladolas le les llegó lleva llevar lo los luego lugarmás manera manifestó mayor me mediante mejor mencionómenos mi mientras misma mismas mismo mismos momento muchamuchas mucho muchos muy nada nadie ni ningún ninguna ningunasninguno ningunos no nos nosotras nosotros nuestranuestras nuestro nuestros nueva nuevas nuevo nuevos nuncao ocho otra otras otro otros para parece parte partirpasada pasado pero pesar poca pocas poco pocos podemos podrápodrán podría podrían poner por porque posible próximo próximosprimer primera primero primeros principalmente propia propias propiopropios pudo pueda puede pueden pues qué que quedó queremosquién quien quienes quiere realizó realizado realizar respectosí sólo se señaló sea sean según segunda segundo seisser será serán sería si sido siempre siendo siete siguesiguiente sin sino sobre sola solamente solas solosolos son su sus tal también tampoco tan tanto teníatendrá tendrán tenemos tener tenga tengo tenido tercera tiene tienentoda todas todavía todo todos total tras trata través trestuvo un una unas uno unos usted va vamos vanvarias varios veces ver vez y ya yo
15
Analizador léxico y stopwords Implementación:
Utilizar un generador de analizadores léxicos (lex en unix)
Crear un analizador léxico a mano y ad hoc Crear un analizador léxico a mano como un
autómata de estados finitos El mejor es el primero, para casos
complicados. El tercero sería el siguiente, si el analizador es simple. El segundo sería muy costoso.
16
Analizador léxico y stopwords La implementación del tratamiento de las
stopwords se puede realizar de dos maneras: Examinar la salida del analizador léxico y
eliminar las palabras de la lista de stopwords (problema de búsqueda).
Eliminar las stopwords como parte del proceso del analizador léxico.
La segunda aproximación es más eficiente, y se puede implementar de forma sencilla con generadores de analizadores léxicos.
17
Stemming Variaciones sintácticas de una palabra
En la consulta aparece una palabra, pero en los documentos aparecen variantes sintácticas de la palabra.
Solución: obtener la raíz de la palabra y sustituirla por las palabras.
Se consigue obtener un concepto común desde las variantes de una palabra se mejora el rendimiento (exhaustividad).
Además se reduce el tamaño de los índices.
18
Stemming Existe controversia sobre la verdadera utilidad del
stemming. Los experimentos no ayudan a ver una clara conclusión.
El problema de aplicar stemming es que se pierde información sobre la palabra completa, o se necesita espacio adicional para almacenar esa información.
Algunos sistemas web desechan esta posibilidad de stemming.
Existen varias posibilidades para aplicar stemming: eliminación de afijos (prefijos y sufijos), tablas de búsqueda, variedad de sucesores y n-gramas.
19
Stemming Criterios para evaluar los stemers:
Corrección, efectividad de la recuperación, compresión
Aplicable en la indexación de documentos o en tiempo de consulta.
Hasta donde llegar: Overstemming se elimina gran parte de la
palabra; las búsquedas pueden dar resultados indeseados.
Understemming se elimina poca porción de la palabra; se pueden perder en una búsqueda documentos relevantes.
20
Stemming Eliminación de afijos
Es intuitivo, simple, y de fácil implementación. Es más importante la eliminación de sufijos
que la de prefijos. Existen varios algoritmos para su
implementación. El más famoso para lengua inglesa es el de Porter.
Básicamente, se trata de aplicar reglas siguiendo un cierto orden, para sustituir sufijos por otras subcadenas o cadenas vacías.
21
Stemming Tablas de búsqueda
Se busca la raíz de una palabra en una tabla. Depende de los datos que se tengan de la
raíz para el idioma. Puede no resultar práctico debido a la falta de
información sobre las raíces de los términos y el espacio de almacenamiento que necesita.
No se puede aplicar para palabras específicas o que no estén en el idioma para el que se tiene la tabla.
22
Stemming Variedad de sucesores
Se basa en la determinación de las fronteras de los morfemas.
Utiliza cierto conocimiento de la lingüística estructural.
Es más complejo que la eliminación de prefijos y sufijos.
La variedad de sucesores de una cadena es el número de caracteres diferentes que la siguen en las palabras de un texto.
23
Stemming Ejemplo de variedad de sucesores:
able, axle, accident, ape, about
apple
a 4 (b, x, c, p)ap 1 (e)app 0appl 0apple 0
Texto
Palabra
Variedad desucesores
24
Stemming Cuando el texto es lo suficientemente
largo (>2000 palabras), se produce que: Tomando una subcadena, a medida que se
añaden caracteres, disminuye la variedad de sucesores.
Llegado a un punto determinado (cantidad de caracteres de la subcadena), la variedad de sucesores comienza a aumentar.
Este es el punto que marca cual es la raíz de la palabra.
25
Stemming Metodos de corte para la variedad de
sucesores: Cutoff. Seleccionar un valor de corte fijo. Peak and plateau. El corte se produce en el carácter
para el que la variedad de sucesores excede la inmediatamente anterior y a la inmediatamente siguiente.
Complete word. El corte se produce en el segmento que coincide con una palabra en el texto.
Entropy. Considera la distribución de variedades de sucesores. Es un cálculo matemático.
26
Stemming Se debe elegir el segmento que es la
raíz: Si el primer segmento aparece en menos de
12 palabras, es probable que sea la raíz. En caso contrario, es posible que el primer
segmento sea un prefijo, con lo que se debe seleccionar el segundo segmento como raíz de la palabra.
Ninguno de los métodos es perfecto.
27
Stemming Ejemplo de variedad de sucesores
able, ape, beatable, fixable, read, readable,reading, reads, red, rope, ripe
Texto
readablePalabra
PREFIJO VARIEDAD DE SUCESORES LETRASR 3 E, I, ORE 2 A, DREA 1 DREAD 3 A, I, SREADA 1 BREADAB 1 LREADABL 1 EREADABLE 1 BLANCO
28
Stemming N-gramas
Se basa en la identificación de digramas y trigramas.
Es más un procedimiento de clustering de términos que de stemming (no se produce corte de palabras).
Puesto que se pueden usar digramas, trigramas, etc., se la ha llamado método de los n-gramas.
29
Stemming Ejemplo n-gramasdirigir di | ir | ri | ig | gi | irdireccion di | ir | re | ec | cc | ci | io | ondirector di | ir | re | ec | ct | to | orescena es | sc | ce | en | naescenario es | sc | ce | en | na | ar | ri | iocenar ce | en | na | ar
BA
CSim
2 A = Número de digramas únicos en la primera palabra
B = Número de digramas únicos en la segunda palabraC = Número de digramas únicos compartidos por la
primera y segunda palabras
30
Stemming Ejemplo n-gramas
Dirigir Dirección Director Escena Escenario Cenar
Dirigir -
Dirección -
Director -
Escena -
Escenario -
Cenar -
30.085
22
x
30.075
22
x
055
02
x
15.085
12
x
045
02
x
53.078
42
x
058
02
x
13.088
12
x
048
02
x
057
02
x
087
02
x
047
02
x
77.085
52
x
67.045
32
x
67.048
42
x
31
Stemming Ejemplo n-gramas
Dirigir Dirección Director Escena Escenario Cenar
Dirigir -
Dirección 0.30 -
Director 0.30 0.53 -
Escena 0 0 0 -
Escenario 0.15 0.13 0 0.77 -
Cenar 0 0 0 0.67 0.67 -
32
Ejercicios
1. Dado el texto con las siguiente palabras:
armario, armas, armazón, vencer, derrota, valentía, venerado, destrozar, descubrir, desestimar, descolgar, construir, derribar, derrocar, desarme, armada, vencimiento
Aplicar el método de peak and plateau y el complete word para obtener la raíz de las palabras: desarmar, armamento, vencido (Nota: tomar como límite de prefijos el valor 4)
2. Utilizando el método de los n-gramas (usando digramas), calcular las similitudes para las palabras: colocar, colocación, coloso, vocación, evocación, gesto.
