Categoría: Internet

Picasa es un programa para organizar fotos realmente revolucionario. ¡Impresionante! Yo consideraría Picasa como una futura Killer App, ya veremos lo que pasa. Por ahora solo hay versión para Windows, pero el programa está en manos de la gente de Google así que no creo que tarden en salir versiones para otras plataformas.

Picasa indexa todas las fotos/imágenes del disco duro y las organiza. Después puedes utilizar un buscador para encontrar las fotos en cuestión de milisegundos. Yo tengo ahora mismo 20.000 fotos en el disco duro, escribo «Hong Kong» lo más rápido que puedo y aparecen INMEDIATAMENTE todas las fotos que tengo de Hong Kong en forma de thumbnails. Increíble pero cierto. Es como tener un Google imágenes en tu disco duro. Google sigue revolucionando el mundo de la informática, esperemos que no bajen el ritmo.

Se ve que la salida a bolsa se les ha subido a la cabeza 🙂

Gmail falla.

Dos minutos después usando Google me sucede algo parecido.

Tenemos millones de ordenadores y dispositivos interconectados en Internet. Pero solo utilizamos este sistema para comunicarnos e intercambiar información. Imaginad que todas estas máquinas pueden decidir en cierto momento trabajar como una única máquina superpotente, compartiendo potencia de cálculo y memoria. No es Matrix, es lo que en el futuro se denominará El Grid.

Actualmente hay varios proyectos (Búsqueda de vida extraterrestre, búsqueda de números primos, romper claves) que utiilizan la potencia de muchos ordenadores de forma rudimentaria. Estos proyectos dividen los datos a tratar en pequeños trozos y los reparten a los usuarios que lo deseen. Una vez el usuario a analizado el trozo de información lo devuelve a los servidores de la organización que se encargan de verificar el análisis.

Ahora imaginad que podéis compartir vuestro procesador cuando no lo utilicéis, y automáticamente pasa a formar parte de un superordenador que utiliza tu ordenador cuando es necesario. Imaginadlo a la inversa, necesitáis mucha potencia de cálculo para resolver cierta tarea (Renderizar una escena 3D por ejemplo), lanzáis el proceso y éste se encargaría de buscar procesadores compartidos por Internet y en cuestión de segundos la tarea habría terminado (Suponemos que cuando Grid funcione, Internet será muy muy rápida 🙂 ).

Todo esto puede sonar a ciencia ficción o profecía pero hay miles de personas que trabajan para hacer este sueño realidad. Actualmente hay muchos «MiniGrids» funcionando en redes locales controladas por científicos, pero aun queda mucho para convertir Internet en un Grid gigantesco.

Uno de los laboratorios donde más avanzada está la investigación es en el Cern (Laboratorio Europeo), donde hace 15 años se creó la WWW gracias a Tim Berners Lee. Esperemos que el Cern nos vuelva a sorprender con algo revolucionario, que se adelanten a los americanos y que cambien nuestras vidas tal y como ha hecho la World Wide Web.

Llegamos al último capítulo de la serie donde vamos a explicar los fundamentos de ordenación de resultados de una búsqueda basándonos en el cálculo del Pagerank de Google.

En el capítulo 3 aprendimos como los resultados de una búsqueda se ordenan según su importancia usando una serie de algoritmos. Pero estos algoritmos son totalmente autómaticos y simplemente se basan en la correspondencia del texto de las páginas con la búsqueda que estamos realizando. Para poder obtener una ordenación mejor debemos introducir componentes más «subjetivos», como por ejemplo el número de enlaces que apunta a determinada página web. Cuantos más enlaces hacia nuestra página mayor será nuestra puntuación (Con ciertas restricciones importantes que veremos a continuación).

Veamos la fórmula básica (No os asustéis que es muy sencillita) con la que se calcula la puntuación (PageRank) de una página web:

• -PR(A) significa que vamos a calcular el PageRank de la web A.
• -T1, T2, T3 … Tn son las páginas web que tienen un link hacia la página web A.
• -d es una constante que suele vale 0.85
• -C(T1), C(T2), C(T3) … C(Tn) son el número de links al exterior de las webs T1,T2,T3 etc…

Vemos que la fórmula tiene en cuenta el PageRank que cada página que nos apunta, además, cuantos más enlaces al exterior tiene la página que nos apunta menor es la puntuación que nos da. Teóricamente la fórmula calcula la probabilidad de que un usuario llegue a tu página navegando haciendo clicks aleatoriamente, cuantos más enlaces hacia tu página más probable es que llegue un navegante despistado. Pero será aún más probable si hay enlaces a tu página desde una web famosa con mucho PageRank. Para verlo más claro vamos a utilizar un ejemplo, imaginaros las siguientes webs:

