wu :: forums « wu :: forums - links » Welcome, Guest. Please Login or Register. May 19th, 2024, 10:06am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: Grimbal, SMQ, Icarus, ThudnBlunder, towr, Eigenray, william wu)    links « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
jhngalt
Newbie

Gender:
Posts: 36
 links   « on: Mar 5th, 2005, 4:22pm » Quote Modify

How would you design a system which spiders the links from a webpage - specifically, how would you check if a link has already been hit?

thanks
 IP Logged
puzzlecracker
Senior Riddler

Men have become the tools of their tools

Gender:
Posts: 319
 Re: links   « Reply #1 on: Mar 5th, 2005, 7:46pm » Quote Modify

put it in some sort of hash table to determine the collision (a link has been hit). and put all links you encounter in a proirity  queue - so remove on at the time and go it.
 IP Logged

While we are postponing, life speeds by
jhngalt
Newbie

Gender:
Posts: 36
 Re: links   « Reply #2 on: Mar 5th, 2005, 8:28pm » Quote Modify

on Mar 5th, 2005, 7:46pm, puzzlecracker wrote:
 put it in some sort of hash table to determine the collision (a link has been hit). and put all links you encounter in a proirity  queue - so remove on at the time and go it.

hi.. why do you put all links you encounter into a priority queue?
thanks,
 IP Logged
puzzlecracker
Senior Riddler

Men have become the tools of their tools

Gender:
Posts: 319
 Re: links   « Reply #3 on: Mar 5th, 2005, 9:15pm » Quote Modify

a queue would also be sufficient  - so that you visit all wepages in order

for ex.

page a: e, f, g, d
:
and so on....

queue would be initially filled with a b c d  then you remove 'a'

and it would be filled with  b c d e f g .. then you go you go to 'b' and so on.    Also, every single jump verify with hash to avoid cycle and repeats.

 IP Logged

While we are postponing, life speeds by
jhngalt
Newbie

Gender:
Posts: 36
 Re: links   « Reply #4 on: Mar 6th, 2005, 6:00am » Quote Modify

on Mar 5th, 2005, 9:15pm, puzzlecracker wrote:
 a queue would also be sufficient  - so that you visit all wepages in order   for ex.     Page z has links a,b,c,d   page a: e, f, g, d  : and so on....     queue would be initially filled with a b c d  then you remove 'a'   and it would be filled with  b c d e f g .. then you go you go to 'b' and so on.    Also, every single jump verify with hash to avoid cycle and repeats.

You said in every single jump verify with hash to avoid cycle and repeats, meaning when you get a link you hash it and see if it already had been previously hit, what hash function do you think we could use, i read somewhere that you could use the checksum of the link, i'm not sure what that is, any ideas?

also some webpages have different urls pointing to it, how could you tell if you have already been there but under a different link..
thanks,
 IP Logged
jhngalt
Newbie

Gender:
Posts: 36
 Re: links   « Reply #5 on: Mar 16th, 2005, 8:09am » Quote Modify

on Mar 6th, 2005, 6:00am, jhngalt wrote:
 You said in every single jump verify with hash to avoid cycle and repeats, meaning when you get a link you hash it and see if it already had been previously hit, what hash function do you think we could use, i read somewhere that you could use the checksum of the link, i'm not sure what that is, any ideas?   also some webpages have different urls pointing to it, how could you tell if you have already been there but under a different link.. thanks,

nobody has any ideas?

 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: links   « Reply #6 on: Mar 17th, 2005, 1:00am » Quote Modify

Well, for the latter part. Visiting the link should help distinguish wether different urls point to the same website. (Just resolve what ip and path or content they point to)
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
TenaliRaman
Uberpuzzler

I am no special. I am only passionately curious.

Gender:
Posts: 1001
 Re: links   « Reply #7 on: Mar 21st, 2005, 10:52pm » Quote Modify

The checksum mentioned could be as simple as adding up the letters in the url. Lucky for us, the urls are all small letters and even luckier since addition of two letters doesnt give us a third letter. (I think!).

If the above is not correct(tho i think it should be), we may use an MD5 checksum.

-- AI

 IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: links   « Reply #8 on: Mar 22nd, 2005, 4:32am » Quote Modify

on Mar 21st, 2005, 10:52pm, TenaliRaman wrote:
 The checksum mentioned could be as simple as adding up the letters in the url.
Addition does not make a good hashfunction, since it is communative.
Essentially that means any anagrams will be confused, among many other things (the hash for "ac" would also be the same as "bb"). And I just don't think you would want to confuse urls like "www.dicktraceysucks.com" with "www.traceysucksdick.com"..

Quote:
 Lucky for us, the urls are all small letters and even luckier since addition of two letters doesnt give us a third letter. (I think!).
But three or four modulo the hastable-size might, not that that matters much, I think.. (Just as long as you get mostly distinct numbers for distinct urls)
 « Last Edit: Mar 22nd, 2005, 4:36am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7527
 Re: links   « Reply #9 on: Jun 14th, 2013, 7:54am » Quote Modify

The problem with a simple sum is that you never get values over a few thousand.  If you have millions of URLs, you get many collisions.

Java String's hash function is basically this:

char val[] = the string's chars
int hash = 0;
for( int i=0 ; i<val.length ; i++ ){
hash = hash*31 + val[i];
}
 IP Logged
TenaliRaman
Uberpuzzler

I am no special. I am only passionately curious.

Gender:
Posts: 1001
 Re: links   « Reply #10 on: Jun 16th, 2013, 4:47pm » Quote Modify

 IP Logged

Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
gitanas
Junior Member

Posts: 55
 Re: links   « Reply #11 on: Jan 27th, 2016, 6:33am » Quote Modify

You could store links in a database.
Moreover add index on that column and search will work very fast.
 IP Logged

Dummy Frog - my blog about interesting and funny things in our World
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »