Entwerfen eines Webcrawlers

72

Ich bin auf eine Interviewfrage gestoßen: "Wenn Sie einen Webcrawler entwerfen würden, wie würden Sie vermeiden, in Endlosschleifen zu geraten?", Und ich versuche, sie zu beantworten.

Wie fängt alles von vorne an? Angenommen, Google hat mit einigen Hub-Seiten begonnen, von denen Hunderte (wie diese Hub-Seiten überhaupt gefunden wurden, ist eine andere Unterfrage). Wenn Google Links von einer Seite usw. folgt, erstellt es weiterhin eine Hash-Tabelle, um sicherzustellen, dass es nicht den zuvor besuchten Seiten folgt.

Was ist, wenn dieselbe Seite in diesen Tagen zwei Namen (URLs) hat, wenn wir URL-Shortener usw. haben?

Ich habe Google als Beispiel genommen. Obwohl Google nicht bekannt gibt, wie seine Webcrawler-Algorithmen, das Seitenranking usw. funktionieren, gibt es Vermutungen?

data-structures search-engine web-crawler google-search large-data-volumes xyz
quelle

Antworten:

83

Wenn Sie eine detaillierte Antwort erhalten möchten, lesen Sie Abschnitt 3.8 dieses Dokuments , in dem der URL-Test eines modernen Schabers beschrieben wird:

Beim Extrahieren von Links stößt jeder Webcrawler auf mehrere Links zu demselben Dokument. Um zu vermeiden, dass ein Dokument mehrmals heruntergeladen und verarbeitet wird, muss für jeden extrahierten Link ein URL-Test durchgeführt werden, bevor er zur URL-Grenze hinzugefügt wird. (Ein alternatives Design wäre, stattdessen den URL-gesehenen Test durchzuführen, wenn die URL von der Grenze entfernt wird, aber dieser Ansatz würde zu einer viel größeren Grenze führen.)

Um den URL-gesehenen Test durchzuführen, speichern wir alle von Mercator gesehenen URLs in kanonischer Form in einer großen Tabelle, die als URL-Satz bezeichnet wird. Auch hier gibt es zu viele Einträge, als dass sie alle in den Speicher passen könnten. Daher wird der URL-Satz wie der Fingerabdrucksatz des Dokuments größtenteils auf der Festplatte gespeichert.

Um Platz zu sparen, speichern wir nicht die Textdarstellung jeder URL im URL-Satz, sondern eine Prüfsumme mit fester Größe. Im Gegensatz zu den Fingerabdrücken, die im Dokumentfingerabdrucksatz des inhaltlichen Tests angezeigt werden, weist der gegen den URL-Satz getestete URL-Stream eine nicht triviale Lokalität auf. Um die Anzahl der Vorgänge für die Sicherungsdatenträgerdatei zu verringern, wird daher ein speicherinterner Cache mit gängigen URLs gespeichert. Die Intuition für diesen Cache ist, dass Links zu einigen URLs häufig vorkommen. Das Zwischenspeichern der beliebten URLs im Speicher führt daher zu einer hohen Trefferquote im Speicher.

Tatsächlich erreichen wir mit einem In-Memory-Cache von 2 ^ 18 Einträgen und der LRU-ähnlichen Taktersatzrichtlinie eine Gesamttrefferquote im In-Memory-Cache von 66,2% und eine Trefferquote von 9,5% in der Tabelle von kürzlich hinzugefügte URLs für eine Netto-Trefferquote von 75,7%. Von den 24,3% der Anfragen, die sowohl im Cache beliebter URLs als auch in der Tabelle der kürzlich hinzugefügten URLs fehlen, führen etwa 1 = 3 zu Treffern im Puffer unserer Dateiimplementierung mit wahlfreiem Zugriff, die sich ebenfalls im Benutzerbereich befindet. Das Nettoergebnis all dieser Pufferung ist, dass jeder Mitgliedschaftstest, den wir für den URL-Satz durchführen, zu durchschnittlich 0,16 Such- und 0,17 Lesekernelaufrufen führt (von denen ein Teil aus den Dateisystempuffern des Kernels bereitgestellt wird). Daher führt jeder Mitgliedschaftstest für URL-Sätze zu einem Sechstel so vieler Kernelaufrufe wie ein Mitgliedschaftstest für den Dokumentfingerabdrucksatz.

Grundsätzlich hashen sie alle URLs mit einer Hashing-Funktion, die eindeutige Hashes für jede URL garantiert. Aufgrund der Lokalität der URLs ist es sehr einfach, URLs zu finden. Google hat sogar seine Hashing-Funktion als Open-Source- Version bereitgestellt : CityHash

