[Alg] Algoritme webspider

[Verwijderd]

Ik zit al een hele tijd te brainstormen over een mogelijk algoritme voor een probleem wat ik voor mijn neus heb liggen. Ik heb een hele grote stapel webpagina's die ik allemaal door een stapel operaties wil halen zodat ik de data uit het document haal wat ik interessant vind. Nu klinkt dit vrij simpel in eerst instantie maar er komt meer bij kijken.

Een vergelijkbare situatie zou kunnen zijn: een aantal webwinkels. De enigste url die ik heb is een overzicht van de beschikbare categorien. De spider zou dus alle links moeten volgen (binnen hetzelfde domein) totdat hij op een product pagina terecht komt. Deze product pagina zal er bij iedere webwinkel weer anders uitzien. Immers hebben niet alle webwinkels dezelfde layout + achterliggende html code (toch jammer )

We gaan er even vanuit dat die product pagina's het volgende bevatten:

- Productomschrijving
- Aantal kenmerken + de bijbehorende waarde (bijvoorbeeld: Kloksnelheid = 2.4 Ghz, Geheugen = 512Mb). Dit is telkens een combinatie van 2 waardes. De naam van het kenmerk en de waarde bij het kenmerk.

Het algoritme zou in staat moeten zijn om het volgende te doen voor iedere mogelijke webwinkel. Het moet dus een universeel algoritme zijn. Er moeten geen templates aan te pas komen of wat dan ook.

- Beginnen bij het categorie overzicht
- Linkjes (binnen hetzelfde domein) volgen totdat hij bij een product overzicht komt
- Alle links naar productinfo pagina's op deze pagina volgen
- Per productinfo pagina mij een lijst geven met kenmerken van dat product + een productomschrijving

Dit hele verhaal moet grotendeels zonder menselijke tussenkomst komen te functioneren. Ik heb zitten spelen met het idee om een aantal pagina's uit dezelfde categorie te diff'en om zo de dynamische van de statische content te scheiden. Immers, de html die de layout genereerd zal vrijwel 100% hetzelfde blijven en is niet van belang.

Echter hou je dan nog een blok rotzooi over. Dit blok rotzooi bevat zowel HTML als de data waar ik interesse in heb (omschrijving + kenmerken). Hoe bak ik een parser die in staat is te onderscheiden of het een kenmerk is en dan ook nog eens in staat is de juiste waarde er bij te zoeken.

Lijkt me een leuke opgave voor de /14 mensjes op de vroege dinsdagochtend om hier een algoritme voor te bedenken Ik heb er iig een hele tijd naar zitten kijken en ik zie hem nog niet. Alle hints zijn welkom. Externe programma's die het werk voor me doen mag natuurlijk ook

[Wim Leers]

Hoeveel mag het kosten? Er zijn immers een aantal commerciële spiders beschikbaar...

[Creepy]

Verwijderd schreef op dinsdag 20 december 2005 @ 10:57:
Lijkt me een leuke opgave voor de /14 mensjes op de vroege dinsdagochtend om hier een algoritme voor te bedenken Ik heb er iig een hele tijd naar zitten kijken en ik zie hem nog niet. Alle hints zijn welkom.

En welke heb je dan zelf al bedacht? Je noemt nu maar 1 optie zonder dat je je algoritme beschrijft.
Als de pagina's steeds hetzelfde zijn opgebouwd lijkt het me een kleine moetie om kenmerken te onderscheiden van de rest van de content

Externe programma's die het werk voor me doen mag natuurlijk ook

Nee, dat mag niet Hier in Programming & Webscripting gaat het om het zelf programmeren.

Bashrat schreef op dinsdag 20 december 2005 @ 11:01:
Hoeveel mag het kosten? Er zijn immers een aantal commerciële spiders beschikbaar...

Maar dan ben je dus niet zelf aan het ontwikkelen

[ Voor 17% gewijzigd door Creepy op 20-12-2005 11:05 ]

[Verwijderd]

