ajmalsiddiqui / levenshtein-diff Goto Github PK

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!

The generate_edits function currently only returns an Err if the matrix passed in is incorrect in some way. In my opinion, it makes much more sense to remove that parameter, call distance internally, and return only the Vec<Edit<T>>.

The downside of doing it this way is that the user can no longer select which version of the levenshtein functions they use. However, I don't see that as a major downside compared to simplifying the API.

I'm willing to write a PR for this if you agree with the idea.

1D vectors are faster and use less memory compared to 2D vectors

https://stackoverflow.com/questions/17259877/1d-or-2d-array-whats-faster

Would you be open to a PR that rewrites the library to use 1D vectors instead? This would obviously be a breaking change.

If so, do you think it's a better idea to use an existing crate like https://docs.rs/array2d/latest/array2d/index.html or just implement the basic logic needed by hand?

Calculating the distance between two collections, where one collection is an exact copy of the other except for the presence of the first item, appears to result in an invalid distance matrix:

fn main() {
    let collection_1: Vec<String> = vec!["Hello".into(), "World".into()];
    let collection_2: Vec<String> = vec!["World".into()];

    let (distance, matrix) = levenshtein_diff::distance(&collection_1, &collection_2);
    let _edits = levenshtein_diff::generate_edits(&collection_1, &collection_2, &matrix);

    println!("levenshtein distance of {distance}");
}

Error log:

   Compiling test-crate v0.1.0 (C:\Users\<private>\test)
    Finished dev [unoptimized + debuginfo] target(s) in 0.50s
     Running `target\debug\test-crate.exe`
thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: InvalidDistanceMatrixError', src\main.rs:6:90
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
error: process didn't exit successfully: `target\debug\test-crate.exe` (exit code: 101)

This also appears to occur when the first and second items are swapped:

fn main() {
    let collection_1: Vec<String> = vec!["Hello".into(), "World".into()];
    let collection_2: Vec<String> = vec!["World".into(), "Hello".into()];

    let (distance, matrix) = levenshtein_diff::distance(&collection_1, &collection_2);
    let _edits = levenshtein_diff::generate_edits(&collection_1, &collection_2, &matrix); // thread 'main' panicked at 'called `Result::unwrap()` on an `Err` value: InvalidDistanceMatrixError', src\main.rs:6:90

    println!("levenshtein distance of {distance}");
}

The Levenshtein functions are often used in performance-critical code. I think it would be good to have benchmarks to advertise the library's performance and use to potentially improve performance. I have used Criterion and Iai to make benchmarks before, and I'd be willing to make a PR if you think it's a good idea to add this.