WARNUNG!
Sie könnten auch über Bot-Fallen sprechen !!! Ein Bot-Trap ist ein Abschnitt einer Seite, der ständig neue Links mit eindeutigen URLs generiert. Wenn Sie den Links folgen, die von dieser Seite bereitgestellt werden, werden Sie im Wesentlichen in einer "Endlosschleife" gefangen. Dies ist nicht gerade eine Schleife, da eine Schleife das Ergebnis des Besuchs derselben URL wäre, aber es ist eine unendliche Kette von URLs, die Sie nicht crawlen sollten.

Update 13.12.2012 - der Tag nach dem Ende der Welt :)

Per Fr0zenFyrs Kommentar: Wenn man den AOPIC- Algorithmus zur Auswahl von Seiten verwendet, ist es ziemlich einfach, Bot-Fallen der Endlosschleifenart zu vermeiden. Hier ist eine Zusammenfassung der Funktionsweise von AOPIC:

  1. Holen Sie sich einen Satz von N Startseiten.
  2. Weisen Sie jeder Seite X Guthaben zu, sodass jede Seite X / N-Guthaben (dh das gleiche Guthaben) hat, bevor das Crawlen gestartet wird.
  3. Wählen Sie eine Seite P aus, auf der das P den höchsten Kreditbetrag aufweist (oder wenn alle Seiten den gleichen Kreditbetrag haben, crawlen Sie eine zufällige Seite).
  4. Crawl-Seite P (Nehmen wir an, P hatte beim Crawlen 100 Credits).
  5. Extrahieren Sie alle Links von Seite P (sagen wir, es gibt 10 davon).
  6. Setzen Sie die Credits von P auf 0.
  7. Nehmen Sie eine 10% ige "Steuer" und ordnen Sie sie einer Lambda-Seite zu.
  8. Weisen Sie jedem auf Seite P gefundenen Link aus dem ursprünglichen Guthaben von P die gleiche Anzahl an Gutschriften zu - die Steuer: also (100 (P-Gutschriften) - 10 (10% Steuer)) / 10 (Links) = 9 Gutschriften pro Link.
  9. Wiederholen Sie ab Schritt 3.

Da die Lambda-Seite kontinuierlich Steuern erhebt, wird sie letztendlich die Seite mit dem größten Guthaben sein und wir müssen sie "crawlen". Ich sage "crawlen" in Anführungszeichen, da wir keine HTTP-Anfrage für die Lambda-Seite stellen, sondern nur die Credits nehmen und sie gleichmäßig auf alle Seiten in unserer Datenbank verteilen .

Da Bot-Traps nur interne Links gutschreiben und selten von außen gutgeschrieben werden, werden sie kontinuierlich Gutschriften (aus Steuern) an die Lambda-Seite weiterleiten. Die Lambda-Seite verteilt diese Credits gleichmäßig auf alle Seiten in der Datenbank, und bei jedem Zyklus verliert die Bot-Trap-Seite immer mehr Credits, bis sie so wenig Credits hat, dass sie fast nie wieder gecrawlt wird. Dies ist bei guten Seiten nicht der Fall, da sie häufig Credits von Backlinks erhalten, die auf anderen Seiten gefunden wurden. Dies führt auch zu einem dynamischen Seitenrang. Sie werden feststellen, dass die Seiten jedes Mal, wenn Sie einen Schnappschuss Ihrer Datenbank erstellen, nach der Anzahl der Credits sortieren, die sie haben, höchstwahrscheinlich grob nach ihrem tatsächlichen Seitenrang sortiert werden .

Dies vermeidet nur Bot-Fallen der Endlosschleife, aber es gibt viele andere Bot-Fallen, auf die Sie achten sollten, und es gibt auch Möglichkeiten, sie zu umgehen .

