Todas las obras de Shakespeare que contengan las palabras: "Brutus" y "Cesar" pero no la palabra "Calpurnia".
Una forma de solucionar este problema es hacer una búsqueda exhaustiva de todos los documentos, seleccionar primero aquellos que tienen las palabras "Brutus" y "Cesar" y luego eliminar de la lista los que también tienen la palabra "Calpurnia". Con el comando grep de Linux se puede hacer en pocos pasos, pero: ¿es esta una buena solución?
La respuesta es no, y estos son los motivos:
- Muy lento para grandes colecciones
- La condición "NO Calpurnia" no es trivial
- No puedo realizar consultas más complejas como por ejemplo: buscar la palabra "Romanos" cerca de "compatriotas"
- No puedo armar un ranking de los documentos devueltos indicando cuales se ajustan más a la consulta.
Una forma de resolver esto es utilizando matrices de incidencia de términos:
En esta matriz ponemos como filas todos los términos relevantes y como columnas los documentos, luego si el término aparece en el documento ponemos un "1" en la celda correspondiente y sino un "0"
| Términos | Antony and Cleopatra | Julius Caesar | The Tempest | Hamlet | Othello | Macbeth |
|---|---|---|---|---|---|---|
| Antony | 1 | 1 | 0 | 0 | 0 | 1 |
| Brutus | 1 | 1 | 0 | 1 | 0 | 0 |
| Caesar | 1 | 1 | 0 | 1 | 1 | 1 |
| Calpurnia | 0 | 1 | 0 | 0 | 0 | 0 |
| Cleopatra | 1 | 0 | 0 | 0 | 0 | 0 |
| mercy | 1 | 0 | 1 | 1 | 1 | 1 |
Una vez que tengo armada una matriz de este tipo puedo obtener rápidamente los documentos para cualquier búsqueda similar a la anterior.
La consulta se resuelve como una serie de operaciones booleanas:
Brutus: 110100 AND (Obtengo el vector correspondiente al término)
Cesar: 110111 AND
Calpurnia: 101111 (Obtengo el vector correspondiente negado)
---------------------------
100100
La respuesta es: "Antony and Cleopatra" y "Hamlet"
¿Funciona esta solución con grandes colecciones de datos?, that's the question
Imaginemos que tenemos una colección mediana: N= 1 millón de documentos, donde cada documento tiene en promedio 1000 palabras distintas.
En promedio una palabra ocupa: 6 bytes, incluyendo espacios y signos de puntuación.
Eso quiere decir que tenemos unos 6 Gb de información en documentos y supongamos que la cantidad de términos distintos entre todos los documentos es de 500 mil, es decir ese es el tamaño de nuestro vocabulario.
Una matriz de 1000000 documentos x 500000 términos tiene un total de 500000000000 ceros y unos. (500 mil millones)
Lo cual es mucho espacio, si cada uno o cero ocupa un bit (pongamos por caso), la matriz sola ocuparía: 62500000000 bytes, es decir: 62 Gb ¡10 veces más que los documentos!
Sin embargo si meditamos un poco sobre la forma de esta matriz nos damos cuenta de que tendría muy pocos unos y casi todos ceros. ¿Por qué? porque cada documento en promedio tiene tan solo mil términos. Así que en principio la cantidad de unos sería un número similar a 1000000 documentos x 1000 términos existentes en un documento: mil millones. La conclusión lógica de esto es: solo guardar la posición de los unos. Eso lo veremos en el próximo post.
Te felicito por este excelente artículo sobre la recuperacion de informacion. Un saludo!
ResponderEliminar