-
UNIVERSIDAD DE MAGALLANES FACULTAD DE INGENIERÍA
DEPTO. DE ING. EN COMPUTACIÓN
Implementación de ranking de documentos utilizando similaridad y NR-grep
José Carlos Alvarado Alvarado .
2004
-
La presente Memoria de Titulo ha sido aprobada con la siguiente calificación: José Carlos Alvarado Alvarado Memoria : Examen de Título : Nota Final :
Sr. Carlos Arias Méndez Director Departamento
De Ingeniería en Computación
Agosto de 2004
-
UNIVERSIDAD DE MAGALLANES FACULTAD DE INGENIERÍA
DEPTO. DE ING. EN COMPUTACIÓN
Implementación de ranking de documentos utilizando
similaridad y el NR-grep
Trabajo de titulación presentado en
Conformidad a los requisitos para
Obtener el titulo de Ingeniero en
Ejecución en Computación e
Informática
Profesor Guía: Sr. Mauricio Marín C.
José Carlos Alvarado Alvarado . 2004
-
i
Resumen
Conceptualmente, la Recuperación de Información (RI) es una operación en la que se
interpreta una necesidad de información de un usuario y se seleccionan los documentos más
relevantes capaces de solucionarla, es decir, consiste en buscar documentos que exhiban un
mayor parecido a la pregunta formulada [15]. En Recuperación para base de datos de texto,
existe una técnica llamada ranking de documentos, y su principal idea es que en una colección de
documentos se puedan listar en algún orden de relevancia, calculando y clasificando la
importancia de cada uno de éstos [1].
Por ello, uno de los objetivos generales de esta memoria es implementar un programa que
permita crear un ranking de documentos para mejorar la calidad de las respuestas de NR-grep, el
cual permite realizar búsquedas mediante expresiones regulares, simples y complejas[2]. NR-
grep no tiene la característica de presentar ningún tipo de ranking de documentos en el resultado
entregado al usuario, pues el resultado que entrega, es un listado de documentos en el orden en
que son encontrados.
La implementación contempla la utilización de dos estrategias para abordar el problema:
la primera consiste en utilizar una base de datos de texto distribuida no procesada, y como
complemento a ésta, una base de datos de texto distribuida procesada. En ambos casos el
objetivo es obtener el ranking que calcula la similaridad de documentos usando el modelo
vectorial. Durante el desarrollo del programa está previsto utilizar la biblioteca de
programación paralela BSP PUB, con el objetivo de aplicar el programa sobre N procesadores,
los que ejecutarán NR-grep en forma secuencial, creando de esta manera, una ejecución en
paralelo de NR-grep.
La base de datos de texto procesada y no procesada se diferencian en la creación de
archivos que son necesarios para la obtención del ranking de documentos, en el primer caso los
archivos son generados al comienzo, antes de la habilitar el programa de consultas, y en el
-
ii
segundo caso, los archivos se van generando a medida que el usuario realiza las consultas.
Además se visualizan las ventajas y desventajas de utilizar una u otra estrategia.
-
iii
Índice Resumen ..................................................................................................................I
Índice ..................................................................................................................... II
1 Capítulo I. Introducción...................................................................................1
1.1 Conceptos Generales ................................................................................1
1.2 Objetivos ....................................................................................................2
1.3 Organización del documento .....................................................................3
2 Capítulo II. Marco Teórico .............................................................................6
2.1 Computación Paralela ................................................................................6
2.2 Modelo BSP de Computacion Paralela ......................................................6
2.3 Herramientas a utilizar ...............................................................................8
3 Capítulo III. NR-grep Búsqueda en texto Flexible y Eficiente ....................10
3.1 NR-grep (Nondeterministic reverse grep) ................................................10
3.2 Clasificación de patrones..........................................................................10
4 Capítulo IV. Modelo RI y Estructura de datos .............................................16
4.1 Indice Invertido ........................................................................................17
4.2 Ranking de Documentos...........................................................................19
-
iv
4.2.1 Método del Vector .................................................................................19
4.2.2 Similaridad ...........................................................................................20
5 Capítulo V. Diseño e Implementación ........................................................23
5.1 Diseño.......................................................................................................23
5.2 Implementación ........................................................................................27
5.2.1 Estrategia de utilización base de datos de texto no procesada ..............28
5.2.1.1 Compilacion y ejecución ....................................................................31
5.2.1.2 Funcionamiento ..................................................................................31
5.2.2 Estrategia de utilización base de datos de texto procesada ....................32
5.2.2.1 Funcionamiento ..................................................................................32
5.3 Esquema de Consultas...............................................................................34
5.3.1 Cliente....................................................................................................34
5.3.2 Servidor .................................................................................................35
6 Capítulo VI. Pruebas y Evaluaciones ..........................................................39
7 Capítulo VII. Conclusiones ...........................................................................47
Bibliografía...........................................................................................................50
-
v
Índice de Figuras
1 Funcionamiento programa general BSP..........................................................7
2 Modelos de Recuperación de información....................................................16
3 Representación gráfica del producto coseno entre documentos d1 y d2 ......21
4 Ejemplo de raíz global propagada hacia los procesadores ..........................25
5 ABB global ....................................................................................................26
6 Esquema básico de consultas.........................................................................27
7 Estructura de directorios ...............................................................................28
8 Formulario de consultas ................................................................................35
9 Ejemplo de consulta utilizando la base de texto procesada.............................36
10 Ejemplo de consulta utilizando la base de texto no procesada .....................37
11 Ranking utilizando base de de datos texto no procesada opción l ................41
12 Ranking utilizando base de datos de texto procesada opción l .....................42
13 Ranking utilizando base de datos de texto procesada opción i .....................43
14 Ranking utilizando base de datos de texto no procesada opción i ................44
-
Capítulo I Introducción
-
1
1 Introducción 1.1 Conceptos generales
El concepto de expresiones regulares (regular expressions) se refiere a una familia de
lenguajes compactos y potentes para la descripción de caracteres. Las expresiones regulares
permiten evaluar o comparar la existencia de un patrón de búsqueda en una cadena o un valor
determinado, ésta comparación es conocida con el nombre de pattern matching o reconocimiento
de patrones. Muchos editores de texto y otras herramientas utilizan estos lenguajes para buscar
ciertas estructuras en el texto.
Por otra parte, la Recuperación de Información (RI) se puede definir como : Dada una
necesidad de información ( consulta + perfil del usuario + ... ) y un conjunto de documentos,
ordenar los documentos de más a menos relevante para esa necesidad y presentar un
subconjunto de los más relevantes. Para abordar éste problema, se pueden observar dos grandes
etapas, la primera es la elección de un modelo que permita calcular la relevancia de un
documento frente a una consulta, y la segunda es el diseño de algoritmos y estructuras de datos
que lo implementen. La primera etapa se mide comparando las respuestas del sistema contra las
que un conjunto de expertos consideran relevantes, y la segunda se mide considerando el tiempo
de respuesta del sistema, espacio extra de los índices, tiempo de construcción, etc [9].
Dentro de éste contexto se encuentra NR-grep, que permite realizar consultas mediante
expresiones regulares como un habitual programa de búsqueda en UNIX (grep, egrep, etc), y
como tal realiza la entrega de resultados en forma como aparecen los documentos en el árbol de
directorios; de ahí surge la necesidad de mejorar la entrega de los resultados realizando un
ranking de documentos, el cual se crea utilizando como función de comparación, la similaridad
entre documentos.
-
2
1.2 Objetivos
El propósito principal de este trabajo es mejorar la calidad de las respuestas que entrega NR-
grep, pues NR-grep, no posee la característica de presentar algún orden de relevancia en el listado
de archivos que entrega al usuario.
Los objetivos generales son :
Implementar una aplicación que permita mejorar la calidad de las respuestas de NR-grep.
Habilitar dicha aplicación para realizar un procesamiento de texto en forma paralela.
Dentro de los objetivos generales, se destacan los siguientes objetivos específicos:
Implementar el Modelo Vectorial para obtener un ranking de documentos.
Implementar una aplicación que permita la comunicación entre procesadores,
utilizando la biblioteca BSP PUB, con el fin de crear un ranking global utilizando
N procesadores.
Visualizar posibles ventajas y desventajas de utilizar la base de datos de texto
distribuida procesada versus la no procesada, en ambos casos se crearán
programas con estructuras de datos similares, como también la estructura de
archivos y directorios utilizados.
Crear una interfaz gráfica que permita al usuario interactuar con el sistema.
Para alcanzar los objetivos mencionados se seguirán los siguientes pasos:
-
3
1. Revisar el funcionamiento de NR-grep, para aplicarlo sobre las bases de datos de
texto.
2. Implementar un programa que permita trabajar con la base de datos de texto en forma
local, ya sea procesada como no-procesada.
3. Definir una estructura de datos para el almacenamiento de las respuestas en forma
global, utilizando los N procesadores.
4. Luego, se distribuirá la base de datos de texto e crearan programas que implementen
una programación paralela.
5. Comparar la calidad de respuestas obtenidas al aplicar los programas sobre la base de
datos de texto distribuida procesada y no procesada.
1.3 Organización del documento
El resto de éste documento se encuentra organizado de la siguiente manera:
Capítulo II. Marco Teórico: En este capítulo se describen algunos conceptos importantes con
respecto al sistema operativo y herramientas utilizadas en la implementación de los programas,
Linux, biblioteca PUB, entre otros.
Capítulo III. NR-grep Búsqueda en Texto Flexible y Eficiente: Aquí se describe a grandes
rasgos el software NR-grep.
Capítulo IV. Modelo RI y estructuras de datos: En este capítulo se presenta el modelo RI,
método y función de similaridad a utilizar.
Capítulo V. Diseño e implementación: Aquí se describe la lógica a utilizar para la
implementación del programa, además, se entrega una pequeña descripción acerca de los
archivos y la estructura de directorios utilizada.
-
4
Capítulo VI. Pruebas y evaluaciones: En este capítulo se entregan las comparaciones realizadas
entre las estrategias propuestas, también, se mencionan los posibles trabajos a futuro.
Capítulo VII. Conclusiones: Se mencionan las conclusiones que se obtuvieron una vez realizadas
las pruebas comparativas entre una y otra estrategia, junto a la salida de NR-grep.
-
Capítulo II Marco Teórico
-
6
2 Marco Teórico 2.1 Computación Paralela
El concepto de paralelismo se entiende como la incorporación de varios procesadores
comunicados entre sí, para resolver un problema computacional. De esta manera, el problema se
puede solucionar en menor tiempo de ejecución, pues la carga computacional se particiona entre
varios procesadores, obteniendo con esto una mejora en relación entre costo y rendimiento [11].
La computación paralela requiere de al menos tres componentes distintos. El primero es el
hardware paralelo para ejecutar aplicaciones paralelas. El segundo es una máquina abstracta o
modelo de programación en el cual se escriban aplicaciones en paralelo. El tercero es el software
que permita desarrollar las aplicaciones [10].
2.2 Modelo BSP de Computación Paralela
Es un estilo de programación paralela desarrollado para paralelismo de propósito general,
es decir, paralelismo a través de todas las áreas de aplicación y una amplia variedad de
arquitecturas [6].
Las propiedades fundamentales de BSP son:
Es independiente de la arquitectura, contrario a muchos sistemas de programación
paralela, BSP es diseñado para ser independiente de la arquitectura, de manera que los
programas se ejecuten sin necesidad de cambios cuando son llevados de una arquitectura
a otra, es decir, los programas en BSP son altamente portables.
El funcionamiento de un programa en determinada arquitectura es predecible, el tiempo
de ejecución de un programa en BSP puede ser computado por el código del programa y
por algunos parámetros relacionados con la arquitectura.
-
7
En el modelo BSP se distinguen dos aspectos fundamentales de computación paralela que
son: la comunicación y sincronización. En la figura 2.2.1 se puede observar el
funcionamiento de un programa general BSP, el cual procede en bloques de ejecución llamados
supersteps. Un superstep está compuesto de tres etapas:
• Computación local simultánea en cada proceso, usando sólo valores almacenados en
su memoria local.
• Comunicación entre los procesos, para llevar a cabo la transferencia de datos entre los
procesadores.
• Una barrera de sincronización con la cual se espera que se completen todas las
comunicaciones, es decir, todos los mensajes son enviados a su destino, y éstos se
encuentran disponibles al instante en que se inicia el siguiente superstep.
Figura 2.2.1 Funcionamiento de un programa general BSP.
-
8
Este modelo de programación paralela es aplicable a varias clases de arquitecturas
paralelas: memoria distribuida, memoria compartida y redes. Existe una biblioteca para el
desarrollo de algoritmos paralelos llamada BSP PUB, disponible en lenguajes de programación
tales como C, C++ y Fortran; para programar de una manera SPMD (Single Program Multiple
Data) [7].
El objetivo de la biblioteca BSP PUB es proveer la comunicación necesaria para
manipular partes de la estructura de datos que se encuentran en otros procesadores.
2.3 Herramientas a utilizar
Software de búsqueda mediante expresiones regulares NR-grep versión 1.1, el cual fue
utilizado para realizar las búsquedas mediante expresiones regulares, el código fuente
puede ser descargado en: http://www.dcc.uchile.cl/~gnavarro/software/nrgrep-1.1.tar.gz.
Lenguaje de programación:
C++, utilizado en la implementación del programa principal.
PHP, utilizado para creación de los formularios de consulta.
PERL, para la implementación del script para el filtraje de los documentos
de las base de datos de texto, cliente y servidor.
Biblioteca STL, para la utilización estructuras de datos.
Para la programación paralela se utilizó la biblioteca PUB (Paderborn University BSP).
4 equipos Pentium IV, con 128 MB de Ram, conectados en red (velocidad de 100Mbps) y
ejecutando Linux RedHat 7.3, la versión del kernel de Linux es 2.4.18-3.
-
Capítulo III NR-grep Búsqueda en Texto Flexible
y Eficiente
-
10
3 NR-grep: Búsqueda en Texto Flexible y Eficiente 3.1 NR-grep (Nondeterministic reverse grep)
NR-grep (nondeterministic reverse grep) es una herramienta diseñada para la búsqueda
eficiente de patrones complejos. Diferente de las herramientas anteriores de la familia del grep,
tales como agrep y grep de GNU, NR-grep se basa en un concepto único y uniforme: la
simulación bit-paralelo de un autómata sufijo no-determinístico.
NR-grep puede buscar de patrones simples a expresiones regulares, exactamente o
permitiendo errores en las búsquedas, con una eficacia que disminuye en forma leve mientras que
la complejidad del patrón buscado, aumenta. Otro concepto integrado completamente en NR-
grep y que contribuye esta disminución leve, es la selección de los subpatrones adecuados para la
exploración rápida.
NR-grep es una herramienta de búsqueda construida sobre el algoritmo BNDM (Backward
Nondeterministic Dawg Matching algorithm), BNDM esta basado en el algoritmo BDM
(Backward DAWG matching), éste algoritmo utiliza autómatas de sufijos para detectar substring
dentro del texto. Como el algoritmo Boyer-Moore, BDM también puede saltar caracteres
dentro de un texto. En el algoritmo BDM original, el autómata de sufijos es creado en forma
determinista, BNDM es una versión de BDM, éste mantiene el autómata de sufijos en forma no
determinista usando bit paralelo (bit-parallelism), por ello el nombre Nondeterministic Reverse
Grep, puesto que BNDM explora el texto en la dirección opuesta [2].
3.2 Clasificación de patrones
NR-grep clasifica los patrones permitidos de búsqueda en tres niveles:
-
11
• Patrones simples: un patrón simple es una secuencia de m clases de caracteres (notar que un
solo carácter es un caso particular de una clase). La característica que lo distingue es que una
ocurrencia de un patrón simple tiene longitud m, pues cada posición del patrón coincide con
una posición del texto.
Ejemplo : [Vv]acaciones , para las palabras Vacaciones y vacaciones.
199[0-9] , define los años 1990 al 1999.
• Patrones extendidos: un patrón extendido agrega a los patrones simples la capacidad de
caracterizar clases individuales opcionales o repetibles (pueden aparecer consecutivamente un
número de veces en el texto). El propósito de patrones extendidos es capturar lo más posible
las extensiones usadas comúnmente de los patrones normales en la búsqueda para desarrollar
los algoritmos especializados.
Ejemplo: [0-9]+\.?[0-9]*, expresión que indica números.
gatos? , para las palabras gato y gatos.
• Expresiones regulares: una expresión regular es formada por las clases simples, una
secuencia de caracteres nula o vacía, concatenación, unión o repetición de otras expresiones
regulares. Éste es el tipo más general de patrón que usa para la búsqueda.
Ejemplo: Roos(ve|Be)lt , puede ser la expresión Rossvelt o RossBelt.
(Sr.|Sra.|Srta.) Pérez , para indicar Sr. Pérez o Sra. Pérez o Srta. Pérez
En NR-grep se desarrollaron diversos algoritmos de búsqueda para cada tipo de patrón
(debido al aumento de la complejidad), de ésta manera patrones más simples se buscan con
algoritmos más simples y más rápidos.
NR-grep recibe en la línea de comando un patrón y una lista de los archivos a buscar, las
opciones que se inspiran la mayoría de ellas en el programa agrep son:
-
12
• i, la búsqueda es caso insensible ( mayúsculas y minúsculas );
• W, solamente las palabras enteras que concuerdan con el patrón se aceptan;
• x, solamente los líneas completas que concuerdan con el patrón;
• c: muestra el total de registros que se ajustan al patrón, pero no los muestra.
• l: imprime sólo los nombres de los archivos que contienen coincidencias;
• G: imprime el contenido entero de los archivos donde se encontraron coincidencias;
• h: solo muestra los registros que se ajustan al patrón, pero no individualiza por archivo;
• n: muestra un listado con todos los registros que calzaron con la búsqueda del patrón,
indicando el archivo al que pertenecen y el nro. de línea donde fue encontrado;
• v: muestra un listado con todos los registros que no se ajustaron a la búsqueda, indicando
el archivo al que pertenecen.
• L: toma el patrón literalmente (sin ningún carácter especial);
Hay opciones que no se pueden utilizar en forma conjunta, estas son:
-c y –G, -n y –l, y por último –l y –G.
A continuación se muestran algunos ejemplos de uso de NR-grep en un ambiente Linux.
Tomando el patrón tercera en forma literal y sobre el directorio
/soft/tercera/diario/1998/12/09/, la salida es: >> nrgrep –L tercera /soft/tercera/diario/1998/12/09/* más información sobre este tema [email protected]
-
13
Utilizando la búsqueda insensible a mayúsculas y minúsculas, con la expresión tUcApeL y
sobre el directorio /soft/tercera/casos/tucapel/datos/, la salida es la siguiente:
>>nrgrep –i tUcApeL /soft/tercera/casos/tucapel/datos/* /soft/tercera/casos/tucapel/datos/dato1.html: Caso Tucapel d valign="bottom" align="left" height="19"> > nrgrep –li (presidente|juez) /soft/tercera/casos/tucapel/datos/* /soft/tercera/casos/tucapel/datos/dato1.html /soft/tercera/casos/tucapel/datos/dato2.html /soft/tercera/casos/tucapel/datos/dato3.html.
Finalmente, las ventajas principales al realizar una comparación entre NR-grep y la familia
del programa grep son: la uniformidad en el diseño, bajos tiempos de búsqueda, rapidez en la
-
14
búsqueda de patrones complejos, patrones extendidos de gran alcance, el modelo mejorado del
error para buscar en forma aproximada, y la optimización de subpatrones.
NR-grep fue desarrollado completamente en ANSI C y probado sobre las plataformas Linux y
Solaris.
-
Capítulo IV Modelo RI y Estructura de Datos
-
16
4 Modelo RI y Estructura de Datos
El objetivo en la Recuperación de información es localizar información en grandes
colecciones de documentos, los usuarios de estos sistemas formulan consultas que expresan qué
contenidos desean localizar. Para ello es preciso que el sistema procese previamente la colección
de documentos a fin de construir estructuras de acceso (índices) que permitan una localización
rápida. Los buscadores en Internet son los sistemas de Recuperación de Información más
populares [9].
Una de las partes más importantes dentro de la Recuperación de Información es la respuesta o
los resultados obtenidos y en que orden se entregan. Los documentos son caracterizados por
palabras claves, algunas de éstas palabras pueden ser más importantes que otras, por lo que el
concepto de peso de una palabra clave se hace importante.
Figura 4.1 Modelos de Recuperación de Información.
Entre los modelos más populares de Recuperación de Información observados en la figura
4.1 se encuentra el Modelo Vectorial, por ser simple y eficiente de implementar, además de
-
17
entregar buenos resultados, por lo cual fue elegido como base para realizar el ranking de
documentos.
4.1 Índice Invertido
Los índices invertidos suelen estar compuestos por una lista invertida y un conjunto de
archivos en donde se almacena la información con respecto a los archivos que componen la base
de datos de texto [7].
Los archivos se desglosan de la siguiente manera:
• Documentos.txt, almacena todos los nombres de documentos que componen la base
de datos de texto.
• Vocabulario.txt, contiene las palabras relevantes de la colección, con un
identificador de cada palabra y las frecuencias con que aparecen en los documentos.
• Listas Invertidas.txt, este archivo almacena una lista de pares (documento,
frecuencias) por cada palabra de vocabulario.txt. Se considera la frecuencia de una
palabra en un documento, a la cantidad de veces que aparece la palabra en un
documento, por ejemplo, si una palabra con identificador de palabra 20 se encuentra
en los documentos con identificadores 70, 256 y 300, entonces en el archivo aparece la
línea, .... 20,70,0.3,256,0.1,300,0.6 ...., en cuanto a frecuencia normalizada ésta
considera la cantidad de veces que aparece la palabra en el documento y la cantidad de
veces de la palabra mas relevante del documento, formando el cuociente
Frec(palabra) / Frec(palabra más relevante). En forma general, Frec(t,i) es la
frecuencia normalizada de la palabra relevante t en el documento i, sea Fmx(i) el
número de veces en que aparece la palabra relevante más frecuente en el documento i,
y sea F(t,i) el número de veces en que la palabra relevante t aparece en el documento
i. Entonces la frecuencia normalizada esta dada por,
Frec(t,i) = F(t,i) / Fmx(i) 4.1
-
18
A continuación, se muestra un ejemplo de los archivos, vocabulario y lista invertida.
Archivos : DOCUMENTO 1, DOCUMENTO 2 y DOCUMENTO 3.
hola mundo hola chao casa arbol casa mundo chao Hola mundo
Donde, el archivo Documentos.txt posee el nombre e identificador del archivo. Documentos.txt
0 DOCUMENTO 1 1 DOCUMENTO 2 2 DOCUMENTO 3
El archivo Vocabulario.txt es :
Vocabulario.txt arbol,0,1 casa,1,1 chao,2,2 hola,3,2 mundo,4,1
, lo que significa que la palabra arbol tiene el identificador de palabras 0, y aparece en el
archivo con identificador de archivos 1. Finalmente, Listas Invertidas.txt :
Listas Invertidas.txt 0, 3,0.500 1, 3,1.000 2, 1,0.333, 2,0.500 3, 1,0.333, 2,1.000 4, 1,1.00
, donde la palabra con identificador 0 se encuentra en el archivo con identificador 3 y posee una
frecuencia normalizada de 0.500.
-
19
4.2 Ranking de Documentos.
Al realizar las consultas sobre el índice invertido, cada palabra que sea parte de la consulta
genera un conjunto de documentos, donde sus URL’s deben ser presentadas en orden de ranking
( los más relevantes, i.e. mayor ranking primero) al usuario.
Para construir el ranking de documentos, se utiliza el método del vector, que se explica a
continuación.
4.2.1 Método del Vector
La descripción del modelo vectorial o también llamado método del Vector es la siguiente:
• Se selecciona un conjunto de palabras útiles para discriminar términos (vocabulario).
• En los sistemas modernos, toda palabra del texto o documento se considera un término,
excepto por las stopwords.
• Sea {t1,...,tk} el conjunto de términos y {d1,...,dN} el de documentos.
• Un documento se modeliza como un vector
→ di → di = ( w( t1 , di ),...w( tk , di ) ) 4.2
; donde w(t,i) es el peso del término tk en el documento di.
• Hay varias formulas para calcular los pesos de los términos, pero la que se utilizará es:
W(t,i) = log N Frec(t,i) 4.3
( D(t)
) *
donde t = documento, i = palabra, Frec(t,i) es la Frecuencia Normalizada, N el número
total de documentos existentes, y D(t) es la cantidad de documentos en donde aparece la
palabra t.
-
20
Luego el ranking R(i,Q) de un documento i frente una consulta Q formada por n palabras
t esta dado por,
R(i,Q) = ∑ {∀ t ∈ Q }[ W(t,i) ] 4.4 El siguiente es un ejemplo del ranking de documentos frente a una consulta realizada
utilizando los archivos de la figura 4.2 :
Para la consulta chao y los documentos encontrados son DOCUMENTO 1 y DOCUMENTO
2, cuyos ranking’s son 0.0880 y 0.0586. Por lo tanto, el ranking de documentos queda
encabezado por el Documento1, el cual posee una mayor relevancia.
Consulta : chao ; R(DOCUMENTO 1) = 0.0880, R(DOCUMENTO 2) = 0.0586;
Ranking de documentos : DOCUMENTO 1
DOCUMENTO 2
4.2.2 Similaridad
Otro concepto importante es la similaridad entre documentos, que es el grado de
igualdad o semejanza entre documentos.
Una de las funciones de similaridad más utilizada es la distancia coseno o producto punto
entre dos vectores (representación vectorial del documento). En la figura 4.2.1 se
representa gráficamente el producto coseno entre el documento d1 que contiene información
acerca de La crisis de los misiles y el documento d2 que contiene información acerca de Los
misiles en Cuba.
-
21
Figura 4.2.1 Representación gráfica del producto coseno entre documentos d1 y d2.
La similaridad entre documentos se efectúa entre las representaciones vectoriales de cada
documento. Dos documentos iguales tienen similaridad 1, y ortogonales (si no comparten
términos) tienen similaridad cero.
-
Capítulo V Diseño e Implementación
-
23
5 Diseño e Implementación En el presente capítulo se muestra el diseño, lógica e implementación de las estructuras que
se utilizan para la construcción del índice y posterior obtención del ranking de documentos.
5.1 Diseño
NR-grep se aplica en forma secuencial sobre una base de datos de texto local, por lo que en el
diseño se debía tener presente que NR-grep se aplicará en forma paralela, obteniendo de esta
manera un NR-grep distribuido.
Como NR-grep es aplicado en forma secuencial sobre cada procesador se obtendría N
listados (siendo N la cantidad de procesadores a utilizar) al aplicarlo en forma paralela, N
listados que posteriormente serían utilizados para crear el ranking de documentos utilizando la
función de similaridad entre documentos.
Para utilizar la similaridad como función de comparación entre los documentos, se creó un
índice invertido, ya que se debe tener una representación vectorial (vector de palabras relevantes
con sus respectivos pesos) de los documentos para obtener el producto coseno. Este índice se
creará con unas pequeñas variaciones en cuanto a los archivos que se utilizan en su
implementación, como también en la secuencia de almacenamiento de la información. Esto,
debido a que se debe tener en cuenta que en un primer momento se trabaja con la base de datos
de texto no procesada y luego con la procesada.
La base de datos de texto procesada y no procesada se diferencian en la creación de archivos
que son necesarios para la obtención del ranking de documentos, en el primer caso los archivos
son generados al comienzo, antes de la habilitar el programa de consultas, y en el segundo caso,
los archivos se van generando a medida que el usuario realiza las consultas.
-
24
Durante la implementación se utilizó la estructura de Árbol Binario de Búsqueda (ABB) para
el almacenamiento del ranking de documentos, cada nodo del ABB está definido por una clase
llamada NodoDTV, la cual encapsula la información relevante de un documento junto con el
procesador al que pertenece. Los atributos que posee esta clase son:
Nombre del documento. Distancia. Procesador al que pertenece. Identificador del documento. Cantidad de veces que aparece la palabra más relevante.Inicio y fin en frecuencias.dat.
Además, se encuentran los punteros a los objetos NodoDTV y otras variables utilizadas.
Se debe tener en cuenta que cada procesador crea su propio ranking (ABB) con la
información local. Desde luego, el ABB principal es creado por el primer procesador que posea la
información necesaria; una vez construido el ABB, se propaga la raíz hacia los demás
procesadores. Con ello se crean los ABB locales, cada uno con su propia información pero con la
raíz global, para luego agregar los nodos de los ABB locales al ABB global.
La lógica para la construcción del ABB es la siguiente:
1. Ubicación de la raíz global
El procesador que obtenga datos para formar el ABB local es quien entrega la raíz
global, el recorrido de los procesadores se realiza en forma secuencial, es decir,
comienza el procesador 1 hasta donde se encuentre una raíz, de lo contrario no existe
raíz global lo que indica que no hay documentos que satisfagan la consulta.
-
25
El procesador que tenga la raíz, la comunica hacia los demás procesadores utilizando
las propiedades de la biblioteca PUB, en la figura 5.1.1 se puede observar en forma
gráfica la propagación de la raíz utilizando cuatro procesadores.
Figura 5.1.1 Ejemplo de raíz global propagada hacia los ABB locales de cada procesador.
2. Inserción de nodos.
Para la inserción del nodo en el ABB local se toma el resultado del producto punto
que en general es la distancia coseno entre dos documentos.
Para la inserción de los nodos en el árbol global, se utiliza el atributo distancia del
nodo a insertar.
En ambos casos una distancia mayor significaba que los documentos eran bastante
similares, y en el caso contrario significaba que los documentos eran distintos.
La figura 5.1.2 muestra una representación particular de ABB global construido a
partir de los ABB locales de la figura 5.1.1, ya que el orden de los nodos es obtenido una
vez realizada la similaridad entre los documentos.
-
26
Figura 5.1.2 ABB global.
Para tener una mejor perspectiva y desarrollo del proyecto, éste se dividió en tres etapas,
las dos primeras, consistieron en crear los archivos y programas necesarios para realizar las
consultas sobre la base de datos de texto no procesada y procesada. La tercera etapa consiste en
crear una aplicación gráfica para que el usuario interactúe con el sistema.
En ambos casos, se utilizó la base de datos de texto de la Tercera la cual fue descargada
en el directorio /soft/tercera/, ubicado en cada uno de los procesadores utilizados, ya que de
acuerdo al Modelo BSP cada procesador debe tener la misma estructura de directorios, junto a los
archivos y ejecutables necesarios para que el programa principal se ejecute.
La figura 5.1.3 muestra un esquema básico del proceso de consulta, en él se encuentran
los 4 procesadores, cada uno almacena parte de la base de datos de texto distribuida, el Servidor
que esta escuchando peticiones de consulta y el formulario de consultas.
El proceso comienza cuando el usuario realiza la consulta en el formulario, los datos de la
consulta son enviados al Servidor que está a la espera de peticiones, el que además ejecuta el
programa en paralelo con los datos de la consulta. A partir de ello, cada procesador crea su ABB
con los datos locales, y posteriormente se crea el ABB global que almacena el ranking de
documentos que son enviados como respuesta al usuario.
-
27
Figura 5.1.3 Esquema básico de consultas.
5.2 Implementación Durante el desarrollo del proyecto se crearon directorios similares para abordar cada una de
las estrategias a utilizar, para luego realizar las comparaciones respectivas junto a la salida de
NR-grep. Recordar que ambas estrategias se diferencian en los archivos de almacenamiento
de datos.
Ambos directorios denominados Base Procesada y Base No Procesada, se describen a
continuación y cuyo esquema se observa en la figura 5.2.1.
-
28
Figura 5.2.1 Estructura de directorios.
5.2.1 Estrategia de utilización base de datos de texto no procesada
Bajo éste directorio se encuentran los archivos Makefile y bsprueba.cc, además de los
subdirectorios Frecuencias y Estructuras. A continuación se entrega una explicación de
cada archivo y al final se dará una breve reseña del funcionamiento.
Frecuencias: En éste directorio se almacenan los archivos utilizados para crear el índice
invertido, los cuales son:
• Historial.txt: Almacena los nombres de archivos procesados, su formato es :
( id_doc, pal_rel, beg, end, nombre_doc ), y donde:
id_doc : identificador numérico del documento.
pal_rel : cantidad de veces de que aparece la palabra más relevante.
beg: bytes de inicio en archivo frecuencias.dat
end: bytes de fin en archivo frecuencias.dat.
nombre_doc : nombre del documento.
Ejemplo: 1,17,0,2484,/soft/tercera/casos/matute/documentos/informe1.html
2,19,2484,4669,/soft/tercera/casos/matute/documentos/informe2.html
-
29
3,12,4669,5212,/soft/tercera/casos/matute/noticias/archivo.html
4,105,5212,7773,/soft/tercera/casos/matute/noticias/archivo1.html
....
• Words.txt: Es el vocabulario de los archivos procesados, su formato es:
( identificador_numérico_palabra, palabra).
• Frecuencias.dat: Archivo binario encargado de almacenar el id de la palabra junto a
su frecuencia, cuyo formato es: ( nombre_doc, id_pal1, frec1, id_pal2, frec2 . . . id_docn, nombre_docn id_palm, frecm )
n : total de documentos, m: total palabras en el documento.
• Blip.pm: Es una biblioteca definida PERL, definida para almacenar las palabras
irrelevantes y funciones para el manejo de datos.
• Filtro: Script PERL, que se encarga de obtener las palabras relevantes de cada
documento, ignorando las palabras irrelevantes (preposiciones, conjunciones,
artículos, etc.) y etiquetas que forman parte del documento HTML, También se
encarga de crear los archivos frecuencias.dat, historial.txt y words.txt, teniendo
en cuenta que en esta etapa cada vez que se realiza una consulta algunos documentos
ya se encuentran procesados y otros no, por lo que los datos relevantes del documento
nuevo van siendo agregados a los archivos correspondientes, para evitar el reingreso
de datos, como también recalcular las frecuencias ya obtenidas.
Estructuras: Dentro de este directorio se almacenan las estructuras y funciones que fueron
definidas para el manejo de datos.
• estructuras.h: Dentro del archivo se define la clase NodoDTV, que es la que
modeliza un documento como objeto, almacenando los datos importantes de un
-
30
documento, tal como procesador al que pertenece, veces de la palabra mas relevante,
nombre del documento, etc.
• funciones.cc: Se definen las funciones utilizadas para el manejo del archivo
frecuencias.dat del cuál se obtiene el vector que representa el documento, es decir, el
mapa que representa el documento. También se encuentran las funciones que permiten
calcular la similaridad entre documentos mediante la distancia coseno, o más
comúnmente llamada producto punto. Esta operación consiste en obtener el producto
entre dos mapas, siendo el índice del mapa el identificador de cada palabra y su
contenido, la frecuencia normalizada de la palabra. Por otra parte, se encuentran las
funciones que permiten insertar los nodos al ABB. Esta función se encuentra
sobrecargada, debido a que se debe realizar una inserción local, y además la inserción
al ABB global, ya que en el primer caso la inserción se hace obteniendo el producto
punto entre los documentos, y en el segundo caso, sólo se compara la distancia a la
raíz. Además, se encuentra la función encargada de liberar la memoria utilizada.
-
31
5.2.1.1 Compilación y ejecución Dentro del archivo Makefile se encuentran las reglas de compilación para los archivos que
forman parte del proyecto, además de las reglas para creación y copia remota de directorios y
archivos.
La ejecución se realiza mediante la opción run del programa pubd con la siguiente
instrucción:
pubd -e ssh -p N -n IP –run = "ruta del ejecutable lista de parámetros";
( N: número de computadores a utilizar, IP: números IP de cada computador)
donde se levanta el programa residente (daemon) y se ejecuta el programa.
5.2.1.2 Funcionamiento
En esta etapa la estrategia consiste en analizar los documentos a medida que se realizan
las consultas, es decir, al realizar una consulta, el parámetro ruta se revisa con el fin de encontrar
todos los archivos mencionados, una vez que se obtienen los archivos se coteja con el archivo
historial.txt, donde se encuentran los archivos procesados hasta ese instante. En caso de no
encontrarse dentro del listado, el archivo es revisado y se almacenan las palabras relevantes y
frecuencias, en el archivo words.txt y frecuencias.dat, y en caso de encontrarse procesado se
sigue la ejecución normal.
Luego, se realiza la parte común a las dos estrategias, la que consiste en la creación del
ABB en cada procesador, en donde cada uno utiliza sus propios datos teniendo en cuenta que la
raíz es entregada por el primer procesador que pueda crear su ABB, comenzando el recorrido por
el procesador principal (procesador 0, identificador con el cual distingue a los diferentes
procesadores PUB) y luego en caso de no existir raíz, continúa con procesador 1, procesador 2, ...
, procesador n, donde n es el número total de procesadores. Al no existir raíz, significa que no
hay respuesta para la consulta.
-
32
De existir respuesta, se comienza insertar los nodos de los ABB locales de cada
procesador al ABB global del procesador que proporcionó la raíz global, transformándolo de esta
manera en un ABB global.
Finalmente, se recorre el ABB en inorden, tomando en primer lugar la raíz, y luego se
entrega a la función que realiza el recorrido el subárbol izquierdo y posteriormente el subárbol
derecho, con lo cual se obtiene ranking de documentos completo. Como ejemplo, se tiene el
ABB global de la figura 5.2 cuyo recorrido es: D1, C, A, D, B, F.
5.2.2 Estrategia de utilización base de datos de texto procesada
Bajo éste directorio se encuentran los archivos Makefile y bsprueba.cc, además de los
subdirectorios Frecuencias y Estructuras. Los subdirectorios y archivos que lo componen son
los mismos que posee la estrategia de utilización de base de datos de texto no procesada.
En esta etapa el filtro se realiza al comienzo, donde se examinan todos los documentos de
la base de datos de texto, de esta manera, el archivo frecuencias.dat, words.txt e
historialt.txt son creados al principio y contienen toda la información relevante de los
documentos que forman parte de la base de datos de texto. La compilación y ejecución es
similar al de la estrategia de utilización base de datos de texto no procesada.
5.2.2.1 Funcionamiento
En esta etapa la estrategia consiste en analizar los documentos al comienzo antes de habilitar
el proceso de consultas, es decir, se procesan todos los archivos que componen la base de datos
de texto. Esto significa, ejecutar el script encargado de obtener los archivos de control para
la obtención del ranking de documentos.
-
33
Luego, se realiza la parte común a las dos estrategias, la que consiste en la creación del ABB
local en cada procesador, en donde cada uno utiliza para ello sus propios datos y teniendo en
cuenta que la raíz es entregada por el primer procesador que pueda crear su ABB local,
comenzando el recorrido por el procesador principal (procesador 0, identificador que utiliza PUB
para identificar cada procesador) y luego en caso de no existir raíz continúa con procesador 1,
procesador 2, ... , procesador n, donde n es el número total de procesadores.
Cuando no existe raíz, significa que no hay respuesta para la consulta, de lo contrario se
comienza a insertar los nodos de los árboles locales de cada procesador al ABB global del
procesador que tiene la raíz global, transformándolo de esta manera en un ABB global.
Finalmente, se recorre el ABB en inorden, tomando en primer lugar la raíz, y luego se
entrega a la función que realiza el recorrido el subárbol izquierdo y posteriormente el subárbol
derecho, con lo cual se obtiene ranking de documentos completo. Como ejemplo, se tiene el
ABB global de la figura 5.2 cuyo recorrido es: D1, C, A, D, B, F.
-
34
5.3 Esquema de Consultas
La etapa final del proyecto consistió en dejar disponible el buscador desarrollado
mediante un esquema cliente-servidor utilizando socket. Para crear el Cliente y Servidor se
utilizó el Lenguaje PERL, debido a la gran facilidad que entrega éste para construir este tipo de
aplicaciones, para ello sólo se debe incluir el modulo IO::Socket que entrega las subrutinas para
el manejo de los sockets. Tanto el servidor como el formulario de consultas fueron creados en el
procesador principal.
5.3.1 Cliente
Mediante un formulario se obtienen los datos que el usuario entrega para realizar la
consulta, datos previamente revisados y formateados, los cuales son enviados al servidor
mediante el uso de socket.
Una vez enviados los datos el cliente espera la respuesta del Servidor, luego, retira del
socket el mensaje donde viene una lista de archivos en orden de relevancia , y los cuales que
forman la respuesta encontrada en la base de datos de texto distribuida, posteriormente forma un
documento HTML creando un enlace a cada documento que es parte de la respuesta, que es
finalmente mostrado al usuario.
El usuario ejecuta al cliente desde un formulario HTML mediante el esquema cgi-bin,
cuyo formulario de consulta se puede observar en la figura 5.3.1.1
-
35
Figura 5.3.1.1 Formulario de consultas.
Las opciones del formulario de consulta (figura 5.3.1.1) son las siguientes:
Base de datos de texto:
• Procesada
• No Procesada
Opción :
• Insensible MAY/MIN
• Literal
• Solo nombres de archivos.
5.3.2 Servidor
El servidor toma los parámetros que forman la consulta del último mensaje recibido en el
socket y ejecuta el programa BSP, donde cualquiera de los procesadores le entregara el resultado
mediante la copia remota del archivo resultante.
-
36
Una vez que se obtiene el conjunto de documentos ordenados por ranking, el servidor crea
el mensaje donde se encuentran las URLs que se entregarán como respuesta al usuario,
posteriormente el mensaje es puesto en un socket.
La figura 5.3.1.2 muestra el resultado de la consulta pino(c|chet) sobre la base de datos de
texto procesada, utilizando la opción Insensible MAY/MIN y sobre el directorio
/soft/tercera/diario/2001/01/10/extras/*.*. En ella se puede apreciar el listado de archivos en
orden de relevancia.
Figura 5.3.1.2 Ejemplo de consulta utilizando la base de texto procesada.
-
37
En la figura 5.3.1.3 se puede observar un segundo ejemplo de consulta, esta vez utilizando
la base de datos de texto no procesada, expresión (matute|lagos) y sobre el directorio
/soft/tercera/diario/*.*.
Figura 5.3.1.3 Ejemplo de consulta utilizando base de texto no procesada.
-
Capítulo VI Pruebas y evaluaciones
-
39
6 Pruebas y Evaluaciones
Las pruebas se realizaron utilizando 4 equipos Pentium IV, con 128 MB de Ram, conectados
en red (velocidad de 100Mbps) y ejecutando Linux RedHat 7.3, la versión del kernel de Linux es
2.4.18-3.
Al comienzo las pruebas se realizaban en forma local, utilizando solamente el procesador
principal obteniendo (en algunos casos utilizando los procesadores virtuales) resultados similares
a los que se encontrarían mas adelante utilizando los procesadores en paralelo. Una vez
implementados los programas en paralelo utilizando la biblioteca BSP PUB, se continuó con la
etapa de pruebas y evaluaciones, comparando los listados ordenados por relevancia al utilizar una
u otra estrategia.
Al momento de realizar las comparaciones se debía tener presente que el primer archivo que
entregaba NR-grep, es tomado como raíz, ya sea para construir el ABB local, como para el ABB
global. De esta manera, los listados tendrían una raíz común, pero, los listados son creados de
manera diferente, pues NR-grep tiene la característica de no presentar ningún orden de relevancia
en sus listados, ya que los archivos son mostrados en el orden en que son encontrados dentro del
árbol de directorios. A diferencia de las estrategias, que forman sus listados de archivos a través
de un ranking de documentos.
En primer lugar, se abordó la primera estrategia utilizando los 4 procesadores disponibles,
obviamente se podían utilizar más procesadores, pero por disponibilidad de computadores solo se
utilizaron 4. En teoría, los listados ordenados por relevancia debían presentar aproximaciones a
los que entregaba la segunda estrategia, pues a utilizar la formula 4.2.12, los valores se
incrementan a medida que se realizan consultas (donde se procesen nuevos documentos), pues el
valor N (cantidad de documentos procesados) de la formula:
-
40
W(t,i) = log N Frec(t,i)
( D(t)
) *
era 0 en la primera consulta, lo que significaba que no se habían procesado documentos. Desde
luego, se debían realizar bastantes consultas para ir obteniendo un incremento deseable del valor
N. De este modo, se tendría una mejor aproximación al cálculo total de la base de datos de
texto.
Posteriormente se realizaron las pruebas de la segunda estrategia, que consistía en utilizar
la base de datos de texto procesada. Los resultados, como se esperaban fueron muy diferentes al
compararlos con los resultados que entregaba la primera estrategia utilizada. Obviamente, esto se
debía a que ya se tenía procesada la base de datos de texto, lo que permite tener valores más
precisos ya que se tiene el cálculo total de la base de datos de texto. Esto se vio reflejado al
momento de realizar las comparaciones con los listados de archivos que entregaba la primera
estrategia, pues el orden de los archivos era solo aproximado. De igual modo, las comparaciones
realizadas entre las estrategias y el listado entregado por NR-grep, se realizaron comparando el
orden de los archivos. Ambas estrategias presentaban listados diferentes al presentado por NR-
grep, debido a que los listados se creaban calculando la relevancia de los documentos y NR-grep
solo los lista de acuerdo al orden en que son encontrados.
En cuanto al tiempo de respuesta, se debe tener en cuenta que al utilizar la segunda
estrategia el proceso de filtraje y creación de los archivos necesarios para crear el ranking de
documentos se realiza al comienzo, proceso que es mucho más veloz en comparación a la
segunda estrategia, pues en ésta cada documento que no ha sido procesado pasa por única vez por
el proceso de filtraje (obtención de palabras relevantes y frecuencias normalizadas) al momento
que se realiza la consulta, haciendo que el proceso sea lento, hecho que queda demostrado
cuando la respuesta de NR-grep tiene muchos documentos que no han sido procesados.
-
41
A continuación se muestran algunos resultados del ranking de documentos obtenidos
utilizando ambas estrategias y la salida entregada por NR-grep.
En las figuras 6.1 y 6.2, se pude notar las diferencias que existen en el orden de los
listados de documentos entregados por ambas estrategias, al realizar la consulta con la expresión
.e[^a-zA-Z_]n# , opción l (solo nombres de archivo) y sobre el directorio
/soft/tercera/casos/prats/documentos/fallo/. La expresión busca cualquier carácter en la primera
posición, luego el carácter "e", posteriormente cualquier carácter excepto una letra o una raya un
la tercera posición, luego "n", y finaliza con un separador. Ejemplo : be1nx, donde x representa
un tabulador.
A medida que se realizaban nuevas consultas, los resultados no variaban en forma
drástica, debido a que la primera estrategia (base de datos de texto procesada) trabaja con el
cálculo total de la base de datos de texto. De acuerdo a ello se puede mencionar que, utilizando
la base de datos de texto procesada (figura 6.2) se obtiene un mejor ranking de documentos en
comparación con el resultado de la estrategia que utiliza la base de datos de texto no procesada
(figura 6.1).
Figura 6.1 Ranking utilizando base de datos de texto no procesada opción l.
-
42
Ambas estrategias obtienen un mejor ranking de documentos al realizar la comparación
con el listado que entrega NR-grep, pues NR-grep proporciona un listado sin ningún tipo
relevancia de documentos, ya que los muestra en forma que son encontrados dentro del árbol de
directorios. El listado de archivos que entrega NR-grep es el siguiente:
/soft/tercera/casos/prats/documentos/fallo/fallo00.html
/soft/tercera/casos/prats/documentos/fallo/fallo01.html
/soft/tercera/casos/prats/documentos/fallo/fallo02.html
/soft/tercera/casos/prats/documentos/fallo/fallo03.html
/soft/tercera/casos/prats/documentos/fallo/fallo04.html
/soft/tercera/casos/prats/documentos/fallo/fallo05.html
/soft/tercera/casos/prats/documentos/fallo/fallo06.html
/soft/tercera/casos/prats/documentos/fallo/fallo07.html
/soft/tercera/casos/prats/documentos/fallo/fallo08.html
/soft/tercera/casos/prats/documentos/fallo/fallo09.html
/soft/tercera/casos/prats/documentos/fallo/fallo10.html
/soft/tercera/casos/prats/documentos/fallo/fallo11.html
/soft/tercera/casos/prats/documentos/fallo/fallo12.html
/soft/tercera/casos/prats/documentos/fallo/fallo13.html
/soft/tercera/casos/prats/documentos/fallo/fallo14.html
/soft/tercera/casos/prats/documentos/fallo/fallo15.html
Figura. 6.2 Ranking utilizando base de datos de texto procesada opción l.
-
43
.
Otra muestra comparativa es la presentada por las figuras 6.3, 6.4. En ellas se observa el
ranking de documentos al utilizar la base de datos de texto procesada y no procesada, la
expresión buscada es ministro, opción i (insensible mayúsculas y minúsculas) y sobre el
directorio /soft/tercera/diario/2001/01/10/extras, en ellas se aprecia las diferencias en el orden
del listado de documentos encontrados.
/soft/tercera/diario/2001/01/10/extras/t-10.07.3a.EXT.INSULZA.html /soft/tercera/diario/2001/01/10/extras/t-10.09.3a.EXT.VELASCO.html /soft/tercera/diario/2001/01/10/extras/t-10.11.3a.EXT.FERNANDEZ.html /soft/tercera/diario/2001/01/10/extras/t-10.17.3a.EXT.MATUTE.html /soft/tercera/diario/2001/01/10/extras/t-10.18.3a.EXT.LAGOS.html /soft/tercera/diario/2001/01/10/extras/t-10.21.3a.EXT.VALDOVINOS.html /soft/tercera/diario/2001/01/10/extras/t-10.07.3a.EXT.INSULZA.html /soft/tercera/diario/2001/01/10/extras/t-10.09.3a.EXT.VELASCO.html /soft/tercera/diario/2001/01/10/extras/t-10.11.3a.EXT.FERNANDEZ.html /soft/tercera/diario/2001/01/10/extras/t-10.17.3a.EXT.MATUTE.html
Por su parte la lista de archivos anterior, muestra el resultado al realizar la misma consulta
pero esa vez utilizando NR-grep, esta salida como se ha dicho anteriormente, muestra el orden
que poseen los archivos dentro del árbol de directorios buscado.
Figura. 6.3 Ranking utilizando base de datos de texto procesada opción i.
-
44
Figura. 6.4 Ranking utilizando base de datos de texto no procesada opción i
.
Algunos de los trabajos por realizar a futuro son:
Utilizar algoritmos de Lematización, recordar que lematización es el proceso mediante el
cual se buscan variaciones morfológicas de los términos, con el objetivo de extraer la raíz
común a ellos. El objetivo de la lematización en la recuperación de información es
reducir el número de términos en el índice semánticamente similares, por ejemplo se
tienen las siguientes palabras:
generalizaciones
generalizando
generalizar
generalizas
raíz artificial es la palabra gener , luego los documentos a los que pertenecen las
palabras anteriores quedan apuntando a una raíz en común.
-
45
Ello permite reducir el espacio de almacenamiento y aumenta la velocidad del proceso
de búsqueda.
Habilitar las opciones de NR-grep que no fueron utilizadas.
-
Capítulo VII Conclusiones
-
47
7 Conclusiones
El objetivo principal de la memoria consistía en resolver el problema presentado por NR-
grep, en cuanto a la calidad del ranking de documentos entregado como respuesta al usuario. La
lista de archivos entregado por NR-grep, contiene el orden en que son encontrados en el árbol de
directorios.
Para ello se creó el ranking de documentos basándose en el Modelo Vectorial. El ranking
debía ser realizado en forma paralela utilizando la base de datos de texto distribuida mediante el
uso de la biblioteca BSP PUB, con ello se logró aplicar en forma secuencial y a la vez en
paralelo, a NR-grep. Secuencial, porque se aplica en cada procesador en forma local, y paralelo,
debido a que el programa se ejecuta a la vez en todos los procesadores. De éste modo NR-grep
es aplicado en forma distribuida para obtener un ranking de documentos.
Las evaluaciones normalmente se basan en la relevancia de los documentos encontrados, cosa
que ha representado un problema, pues medir la relevancia es un proceso subjetivo y de poca
confianza. Las comparaciones realizadas fueron básicamente comparaciones basadas en el
orden de los archivos listados, entregados por una y otra estrategia, además, de comparar los
listados de documentos que entregaba NR-grep al realizar la misma consulta.
Al utilizar la base de texto procesada, los listados eran obtenidos basándose en el cálculo
completo de la base de datos de texto. Ello permitía obtener una mejor calidad de respuestas al
compararlo con la estrategia que utiliza la base de datos de texto no procesada. En Teoría, éste
ranking debe ser de mejor calidad, pues la estrategia que utiliza la base de datos de texto no
procesada solo crea el ranking con valores aproximados. De este modo, al procesar un nuevo
documento, la estrategia va obteniendo una mejor aproximación al cálculo total de la base de
datos de texto, y con ello al ranking presentado por la estrategia que utiliza la base de datos de
texto procesada. También, basándose en la teoría, ambas estrategias obtienen un mejor ranking
-
48
de documentos que el listado presentado por NR-grep, pues comparar el orden en el que son
encontrados los archivos difiere bastante con los que entrega ranking de documentos.
Una ventaja que posee la estrategia que utiliza la base de datos de texto no procesada es la
actualización de la base de datos de texto, ya que permite ingresar nuevos documentos sin tener
que modificar los archivos básicos en forma drástica, pues sólo los ingresa como nuevos valores,
a diferencia de la de la estrategia que utiliza la base de datos de texto procesada, ya que en esta se
deben procesar todos los documentos, incluyendo los nuevos, para obtener un cálculo completo
basado en la base de datos de texto.
Esto también deja abierta la posibilidad de que la base de datos de texto no procesada pueda
captar documentos que no pertenezcan a la base de datos de texto propia, pues la búsqueda se
realiza según el directorio que el usuario estime conveniente. Con esto, se opta a una mayor
cantidad de documentos para realizar el ranking, ya que los valores de los documentos son
ingresados en los archivos correspondientes para realizar el ranking de documentos. Pero esto
a su vez es una desventaja, pues si se procesan documentos que no pertenecen a la base de datos
de texto propia, el universo de documentos aumenta y de esta manera el ranking de documentos
va teniendo una menor precisión.
Por su parte, la estrategia que utiliza la base de datos de texto procesada obtuvo un ranking de
documentos muy diferentes al compararlos con la otra estrategia y al listado que entregaba NR-
grep por supuesto, se debía a que en ésta estrategia se tiene la ventaja de trabajar con la base de
datos de texto procesada, lo cual entrega un cálculo completo de la base de datos de texto, y
además, agiliza el proceso de respuesta. De acuerdo a ello, se puede mencionar que al utilizar esta
estrategia, se obtiene un mejor ranking de documentos porque ésta utiliza el cálculo total de la
base de datos de texto, mientras que con la segunda estrategia, solo se tiene una aproximación al
cálculo total. Además, al realizar las consultas, resulta una respuesta mucho más rápida a
diferencia de la primera estrategia, pues el proceso de filtraje y obtención de los archivos
necesarios para crear el ranking se realiza antes de habilitar el proceso de consultas.
-
Bibliografía
-
50
Bibliografía [ 1 ] Baeza-yates R. y Ribeiro-Nieto, Modern Information Retrieval, Adisson- Wesley, 2000.
[ 2 ] Gonzalo Navarro, NR-grep: a Fast and Flexible Pattern Matching Tool, Software Practice
and Experience (SPE), Wiley, 2001.
[ 3 ] WWW. Algoritmos de relevancia de respuestas para la recuperación de información,
Manuel Elizalde Vieyra, http://fismat.umich.mx/~anta/, 2000.
[ 4 ] WWW. Sistemas Integrales en Internet, Informática y Administración,
http://www.pmulti.com/, 2002.
[ 5 ] WWW. BSP PUB Library at Paderborn University, http://www.uni-paderborn.de/bsp
[ 6 ] WWW. BSP and Worldwide Standard, http://www.bsp-worldwide.org
[ 7 ] WWW. User Guide and Function Reference, http://www.uni-paderborn.de/~pub, 2002.
[ 8 ] WWW. Introducción a BSP, http://kataix.umag.cl/~mmarin, 2002.
[ 9 ] WWW. Recuperación de la información: Algoritmos Estructuras de datos y Búsqueda en
la Web, Gonzalo Navarro y Ricardo Baeza-Yates, http://kataix.umag.cl/~mmarin, 2003.
[ 10 ] WWW. Designing and Building Parallel Programs, Addison-Wesley,
http://wotug.kent.ac.uk/parallel/books/addison-wesley/.
http://www.pmulti.com/http://www.uni-paderborn.de/~pubhttp://kataix.umag.cl/~mmarinhttp://kataix.umag.cl/~mmarin
-
51
[ 11 ] WWW. Parallel simulation and optimization of silicon clusters, David Santo Orcero,
España, http://www.orcero.org/irbis,2002.
[ 12 ] WWW. Red Hat Linux, http://www.redhat.es/.
[ 13 ] WWW. The PERL directory, http://www.perl.org.
[ 14 ] WWW. Standard Template Library Programmer’s Guide, http://www.sgi.com/tech/stl.
[ 15 ] WWW. Mecanismos de Recuperación de información en la WWW, Adelaida M.Delgado
Domínguez, dmi.uib.es/people/adelaida/.
http://www.redhat.es/http://www.perl.org/http://www.sgi.com/tech/stl