7 ms·
Building a full-text search engine in 150 lines of Python code
- habibur 6y agoExcellent read. Was searching for a full text search engine but not finding any suitable one. Plan to implement one just this way.
- bartdegoede 6y agoAuthor here: you may want to check out something like Whoosh https://whoosh.readthedocs.io/en/latest/intro.html https://whoosh.readthedocs.io/en/latest/intro.html (it's like a clone of Lucene but in pure Python). I've used this to build some basic search for a small Python website and it was more than fast enough for my purposes :-)
- rakoo 6y agoSQLite has a pretty good built-in fts engine: https://www.sqlite.org/fts5.html https://www.sqlite.org/fts5.html
- habibur 6y agoProblem is FTS5 isn't included in the most default installation through package managers [I use Fedora]. And recompiling from source breaks a lot of things, as sqlite libraries are generally linked with all apps that use it.
- rakoo 6y agoI admit I only used sqlite through the go driver (https://github.com/mattn/go-sqlite3 https://github.com/mattn/go-sqlite3) where using fts5 amounts to one flag during the compile phase.
- edwinyzh 6y agoBut SQLite's FTS5 has no support for the `offsets` function...
- dmitriid 6y agoMany years ago I ran into this paper "Self-indexing inverted files for fast text retrieval" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.18.8282&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.18.... It's short and to the point. And then I implemented all that ... in PHP and MySQL :) It feels daunting at first, but once you understand what it wants you to do, it's actually not that hard (for this particular paper, and this particular approach). However, you do want to employ a stemming library to normalize word forms.
- denysvitali 6y agoDoes anybody work for Atlassian here? If so, can you please share this with the Confluence team? Thanks...
- bigtones 6y agoAnd the Jira team
- 12ian34 6y agoJQL really isn't that bad is it?
- tyingq 6y agoIf you want to feel extra sad about it, see this: https://jira.atlassian.com/browse/CONFSERVER-13499 https://jira.atlassian.com/browse/CONFSERVER-13499
- nova22033 6y agoIf a wiki page has the word adrecordset, a search on recordset should include the page. Currently only a search on adrecordset or a search with wildcards returns the page. Wait..this seems unreasonable? Isn't this how it works with elasticsearch or solr? or even google for that matter..a search for green won't return evergreen..
- mlthoughts2018 6y agoI worked previously for a very high traffic ecommerce company (Alexa top 300 site). As part of the search team, I worked on a project where we deliberately rewrote the whole product search engine in Python and Cython, including our own algorithms manipulating documents for deletion, low latency reindexing after edits, and more. We did this because SOLR was too slow and the process of defining custom sort orders (for example, new sort orders defined by machine learning ranking algorithms, and needing to be A/B tested regularly) was awful and performance in SOLR was poor. It was a really fun project. One of the slogans for our group at the time was “rewriting search in Python for speed.” The ultimate system we deployed was insanely fast. I doubt you could have made it faster even writing the entire thing directly in C or C++. It became a reference project in the company to help avoid various flavors of arrogant dismissal of Python as a backend service language for performance critical systems.
- NicoJuicy 6y agoCould i send you a mail somewhere? I'd like to have a casual conversation about e-commerce and some of your insights.
- inertiatic 6y agoDefining custom sort orders in Solr is as simple as uploading a text file with the values you intend to use for ranking. This is a great feature that is in fact missing from Elasticsearch and saves you so much reindexing time. There certainly are usecases where Lucene based solutions aren't the best fit. But I think the claim that you couldn't make something faster by moving away from Python is outlandish.
- IncRnd 6y ago> There certainly are usecases where Lucene based solutions aren't the best fit. But I think the claim that you couldn't make something faster by moving away from Python is outlandish. I read that as a statement that they implemented a proper and bespoke algorithm, not that the speed of Python is greater than C. I am surprised that you read it that way. Who in their right mind would say Python speed is faster than C speed?
- creamytaco 6y agoWhy would one choose Python for this instead of Go or Rust? I imagine Python performance would be terrible.
- theplague42 6y agoBecause it's easier for the average developer to follow Python code? This is a tutorial/demo, not a library.
- bartdegoede 6y agoThe idea was to illustrate the concepts of an inverted index and tf-idf :-) I've built some stuff like this for a smaller project written in Python because it was Easier™ than spinning up an Elasticsearch cluster (ie it definitely didn't need to scale :-D)
- sodapopcan 6y agoYes, I've been really interested in FTS recently and love articles like this. I'm currently implementing a paired-down version myself in Elixir because I'm searching one "table" (not postgres) and I don't want to bring in external dependencies for it.
- neolog 6y agoIf the dataset is small, speed doesn't matter. Also, there's PyPy if you need speed.
- Thaxll 6y agoThe article is good and so can be applied to any language, also Python is not that slow.
- roelschroeven 6y agoAs a lot of the work is done by code library code, there's a very good chance that the code is not all that slow.
- arafalov 6y agoNice introduction. A good ramp-up from basic splitting to ranking. It does need to be said that when Lucene had a set of features this small, it was also pretty tiny. And, if those are the needs, one could still download it and it will probably run on modern JVM: https://archive.apache.org/dist/lucene/java/ https://archive.apache.org/dist/lucene/java/ lucene-1.4.3.jar 2004-11-29 14:13 316K It is a bit bigger of course, but that's because it already had stemmers, multilingual support, multiple Query Parsers including phrase, RAM and Disk directory implementations and a bunch of other advanced features one can easily see by unzipping the jar file.
- finikytou 6y agoit amaze me how much is about creating an eco-system to scale and handling complexity and how software grow to answer that instead of trying to split into two different piece of software. Many people/companies/websites just need those basic features when search is not a core essential capability
- arafalov 6y agoWell, Solr and Lucene projects are right now in the process of splitting up (after joining for versions 3-8). And, you could have always used Lucene directly as an embedded search library. Amazon does, for example, for their customer facing search as their scalability patterns do not align with either Solr or Elasticsearch. And if you do use Lucene directly, you can choose just the libraries that apply to your use case. I think at minimum, you can get away with maybe 3 jars (core, queryparser, analyzers-common) and that's just over 5Mb for the latest Lucene, which includes things like: http://blog.mikemccandless.com/2021/03/open-source-collaboration-or-how-we.html http://blog.mikemccandless.com/2021/03/open-source-collabora... Sometimes, there is a disconnect between implementation that is very flexible and messaging that just shows 'use everything' garden path.
- fakedang 6y ago> Amazon does, for example, for their customer facing search as their scalability patterns do not align with either Solr or Elasticsearch. Can you explain this to a non-programmer?
- ignoramous 6y agoReminds of this David Crawshaw (CTO at Tailscale) presentation on full-text search with SQLite which probably requires 10 lines or less: https://www.youtube-nocookie.com/embed/RqubKSF3wig https://www.youtube-nocookie.com/embed/RqubKSF3wig
- edoceo 6y agoYea! FTS5 FTW! Amazing for what it costs.
- asdfasgasdgasdg 6y agoIt's not relevant or an indicator of power that this example requires ten lines of SQL. This presentation just uses SQLite's builtin full-text search system [1]. Of course it's going to require less code to call a library than to implement it. [1]: https://sqlite.org/fts5.html https://sqlite.org/fts5.html
- ignoramous 6y agoRelevant because "building a full-text search engine" is solved using SQLite just as much as it can be solved by writing Python on top of lxml and py-stemmer. SQLite is no heavyweight dependency àla Apache Lucene. It also helps that it is bundled in billions of Android and iOS devices.
- asdfasgasdgasdg 6y agoI'm sure there's some pypi package that has a full search system you can download. For that matter, there's the python sqlite package. It's irrelevant that it's ten lines of library calling code when you're comparing it to a toy implementation.
- arafalov 6y agoApache Lucene can be as small as 5Mb, if you don't load what you don't need.
- runningmike 6y agoUsing nlp techniques to create tokens is for a fast and simple python search often not needed. It makes things slow and python standard string function are often good enough. Issues arise when searching for combinations of words like ‘machine learning’ in a sentence. Nice read, but the GitHub repro needs a license to be more useful.
- bartdegoede 6y agoAdded an MIT license. Have fun :-)
- superyesh 6y agoNeat! One production ready python library I love to use in this space is https://radimrehurek.com/gensim/ https://radimrehurek.com/gensim/ It is quite mature and can handle a good amount of data well! It offers topic modeling too and can b helpful to find similar documents also.
- machiaweliczny 6y agoCool article. I recently build program in Go that takes wikipedia article and gets all dependencies then using tfidf*count ranks concepts in order of "importance". Seems quite good for math articles to get list of more basic concepts to understand first.
- throwaway320912 6y agoFun times. I once applied pagerank onto a set of 8000 math articles and ran the result as a web app in 2009/10. http://web.archive.org/web/20091230103939/http://myyn.org/m http://web.archive.org/web/20091230103939/http://myyn.org/m As a gimmick, I created 36 groups, with group 1 containing the most important concepts: http://web.archive.org/web/20100109055506/http://myyn.org/m/chambers/1/ http://web.archive.org/web/20100109055506/http://myyn.org/m/... Spoiler, the top ten concepts were: Function · Set · Number · Integer · Real Number · Point · Property · Finite · Ring · Relation Theory BTW: Glad the archive has a copy, because I do not.
- sdfhbdf 6y agoWow thats such a cool idea. Really nice.
- andrewmatte 6y agoThis doesn't account for synonyms. I'd rather use a document embedding search.
- KAdot 6y agoThe article looks suspiciously similar to https://artem.krylysov.com/blog/2020/07/28/lets-build-a-full-text-search-engine/ https://artem.krylysov.com/blog/2020/07/28/lets-build-a-full.... Very similar examples, code and structure.
- diogenesjunior 6y agoExcept that one is written in go and the other in python...
- johnwheeler 6y agoYes, but where's the attribution?
- pmiller2 6y agoSo? Wikipedia is one of the most convenient, large English corpora available, and I doubt there are many significantly different ways to write the bit of functionality that's built up here. I'm not sure if that's what you're meaning to suggest, or that there was some kind of plagiarism / inspiration going on here.
- google234123 6y agoI think it is plagiarize. Compare "def analyze" and "func analyze". Very similar.
- happyweasel 6y agoAs Joel spolsky said: "Just do me a favor and search the damned hard drive, quickly, for the string I typed, using full-text indexes and other technologies that were boring in 1973."
- boynamedsue 6y agoreturn [token for token in tokens if token] What the what?
- mplanchard 6y agoAka list(filter(None, tokens)) Or list(filter(lambda x: bool(x), tokens))
- throwaway1777 6y agoLol. Compact map.
- suresk 6y agoComprehensions in Python are pretty handy, but they can look weird sometimes. This is filtering out `None`, empty string, etc values from a list. It is iterating over a list (tokens) and creating a temporary variable (token). It tests the truthyness of it (if token), which means None and '' will return False and thus be excluded, and then returns it (the first token).
- xmly 6y agoVery nice work! Thank you for sharing.
- gfxgirl 6y agoFailed for me. I use Chinese and Japanese. There are no spaces to split on. I also search code where this also fails. I know it was meant to be simple and illustrate some points. I think the point it fails at is that this is actually a much harder problem in real life than a simple 150 line solution suggests.
- samcodes 6y agoif you use a library for Chinese/Japanese tokenization (which is harder because the lack of space), it seems like the rest of the code would work?
- js2 6y agoA well worked example using Python and Redis: https://redislabs.com/ebook/part-2-core-concepts/chapter-7-search-based-applications/7-1-searching-in-redis/7-1-1-basic-search-theory/ https://redislabs.com/ebook/part-2-core-concepts/chapter-7-s...
- rcarmo 6y agoI went down this rabbit hole some ten years ago, and somewhere along the line I discovered SQLite has an FTS engine (up to version 5 now, I think) and just started using that instead. Massive performance for tens of gigs’ worth of text content on a single core.
- Bridgeburner4 6y ago@op great article. I ran your code first without fully reading the article. It took the code almost an hour to parse and index the data using the terminal. A suggestion, if you want to make the code more friendly. Either: 1. Write a note to README.md that once you exit the program, you loose the indexed data. or 2. Save the indices to disk. :) thanks for the article