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



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

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

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



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



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



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



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



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



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



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



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

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



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



  • @romanbiz

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


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

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



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

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

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



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

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



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



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



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

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



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



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



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


Log in to reply