Building a Search Engine from Scratch: Crawling, Indexing, and Ranking

[00:00:00]recently I was looking for alternatives to Google but for some reason there weren't any so what better solution than to make one for [Music] myself so search engine consists of three parts the crawler the indexer and the front end the crawler gets the contents of the websites and finds new ones the indexer then processes all that data and the front end allows someone to query it so let's take a closer look at the crawler the thing with the Internet is that there isn't just a list of which sites exist and which don't and you can't just randomly try different URLs since most of them won't exist now you could get people to submit websites which Google partially does but that's only effective once you're really big instead we have to rely on URLs that we find on the internet so we'll start with some arbitrary page that we know exists and then find any URLs on that page then look at those pages to find any URLs and so on so here's a code I'm using to get the contents of the page and I have some simple text processing here to detect the URLs and then add them to my database now here I just constantly run our function on any website that hasn't been crawled yet and stop once we hit some number of stored sites I've set the starting page to the Wikipedia homepage so let's just give this a quick run and FBI open up what the okay so turns out you can't just go around willy-nilly requesting the contents of every site you come across some sites don't want certain pages to be accessed by robots and some sites don't want robots accessing their Pages at all for some reason Reddit there is a standard for this kind of thing luckily where sites will include a file called robots.txt under the root URL it contains rules on which Pages you're allowed to or not allowed to look through for all Bots or for specific ones if you don't follow these rules the website might be able to detect your web crawler and block it even if this doesn't happen it's a good idea to follow these rules since they usually disallow crawling on pages that you wouldn't really want to be crawling on anyway and as a little reward for being nice sometimes the file will link to a Sit map which is another file that list a bunch of important pages on the site for you to crawl anyway I won't bore you with the details on the rules but I've made the code to pars this file as well as the sitemap file and now we can crawl responsibly so now we can try out our web crawler and it seems to be working pretty good but right now we aren't storing any useful information about the sites now we could just store the entire contents of every page but thinking ahead that'll make it hard to search for sites given some query so instead let's just store some things that we really want the first thing we'll store is an incoming and outgoing Links of every page which will be useful a bit later my current method of finding URLs isn't the greatest so I'm going to redo it instead I'm finding the links with this regex expression which matches everything that looks like a URL as well as anything within an HF property of an element which will always be a valid URL the second thing we should store is every term on the page which I'm finding by filtering out non-alpha numeric characters then separating everything by wh space I have this so that I store every term in my database and Link every page the term is in to the term entry as well as storing every page and linking every term on that page to the page entry so the links are two ways this will help speed things up when we go query our database all right so now it's time to try it and let's just set the limit to a modest 100 right now all right a page can link to the same URL multiple times so we should filter out duplicates oh yeah and you can put the path only in the HF property and that should link to that path from the end apparently you can start with two slashes yeah just put whatever you want in the hre okay so here I learned a very important lesson about the internet it's a complete Anarchy sure there are some conventions that most people agree on but really anyone can do whatever they want and there's nothing I can do about it so I just wrapped everything in a try statement to catch any more edge cases and now everything works fine okay so now we have everything we need to start getting results I'll just use this bit of code to get every site that contains every term in our search query and I'll whip up a simple friend end and give it a go nice it seems to be working fine but it's pretty garbage it's just giving us a websites in the order we craw them in and in any half decent search engine the results would be ordered so that the most relevant go to the top the most obvious solution here is to save the frequency of each term in the document in other words the number of times the term occurs in the page divided by the total number of terms in the page for each page add up the frequencies of each term in our query within that page and Order based on the sum this intuitively makes sense if we're looking for say Obama a page dedicated to Obama will include the word Obama more than page about say US presidents in general we'll call this number the term frequency or TF this works well but we can do a bit better for example if we search for the Lord of the Rings our current strategy will give us a site that contains a bunch of the word thee so we have to filter out these common words a nice way of doing this is to use a number of pages each term is in we can take this number and divide it from the total number of pages in our database then take a log of that this is known known as the inverse document frequency or IDF if we take the term frequency and multiply it by the inverse document frequency we get a number known as the tfidf of a term we can calculate this for every term in a query add all those up and sort by the result this works well but it's easy to abuse just Spam a few specific terms and your site gets bumped to the top of the search rankings well it's a good thing the creators of Google thought of this already they made an algorithm called Patron named after its creator Larry Page a very fitting name basically this algorithm determines how reputable a page is based on how much it's linked to by other sites start off by giving each page a page rank value of 0.25 for each page distribute its page rank evenly among its outgoing links now just repeat this process a few times until it settles the pages that are linked to by many reputable sites get a higher page Rank and are therefore more reputable themselves this algorithm is meant to simulate someone surfing through the sites and randomly clicking on links from site to site we can improve this slightly however by simulating a random chance that the surfer gets bored and hops on to a random site I'll set the chance to 15% and we can simulate this Behavior by Distributing 15% % of a Page's page rank among all pages than Distributing the remaining 85% among its outgoing links just like before we can run this algorithm after a crawling step and store the page rank of each page so now when a user searches something just like before we'll get every site that contains every term in the query but now for each of those sites we'll calculate the TF IDF of each term take the sum of those multiply it by the site's page Rank and then sort it based on that product and testing it out here it's working pretty good but right now all we have is 100 sites that's basically nothing for reference Google has upwards of 400 billion sites in their index and even just the English Wikipedia alone has over 6 million articles so I'm going to bump up our limit to 2,000 and running this exposed a pretty big issue in my crawler which was that it was just slow like really slow and it only got worse as I switched to a database on the cloud because my own hard drive was getting too full it was taking upwards of a minute per site which was simply too slow so I had to optimize I won't bore you with the details but it mostly consisted of finding which parts took the longest then messing with SQL queries until I got something a bit faster eventually through trial and error I got the time to crawl parse and store everything about a website down to 2 to 3 seconds per site and I sped up the time to query from over a minute to 5 to 10 seconds I also changed a starting page to this list of websites on Wikipedia since starting from the Wikipedia homepage meant I got a bunch of Wikipedia articles and not much else so I bumped the site limit to 50,000 ran it waited a couple days and as the crawler got closer to 50,000 it gave me one final Edge case to deal with an infinite redirect loop I ended up just fixing this manually and finally it was done now 50,000 is a far cry from the 400 billion links in Google but it's already taking up 5 GB of storage even with significant storage optimizations that I made regardless you can try it out yourself at the link in the description or the pin comment whichever YouTube will let me do be warned though my database provider pauses my instance after a few days of inactivity so it may not be working for you anyway that's it for this video If you enjoyed it press any number of the buttons below this video because YouTube enjoys that also my last video did way better than I thought it would so thank you everyone for that