Проектирование веб-обходчика


Я столкнулся с вопросом интервью "если бы вы разрабатывали веб-Искатель, как бы вы избежали попадания в бесконечные циклы? - и я пытаюсь ответить на него.

Как все это начинается с самого начала. Скажем, Google начал с некоторых страниц концентратора, говорят сотни из них (как эти страницы концентратора были найдены в первую очередь, это другой под-вопрос). Поскольку Google следует за ссылками со страницы и т. д., Он продолжает создавать хэш-таблицу, чтобы убедиться, что она не следует ранее посещенные страницы.

Что делать, если одна и та же страница имеет 2 имени (url) говорят в эти дни, когда у нас есть URL-шортенеры и т. д..

Я взял Google в качестве примера. Хотя Google не просачивается, как работают его алгоритмы веб-обходчика и ранжирование страниц и т. д., Но какие-либо догадки?

8 64

8 ответов:

Если вы хотите получить подробный ответ взглянем на раздел 3.8 настоящий документ, который описывает URL-видимый тест современного скребка:

в процессе извлечения ссылок, любые Веб-искатель столкнется с несколькими ссылки на один и тот же документ. Избегать загрузка и обработка документа несколько раз, URL-видимый тест должен выполняется на каждой извлеченной ссылке перед добавлением его в границу URL. (Альтернативный дизайн был бы к вместо того, чтобы проанализировать URL-адрес-видел тест, когда URL-адрес удаляется с границы, но такой подход приведет к гораздо большая граница.)

выполнить URL-видел тест, мы храним все URL-адреса видны Меркатора в каноническом форма в большой таблице называется URL набор. Опять же, слишком много записей чтобы они все умещались в памяти, так хотелось набор отпечатков пальцев документа, URL набор хранится в основном на дисках.

сохранить космоса у нас нет хранить текстовую информацию представление каждого URL-адреса в URL-адресе набор, но скорее фиксированного размера контрольная сумма. В отличие от отпечатков пальцев представленный контент-видел тест набор отпечатков пальцев документа, поток URL-адресов, проверку набора URL-адреса нетривиальное количество местности. К уменьшить количество операций на архив диска подпорки, мы поэтому держим кэш в памяти популярных URL-адресов. Интуиция для этого кэша заключается в том, что ссылки на некоторые URL-адреса довольно распространены, так что кэширование популярные в памяти приведет к высокому попаданию в память ставка.

фактически, используя in-memory кэш из 2^18 записей и LRU-подобных политика замены часов, мы достигаем общая скорость попадания в память кэш 66,2%, и скорость попадания 9,5% в таблице недавно добавленных URL-адресов, для чистой скорости попадания 75,7%. Более того, из 24,3% запросов, которые пропускают в как кэш популярных URL-адресов, так и таблица недавно добавленных url, о компании 1=3 произвести удары по буфер в нашем реализация файла произвольного доступа, который также находится в пользовательском пространстве. Этот конечным результатом всей этой буферизации является что каждый тест членства мы выполняем по набору URL результаты в среднем 0.16 искать и 0.17 читать ядро звонки (некоторые из которых являются подается из файловой системы ядра буфера.) Итак, каждый URL-адрес устанавливает членство тест индуцирует одну шестую часть ядра вызовы в качестве теста членства на набор отпечатков пальцев документа. Эти экономия происходит исключительно за счет на сумму населенный пункт URL-адрес (т. е., повторение популярные URL-адреса), присущих поток URL-адреса, обнаруженные во время обхода.

в основном они хэшируют все URL-адреса с помощью функции хэширования, которая гарантирует уникальные хэши для каждого URL-адреса, и из-за локальности URL-адресов становится очень легко найти URL-адреса. Google даже с открытым исходным кодом их функция хэширования:CityHash

внимание!
Они также могут говорить о боте ловушки!!! Ловушка бота-это раздел страницы, который продолжает генерировать новые ссылки с уникальными URL-адресами, и вы по существу попадете в "бесконечный цикл", следуя ссылкам, которые обслуживаются этой страницей. Это не совсем цикл, потому что цикл будет результатом посещения одного и того же URL-адреса, но это бесконечная цепочка URL-адресов, которые вы должны избегать обхода.