Kiril
quelle
Hervorragende Erklärung. Ich hatte die gleiche Frage zu Loops (wurde oben beantwortet) und Bot-Fallen (immer noch auf der Suche nach einem guten Weg, um herumzukommen). Ich hätte CityHash zusätzlich +1 gegeben, wenn SO es mir erlaubt hätte. Prost;)
Fr0zenFyr
@ Fr0zenFyr Sie müssen sich keine Gedanken über Bot-Traps der Endlosschleifenart machen, insbesondere wenn Sie den AOPIC- Algorithmus zum Auswählen von URLs zum Crawlen verwenden. Ich werde meine Antwort etwas detaillierter aktualisieren.
Kiril
@ Fr0zenFyr Der beste Weg, um Bot-Fallen zu vermeiden, ist höflich zu kriechen. Andernfalls müssen Sie sich alle Möglichkeiten ansehen, wie Sie gefangen werden und sie umgehen können. Das heißt, Sie müssen grundsätzlich einen Browser implementieren, Proxys verwenden und mehrere Browser imitieren, indem Sie die Benutzeragenten wechseln (gemäß der Browser-Nutzungsstatistik )
Kiril
Mein aktuelles Modell folgt vollständig robots.txt, no-follow usw. und führt kein aggressives Crawlen durch. Vielen Dank für das Update Ihres Beitrags. Ich werde Ihren Vorschlag zu AOPIC versuchen. Übrigens, Maya Kalender Tag ist 21Dec2012 [rollende Augen] ..;)
Fr0zenFyr
1
@raju, das nicht bei jedem Zyklus passiert, sondern nur, wenn Sie das Lambda "kriechen". Das "Kriechen" des Lambda sollte nicht sehr oft vorkommen und Sie können es asynchron tun. Es muss nicht in Echtzeit geschehen, es muss nur irgendwann geschehen.
Kiril
7

Während alle hier bereits vorgeschlagen haben, wie Sie Ihren Webcrawler erstellen, ordnet Google die Seiten wie folgt ein.

Google gibt jeder Seite einen Rang basierend auf der Anzahl der Rückruf-Links (wie viele Links auf anderen Websites auf eine bestimmte Website / Seite verweisen). Dies wird als Relevanzbewertung bezeichnet. Dies basiert auf der Tatsache, dass eine Seite, auf die viele andere Seiten verlinkt sind, wahrscheinlich eine wichtige Seite ist.

Jede Site / Seite wird als Knoten in einem Diagramm angezeigt. Links zu anderen Seiten sind gerichtete Kanten. Ein Grad eines Scheitelpunkts ist definiert als die Anzahl der eingehenden Kanten. Knoten mit einer höheren Anzahl eingehender Kanten werden höher eingestuft.

So wird der PageRank ermittelt. Angenommen, diese Seite Pj hat Lj-Links. Wenn einer dieser Links zur Seite Pi führt, gibt Pj 1 / Lj seiner Bedeutung an Pi weiter. Das Wichtigkeitsranking von Pi ist dann die Summe aller Beiträge von Seiten, die darauf verlinken. Wenn wir also die Menge der Seiten bezeichnen, die durch Bi mit Pi verknüpft sind, dann haben wir diese Formel:

Importance(Pi)= sum( Importance(Pj)/Lj ) for all links from Pi to Bi

Die Ränge werden in eine Matrix gestellt, die als Hyperlink-Matrix bezeichnet wird: H [i, j]

Eine Zeile in dieser Matrix ist entweder 0 oder 1 / Lj, wenn eine Verbindung von Pi zu Bi besteht. Eine weitere Eigenschaft dieser Matrix ist, dass wir 1 erhalten, wenn wir alle Zeilen in einer Spalte summieren.

Jetzt müssen wir diese Matrix mit einem Eigenvektor namens I (mit dem Eigenwert 1) multiplizieren, so dass:

I = H*I

Jetzt beginnen wir zu iterieren: I H, I I H, I I I H .... I ^ k * H, bis die Lösung konvergiert. dh wir erhalten in Schritt k und k + 1 so ziemlich die gleichen Zahlen in der Matrix.

Was jetzt im I-Vektor übrig bleibt, ist die Wichtigkeit jeder Seite.

Ein einfaches Beispiel für Hausaufgaben finden Sie unter http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html

Um das doppelte Problem in Ihrer Interviewfrage zu lösen, führen Sie eine Prüfsumme auf der gesamten Seite durch und verwenden Sie entweder diese oder eine Bash der Prüfsumme als Schlüssel in einer Karte, um die besuchten Seiten zu verfolgen.

Adrian
quelle
1
Die Prüfsumme kann unterschiedlich sein, wenn die Seite dynamischen Inhalt ausspuckt.
Edocetirwi
@edocetirwi guter Punkt, ich denke, Sie müssten nach etwas anderem suchen oder es mit der URL auf eine sinnvolle Weise kombinieren
Adrian
oh, also integrierst du einfach über das hyperlink matrixwas die abmessungen every-webpage-on-the-internetx hat every-webpage-on-the-internet. Einfach?!? Wie macht man das genau (angesichts seiner sehr spärlichen Matrix)?
CpILL
@CpILL Sie sind 7 Jahre zu spät, aber es gibt clevere Möglichkeiten, große Matrizen zu multiplizieren, ohne in die Luft zu jagen. Wenn Sie eine produktionsbereite Lösung wünschen, bin ich bereit, die Zahlung zu akzeptieren
Adrian
@Adrian Ich bin mir sicher, dass du es bist ... aber ich habe bemerkt, dass es hauptsächlich Entwickler von Stackoverflow sind und wir machen es gerne selbst, deshalb sind wir hier! : D
CpILL
1

