Tag Info

8

The answer is yes. However I would not do that with an Earley parser because there are simpler ones with the same capabilities. Basically, Earley parser belongs to a family of general context-free parsers, that produces all possible parses for a given string, when the grammar is ambiguous. There are two ways (at least) of understanding these parsers: as ...

6

I don't think that the algorithm is flawed. If two strings are matched, we compare first its last two characters (and then recurse). If they are the same, we can match them to get an optimal alignment. For example, consider the strings test and testat. If you don't match the two last ts, than one of the ts remains unmatched, since otherwise your matching ...

6

There are a lot of different approaches that you could take. While the commenters are right, coming up with a distance metric is important, based on my own experience, finding good representations of your words/phrases is going to be significantly more important. Most of the "semantic" clustering algorithms that immediately come to mind are document level, ...

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

For modern cryptographic hash functions, no, there is no efficiently computable closeness predicate, assuming the distribution on $x$ has sufficient entropy. The intuition is that these hash functions are designed to "have no structure", so they don't admit anything like this. In technical terms, modern cryptographic hash functions behave "like a random ...

5

Some better statistics to think of are word length and $n$-gram analysis. For word length, you can collect statistics of the distribution of word length of city names, and compare it to the length of what you get. $n$-gram analysis looks at the distribution of sequences of $n$ letters in your sample text (say $n=2$). Both approaches can be combined. Given ...

5

Suffix arrays can be used for this problem. They contain the starting positions of each suffix of the string sorted in lexicographic order. Even though they can be constructed naively in $O(n\log n)$ complexity, there are methods to construct them in $\Theta(n)$ complexity. See for example this and this. Let us call this suffix array SA. Once the suffix ...

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

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

4

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

4

Below is an expected $\mathcal{O}(n + m )$ algorithm (which can be extended to other $k$, making it $\mathcal{O}(nk +m )$). (I haven't done the calculations to prove it is so, though). The idea is similar to the Rabin-Karp rolling hash algorithm for exact substring matches. The idea is to separate each string of length $m$ into $2k$ blocks of $m/2k$ size ...

4

The problem is known as "median string problem" and it is NP-complete; some results can be found searching with Google; in particular "2-Approximation Algorithms for Median and Centre String Problems". If $x$ must be one of the points in $S$ then the problem becomes solvable in polynomial time.

4

What you are interested in are semi-global and/or local alignments. The usual way to compute those is to adapt the dynamic programing algorithm for the Levenshtein distance: Initialise the first row/column with $0$ (instead of $i$/$j$) if free deletions/insertions are allowed at the beginning. Select the minimum value from the last row/column as result if ...

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 You may want to use a metric tree for fast research, if brute force is not possible (always try brut force). Finding your neighbours will be possible in$\mathcal O(\log (n))$, but the constant in$\mathcal O$may be big. You seem to have millions of strings, so it may be a good trade-off. Do not store the strings in the metric tree. Just store an index, ... 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(...

4

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

4

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 \{ t_M(x), t_M(y) \}$. Now we construct a machine $M'$ like this: M'(z) { if x == z or xy is a prefix of z wait for T steps return M(z) } We observe that $... 3 There are apparently several different variants of the Monge–Elkan metric. You can check out this paper which describes several different metrics (not only Monge–Elkan). Many other online references also exist. 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

When the code is linear, there is no need to go over all pairs of codewords, due to linearity. Indeed, since $d(x,y) = d(x\oplus y, 0)$ and for any two codewords $x,y \in C$, linearity implies that $x\oplus y \in C$, we see that the minimal distance is the minimal weight of a non-zero codeword. There are other ways characterization of the minimal distance, ...

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

I do not know about publicly available tools to do it, but I did fair amount of diff related algorithms and one tool to check similarities between codes. There are some basics to start with: 0) diff operates well on similar changed texts and falls into worst case when they are different. 1) Tools to check similarities on codes that I have seen, used and ...

3

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 search (string matching). This particular problem can be solved efficiently using convolution methods. The running time will be something like $O(n \lg n)$, times ...

3

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 common in computational genomics. See https://en.wikipedia.org/wiki/N-gram and https://en.wikipedia.org/wiki/K-mer for definitions.

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

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

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?

2

Yes. This is one plausible method, if you want to find pairs of vectors that are very close to each other. Two vectors that are close in Hamming distance are likely to end up in the same bin at some point. Suppose two vectors $v,w$ agree in fraction $p$ of their coordinates (where $0\le p \le 1$). Then, heuristically, if we look at a pair of coordinates, ...

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