Talk:Levenshtein distance/Alignment: Difference between revisions
Content added Content deleted
(→Algo?) |
(→Algo?: Start with LCS) |
||
(One intermediate revision by one other user not shown) | |||
Line 1: | Line 1: | ||
==Algo?== |
==Algo?== |
||
Is there an algorithm you can point me at? --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 15:07, 3 May 2013 (UTC) |
Is there an algorithm you can point me at? --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 15:07, 3 May 2013 (UTC) |
||
:I don't know any reference, but anyway it's not really different from the Levenshtein distance algorithm. The only difference is that you don't only memoize the distance, |
:I don't know any reference, but anyway it's not really different from the Levenshtein distance algorithm. The only difference is that you don't only memoize the distance, you also memoize the alignments.--[[User:Grondilu|Grondilu]] ([[User talk:Grondilu|talk]]) 00:38, 4 May 2013 (UTC) |
||
::It's a trivial derivation from the [[Longest common subsequence|LCS]]. –[[User:Dkf|Donal Fellows]] ([[User talk:Dkf|talk]]) 00:22, 16 January 2014 (UTC) |
Latest revision as of 00:22, 16 January 2014
Algo?
Is there an algorithm you can point me at? --Paddy3118 (talk) 15:07, 3 May 2013 (UTC)
- I don't know any reference, but anyway it's not really different from the Levenshtein distance algorithm. The only difference is that you don't only memoize the distance, you also memoize the alignments.--Grondilu (talk) 00:38, 4 May 2013 (UTC)
- It's a trivial derivation from the LCS. –Donal Fellows (talk) 00:22, 16 January 2014 (UTC)