Kommt darauf an, wie tief ihre Frage sein sollte. Wenn sie nur versuchen wollten, nicht denselben Links hin und her zu folgen, wäre es ausreichend, die URLs zu hashen.

Was ist mit Inhalten, die buchstäblich Tausende von URLs enthalten, die zu demselben Inhalt führen? Wie ein QueryString-Parameter, der nichts beeinflusst, aber unendlich viele Iterationen haben kann. Ich nehme an, Sie könnten auch den Inhalt der Seite hashen und URLs vergleichen, um festzustellen, ob sie dem Abfangen von Inhalten ähneln, die durch mehrere URLs identifiziert werden. Siehe zum Beispiel Bot-Fallen, die in @ Liriks Beitrag erwähnt wurden.

mellamokb
quelle
Dies bringt mich zu einer anderen Frage, die ich hatte. Wie haben wir den gesamten Inhalt einer Seite gehasht? Solche Seiten sind mindestens 2 Pager. Welche Art von Hash-Funktionen können 2 Pager auf einen einzigen Wert hashen? Wie groß ist eine typische Hash-Ausgabe?
XYZ
0

Sie müssten eine Art Hash-Tabelle haben, in der die Ergebnisse gespeichert werden. Sie müssten sie nur vor jedem Laden der Seite überprüfen.

Chuchu
quelle
0

Das Problem hierbei ist nicht, doppelte URLs zu crawlen, die durch einen Index unter Verwendung eines aus URLs erhaltenen Hashs behoben werden. Das Problem besteht darin, DUPLICATED CONTENT zu crawlen. Jede URL einer "Crawler-Falle" ist anders (Jahr, Tag, Sitzungs-ID ...).

Es gibt keine "perfekte" Lösung ... aber Sie können einige dieser Strategien anwenden:

• Behalten Sie ein Feld bei, in dem sich die URL auf der Website befindet. Erhöhen Sie für jeden Artikel, in dem URLs von einer Seite abgerufen werden, die Stufe. Es wird wie ein Baum sein. Sie können aufhören, auf einer bestimmten Ebene wie 10 zu crawlen (ich denke, Google verwendet dies).

• Sie können versuchen, eine Art HASH zu erstellen, die verglichen werden kann, um ähnliche Dokumente zu finden, da Sie nicht mit jedem Dokument in Ihrer Datenbank vergleichen können. Es gibt SimHash von Google, aber ich konnte keine Implementierung finden, die ich verwenden könnte. Dann habe ich meine eigenen erstellt. Mein Hash zählt nieder- und hochfrequente Zeichen im HTML-Code und generiert einen 20-Byte-Hash, der mit einem kleinen Cache der zuletzt gecrawlten Seiten in einem AVLTree mit einer NearNeighbors-Suche mit einer gewissen Toleranz (ca. 2) verglichen wird. Sie können keinen Verweis auf Zeichenpositionen in diesem Hash verwenden. Nachdem Sie die Falle "erkannt" haben, können Sie das URL-Muster des doppelten Inhalts aufzeichnen und damit auch Seiten ignorieren.

• Wie bei Google können Sie für jede Website ein Ranking erstellen und mehr als einer anderen "vertrauen".

Lexmooze
quelle
0

Der Crawler verwaltet einen URL-Pool, der alle zu crawlenden URLs enthält. Um eine „Endlosschleife“ zu vermeiden, sollten Sie vor dem Hinzufügen zum Pool die Existenz jeder URL überprüfen.

Dies ist jedoch nicht einfach zu implementieren, wenn das System auf ein bestimmtes Niveau skaliert wurde. Der naive Ansatz besteht darin, alle URLs in einem Hashset zu halten und die Existenz jeder neuen URL zu überprüfen. Dies funktioniert nicht, wenn zu viele URLs vorhanden sind, um in den Speicher zu passen.

Hier gibt es einige Lösungen. Anstatt beispielsweise alle URLs im Speicher zu speichern, sollten wir sie auf der Festplatte behalten. Um Platz zu sparen, sollte anstelle der unformatierten URL ein URL-Hash verwendet werden. Es ist auch erwähnenswert, dass wir die kanonische Form der URL anstelle der ursprünglichen beibehalten sollten. Wenn die URL also durch Dienste wie bit.ly gekürzt wird, ist es besser, die endgültige URL zu erhalten. Um den Überprüfungsprozess zu beschleunigen, kann eine Cache-Schicht erstellt werden. Oder Sie können es als verteiltes Cache-System betrachten, das ein separates Thema ist.

