[Alg] Alle paden naar een bepaalde pagina vinden

[-FoX-]

Ik ben al een hele tijd aan het brainstormen over een manier om alle mogelijke paden naar een bepaalde webpagina te vinden, vanaf een bepaalde startpagina (meestal de home van een website).

Hier bestaan vast diverse technieken voor, maar ik wil het wiel ook niet weer gaan heruitvinden. Neem als voorbeeld een bepaald artikel op amazon.com. Hiervoor zijn diverse mogelijkheden om uiteindelijk op dit item uit te komen. En ik wil weten welke allemaal...

Eén manier is het crawlen van de webpagina en er op die manier alle mogelijke links uit filteren waarin de bepaalde pagina voorkomt. Ik heb me laten vertellen dat dit heel wat werk met zich mee brengt als je dit deftig wil laten werken voor elk mogelijke beschikbare website.
Om dan nog maar niet te spreken over de hardware die het nodig heeft en de tijd om dit te bereiken

De bedoeling is om hier uiteindelijk een implementatie voor te gaan voorzien (in Java), en ik heb dan ook een eerste blik geworpen op het Nutch project. Maar heb eigenlijk totaal geen zicht over hoeveel werk we hier precies spreken... Heeft iemand daar een goed zicht op, die hij ook goed kan onderbouwen

Lijkt me dus een hele opgave te zijn. Ik heb er iig een hele tijd over zitten denken, maar ben nog niet tot een goed besluit gekomen. Alle hints zijn meer dan welkom!!
Externe programma's die het werk voor me doen mag natuurlijk ook
Ik wil voorlopig nog alle opties even open houden

[H!GHGuY]

Je zal denk ik gebruik moeten maken van gerichte grafen. Elke pagina is een node en kan zowel verwijzen als verwezen worden. Uiteindelijk ga je op het net crawlen en zo je graaf opbouwen.

Wanneer je dan alle pagina's wil die verwijzen naar die node, kun je gewoon de juiste node selecteren en gegevens opvragen.

Wat heb je nodig:
- HTTP crawler en parser om de links eruit te halen
- graaf geschikt voor wat je wil
- veel geheugen

Ik wil er zeker bij vermelden dat je dit soort graaf eigenlijk impliciet in een databank kan opslaan. Bijvoorbeeld door

code:

links: INDEX | Link | Parsed
referrals: FromLinkINDEX | ToLinkINDEX

wat heb je dus nodig:
- HTTP crawler en parser om links eruit te halen
- DB die past bij jouw noden
- veel HD ruimte en geheugen

