# 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 ...
• 22k

### 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 ...
• 29.4k
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 ...
• 158k

### 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 ...
• 276k
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 ...
• 158k
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 ...
• 158k

### Advice needed. NLP and ML. Where to start?

Spell checking, grammar checking, proofreading with ML Norvig: How to Write a Spelling Corrector "Artistic Style Transfer" for articles (if it is even possible), i.e. "transfer" Shakespeare'...
• 2,360
Accepted

### Advice needed. NLP and ML. Where to start?

As far as I can see, your reading list lacks specific NLP introductions. A really good starting point is Dan Jurafsky and Chris Manning's Coursera course (for example here https://www.youtube.com/...
• 226
Accepted

• 276k

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

### 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.3k
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 ...
• 276k
1 vote

• 276k
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 ...
• 158k
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 ...
• 603
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 ...
• 158k
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,469

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