Hacker News new | ask | show | jobs
by cirwin 987 days ago
I wrote something like this for contact auto completion - running in the browser we had to ensure that both tree construction was fast, and also that completion was instantaneous. So the next level of optimization is to amortize tree construction over searches (using the observation that most of the tree is never accessed)

https://github.com/superhuman/trie-ing
2 comments
leeoniya 987 days ago
interesting. i made something much more stupid, but brutally effective: https://github.com/leeoniya/uFuzzy

i guess if you wanted results ordered by contact frequency you can just keep the original haystack sorted by frequency, and would get the Richard match first. or keep the frequency in an adjacent lookup and sort/pick the result afterwards.

PSA: don't use the ultra popular Fuse.js for fuzzy matching, it's super slow and has pretty terrible match quality. e.g. https://leeoniya.github.io/uFuzzy/demos/compare.html?libs=uF...

link
rockwotj 987 days ago
If youre interested in a TypeScript fork of this that also supports deletion, see here: https://github.com/shortwave/trie

There are also a couple of bug fixes in there, for example: https://github.com/shortwave/trie/commit/1e7045d89cc20011251...

link