A search engine in 80 lines of Python

What is the point of flexing about LOC, if it is not a total number of \r\n since we are using external deps? I know that there is no unit for codebase in SI system, but I think we should measure cognitive load somehow.

This is really cool. I have a pretty fast BM25 search engine in Pandas I've been working on for local testing.

https://github.com/softwaredoug/searcharray

Why Pandas? Because BM25 is one thing, but you also want to combine with other factors (recency, popularity, etc) easily computed in pandas / numpy...

BTW phrases are the hard thing. There are a lot of edge case in phrase matching. Not to mention slop, etc. And you want to compact positions into as little memory as possible

https://github.com/softwaredoug/searcharray/blob/main/search...

Looking at the code (src/microsearch/engine.py), we have:

    class SearchEngine:
        def __init__(self, k1: float = 1.5, b: float = 0.75):
            self._index: dict[str, dict[str, int]] = defaultdict(lambda: defaultdict(int))
            self._documents: dict[str, str] = {}
            self.k1 = k1
            self.b = b

Looking at `_documents`, I'm guessing the keys are URLs and the values contents of those URLs, but i might be wrong.

The whole thing looks like it would've been a useful resource for people to learn how to build search engines with, that people could build on, had the writer been bothered to document it. But as it is I'm disappointed with the poor code.

Is it really a good idea to build something like this (big data, needs to crunch data fast) in Python (slow)?

Don't use keywords (1-grams), the best results for English can be achieved with 2+3-grams. n-grams retain context.

Imo, it's not fair to talk about 80 lines of code while using thitd party libraries (feedparser, bs4, etc)

Google allows you to search for "search engine" (notice the double quotes) and it’ll only show you results where the two words appear in this specific order.

At least only some of the time, unfortunately. What power users want is "grep for the Web", not "Google, tell me what you want me to see."

I have myself dabbled a little bit in that subject. Some of my notes:

- some RSS feeds are protected by cloudflare. It is true however that it is not necessary for majority of blogs. If you would like to do more then selenium would be a way to solve "cloudflare" protected links

- sometimes even selenium headless is not enough and full blown browser in selenium is necessary to fool it's protection

- sometimes even that is not enough

- then I started to wonder, why some RSS feeds are so well protected by cloudflare, but who am I to judge?

- sometimes it is beneficial to cover user agent. I feel bad for setting my user agent to chrome, but again, why RSS feeds are so well protected?

- you cannot parse, read entire Internet, therefore you always need to think about compromises. For example I have narrowed area of my searches in one of my projects to domains only. Now I can find most of the common domains, and I sort them by their "importance"

- RSS links do change. There need to be automated means to disable some feeds automatically to prevent checking inactive domains

- I do not see any configurable timeout for reading a page, but I am not familiar with aiohttp. Some pages might waste your time

- I hate that some RSS feeds are not configured properly. Some sites do not provide a valid meta "link" with "application/rss+xml". Some RSS feeds have naive titles like "Home", or no title at all. Such a waste of opportunity

My RSS feed parser, link archiver, web crawler: https://github.com/rumca-js/Django-link-archive. Especially interesting could be file rsshistory/webtools.py. It is not advanced programming craft, but it got the job done.

Additionally, in other project I have collected around 2378 of personal sites. I collect domains in https://github.com/rumca-js/Internet-Places-Database/tree/ma... . These files are JSONs. All personal sites have tag "personal".

Most of the things are collected from:

https://nownownow.com/

https://searchmysite.net/

I wanted also to process domains from https://downloads.marginalia.nu/, but haven't got time to read structure of the files

Nice! It wouldn't be much work to add fuzzy-search functionality (all results with a prefix edit-distance below some threshold delta, so that a search for "hackrnew" matches "hackernews"). Basically, what you would do is you add an additional inverted index, but this time the keys are n-grams of words in your document collection (typically 3-grams), and the postings are the words (or their ID) in which these n-grams occur. There is then a nice lemma that basically says the following (where PED is the prefix edit distance, and N(x) are the n-grams of word x):

If PED(x, y) <= delta, then |N(x) ∩ N(y)| >= |N(x)| - n ∙ delta

That is, x and y must have at least |N(x)| - n ∙ delta n-grams in common to have a PED(x, y) less then or equal to delta.