Best werk je multi-threaded.
Een ideetje: Elke thread haalt telkens (#threads) niet geparste links uit de DB. (Dit om te voorkomen dat 2 parsers dezelfde links gaan bekijken. Je houdt dus centraal bij welke thread wat doet) Hij selecteert dus een link die op dit moment niet bekeken wordt. Vraagt deze op en parset die.
Vervolgens voeg je de nieuwe links toe (als ze nog niet bestaan) en stop je de verwijzingen in je DB.

Ik zou van dit simpel concept (Vooral race-problemen en DB-access gerelateere problemen zie ik op dit moment) maximaal een week uittrekken in een high-level taal als Java/C# om de basis geklaard te zien.

Een andere manier is om 1 thread alle DB access te laten doen en de andere threads (crawling en parsing) aan te sturen. (eventueel mbv een threadpool) Gezien de latency op het WWW en de snelheid van de DB is de kans groot dat je break-even uitkomt qua workload.

De grootste suggestie van al:
www.google.com heeft de mogelijkheid om te zien welke pagina's linken naar een URL

[-FoX-]

Stel je het niet wat te simpel voor?

Er zijn namelijk heel wat problemen die kunnen voorkomen met crawlers alleen al:
• Crawler trap: wanneer een reeks web pagina’s ervoor zorgen dat een crawler een oneindig aantal verzoeken in moet dienen. Een techniek hiervoor kan zijn om een oneindige dynamische structuur te laten genereren zoals: http://domain.com/foo/bar/foo/bar/foo/...
• Traveling Salesman Problem (TSP): Eén van de bekende problemen in de computerwetenschappen op operationeel onderzoek. Een rechtstreekse manier om dit probleem op te lossen, is door alle mogelijkheden na te gaan, maar aangezien het aantal combinaties n! (faculteit n) bedraagt, lopen we al snel tegen een probleem aan.
• Grote pagina sets: Door een groot aantal pagina sets worden de files van de crawler snel erg groot hetgeen problemen kan opleveren omtrent trafiek en opslag.
• Sommige sites blokkeren bepaalde crawlers of prefereren niet gecrawld te worden door het toevoegen van een robots.txt bestand aan de site root.
• Het crawlen van websites brengt een grote load met zich mee voor de server.
Wie kan dit nog aanvullen?

Dan zijn er nog site's die hun links generen mbv javascript; wat met transactionele site's? Sites die gebruik maken van flash, applets, ajax, ... ?

Ik denk dus dat je met een weekje wel heel erg te kort zal schieten?!

Overigens, heb je een idee welke min. hardware requirements er nodig zijn om schaalbaar te kunnen crawlen. Ik had gedacht aan min. 1GB geheugen met een grote harddisk +100GB?

Ohja, met google is het wel mogelijk om directe links (link: site: tags) te vinden (als ze al geïndexeerd zijn tenminste); maar om alle mogelijke paden op te gaan halen zie ik nog niet direct zo zitten.

[-FoX-]

Niemand die nog nuttige toevoegingen kan aanbrengen?

[H!GHGuY]

-FoX- schreef op zaterdag 21 oktober 2006 @ 11:28:
Stel je het niet wat te simpel voor?

Er zijn namelijk heel wat problemen die kunnen voorkomen met crawlers alleen al:
• Crawler trap: wanneer een reeks web pagina’s ervoor zorgen dat een crawler een oneindig aantal verzoeken in moet dienen. Een techniek hiervoor kan zijn om een oneindige dynamische structuur te laten genereren zoals: http://domain.com/foo/bar/foo/bar/foo/...

Simpel opgelost: je itereert niet meer dan bvb 100 maal. Dat is meer dan genoeg voor een standaard website. Bovendien creert de persoon die de crawler trap maakt een behoorlijke load op zijn server.

• Traveling Salesman Problem (TSP): Eén van de bekende problemen in de computerwetenschappen op operationeel onderzoek. Een rechtstreekse manier om dit probleem op te lossen, is door alle mogelijkheden na te gaan, maar aangezien het aantal combinaties n! (faculteit n) bedraagt, lopen we al snel tegen een probleem aan.

Ik denk dat ik even verward ben. Wat wil je exact ?
TSP wil de kortste afstand tussen een gegeven aantal plaatsen. Heeft imo NIETS met jouw probleem te maken. Duik maar even in de grafentheorie, daar zijn waarschijnlijk zeer veel oplossingen voor jouw probleem.
- Stroomnetwerken om het aantal paden te bepalen uit je knoop. (stroomnetwerk met alle verbindingen waarde 1)
- Dijkstra, Bellman-Ford voor kortste afstanden vanuit 1 knoop
- Floyd-Warshall voor de kortste afstanden tussen ALLE knopenparen. O(n^3) algoritme!
- etc.

• Grote pagina sets: Door een groot aantal pagina sets worden de files van de crawler snel erg groot hetgeen problemen kan opleveren omtrent trafiek en opslag.

Je crawler houdt enkel bij: URL X onderzocht, URL Y niet onderzocht.
URL X linkt naar URL Y. Kan in een eenvoudige DB

• Sommige sites blokkeren bepaalde crawlers of prefereren niet gecrawld te worden door het toevoegen van een robots.txt bestand aan de site root.

Dan moet je je daar aan houden. Daarnaast is dit enkel een implementatiedetail.

• Het crawlen van websites brengt een grote load met zich mee voor de server.

Jouw server of de webserver? De webserver is er voor gemaakt. Bovendien is ook dit eenvoudig op te lossen. Tijdens het opslaan van de links, geef je aan elke link een random getal mee. Bij het ophalen vraag je een random range op (weerom #threads lang): SELECT TOP 10 FROM ... WHERE RANDOMNR > 127813

Wie kan dit nog aanvullen?

Dan zijn er nog site's die hun links generen mbv javascript; wat met transactionele site's? Sites die gebruik maken van flash, applets, ajax, ... ?

Ik denk dus dat je met een weekje wel heel erg te kort zal schieten?!

Ok, die week werk was enkel HTTP parsing.
Anderzijds zou ik me van die andere technieken niet veel aantrekken. Een doorsnee website bouwer weet dat hij zijn site met zulke technieken om zeep helpt voor bots. Bovendien bestaan er dan ook meestal wel alternatieven voor bots waarin de links wel allemaal mooi staan.

Overigens, heb je een idee welke min. hardware requirements er nodig zijn om schaalbaar te kunnen crawlen. Ik had gedacht aan min. 1GB geheugen met een grote harddisk +100GB?

1 ding geef ik je mee. Die crawler zal jaren kunnen draaien eer je een deftig resultaat krijgt. Als je weet hoeveel servers bvb Google heeft...

Ohja, met google is het wel mogelijk om directe links (link: site: tags) te vinden (als ze al geïndexeerd zijn tenminste); maar om alle mogelijke paden op te gaan halen zie ik nog niet direct zo zitten.

Je vergeet wel 1 ding: Alle wegen leiden naar Rome.
Zoals ik jouw probleem zie: "alle paden vinden naar een site" denk ik meteen aan het algo van Warshall (niet Floyd-Warshall) maar je moet beseffen dat je via Moskou ook een pad hebt naar Rome en via New-York -> Moskou ook.

Het WWW heet niet voor niets een WEB. Je kan ALTIJD via ELKE site passeren om naar de gekozen site te gaan. Denk maar aan dit eenvoudig voorbeeld: als ALLE websites langs maximaal 4 opeenvolgende links naar google linken en google linkt naar de gegeven website, dan linken alle websites op het hele web naar die site.

[Johnny]

-FoX- schreef op zaterdag 21 oktober 2006 @ 11:28:
• Sommige sites blokkeren bepaalde crawlers of prefereren niet gecrawld te worden door het toevoegen van een robots.txt bestand aan de site root.

Dat is vooral om te voorkomen dat de gegevens in een publieke databank terecht komen, maar dat betekent niet dat het verboden, of moeilijker is om de website te crawlen, het implementeren van robots.txt is is alleen maar meer werk.

• Het crawlen van websites brengt een grote load met zich mee voor de server.
Wie kan dit nog aanvullen?

Dat valt ook wel mee, je vraagt namelijk iedere pagina maar 1 keer op en geen Javascript, CSS, Flash en afbeeldingen, en je kan makkelijk een pauze tussen de bezoeken invoegen of een limiet instellen.

Dan zijn er nog site's die hun links generen mbv javascript; wat met transactionele site's? Sites die gebruik maken van flash, applets, ajax, ... ?

Ik denk dus dat je met een weekje wel heel erg te kort zal schieten?!

Als je die ook nog mee gaat rekenen dan zal het inderdaad wel lang duren, het is namelijk onmogelijk om alle mogelijke paden te vinden want ze kunnen ook vanaf afgeschermede pagina's, emails, favorieten enz. komen.

[4of9]

-FoX- schreef op zaterdag 21 oktober 2006 @ 11:28:
Stel je het niet wat te simpel voor?

Er zijn namelijk heel wat problemen die kunnen voorkomen met crawlers alleen al:
• Crawler trap: wanneer een reeks web pagina’s ervoor zorgen dat een crawler een oneindig aantal verzoeken in moet dienen. Een techniek hiervoor kan zijn om een oneindige dynamische structuur te laten genereren zoals: http://domain.com/foo/bar/foo/bar/foo/...
• Traveling Salesman Problem (TSP): Eén van de bekende problemen in de computerwetenschappen op operationeel onderzoek. Een rechtstreekse manier om dit probleem op te lossen, is door alle mogelijkheden na te gaan, maar aangezien het aantal combinaties n! (faculteit n) bedraagt, lopen we al snel tegen een probleem aan.
• Grote pagina sets: Door een groot aantal pagina sets worden de files van de crawler snel erg groot hetgeen problemen kan opleveren omtrent trafiek en opslag.
• Sommige sites blokkeren bepaalde crawlers of prefereren niet gecrawld te worden door het toevoegen van een robots.txt bestand aan de site root.
• Het crawlen van websites brengt een grote load met zich mee voor de server.
Wie kan dit nog aanvullen?

Dan zijn er nog site's die hun links generen mbv javascript; wat met transactionele site's? Sites die gebruik maken van flash, applets, ajax, ... ?

Ik denk dus dat je met een weekje wel heel erg te kort zal schieten?!

Overigens, heb je een idee welke min. hardware requirements er nodig zijn om schaalbaar te kunnen crawlen. Ik had gedacht aan min. 1GB geheugen met een grote harddisk +100GB?

Ohja, met google is het wel mogelijk om directe links (link: site: tags) te vinden (als ze al geïndexeerd zijn tenminste); maar om alle mogelijke paden op te gaan halen zie ik nog niet direct zo zitten.

Die server load valt op zich wel mee als je zorgt dat je in kunt stellen dat je bijvoorbeeld maar 1 pagina per 2 seconden op haalt. Iedere pagina ga je dan checken op links en daar loop je dan door heen.

Javascript link zijn ook nog wel te doen dmv regular expression, alleen er zijn erg veel uitzonderingen. Ik ben laatst bezig geweest voor mijn werk om een crawler te maken. Met regular expressions denk ik dat je zo'n 98% (gokje) van de links kunt vinden.

100 GB kan maar is niet nodig IMO. Je wilt alleen de links hebben niet de gehele pagina's. Je kunt een pagina na het parsen gewoon disposen. (ik parste in het geheugen) een flinke pagina is ook maar een paar 100 kb. Als je je linkjes in de database opslaat en checkt op dubbele linkjes kom je al een heel eind. (en de parent URL opslaan)

robots.txt is eenvoudig te parsen. Voor je begint kijk je of een robots.txt is, zo niet dan check je de meta tags index en follow. en als dan alles oke kun je beginnen met parsen.

Dat oneindige verzoek probleem ben ik ook tegen gekomen. Weet niet meer precies hoe het zat, maar je kunt natuurlijk een maximale diepte instellen bijvoorbeeld om te voorkomen dat je dit soort problemen krijgt.

Wat het zoeken naar alle paden naar een document, als je een database hebt kom je al een heel eind denk ik. (ik weet niet over hoeveel linkjes het gaat of wat voor sites en hoeveel)

[-FoX-]

H!GHGuY schreef op zondag 22 oktober 2006 @ 11:38:Simpel opgelost: je itereert niet meer dan bvb 100 maal. Dat is meer dan genoeg voor een standaard website. Bovendien creert de persoon die de crawler trap maakt een behoorlijke load op zijn server.

Een crawler trap hoeft niet bewust gemaakt te zijn, maar kan wel. Hier tegen moet ik me dus gaan beschermen; niet meer dan 100x itereren is wel een mogelijkheid, maar vind ikzelf niet echt een nette oplossing.

Ik denk dat ik even verward ben. Wat wil je exact ?
TSP wil de kortste afstand tussen een gegeven aantal plaatsen. Heeft imo NIETS met jouw probleem te maken. Duik maar even in de grafentheorie, daar zijn waarschijnlijk zeer veel oplossingen voor jouw probleem.
- Stroomnetwerken om het aantal paden te bepalen uit je knoop. (stroomnetwerk met alle verbindingen waarde 1)
- Dijkstra, Bellman-Ford voor kortste afstanden vanuit 1 knoop
- Floyd-Warshall voor de kortste afstanden tussen ALLE knopenparen. O(n^3) algoritme!
- etc.

TSP heeft niet direct iets met dit probleem te maken; maar ik wil wel graag weten als ik op een dood knooppunt terecht kom.

Jouw server of de webserver? De webserver is er voor gemaakt. Bovendien is ook dit eenvoudig op te lossen. Tijdens het opslaan van de links, geef je aan elke link een random getal mee. Bij het ophalen vraag je een random range op (weerom #threads lang): SELECT TOP 10 FROM ... WHERE RANDOMNR > 127813

Mijn server, de crawler dus. Ik wil namelijk nu al een inschatting kunnen maken welke server hiervoor nodig zal zijn en hoe lang het gemiddeld zal duren om een site van bvb 1.000 pagina's te crawlen. Ik vermoed dat vooral memory en cpu usage van belang zullen zijn; data opslag ook wel, maar in mindere mate aangezien ik de pagina's niet moet cachen, e.d. aangezien er toch geen zoekacties op uitgevoerd zullen worden. Wat zou jij voorstellen als min. server specificatie voor dergelijk systeem?

Ok, die week werk was enkel HTTP parsing.
Anderzijds zou ik me van die andere technieken niet veel aantrekken. Een doorsnee website bouwer weet dat hij zijn site met zulke technieken om zeep helpt voor bots. Bovendien bestaan er dan ook meestal wel alternatieven voor bots waarin de links wel allemaal mooi staan.

Een maand lijkt me realistischer als ik het zo bekijk, maar misschien kom ik daar zelfs niet mee toe en stuit ik op een heleboel andere problemen.
- transactionele site's bvb
- anchor links
- escape karakters, ...
om zo maar even enkele out-of-the-blue te noemen...?

Je vergeet wel 1 ding: Alle wegen leiden naar Rome.
Zoals ik jouw probleem zie: "alle paden vinden naar een site" denk ik meteen aan het algo van Warshall (niet Floyd-Warshall) maar je moet beseffen dat je via Moskou ook een pad hebt naar Rome en via New-York -> Moskou ook.

Het WWW heet niet voor niets een WEB. Je kan ALTIJD via ELKE site passeren om naar de gekozen site te gaan. Denk maar aan dit eenvoudig voorbeeld: als ALLE websites langs maximaal 4 opeenvolgende links naar google linken en google linkt naar de gegeven website, dan linken alle websites op het hele web naar die site.

Het is ook niet de bedoeling om ALLE paden naar een site te vinden; maar wel om 1 bepaald item/page binnen 1 site te vinden. In grote websites zijn er verschillende manieren om tot een bepaalde pagina te komen, en hetgeen ik wil weten is welke?
Maar ik denk niet dat google een goed aanspreekpunt kan zijn, omdat we er rekening mee moeten houden dat bepaalde (nieuwe) paginas nog niet geïndexeerd werden.

4of9 schreef op zondag 22 oktober 2006 @ 11:46:
Dat oneindige verzoek probleem ben ik ook tegen gekomen. Weet niet meer precies hoe het zat, maar je kunt natuurlijk een maximale diepte instellen bijvoorbeeld om te voorkomen dat je dit soort problemen krijgt.

Hoe lang ben jij toen precies aan je crawler bezig geweest, uitgedrukt in uren?

Wat het zoeken naar alle paden naar een document, als je een database hebt kom je al een heel eind denk ik. (ik weet niet over hoeveel linkjes het gaat of wat voor sites en hoeveel)

De grote van de site is niet vastgelegd omdat het om het even welke site kan zijn, zelfs site's zoals ebay/amazon komen in aanmerking.

[4of9]

Ik denk dat ik een weekje of 2 bezig ben geweest.
Daarbij in gedachten nemend dat vanwege het gebruik van regular expressions ik het boek mastering regular expressions heb doorgewerkt tussendoor.

Met een weekje zou je een goede basis moeten kunnen leggen. (het ophalen van pagina's, het zoeken naar links en het implementeren van een goede queue)

Waar denk ik de meeste tijd in gaat zitten is het goed afhandelen van de uitzonderingen. Zowel van het vinden van links tot http exceptions etc etc.

[Verwijderd]

Je wilt dus in een gerichte graaf op zoek gaan naar ieder punt Y wat naar een punt X wijst. Hierbij is dus de totale set van punten bij aanvang nog niet bekend. Ik neem aan dat je de set wilt opbouwen a.d.h.v. de punten die je al hebt en de verwijzingen die vanuit deze punten gemaakt worden naar andere punten.

[mogelijke oplossing]
Start met een set initiële punten (pagina's) waaronder punt X. Kleur alle punten oranje op X na, deze wordt groen. Vanuit ieder groen punt is het mogelijk om op punt X uit te komen. De oranje punten zijn de punten die nog geparsed moeten worden. Rode punten (nu nog niet aanwezig) zijn de punten die reeds zijn geparsed maar die niet naar een groen punt verwijzen.

Vervolgens kun je de onderstaande pseudo-code uitvoeren om te bepalen vanuit welke punten (de groene) een pagina te benaderen is, de rode punten zijn de pagina's welke geen indirecte link naar de opgegeven pagina hebben.

code:

void markGreen(point)
{
  // Kleur het punt groen
  makeGreen(point);
  
  // Neem alle parents van het punt
  parents = getParents(point);
  
  // Kleur ze groen als ze nog niet groen zijn
  foreach(parents as parent)
  {
    if(parent.color != GREEN)
    {
      markGreen(parent);
    }
  }
}

int main()
{
  while(parent = getRandomOrangePoint())
  {
    // Bepaal alle relevante punten die toegevoegd mogen worden aan de graaf
    children = parsePoint(parent);
    
    foreach(children as child)
    {
      // Kijk of het punt bestaat
      if(!exists(child))
      {
        // Voeg een niet bestaand punt toe en maak het oranje
        addPoint(child);
        makeOrange(child);
      }
      else
      {
        // Het punt bestaat al :)
        // Kijk naar de kleur
        if((child.color == GREEN) && (parent.color != GREEN))
        {
          // Markeer dit punt ook als zijnde groen
          markGreen(parent);
        }
      }
    }
    
    if(parent.color == ORANGE)
    {
      makeRed(parent);
    }
  }
}

[/mogelijke oplossing]

Ik ben erg benieuwd naar de snelheid waarmee dit te realiseren is. Ik neem aan dat dit afhankelijk is van het aantal punten aangezien deze allemaal moeten worden geparsed.

[H!GHGuY]

-FoX- schreef op zondag 22 oktober 2006 @ 12:47:
Een crawler trap hoeft niet bewust gemaakt te zijn, maar kan wel. Hier tegen moet ik me dus gaan beschermen; niet meer dan 100x itereren is wel een mogelijkheid, maar vind ikzelf niet echt een nette oplossing.

Dat vind ik om eerlijk te zijn een hele nette oplossing. Je stelt gewoon een limiet eraan. Ik denk niet dat er een manier is om het anders te doen, tenzij je echt content gaat vergelijken wat imo een veel vuilere oplossing is want wanneer bepaal je dan wanneer je een pagina uit het geheugen moet doen?

TSP heeft niet direct iets met dit probleem te maken; maar ik wil wel graag weten als ik op een dood knooppunt terecht kom.
[...]
Mijn server, de crawler dus. Ik wil namelijk nu al een inschatting kunnen maken welke server hiervoor nodig zal zijn en hoe lang het gemiddeld zal duren om een site van bvb 1.000 pagina's te crawlen. Ik vermoed dat vooral memory en cpu usage van belang zullen zijn; data opslag ook wel, maar in mindere mate aangezien ik de pagina's niet moet cachen, e.d. aangezien er toch geen zoekacties op uitgevoerd zullen worden. Wat zou jij voorstellen als min. server specificatie voor dergelijk systeem?
[...]
Een maand lijkt me realistischer als ik het zo bekijk, maar misschien kom ik daar zelfs niet mee toe en stuit ik op een heleboel andere problemen.
- transactionele site's bvb
- anchor links
- escape karakters, ...
om zo maar even enkele out-of-the-blue te noemen...?
[...]
Het is ook niet de bedoeling om ALLE paden naar een site te vinden; maar wel om 1 bepaald item/page binnen 1 site te vinden. In grote websites zijn er verschillende manieren om tot een bepaalde pagina te komen, en hetgeen ik wil weten is welke?
Maar ik denk niet dat google een goed aanspreekpunt kan zijn, omdat we er rekening mee moeten houden dat bepaalde (nieuwe) paginas nog niet geïndexeerd werden.

Hoe lang ben jij toen precies aan je crawler bezig geweest, uitgedrukt in uren?

De grote van de site is niet vastgelegd omdat het om het even welke site kan zijn, zelfs site's zoals ebay/amazon komen in aanmerking.

reken op een weekje werk voor de basis, en exponentieel meer werk naarmate je wil uitbreiden.