PDF de programación - Resumen Tema 3: Búsqueda

Resumen Tema 3: Búsqueda

José Alberto Benítez Andrades

Enero 2011

En este trabajo se resumen las conclusiones obtenidas después de haber realizado la lectura de los
artículos propuestos de Steve Lawrence y C. Lee Giles, Searching the World Wide Web, Nick Craswell,
David Hawking y Stephen Robertson, Eective Site Finding using Link Anchor Inofrmation y Dunja
Mladenic, Text-Learning and Related Intelligent Agents: A survey.

1. Características propias de la web que afectan a la búsqueda.

En primer lugar, debemos destacar que Internet, y concretamente la web, es una fuente de infor-
mación joven, distribuida, de carácter dinámica, y que crece de una manera muy rápida. Para poder
obtener y recuperar la información, no podemos mirar atrás y utilizar las tecnologías antiguas, debido
a que, fueron creadas en su momento, para poder indexar colecciones de documentos estáticos, no
dinámicos, directamente accesibles.

La web posee una naturaleza que hace cuestionarse si la arquitectura que poseen los buscadores,
centralizada, puede mantener la cantidad tan grande de documentos que hay actualmente en la red, y
sobre todo, si son capaces de actualizar sus bases de datos, de forma que, detecten la información que
es modicada, borrada o insertada. Las respuestas a estas preguntas impactan en la mejor metodología
de búsqueda a seguir y en el futuro de la tecnología de búsqueda en Internet. Los buscadores poseen
una cobertura bastante limitada, ya que, ningún buscador llega a indexar una tercera parte del total
de las páginas que existen realmente en Internet.

Existen muchos problemas que afectan a los buscadores a la hora de poder convertirse en motores

de búsqueda potentes, caben destacar los siguientes puntos principalmente:

Gran número de webs que existen actualmente en Internet: Hace 10 años, había un número
bastante elevado de webs en todo Internet, pero en la época actual, ese número se ha elevado de
manera exponencial. Hay demasiada información, de la cual, una parte de ella, es además SPAM,
y no interesa en los buscadores porque no proporciona la información que necesita el usuario.

Crecimiento continuo de las webs: A diario, crece el número de páginas web que crean distintos
tipos de personas. Ya sean, webs particulares, de negocios, blogs de opinión, etcétera. Siempre
se recomienda que mediante distintas herramientas, se introduzcan las webs en distintos motores
de búsqueda de forma manual, para facilitar el trabajo a estos. No obstante, muchas personas
desconocen este tipo de herramientas.

Velocidades de los rastreadores que se utilizan, junto con el hardware necesario para poder
ejecutar las diferentes herramientas necesarias para indexar las webs.

1

Duplicidad de contenido web: Cuesta bastante tiempo, descargar las páginas, comprobar si es
contenido duplicado, y posteriormente borrarlo, pensando en que además de esa acción, se deben
insertar URLs nuevas, y cambiar algunas que ya estaban, porque se han modicado.

2. Tipos de información a considerar en la búsqueda en web:

2.1. Contenido Textual.

La manera más común de expresar y comunicar la información o el conocimiento sobre alguna
materia en la red, es mediante el texto. El texto, puede codicarse en bits de dos formas principalmente:

EBCDIC y ASCII, al principio con 7 bits y posteriormente 8

Unicode: Posee 16 bits y se utiliza para acomodar los lenguajes orientales.

Los sistemas de recuperación de información, deben recuperar la información en varios formatos debido
a que, no existe un formato único, sino que existen varios formatos de texto. Hace años, se convertían
los documentos necesarios, pero en la actualidad se utilizan una serie de ltros para evitar estas
conversiones. Algunos de los formatos que se utilizan en los documentos son: formato para intercambio
de documento (RTF), formato para mostrar (PDF, PostScript), formato para codicación de correo
(MIME), cheros comprimidos, uuencode/uudecode, binhex. La cantidad de información tiene una
relación con la distribución de símbolos en el documento.

La entropía, en la teoría de la información, es una magnitud que mide la información provista por

una fuente de datos, es decir, lo que nos aporta sobre un dato o hecho concreto.

Por ejemplo, si nos dicen que todos los comercios están cerrados, en un domingo, no nos aporta
nada nuevo porque ya sabemos que los domingos se descansa, sin embargo, si nos dicen un día entre
semana, que los comercios están cerrados, signica que nos encontramos en un día festivo.

La medida de la entropía puede aplicarse a fuentes de información de cualquier naturaleza, y nos
permite codicarla adecuadamente, indicándonos los elementos de código necesarios para transmitirla,
eliminando toda redundancia. (Para indicar el resultado de una carrera de caballos basta con trans-
mitir el código asociado al caballo ganador, no hace falta contar que es una carrera de caballos ni su
desarrollo).

La entropía nos indica el límite teórico para la compresión de datos.
Su cálculo se realiza mediante la siguiente fórmula:

H =m

i=1pilog2pi

