# 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
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 ...
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 ...
23 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/...
870 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 ...
47 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 ...
54 views

359 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 ...
187 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$ ...
229 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 ...
367 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 ...
114 views

### Advice needed. NLP and ML. Where to start? [closed]

Hi fellow computer scientists, I just began my journey to the world of ML and NLP so please bear with me. I'm hoping to find some guidance here. I would be very grateful if anyone could point me in ...
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 ...