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

[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 формате

[romanbiz]

@Denis_krsk Спасибо за мысль, я писал выше

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

[DrPrime]

Делаем ассоциированный массив
VAR_LINKS = {}

Делаем While цикл

while(true){
    VAR_TEMP_LINKS = []
    if(VAR_CYCLE_INDEX == 0)
    {
        //Тут собираем ссылки первый раз
    }else
    {
             //Проверка есть ли список для этой иттерации
            try{
             var a = VAR_LINKS[VAR_CYCLE_INDEX]
              }catch(e){
            _break()
            }
              Foreach(VAR_LINKS[VAR_CYCLE_INDEX])
                     //Парсим ссылки с каждой страницы в массив TEMP_LINKS
 
    }
        //Ложим в ассоц массив наш массив
         if(VAR_TEMP_LINKS.length  > 0) 
         VAR_LINKS[VAR_CYCLE_INDEX + 1 ] = VAR_TEMP_LINKS

}

За первый проход помещаем в массив спаршенных ссылок

VAR_LINKS = {
1:["ссылка1", "ссылка2"]
}

Следующий проход

VAR_LINKS = {
1:["ссылка1", "ссылка2"];
2:["ссылка3", "ссылка4"]
}

При этом в общем цикле еще делаем добавление в общий список и ресурс, а так же проверку перед переходом по ссылке, что бы много раз не переходить по тем же ссылкам.
Так же желательно поменять переменный cycle index
П.С.
Мог ошибиться в где то в синтаксисе с асоц массивами, лень искать скрипт в котором этом реализовано, но факт того что это рабочее - подтверждаю на личном опыте. Делал такой "ПАУК" для одной соц сети, что собирать друзей друзей * N раз

[romanbiz]

@DrPrime Огромнейшее спасибо за ответ! Буду завтра разбирать