donde H es la entropía, las p son las probabilidades de que aparezcan los diferentes códigos y m el
número total de códigos. Si nos referimos a un sistema, las p se reeren a las probabilidades de que se
encuentre en un determinado estado y m el número total de posibles estados.

Se utiliza habitualmente el logaritmo en base 2, y entonces la entropía se mide en bits.
Por ejemplo: El lanzamiento de una moneda al aire para ver si sale cara o cruz (dos estados con

probabilidad 0,5) tiene una entropía:

H = 1

2log2

1

0,5 + 1

2log2

1
0,5 = (0, 5 + 0, 5) log22 = 1bit

2

A partir de esta denición básica se pueden denir otras entropías.
Modelado del lenguaje natural: Los símbolos son los encargados de separar a las palabras o son
parte de ellas, no poseen una distribución uniforme, se trata de un modelo binomial y dependen de los
símbolos previos, el modelo Markov de orden K. Las palabras pueden ser tomadas por símbolos.

La llamada Ley de Zipf, formulada en la década de los cuarenta por el lingüista de Harvard George
Kingsley Zipf, es una ley empírica según la cual, por ejemplo, en una lengua la frecuencia de aparición
de las distintas palabras sigue una distribución que puede aproximarse por

P n ∼ 1/na

donde Pn representa la frecuencia de una palabra ordenada n-ésima y el exponente es próximo a 1.
Esto signica que el segundo elemento se repetirá aproximadamente con una frecuencia de 1/2 de la
del primero, y el tercer elemento con una frecuencia de 1/3 y así sucesivamente. Una ley no empírica,
pero más precisa, derivada de los trabajos de Claude Shannon fue descubierta por Benoît Mandelbrot.
De manera similar a la ley de Zipf, existe otra ley empírica que describe el comportamiento de los
términos dentro de un texto escrito denominada ley de Heaps. En esta ley, se plantea una relación
entre el tamaño del texto (cantidad de palabras) y el crecimiento del vocabulario (cantidad de palabra
únicas). En particular, postula que el tamaño del vocabulario (y su crecimiento) es una función del
tamaño del texto.

V = Knβ

donde:
N: Es el tamaño del documento (cantidad de palabras)
K: Constante que depende del texto, típicamente entre 10 y 100.
β: También es una constante que depende del texto, donde 0 <>

10 <= K <= 20

0.5 <= β <= 0.6

Por lo tanto, si K = 20 y beta = 0.5, resulta:

N

10000
25000
40000
80000
100000

V

6325
10000
12649
17889
20000

Nótese que el tamaño del corpus creció 10 veces, mientras que el vocabulario apenas superó las 3

veces su tamaño inicial.

Los resultados de la ley de Heaps plantean que a medida que se incorporan documentos a una

colección, cada vez se descubrirán nuevos términos para el vocabulario.

Su aplicación es directa ya que permite estimar el tamaño del vocabulario con lo cual se puede
determinar  por ejemplo  la escalabilidad de las estructuras de datos necesarias para almacenar los
índices que soportan el SRI. Esto es altamente útil si se utilizará una tabla de hash en memoria para
el índice.

3

2.2.

Información en los enlaces (link anchor information).

Un hipervínculo, según el documento Eective Site Finding using Link Anchor Information, se
trata de una relación entre dos documentos o dos partes del mismo documento. El documento ori-
gen es el que contiene el enlace. En una web, el documento fuente contendría un texto como: < a
href=http://www.indipro.es> INDIPRO Site </a>

Llamaremos documento objetivo a aquel al que se reere el enlace, es decir, a http://www.indipro.es.
Los métodos que utilizan el ranking basado en hipervínculos se dividen principalmente en tres tipos:

1. La suposición por recomendación : Al vincular un objetivo, un autor de la página es reco-
mendado. Acorde con esto, una página es más recomendable, cuanto más alto es el grado que
tiene y debe estar mejor clasicada. Esto se puede basar en un conteo de enlaces simples o en
el cálculo de un peso por la propagación de la página iterativa. Un estudio reciente encontró
que los métodos de recomendación de enlaces hacen un buen trabajo recolectando objetos muy
interesantes, dicho por expertos. Los jueces de calidad son muy necesarios para establecer las re-
comendaciones. Sin embargo, hay muchos criterios de evaluación de enlaces, para unos usuarios
pueden ser unos enlaces mejores que otros.

2. La suposición de localización de tema : las páginas conectadas por enlaces tienen más
probabilidad de ser del mismo que tema que las que no lo están. Distintos estudios del año 2000
encontraron que esto era cierto. Usando estos métodos, una página que está enlazada a páginas
relevantes, puede ser rankeada de mejor manera.

3. La suposición de descripción de anclaje : El texto de anclaje de un enlace describe su objetivo.
Usando el enlace mencionado anteriormente, el texto de anclaje INDIPRO Site está describiendo
http://www.indipro.es/. Este método produce que se indexe por la descripción de anclaje, el
enlace de dest