[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [PATCH] add 'string-distance' to calculate Levenshtein distance

From: Paul Eggert
Subject: Re: [PATCH] add 'string-distance' to calculate Levenshtein distance
Date: Sat, 14 Apr 2018 10:36:49 -0700
User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.7.0

Nathan Moreau wrote:
What is the difference with the code present in lib/diffseq.h?

lib/diffseq.h uses the Myers-Ukkonen algorithm that scales better for the common case where strings are closely related. If the two strings are length N and their Levenshtein distance is D (where D is much less than N), then lib/diffseq.h is O(N*D) whereas the proposed algorithm is O(N**2).

So yes, it'd be better if the code used lib/diffseq.h rather than rolled its own algorithm.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]