Das het leuke, het bovenstaande is slechts een derde deel van het algoritme
Wanneer er een extern programma gebruikt zou worden dan zou de spider allereerst aanpasbaar moeten zijn en ten tweede zou deze spider vrij goedkoop moeten zijn. Het is en het blijft natuurlijk een vrijetijdsprojectje

Hoe minder hoe beter dus

Het probleem is dat het een specifiek probleem is. Een spider zou wel informatie kunnen spideren maar de ellende is dat er slechts een deel van de data uit het document van belang is. De rest kan de spider gewoon ignoren. Daarnaast moet de spider ook rekening houden met de logische opbouw.

Wanneer het volgende een stukje van een document is:

code:

Dit is de omschrijving

Kenmerk 1           Waarde 1
Kenmerk 2           Waarde 2
Kenmerk 3           Waarde 3

Dan zou de spider mij moeten kunnen vertellen dat de omschrijving: "Dit is de omschrijving" is en dat er 3 kenmerken zijn (Kenmerk1, Kenmerk 2, Kenmerk 3) waarbij hij ook nog weet welke waarde bij welk kenmerk hoort. Ofwel hij moet weten dat bij dit product de waarde: "Waarde 1" bij het kenmerk: "Kenmerk 1" hoort.

Voor zo ver ik weet zijn er geen spiders die dit kunnen.

[Verwijderd]

Creepy schreef op dinsdag 20 december 2005 @ 11:05:
En welke heb je dan zelf al bedacht? Je noemt nu maar 1 optie zonder dat je je algoritme beschrijft.
Als de pagina's steeds hetzelfde zijn opgebouwd lijkt het me een kleine moetie om kenmerken te onderscheiden van de rest van de content

Het principe is heel simpel. Wanneer ik 2 pagina's uit dezelfde categorie langs een diff tool te halen zodat dit tooltje mij het dynamische en het statische deel aanlevert. Het statische deel kan ik in principe gewoon weggooien. Dit is niet de inhoud die mijn interesse wekt. Het dynamische deel is anders. Ergens in de brei die ik daarbij over houdt moeten de omschrijving en kenmerken staan die ik wens te onderscheiden. Maar hoe we dat gaan doen? Ik heb werkelijk nog geen idee

De ellende is dat het algoritme op iedere mogelijke pagina layout moet werken. Wanneer ik de spider over norrod.nl of over funprice.nl heen haal mag dit geen verschil maken. Hij moet in beide gevallen in staat zijn de gegevens te extraheren.

Juist dit laatste feitje maakt dit vrij pittig

Als het een kleine moeite is kun je me vast wel wat hints geven over hoe je dat dan wel niet van plan was De reden waarom ik niet meer algoritmen opnoem is omdat ik er niet meer kan bedenken

Creepy schreef op dinsdag 20 december 2005 @ 11:05:
Nee, dat mag niet Hier in Programming & Webscripting gaat het om het zelf programmeren.

[...]

Maar dan ben je dus niet zelf aan het ontwikkelen

In principe moet de oplossing zo veel mogelijk zelf ontwikkeld worden. Er mogen wel externe tooltjes gebruikt worden zoals bijvoorbeeld de diff tool die op praktisch ieder unix-based platform wel bestaat.

[ Voor 3% gewijzigd door Verwijderd op 20-12-2005 11:22 ]

[djluc]

Een basis zou semantiek in HTML kunnen zijn. Bijvoorbeeld een table in HTML heeft als eigenschap dat er een horizontale en verticale relatie bestaat. Een dl/dt enzovoorts hebben weer een eigen vorm van relatie. Ik denk dat dit de enige manier is om te kijken wat de relatie is.

Een andere mogelijkheid zou zijn om de HTML te parsen en dan de visuele verbindingen proberen te herkennen. Bijvoorbeeld: je herkent dat er 2 kolommen met waarden naast elkaar staan. Je gokt dan op een overeenkomst kenmerk - waarde.

Dit kan je vervolgens uitwerken door de relatie verder te gaan ontwikkelen middels het vergelijke van de pagina's. Als je op iedere pagina een tabel tegenkomt met daar vaak dezelfde waarden in de linkerkolom dan is dat de eigenschappen kolom. De waarden staan dus in een andere kolom. De waarden kan je tevens vergelijken op datatype. Denk aan getallen enzovoorts. Als je dan eenmaal leuk bezig bent kan je nog gaan kijken naar de hoeveelheden, bijvoorbeeld GB/MB enzovoorts.

