262 questions
0
votes
1
answer
131
views
Is it possible to fix a recursive Python function within a 12-character edit distance? [closed]
I have the following recursive Python function. The goal is to return the index of the first occurrence of it in the list. Is it possible to fix this code within a maximum of 12 edits?
def index_of(it,...
- 17
3
votes
1
answer
109
views
Computing Levenshtein distance on a "large" dataset
I'm currently in the process of trying to compute Levenshtein distance matrices for my fairly large dataset of approx 420 long DNA sequences (about 2kbp), so I cannot check them manually for mistakes ...
- 31
1
vote
2
answers
68
views
Levenshtein distance algorithm without delete operation
I modified Levenshtein distance algorithm form geeksforgeeks using full matrix. I deleted a delete operation (prevRow[j]) and it works now well only for specific order of input string.
cout << ...
- 13
1
vote
0
answers
47
views
Directed Graph Edit Distance Computation Issue Using AStar Algorithm in Graph-Matching-Toolkit
I am comparing pairs of identical directed graphs represented in GXL format using the Graph-Matching-Toolkit(https://github.com/dzambon/graph-matching-toolkit). Since the graphs are identical, I ...
- 11
1
vote
1
answer
95
views
Calculating the distance of a sequence with adjacent transpositions, and no insertion or deletion
How can I calculate the numeric distance of two sequences under the requirement that sequence elements may only be swapped with adjacent elements? Insertion, and deletion are not allowed. The distance ...
- 465
0
votes
1
answer
60
views
Given the length of a word, how many character-level errors should we permit?
Using edit distance metrics, e.g. the Levenshtein-Damerau edit distance, words can easily be flagged as misspellings of other words.
However, the edit distance that constitutes a misspelling will ...
- 115
2
votes
1
answer
1k
views
How does Oracle DB compute edit distance and similarity with non-ASCII characters?
I've recently been working with Oracle DB, and when evaluating their matching functions (in this case, EDIT_DISTANCE and EDIT_DISTANCE_SIMILARITY, which - I think - implement unnormalized and ...
- 964
3
votes
1
answer
816
views
Why is Rust port of function 2x slower than C++?
I have a function to compute String edit distance in C++:
#include <string>
#include <vector>
#include <algorithm>
size_t sed_diff(const std::string & a, const std::string & ...
- 329
3
votes
2
answers
1k
views
Why "Longest Common Subsequence" prohibits "substitution" using edit distance methodology
Edit distance is a famous class of problems including:
Different types of edit distance allow different sets of string
operations. For instance:
The Levenshtein distance allows deletion, insertion ...
- 860
0
votes
1
answer
144
views
Finding the subset of a dictionary that has the minimum edit distance to a given string
I'm looking for the most efficient way of solving an Levenshtein edit distance problem.
We are given as input:
A set of strings S of size n <= 8, with average length m <= 50
A target string t of ...
- 157
0
votes
0
answers
90
views
Find out edit distance between two strings
I am calculating edit distance between two dataframe. Both the dataframe consists of ~30L of rows, as the dataframe size is large it is taking lot of time. Is there any way to improve the performance?
...
- 111
2
votes
0
answers
70
views
Graph edit distance for connected components in a graph - considering the spatial distance
has anyone ever done or seen something like this?
I have two disconnected graphs of the same size with the same nodes but different edges. They may contain connected components. I want to compare one ...
0
votes
1
answer
145
views
group_by edit distance between rows over multiple columns
I have the following data frame.
Input:
class id q1 q2 q3 q4
Ali 12 1 2 3 3
Tom 16 1 2 4 2
Tom 18 1 2 3 4
Ali 24 2 2 4 3
Ali 35 2 2 4 3
Tom ...
- 1,148
3
votes
1
answer
238
views
solr fuzzy search with edit distance above 1
Enviornment- java version "11.0.12" 2021-07-20 LTS, solr-8.9.0
I have the following field declaration for my Solr index:
<field name="Field1" type="string" multiValued=...
- 124
0
votes
0
answers
249
views
Numpy implementation of Edit Distance Algorithm
I am new to numpy(and python) and working on making the edit distance Algorithm with numpy. This is my code so far. I have an error for the first line after the else: . The error says: "index 3 ...
- 67