Conception d'un robot Web

Question

Je suis venu à travers une interview, à la question "Si vous étiez de la conception d'un robot d'indexation web, comment voulez-vous éviter de tomber dans une boucle infinie?" et j'essaie d'y répondre.

Comment ça a commencé dès le début. Dire que Google a commencé avec un hub pages, des centaines d'entre eux (la Façon dont ces pages hub ont été trouvés, en premier lieu, un autre sous-question). Que Google suit les liens d'une page, et ainsi de suite, de ne garder de faire une table de hachage pour s'assurer qu'il n'a pas suivi les précédentes pages visitées.

Et si la même page a 2 noms (Url) de dire en ces jours où nous avons des raccourcisseurs d'URL, etc..

J'ai pris pour exemple Google. Si Google n'a pas de fuite comment sa web crawler et algorithmes de classement de page etc, mais toutes les suppositions?

Answer 1

Si vous souhaitez obtenir une réponse détaillée de prendre un coup d'oeil à la section 3.8 du présent document, qui décrit l'URL-vu de test d'un système moderne de grattoir:

Dans le cadre de l'extraction de liens, tout Le Web crawler permettra de rencontrer de multiples les liens vers le même document. Pour éviter le téléchargement et le traitement d'un document plusieurs fois, une URL-vu test doit être effectuée sur chaque extrait lien avant l'ajout de l'URL de la frontière. (Une conception alternative serait de au lieu d'effectuer l'URL-vu test quand l'URL est retiré de la frontière, mais cette approche conduirait à une beaucoup plus de frontière.)

Pour effectuer la URL-vu de test, nous conservons toutes les Url vus par Mercator dans canonique forme dans un grand tableau intitulé URL ensemble. Encore une fois, il y a trop d'entrées pour eux tous pour s'adapter à la mémoire, donc comme le document d'empreintes digitales ensemble, l'URL ensemble est stocké principalement sur le disque.

Pour enregistrer de l'espace, nous ne stockons pas les textes la représentation de chaque URL dans l'URL , mais plutôt à une taille fixe somme de contrôle. Contrairement aux empreintes digitales présenté au contenu-vu du test document d'empreintes digitales ensemble, les flux de de Url testé par rapport à l'URL a un montant non négligeable de la localité. Pour réduire le nombre d'opérations sur le sauvegarde de fichier de disque, nous avons donc garder un cache en mémoire populaire Url. L'intuition de ce cache est que des liens vers des Url sont tout à fait commun, si la mise en cache les plus populaires dans la mémoire va conduire à une forte en mémoire frappé taux d'.

En fait, l'utilisation d'une mémoire cache de 218 entrées et de la LRU-comme l'horloge de la politique de remplacement, nous atteindre un ensemble de taux de succès sur la mémoire cache de 66,2%, et un taux de succès de 9,5% sur la table de récemment ajoutée Url, pour un net taux de succès de 75.7%. En outre, de la 24,3% des demandes qui manquent dans à la fois le cache de populaire Url et le table de récemment ajoutée Url, sur 1=3 produire des hits sur le tampon dans notre fichier à accès aléatoire de la mise en œuvre, qui réside également dans l'espace utilisateur. L' résultat net de l'ensemble de cette mise en mémoire tampon est que chaque test, nous avons effectuer sur l'URL de l'ensemble des résultats dans la moyenne de 0,16 chercher et de 0,17 lire noyau appels (une fraction de qui sont servi du noyau du système de fichiers tampons). Ainsi, chaque URL de l'appartenance test induit un sixième autant de noyau les appels d'adhésion d'essai sur le document d'empreintes digitales ensemble. Ces les économies sont purement en raison de la quantité de URL localité (c'est à dire, la répétition de populaire Url) inhérente dans le flux de Url rencontrés lors d'une analyse.

En gros, ils hachage toutes les Url avec une fonction de hachage qui garantit unique hachages pour chaque URL et en raison de la localité d'Url, il devient très facile de trouver des Url. Google, même open-source leur fonction de hachage: CityHash

AVERTISSEMENT!
On pourrait aussi parler de bot pièges!!! Un bot piège est une section d'une page qui continue de générer de nouveaux liens avec une Url unique, et vous obtiendrez donc pris au piège dans une "boucle infinie", en suivant les liens qui sont desservies par cette page. Ce n'est pas exactement une boucle, car une boucle serait le résultat de la visite de la même URL, mais c'est une chaîne infinie d'Url qui vous devriez éviter de l'analyse.

Mise à jour 12/13/2012- le jour après que le monde était censé mettre fin à l' :)

Par Fr0zenFyr commentaire: si l'on utilise le AOPIC algorithme pour la sélection de pages, puis c'est assez facile à éviter bot-les pièges de la boucle infinie genre. Voici un résumé de la façon dont AOPIC œuvres:

1. Obtenir un ensemble de N de graines de pages.
2. Allouer un montant X de crédit à chaque page, de telle sorte que chaque page X/N de crédit (c'est à dire une quantité égale de crédit), avant de ramper a commencé.
3. Sélectionnez une page P, où P est le montant le plus élevé de crédit (ou si toutes les pages ont le même montant de crédit, l'analyse d'une page au hasard).
4. Analyse de la page P (disons que P a 100 crédits lorsqu'il a été analysé).
5. Extraire tous les liens à partir de la page P (disons il y a 10 d'entre eux).
6. Définir les crédits de P à 0.
7. Prendre 10% "impôt" et de les attribuer à un Lambda de la page.
8. Allouer un montant équivalent de crédits de chaque lien trouvé sur la page de P à partir de P original du crédit de la taxe: (100 (P crédits) - 10 (10% de taxe))/10 (liens) = 9 crédits par chaque lien.
9. Répétez à partir de l'étape 3.

Depuis le Lambda page continu de collecte de l'impôt, par la suite il sera la page avec le plus grand montant de crédit et nous aurons à "ramper". Je dis "ramper" entre guillemets, parce que nous ne sommes pas réellement faire une requête HTTP pour le Lambda page, nous venons de prendre ses crédits et de les distribuer de manière égale à toutes les pages de notre base de données.

Depuis bot pièges uniquement à donner des liens internes de crédits et qu'ils ont rarement de crédit de l'extérieur, ils n'aura de cesse de fuite de crédits d'impôt) pour le Lambda de la page. Le Lambda page de distribuer des crédits à toutes les pages de la base de données de manière uniforme et à chaque cycle, le bot piège de la page va perdre de plus en plus de crédits, jusqu'à ce qu'il a si peu de crédits qu'il n'est jamais analysé de nouveau. Cela n'arrivera pas avec de bonnes pages, parce que souvent ils obtiennent des crédits de back-liens sur d'autres pages. Cela se traduit également dans une dynamique de page rank, et ce que vous remarquerez est que chaque fois que vous prenez un instantané de votre base de données, afin que les pages par le montant des crédits qu'ils ont, alors ils seront très probablement être commandé à peu près en fonction de leur véritable rang de page.

Cette seulement éviter les bot les pièges de l'infini-en boucle, mais il y a beaucoup d'autres bot pièges que vous devriez regarder dehors pour et il y a des moyens de les contourner.

Answer 2

Alors que tout le monde ici l'a déjà suggéré comment créer votre site web crawler, voici comment Google classe les pages.

Google donne à chaque page un classement basé sur le nombre de rappel des liens (en nombre de liens sur d'autres sites pointent vers un site web spécifique/page). Ceci est appelé le niveau de pertinence. Ceci est basé sur le fait que si une page a de nombreux autres pages de lien, c'est probablement l'une des pages les plus importantes.

Chaque site/la page est considérée comme un nœud dans un graphe. Des liens vers d'autres pages sont des arêtes orientées. Un degré d'un sommet est défini comme le nombre d'entrants bords. Les nœuds avec une hausse du nombre d'entrants bords sont d'un rang plus élevé.

Voici comment le PageRank est établi. Supposons que la page Pj a Lj liens. Si l'un de ces liens est à la page Pi, alors Pj va passer à 1/Lj de son importance pour le Pi. L'ordre d'importance de la Pi est alors la somme de toutes les contributions faites par les pages un lien vers elle. Donc, si nous noterons l'ensemble de pages un lien vers Pi-Bi, puis nous avons cette formule:

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

Les rangs sont placés dans une matrice appelle de lien hypertexte de la matrice: H[i,j]

Une ligne de cette matrice est soit 0, soit 1/Lj s'il existe un lien de Pi pour les Bi. Une autre propriété de cette matrice est que si nous somme de toutes les lignes dans une colonne on obtient 1.

Maintenant nous avons besoin de multiplier cette matrice par un vecteur Propre, nommé I (avec valeur propre 1) tels que:

I = H*I

Maintenant, nous commencer à répéter: I*H, I*I*H, I*I*I*H .... I^k *H jusqu'à ce que la solution converge. ie nous obtenir à peu près les mêmes chiffres dans la matrice à l'étape k et k+1.

Maintenant, tout ce qui est à gauche dans le I du vecteur est l'importance de chaque page.

Pour une simple classe devoirs exemple voir http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html

Pour résoudre le double problème dans votre interview en question, faire une somme de contrôle sur l'ensemble de la page et l'utilisation ou bien un bash de la somme de contrôle que votre clé dans une carte à garder une trace des pages visitées.

Answer 3

Dépend de la profondeur de leur question était destiné à être. Si ils ont juste essayer d'éviter les mêmes liens d'avant en arrière, puis le hachage de l'URL serait suffisant.

Ce sujet du contenu qui a littéralement des milliers d'URL qui mènent vers le même contenu? Comme un paramètre de chaîne de Requête qui n'a rien, mais peut avoir un nombre infini d'itérations. Je suppose que vous pourriez hachage du contenu de la page et de comparer les URL pour voir si elles sont similaires à capturer le contenu qui est identifié par plusieurs URL. Voir, par exemple, Bot Pièges mentionnés dans @Lirik post.

Answer 4

Vous auriez besoin d'une sorte de table de hachage pour stocker les résultats, il vous suffirait de vérifier avant chaque chargement de page.

Answer 5

Le problème ici n'est pas d'analyser dupliqué URL, ce qui est résolue par un index à l'aide d'un algorithme de hachage obtenue à partir d'url. Le problème est d'analyser le CONTENU DUPLIQUÉ. Chaque url d'un "Crawler " Piège" est différent (l'année, le jour, l'id de session...).

Il n'est pas "parfait" solution... mais vous pouvez utiliser certaines de ces stratégies:

• Gardez un champ dont le niveau de l'url est à l'intérieur du site web. Pour chaque cicle d'obtenir des url d'une page, d'augmenter le niveau. Il sera comme un arbre. Vous pouvez vous arrêter pour analyse à un certain niveau, à l'instar de 10 (je pense que google utilisez cette).

• Vous pouvez essayer de créer une sorte de HACHAGE qui peut être comparé à trouver des documents similaires, puisque tu ne peux pas comparer avec chaque document dans votre base de données. Il y a SimHash de google, mais je ne pouvais pas trouver tout de la mise en œuvre d'utilisation. Ensuite ive créé mon propre. Mon hash comte de basse et de haute fréquence de caractères à l'intérieur du code html et de générer un 20bytes de hachage, ce qui est comparé avec un petit cache de la dernière exploration des pages à l'intérieur d'un AVLTree avec un NearNeighbors de recherche avec une certaine tolérance (2). Vous ne pouvez pas utiliser toute référence à des personnages endroits dans ce hash. Après "reconnaître" le piège, vous pouvez enregistrer le modèle d'url de la duplication de contenu et de commencer à ignorer les pages.

• Comme google, vous pouvez créer un classement pour chaque site et de la "confiance" de plus dans l'une que les autres.