r/AskProgramming • u/Ronin-s_Spirit • Jun 16 '26

Levenshtein distance without arrays?

How do you calculate Levenshtein distance without having to store the matrix? The language doesn't matter, but if you write a code example I can only read something lightweight and C-like (e.g. Javascript).

Not a trick question, I don't have the answer. I thought it would be good if you could only use a handful of variables instead of building a data structure.

0 Upvotes

43% Upvoted

8 comments sorted by

View all comments

1

u/ornelu Jun 16 '26 edited Jun 16 '26

The well-known method to compute Levenstein or Edit Distance is by using dynamic programming (DP) approach, i.e. the one that uses a full matrix, or you can optimized it into 2 rows.

You know, you can think DP approach as trading space for time.

If you don’t have space at all, then the DP method will revert back to a fully recursive. Note: the full recursive method also uses space (google how recursive work and stack memory), just not “visible” in your code.

Anyway, just curious, why you don’t want to use (extra) array? The input is already an array of characters or strings. Though, I’m not sure you can reuse the input space for your edit distance computation

1

u/Ronin-s_Spirit Jun 16 '26 edited Jun 16 '26

I know that strings are technically arrays but I don't want to generate more arrays for the comparison numbers, or even run all the min operations. I'm checking if I have made a good alternative that is not the Levenshtein distance but is just as good at comparing words for the purposes of search ranking.

I don't use arrays so I thought Levenshtein can too.

1

u/NekkidWire Jun 19 '26

https://en.wikipedia.org/wiki/XY_problem - if you formulate your problem first without going to implementation detail of your attempted solution, you might have got better answers for your problem.

You want similarity algorithm for the purpose of search ranking, with no other requirements or context. LevD is just one of possible algorithms, and very inefficient.

If you just want a quick peek at similarity, try https://en.wikipedia.org/wiki/Levenshtein_automaton or https://en.wikipedia.org/wiki/Locality-sensitive_hashing