# Tag Info

6

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-shingles (say 30 char shingles) for each document Compute min-hashes for the documents Use locally-sensitive hashing to look-up similar documents when inserting ...

6

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 refute a (somewhat) widely believed conjecture, SETH, and Abboud et al. gave stronger results in this direction.

5

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 distance between two words $w,x$ is $\le 4$, and the two words both have length 20, then there exists some 4-gram that is common to both words (i.e., some $u$ of ...

5

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 both input sequences are $p$-sequences, that is, if every letter occurs only once in each input sequence: Laurent Bulteau, Guillaume Fertin, Irena Rusu: Sorting ...

5

There is in fact a whole bunch of related algorithms. In modern context I believe "time warp" would be called sequence alignment. Depending on whether you want to match complete strings or optimal substrings one gets Needleman-Wunsch and Smith-Waterman. In your latter algorithm the costs seem to vary, that is one can attribute different costs for deletion ...

4

Right, the code $VT_0(4)$ has Levenshtein distance (edit distance) of 4: to get from one codeword to another you must do 2 deletions and 2 insertions. Therefore, the code can correct one deletion. Indeed, if 101 was received, the only possible way to get this message assuming one deletion, is if 1001 was sent. Decoding can be done in several ways: The ...

4

Consider the two strings 01010101 and 10101010. They have distance 8 on the cube but their edit distance is 2.

4

There is trivially an edit distance between any two strings. The worst possible case is that you delete all of the characters of the original string, and then insert all the characters of the target string.

4

Given two strings $v,w \in \Sigma^*$ with $m = |v| \geq |w| = n$ (w.l.o.g.), align them like so: $\qquad\displaystyle\begin{array}{ccccccc} v_1 & v_2 & \dots & v_n & v_{n+1} & \dots & v_m \\ w_1 & w_2 & \dots & w_n & - & \dots & - \end{array}$ This alignment implies an edit distance of $\qquad\displaystyle 0 ... 4 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$x$to$y$, we can perform it in reverse to transform$y$to$x$at the same cost. This shows that$d(y,x) \leq d(x,y)$, and similarly$d(x,y) \leq d(y,x)$.$d(...

3

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 Levenshtein automaton. Now the intersection of a CFL and a regular language is another CFL. Also, given a CFL, you can efficiently determine whether it is non-...

3

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's writing style onto a given text. Yes, it is possible. Recurrent neural networks can do this. See The Unreasonable Effectiveness of Recurrent Neural ...

3

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/watch?v=nfoudtpBV68 ). This specifically covers spell checking in one of the first videos. In general, spell checking is a rather easy task, while (convincing) ...

3

Finding the minimal distance is called the "Sorting By Translocation" problem. Part of an abstract from a paper: "Given two signed multi-chromosomal genomes Pi and Gamma with the same gene set, the problem of sorting by translocations (SBT) is to find a shortest sequence of translocations transforming Pi to Gamma, where the length of the sequence is called ...

3

Comparing two strings Algorithms for computing the Levenshtein edit distance between a pair of strings can be found in the Wikipedia page on the edit distance. As that page explains, the running time for computing the edit distance between two strings of length $M$ is $O(M^2)$ time and $O(M)$ space. If you only care about whether the edit distance is $\le ... 3 Those two statements are correlated: "giving priority to the highest word position" is the same as "the node that has advanced farthest in the word is given priority". This appears to be why the algorithm selects state three. State zero does not result in an advancement in word position, whereas the transition to state three is further in the word position ... 3 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 have unique characters. This gives useful upper and lower bounds on the Levenshtein edit distance. Insert/delete edit distance, and longest common ... 3 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$\le D$from$x$. Thus, you can test whether a string is close to$x$in$O(n)$time, where$n$is the length of the string. I'm not sure what the space ... 3 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 required to find the 'best' one. Therefore, I'll give a brief overview of some well-known similarity measures: First, I consider distances most commonly ... 3 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 at most 100 apart. This reduces the number of entries to compute from$10^{14}$to roughly$2\cdot 10^9$, which is feasible. 3 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 difference of those languages (i.e.,$(L_1 \setminus L_2) \cup (L_2 \setminus L_1)$). One dissimilarity measure is$d(L_1,L_2) = 2^{-n}$where$n=\min\{|x| : ...

2

It depends on the exact definition of edit distance: Let, $s1=a$, $s2=bb$ The edit distance between $s1,s2$ is 3 if allowed only insertions and deletions; but it is 2 if allowed insertions, deletions and substitutions. With substitutions, it is clear that the number of letters you need to change is at most the length of the longer string.

2

You got the recursive definition wrong. It's $\qquad\displaystyle d_{ij} = \min \begin{cases} d_{i-1, j} + c_\mathrm{del}(b_{i}) \\ d_{i,j-1} + c_\mathrm{ins}(a_{j}) \\ d_{i-1,j-1} + [a_j \neq b_i] \cdot c_\mathrm{sub}(a_{j}, b_{i}) \end{cases}$ where the $c_{\mathrm{op}}$ are fixed costs for the respective operations, ...

2

The two strings s and t are compared starting from the high index, down to index 1. This is not visible since the initial call to string_compare is not provided. The i and j arguments for that initial call are the length of strings s and t. It should be noted that s and t could be globals, since they are the same in all calls. A call to the function ...

2

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$ with all nodes at Hamming distance one, respectively. Now the problem is just finding a shortest path from $x$ to $y$.

2

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. u3 is substituted with v2. Cost 1. This implies the substitution of edge (u2,u3) with (v3,v2) with cost 0. u4 is substituted with v1. Cost 0. This implies the ...

1

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 corresponding to $T$. If $S,T$ agree in a $p$ fraction of entries (i.e., $|S \cap T|=pn$), then the expected value of the Hamming distance between these two bit-...

1

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 exactly my case. I found that this is indeed possible in polynomial time. $O(n^2)$ to be exact. David A. Christie: Sorting permutations by block interchanges. ...

1

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 apply a straightforward modification to computing the Levenshtein edit distance, where you set the cost of an insertion to be 1 and the cost of a deletion or ...

1

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 right child of the root, and $U$ and $V$ be the subtrees rooted at these vertices, respectively. Let $w$ be the rightmost leaf in $U$. To transform $T$ into a ...

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