kmschaal

Space-filling curves as a traveling salesman heuristic is a really nice application I was not aware of. I have mostly seen them in the context of domain decomposition for parallel computing, where you cut the curve at n points to obtain n+1 disjoint domains.

Tested it and you are right, thanks for the clarification.

OP here, I wanted to add one technical note I forgot to mention in the post.

The prefix search uses the same suffix array as the substring search. This approach might also be useful for other search libraries that rely on suffix arrays. It can improve the search experience with minimal additional effort.

Happy to discuss the implementation details if anyone’s curious!

μFuzzy has a great comparison project that could serve as a reference for all fuzzy search implementations. My fuzzy searcher (v1) is already included and will soon be updated to v2 (PR is open).

Thank you! I will do a comparison in the near future and update the readme.

Thank you for your explanation, I get your point. Regarding your last suggestion: I think it would be great to measure how often the correct result is near the top. However, don't we face the same issue as before? What is the correct result? Is it the term the user has in mind when writing the query? But what if they make a typo, and the term with the typo also exists in the dataset? Or they just type half of the term they are thinking of, but there are many terms in the dataset with the same prefix?

So, in the end, I believe it's worthwhile to try different implementations and share our subjective experiences.

Hi, thank you for your questions. Unfortunately there are no comparisons yet. The gif is simply a looped screen recording created with Camtasia. Best regards!

Glad to hear that it works well, will look into it.

Thank you for your comment! It is indeed a problem in plain fuzzy search libraries (like this one) that substring matches can have a lower quality than unequal strings of similar length. A solution to that is to implement a higher level search controller that queries the fuzzy searcher, as well as a suffix array searcher. The controller than mixes the matches and returns the best matches across the two searchers. One can even add more searchers, e.g. a phonetic one. With the correct parameters this approach works well.

Thank you, sounds great!

Hi, thanks for sharing! No, I haven't taken wasm into consideration. It would be interesting to see the performance gain, in particular for indexing.

Sorry for the confusion. I think you could generate the memento each time you compile your blog into HTML. The memento can be stored as a json file and served statically by your fileserver. When a user visits your page, retrieve the memento from the server. Then, initialize the searcher with it. In this way you avoid indexing content at runtime.

As a bonus you could cache the memento in the local storage or session storage.

Thank you for your kind feedback! That's a great idea. I have implemented a memento object that can be used for transferring the serialized state of the searcher. The intent of the implementation was to transfer the searcher between a web worker and the main thread. You could try to serve the Memento from the server and store it in an index db. You may have a look at the web worker example I provide in the repository.

It's subjective, I have to admit. I would say a search is accurate if most people find what they are looking for in their dataset in the first try.

Distance definitions such as the Levenshtein and Damerau-Levenshtein distances provide a solid basis for discussions on accuracy. However, they are costly to compute and hence not widely adopted in fuzzy search libraries.

I started by using the known filter equation for the Levenshtein distance and computed a quality score with a leightweight formula. Then, I realized that the filter equation can be extended to the Damerau-Levenshtein distance by sorting the characters of the 3-grams.

In my tests, this implementation worked well. Please let me know how it works for you if you test it.

Thank you!

Hi, thank you for your interest! I believe that most fuzzy search implementations lack accuracy in one aspect or another. The primary goals of my library are accuracy and query performance. However, I haven't looked into Fuse yet. I'm highly interested in hearing feedback from people who have tried both libraries with their datasets.

I think What3Words is in principle a nice idea, but it could have been implemented much better. I am thinking of the following:

- have a fixed pattern, e.g. adjective.adjective.noun.

- create groups of words and put them in hierarchies. E.g. noun->animal->predator

- cover the world with a one-dimensional Hilbert curve

- Increment the noun along the curve. When all nouns are exhausted, start with the first noun again and increment the adjective in the middle, a.s.o. (analog to how incrementing a number with several digits works).

With this approach, the location purple.flying.tiger would be next to purple.flying.lion.

Thank you for your kind feedback. As a backend developer, I wouldn't have been able to build this site from scratch. Instead, I opted for an HTML5 UP! template (https://html5up.net/), which turned out to be one of the best 20 bucks I've ever spent.

Thank you for sharing. The example, where the same sentence is presented with different labels, effectively illustrates the essence of the idea.

Thank you for your comment. Your experience leads me to believe that the concept might be more useful for non-native speakers. The labels have helped us shorten lengthy PR discussions and focus on the factual aspects. For context: I work in a German company with an international team, and we use English as our business language

The blog post explores the idea that code review comments should be more than just polite and respectful – they should convey their intent clearly and effectively. As developers, we're well aware of the complexity of code, and communication around it should be streamlined and efficient.

Semantic comments come with labels that convey their purpose, whether it's a simple remark, a question seeking an answer, a hint for future consideration, a suggestion open for discussion, an important point requiring change, or a crucial issue that must be addressed.

I can second this; from my experience reading text backwards greatly helps with finding typos. The reason for this is presumably that in this way it is easier to force our brain to look at every single word in isolation. In normal (forward) reading we process more than one word at a time.