# Tag Info

### How does editing software (like Microsoft word or Gmail) pick the 2nd string to compare in Levenshtein distance?

Yes, the entire dictionary is compared against each word. This can be fast by using a trie and an algorithm similar to Levenshtein's. I have built my own spelling corrector that checks words against a ...

### How does editing software (like Microsoft word or Gmail) pick the 2nd string to compare in Levenshtein distance?

Companies with search engines (e.g. Microsoft or Google) don't always directly search for the string with the smallest Levenshtein distance. They have a huge database of search queries, from which ...
• 22.2k

### How does editing software (like Microsoft word or Gmail) pick the 2nd string to compare in Levenshtein distance?

I just tried and found that the spelling checker on my phone finds a perfectly fine replacement for “gekki wirkd”. Look at your keyboard, and it is obvious. A good spelling checker does much better ...
• 30.5k
Accepted

### Complexity of Block edit distance with Swapping only

When one operation is exactly "removing a block and inserting it between two other positions", the problem of computing the string distance is known as Transposition Distance. It is NP-hard even if ...
Accepted

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

Yes. This can be done, using Levenshtein automata. Let $S_k = \{y \in \{0,1\}^* : d(x,y) \le k)\}$. Then the set $S_k$ is regular, and one can construct a finite-state automaton for it, called a ...
• 161k
Accepted

### Usual distances on DFAs (Deterministic Finite Automata)?

There are many possible distance metrics, and without any criteria, we have no basis to choose. Here are two plausible ones. Let $L_1,L_2$ be the languages of the two DFAs. Let $L$ be the symmetric ...
• 161k

### Uniformly sample $x,y\in\{0,1\}^n$ with Levenstein distance $k$

There are two considerations: running time, and correctness. Running time: When $k < (n-1)/\lg(4n)$, heuristically I expect the running time of your algorithm to be fine and I'd guess you won't ...
• 161k

• 161k

### Edit distance of list with unique elements

TL;DR: A slightly more restrictive kind of edit distance, in which we can only insert and delete individual characters, can be computed in linearithmic time when both (or even just one) of the strings ...
• 5,479

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

I think your approach has merit, but you want to limit the amount of searches on $V$. Model $V$ as a graph and connect all nodes whose strings have Hamming distance one. Then you connect $x$ and $y$ ...
• 72.6k

### How does editing software (like Microsoft word or Gmail) pick the 2nd string to compare in Levenshtein distance?

There are many ways to organize data to optimize queries. Regarding text search the classical way is to build a Suffix Tree. This allows to perform searchs in a big text with the time proportional to ...
• 121
Accepted

### Graph Edit Distance

No, it is not an error. u1 is deleted. Cost 1. u2 is substituted with v3. Cost 0 (Equal labeling). This Operation together with the first Node deletion implies the deletion of edge (u1, u2). Cost 1. ...
1 vote
Accepted

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

the additional cost of adding a swap function should be: T(j-2,k-2) + Cs , if A[j-1]=B[k],and A[j]=B[k-1] I found the answer by studying the Damerau–Levenshtein distance modification of the ...
1 vote

### Edit distance proof when last chars of 2 strings are the same

Let's show that if $s$ and $t$ end with the same symbol, then there is always an optimal solution in which the final letters are left alone. Note that there could be other optimal solution in which ...
• 278k
1 vote

• 278k
1 vote
Accepted

### hamming distance of bloom filters

Let $S,T$ be two sets of size $n$. Suppose we hash each to a $m$-bit Bloom filter, using $k$ hash functions; let $x_S$ be the $m$-bit vector corresponding to $S$, and $x_T$ the $m$-bit vector ...
• 161k
1 vote

### Complexity of Block edit distance with Swapping only

Thanks to C Komus for providing the initial paper. After reading in the paper that he added, the authors cited another paper which can perform it if the words are permutations of each others, which is ...
• 613
1 vote

### Insert-only Levenshtein distance

Your problem appears to be: Given strings $S,T$, determines whether $S$ appears as a subsequence of $T$. There are several ways you could approach this. One way is to use dynamic programming and ...
• 161k
1 vote

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

If we limited ourselves to those $y$ with $|y| \le |x|$ (or any finite set) and a computable strict partial order, we can construct the (finite) DAG of the order on our $y$s and find the set of all ...
• 719
1 vote

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

Comparing 2000 paragraphs to 2000 paragraphs is only four million comparisons. The key to the problem is not to use a function that computes the Levenshtein distance but to use one that computes the ...
• 1,064
1 vote

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

This approximation is essentially arbitrarily bad. Suppose you have a complete binary tree $T$ containing $2^k - 1$ nodes, of which the bottom $2^{k-1}$ are leaves. Let $u$ and $v$ be the left and ...
• 5,479

Only top scored, non community-wiki answers of a minimum length are eligible