обновление 12/13/2012- на следующий день после этого мир должен был закончиться :)

Per Комментарий Fr0zenFyr: если кто-то использует AOPIC алгоритм выбора страниц, то это довольно легко избежать бот-ловушки бесконечного цикла рода. Вот краткое описание того, как работает AOPIC:

  1. получить набор из N начальных страниц.
  2. выделите X сумму кредита для каждой страницы, чтобы каждая страница имела x / N кредит (т. е. равную сумму кредита) до начала обхода.
  3. выберите страницу P, где P имеет самую высокую сумму кредита (или если все страницы имеют одинаковую сумму кредита, а затем сканируют случайную страницу).
  4. обход страницы P (допустим, что у P было 100 кредитов, когда он был обведен).
  5. извлеките все ссылки со страницы P (допустим, их 10).
  6. установите кредиты P в 0.
  7. возьмите 10% "налог" и выделите его на лямбда-страницу.
  8. выделите равное количество кредитов каждая ссылка, найденная на странице P из оригинального кредита P-the tax: so (100 (P credits) - 10 (10% налог)) / 10 (ссылки) = 9 кредитов за каждую ссылку.
  9. повторите шаг 3.

поскольку лямбда-страница постоянно собирает налог, в конечном итоге это будет страница с наибольшей суммой кредита, и нам придется "ползать" по ней. Я говорю "сканировать" в кавычках, потому что мы на самом деле не делаем HTTP-запрос для лямбда-страницы, мы просто берем ее кредиты и распределяем их поровну все на страницах в нашей базе.

Так как бот ловушки только дают внутренние ссылки кредиты и они редко получают кредит извне, они будут постоянно просачиваться кредиты (от налогообложения) на страницу лямбда. Лямбда-страница будет равномерно распределять эти кредиты по всем страницам в базе данных, и на каждом цикле страница ловушки бота будет терять все больше и больше кредитов, пока у нее не будет так мало кредитов, что она почти никогда не будет обход снова. Это не произойдет с хорошими страницами, потому что они часто получают кредиты от обратных ссылок, найденных на других страницах. Это также приводит в динамическом рейтинге страниц вы заметите, что каждый раз, когда вы делаете снимок своей базы данных, упорядочивайте страницы по количеству кредитов, которые у них есть, тогда они, скорее всего, будут упорядочены примерно в соответствии с их true Page rank.

Это только избежать бот ловушки бесконечного цикла рода, но есть многие другие ловушки для ботов что вы должны следить за и есть способы их обойти тоже.

хотя все здесь уже предложили, как создать свой веб-искатель, вот как Google ранжирует страницы.

Google присваивает каждой странице ранг, основанный на количестве ссылок обратного вызова (сколько ссылок на других сайтах указывают на конкретный сайт/страницу). Это называется оценка релевантности. Это основано на том, что если на странице есть много других страниц, связанных с ней, это, вероятно, важная страница.

каждый сайт / страница рассматривается как узел в графике. Ссылки на другие страницы направленные края. Степень вершины определяется как число входящих ребер. Узлы с большим числом входящих ребер ранжируются выше.

вот как определяется PageRank. Предположим, что страница Pj имеет ссылки на ЖЖ. Если одна из этих ссылок относится к странице Pi, то Pj передаст 1/Lj своей важности Pi. Рейтинг важности Pi - это сумма всех вкладов, сделанных страницами, ссылающимися на него. Поэтому, если мы обозначим набор страниц, ссылающихся на Pi по Bi, то у нас есть это формула:

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

ранги помещаются в матрицу, называемую матрицей гиперссылок: H[i, j]

строка в этой матрице равна либо 0, либо 1/Lj, если есть ссылка от Pi до Bi. Другое свойство этой Матрицы заключается в том, что если мы суммируем все строки в столбце, мы получим 1.

теперь нам нужно умножить эту матрицу на собственный вектор, названный I (с собственным значением 1) таким, что:

I = H*I

теперь мы начинаем повторять: IH, IяH, Яяясек .... I^k *H, пока решение не сходится. т. е. мы получаем практически одинаковые числа в матрице на шаге k и k+1.

