3 ms·

Back in 2006 I wanted to learn more about how search engines worked, so I started porting Lucene to Common Lisp. Actually, I wrote a Common Lisp port of Ferret.

Back in 2006 I wanted to learn more about how search engines worked, so I started porting Lucene to Common Lisp. Actually, I wrote a Common Lisp port of Ferret. Ferret is a Ruby port of Lucene. Lucene is sort of Doug Cutting's Java version of Text Database (TDB), which he and Jan Pedersen developed at Xerox PARC, and which, to complete the circle, was written in Common Lisp. I didn't know Ruby, and I didn't know search engines, but I did know Common Lisp. It took me 7 months to create a binary-compatible, pretty dang functional port of Lucene. I called it Montezuma[1], and it's still actually used by people. About half the time was spent implementing the text analyzer, document store, and indices. The remaining 50% was spent implementing search (and parsing the query language). It was a very rewarding experience--It was one of the largest projects I'd worked on, mostly solo (I got some help near the end), in an area I knew nothing about, working in an extremely test-driven fashion (over 2000 unit tests when I was done). I did not, however, learn as much about indexing and search as I expected. I learned a lot, yes, but quite a bit of the Ruby code was so easy to translate to Common Lisp that I didn't have to understand everything in order to make it work. I still recommend writing a small search engine as an interesting exercise, though. 1. https://github.com/sharplispers/montezuma https://github.com/sharplispers/montezuma

fizx 7y ago
LMAO Ferret was sooo bad. It was written by a guy who effed off to Japan to study Jujitsu, and I remember my first startup job was porting all of its ints to size_t.
ignoramous 7y ago
A footnote: For Java devs out there, the Lucene codebase is a joy to read [0]. Esp, the APIs. Highly recommend it just for the documentation which is top-notch. Michael McCandless, Lucene's committer-in-chief, sometimes blogs about its internals [1]. [0] https://github.com/apache/lucene-solr/tree/master/lucene https://github.com/apache/lucene-solr/tree/master/lucene [1] http://blog.mikemccandless.com/2019/10/concurrent-query-execution-in-apache.html http://blog.mikemccandless.com/2019/10/concurrent-query-exec...
misterman0 7y ago
Or, instead of porting Lucene, just take its main concepts such as analysis, tokenization, an in-memory trie or binary search tree, query parser, term, query and collector and implement them the way _you_ would and using whatever bit maps and other file formats _you_ see fit when serializing to disk. If you iterate enough times you'll realize that as you have grown in your capacity of understanding these concepts your code base has turned into quite an approximation of Lucene, with the same flaws and the same strengths. If you feel Lucene is close to a global, or at least a very high local optima, then by now you know search. Now the real fun begins, because now you get to implement your own search model as either a Lucene model or one that is supported by your own code. There are ten or twelve really interesting problems to solve before you can call it a day. Before you're done, you'll start to see everything and I do mean everything as a search problem. Use Wikipedia as your tutor but prepare yourself to have your current world view become completely transformed, because what's a search problem, really? What's a word? What's a phrase? What's their meaning? What's this word's meaning in the context of these other words? What's a paragraph? What's the meaning of this paragraph, in the context of these other paragraphs? What are some of the patterns we can perceive in the binary representation of our data? What are some of the patterns we can perceive in the vector space representation of our data? The answers to these questions and more lies in the search model and implementing one is the most fascinating thing there is, because no one, not even Google's top engineer, knows what the correct set of questions are.

fizx 7y ago

LMAO Ferret was sooo bad. It was written by a guy who effed off to Japan to study Jujitsu, and I remember my first startup job was porting all of its ints to size_t.

ignoramous 7y ago

A footnote: For Java devs out there, the Lucene codebase is a joy to read [0]. Esp, the APIs. Highly recommend it just for the documentation which is top-notch. Michael McCandless, Lucene's committer-in-chief, sometimes blogs about its internals [1]. [0] https://github.com/apache/lucene-solr/tree/master/lucene https://github.com/apache/lucene-solr/tree/master/lucene [1] http://blog.mikemccandless.com/2019/10/concurrent-query-execution-in-apache.html http://blog.mikemccandless.com/2019/10/concurrent-query-exec...

misterman0 7y ago

Or, instead of porting Lucene, just take its main concepts such as analysis, tokenization, an in-memory trie or binary search tree, query parser, term, query and collector and implement them the way _you_ would and using whatever bit maps and other file formats _you_ see fit when serializing to disk. If you iterate enough times you'll realize that as you have grown in your capacity of understanding these concepts your code base has turned into quite an approximation of Lucene, with the same flaws and the same strengths. If you feel Lucene is close to a global, or at least a very high local optima, then by now you know search. Now the real fun begins, because now you get to implement your own search model as either a Lucene model or one that is supported by your own code. There are ten or twelve really interesting problems to solve before you can call it a day. Before you're done, you'll start to see everything and I do mean everything as a search problem. Use Wikipedia as your tutor but prepare yourself to have your current world view become completely transformed, because what's a search problem, really? What's a word? What's a phrase? What's their meaning? What's this word's meaning in the context of these other words? What's a paragraph? What's the meaning of this paragraph, in the context of these other paragraphs? What are some of the patterns we can perceive in the binary representation of our data? What are some of the patterns we can perceive in the vector space representation of our data? The answers to these questions and more lies in the search model and implementing one is the most fascinating thing there is, because no one, not even Google's top engineer, knows what the correct set of questions are.