data-structures - motores - qué es un crawler

Diseñando un rastreador web (8)

Bueno, la web es básicamente un gráfico dirigido, por lo que puede construir un gráfico a partir de las URL y luego hacer un recorrido BFS o DFS mientras marca los nodos visitados para que no visite la misma página dos veces.

Me encontré con una pregunta de la entrevista "Si estuvieras diseñando un rastreador web, ¿cómo evitarías entrar en ciclos infinitos?" Y estoy tratando de responderlo.

¿Cómo comienza todo desde el principio? Digamos que Google comenzó con algunas páginas centrales que dicen que cientos de ellas (cómo se encontraron estas páginas centrales en primer lugar es una sub-pregunta diferente). Como Google sigue los enlaces de una página y así sucesivamente, sigue haciendo una tabla hash para asegurarse de que no sigue las páginas visitadas anteriormente.

¿Qué pasa si la misma página tiene 2 nombres (URL) dicen en estos días cuando tenemos acortadores de URL, etc.

Tomé Google como un ejemplo. Aunque Google no filtra cómo funcionan los algoritmos del rastreador web y el ranking de la página, etc., ¿pero adivina?

Depende de cuán profunda sea la intención de su pregunta. Si solo trataran de evitar seguir los mismos enlaces de ida y vuelta, entonces bastaría con hash las URL.

¿Qué pasa con el contenido que tiene literalmente miles de URL que conducen al mismo contenido? Como un parámetro QueryString que no afecta a nada, pero puede tener un número infinito de iteraciones. Supongo que también podría analizar el contenido de la página y comparar las URL para ver si son similares al contenido capturado que se identifica por varias URL. Ver por ejemplo, Trampas de Bot mencionadas en la publicación de @Lirik.

El problema aquí no es rastrear las URL duplicadas, que se resuelve mediante un índice que utiliza un hash obtenido de las URL. El problema es rastrear CONTENIDO DUPLICADO. Cada url de una "Trampa de correa es diferente" (año, día, ID de sesión ...).

No hay una solución "perfecta" ... pero puede usar algunas de estas estrategias:

• Mantenga un campo del nivel donde se encuentra la url dentro del sitio web. Para cada ciclo de obtener URL de una página, aumente el nivel. Será como un árbol. Puede detenerse para rastrear en cierto nivel, como 10 (creo que google usa esto).

• Puede intentar crear un tipo de HASH que se pueda comparar para encontrar documentos similares, ya que no se puede comparar con cada documento en su base de datos. Hay SimHash de google, pero no pude encontrar ninguna implementación para usar. Entonces he creado el mío. Mi hash cuenta los caracteres de baja y alta frecuencia dentro del código html y genera un hash de 20bytes, que se compara con un pequeño caché de las últimas páginas rastreadas dentro de un AVLTree con una búsqueda NearNeighbors con algo de tolerancia (alrededor de 2). No puede usar ninguna referencia a las ubicaciones de caracteres en este hash. Después de "reconocer" la trampa, puede registrar el patrón de URL del contenido duplicado y comenzar a ignorar las páginas con eso también.

• Al igual que Google, puede crear un ranking para cada sitio web y "confiar" más en uno que en otros.

El rastreador mantiene un grupo de URL que contiene todas las URL que se rastrearán. Para evitar el "bucle infinito", la idea básica es verificar la existencia de cada URL antes de agregarla al conjunto.

Sin embargo, esto no es fácil de implementar cuando el sistema ha escalado a cierto nivel. El enfoque ingenuo es mantener todas las URL en un hashset y verificar la existencia de cada nueva URL. Esto no funcionará cuando haya demasiadas URL para caber en la memoria.

Hay un par de soluciones aquí. Por ejemplo, en lugar de almacenar todas las URL en la memoria, debemos guardarlas en el disco. Para ahorrar espacio, se debe usar hash de URL en lugar de la URL sin formato. También vale la pena señalar que debemos mantener la forma canónica de URL en lugar de la original. Entonces, si la URL es acortada por servicios como bit.ly, es mejor obtener la URL final. Para acelerar el proceso de comprobación, se puede construir una capa de caché. O puede verlo como un sistema de caché distribuida, que es un tema separado.

La publicación Build a Web Crawler tiene un análisis detallado de este problema.

Este es un ejemplo de rastreador web. Que se puede utilizar para recopilar direcciones MAC para mac spoofing.