If you now have an input x, you calculate N(x) and retrieve all postings from the n-gram index for each n-gram of x. You can now merge all of these postings and get a list that looks like this: [worda, worda, worda, wordb, wordb, wordc] (for each q-gram x and some word y have in common, you get one entry of y). If you merge the duplicates, you get: [(worda, 3), (wordb, 2), (wordc, 1)], and for each y (in this case, worda, wordb, wordc), the number in the corresponding tuple is |N(x) ∩ N(y)|.

If this number is larger than |N(x)| - n ∙ delta, you explicitly compute PED(x, y) and check whether it is below your threshold. If the number is smaller, you can simply skip it, saving you large amounts of costly PED calculations.

Your result is a list of words y with a PED(x, y) to the input x below some threshold, and you can then use this list of words to query your existing index.

I used this approach many years ago to implement a fuzzy client-side JS search engine on https://dont.watch/ (if you look into the JS code, you can see that the inverted index and the (compressed) n-gram index are simply transferred in the JS-file). The actual search engine is around 300 lines of JS, with no external dependencies and some very basic heuristics to improve the search results).

i know it is unrelated but i liked your website.

This is very cool and very educational. Don't deploy it, though. :-)

I needed something like this once, but at a little bit larger scale (few tens of thousands of documents). The answer, as always, was [sqlite](https://www.sqlite.org/fts5.html); structurally though it's just what you have here but with someone else writing the inverted-index persistence layer.

Also, forgot to add, for this approach you better use sketches (bloom filter/hyperminhash). Same results with lightning performance.

Thanks for this lovely well written account. Made me wish I still taught this kind of coding because it would be such a lovely example for students to work through. (We used to do a bootcamp of build your own Facebook and Google in a week) Very inspirational.

Checks out. Most of the difficulty in search is dealing with the data volume. The logic itself is surprisingly easy, or it can be. Of course you can complicate it endlesssly, but this project successfully cuts most of the fluff...

So with that in mind, approaching the problem not as one of how to make the search engine bigger, but the data smaller (physically or better signal/noise ratio) goes a very long way.

just fyi, PageRank and BM25 address orthogonal problems of reputation/popularity (PageRank) and query/semantic matching (BM25). Saying you're using bm25 instead of PageRank makes no sense.

I like it!

Here is a recommendation engine in < 20 lines of python to go along your search engine (if you keep session logs of clicked urls).

  def build_recommendations(logs: List[List[str]], window_size: int = 10, 
  max_recommendations_per_url: int = 50) -> dict:
      recommendations = {}
      for session in logs:
          for i in range(0, len(session)-1):
              url_id = session[i] # reference element
              window = session[i+1 : i+window_size] # sliding window
              recommendations[url_id] = recommendations.get(url_id, {})
              for pos, next_link in enumerate(window):
                  weight = window_size - pos # elements in the window get decreasing weight proportional to their distance from the reference element
                  recommendations[url_id][next_link] = recommendations[url_id].get(next_link, 0)
                  recommendations[url_id][next_link] += weight
    
      for url_id, link_recommendations in recommendations.items():
          # sort and truncate the recommendations
          recommendations[url_id] = dict(sorted(link_recommendations.items(), key=lambda item: item[1], reverse=True)[:max_recommendations_per_url])

      return recommendations

  recommendations = build_recommendations(your_logs)
  print(list(recommendations[some_url_id].keys())) # gives an ordered list of the recommended url_ids for the given url_id

chunk for chunk in chunks if chunk

I believe there's a saying about a woodchuck somewhere in here

Why not use whoosh? https://whoosh.readthedocs.io/en/latest/quickstart.html

For an inverted index with JavaScript/Typescript, here is my implementation: https://github.com/vasilionjea/lofi-dx

It was a fun little project but definitely way more than 80 LOC :)

Really cool project! Building a search engine from the ground up to tackle small site discoverability? That's a challenge I can get behind. I'm especially into how you used asyncio in Python for faster crawling – smart move.

But, let's talk scale and features. As it stands, handling bigger data sets or adding more complex search features might be tough. On the features side, playing around with query operators or n-gram indexing could seriously level up your search results.

Expanding beyond RSS for content could also give your engine a nice touch. Just throwing in my thoughts – been around the block with search tech a bit. Can't wait to see what's next for your project!

This checks out! Pretty much exactly what we did in my undergrad Information Retrieval class.

Last time I checked lxml.html and lxml.html.clean (possibly with cssselect) were much faster than BeautifulSoup. Not sure this is still the case.