# Tagged Questions

The tag has no usage guidance.

46 views

### Relation between edit distances over different alphabets

Assume we have two strings $S_1$ and $S_2$ of lengths $cn$ and $cm$ bits resepctively for some $c\in\Bbb N$. Assume that the Levenshtein distance (minimum number of single-character edits (i.e. ...
66 views

### Communication complexity of edit resilient synchronization

Supposing we have two strings $A$ and $B$ that are both edit distance $\tau$ from each other at two different sites is there a communication complexity model where synchronizing such strings have been ...
382 views

### Min Hamming distance of a given string from substrings of another string

Let $U$ be a small finite set. Consider the following problem: Input: two strings $u \in U^k$ and $v\in U^n$ with $k \leq n$. Output: a (contiguous) substring of $v$ of length $k$ with the minimum ...
90 views

### Long distance string problem

We are considering length n strings over the alphabet S. The goal is to compute a set of string, M, such that for any string, x, in S^n there exists a string, y, in M such that the hamming distance ...
646 views

### Edit distance in sublinear space

What is the best known complexity for computing the exact edit distance between two strings of the same length using working space which is sublinear in the size of the input? I assume the input is ...
207 views

### extension for Levenshtein distance

I am looking for an extension for Levenshtein distance (Edit distance) for multi dimensional strings (2D and 3D). I am not sure if there is a formal definition for multi dimensional or not, but here ...
485 views

### Spell Checker with BK tree and edit distance that accounts for transpositions

I want to try and write code for a BK tree using a certain edit distance that accounts for transpositions for a spell corrector. I've looked into Damerau-Levenshtein distance, but the triangle ...
486 views

### Edit distance with move operations

Motivation: A coauthor edits a manuscript and I would like to see a clear summary of the edits. All "diff"-like tools tend to be useless if you are both moving text around (e.g., re-organising the ...
525 views

### Shortest number of editing move between two words

I am looking for a data structure and an algorithm to compute the minimum number of changes required to transform one word into another, given the two words as inputs, where the only allowed changes ...
626 views

### Efficiently finding the minimum number of transpositions needed to sort a list

I'd like an efficient method for calculating the minimum number of transpositions needed to sort a list. I don't need to know what the transpositions actually are. For example, the list [1, 1, 2, 0] ...
301 views

### Edit distance algorithms that depend on alphabet

The best known algorithm for computing the exact edit distance between two strings is I believe an algorithm by Masek and Paterson that runs in time $O(n^2/\log^2 n)$, for binary alphabets. Is there ...
686 views

### Space complexity to compute the optimal string alignment for the Levenshtein edit distance

If we are given two strings of size $n_1$ and $n_2$, the standard Levenshtein edit distance computation is by a dynamic algorithm with time complexity $O(n_1 n_2)$ and space complexity $O(n_1 n_2)$. (...
958 views

### Proof of Levenshtein distance

In the article Levenshtein distance Wikipedia says about the proof of invariant that: This proof fails to validate that the number placed in d[i,j] is in fact minimal; this is more difficult to ...
6k views

### efficient diff algorithm for trees and Levenshtein distance

I've recently read this summary of the issues involved with doing diff between trees and it got me interested in learning what is the state of the art for this problem. Also, suppose that between ...
534 views

### Edit distance between two partitions

I have two partitions of $[1 \ldots n]$ and am looking for the edit distance between them. By this, I want to find the minimal number of single transitions of a node into a different group that are ...
172 views

### Edit-Distance of weighted automata

I'm trying to understand "Edit Distance of Weighted Automata" by Mehryar Mohri: [83], [93] and [99] at http://www.cs.nyu.edu/~mohri/pub/ (they are virtually identical so which of them doesn't matter). ...