Comenzando con un nuevo post para el blog sobre lo que es indexado, ya saben, eso que hace google de modo inconmensurable al internet.

Me gustaría darles algunos conceptos básicos demás pero como siempre me ha gustado ir al grano, les recomiendo que si quieren entender esto más a fondo busquen por "Lógica booleana" y "Grep"

Técnica de matrices de incidencia

Las matrices de incidencia son tablas las cuales relacionan un documento con una palabra, y cada celda toma el valor de un cero o un uno, con esto sabemos si una palabra se encuentra presente en el archivo y nos permite realizar la consulta de lógica booleana con una mayor velocidad.

Por ejemplo, si buscáramos los documentos que contienen la palabra "Empleado", debemos acceder a la columna de la palabra y devolver cada documento que la contiene (primer columna de la izquierda), en este caso cada 'celda' donde encontremos un uno. Para este ejemplo sólo devolvería el documento "Contrato de trabajador.txt".

Algunos ya se habrán dado cuenta, otros van a asentir ahora que lo lean, y es que este modelo de indexado de documentos es que para cada palabra que no existe dentro del documento, se emplea un entero en memoria y produce un mal gaste de la memoria. Entonces ¿qué hacemos?

Índices Invertidos

En esta técnica, se tiene que decir en qué documento se encuentra cada término, para ello se define un diccionario el cual contiene todas las palabras encontradas dentro de cada documento y cada palabra tiene asociada una lista donde están almacenadas las referencias de cada documento donde haya aparecido esta palabra. A cada referencia de documento donde se haya dicha palabra se le llama posting, y a al arreglo/lista donde están todos los documentos enlistados se le llama postings.

Veámoslo usando la misma tabla anterior:

Como se puede apreciar en la tabla anterior, ahora con solo acceder a la fila "Empleado", ya sabemos que este está en el documento "Contrato de trabajador.txt" y del mismo modo con la palabra "Nombre" sabemos que aparece en todos los documentos.

Metodología para Indexar Documentos

Para llevar a cabo la indexación de documentos, se llevan a cabo los siguientes pasos:

• En primer lugar tenemos que agrupar los documentos que procesaremos con el algoritmo.
• Tokenizar el texto de los documentos, preprocesar el contenido.
• Normalizar los resultados arrojados, como por ejemplo, si nos llegamos a encontrar la palabra ‘amigos’, almacenarla como ‘amigo’, con esto evitaremos tener que almacenar elementos con el mismo lemma.
• Indexar. Hacer el diccionario de listas. Para este paso, se extraen todas las palabras de cada documento.
  • Si la palabra aún no se encuentra dentro del diccionario, se añade como llave de nuestra tabla hash y como valor se le asigna una lista de un elemento que es el archivo donde se encontró.
  • Si la palabra ya se encuentra dentro del diccionario, se toma el documento donde se encontró y este es aprendizado a la lista de dicha palabra. Así hasta haber recorrido todos los documentos.
• Para hacer una consulta donde aparezca una palabra, lo único que se debe hacer es acceder al diccionario (tabla hash) y traer de vuelta la lista (postings), con ello sabremos que en esos documentos se contiene la petición. Si se desean manejar consultas de dos o más elementos se debe de traer todos los postings de cada palabra y aplicarles un poco de teoría de conjuntos, ya sea intersección (and), union (or), resta, or exclusivo, etc. según se desee.

Python: Indexado de documentos locales

Aquí les presento un pequeño script que indexa los documentos en formato ".txt" recorriendo un árbol de direcciones a partir de donde se ejecuta el script (o de una raíz dada), extrayendo todos los nombres de los ficheros en una lista que se emplea dentro del ciclo que indexa estos documentos para conseguir el diccionario. Al finalizar, se pide al usuario introducir una consulta, si la consulta tiene una longitud de un elemento entonces se imprimen los postings, si tiene una longitud mayor, se procesan todos los postings de los elementos con un poco de lógica de conjuntos... aajah... aajah... el algoritmo de la sección anterior con otras palabras. AL GRANO! DAME EL CÓDIGO!

# -*- coding: utf-8 -*-
import os
from os.path import isfile, join
import string

RAIZ = './'
EXTENSION = ".txt"

###############################################
# Escaneamos el árbol de ficheros y guardamos #
# en una lista los ficheros con extensión txt #
###############################################
archivos_txt = []
for base, dirs, files in os.walk(RAIZ):
	for file in files:
		fich = join(base, file)
		if fich.endswith(EXTENSION):
			archivos_txt.append(fich)


# {palabra : documento}
diccionario = {}



#########################################
#      Llenamos el diccionario          #
#########################################
for arch in archivos_txt:

	t = open(arch).read().lower()
	t = t.translate(string.maketrans("",""), string.punctuation) # 'Quitar' puntuación

	pals = t.split()
	for p in pals:
		if not p in diccionario:
			diccionario[p] = set()
		diccionario[p].add(arch)



#############################
#      Hacer Consultas      #
#############################
while True:
	op = raw_input("\nIntroduce tu búsqueda:\n>>> ")
	op = op.translate(string.maketrans("",""), string.punctuation)

	busq = op.split()

	# Para un solo elemento
	if len(busq) == 1:
		# op = lemma(op.decode('utf-8'))

		if op in diccionario:
			for res in diccionario[op]:
				print res
			print
			print ">>> Resultados:" , len(diccionario[op]), "<<<\n"
		else:
			print ">>> No hubo resultados para esta búsqueda <<<\n"

	# Más de un elemento
	elif len(busq) > 1:
		tipo = raw_input("\nQué tipo de búsqueda desea realizar:\n" + 
						"A) AND\n" + 
						"B) OR\n" + 
						"C) RESTA\n" + 
						">>> ").lower()

		conjb = []
		for i in xrange(len(busq)):
			r = set() if busq[i] not in diccionario else diccionario[busq[i]]
			conjb.append(r)

		resultado = conjb[0]

		for i in range(1, len(busq)):
			if tipo == 'a':
				resultado = resultado & conjb[i]
			elif tipo == 'b':
				resultado = resultado | conjb[i]
			elif tipo == 'c':
				resultado = resultado - conjb[i]


		# Mostramos los resultados
		for res in resultado:
			print res
		print
		print ">>> Resultados:" , len(resultado), "<<<\n"

	print "Presionar 'ctrl' + 'c' para salir del programa"

En este código se pueden apreciar algunas cosas. Las operaciones booleanas las he realizado usando conjuntos de Python (Set) y he aprovechado las funciones nativas del lenguaje para realizar el And, Or y Resta (Or exclusivo). Se puede apreciar esto que les digo en las líneas 71 al 74, 80, 82 y 84 del código.

Tarea: Saquen el lemma de las palabras para evitar tener diferentes entradas en las llaves como "árbol" y "árboles". Puedes usar una librería como NLTK o Clips Pattern para que sea más fácil

¿Qué tan buenos son los documentos devueltos?

Algo extra que me gustaría decir es que para medir la efectividad de los resultados devueltos por la consulta hay dos maneras de medir la efectividad de un buscador:

• Precisión: Fracción de los documentos recibidos que tienen información relevante al usuario.
• Recall: Fracción de los documentos relevantes en la colección que son devueltos.

Las dos mediciones no suelen ser muy efectivas en cierto modo, así que podemos usar una más equilibrada que media entre ambas soluciones anteriores:

Dudas / Comentarios

Si tienes alguna duda o comentario, escríbelo aquí o mandame un tweet a @JordyCRPetrucci y te ayudaré con gusto.

• ← Previous Post
• Next Post →