# 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 ...

### 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 ...

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

Edit distance is definitely not the way to proceed. The standard approach toward near-identical document deduplication is to compute hashes of shingles. Here's one way to do it: Compute a set of k-...
Accepted

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

There's a "trick" you can use that might potentially speed up your algorithm a little: shingling. No guarantees that it'll necessarily help in your particular case, though. Lemma. If the edit ...

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

The fastest known exact algorithm is due to Masek and Paterson, and runs in time $O(n^2/\log n)$ for two strings of length $n$. Bačkurs and Indyk show that an $O(n^{2-\epsilon})$ algorithm would ...
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

### 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 ...
Accepted

### 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 ...
Accepted

### Edit distance for huge strings with bounds

You can use the usual dynamic programming algorithm. Instead of computing the edit distance between all prefixes of the input strings, compute only the edit distance between prefixes whose length is ...
Accepted

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

There are many measures of similarity between sequences (or arrays or even strings), which one to use depends on the specific goals for the similarity. It may be the case that some trial and error is ...

1 vote

### What is the difference between these two Edit Distance Algorithm

I'm going to assume by "doesn't work" you mean "gives the wrong answer". In dynamic programming, every cell in the table is supposed to represent a solution to a subproblem. In the ...
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
Accepted

### Extending ordered tree edit distance to DAGs

So after some thinking and digging around, I know believe (no rigorous proof) that edit distance between ordered DAGs is NP hard (in fact even Max-SNP hard) and thus no efficient algorithm is likely. ...
1 vote

The algorithm is based on dynamic programming. It computes a table $d[i,j]$ which stores the edit distance between $a_1\ldots a_i$ and $b_1\ldots b_j$. Although you only really need $i$ to range from $... 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 ... 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 ... 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 ...

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