Как избежать зацикливания при разработке поискового робота

Прежде всего, давайте зададим себе вопрос: при каких условиях в этой задаче может возникнуть бесконечный цикл? Такая ситуация вполне вероятна, например, если мы рассматриваем Всемирную паутину как граф ссылок.

Чтобы предотвратить зацикливание, нужно его обнаружить. Один из способов — создание хэш-таблицы, в которой после посещения страницы v устанавливается hash[v] = true.
Подобное решение применимо при поиске в ширину. Каждый раз при посещении страницы мы собираем все ее ссылки и добавляем их в конец очереди. Если мы уже посетили страницу, то просто ее игнорируем.

Здорово, но что означает посетить страницу v? Что определяет страницу v: ее содержимое или URL?

Если для идентификации страницы использовать URL, то нужно сознавать, что параметры URL-адреса могут указывать на другую страницу. Например, страница www.careercup.com/page?id=microsoft-interview-questions отличается от страницы www.careercup.com/page?id=google-interview-questions. С другой стороны, можно добавить параметры, а страница от этого не изменится. Например, страница www.careercup.com?foobar=hello — это та же страница, что и www.careercup.com.

Вы можете сказать: «Хорошо, давайте идентифицировать страницы на основании их содержимого». Это звучит правильно, но не очень хорошо работает. Предположим, что на домашней странице careercup.com представлен некий генерирующийся случайным образом контент. Каждый раз, когда вы посещаете страницу, контент будет другим. Такие страницы можно назвать разными? Нет.

На самом деле не существует идеального способа идентифицировать страницу, и задача превращается в головоломку.

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

Давайте посмотрим, как такой алгоритм может работать.

Допустим, что существует база данных, хранящая список элементов, которые необходимо проверить. При каждой итерации мы выбираем страницу с самым высоким приоритетом:

1. Открываем страницу и создаем подпись страницы, основанную на определенных подсекциях страницы и ее URL.
2. Запрашиваем базу данных, чтобы увидеть, когда посещалась страница с этой подписью.
3. Если элемент с такой подписью недавно проверялся, то присваиваем низший приоритет и возвращаем страницу в базу данных.
4. Если элемент новый, то совершаем обход страницы и добавляем ее ссылки в базу данных.

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

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

Разбор взят из книги Гейл Л. Макдауэлл «Cracking the Coding Interview» (есть в переводе).