Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [edit-distance]

The edit distance (also: Levenshtein distance) between two strings measures the number of insertions and deletions it takes to convert one string to another.

0
votes
1answer
33 views

Graph Edit Distance

Source: K. Riesen, Structural Pattern Recognition with Graph Edit Distance, Advances in Computer Vision and Pattern Recognition. Link: https://www.springer.com/cda/content/document/...
1
vote
0answers
24 views

Can we compute edit distance in strongly sub-quadratic time?

Can we compute the edit distance between two strings of length $n$ in strongly sub-quadratic time, i.e., in time $O(n^{2−\epsilon})$ for some $\epsilon>0$?
2
votes
1answer
29 views

Edit distance for huge strings with bounds

My question is simple but I don't know if the answer is. If you have two strings of length 10 million each, is there an algorithm that would allow you in practice to compute their edit distance (...
0
votes
0answers
70 views

N-gram similarity vs jacccard coefficient

According to this and this, Jaccard is one method of N-gram similarity (N=2). Is that so, or what is the difference between them? If I want to calculate the similarity between two sentences (with the ...
1
vote
0answers
31 views

Non-discrete edit distance for range maps

I'm looking for some kind of edit distance measure between what may be called 'non-discrete symbols sequences'. By a discrete symbol sequence I would mean something like a string, where each symbol ...
2
votes
1answer
34 views

Is there a heuristic or function to determine if two arrays of integers are alike or similar

What I am trying to do is determine "closeness" or how similar are arrays of integers (or byte arrays, doesn't matter). For example, let's say a = [0, 1, 2, 3, 4], <...
0
votes
0answers
60 views

How do iterative algorithms for Levenshtein edit distance actually find the number of substitutions, deletions etc.?

Please can someone explain how Levenshtein edit distance works? I've stepped through the algorithm in code and in excel, but I don't understand how this actually succeeds in finding an edit distance. ...
2
votes
0answers
115 views

Is Levenshtein algorithm efficient for text similarity?

I searched on the net the different measures of text similarity. And I found many algorithms concerning this issue and there are classified into many categories such: Token-Based Measure: Tf-idf, ...
4
votes
1answer
96 views

Extending ordered tree edit distance to DAGs

Computing edit distance (shortest sequence of edit operations) on ordered trees is a well studied problem with many known algorithms (e.g. Zhang & Shasha, RTED). There is also considerable ...
0
votes
1answer
549 views

Detailed explanation about Damerau Levenshtein Distance algorithm? [closed]

I'm a fresh year Computer Science student. Our teacher gave us damerau levenshtein distance algorithm pseudo code (which he got from Wikipedia apparently) and asked us to explain how the algorithm ...
0
votes
1answer
67 views

String edit distance between strings x, y, with restrictions on 'intermediary' strings

This is a problem I encountered in a recent interview test. I achieved a slow-ish solution to it, and I'm keen to figure out the most efficient. Problem Given a starting string $x$, a target string ...
1
vote
0answers
46 views

Regular Expression Metric space

With Levenshtein distance we can create a metric space over string. Is there are any distance metrics for regular expressions?
5
votes
2answers
492 views

Efficient algorithm for edit distance for short sequences

I have an application that needs to compute billions of levenshtein distance between pairs of strings. The strings are short (70 in length) DNA sequences, consisting only of 4 characters. Also it can ...
0
votes
0answers
38 views

Tracking Solution with Multiple Matrices in Dynamic Programming

We recently figured out a Dynamic Programming solution to compare two trees using concepts of edit distance in strings. It goes something like this- $A[i', i, j', j] = \min \begin{cases} B[i', i-1, ...
3
votes
1answer
279 views

hamming distance of bloom filters

In the introduction of Distance-Sensitive Bloom Filters the authors state: The relative Hamming distance between two Bloom filters (of the same size, and created with the same hash functions) can ...
1
vote
2answers
160 views

Complexity of Block edit distance with Swapping only

Suppose I have distinct letters in an alphabet $\sum = \{a_1,a_2,...,a_n\}$. I also have two permutations of these letters, let's call them $A,B$. How can I find the Edit distance between $A$ and $B$ ...
1
vote
0answers
187 views

Tips for improving implementation of Wagner-Fischer-algorithm

So I'm working on an implementation of a Wagner-Fischer-Algorithm for an online programming challenge site, but I can't seem to push the time down to where it needs to be. The assignment is to, for a ...
4
votes
0answers
194 views

Sequence Alignment with general gap penalties: proof of optimal substructure

I am very well-aware of how optimal substructure for pairwise global sequence alignment using the Needleman-Wunsch algorithm works. However, I have merely seen hand-waving explanations for the ...
0
votes
1answer
204 views

Insert-only Levenshtein distance

I am wondering if a constrained insert-only form of Levenshtein distance has been implemented before by someone? In my particular use case, all other operations should not count as they are not ...
4
votes
2answers
94 views

Advice needed. NLP and ML. Where to start? [closed]

Hi fellow computer scientists, I just began my journey to the world of ML and NLP so please bear with me. I'm hoping to find some guidance here. I would be very grateful if anyone could point me in ...
0
votes
1answer
80 views

What is the error when using Levenshtein distance on flattened binary trees?

I need to calculate the edit distance between many pairs of binary trees. Unfortunately this is computationally expensive. The trees are stored as a flattened list of indices into node and terminal ...
5
votes
3answers
125 views

Find member of CFL that is Levenshtein-closest to non-member string

Is there an (efficient?) algorithm which given a context-free language $L$ (given as a grammar) and a string $x$ with $x \not \in L$ computes a $y$ with $y \in L$ and $\forall y': y' \in L \implies d(...
1
vote
1answer
64 views

Length of an Edit Script and the Number of Deletions

I am reading the 1989 paper called "An O(NP) Sequence Comparison Algorithm" by Wu, Manber, Myers, and Miller. The algorithm sounds like a good fit for a project I'm doing at work. I have found some ...
5
votes
1answer
2k views

Find all pairs of strings in a set with Levenshtein distance < d

I have a set of $n = $ 100 million strings of length $l = 20$, and for each string in the set, I would like to find all the other strings in the set with Levenshtein distance $\le d = 4$ from that ...
1
vote
1answer
82 views

Can anybody suggest some algorithms for computing the edit distance other than ‎Wagner–Fischer algorithm? [closed]

I'm currently working with finding edit distance between two string of unequal length. But I'm sorry to say that I've got only one algorithm using Dynamic programming to find out edit distance. But I'...
2
votes
1answer
236 views

Variation to edit distance depending on position still a metric?

The edit distance between two strings $d(w_1, w_2)$ sums up the cost of edit operations that transform one string into the other. If done right, the edit distance is a metric. In particular, the ...
0
votes
0answers
137 views

How does Lucene build its inverted index so rapidly

I am writing a small Ruby on Rails engine that does simple full-text search. When someone imports text from a given model (eg. Articles, Posts, etc) an inverted index is built that looks like the ...
2
votes
0answers
404 views

Matching strings in one set to strings in another based on Levenshtein distance

Suppose I have two sets, A and B, which each have one or more strings. I'm looking for an algorithm that'll go through each ...
8
votes
2answers
124 views

What are some efficient ways to find the differences between two large corpuses of text that have similar, but differently ordered content?

I have two large files containing paragraphs of English text: The first text is about 200 pages long and has about 10 paragraphs per page (each paragraph is 5 sentences long). The second text ...
5
votes
1answer
196 views

How to speed up process of finding duplicates/similar items in a large amount of strings?

Our software receives documents (in the order of tens of thousands) from various providers, each document flows through a number of steps, one of those steps finds duplicates and similar documents (...
-2
votes
1answer
718 views

Edit distance between two strings

If X denotes the length of string s1 and Y denotes the length of the string s2, then the edit distance between s1 and s2 is never more than Min(X,Y) or ...
1
vote
0answers
44 views

How to find close match of levenshtein distance [duplicate]

Let's say we have some function, float distance(String a, String b) { /*...*/ } to find the Levenshtein distance between two strings, and we have a large array ...
12
votes
1answer
512 views

Edit distance of list with unique elements

Levenshtein-Distance edit distance between lists is a well studied problem. But I can't find much on possible improvements if it is known that no element does occurs more than once in each list. ...
3
votes
1answer
82 views

How is the Varshamov-Tenegolts code decoded?

For $0 \leq a \leq n$ the VT code $VT_a(n)$ consists of all tuples $(x_1,x_2,..,x_n) \in \{ 0,1\}^n$ such that $ \sum_{i=1}^{n} ix_i = a (mod (n+1))$ For example $VT_0(4) = \{ 0000,1001,0110,1111 \}$ ...
2
votes
1answer
98 views

Why can't edit distance be solved as L1 distance?

Given two strings $x$ and $y$ over the alphabet $\Sigma$ one defines the edit-distance $\text{ed}(x,y)$ as the minimum number of substitutions, insertions and deletions of characters required to ...
1
vote
1answer
82 views

Sequence alignment with one to many characters

I'm trying to align a sequence of characters together, I found that sequence alignment algorithms which use dynamic programming like Needleman-Wunsch or Smith–Waterman only align one character with ...
1
vote
1answer
322 views

Skienna's recursive algorithm for edit distance

I'm having some trouble understanding part of Skienna's algorithm for edit distance presented in his Algorithm Design Manual. I'm posting the recursive version, prior to when he applies dynamic ...
5
votes
1answer
106 views

Understanding the heuristic used for approximate string searching through an FSA

The paper I'm looking at: Fast approximate string matching with finite automata (2009) Explanation of the algorithm (from my understanding anyway): A word is inputted into the automaton and from ...
6
votes
1answer
3k views

Why is the running time of edit distance with memoization $O(mn)$?

I understand without memoization it is going to be $O(3^{\max\,\{m,n\}})$ because every call results in extra three calls: thus we end up having a call tree with three children for each node, with ...
1
vote
2answers
3k views

Edit distance (Levenshtein-Distance) algorithm explanation

I want to calculate the edit distance (aka Levenshtein-Distance) between two words: «solo» and «oslo». According to this site we'll get the result matrix: What I don't understand is: In case of ...
5
votes
2answers
1k views

How fast can we identifiy almost-duplicates in a list of strings?

I'm having trouble figuring out the upper bound running time for this scenario: Input: $N$ number of strings $M$ upper bound of string length $T$ threshold for edit distance (2 strings with a ...
1
vote
3answers
777 views

Is there a basic proof that there exists some edit distance between two strings?

Title says it all pretty much. I do realize that often edit distance is defined as the minimum number of operations needed to transform one string to another, but I want something to point to that's ...
2
votes
0answers
541 views

Distance preserving projection for Euclidean distance

Suppose I have two vectors $V_1, V_2 \in R^l$. Can they be converted into bit vectors $B_1,B_2 \in \{0,1\}^l $ such that if $V_1, V_2$ is close in Euclidean distance, $B_1,B_2$ is close in hamming ...
6
votes
1answer
333 views

Semi-local Levenshtein distance

If you have a long string of length $n$ and a shorter string of length $m$, what is a suitable recurrence to let you compute all $n-m+1$ Levevenshtein distances between the shorter string and all ...
7
votes
1answer
2k views

Levenstein distance and dynamic time warp

I am not sure how to draw parallel between the Wagner–Fischer algorithm and dtw algo. In both case we want to find the distance of each index combination (i,j). In Wagner–Fischer, we initiate the ...
7
votes
1answer
2k views

Alternative to Hamming distance for permutations

I have two strings, where one is a permutation of the other. I was wondering if there is an alternative to Hamming distance where instead of finding the minimum number of substitutions required, it ...