I recently decided to explore the possibility of developing my own search engine. This involved understanding a few key concepts of how a search engine fundamentally works as well as some independent research on what popular languages would be suitable for such a project. It seems that while using a basic LAMP stack might prove too faulty on a large scale search engine it is not impossible. Building a basic web crawler with PHP/MySQL may not be as horrible of an idea as one might think!
It’s only mid-December and already I can feel the on-slew of cold as winter approaches. With a few inches of snow piling up outside my window, I warm myself up with a fresh cup of coffee and plug back in to my laptop; Yet, again I am exploring the wonderful world of search.
We’ve come a long way from the Google Search of 1999 and the Yahoo Search of the past. Bing has recently stepped onto the web scene (as a mass-marketed re-branded web solution). Google, still tops the lot in sheer volume of search traffic, but aren’t we forgetting about all of the other search engines on our massive list of web search?
The reason it sparked my interest to find out more about some of the requirements and specifications necessary for developing your own search engine was due to a recent project that involved seeking out and identifying broken links on a web site. A part of the project involved writing a small light-weight bot that would crawl only the internal links that pointed to your web site and detect any broken links in order to notify the web master. This is actually one fundamental part of what a search engine does. In my efforts I needed to find the most effective and efficient methods to crawl a site internally in order to find all of its internal links without using any site-map or file-system structures. It needed to be done strictly over HTTP and this is what led me to some key search engine and web crawler articles.
The most difficult part of writing this bot was having to rely solely on the links that the web pages of the site provided. Since a dynamic or database-driven web site can potentially have thousands of pages it proved more difficult than I had originally anticipated to map out this link structure directly over an HTTP crawl.

HTML Parsing
The first challenge was trying to obtain all the links provided by the <a> tags in the page. At first I thought to use a regex search pattern, but later on it proved more ostentatious than necessary. So, instead I turned to a common solution using the PHP libxml DOM object. With DOM you can easily obtain all of the HREF properties of the <a> HTML tags on the page through the getElementsByTagName method. Once we have the specific HREF attribute of that tag we can iterate through the object and produce an array for all other tags.
Some of the problems further presented by parsing the HTML could involve javascript, improper markup, or other external requirements. In the spirit of keeping things simple I chose to ignore these underlying factors.

The Domain Name Space Problem
The second challenge was identifying which of the links on the page were pointing to another page on the same website and which were pointing to external websites. Domain name-space is so vast that it has become increasingly difficult to identify the validity of a domain without having to rely on DNS. Since TLDs have grown so tall and stretched so wide that they now encompass UTF-8 characters and even CTLD catenation, many of my test methods have failed. Again, for purposes of simplification I chose to ignore the one-off problems and deal with the most common scenarios and their proven solutions.
I solved this problem by writing a very simplistic function to help me break down the individual components of the URL into some very distinct properties and return them in an array. The code below demonstrates the basic functionality of this method.

function breakURI($URI) {
  // This function identifies four key components of any URI that's the protocol, the domain, the port and the path.
  // The domain can be further broken down in to tld and sub domains, and the path can be further divded in to path + query string
  $pattern = "/^(?<protocol>[a-z]+:\/\/)?(?<domain>[a-z0-9\.-]*\.[a-z]{2,})(?<port>:\d+)?(?<path>[\/|\?].*)?$/i";
  if (!preg_match($pattern, $URI, $match)) return false;
  // Get the query string from the path (if any) and move it to it's own element in the array
  if (isset($match['path']) && strstr($match['path'],"?")) {
    $match['querystring'] = substr(strstr($match['path'],"?"),1);
    $match['path'] = str_replace('?'.$match['querystring'], null, $match['path']);
  }
  if (isset($match['port'])) $match['port'] = substr($match['port'], 1);
  // Verify that the domain is indeed a valid FQDN and classify any of its sub-parts
  $match['subdomains'] = explode(".",$match['domain']);
  $match['fqdn'] = $match['domain'];
  $match['tld'] = array_pop($match['subdomains']);
  $match['domain'] = array_pop($match['subdomains']);
  foreach($match['subdomains'] as $domain) if (strlen($domain) < 1 || $domain == '.' || $domain === null) return false;
  if (substr($match['domain'], 0, 1) == '-' || substr($match['domain'], -1) == '-') return false;
  $keys = array_keys($match);
  foreach ($keys as $var) if (is_numeric($var)) unset($match[$var]);
  if (!$match['protocol']) $match['protocol'] = 'http://'; // Protocol is always assumed if not supplied
  if (!isset($match['path']) || strlen($match['path']) < 1) $match['path'] = '/'; // Path is always assumed to be root if not path is supplied
  $add_port = (isset($match['port']) && $match['port'] && $match['port'] != "80") ? ':' .$match['port'] : null;
  $match['URI'] = (isset($match['querystring'])) ? $match['protocol'] . $match['fqdn'] . $add_port . $match['path'] . '?' . $match['querystring'] : $match['protocol'] . $match['fqdn'] . $add_port . $match['path'];
  return $match;
}

