# 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
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/...
46 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$ ...
228 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 ...
229 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 ...
365 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 ...
172 views