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
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
4
votes
Accepted
How is n-gram different from k-mer?
Yes, they mean the same thing. A n-gram is a sequence of n consecutive things (words, letters, whatever). A k-mer is a sequence of k consecutive things (DNA basepairs). The phrase k-mer is more ...
D.W.♦
- 156k
3
votes
Accepted
Are two strings equal if all deciders for a language take the same amount of time for both?
Your "distance" $d(x,y)$ is never zero for distinct, non-trivial $x$ and $y$.
Let $M$ be a decider for $L$ and $x,y \in \Sigma^*$ with $\varepsilon \neq x \neq y$. Let furthermore $T = 1 + \max \{ ...
- 72k
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
Accepted
Is there a better-than-brute-force algorithm to generate a graph whose relation is string edit distance=1?
In the worst case any such algorithm will work $\Omega(n^2)$ because your graph can have $\Omega(n^2)$ edges.
By the way, are you interested in some particular string metric?
3
votes
Find the closest string to a fixed set of strings
This is a nearest-neighbor problem, and there are a variety of algorithms for the problem. The simplest is a k-d tree, and there are more sophisticated data structures as well. Another approach is ...
D.W.♦
- 156k
3
votes
Accepted
String searching, where we allow characters to almost-match
You're looking for all instances of $Q$ as a substring of $T$, except that two symbols are still considered to match even if they differ by one, so this is basically a generalization of substring ...
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
2
votes
String distance metric for possibly truncated words
I know this is an old question, but since Google brought me here, maybe it will bring some future beings here as well...
I would recommend using the Jaro-Winkler Distance which is defined in terms of ...
2
votes
Accepted
Sort by typical position?
As I understand your question, your problem statement is:
Given a set of ordered lists $\{L_1,L_2,\ldots,L_n\}$, learn the relation $r(a,b)$ for the partial order of each $L_1,L_2,\ldots,L_n$. Then ...
- 220
2
votes
Are two strings equal if all deciders for a language take the same amount of time for both?
Raphael's answer explains why $d$ as defined doesn't work. You stated that you want a metric, ideally. To explain why you will have trouble defining it with any kind of max/min relating running time: ...
- 923
1
vote
Upper bound on size of minimal binary coverage code
So, according to Theorem 4.3 of this monograph by Réné Struik, if we consider $q$-ary binary codes of length $n$, such that $n \to \infty$ with $r/n \to p \in [0,(q-1)/q]$, then the minimal code size ...
- 121
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
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,459
1
vote
Find member of CFL that is Levenshtein-closest to non-member string
The language $E = \{x\} \cdot \Sigma^*$ is regular, as is $I = \Sigma^* \{x_1\} \Sigma^* \{x_2\} \Sigma^* \cdots \Sigma^* \{x_n\} \Sigma^*$. For any language class of $L$ for which we can compute ...
- 709
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 ...
- 709
1
vote
Levenshtein distance cabable working with (large) vectors - not strings
Don't convert the numbers to decimal digits and then concatenate. Instead, just use the sequence of numbers directly. The Levenshtein distance can be used on any sequence, not just a sequence of ...
D.W.♦
- 156k
Only top scored, non community-wiki answers of a minimum length are eligible