25
votes
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 ...
- 451
19
votes
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 ...
- 21.6k
8
votes
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 ...
- 28.4k
6
votes
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-...
- 448
6
votes
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 ...
D.W.♦
- 156k
6
votes
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 ...
- 275k
5
votes
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 ...
4
votes
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 ...
D.W.♦
- 156k
4
votes
Accepted
Variation to edit distance depending on position still a metric?
Here is why the usual edit distance is a metric:
$d(w,w) = 0$ since no operations need to be performed to get from $w$ to $w$.
$d(x,y) = d(y,x)$ since given a sequence of operations for transforming $...
- 275k
4
votes
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 ...
D.W.♦
- 156k
3
votes
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,459
3
votes
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,350
3
votes
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
3
votes
Accepted
Efficient algorithm for edit distance for short sequences
One approach is to build a Levenshtein automaton for the fixed string (see, e.g., here). Given a string $x$ and a distance $D$, you can build a DFA that recognizes all strings that are at distance $\...
D.W.♦
- 156k
3
votes
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 ...
D.W.♦
- 156k
3
votes
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 ...
- 275k
3
votes
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 ...
- 7,768
3
votes
Is there a way to determine the LCS of three based on the LCS-s of all three pairs?
If $|\Sigma| \geq 3$, then for any non-negative integers $x \leq x_{AB}, x_{AC}, x_{BC}$ we can find strings $A,B,C$ such that $\operatorname{lcs}(A,B,C) = x$, $\operatorname{lcs}(A,B) = x_{AB}$, $\...
- 275k
2
votes
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.
...
2
votes
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$ ...
- 72k
2
votes
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
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 ...
- 275k
1
vote
Compute the edit distance between two words in which substitution is not allowed
You can use the same dynamic programming algorithm as the one for the Levenshtein distance with a bit of modifications.
Let $u=u_1…u_n$ and $v=v_1…v_m$ be two words. We want to build a $(n+1)\times(m+...
- 12.5k
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 ...
- 326
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 ...
- 205
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. ...
- 171
1
vote
Detailed explanation about Damerau Levenshtein Distance algorithm?
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 $...
- 275k
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 ...
D.W.♦
- 156k
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 ...
- 593
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 ...
D.W.♦
- 156k
Only top scored, non community-wiki answers of a minimum length are eligible