# Questions tagged [edit-distance]

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

50 questions
Filter by
Sorted by
Tagged with
826 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. ...
2k 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 ...
135 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 ...
2k 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 ...
1k views

### Efficient algorithm for edit distance for short sequences

I have an application that needs to compute billions of levenshtein distance between pairs of strings. The strings are short (70 in length) DNA sequences, consisting only of 4 characters. Also it can ...
3k 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 ...
4k 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 ...
300 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 (...
2k 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 ...
122 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 ...
384 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 ...
65 views

117 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 \}$ ...
381 views

### hamming distance of bloom filters

In the introduction of Distance-Sensitive Bloom Filters the authors state: The relative Hamming distance between two Bloom filters (of the same size, and created with the same hash functions) can ...
230 views

### Sequence Alignment with general gap penalties: proof of optimal substructure

I am very well-aware of how optimal substructure for pairwise global sequence alignment using the Needleman-Wunsch algorithm works. However, I have merely seen hand-waving explanations for the ...
322 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 ...
100 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 ...
49 views

### Edit distance for huge strings with bounds

My question is simple but I don't know if the answer is. If you have two strings of length 10 million each, is there an algorithm that would allow you in practice to compute their edit distance (...
40 views

### Is there a heuristic or function to determine if two arrays of integers are alike or similar

What I am trying to do is determine "closeness" or how similar are arrays of integers (or byte arrays, doesn't matter). For example, let's say a = [0, 1, 2, 3, 4], <...
26 views

### Computing similarity of two graphs with partially overlapping sets of nodes

Consider two graphs $G_1 = (E_1, V_1)$ and $G_2 = (E_2, V_2)$ with their associated sets of edges $E$ and nodes $V$. I'm familiar with concepts such as edit distance for computing the similarity/...
51 views

### Edit distance between all word pairs

Let there be a dictionary of M words with average length N. We want to compute an M×M matrix of edit distances between all word pairs. Since there are M² word pairs, and the pairwise edit distance ...
193 views

### Interleave two arrays such that collisions are minimised (dynamic programming) [closed]

This is a fascinating bioinformatics dynamic programming that I am solving. I am not looking for an answer to the problem, but rather any algorithms, research papers, or other pointers that could be ...
215 views

### Is Levenshtein algorithm efficient for text similarity?

I searched on the net the different measures of text similarity. And I found many algorithms concerning this issue and there are classified into many categories such: Token-Based Measure: Tf-idf, ...
496 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 ...
570 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 ...
1k 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 ...
197 views

### Complexity of Block edit distance with Swapping only

Suppose I have distinct letters in an alphabet $\sum = \{a_1,a_2,...,a_n\}$. I also have two permutations of these letters, let's call them $A,B$. How can I find the Edit distance between $A$ and $B$ ...
124 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'...
399 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 ...
197 views

### Edit Distance Algorithm (variant of longest common sub-sequence)

I'm working on a school assignment which is defined as a variant of the longest common subsequence problem and which is presented in the context of dynamic programming. The problem is defined as ...
4k 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 ...
34 views

### Can we compute edit distance in strongly sub-quadratic time?

Can we compute the edit distance between two strings of length $n$ in strongly sub-quadratic time, i.e., in time $O(n^{2−\epsilon})$ for some $\epsilon>0$?
33 views

### Non-discrete edit distance for range maps

I'm looking for some kind of edit distance measure between what may be called 'non-discrete symbols sequences'. By a discrete symbol sequence I would mean something like a string, where each symbol ...
54 views

### Regular Expression Metric space

With Levenshtein distance we can create a metric space over string. Is there are any distance metrics for regular expressions?
238 views

### Tips for improving implementation of Wagner-Fischer-algorithm

So I'm working on an implementation of a Wagner-Fischer-Algorithm for an online programming challenge site, but I can't seem to push the time down to where it needs to be. The assignment is to, for a ...
88 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 ...
66 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 ...
103 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 ...
48 views

### Graph Edit Distance

Source: K. Riesen, Structural Pattern Recognition with Graph Edit Distance, Advances in Computer Vision and Pattern Recognition. Link: https://www.springer.com/cda/content/document/...
92 views

### String edit distance between strings x, y, with restrictions on 'intermediary' strings

This is a problem I encountered in a recent interview test. I achieved a slow-ish solution to it, and I'm keen to figure out the most efficient. Problem Given a starting string $x$, a target string ...
1k views

### Detailed explanation about Damerau Levenshtein Distance algorithm? [closed]

I'm a fresh year Computer Science student. Our teacher gave us damerau levenshtein distance algorithm pseudo code (which he got from Wikipedia apparently) and asked us to explain how the algorithm ...
397 views

### Insert-only Levenshtein distance

I am wondering if a constrained insert-only form of Levenshtein distance has been implemented before by someone? In my particular use case, all other operations should not count as they are not ...
85 views

### What is the error when using Levenshtein distance on flattened binary trees?

I need to calculate the edit distance between many pairs of binary trees. Unfortunately this is computationally expensive. The trees are stored as a flattened list of indices into node and terminal ...
76 views

### How do iterative algorithms for Levenshtein edit distance actually find the number of substitutions, deletions etc.?

Please can someone explain how Levenshtein edit distance works? I've stepped through the algorithm in code and in excel, but I don't understand how this actually succeeds in finding an edit distance. ...
50 views

### Tracking Solution with Multiple Matrices in Dynamic Programming

We recently figured out a Dynamic Programming solution to compare two trees using concepts of edit distance in strings. It goes something like this- \$A[i', i, j', j] = \min \begin{cases} B[i', i-1, ...