Projekt Egor

Tento projekt implementuje základní dávkový crawler/robot pro stahování webového obsahu. Jeho podrobný popis je součástí přednášky NDBI041 na MFF UK.

Crawler postupuje v následujících krocích:

1. Všechny dosud známé URL jsou udržovány v setříděném seznamu, označme ho například existing.txt. V každém iteračním kroku se k tomuto seznamu sloučí nové příchozí URL, označme například incoming.txt. Všechna stažená data skončí ve výstupním souboru (označme stream.data). Při slučování seznamů incoming.txt a existing.txt se postupuje takto:
   1. URL existuje v obou seznamech, pak se stahuje jen tehdy, pokud se ho dosud nepodařilo stáhnout bez chyby
   2. URL existuje jen v seznamu existing.txt, pak se stahuje jen tehdy, pokud se ho dosud nepodařilo stáhnout bez chyby
   3. URL existuje jen v seznamu incoming.txt, pak se bude určitě činit pokus o jeho stažení
2. Všechny získané HTML dokumenty z předchozího kroku projdou extrakcí odkazů, vznikne nový seznam incoming.txt.
3. Soubor stream.data se odrotuje, abychom zbytečně neparsovali již zpracované HTML dokumenty.
4. Opakuj výše uvedené kroky.

Implementace

Celý crawler lze modulárně postavit z několika málo programů. Pomocí vhodných skriptů můžeme dostat implementaci pro jednouzlovou nebo distribuovanou instalaci, a mezi těmito instalacemi lze snadno přecházet. Nejhorší složitost dílčího kroku je O(n.log(n)), přičemž kroky pracující s největšími datovými objemy běží se složitostí O(n).

Jednouzlovou instalaci získáme nasazením skriptu:

./run.sh robot.Process -i incoming.txt -e existing.txt -o stream.data
./run.sh robot.HtmlParser -i stream.data -m -a | sort -t ' ' -k 2 -u >incoming.txt
gzip stream.data
mv stream.data.gz stream-`date +"%Y-%m-%d-%H-%M"`.gz
mv existing.txt-new existing.txt

Seznam incoming.txt obsahuje seznam URL v textovém formátu, kde každý řádek obsahuje jedno (úplné a normalizované) URL. Na začátku by měl být naplněn seznamem výchozích URL.

Naproti tomu existing.txt využívá zhuštěný zápis setříděného seznamu řetězců (textové reprezentace zápisu URL), kdy se nejprve zapisuje počet znaků shodných s předchozím řetězcem v seznamu a potom zbytek řetězce, počínaje za posledním shodným znakem. Konkrétně se tedy seznam {aaaa, aaba, abba, ace, acer} zapisuje jako:

• 0, "aaaa"
• 2, "ba"
• 1, "bba"
• 1, "ce"
• 3, "r"

Samotné řetězce se zapisují v Pascalském formátu (počet bytů řetězce, následovaných datovou reprezentací v UTF8 formátu). Pro převod do standardního textového seznamu řetězců můžete použít program BinaryItemsInput.

-- LeoGalambos - 04 Sep 2016