-Página Web A (PageRank = ¿?¿?)
-Página Web T1 (PageRank = 5):
   -Link hacia A.
   -Link a slashdot
   -Link a barrapunto
   -Link a la nasa
-Página Web T2 (PageRank=3):
   -Link hacia A
   -Link a google

Deseamos conocer el valor del PageRank de la Web A y ver si nos beneficia más la Web T1 o la Web T2. Procedemos a aplicar la fórmula:

PageRank(A)=(1-0.85) + 0.85*(PageRank(T1)/C(T1)) + 0.85*(PageRank(T2)/C(T2))

Nos valta saber C(T1) y C(T2) que simplemente se calculan sumando el número de links al exterior de ambas páginas, C(T1)=4 y C(T2)=2.

PageRank(A)=(1-0.85) + 0.85*(5/4) + 0.85*(3/2)

PageRank(A)=(1-0.85) + 1 + 1.275

Observad que la página T2 con PageRank 3 nos beneficia algo más que T1 con PageRank 5 porque no tiene tantos links al exterior. Si terminamos de operar obtenemos nuestra puntuación final:

PageRank(A)=2.425=2(Redondeando hacia abajo)

Ya sabemos calcular el PageRank a mano (Algo bastante inútil, aquí te lo calculan automáticamente), pero ¿Qué conclusión práctica podemos sacar de la fórmula? Veámoslo con un par de ejemplos prácticos:

– Si tenemos una web con PageRank 2 y nos enlazan 20 nuevas páginas con PageRank 1 seguramente sigamos con PageRank 2, pero si hay una web que nos enlaza con PageRank 6 seguro que subiremos a PageRank 3. Cuanto mayor sea el PageRank de la web que nos enlaza mayor es la puntuación que nos da.

-Si tenemos una web con PageRank 2 y nos enlaza una web con PageRank 3 que tiene enlaces a otras 5000 webs seguramente sigamos con PageRank 2, pero si la misma web solo tiene nuestro enlace seguro que subiremos a PageRank 3. Cuanto menos enlaces al exterior tenga la web que nos enlaza mayor es la puntuación que nos da.

Hoy en día el algoritmo para calcular el PageRank es mucho más complicado que el explicado y tiene en cuenta muchas más variables para dar puntuaciones lo más fiables posibles. Pero la base sigue siendo parecida a la fórmula de este artículo. ¿Cómo mejoraríais la fórmula del PageRank? ¿Qué factores creéis que son importantes a la hora de evaluar una web de forma automática?

Más información en los papers orginales escritos por los creadores de Google en The Anatomy of a large-scale hypertextual Web search engine y The PageRank citation ranking: Bringing order to the Web.

Y para los que han llegado hasta aquí leyendo todos estos artículos un regalito: una foto de Sergey de juerga en la universidad, uno de los creadores del fenómemo Google haciendo el gilipichis 😉

En el Capítulo 1 aprendíamos las diferencias entre los diversos tipos de buscadores. En el Capítulo 2 aprendíamos como se pueden buscar cosas de forma muy rápida cuando tenemos mucha información. En este capítulo vamos ver el último paso de funcionamiento de un buscador, no por ello menos importante. Se trata de la ordenación de los resultados de una búsqueda. Para esta tarea existen cientos de algoritmos y métodos de los cuales vamos a ver una pequeña introducción intuitiva. Según la eficacia de estos métodos el usuario obtendrá una satisfacción mayor o menor. ¿Os molesta que el Google no encuentre lo que buscáis? ¿Os molesta encontrar el mejor resultado en la segunda página?

El primer método que nos viene a todos a la cabeza es el de poner antes las páginas web donde más veces aparezca la palabra que buscamos. Supongamos que buscamos «Albert Einstein», aplicamos los métodos descritos en el Capítulo 2, y solo exisen 3 páginas en Internet que contienen alguna de las dos palabras:

-Página web 1: » Albert Einstein murió en 1955. Uno de los mayores logros de Einstein fue la formulación de la teoría de la relatividad.»

-Página web 2: » Albert es un niño muy juguetón. Siempre está dando la tabarra. Pero Albert también tiene una mente brillante con la que podría rivalizar con el mismísimo Einstein. Puede que algún día Albert nos sorprenda. Albert tiene una gran imaginación. Podríamos educarlo para que llegue a ser un genio que gane el premio Nobel.»

-Página web 3: «Uno de los grandes fallos reconocidos de Einstein fue la introducción de la constante cosmológica. Aunque últimamente se está viendo que Albert Einstein no estaba tan equivocado. Albert era nunca aceptó plenamente las teorías de la mecánica cuántica.»

