The edit-distance tag has no wiki summary.
10
votes
2answers
239 views
Edit distance with move operations
Motivation: A coauthor edits a manuscript and I would like to see a clear summary of the edits. All "diff"-like tools tend to be useless if you are both moving text around (e.g., re-organising the ...
11
votes
4answers
410 views
Shortest number of editing move between two words
I am looking for a data structure and an algorithm to compute the minimum number of changes required to transform one word into another, given the two words as inputs, where the only allowed changes ...
7
votes
1answer
281 views
Efficiently finding the minimum number of transpositions needed to sort a list
I'd like an efficient method for calculating the minimum number of transpositions needed to sort a list. I don't need to know what the transpositions actually are.
For example, the list [1, 1, 2, 0] ...
2
votes
1answer
167 views
Edit distance algorithms that depend on alphabet
The best known algorithm for computing the exact edit distance between two strings is I believe an algorithm by Masek and Paterson that runs in time $O(n^2/\log^2 n)$, for binary alphabets.
Is there ...
5
votes
2answers
213 views
Space complexity to compute the optimal string alignment for the Levenshtein edit distance
If we are given two strings of size $n_1$ and $n_2$, the standard Levenshtein edit distance computation is by a dynamic algorithm with time complexity $O(n_1 n_2)$ and space complexity $O(n_1 n_2)$. ...
4
votes
1answer
358 views
Proof of Levenshtein distance
In the article Levenshtein distance Wikipedia says about the proof of invariant that:
This proof fails to validate that the number placed in d[i,j] is in
fact minimal; this is more difficult to ...
6
votes
2answers
1k views
efficient diff algorithm for trees and Levenshtein distance
I've recently read this summary of the issues involved with doing diff between trees and it got me interested in learning what is the state of the art for this problem.
Also, suppose that between ...
11
votes
3answers
410 views
Edit distance between two partitions
I have two partitions of $[1 \ldots n]$ and am looking for the edit distance between them.
By this, I want to find the minimal number of single transitions of a node into a different group that are ...
1
vote
0answers
150 views
Edit-Distance of weighted automata
I'm trying to understand "Edit Distance of Weighted Automata" by Mehryar Mohri: [83], [93] and [99] at http://www.cs.nyu.edu/~mohri/pub/ (they are virtually identical so which of them doesn't matter).
...
2
votes
1answer
271 views
Using compression to improve edit distance computation
I am doing a seminar on a paper titled "Unified Compression-Based Acceleration
of Edit-Distance Computation" that uses straight-line programs to improve edit distance computation. It is a common ...
8
votes
4answers
607 views
Intermediate/Coding representation for Levenshtein Distance
The phrases:
The quick brown fox jumps over the lazy dog [A]
and
The uick brown fox jumps oower the lazy dog [B]
can be compared using Levenshtein Distance algorithm to determine ...