Der Beitrag Build a Web Crawler enthält eine detaillierte Analyse dieses Problems.

Kennzeichen
quelle
0

Ich musste auch Crawler verwenden und kann keinen geeigneten für meine Anforderung finden. Danach habe ich eine grundlegende Crawler-Bibliothek entwickelt, um einfache Anforderungen zu implementieren. Aber es ermöglicht, fast alle Prinzipien des Crawlers zu erfüllen. Sie können das DotnetCrawler-Github-Repo überprüfen, das Downloader-Processor-Pipeline-Module mit Standardimplementierung mithilfe von Entity Framework Core selbst implementiert, um Daten in SQL Server zu speichern.

https://github.com/mehmetozkaya/DotnetCrawler

Mehmet Özkaya
quelle
0

Der Webcrawler ist ein Computerprogramm, mit dem folgende Schlüsselwerte (HREF-Links, Bildlinks, Metadaten usw.) von der angegebenen Website-URL erfasst / gecrawlt werden. Es ist wie intelligent gestaltet, um verschiedenen HREF-Links zu folgen, die bereits von der vorherigen URL abgerufen wurden. Auf diese Weise kann Crawler von einer Website zu anderen Websites springen. Normalerweise wird es als Webspinne oder Webbot bezeichnet. Dieser Mechanismus fungiert immer als Rückgrat der Websuchmaschine.

Den Quellcode finden Sie in meinem Tech-Blog - http://www.algonuts.info/how-to-built-a-simple-web-crawler-in-php.html

<?php
class webCrawler
{
    public $siteURL;
    public $error;

    function __construct()
    {
        $this->siteURL = "";
        $this->error = "";
    }

    function parser()   
    {
        global $hrefTag,$hrefTagCountStart,$hrefTagCountFinal,$hrefTagLengthStart,$hrefTagLengthFinal,$hrefTagPointer;
        global $imgTag,$imgTagCountStart,$imgTagCountFinal,$imgTagLengthStart,$imgTagLengthFinal,$imgTagPointer;
        global $Url_Extensions,$Document_Extensions,$Image_Extensions,$crawlOptions;

        $dotCount = 0;
        $slashCount = 0;
        $singleSlashCount = 0;
        $doubleSlashCount = 0;
        $parentDirectoryCount = 0;

        $linkBuffer = array();

        if(($url = trim($this->siteURL)) != "")
        {
            $crawlURL = rtrim($url,"/");
            if(($directoryURL = dirname($crawlURL)) == "http:")
            {   $directoryURL = $crawlURL;  }
            $urlParser = preg_split("/\//",$crawlURL);

            //-- Curl Start --
            $curlObject = curl_init($crawlURL);
            curl_setopt_array($curlObject,$crawlOptions);
            $webPageContent = curl_exec($curlObject);
            $errorNumber = curl_errno($curlObject);
            curl_close($curlObject);
            //-- Curl End --

            if($errorNumber == 0)
            {
                $webPageCounter = 0;
                $webPageLength = strlen($webPageContent);
                while($webPageCounter < $webPageLength)
                {
                    $character = $webPageContent[$webPageCounter];
                    if($character == "")
                    {   
                        $webPageCounter++;  
                        continue;
                    }
                    $character = strtolower($character);
                    //-- Href Filter Start --
                    if($hrefTagPointer[$hrefTagLengthStart] == $character)
                    {
                        $hrefTagLengthStart++;
                        if($hrefTagLengthStart == $hrefTagLengthFinal)
                        {
                            $hrefTagCountStart++;
                            if($hrefTagCountStart == $hrefTagCountFinal)
                            {
                                if($hrefURL != "")
                                {
                                    if($parentDirectoryCount >= 1 || $singleSlashCount >= 1 || $doubleSlashCount >= 1)
                                    {
                                        if($doubleSlashCount >= 1)
                                        {   $hrefURL = "http://".$hrefURL;  }
                                        else if($parentDirectoryCount >= 1)
                                        {
                                            $tempData = 0;
                                            $tempString = "";
                                            $tempTotal = count($urlParser) - $parentDirectoryCount;
                                            while($tempData < $tempTotal)
                                            {
                                                $tempString .= $urlParser[$tempData]."/";
                                                $tempData++;
                                            }
                                            $hrefURL = $tempString."".$hrefURL;
                                        }
                                        else if($singleSlashCount >= 1)
                                        {   $hrefURL = $urlParser[0]."/".$urlParser[1]."/".$urlParser[2]."/".$hrefURL;  }
                                    }
                                    $host = "";
                                    $hrefURL = urldecode($hrefURL);
                                    $hrefURL = rtrim($hrefURL,"/");
                                    if(filter_var($hrefURL,FILTER_VALIDATE_URL) == true)
                                    {   
                                        $dump = parse_url($hrefURL);
                                        if(isset($dump["host"]))
                                        {   $host = trim(strtolower($dump["host"]));    }
                                    }
                                    else
                                    {
                                        $hrefURL = $directoryURL."/".$hrefURL;
                                        if(filter_var($hrefURL,FILTER_VALIDATE_URL) == true)
                                        {   
                                            $dump = parse_url($hrefURL);    
                                            if(isset($dump["host"]))
                                            {   $host = trim(strtolower($dump["host"]));    }
                                        }
                                    }
                                    if($host != "")
                                    {
                                        $extension = pathinfo($hrefURL,PATHINFO_EXTENSION);
                                        if($extension != "")
                                        {
                                            $tempBuffer ="";
                                            $extensionlength = strlen($extension);
                                            for($tempData = 0; $tempData < $extensionlength; $tempData++)
                                            {
                                                if($extension[$tempData] != "?")
                                                {   
                                                    $tempBuffer = $tempBuffer.$extension[$tempData];
                                                    continue;
                                                }
                                                else
                                                {
                                                    $extension = trim($tempBuffer);
                                                    break;
                                                }
                                            }
                                            if(in_array($extension,$Url_Extensions))
                                            {   $type = "domain";   }
                                            else if(in_array($extension,$Image_Extensions))
                                            {   $type = "image";    }
                                            else if(in_array($extension,$Document_Extensions))
                                            {   $type = "document"; }
                                            else
                                            {   $type = "unknown";  }
                                        }
                                        else
                                        {   $type = "domain";   }

                                        if($hrefURL != "")
                                        {
                                            if($type == "domain" && !in_array($hrefURL,$this->linkBuffer["domain"]))
                                            {   $this->linkBuffer["domain"][] = $hrefURL;   }
                                            if($type == "image" && !in_array($hrefURL,$this->linkBuffer["image"]))
                                            {   $this->linkBuffer["image"][] = $hrefURL;    }
                                            if($type == "document" && !in_array($hrefURL,$this->linkBuffer["document"]))
                                            {   $this->linkBuffer["document"][] = $hrefURL; }
                                            if($type == "unknown" && !in_array($hrefURL,$this->linkBuffer["unknown"]))
                                            {   $this->linkBuffer["unknown"][] = $hrefURL;  }
                                        }
                                    }
                                }
                                $hrefTagCountStart = 0;
                            }
                            if($hrefTagCountStart == 3)
                            {
                                $hrefURL = "";
                                $dotCount = 0;
                                $slashCount = 0;
                                $singleSlashCount = 0;
                                $doubleSlashCount = 0;
                                $parentDirectoryCount = 0;
                                $webPageCounter++;
                                while($webPageCounter < $webPageLength)
                                {
                                    $character = $webPageContent[$webPageCounter];
                                    if($character == "")
                                    {   
                                        $webPageCounter++;  
                                        continue;
                                    }
                                    if($character == "\"" || $character == "'")
                                    {
                                        $webPageCounter++;
                                        while($webPageCounter < $webPageLength)
                                        {
                                            $character = $webPageContent[$webPageCounter];
                                            if($character == "")
                                            {   
                                                $webPageCounter++;  
                                                continue;
                                            }
                                            if($character == "\"" || $character == "'" || $character == "#")
                                            {   
                                                $webPageCounter--;  
                                                break;  
                                            }
                                            else if($hrefURL != "")
                                            {   $hrefURL .= $character; }
                                            else if($character == "." || $character == "/")
                                            {
                                                if($character == ".")
                                                {
                                                    $dotCount++;
                                                    $slashCount = 0;
                                                }
                                                else if($character == "/")
                                                {
                                                    $slashCount++;
                                                    if($dotCount == 2 && $slashCount == 1)
                                                    $parentDirectoryCount++;
                                                    else if($dotCount == 0 && $slashCount == 1)
                                                    $singleSlashCount++;
                                                    else if($dotCount == 0 && $slashCount == 2)
                                                    $doubleSlashCount++;
                                                    $dotCount = 0;
                                                }
                                            }
                                            else
                                            {   $hrefURL .= $character; }
                                            $webPageCounter++;
                                        }
                                        break;
                                    }
                                    $webPageCounter++;
                                }
                            }
                            $hrefTagLengthStart = 0;
                            $hrefTagLengthFinal = strlen($hrefTag[$hrefTagCountStart]);
                            $hrefTagPointer =& $hrefTag[$hrefTagCountStart];
                        }
                    }
                    else
                    {   $hrefTagLengthStart = 0;    }
                    //-- Href Filter End --
                    //-- Image Filter Start --
                    if($imgTagPointer[$imgTagLengthStart] == $character)
                    {
                        $imgTagLengthStart++;
                        if($imgTagLengthStart == $imgTagLengthFinal)
                        {
                            $imgTagCountStart++;
                            if($imgTagCountStart == $imgTagCountFinal)
                            {
                                if($imgURL != "")
                                {
                                    if($parentDirectoryCount >= 1 || $singleSlashCount >= 1 || $doubleSlashCount >= 1)
                                    {
                                        if($doubleSlashCount >= 1)
                                        {   $imgURL = "http://".$imgURL;    }
                                        else if($parentDirectoryCount >= 1)
                                        {
                                            $tempData = 0;
                                            $tempString = "";
                                            $tempTotal = count($urlParser) - $parentDirectoryCount;
                                            while($tempData < $tempTotal)
                                            {
                                                $tempString .= $urlParser[$tempData]."/";
                                                $tempData++;
                                            }
                                            $imgURL = $tempString."".$imgURL;
                                        }
                                        else if($singleSlashCount >= 1)
                                        {   $imgURL = $urlParser[0]."/".$urlParser[1]."/".$urlParser[2]."/".$imgURL;    }
                                    }
                                    $host = "";
                                    $imgURL = urldecode($imgURL);
                                    $imgURL = rtrim($imgURL,"/");
                                    if(filter_var($imgURL,FILTER_VALIDATE_URL) == true)
                                    {   
                                        $dump = parse_url($imgURL); 
                                        $host = trim(strtolower($dump["host"]));
                                    }
                                    else
                                    {
                                        $imgURL = $directoryURL."/".$imgURL;
                                        if(filter_var($imgURL,FILTER_VALIDATE_URL) == true)
                                        {   
                                            $dump = parse_url($imgURL); 
                                            $host = trim(strtolower($dump["host"]));
                                        }   
                                    }
                                    if($host != "")
                                    {
                                        $extension = pathinfo($imgURL,PATHINFO_EXTENSION);
                                        if($extension != "")
                                        {
                                            $tempBuffer ="";
                                            $extensionlength = strlen($extension);
                                            for($tempData = 0; $tempData < $extensionlength; $tempData++)
                                            {
                                                if($extension[$tempData] != "?")
                                                {   
                                                    $tempBuffer = $tempBuffer.$extension[$tempData];
                                                    continue;
                                                }
                                                else
                                                {
                                                    $extension = trim($tempBuffer);
                                                    break;
                                                }
                                            }
                                            if(in_array($extension,$Url_Extensions))
                                            {   $type = "domain";   }
                                            else if(in_array($extension,$Image_Extensions))
                                            {   $type = "image";    }
                                            else if(in_array($extension,$Document_Extensions))
                                            {   $type = "document"; }
                                            else
                                            {   $type = "unknown";  }
                                        }
                                        else
                                        {   $type = "domain";   }

                                        if($imgURL != "")
                                        {
                                            if($type == "domain" && !in_array($imgURL,$this->linkBuffer["domain"]))
                                            {   $this->linkBuffer["domain"][] = $imgURL;    }
                                            if($type == "image" && !in_array($imgURL,$this->linkBuffer["image"]))
                                            {   $this->linkBuffer["image"][] = $imgURL; }
                                            if($type == "document" && !in_array($imgURL,$this->linkBuffer["document"]))
                                            {   $this->linkBuffer["document"][] = $imgURL;  }
                                            if($type == "unknown" && !in_array($imgURL,$this->linkBuffer["unknown"]))
                                            {   $this->linkBuffer["unknown"][] = $imgURL;   }
                                        }
                                    }
                                }
                                $imgTagCountStart = 0;
                            }
                            if($imgTagCountStart == 3)
                            {
                                $imgURL = "";
                                $dotCount = 0;
                                $slashCount = 0;
                                $singleSlashCount = 0;
                                $doubleSlashCount = 0;
                                $parentDirectoryCount = 0;
                                $webPageCounter++;
                                while($webPageCounter < $webPageLength)
                                {
                                    $character = $webPageContent[$webPageCounter];
                                    if($character == "")
                                    {   
                                        $webPageCounter++;  
                                        continue;
                                    }
                                    if($character == "\"" || $character == "'")
                                    {
                                        $webPageCounter++;
                                        while($webPageCounter < $webPageLength)
                                        {
                                            $character = $webPageContent[$webPageCounter];
                                            if($character == "")
                                            {   
                                                $webPageCounter++;  
                                                continue;
                                            }
                                            if($character == "\"" || $character == "'" || $character == "#")
                                            {   
                                                $webPageCounter--;  
                                                break;  
                                            }
                                            else if($imgURL != "")
                                            {   $imgURL .= $character;  }
                                            else if($character == "." || $character == "/")
                                            {
                                                if($character == ".")
                                                {
                                                    $dotCount++;
                                                    $slashCount = 0;
                                                }
                                                else if($character == "/")
                                                {
                                                    $slashCount++;
                                                    if($dotCount == 2 && $slashCount == 1)
                                                    $parentDirectoryCount++;
                                                    else if($dotCount == 0 && $slashCount == 1)
                                                    $singleSlashCount++;
                                                    else if($dotCount == 0 && $slashCount == 2)
                                                    $doubleSlashCount++;
                                                    $dotCount = 0;
                                                }
                                            }
                                            else
                                            {   $imgURL .= $character;  }
                                            $webPageCounter++;
                                        }
                                        break;
                                    }
                                    $webPageCounter++;
                                }
                            }
                            $imgTagLengthStart = 0;
                            $imgTagLengthFinal = strlen($imgTag[$imgTagCountStart]);
                            $imgTagPointer =& $imgTag[$imgTagCountStart];
                        }
                    }
                    else
                    {   $imgTagLengthStart = 0; }
                    //-- Image Filter End --
                    $webPageCounter++;
                }
            }
            else
            {   $this->error = "Unable to proceed, permission denied";  }
        }
        else
        {   $this->error = "Please enter url";  }

        if($this->error != "")
        {   $this->linkBuffer["error"] = $this->error;  }

        return $this->linkBuffer;
    }   
}
?>
Karthikeyan Moorthy
quelle
1
Dies beantwortet die Frage nicht wirklich: "Wenn Sie einen Webcrawler entwerfen würden, wie würden Sie vermeiden, in Endlosschleifen zu geraten?" Bitte verbessern Sie Ihre Antwort.
Brian Tompsett -
Hallo Brain Sir, danke für die Kommentare. Eigentlich müssen wir eine Instanz für diese Klasse erstellen und können uns dann für die Verwendung bewerben.
Karthikeyan Moorthy
-1