Si aplicamos el método de contar las palabras clave y poner antes las páginas web en las que más aparezcan las palabras buscadas obtendríamos la siguiente ordenación:

-PRIMERA POSICIÓN (Las Palabras Albert y Einstein aparecen 5 veces): » Albert es un niño muy juguetón. Siempre está dando la tabarra. Pero Albert también tiene una mente brillante con la que podría rivalizar con el mismísimo Einstein. Puede que algún día Albert nos sorprenda. Albert tiene una gran imaginación. Podríamos educarlo para que llegue a ser un genio que gane el premio Nobel.»

-SEGUNDA POSICIÓN (Las Palabras Albert y Einstein aparecen 4 veces):»Uno de los grandes fallos reconocidos de Einstein fue la introducción de la constante cosmológica. Aunque últimamente se está viendo que Albert Einstein no estaba tan equivocado. Albert era nunca aceptó plenamente las teorías de la mecánica cuántica.»

-TERCERA POSICIÓN (Las Palabras Albert y Einstein aparecen 3 veces): «Albert Einstein murió en 1955. Uno de los mayores logros de Einstein fue la formulación de la teoría de la relatividad.»

Fijaros que si el Google nos diera este resultado no estaríamos muy satisfechos con la primera página obtenida ya que no habla de Albert Einstein. Debemos mejorar nuestro algoritmo de ordenación de resultados. ¿Qué es mejor GENERALMENTE, una web con 50.000 palabras donde aparece Albert Einstein una vez, o una web con 50 palabras donde aparece Albert Einstein una vez? Yo creo que todos escogeríamos la segunda web. Veamos como podemos mejorar nuestro método para tener en cuenta este factor.

Además de tener en cuenta el número de apariciones de las palabras clave, vamos a contar el número de palabras de cada web. Calculamos el número de palabras de cada web y lo dividimos entre el número de apariciones de las palabras para obtener la puntuación final. Cuanto más palabras tenga la web menor será la puntuación a no ser que la palabra clave aparezca muchas veces.

-PRIMERA POSICIÓN (Número de palabras:21. Número apariciones: 3 . Puntuación: 3/21=0.14): «Albert Einstein murió en 1955. Uno de los mayores logros de Einstein fue la formulación de la teoría de la relatividad.»

-SEGUNDA POSICIÓN (Número de palabras:38. Número apariciones: 4 . Puntuación: 4/38=0.10 ):»Uno de los grandes fallos reconocidos de Einstein fue la introducción de la constante cosmológica. Aunque últimamente se está viendo que Albert Einstein no estaba tan equivocado. Albert era nunca aceptó plenamente las teorías de la mecánica cuántica.»

-TERCERA POSICIÓN (Número de palabras:53. Número apariciones: 5 . Puntuación: 5/53=0.09): » Albert es un niño muy juguetón. Siempre está dando la tabarra. Pero Albert también tiene una mente brillante con la que podría rivalizar con el mismísimo Einstein. Puede que algún día Albert nos sorprenda. Albert tiene una gran imaginación. Podríamos educarlo para que llegue a ser un genio que gane el premio Nobel.»

Fijaros que hemos conseguido que las páginas con mayor Densidad de palabras clave aparezcan primero. Seguramente hayáis notado esta característica al buscar con Google, generalmente los primeros resultados muestran webs donde las palabras que hemos buscado están muy cercanas y aparecen muchas veces.

Tened en cuenta que ésta es una pequeña descripción del método de forma intuitiva. La fórmula completa tiene en cuenta otros factores importantes, ya que según lo descrito una web que pusiera «Albert Einstein» a secas sería la ganadora. Este no es un método definitivo ni mucho menos, hay muchos algoritmos que utilizan técnicas muy avanzadas para intentar darnos los mejores resultados. Una mejora sería aplicar este método para cada frase, e ir sumando la puntuación de cada frase para obtener una puntuación final.

A este método se le pueden encontrar muchos defectos, pero por lo general funciona bastante bien. Además, debéis tener en cuenta que la ordenación de los resultados finales es algo muy subjetivo. Quizás un resultado no le sirva para nada a la persona X, pero a la persona Y le sea de mucha utilidad. Por ello Google, además de utilizar algoritmos básicos de ordenación como el que acabamos de explicar, usa también el famoso PageRank para mejorar aún más a disposición de los resultados.

PageRank asigna una puntuación a cada página según una fórmula que explicaremos en el siguiente capítulo. El valor del PageRank se utiliza junto con el valor obtenido por el Algoritmo de Ordenación «similar» al explicado en este artículo para obtener la posición final de cada web en los resultados de un búsqueda.