[alg] (lijst) strings matchen tegen lijstje substrings

[killercow]

Ik heb een lijstje met urls welke ik wil spideren.
En ik heb een lijstje met url parts welke ik wel of niet mag spideren zoals de robots.txt aangeeft.

Nu kan ik natuurlijk voor elke url die ik wil spideren de robots.txt rules ophalen/uit cache vissen, en zo kijken of die url allowed is, maar dit is niet erg efficient als je het mij vraagt. Zeker omdat urls met betrekking tot de zelfde robots.txt niet achter elkaar opgehaald worden, en er dus constant van rules geswitched moet worden.

Omdat ik niet omgekeerd kan querien naar de database met rules "select allowed from rules where urlrule == stukje van inputurl" is het per URL niet sneller op te lossen dan dat.

Een andere oplossing is als volgt:

Zodra ik een link vindt, zet ik de checked variabele op NO/null.
En zodra ik dan toe ben aan het spideren van die link (en hij staat nog op null), check ik alle files van dat domain die nog op null staan (mits er rules/een robots.txt is natuurlijk), en zet ik bij alle links van dat domein op allow,of disallow afhankelijk wat de robots.txt me verteld.

Doordat ik nu vanuit de rules kan zoeken (meer urls dan rules), kan ik met de volgende query redelijk snel alle urls vinden.

select id from urls where domain=X and url like 'rule%' and checked=null

Hierdoor kan ik vrij simpel voldoen aan robots.txt.

Al met al zou dit aardig moeten werken, maar toch blijft het een beetje een ranzige oplossing. zeker omdat ik constant nieuwe urls van een domain zou kunnen blijven ontvangen, en zo dus constant bovenstaande handlingen op een beperkt groepje urls blijf uitvoeren. Heeft iemand een beter/sneller idee?

[Varienaja]

1. Uit de substring-urls volledige urls genereren.

2. lijst met urls sorteren.
3. lijst van punt 1 sorteren.

4. beide lijsten gelijktijdig doorlopen, ondertussen de items uit lijst van punt2 verwijderen die voorkomen in lijst van punt3.

Sorteren is n log n, beide lijsten doorlopen is n --> totale algoritme is n log n. En dat lijkt me goed te doen.

[MSalters]

Is zo'n robots.txt zo groot dat 'ie niet in je db past? Want anders hoef je alleen de URLs van een enkele site met de bijbehorende robots.txt te vergelijken. Het checken van een URL tegen een robots.txt doe je uiteraard niet in SQL.

[killercow]

Een robots.txt kan natuurlijk prima in de database.

Een check doe je niet in SQl, maar als een db-engine mij via een handige query me in enkeer het antwoord kan geven doe ik dat liever dan zelf een lijstje fetchen en dan checken. (zeker aangezien de db-engine vast een snellere opslag/retreiver heeft dan ik kan bouwen voor dat soort datasets.

Het probleem is dat als ik een link heb en hem daarna tegen alle regels in de robots.txt wil houden ik alle rules moet matchen tegen het begin van de huidige string.

voorbeeld:
url; /mapje/map1/map2/map3/file2.html
rules:
disallow: /mapje/map1/
disallow: /mapje/map4
disallow: /anderemap
allow: /mapje/map1/map2/map3/file1.html

zoals je kunt zien moet ik dus voor elke file alle rules af.
Nu kan ik ze dus per domain groeperen en dan iets massaler behandelen, maar dan nog heb je een redelijk vage oplossing. (iig kwa algoritme)

Is er geen mooie hash oplossing? of longest common substring voor dit soort matches? (niet dat de huidige situatie niet zou kunnen werken, maar als je enkele honderden duizenden urls wilt matchen zul je toch met een echte oplossing moeten kunnen komen right?) heb weinig zin om nutteloos cpu cycles te burnen op iedere url.

[ Voor 14% gewijzigd door killercow op 03-03-2006 22:58 ]