The edit distance (also: Levenshtein distance) between two strings measures the number of insertions and deletions it takes to convert one string to another.

learn more… | top users | synonyms

3
votes
3answers
86 views

Find member of CFL that is Levenshtein-closest to non-member string

Is there an (efficient?) algorithm which given a context-free language $L$ (given as a grammar) and a string $x$ with $x \not \in L$ computes a $y$ with $y \in L$ and $\forall y': y' \in L \implies d(...
1
vote
1answer
14 views

Length of an Edit Script and the Number of Deletions

I am reading the 1989 paper called "An O(NP) Sequence Comparison Algorithm" by Wu, Manber, Myers, and Miller. The algorithm sounds like a good fit for a project I'm doing at work. I have found some ...
3
votes
1answer
126 views

Find all pairs of strings in a set with Levenshtein distance < d

I have a set of $n = $ 100 million strings of length $l = 20$, and for each string in the set, I would like to find all the other strings in the set with Levenshtein distance $\le d = 4$ from that ...
1
vote
1answer
61 views

Can anybody suggest some algorithms for computing the edit distance other than ‎Wagner–Fischer algorithm? [closed]

I'm currently working with finding edit distance between two string of unequal length. But I'm sorry to say that I've got only one algorithm using Dynamic programming to find out edit distance. But I'...
2
votes
1answer
35 views

Variation to edit distance depending on position still a metric?

The edit distance between two strings $d(w_1, w_2)$ sums up the cost of edit operations that transform one string into the other. If done right, the edit distance is a metric. In particular, the ...
0
votes
0answers
35 views

How does Lucene build its inverted index so rapidly

I am writing a small Ruby on Rails engine that does simple full-text search. When someone imports text from a given model (eg. Articles, Posts, etc) an inverted index is built that looks like the ...
2
votes
0answers
90 views

Matching strings in one set to strings in another based on Levenshtein distance

Suppose I have two sets, A and B, which each have one or more strings. I'm looking for an algorithm that'll go through each ...
8
votes
0answers
79 views

What are some efficient ways to find the differences between two large corpuses of text that have similar, but differently ordered content?

I have two large files containing paragraphs of English text: The first text is about 200 pages long and has about 10 paragraphs per page (each paragraph is 5 sentences long). The second text ...
5
votes
1answer
78 views

How to speed up process of finding duplicates/similar items in a large amount of strings?

Our software receives documents (in the order of tens of thousands) from various providers, each document flows through a number of steps, one of those steps finds duplicates and similar documents (...
-2
votes
1answer
141 views

Edit distance between two strings

If X denotes the length of string s1 and Y denotes the length of the string s2, then the edit distance between s1 and s2 is never more than Min(X,Y) or ...
1
vote
0answers
22 views

How to find close match of levenshtein distance [duplicate]

Let's say we have some function, float distance(String a, String b) { /*...*/ } to find the Levenshtein distance between two strings, and we have a large array ...
8
votes
0answers
97 views

Edit distance of list with unique elements

Levenshtein-Distance edit distance between lists is a well studied problem. But I can't find much on possible improvements if it is known that no element does occurs more than once in each list. ...
3
votes
1answer
36 views

How is the Varshamov-Tenegolts code decoded?

For $0 \leq a \leq n$ the VT code $VT_a(n)$ consists of all tuples $(x_1,x_2,..,x_n) \in \{ 0,1\}^n$ such that $ \sum_{i=1}^{n} ix_i = a (mod (n+1))$ For example $VT_0(4) = \{ 0000,1001,0110,1111 \}$ ...
2
votes
1answer
88 views

Why can't edit distance be solved as L1 distance?

Given two strings $x$ and $y$ over the alphabet $\Sigma$ one defines the edit-distance $\text{ed}(x,y)$ as the minimum number of substitutions, insertions and deletions of characters required to ...
1
vote
1answer
57 views

Sequence alignment with one to many characters

I'm trying to align a sequence of characters together, I found that sequence alignment algorithms which use dynamic programming like Needleman-Wunsch or Smith–Waterman only align one character with ...
1
vote
1answer
108 views

Skienna's recursive algorithm for edit distance

I'm having some trouble understanding part of Skienna's algorithm for edit distance presented in his Algorithm Design Manual. I'm posting the recursive version, prior to when he applies dynamic ...
5
votes
1answer
71 views

Understanding the heuristic used for approximate string searching through an FSA

The paper I'm looking at: Fast approximate string matching with finite automata (2009) Explanation of the algorithm (from my understanding anyway): A word is inputted into the automaton and from ...
4
votes
1answer
290 views

Why is the running time of edit distance with memoization $O(mn)$?

I understand without memoization it is going to be $O(3^{\max\,\{m,n\}})$ because every call results in extra three calls: thus we end up having a call tree with three children for each node, with ...
1
vote
2answers
2k views

Edit distance (Levenshtein-Distance) algorithm explanation

I want to calculate the edit distance (aka Levenshtein-Distance) between two words: «solo» and «oslo». According to this site we'll get the result matrix: What I don't understand is: In case of ...
2
votes
2answers
354 views

How fast can we identifiy almost-duplicates in a list of strings?

I'm having trouble figuring out the upper bound running time for this scenario: Input: $N$ number of strings $M$ upper bound of string length $T$ threshold for edit distance (2 strings with a ...
1
vote
3answers
299 views

Is there a basic proof that there exists some edit distance between two strings?

Title says it all pretty much. I do realize that often edit distance is defined as the minimum number of operations needed to transform one string to another, but I want something to point to that's ...
2
votes
0answers
299 views

Distance preserving projection for Euclidean distance

Suppose I have two vectors $V_1, V_2 \in R^l$. Can they be converted into bit vectors $B_1,B_2 \in \{0,1\}^l $ such that if $V_1, V_2$ is close in Euclidean distance, $B_1,B_2$ is close in hamming ...
6
votes
1answer
219 views

Semi-local Levenshtein distance

If you have a long string of length $n$ and a shorter string of length $m$, what is a suitable recurrence to let you compute all $n-m+1$ Levevenshtein distances between the shorter string and all ...
4
votes
1answer
769 views

Levenstein distance and dynamic time warp

I am not sure how to draw parallel between the Wagner–Fischer algorithm and dtw algo. In both case we want to find the distance of each index combination (i,j). In Wagner–Fischer, we initiate the ...
6
votes
1answer
1k views

Alternative to Hamming distance for permutations

I have two strings, where one is a permutation of the other. I was wondering if there is an alternative to Hamming distance where instead of finding the minimum number of substitutions required, it ...