теперь все, что осталось в векторе I, является важностью каждой страницы.

для простого примера домашнего задания класса см. http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html

Что касается решения проблемы дублирования в вашем вопросе интервью, сделайте контрольную сумму на всю страницу и использовать либо это, либо Баш контрольной суммы в качестве ключа в карте, чтобы отслеживать посещенные страницы.

зависит от того, насколько глубоким должен был быть их вопрос. Если бы они просто пытались избежать перехода по одним и тем же ссылкам взад и вперед, то хэширования URL-адресов было бы достаточно.

Как насчет контента, который имеет буквально тысячи URL-адресов, которые приводят к одному и тому же контенту? Как параметр QueryString, который ни на что не влияет, но может иметь бесконечное число итераций. Я полагаю, вы также можете хэшировать содержимое страницы и сравнивать URL-адреса, чтобы узнать, являются ли они аналогично содержимому catch, которое идентифицируется несколькими URL-адресами. см., например, ловушки ботов, упомянутые в сообщении @Lirik.

вам нужно будет иметь какую-то хэш-таблицу для хранения результатов, вам просто нужно будет проверить ее перед каждой загрузкой страницы.

проблема здесь заключается в том, чтобы не сканировать дублированные URL-адреса, которые разрешаются индексом с использованием хэша, полученного из URL-адресов. Проблема заключается в обходе дублированного контента. Каждый url "гусеничной ловушки" отличается (год, День, SessionID...).

нет "идеального" решения... но вы можете использовать некоторые из этих стратегий:

• держите поле того уровня, который url находится внутри веб-сайта. Для каждой ячейки получения URL-адресов со страницы увеличьте уровень. Это будет как дерево. Вы можете перестать ползать на определенном уровне, например 10 (я думаю, что google использует это).

• вы можете попробовать создать своего рода хэш, который можно сравнить, чтобы найти похожие документы, так как вы не можете сравнить с каждым документом в вашей базе данных. Есть SimHash от google, но я не смог найти никакой реализации для использования. Тогда я создал свой собственный. Мой хэш подсчитывает низкие и высокочастотные символы внутри html-кода и генерирует хэш 20bytes, который сравнивается с небольшим кэшем последнего обхода страницы внутри AVLTree с поиском NearNeighbors с некоторым допуском (около 2). Вы не можете использовать любую ссылку на расположение символов в этом хэше. После "распознавания" ловушки вы можете записать шаблон url дублированного контента и начать игнорировать страницы с этим тоже.

• Как и google, вы можете создать рейтинг для каждого веб-сайта и "доверять" больше, чем другим.

искатель сохраняет пул URL-адресов, содержащий все URL-адреса для обхода. Чтобы избежать "бесконечного цикла", основная идея состоит в том, чтобы проверить существование каждого URL-адреса перед добавлением в пул.

однако это нелегко реализовать, когда система масштабируется до определенного уровня. Наивный подход заключается в сохранении всех URL-адресов в хэш-наборе и проверке существования каждого нового URL-адреса. Это не будет работать, когда есть слишком много URL-адресов, чтобы вписаться в память.

есть несколько решений здесь. Например, вместо того, чтобы хранить все URL-адреса в памяти, мы должны хранить их на диске. Для того чтобы сохранить космос, URL-адрес хэш должен быть использован вместо исходный URL-адрес. Стоит также отметить, что мы должны сохранить каноническую форму URL, а не оригинал. Так что, если URL-адрес является укороченным на услуги, такие как bit.лы, это лучше, чтобы получить конечный URL. Для ускорения процесса проверки можно построить слой кэша. Или вы можете видеть его как распределенную систему кэша, которая является отдельной тема.

пост построить веб-Искатель есть подробный анализ этой проблемы.

ну, веб-это в основном ориентированный граф, поэтому вы можете построить график из URL-адресов, а затем выполнить обход BFS или DFS, отмечая посещенные узлы, чтобы вы не посещали одну и ту же страницу дважды.

Это пример веб-краулер. Который может быть использован для сбора mac-адресов для подмены mac.

#!/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://stackoverflow.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'])

измените url для обхода других сайтов......удачи