Оптимальный алгоритм парсинга для BAS

[romanbiz]

Всем привет. Пишу парсер сайта через браузер.
Условно говоря, задача в том чтобы собрать все внутренние ссылки (на сайте внешних ссылок нет), переходя по ним.
Использую экшн Для каждого элемента- Начать цикл.
Пытаюсь сделать вложенные циклы, еще при помощи меток переходить обратно итп, но цельного понимания как это организовать нет, плаваю в этом, охватить полностью все ссылки не получается, что-то да и теряю. Я просто не понимаю как сделать чтобы он обошел все страницы.

То есть, вопрос в алгоритме обхода графа при помощи Для каждого элемента- Начать цикл. Как оптимальным образом организовать обход, буду признателен за советы.

Я знаю что существуют методики типа https://ru.wikipedia.org/wiki/Поиск_в_глубину но от попытки придумать как это переложить на Для каждого элемента- Начать цикл мозг начинает закипать.

[bigorat]

@romanbiz а выпарсить сайт через sitemap нельзя? Так же проще, я вот один так и парсил причем методом GET запросов.

[romanbiz]

@bigorat Нет, sitemap никак не получить. Сайт закрытый. Ну и еще есть детали типа отсутствия ссылок в браузере (не IFRAME а JS), приходится сохранять каждую страницу с идентификатором, но я уже просто решил не грузить кучей подробностей. В общем нужен именно алгоритм обхода сайта.

[bigorat]

@romanbiz да, тогда все сложнее, тут надо смотреть что за сайт и от этого плясать конечно :(

[romanbiz]

@bigorat А что именно зависит от сайта? Можете сказать конкретные детали, которые влияют на сложность алгоритма обхода? По моему мнению на алгоритм обхода особенности сайта не влияют вообще.

[ruzne]

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

[romanbiz]

@ruzne Спасибо за ответ. Думал о таком механизме. Но на вопрос как обойти ВСЕ страницы он не отвечает.

[ruzne]

а тоесть, есть такой вариант что начиная с одной страници на какую то страницу переходя по ссылкам можно и не попасть, тут только полным посимволным перебором,
а или понял, если важно чтобы и рефер был похож на ностоящий, можно сохранять хеш урлРефер:урл

[romanbiz]

@ruzne Почему посимвольным перебором? Существует несколько методов обхода графа, я давал ссылку выше.

Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин

[romanbiz]

@ruzne без разницы какой рефер, интересует алгоритм обхода графа, а не как обмануть сайт.

[ruzne]

@romanbiz

foo(url){
  arr = getUrl();
  foreach iUrl(arr){
    foo(iUrl)
  }
}

[romanbiz]

@ruzne Вот еще метод в ширину. Вопрос как это переложить на Для каждого элемента- Начать цикл

Поместить узел, с которого начинается поиск, в изначально пустую очередь.
Извлечь из начала очереди узел U и пометить его как развёрнутый.
Если узел U является целевым узлом, то завершить поиск с результатом «успех».
В противном случае, в конец очереди добавляются все преемники узла U, которые ещё не развёрнуты и не находятся в очереди.
Если очередь пуста, то все узлы связного графа были просмотрены, следовательно, целевой узел недостижим из начального; завершить поиск с результатом «неудача».
Вернуться к п. 2.
Примечание: деление вершин на развёрнутые и не развёрнутые необходимо для произвольного графа (так как в нём могут быть циклы). Для дерева эта операция не нужна, так как каждая вершина будет выбрана один-единственный раз.

[romanbiz]

@ruzne said in Оптимальный алгоритм парсинга для BAS:

foo(url){
  arr = getUrl();
  foreach iUrl(arr){
    foo(iUrl)
  }
}

Можете пояснить что это и как работает?

[ruzne]

функция принимающая на вход урл,
переходит по этому урлу, получает со страницы все ссылки в массив селектором а. для каждой полученой ссылки вызывем ту же функцию
можно добавить после foo(iUrl) history.go(-1) - перейти к предидущей страници

а я бы открывал каждую новую ссылку в новой вкладке, и после того как обошол все ссылки на первой вкладке переходил бы к следующей

[romanbiz]

@ruzne Повторюсь, я просил алгоритм для Для каждого элемента- Начать цикл.
Можете мне рассказать об алгоритме обхода по Вашему методу? То есть каким образом он сумеет перейти по всем ссылкам сайта, чтобы я понимал что это работает. А то, к сожалению, я не вижу как это решает задачу по обходу всех страниц.

[Antonio]

@romanbiz , ты все как-то усложняешь. Нет гарантий, что пройдешь по всем страницам. Пройдешь только по тем страницам, которые перелинкованы. Соответственно берешь те страницы, которые тебе уже известны и добавляешь их в список 1. Проходишь по ним и собираешь ссылки, сохраняешь в список 2 (может быть не за один проход, а как настроишь). Потом убираешь из списка 1 ссылки по которым прошел и переносишь их в список 3. Чистишь список 2 от дублей и вхождений строк из списка 3. Оставшееся переносишь в список 1. Повторяешь. Мне кажется, что тут принципиально нового не сделать ничего.

[ruzne]

@romanbiz
0_1520263883664_test.xml
вероятно это будет работать.

это лишшаблон необходимо добвавить нужные проверки и убрать лишние, так же проверить правильность формирования ссылок, в зависимости от того относительные они или абсолютные, а если го хистори не работает то заменить на загрузить страницу урл, он в том месте как раз востанавливается из стека
upd: там еще состояние forech нужно сохранять, но это домашняя работа, так же в стек

[romanbiz]

@Antonio Это очень неоптимальный алгоритм к сожалению. Все страницы перелинкованы, такова структура сайта.

[Antonio]

@romanbiz, если на сайте меньше 10000 страниц, то ты будешь думать дольше, чем таким образом ссылки пройдешь. Но я с интересом, конечно, почитаю, если кто-то предложит реальный и более оптимальный алгоритм.

[A Former User]

@romanbiz Меня тут мысль посетила, может можно карту сайта использовать? В ней по идее все есть в xml формате