Since all web crawlers need to start somewhere it was easy enough to work from a web sites home page and then identify relative and absolute links from there. It’s assumed that the homepage should contain links to all of the key areas of the web site and that all other pages should point back to the home page. This also led me to a deeper understanding of a primary component in SEO. Search engines like web sites that make it easy to discover their site-map through proper linking.

Link Resolution
I had to make a few basic assumptions in sifting through the links of each page with my crawler. Whenever a link leads to a ‘javascript:’ or ‘mailto:’ it is safe to ignore it for the purposes of crawling the site since it is not likely to point to anything in which the crawler will be interested. Whenever the link does not contain a domain name it is not likely to be an internal link. Since some websites will use a relative-path link for some or all of their pages, I needed to ensure that those paths were properly used in forming the complete URL. Anything with a relative-path is obviously considered an internal link. For those links that contained an actual domain name or full URI we needed to determine if the domain name of the web site was a part of this URL to ensure that it was still pointing internally to the same web site. In my test-runs, sub-domains and IP addresses proved somewhat problematic to my methods. I worked around this by simply resolving all IP addresses to their rDNS (where available) or just ignoring it all-together. Allowing the crawler to blindly follow external links was, no-doubt, a bad idea since this would lead to an overload of my modest development server. This is why I had to be very careful in making sure the crawler was only following internal links.
During my early test runs the bot had actually followed a twitter link, which caused it to crawl thousands of pages on twitter and many other sites that just flooded my db with hundreds of thousands of external links. Needless to say I learned that such a bot would need constant monitoring when working in a small development environment that might not be able to handle that much traffic.

Indexing: The Most Cumbersome Search Engine Task
An actual crawler-search-engine is made up of more than one part. It usually has the crawler, which is the automated bot that follows the links on each page to explore a significant portion of the web. It also has an index, which stores the information about the web pages the bot has crawled and sorts them in terms of components that make up its indexing algorithms. The simple bot I described earlier was just one basic part of a search engine, but it was the most relevant part to my particular project.
Later, I decided to take my interests a little further by starting a personal project on the side that involved developing a simple indexing algorithm. This is where everything got really interesting! It appears that different search engines have different ways of indexing the web.
When we use a search engine like Google to search for things that interest us we aren’t really searching the web, but a sort-of copy of the web that is stored in Google’s index. This index doesn’t actually contain every web page on the world-wide-web, but a rather significant portion of it (billions and billions of web pages). It is significant enough so that we can safely assume that when we search Google we are in fact searching the web. This index is also updated constantly, but it isn’t always 100% accurate. Sometimes search engines will fail in finding the most relevant information for your search. The reason for this is that there is so much information on the web and so little information is provided by your search query in order to accurately determine the most relevant results in a reasonable amount of time and without causing the user to supply additional information about their search.
Search engines aim to solve this problem by developing various indexing algorithms that ask additional questions – not to the user, but to the pages in its index. These questions focus mainly on where your search terms fall on the web pages found to contain those terms and how frequent they are on those pages. That’s the most fundamental aspect of most indexing algorithms, but many search engines today take it a lot further. Google, for example, will attempt to exclude your pages from its index if you use terms or phrases too often (possible spaming); Use them too many times and the search is not likely relevant; Use them too few times and the search is also not likely relevant; Use them in your title, but not your URL and the search is likely ranked lower by the indexing algorithm.
At this point what I had was a very simple bot that constantly crawled through all the pages on a particular web site and stored the pages in a MySQL database. There was another script that would sort this index using only a few factors (namely: key-word location, frequency, and external link relevancy). This could be either achieved through writing your own daemon or just simply going about it the easy way, like I did, and using a custom script run by a cron job. I noticed how quickly the index could grow if I let the bot crawl external links. My database went from just a few Megabytes to several Gigabytes within just a couple of weeks.

The Search
Now, all I needed was an actual search component. A script that would return results for a particular search phrase by gathering things like Titles, Web Snippets, Links, and Cached Pages. This is all very similar to what Google does albeit on a much-much smaller scale. I didn’t intend to write a fully functional search engine so some of my techniques are actually quite error-prone and most will probably fail the scalability test. Though I think for a personal project I’m quite psyched about taking up building a search engine further. I may consider one day releasing the code and open-sourcing the project through some distributed source revision control system like git or mercurial. Who knows? For now I’m just happy to share some of my minuscule findings.

Other Uses
So what possible reason would there be to develop your own search engine? It’s true that trying to do what Google has already done falls in the cliché of “re-inventing the wheel”, but that shouldn’t stop us learning from, experimenting with, or redesigning the wheel. There could be a number of other practical applications for these techniques. For example, one might need a search engine for a private Intra-web. You may have a need to index the web in a different manner than those proprietary methods depicted by Google, Yahoo, or MSN. Smaller search engines today that do not get as much traffic as the big search engines can still be found very useful in some niches.