Nun, das Web ist im Grunde ein gerichtetes Diagramm. Sie können also ein Diagramm aus den URLs erstellen und dann eine BFS- oder DFS-Durchquerung durchführen, während Sie die besuchten Knoten markieren, damit Sie nicht zweimal dieselbe Seite besuchen.

Pepe
quelle
3
Aber wie konstruieren Sie den Graphen überhaupt? Wenn wir keine doppelten Knoten wollen, dh wir wollen nur einen Knoten für eine URL, dann brauchen Sie wieder eine Möglichkeit, ein Duplikat zu erkennen und zu verwerfen, während Sie das Diagramm selbst konstruieren.
xyz
@learnerforever hmmm ja das ist wahr ... Ich habe ehrlich gesagt nur einen einfachen Crawler geschrieben, der nur etwa 100 Links handhabte, so dass es kein großes Problem war, tatsächlich auf jede Seite zu gehen. Aber ja, ich kann die Probleme sehen, die auftreten, wenn Sie dies auf das gesamte Web anwenden. Liriks Papier scheint sich jedoch zu lohnen ...
Pepe
-1

Dies ist ein Webcrawler-Beispiel. Hiermit können Mac-Adressen für Mac-Spoofing gesammelt werden.

#!/usr/bin/env python

import sys
import os
import urlparse
import urllib
from bs4 import BeautifulSoup

def mac_addr_str(f_data):
global fptr
global mac_list
word_array = f_data.split(" ")

    for word in word_array:
        if len(word) == 17 and ':' in word[2] and ':' in word[5] and ':' in word[8] and ':' in word[11] and ':' in word[14]:
            if word not in mac_list:
                mac_list.append(word)
                fptr.writelines(word +"\n")
                print word



url = "http://stackoverflow.com/questions/tagged/mac-address"

url_list = [url]
visited = [url]
pwd = os.getcwd();
pwd = pwd + "/internet_mac.txt";

fptr = open(pwd, "a")
mac_list = []

while len(url_list) > 0:
    try:
        htmltext = urllib.urlopen(url_list[0]).read()
    except:
        url_list[0]
    mac_addr_str(htmltext)
    soup = BeautifulSoup(htmltext)
    url_list.pop(0)
    for tag in soup.findAll('a',href=True):
        tag['href'] = urlparse.urljoin(url,tag['href'])
        if url in tag['href'] and tag['href'] not in visited:
            url_list.append(tag['href'])
            visited.append(tag['href'])

Ändern Sie die URL, um weitere Websites zu crawlen. Viel Glück

ashish jha
quelle