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.

15 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
54 views

Number of strings at given edit distance

I would like to know the number of strings at edit distance $n$ of a string $s$. I guess this is textbook knowledge... but I cannot find the textbook in question. More formally, I have an alphabet $\...
3
votes
0answers
228 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 ...
2
votes
0answers
23 views

Computing similarity of two graphs with partially overlapping sets of nodes

Consider two graphs $G_1 = (E_1, V_1) $ and $G_2 = (E_2, V_2)$ with their associated sets of edges $E$ and nodes $V$. I'm familiar with concepts such as edit distance for computing the similarity/...
2
votes
0answers
46 views

Edit distance between all word pairs

Let there be a dictionary of M words with average length N. We want to compute an M×M matrix of edit distances between all word pairs. Since there are M² word pairs, and the pairwise edit distance ...
2
votes
0answers
200 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, ...
2
votes
0answers
485 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 ...
2
votes
0answers
566 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 ...
1
vote
0answers
30 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$?
1
vote
0answers
33 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 ...
1
vote
0answers
52 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?
1
vote
0answers
228 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 ...
1
vote
1answer
93 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 ...
0
votes
0answers
75 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. ...
0
votes
0answers
50 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, ...
0
votes
0answers
198 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 ...