[algo] Webpagina's vergelijken

[kvdveer]

Ik had een leuk ideetje, en ik wil even kijken of het haalbaar is.

case
Ik wil identieke teksten gaan zoeken op google, gebaseerd op een klein aantal (10 is de limiet voor google) kernwoorden. Google geeft me een aantal results terug, en ieder van die results open ik. De http-kant handel ik uiteraard netjes af, maar waar het me nu eigenlijk om gaat: Hoe vergelijk ik die teksten?

Voorbeeldje: Ik zoek naar de 1e meditatie van descartes (cogito ergo sum). Ik weet de eerste regel: "SEVERAL years have now elapsed"
[google=descartes SEVERAL years have now elapsed]

In dit geval zijn de eerste 5 hits goede hits, dus daar hoef ik nu nog even niet op te filteren.

Als je echter naar de HTML-code gaat kijken, dan blijkt dat de teksten niet identiek zijn: sommigen hebben <br>-tags, anderen knoeien met de interpunctie. Er is zelfs een site die de individuele alinea's in <TD's> heeft gestopt.

Wat er uit mijn programmerseltje moet komen is een tekst: geen urls. Daar hebben we google al voor...

mogelijke oplossing
Mijn eerste oplossing is als volgt:
[0] Ik neem aan dat al mijn resultaten HTML zijn. (dat hoeft op zich niet zo te zijn natuurlijk, veel teksten staan op het web als .txt)
[1] Ik vervang alle meervoudige whitespace door een spatie.
[2-] Ik verwijder alles wat gegarandeerd mijn teksten niet bevat:
s/<(A|HEAD|SCRIPT|SELECT|STYLE).*?>.*?</\1>/ /i
[3] Ik vervang alle </TR>'s, <br>'s, </DIV>'s, <P>'s en </P>'s door een newline. s/<(/TR|BR|/DIV|/P|P).*?>/\n/i
[4] Ik verwijder alle HTML-tags. s/<.*?>/ /

Nu heb ik de teksten zoals ze op de webpagina's staan, maar inclusief extra rotzooi. Dat doe ik voor (bijvoorbeeld) de eerste 5 hits van google.

Vervolgens ga ik ditalles woord voor woord vergelijken:
[1] ik neem het eerste woord van Hit 1.
[2] Ik bepaal waneer het betreffende woord voor het eerst voorkomt in hit 2 tot 5.
[3] ik neem het tweede woord van Hit 1.
[4] Ik bepaal waneer het betreffende woord voorkomt in de overige hits, tellend vanaf de positie die ik bij [2] heb gevonden. Is is dit niet [2]+1, dan neem ik het tweede woord en begin vanaf [1]. Is dit wel [2]+1, dan ga ik naar [3] maar dan met het derde woord.
[5] komen een aantal woorden overeen tot aan het eind van een regel, dan gaat die regel met de interpunctie zoals in hit 1 naar de 'return buffer'.

vraag
Ik vind het bovenstaande nogal omslachtig, is er niet een eenvoudiger methode. (let op: ik wil niet weten of er overeenkomde teksten gevonden zijn, ik wil weten wat de gevonden tekst exact is).

[Nielsz]

In mijn ubbparser heb ik een optie om de kale text op te slaan.
Als ik een [/tag] tegen kom, doe ik $this->CleanText.=$text;
Zo krijg ik een string met alle kale text.

Dus je moet idd een soort van ubbparser maken, die dan niet kijkt naar [] maar naar <>. Het is ff wat programmeren maar dan heb je ook wat

[kvdveer]

Nielsz schreef op 20 oktober 2002 @ 16:31:
Dus je moet idd een soort van ubbparser maken, die dan niet kijkt naar [] maar naar <>. Het is ff wat programmeren maar dan heb je ook wat

Het zuiveren van de tekst is niet echt het probleem... Het gaat hier echt om het vergelijken: dat is lastiger. Een parser bouwen lukt me wel...

[djc]

Als je zorgt dat je een soort "pointer" hebt naar het eerste woord, dan kun je bijvoorbeeld een array met 5 pointers maken, en telkens het karakter op de eerste pointer lezen en weggooien en vervolgens de eerste karakters van elke volgende pointer lezen en weggooien... Net zo lang tot je bij het einde van de tekst komt.

Maar dat is niet zo veel verschil met je eigen methode, geloof ik.

[MisterData]

Als je twee strings wilt vergelijken en wilt weten hoever ze uitelkaar liggen dan kun je de levenshtein functie gebruiken

[Verwijderd]

This function returns the Levenshtein-Distance between the two argument strings or -1, if one of the argument strings is longer than the limit of 255 characters (255 should be more than enough for name or dictionary comparison, and nobody serious would be doing genetic analysis with PHP).

