Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

levenshtein distance space complexity #80

Open
adamgrzelak opened this issue Apr 16, 2023 · 0 comments
Open

levenshtein distance space complexity #80

adamgrzelak opened this issue Apr 16, 2023 · 0 comments

Comments

@adamgrzelak
Copy link

Hello,

First of all I would like to say thank you for developing and sharing this tool with the community. I recently used it for a project and I think it works great.

I have been going through the code out of curiosity and I would like to propose an improvement (in my opinion).

Calculation of Levenshtein distance can be implemented in a way that reduces space complexity, since only the previous row of the distance matrix actually has to be stored in memory. Based on simple tests, I estimate that this implementation reduces the time required this particular task by more than half.

Source with example:
https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python

Please let me know if that makes sense to you, and if yes, I will open a PR.

Kind regards,
Adam Grzelak

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant