How can I calculate the Levenshtein distance between two words without allocating a full matrix—or preferably any additional arrays? The programming language is not important, but a lightweight C-like or JavaScript-style example would be easiest to follow. I'm wondering whether the calculation can be done with only a handful of variables, or whether a different word-similarity measure would be more practical for search ranking.
3 Answers
If your goal is search ranking rather than exact edit distance, you may not need Levenshtein distance at all. A simpler custom similarity score can compare matching characters, prefixes, or common subsequences with constant-sized state, but it won’t have the same behavior or guarantees as true Levenshtein distance. It’s worth testing the ranking quality on your actual search data.
If you refuse all auxiliary storage, the usual dynamic-programming approach has to give up its memoized results and recompute them, typically through recursion. That can use constant explicit storage, but the runtime becomes much worse, and the call stack still consumes memory. In practice, there’s a space-for-time tradeoff rather than a free constant-space version.
You don’t need to keep the entire dynamic-programming matrix. Each cell only depends on the cell above, the one to the left, and the diagonal cell, so retaining just the previous row and the current row is enough. That reduces the extra space to O(min(m,n)) while keeping the usual O(mn) time complexity.
The two-row version is already a substantial memory reduction, but it still requires arrays for the row values. The input strings themselves can remain unchanged.
So a handful of variables is possible only by accepting substantially more work, while the practical exact algorithm normally keeps at least one or two rows.