meilisearch/charabia

Implement an efficient `Nonspacing Mark` Normalizer

ManyTheFish opened this issue · 2 comments

ManyTheFish commented

In the Information Retrieval (IR) context, removing Nonspacing Marks like diacritics is a good way to increase recall without losing much precision, like in Latin, Arabic, or Hebrew.

Technical Approach

Implement a new Normalizer, named NonspacingMarkNormalizer, that removes the nonspacing marks from a provided token (find a naive implementation with the exhaustive list in the Misc section).
Because there are a lot of sparse character ranges to match, it would be inefficient to create a big if-forest to know if a character is a nonspacing mark.
This way, I suggest trying several implementations of the naive implementation below in a small local project.

Interesting Rust Crates

  • hyperfine: a small command-line tool to benchmark several binaries
  • roaring-rs: a bitmap data structure that has an efficient contains method
  • once_cell: a good Library to create lazy statics already used in the repository

Misc

Hey! 👋
Before starting any implementation, make sure that you read the CONTRIBUTING.md file.
In addition to the recurrent rules, you can find some guides to easily implement a Segmenter or a Normalizer.
Thanks a lot for your Contribution! 🤝

crudiedo commented

Hi everyone,

I’ve got the implementation prepared for the PR, but first wanted to agree on the data structure we’re going to use.

As proposed, I’ve made a sample app and did some benchmarking - you can find it there:

https://github.com/crudiedo/nonspacing-bench

The results are quite interesting - it looks like the built-in HashSet structure performs better than roaring bitmap (at least on my machine and using the 1.5MB sample text):

Naive                time:   [22.296 ms 22.378 ms 22.461 ms]  

BTreeSet             time:   [14.278 ms 14.335 ms 14.394 ms] 

RoaringBitmap        time:   [15.217 ms 15.274 ms 15.333 ms] 

HashSet              time:   [9.5395 ms 9.5683 ms 9.5972 ms]

Of course there's still a memory difference matter, but I believe the speed is the priority especially since there are only 1281 marks to store.

I'm still not sure how to properly measure data structure size in Rust (besides 4 bytes for u32 * 1281 lol), so I used jemalloc and it's 328480 bytes allocated for a sample using hashset vs 289632 for roaring one.

So I believe we should be good with HashSet (or BTreeSet if I'm missing something about HashSet), and there's no need to use RoaringBitmap.

Thanks, let me know your thoughts and I'll move forward with submitting PR (:

ManyTheFish commented

Hey @crudiedo.

I tried your repo and here are my results:

Naive                   time:   [58.785 ms 58.823 ms 58.860 ms]

BTreeSet                time:   [13.723 ms 13.728 ms 13.733 ms]

RoaringBitmap           time:   [13.142 ms 13.148 ms 13.154 ms]

HashSet                 time:   [10.567 ms 10.578 ms 10.591 ms]

it's funny that the Naive approach has a lower performance than on your computer. 🤯

I think that using a HashSet is a good idea too, nice job! 👍

You can create a PR by replacing the current Hebrew normalizer, it is a good base to introduce your work, therefore, nonspacing marks include the Hebrew diacritics.

  • ❤️2