#!/usr/bin/env python import sys import os import urlparse import urllib from bs4 import BeautifulSoup def mac_addr_str(f_data): global fptr global mac_list word_array = f_data.split(" ") for word in word_array: if len(word) == 17 and '':'' in word[2] and '':'' in word[5] and '':'' in word[8] and '':'' in word[11] and '':'' in word[14]: if word not in mac_list: mac_list.append(word) fptr.writelines(word +"/n") print word url = "http://.com/questions/tagged/mac-address" url_list = [url] visited = [url] pwd = os.getcwd(); pwd = pwd + "/internet_mac.txt"; fptr = open(pwd, "a") mac_list = [] while len(url_list) > 0: try: htmltext = urllib.urlopen(url_list[0]).read() except: url_list[0] mac_addr_str(htmltext) soup = BeautifulSoup(htmltext) url_list.pop(0) for tag in soup.findAll(''a'',href=True): tag[''href''] = urlparse.urljoin(url,tag[''href'']) if url in tag[''href''] and tag[''href''] not in visited: url_list.append(tag[''href'']) visited.append(tag[''href''])

Cambia la URL para rastrear más sitios ...... buena suerte

Si bien todos aquí ya sugirieron cómo crear su rastreador web, aquí se explica cómo clasifica Google las páginas.

Google asigna a cada página un rango basado en el número de enlaces de devolución de llamada (cuántos enlaces en otros sitios web apuntan a un sitio web / página específico). Esto se llama puntuación de relevancia. Esto se basa en el hecho de que si una página tiene muchas otras páginas enlazadas, probablemente sea una página importante.

Cada sitio / página se ve como un nodo en un gráfico. Los enlaces a otras páginas son bordes dirigidos. Un grado de vértice se define como el número de bordes entrantes. Los nodos con un mayor número de bordes entrantes tienen una clasificación más alta.

Así es como se determina el PageRank. Supongamos que la página Pj tiene enlaces Lj. Si uno de esos enlaces es a la página Pi, entonces Pj transmitirá 1 / Lj de su importancia a Pi. La clasificación de importancia de Pi es entonces la suma de todas las contribuciones hechas por las páginas que enlazan con ella. Entonces, si denotamos el conjunto de páginas que enlazan a Pi por Bi, entonces tenemos esta fórmula:

Importance(Pi)= sum( Importance(Pj)/Lj ) for all links from Pi to Bi

Los rangos se colocan en una matriz llamada matriz de hipervínculo: H [i, j]

Una fila en esta matriz es 0, o 1 / Lj si hay un enlace de Pi a Bi. Otra propiedad de esta matriz es que si sumamos todas las filas en una columna obtenemos 1.

Ahora necesitamos multiplicar esta matriz por un vector Eigen, llamado I (con valor propio 1) tal que:

I = H*I

Ahora comenzamos a iterar: I H, I I H, I I I H .... I ^ k * H hasta que la solución converja. es decir, obtenemos casi los mismos números en la matriz en el paso k y k + 1.

Ahora lo que queda en el vector I es la importancia de cada página.

Para un ejemplo simple de tarea de clase, consulte http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html

En cuanto a la solución del problema duplicado en la pregunta de la entrevista, realice una suma de comprobación en toda la página y use ese o un resumen de la suma de comprobación como clave en un mapa para realizar un seguimiento de las páginas visitadas.

Si desea obtener una respuesta detallada, eche un vistazo a la sección 3.8 de este documento , que describe la prueba de URL visto de un raspador moderno:

En el transcurso de la extracción de enlaces, cualquier rastreador web encontrará múltiples enlaces al mismo documento. Para evitar descargar y procesar un documento varias veces, se debe realizar una prueba de URL vista en cada enlace extraído antes de agregarlo a la frontera de la URL. (Un diseño alternativo sería realizar la prueba de URL visto cuando la URL se elimina de la frontera, pero este enfoque daría como resultado una frontera mucho más grande).
Para realizar la prueba de URL visto, almacenamos todas las URL vistas por Mercator en forma canónica en una tabla grande llamada conjunto de URL. Nuevamente, hay demasiadas entradas para que todas puedan caber en la memoria, por lo que al igual que el conjunto de huellas dactilares del documento, el conjunto de URL se almacena principalmente en el disco.
Para ahorrar espacio, no almacenamos la representación textual de cada URL en el conjunto de URL, sino más bien una suma de verificación de tamaño fijo. A diferencia de las huellas dactilares presentadas en el conjunto de huellas digitales de documentos de la prueba vista en el contenido, la secuencia de URL probadas contra el conjunto de URL tiene una cantidad de localidad no trivial. Para reducir el número de operaciones en el archivo de disco de respaldo, conservamos un caché en memoria de las URL populares. La intuición para este caché es que los enlaces a algunas URL son bastante comunes, por lo que el almacenamiento en memoria caché de los populares en la memoria generará una alta tasa de aciertos en la memoria.
De hecho, usando un caché en memoria de 2 ^ 18 entradas y la política de reemplazo de reloj similar a LRU, logramos una tasa de aciertos total en la memoria caché en memoria del 66.2%, y una tasa de aciertos de 9.5% en la tabla de URLs recientemente agregadas, para una tasa de aciertos neta del 75.7%. Además, del 24.3% de las solicitudes que fallan tanto en el caché de URL populares como en la tabla de URL recientemente agregadas, aproximadamente 1 = 3 producen aciertos en el buffer en nuestra implementación de archivo de acceso aleatorio, que también reside en el espacio de usuario. El resultado neto de todo este almacenamiento en búfer es que cada prueba de membresía que realizamos en el conjunto de URL da como resultado un promedio de 0.16 búsquedas y 0.17 llamadas de kernel de lectura (algunas fracciones se sirven de los almacenamientos intermedios del sistema de archivos del kernel). Por lo tanto, cada prueba de membresía del conjunto de URL induce una sexta parte de las llamadas al kernel como una prueba de membresía en el conjunto de huellas digitales del documento. Estos ahorros se deben exclusivamente a la cantidad de URL localidad (es decir, la repetición de URL populares) inherente a la secuencia de URL encontradas durante el rastreo.