Een leuk idee, erg tijdrovend maar ook erg uitdagend!

[Verwijderd]

djluc schreef op dinsdag 20 december 2005 @ 11:39:
Een basis zou semantiek in HTML kunnen zijn. Bijvoorbeeld een table in HTML heeft als eigenschap dat er een horizontale en verticale relatie bestaat. Een dl/dt enzovoorts hebben weer een eigen vorm van relatie. Ik denk dat dit de enige manier is om te kijken wat de relatie is.

De ellende is alleen dat er veel webmasters zijn die alles net weer iets anders doen. Gisteren kwamen we idd ook op dit idee. Zeg maar bepaalde 'templates' aanhouden voor standaard structuren in een pagina. Echter krijg je dit niet echt universeel. Iedere keer als er een gare webmaster gekke dingen doet moet jij je spider aanpassen om hem die gekke structuren te laten begrijpen

djluc schreef op dinsdag 20 december 2005 @ 11:39:
Een andere mogelijkheid zou zijn om de HTML te parsen en dan de visuele verbindingen proberen te herkennen. Bijvoorbeeld: je herkent dat er 2 kolommen met waarden naast elkaar staan. Je gokt dan op een overeenkomst kenmerk - waarde.

Dit is idd een valide optie.

djluc schreef op dinsdag 20 december 2005 @ 11:39:
Dit kan je vervolgens uitwerken door de relatie verder te gaan ontwikkelen middels het vergelijke van de pagina's. Als je op iedere pagina een tabel tegenkomt met daar vaak dezelfde waarden in de linkerkolom dan is dat de eigenschappen kolom. De waarden staan dus in een andere kolom. De waarden kan je tevens vergelijken op datatype. Denk aan getallen enzovoorts. Als je dan eenmaal leuk bezig bent kan je nog gaan kijken naar de hoeveelheden, bijvoorbeeld GB/MB enzovoorts.

Een leuk idee, erg tijdrovend maar ook erg uitdagend!

De spider zou zichzelf wezenlijk moeten leren hoe webshop X zijn pagina's opbouwt. Hij zou hierbij kunnen letten op dingen als:

- Welke content is statisch en is dus onbelangrijk
- Zijn de kenmerken vertoond d.m.v. ul/li, tables, dd/dt danwel een andere vorm
- Waar staat de omschrijving?
- Zijn er css classes die hij kan gebruiken als logische bouwblokken?

Ik zou er zo niet meer weten te bedenken. (Er zijn er vast nog meer). Echter wordt het probleem dan nog erger dan het al was. Om zichzelf dingen aan te kunnen leren zal hij de eerste paar runs alsnog de pagina moeten kunnen ontleden. Hiernaast moet hij vervolgens ook nog weten welke gegevens hij moet onthouden.

En idd, het is een leuk idee. Uitdagend ook. Het is echter wel de bedoeling dat het op de lange duur tijd gaat besparen

[Alarmnummer]

