Information retrieval Flashcards
Describa un indice invertido.
Un ı́ndice invertido (II) contiene por cada palabra una lista de los documentos en los cuáles aparece dicha palabra.
En el indice se guardan las palabras alfabeticamente, por lo que para realizar una consulta no hace falta mas que realizar una busqueda binaria del termino para poder recuperar los documentos que lo contienen.
Liste las opciones de almacenamiento de lexico.
- Léxico Concatenado
- Front Coding
Explique estructura de almacenamiento de lexico concatenado.
La estructura mas simple es una tabla en donde almacenemos en cada posición el offset en bytes a donde está almacenado el término. Cuando llegamos a una posición de esta tabla leemos la posición siguiente para saber la longitud del término, luego vamos a la posición indicada, accedemos al término y comparamos contra el que estamos buscando.
Explique estructura de almacenamiento de lexico front coding.
Este mecanismo aprovecha la particularidad de que en una lista ordenada alfabéticamente de términos los términos vecinos suelen compartir los primeros caracteres. Esto puede aprovecharse mediante una estructura en la cual indiquemos la cantidad de caracteres (prefijo) compartidos con el término anterior, la cantidad de caracteres diferentes y un puntero a cuales son esos caracteres.
Cuando tiene sentido usar front coding?
El front-coding sólo es necesario cuando tenemos poca memoria o bien la memoria que tenemos no es suficiente porque tenemos una enorme cantidad de términos. En general este caso es raro y se suele dar el inverso, el léxico no es un problema en memoria pero queremos poder encontrar los términos muy rápidamente.
Almacentamiento de punteros: Cual es la primera mejora que se puede hacer en el almacenamiento de punteros?
Ordenar los documentos de forma creciente y almacenar, en lugar del nro. de documento, las distancias entre los documentos.
Que problema tiene el almacenamiento de docs. como la distancia entre ellos? Como se soluciona?
El peor de los casos es que un termino aparezca solamente en el ultimo documento, por lo que la cantidad de bits para codificarlo sera suboptima.
Se soluciona usando codigos de longitud variable.
Describa condigos de long. variable.
En cada byte el primer bit indica si el byte es el ultimo o si el nro. sigue en el proximo byte.
Codigo unario.
Escribimos n−1 bits en cero y luego un 1. Para la distancia n el código unario ocupa exactamente n bits.
Codigos gamma.
Concatenacion de:
i) floor(log_2(x)) + 1 en unario
ii) x - 2 ^ ( floor(log_2(x)) ) en binario de floor(log_2(x)) bits
codigos delta.
Concatenacion de:
i) floor(log_2(x)) + 1 en gamma
ii) x - 2 ^ ( floor(log_2(x)) ) en binario de floor(log_2(x)) bits
Que indexar? Desarrolle los conceptos de parsing, case folding, stop words y stemming.
Parsing
El proceso de extracción de términos a partir de los documentos no es trivial, hay muchas consideraciones a hacer, en primer lugar hay que determinar cuales son los separadores que nos permiten separar los términos, espacios en blanco, puntuación etc. Hay que determinar que hacer con cosas del estilo ”Johnson-Johnson” que puede ser uno o dos términos, hay que decidir que hacer con los números. Por ejemplo no tendrı́a sentido indexar los números de página de un documento pero si cosas como 1984, en concreto si tenemos la frase ”2 de Marzo de 1984” tenemos el problema de que hacer con el número ”2”, si lo indexamos entonces vamos a indexar también números de página, números en tablas y todo tipo de ocurrencias del ”2” pero si lo ignoramos no vamos a poder recuperar la frase completa en caso de buscarla. Decisiones…
Case Folding
Una vez tokenizados los términos, proceso que hemos mencionado no es sencillo, hay varias decisiones de pre-procesamiento a tomar. Por ejemplo podemos llevar todos los términos a minúsculas para no tener que indexar ”Casa” y ”casa” como dos términos diferentes, esto nos puede llevar a que ”Azul” y ”azul” se consideren lo mismo cuando en realidad el primero puede ser un nombre de persona o de una ciudad.
Stop Words
Es posible también decidir eliminar de nuestro ı́ndice las denominadas stop words que son palabras muy frecuentes como ”a”, ”que” o en inglés ”is”, ”that”, ”the” ,etc. En algunas aplicaciones eliminar stop words es fundamental para el correcto funcionamiento del algoritmo mientras que en otras los stop words ayudan a que el algoritmo funcione mejor. Decisiones.
Stemming
Finalmente podemos decidir aplicar stemming que consiste en reducir a las palabras a su raı́z idiomática, aplicando stemming cosas como ”advertise” y ”adevertisement” se convierten en un mismo término. Hay varios algoritmos de stemming conocidos siendo el mas popular el algoritmo de Porter. Al igual que en el caso de los stop words algunas aplicaciones se ben beneficiadas por realizar stemming mientras que otras no.
Para que tipo de consultas sirven los indices invertidos, y donde hacen agua?
Nuestro II puede responder, hasta el momento, consultas puntuales de forma eficiente. Esto nos permite también resolver consultas booleanas de tipo ”t1 and t2” o cosas mas complejas como ”(t1 or t2) and (t3)”.
Un tipo de consulta importante y que no podemos resolver son las frases o consultas de proximidad como por ejemplo ”turismo en Parı́s” en donde queremos encontrar los documentos que tienen esa frase. Las frases son una generalización de las consultas por proximidad en donde queremos que los términos de nuestra consulta aparezcan en los documentos cercanos unos a otros, una frase es una consulta con proximidad igual a 1 es decir que cada término debe aparecer a continuación de otro.
Como se puede adaptar el II para aceptar consultas posicionales?
Agregando info posicional de las palabras en los docs.
Para mas detalle, ver apunte.
Que cuidado hay que tener al agregar info. posicional al II? Como se soluciona?
La información posicional hace que nuestro ı́ndice crezca en tamaño notablemente por lo que podrı́a ser conveniente usar códigos gamma o delta para las listas de punteros ya que el tamaño de las mismas podrı́a ser muy grande usando VBcodes.
