Skip to main content
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 ...
JounceCracklePop's user avatar
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 ...
Pseudonym's user avatar
  • 22.2k
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 ...
gnasher729's user avatar
  • 30.5k
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 ...
Christian Komusiewicz's user avatar
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.'s user avatar
  • 161k
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.'s user avatar
  • 161k
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.'s user avatar
  • 161k
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}$, $\...
Yuval Filmus's user avatar
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'...
Martin Thoma's user avatar
  • 2,360
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/...
Sven Büchel's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Discrete lizard's user avatar
  • 8,303
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.'s user avatar
  • 161k
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 ...
j_random_hacker's user avatar
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$ ...
Raphael's user avatar
  • 72.6k
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 ...
GACy20's user avatar
  • 121
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. ...
Kaspar Riesen's user avatar
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 ...
Trixie the Cat's user avatar
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 ...
Yuval Filmus's user avatar
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+...
Nathaniel's user avatar
  • 15.8k
1 vote

Algorithm to Check for Upper Bound of Levenshtein Distance

You may be interested in this implementation: https://github.com/fujimotos/polyleven
Pieter Hartel's user avatar
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 ...
Сергей Макеев's user avatar
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. ...
Martin Modrák's user avatar
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 $...
Yuval Filmus's user avatar
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.'s user avatar
  • 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 ...
AspiringMat's user avatar
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.'s user avatar
  • 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 ...
Jonas Kölker's user avatar
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 ...
Martin Kochanski's user avatar
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 ...
j_random_hacker's user avatar

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