Volledig automatisch gaat dit niet lukken. De meest eenvoudige en best werkende manier is per site een soortement van walker te maken die bepaalde pagina`s afloopt en ophaald. Per site kun je dan informatie eruit filteren (iedere site heeft de informatie toch wel weer anders geformateerd).

Dit is veel beter dan een algemene walker te maken die het op alle sites goed moet doen (dus niet in loops ed blijft vastzitten) en daaruit nog eens content te gaan vissen.

[RagaBaSH]

aantal opties:
je kan beginnen met alleen winkels die een print prijslijst hebben (zoals o.a. funprice en norrod). Deze zijn in de regel makkelijker te "parsen".

andere optie is dat je een systeem bouwt waarin je een pagina inlaad in jouw eigen programma en daarin zelf visueel relaties gaat leggen. dus dat je aangeeft:

• kolom 1.2 (device) hoort bij kolom 1.3 (prijs)
• kolom 1.4 (device) hoort bij kolom 1.5 (prijs)

waarbij je dan kan aangeven dat hij naar beneden door moet nummeren (en dus de naar 2.2 en 2.3 gaan etc.)

betekent dat je wel wat voorwerk moet doen maar omdat je zelf de relaties aangeeft en niet door een algoritme laat uitvogelen wordt het geheel wat minder "natte vinger werk".

[djluc]

[...]maar omdat je zelf de relaties aangeeft en niet door een algoritme laat uitvogelen wordt het geheel wat minder "natte vinger werk".

Dat is inderdaad wel een goed punt: Hoe betrouwbaar moeten de gegevens zijn?

[Verwijderd]

De gegevens moeten redelijk betrouwbaar zijn.

Handmatig relaties gaan leggen of handmatig walkers schrijven is geen optie. De webwinkel is slechts een voorbeeld om jullie het principe uit te leggen. De werkelijke situatie is vele malen groter. Ik heb persoonlijk weinig behoefte om een paar k aan webwalkers te schrijven

aantal opties:
je kan beginnen met alleen winkels die een print prijslijst hebben (zoals o.a. funprice en norrod). Deze zijn in de regel makkelijker te "parsen".

Dit is geen optie. Het zijn deels vastgecodeerde documenten en deels pagina's die door andere mensen geservereerd worden. Het is geen optie om een printer versie van deze documenten te maken.

Het zal dus vrijwel automatisch moeten gebeuren wil dit idee lukken

[Gomez12]

Zorg met je diffje dat je alleen je dynamische inhoud ( op een logische wijze ) overhoud ,maar sla het statische en de semantiek hiervan wel op(zie later ).
Toon dan per website / document 5 voorbeelden een splitscreen met bovenin de originele productpagina min de plaatjes en onderin de in te vullen velden aan 1 persoon en laat deze persoon van de 5 voorbeelden precies de gegevens overtypen die jij wilt hebben in de kolommen die jij wilt hebben. Laat nu je webspider opnieuw over de 5 voorbeelden heengaan en zoeken naar de gegevens die ingevuld zijn en toon dit ter controle aan de gebruiker.
Is dit correct dan heb je een redelijk template voor deze site. Kost je ong 2 minuten per site.

Als je ook de semantiek van de originele site opslaat kan je bij nieuwe sites automagisch al een gok laten tonen van de computer op basis van de semantiek. En op basis van de semantiek en enkele andere kenmerken kan je ook aanmerken of een site veranderd (van opbouw dus opnieuw benoemen) is of niet

Automagisch zal dit zowat niet gaan. Computertechnisch is er al een groot probleem met plaatjes ( waarom zou er in een gifje niet een tekst of een prijs staan ) / pdf'jes / flash.

Het is in het begin geen zaligmakende oplossing, maar op den duur wordt het steeds minder werk. En als je eenmaal een site gedaan hebt ben je er ook klaar mee. Compleet automatisch zie ik niet gebeuren omdat html je te veel vrijheid geeft voor dit soort dingen ( ik kan met 100 absoluut geplaatste divjes een zin van 100 tekens maken die voor de computer onleesbaar is maar waar geen mens in de browser iets van ziet )

[dusty]

Wat gomez hierboven dus vertelt komt neer op een "Template Engine", iets waar je uiteindelijk toch op terecht komt juist omdat er zoveel verschillende mogelijkheden zijn om HTML te (mis/ge)bruiken.

[Verwijderd]

Je hebt eigenlijk 2 problemen.

1) Zorgen dat de spider de tree met html pagina's afloopt en de productpagina's herkend.
2) Uit de productpagina's de juiste informatie halen.

Het eerste is nog wel enigszins betrouwbaar te doen. Het tweede is een stuk lastiger.

Allereerst kunnen webdesigners vele methoden gebruiken om het weer te geven, maar belangrijker is dat elke website weer andere kenmerken weergeeft. Als je de spider niet handmatig de pagina's wilt aanleren, er geen structuur in de pagina's zit en de kenmerken die je zoekt ook niet van te voren bekend zijn lijkt dit een mission impossible.

Ik zou zelf de spider verschillende standaard structuren aanleren en de spider die structuren laten herkennen. Werkt niet op alle pagina's maar je komt er een flink eind mee. Als je 1000 websites bezoekt zullen er zo'n 800 redelijk standaard zijn opgebouwd. De overige 200 zijn dan de uitdaging. Wil je die ook per se doorzoeken, kun je hun structuur toevoegen, maar je kunt ze ook gewoon negeren.

Een spider die automatisch op alle sites alles vindt wat je zoekt is een illusie. Daar komt een hoop handwerk bij kijken. Maar een spider die "meestal" de juiste resultaten retourneert is daarentegen wel goed mogelijk. Maar dan nog moet je per site deze resultaten controleren voordat je de site je database laat verklooien.

[Verwijderd]

Als jouw programmeer omgeving C++ is en je platform Windows, dan zou je eens kunnen kijken naar het JDAWN framework (Job Directed Automated Web Navigator): http://sourceforge.net/projects/jdawn .

Hoewel dit nog erg in alfa state is, is het speciaal ontworpen voor dergelijke dingen. Je kunt de algemene spidering door het framework laten doen (waarbij je zelf programmatisch conditities bepaald over het wel of niet doorgaan met het volgen van links). De specificieke filtering gebeurd dan door middel van aparte plug-ins die je zelf kunt schrijven. Het geheel is dan ook nog voorzien van een GUI om de voortgang en de gaten te houden.

Zoals gezegd, nog erg alfa en al een tijd nix meer aan gedaan, maar als je niet terug schrikt van een beetje programmeren (dit is /14 uiteindelijk ), dan is het mischien wel de moeite van het bekijken waard.

[zneek]

Verwijderd schreef op dinsdag 20 december 2005 @ 11:13:
[...]
De ellende is dat het algoritme op iedere mogelijke pagina layout moet werken. Wanneer ik de spider over norrod.nl of over funprice.nl heen haal mag dit geen verschil maken. Hij moet in beide gevallen in staat zijn de gegevens te extraheren.
[...]

Hey, psst : nieuws: Norrod en Funprice samen onder één holding

Dus is dat probleem weer makkelijk getackeld Die kun je in 1 keer ophalen, zelfde holding, zelfde artikelen.

Verder inhoudelijk. Je komt echt uit op een structuur die per domein/soort site/pagina whatever een andere pagecrawler/parser in moet kunnen schakelen. Of er moeten standaarden zitten in de pagina's/documenten die je moet crawlen die het mogelijk maken om zelf te een standaard crawler te maken. Wij hebben in het verleden wel eens wat met crawlers gedaan, en dat werd sowieso in 1 geval erg naar lapwerk. Dat ging om een 5-tal sites met geen enkele overeenkomst in structuur. Dus 5 aparte brokjes functionaliteit om het parse werk te doen. Dat hebben we destijds met HttpUnit gedaan, een Java opensource ding bedoeld om Http unit tests uit te voeren. Ook makkelijk te misbruiken voor crawlers en html-parse achtige doeleinden.

[MSalters]

dusty schreef op dinsdag 20 december 2005 @ 17:46:
Wat gomez hierboven dus vertelt komt neer op een "Template Engine", iets waar je uiteindelijk toch op terecht komt juist omdat er zoveel verschillende mogelijkheden zijn om HTML te (mis/ge)bruiken.

Erger - DHTML. Op het moment dat je iets van AJAX tegenkomt ben je het haasje, tenzij je een emdedded browser gebruikt (Mozilla/IE-als-ActiveX/Apple WebKit/...). Een simpele GET gaat heel snel mislukken.

[Verwijderd]

MSalters schreef op woensdag 21 december 2005 @ 21:02:
[...]

Erger - DHTML. Op het moment dat je iets van AJAX tegenkomt ben je het haasje, tenzij je een emdedded browser gebruikt (Mozilla/IE-als-ActiveX/Apple WebKit/...).

En laat het Jdawn project nou net dat doen! (gebruikt een embedded active-X IE)