Básicamente, codifican todas las URL con una función de hashing que garantiza hashes únicos para cada URL y, debido a la ubicación de las URL, es muy fácil encontrar las URL. Google incluso tiene una fuente abierta de hash: CityHash

¡ADVERTENCIA!
¡¡¡También podrían estar hablando de trampas para bots !!! Una trampa de bots es una sección de una página que sigue generando nuevos enlaces con URL únicas y básicamente quedará atrapado en un "bucle infinito" al seguir los enlaces que están siendo servidos por esa página. Esto no es exactamente un bucle, porque un bucle sería el resultado de visitar la misma URL, pero es una cadena infinita de URL que debe evitar el rastreo.

Actualización 12/13/2012 - el día después de que se suponía que el mundo terminaría :)

Por Fr0zen Comentario de Fyr: si uno usa el algoritmo AOPIC para seleccionar páginas, entonces es bastante fácil evitar bot-trampas del tipo de bucle infinito. Aquí hay un resumen de cómo funciona AOPIC:

Obtenga un conjunto de N páginas semilla.
Asigne X cantidad de crédito a cada página, de modo que cada página tenga crédito X / N (es decir, la misma cantidad de crédito) antes de comenzar el rastreo.
Seleccione una página P, donde la P tiene la mayor cantidad de crédito (o si todas las páginas tienen la misma cantidad de crédito, luego rastree una página al azar).
Rastrear la página P (supongamos que P tenía 100 créditos cuando se rastreó).
Extraiga todos los enlaces de la página P (digamos que hay 10).
Establezca los créditos de P en 0.
Tome un 10% de "impuesto" y asócielo a una página de Lambda.
Asigne una cantidad igual de créditos a cada enlace encontrado en la página P del crédito original de P: el impuesto: entonces (100 (créditos P) - 10 (10% de impuestos)) / 10 (enlaces) = 9 créditos por cada enlace.
Repita desde el paso 3.

Como la página de Lambda continuamente recauda impuestos, eventualmente será la página con la mayor cantidad de crédito y tendremos que "rastrearla". Digo "crawl" entre comillas, porque en realidad no realizamos una solicitud HTTP para la página Lambda, simplemente tomamos sus créditos y los distribuimos por igual a todas las páginas de nuestra base de datos.

Como las trampas de bots solo otorgan créditos de enlaces internos y rara vez obtienen crédito del exterior, continuamente emitirán créditos (de impuestos) a la página de Lambda. La página de Lambda distribuirá esos créditos a todas las páginas de la base de datos de manera uniforme y en cada ciclo la página trampa del bot perderá más y más créditos, hasta que tenga tan pocos créditos que casi nunca vuelva a rastrearse. Esto no sucederá con las páginas buenas, ya que a menudo obtienen créditos de enlaces posteriores que se encuentran en otras páginas. Esto también da como resultado un rango de página dinámico y lo que notará es que cada vez que toma una instantánea de su base de datos, ordene las páginas por la cantidad de créditos que tienen, entonces lo más probable es que se ordenen aproximadamente de acuerdo con su verdadero rango de página .

Esto solo evita trampas de bucles del tipo de bucle infinito, pero hay muchas otras trampas de bots que debes tener en cuenta y también hay formas de evitarlas.

Tendría que tener algún tipo de tabla hash para almacenar los resultados, solo tendría que comprobarlo antes de cargar cada página.