search

ajmalsiddiqui / levenshtein-diff

A fast, generic implementation of Levenshtein's Algorithm for any kind of sequence, along with the ability to generate edits and regenerate the target sequence by applying edits to the source sequence.
MIT License
8 stars 3 forks source link

[Feature Request] Weighted distances #3

Open atomflunder opened 2 years ago

atomflunder commented 2 years ago

Hi there!

Coming from using the RapidFuzz library in Python, a feature I liked to use was weighted distances. RapidFuzz Docs.

Do you think this would be possible to implement here without too much issue? I know parameters might pose a design problem as there are no optional arguments in Rust and having every function always take weights might be annoying to users. Maybe a separate function would be useful? Would you be open to contributions?

Thanks in advance for responding!

ajmalsiddiqui commented 1 year ago

Hello!

Thanks for filing the issue, and apologies for getting back to you so late.

I am definitely open to contributions!

Could you possibly elaborate on the use cases you have for weighted distances in this context?

Regarding the API itself, I think we can get away without causing any breaking changes. We could move the logic of the algorithm to functions that work with weights, and the existing API could just be wrappers around this that use (1,1,1) as weights. We'd also want to incorporate the weights into the DistanceMatrix (which possibly have to go from a type alias to a struct wrapping the weights). So at first glance, it sounds doable.

atomflunder commented 1 year ago

Hi thanks for respoding!

Could you possibly elaborate on the use cases you have for weighted distances in this context?

In Python, I often times used Insertion/Deletion weights of 1, and Substitution weights of 2, because I personally found this yields better results when trying to find the best match between a string and a list of other strings. This is baked into the RapidFuzz library I mentioned before as the "Indel distance".

As for the implementation, I also thought about just having a struct where you set the weights one time (with a default of (1,1,1)) and then have the functions as methods of that struct, as it is more idiomatic Rust (I think), but I also really like your suggested approach. Not dealing with major breaking changes is probably a very good idea.

Edit: I forked the repo and implemented a rough prototype of both approaches in separate branches with breaking changes and without. Let me know what you think!