2

PythonでWebクローラーを実装しようとしています。これが私がこれまでに持っているものです：

import urllib2

seed=raw_input('Enter a url : ')

def getAllNewLinksOnPage(page,prevLinks):

response = urllib2.urlopen(page)
html = response.read()

links,pos,allFound=[],0,False
while not allFound:
    aTag=html.find("<a href=",pos)
    if aTag>-1:
        href=html.find('"',aTag+1)
        endHref=html.find('"',href+1)
        url=html[href+1:endHref]
        if url[:7]=="http://":
            if url[-1]=="/":
                url=url[:-1]
            if not url in links and not url in prevLinks:
                links.append(url)     
                print url
        closeTag=html.find("</a>",aTag)
        pos=closeTag+1
    else:
        allFound=True   
return links

toCrawl=[seed]
crawled=[]
while toCrawl:
url=toCrawl.pop()
crawled.append(url)
newLinks=getAllNewLinksOnPage(url,crawled)
toCrawl=list(set(toCrawl)|set(newLinks))

print crawled

深度検索を実装して結果を並べ替える方法を考えていました。

4

1 に答える 1

4

これまでに実装したsetのは、クロールするリンクを保持しているため、一種のランダムな順序の検索です。(実際には を保持していますが、それを繰り返しlistに変換すると、set順序がどうであれスクランブルされます。)

これを深さ優先検索にするには、通常の解決策は再帰的に行うことです。そうすれば、クロールするリンクの外部ストレージは必要ありません。これまでにクロールされたリンクを追跡する必要はありますが、繰り返しを避けるためと、最後にリンクを並べ替える必要があるため (これには並べ替えるものが必要です)、それだけです。そう：

def crawl(seed):
    crawled = set()
    def crawl_recursively(link):
        if link in crawled:
            return
        newLinks = getAllLinksOnPage(link)
        crawled.add(seed)
        for link in newLinks:
            crawl_recursively(link)
    crawl_recursively(seed)
    return sorted(crawled)

再帰を使用したくない場合は、リンクの明示的なスタックを使用してクロールすることもできます。しかし、そのスタックを再編成し続けることはできません。または、スタックではなくなります。繰り返しますが、既にクロールされたリンクの別のセットは、検索の繰り返しを回避するという問題を解決します。

def crawl(seed):
    crawled = set()
    to_crawl = [seed]
    while to_crawl:
        link = to_crawl.pop()
        if link in crawled:
            continue
        crawled.add(link)
        newLinks = getAllLinksOnPage(link)
        to_crawl.extend(newLinks)
    return sorted(crawled)

スタックをキューに変える (1 行を に変更するだけto_crawl.pop(0)) と、これは幅優先検索になります。

to_crawlリピートだらけで大きくなりすぎるのが気になる場合は、途中で剥がしてもOK。深さ優先にしたかったので、新しいものではなく、後で積み上げられたものを取り除く必要があります。これを行う最も簡単な方法は、おそらくOrderedSet(たとえば、ドキュメントからリンクされたレシピ) を使用することです。collections

    to_crawl = OrderedSet()
    # …
        new_link_set = OrderedSet(newLinks)
        to_crawl -= new_link_set
        to_crawl |= new_link_set - crawled
于 2013-11-05T21:16:34.957 に答える