# Tag Info

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

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

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

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

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

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

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

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