Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A search engine in 80 lines of Python

alexmolas.com

Post reply on HN
Print view View original

61–70 of 100 posts

Re: A search engine in 80 lines of Python

#61

Post by alexmolas »

Barrin92 wrote: post #56
cabalamat wrote: post #47

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 I've no idea what `k1` or `b` are. Nor is there a single comment in the entire file. Are comments considered unfashionable these days? Looking at `_…

this trend of `a: float` always reminds me of the Rich Hickey "you don't want types, you want proper names" talk. I really hate this (feels to me Go inspired) tendency of undescriptive single letter variable, with the type system abused as a naming assistant. Names can convey proper semantic information about what your program does, use them godammit

I agree with you that better names are always preferable. But type hints also work as documentation. We can have both.

However, in this particular case the undescriptive names are like this for historical reasons. I agree these are not the best names, but are the names used in the literature. If I was working in a physics I would probably use "c" as the speed of light or "kb" as the Boltzmann constant, which are non very descriptive names.

Re: A search engine in 80 lines of Python

#62

Post by planb »

Barrin92 wrote: post #56
cabalamat wrote: post #47

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 I've no idea what `k1` or `b` are. Nor is there a single comment in the entire file. Are comments considered unfashionable these days? Looking at `_…

this trend of `a: float` always reminds me of the Rich Hickey "you don't want types, you want proper names" talk. I really hate this (feels to me Go inspired) tendency of undescriptive single letter variable, with the type system abused as a naming assistant. Names can convey proper semantic information about what your program does, use them godammit

This is right, but if you are implementing a formula known in the domain or documented elsewhere, you can (and should) use the letters used in the formula (in this case, b and k1) instead of making up names.

Re: A search engine in 80 lines of Python

#63

Post by alexmolas »

cabalamat wrote: post #47

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 I've no idea what `k1` or `b` are. Nor is there a single comment in the entire file. Are comments considered unfashionable these days? Looking at `_…

Hi, author here.

If I wanted a catchy title for the post I needed to cut the number of LOC as much as possible;)

Joking apart, thanks for your feedback. I agree that usually it's better to have documentation and code together, but in this case since it's an educational project I decided to split code and documentation, and document the code in a blog post.

Re: A search engine in 80 lines of Python

#64

Post by robertlacok »

karolist wrote: post #7
serialNumber wrote: post #6

Earlier quoted context omitted.

Huh? I check Hacker News multiple times a day - it's not odd to click on an article within an hour of it being posted.

It's not the first time I saw an article posted and then an expert in the field comment on it rather quickly, I thought I may be missing something how other people use this site, had no negative intentions asking this and thanks for the answer ;)

https://f5bot.com is a way to get an email notification when a keyword is mentioned

Re: A search engine in 80 lines of Python

#65

Post by sampo »

Barrin92 wrote: post #56
cabalamat wrote: post #47

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 I've no idea what `k1` or `b` are. Nor is there a single comment in the entire file. Are comments considered unfashionable these days? Looking at `_…

this trend of `a: float` always reminds me of the Rich Hickey "you don't want types, you want proper names" talk. I really hate this (feels to me Go inspired) tendency of undescriptive single letter variable, with the type system abused as a naming assistant. Names can convey proper semantic information about what your program does, use them godammit

> tendency of undescriptive single letter variable

There are 2 schools of thought on which one is clearer,

    F = G * m1 * m2 / r**2
or

    force = gravitational_constant * mass_of_body_1 * mass_of_body_2 / distance_between_bodies ** 2

Re: A search engine in 80 lines of Python

#66

Post by einpoklum »

pphysch wrote: post #22
smalu wrote: post #15

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.

It's meaningful here because if it said "A search engine in 4000 lines of Python" most readers' eyes would glaze over, but 80 is short enough to warrant a glance.

"A search engine in 80 columns of Python code!"

Re: A search engine in 80 lines of Python

#69

Post by lqet »

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) = |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).

Re: A search engine in 80 lines of Python

#70

Post by alpinelogic »

softwaredoug wrote: post #2

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…

Hey, I tackled phrase matching in my toy project here: https://github.com/vasilionjea/lofi-dx/blob/main/test/search...

I think I tested it thoroughly but any feedback would be appreciated!

Edit: I delta-encoded and base36-encoded the positions

Post reply on HN