levenshtein() lijkt me dus niet echt handig similar_text() werkt mischien wel, maar doet denk ik niet wat kvdveer wil

[TlighT]

Om het gemakkelijker te maken, zou ik zeggen dat twee teksten (mits het niet om kunstmatig gegenereerde teksten gaat) identiek zijn als ze dezelfde woorden bevatten, ongeacht in welke volgorde deze woorden staan. Dus als tekst I a woorden bevat en tekst II b woorden en ze hebben x woorden gemeen, dan zou je bijv. kunnen zeggen dat de gelijkeniswaarde tussen de twee teksten (x*2)/(a+b) is. Je zou dan een grenswaarde kunnen leggen; als de gelijkeniswaarde boven deze grenswaarde ligt, dan zijn de twee teksten identiek.

[nulkelvin]

TlighT schreef op 20 oktober 2002 @ 20:17:
Om het gemakkelijker te maken, zou ik zeggen dat twee teksten (mits het niet om kunstmatig gegenereerde teksten gaat) indentiek zijn als ze dezelfde woorden bevatten, ongeacht in welke volgorde deze woorden staan. Dus als tekst I a woorden bevat en tekst II b woorden en ze hebben x woorden gemeen, dan zou je bijv. kunnen zeggen dat de gelijkeniswaarde tussen de twee teksten (x*2)/(a+b) is. Je zou dan een grenswaarde kunnen leggen; als de gelijkeniswaarde boven deze grenswaarde ligt, dan zijn de twee teksten identiek.

Hier moet je mee oppassen want volgorde heeft in een tekst wel degelijk betekenis.

Ik wil wel spruitjes maar geen lever.
Ik wil geen spruitjes maar wel lever.

[TlighT]

nulkelvin schreef op 20 oktober 2002 @ 22:58:
[...]


Hier moet je mee oppassen want volgorde heeft in een tekst wel degelijk betekenis.

Ik wil wel spruitjes maar geen lever.
Ik wil geen spruitjes maar wel lever.

Dat is zo, maar de vraag ging over het vergelijken van teksten. De kans lijkt me vrij klein dat je "in het wild" twee teksten (van een redelijke lengte) tegenkomt die (bijna) dezelfde woorden bevatten maar in een heel andere volgorde.

[kvdveer]

waar ik nog aan zat te denken: Je zou een soort van hash kunnen berekenen, die zo in elkaar zit dat een of twee % van de woorden er niet veel invloed op hebben, en juist het aantal woorden wel. Liever zou ik het dan ook nog zo doen dat langere woorde er meer invloed op hebben dan korte woorden. Als twee hashes maar een paar procent verschillen, dan komen de teksten overeen.
Ook hierbij geldt: we verwijderen interpunctie en cijfers: die komen te vaak niet overeen.

Een van de mogelijkheden is alle letters te nummeren (1-26) en per woord met elkaar te vermenigvuldigen. De hash van de tekst wordt dat de optelsom van deze vermenigvuldiging.

De hash van
'Ik wil naar bed"
= 9*11 + 23*9*12 + 14*1*1*18 + 2*5*4
= 99 + 2484 + 252 + 40 = 2875

Je ziet dat het woord wil het zwaarste telt in deze zin. Waarschijnlijk is het handiger om de letters anders te rangschikken dan alfabetisch.

---

Een heel ander probleem is nog het versnijden van de teksten. Zodra we weten dat twee pagina's identieke teksten bevatten, moeten we natuurlijk ook nog de overige teksten er af halen: Verwijzingen naar de beheerder van de website, menu's, enzovoorts. Hier kunnen we gebruik maken van het feit dat de twee pagina's alleen dezelfde tekst bevatten, maar niet dezelfde rand-rotzooi. Hierover iemand ideeen?

[nulkelvin]

je zou ein bereik aan kunnen wijzen, waarbinnen de teksten hetzelfde zijn ...blaat... en ___blaat___ zou dan iet worden van: het zelfde, behalve de drie tekens ervoor en de drie erna.

[kvdveer]

nulkelvin schreef op 21 oktober 2002 @ 23:00:
je zou ein bereik aan kunnen wijzen, waarbinnen de teksten hetzelfde zijn ...blaat... en ___blaat___ zou dan iet worden van: het zelfde, behalve de drie tekens ervoor en de drie erna.

Ik begrijp niet helemaal wat je bedoelt? leg uit?

[kvdveer]

Nog een iets ander idee wat ik vandaag nog kreeg: een histogram maken van woorden... Op basis van dat histogram kun je bepalen of teksten overeenkomen, en als ze overeenkomen, wat voor rotzooi er eventueel nog bij zit...

Trouwens: mijn html-filter bestaat al:
http://koert.servebeer.com:1000/Gathering/ (hou het een beetje beschaafd svp, uiteraard wordt alles gelogd...)