craig> computer> music> analysis> algorithms>
edit distance
   Levenshtein Distance
Levenshtein distance (LD) is a measure of the similarity between two strings, which we will refer to as the source string (s) and the target string (t). The distance is the number of deletions, insertions, or substitutions required to transform s into t.
   Dynamic Programming Algorithm (DPA) for Edit-Distance
The words `computer' and `commuter' are very similar, and a change of just one letter, p->m will change the first word into the second. The word `sport' can be changed into `sort' by the deletion of the `p', or equivalently, `sort' can be changed into `sport' by the insertion of `p'.
   A versatile divide and conquer technique for optimal string alignment
Common string alignment algorithms such as the dynamic programming algorithm (DPA) and the time efficient Ukkonen algorithm use quadratic space to determine an alignment between two strings. In this paper we present a technique that can be applied to these algorithms to obtain an alignment using only linear space, while having little or no effect on the time complexity.
   Levenshtein 0.8
Levenshtein is a Python C extension and C libray to compute Levenshtein string distance, string similarity, normal and generalized string set medians, and other related quantities.

toolbar help Random Link   Map   Flat Listing   Brief Listing   Login