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

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

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

Algorithm description The input string are broken into tokens. The best matching token are compared to get the monge-elkan score. Ex: Input string 1: "paul johnson" Input string 2 : "johson paule" Score : 0.94 The algorithm uses similarity function (Example : Jaro-Winkler or Levenshtein score) as inner function. The inner function is used to compute ...

5

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.

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

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

4

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

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

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

There are apparently several different variants of the Monge–Elkan metric. You can check out Cohen, Ravikumar and Fienberg, A comparison of string metrics for matching names and records, which describes several different metrics (not only Monge–Elkan). Many other online references also exist.

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

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

What it looks like you are after is the Block Swap edit distance. Here is a paper outlining a polynomial time solution to this problem, An Edit Distance Algorithm with Block Swap . I cant recall the exact time complexity they give in the paper, however it is outlined in there.

2

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 the Jaro Distance $d_j$, the common prefix length of the two strings $l$ (bounded by some maximum value, let's say $b$), and a prefix scaling factor $p$. It ...

2

It is quite hard to propose an "optimal" string distance metric, especially when the specification is only specified by an example. There are many possibilities for you to try: Levenshtein or Edit distance (wiki): allows insertions, deletions and replacements. Hamming distance (wiki): allows only replacements. Episode distance: allows only insertions. ...

2

So you want to use the Jaccard index as your metric of similarity. Well, the Wikipedia page for the Jaccard index (and which I linked to in the comments above) already has some hints on methods for finding close matches, more efficiently than comparing all pairs. For instance, you can use locality-sensitive hashing. Hint for the future: you might want to ...

2

I am assuming that you mean finite-state automaton (FSA) when you say automaton. Actually, this can work for other automata, notably for Push-Down Automata (PDA) and is a nice way to do syntax-error recovery in programming languages compilers. But string matching is usually defined with regular expressions. The answer to your question is called Levenshtein ...

2

You can adopt the usual dynamic program to compute the Levenshtein distance between a word $w$ and a regular language $L$ computed by some given NFA without $\epsilon$ transitions. Suppose $w$ has length $n$. For each $0 \leq \ell \leq n$ and state $s$ of the NFA, we will compute $A(\ell,s)$ which is the minimum Levenshtein distance between the $\ell$th ...

2

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: for every string x in L, there is a machine that first reads in the input, checks if it is x, and if so immediately returns; otherwise it resorts to some "...

2

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 use this learned relation to sort a new list. So, in your example, the relation would be the lexicographical order. But your data set has some noise because ...

1

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 the shortest member of $L \cap R$ for regular $R$, we can answer the insert-at-end and insert-anywhere optimization problem (note that shorter implies smaller ...

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