Questions tagged [edit-distance]

A class of problems concerned with finding or minimizing the sequence of change operations (such as insertion, deletion, substitution, or transposition) to convert one list or string into another

Filter by
Sorted by
Tagged with
3 votes
1 answer
222 views

Damerau-Levenshtein distance performance improvements

I am working on a Python C-extension to calculate Damerau-Levenshtein distance. I am not really familiar with C at all--I just know that it generally has better performance. However, I am not sure how ...
stressed's user avatar
  • 133
1 vote
0 answers
70 views

Spell checker using levenshtein minimum distance

I implemented a simple spell checker. Basically I have to user input an incorrect sentence or a word, then a number N, and then N correct words each on new line. The program has to output "...
Raluca123's user avatar
3 votes
2 answers
285 views

Find pairs of similar (by hamming distance) bit strings

I have a list of binary strings where each binary string max length is 15. I need to find list of integers which is count of similar (should differ by max 1 bit position) binary strings present in the ...
Harry's user avatar
  • 399
2 votes
0 answers
82 views

Simple diff utility in Java using OOP take 2

(See the previous iteration here.) After further revising my code, I have: com.github.coderodde.diff.Diff.java: ...
coderodde's user avatar
  • 28k
5 votes
2 answers
1k views

Find all pairs of words that differ by one letter

I have a list of words in English. My aim is to find all pairs of words that differ by exactly one letter (i.e. edit distance is 1). For instance: PAY-PLAY, WARM-ARM, WORD-WORK. The naive algorithm is ...
kodkod's user avatar
  • 441
2 votes
1 answer
127 views

Simple diff utility in Java using OOP

(Previous and initial iteration lives here.) (The next iteration is here.) Now I was able to spare some lines by putting diff related state in an object. Also, I relied on ...
coderodde's user avatar
  • 28k
6 votes
2 answers
981 views

Simple diff utility in Java

(See the next and second iteration here.) I have this toy implementation of the diff utility in Java: ...
coderodde's user avatar
  • 28k
-1 votes
2 answers
142 views

New String similarity algorithm (java)

Recently I have been developing a library for Java which provides utility functions for arrays, strings, etc.. While researching string similarity algorithms, I managed to write one of my own. I am ...
Temps's user avatar
  • 39
3 votes
0 answers
56 views

Get shortest grouped (distinct) string from Hashset of strings

Well, I just have a lot of strings that have common parts between them and not all of them. By this reason, I wanted to group them by their longest common part and take from that the minimum from each ...
z3nth10n's user avatar
  • 247
1 vote
0 answers
416 views

Java reimplementation of the Python difflib.SequenceMatcher class

I'm rewriting a Python script into an Android app. This script uses difflib.SequenceMatcher to compare sequence of strings. I haven't been able to find something ...
Pierre's user avatar
  • 245
2 votes
0 answers
38 views

Loop through the nearest switch and deletion neighbours of a Boolean assignment

My goal is to look for nearest neighbours in a Boolean-assigned mapping (a Python dictionary). For this purpose I'm looping through the candidates, starting from those with the closest distance. The ...
Felix Emanuel's user avatar
6 votes
2 answers
2k views

Hamming distance between two strings

I wrote this module to find the Hamming distance between two strings. (It's a problem from exercism.io's Haskell track.) As I saw it, the problem has two distinct ...
Josh Friedlander's user avatar
3 votes
0 answers
85 views

calculating upper bound on normalized weighted levenshtein distance

Current implementation I am using a normalized weighted Levenshtein distance for two utf32 strings with the following costs (insertion: 1, deletion: 1, replacement: 2). The normalization is performed ...
maxbachmann's user avatar
2 votes
1 answer
700 views

An implementation of Levenshtein Distance algorithm in modern C++

Below is an implementation of Levenshtein Distance algorithm. I am trying to use modern C++ features as much as I can, i.e. auto, no pointer / raw memory but I feel like it is a constant struggle. ...
Cortex's user avatar
  • 440
1 vote
1 answer
179 views

"Edit Distance" algorithm

I have a piece of code that calculates the edit distance between words and works, but it's apparently not fast enough. ClosestWords.java: ...
Schytheron's user avatar
1 vote
1 answer
851 views

Vectorize pairwise edit distance computation [closed]

How can I vectorize this function? It takes an array of array of tuples as input and computes the distance between elements using Levenshtein's method. I found some simpler examples but they weren't ...
OrangePi3's user avatar
1 vote
1 answer
76 views

Filter string with min distance in r

I have the following sample data: target <- "Stackoverflow" candidates <- c("Stackflow", "Stackflow", "Stckoverfow") I would like to filter the string from ...
BigDataScientist's user avatar
7 votes
2 answers
205 views

Document distance in Python

I wrote a script to calculate document distance. It seems working but I couldn't be sure. (I tried for the small strings and it seems working) Also I am not sure that its fast enough for large texts. ...
seVenVo1d's user avatar
  • 519
6 votes
1 answer
130 views

Search for strings in a list that have > 90% similarity

Explanation: I am working on String comparison in which I want to cross-compare the list of the same input string. For the same string, I am continuing the loop but if a single string will have ...
Muhammad Hamaad Latif's user avatar
5 votes
1 answer
4k views

Finding the closest string match for each string in two dataframe columns

I was wondering what's the fastest method to compare similarity between two lists of strings (e.g. two dataframes, documents etc.) using levenshtein distance or other procedures. I am currently using:...
Maeaex1's user avatar
  • 153
7 votes
3 answers
1k views

Cracking the Coding Interview — 1.5 One Away

I would like to know any suggestions about to improve my code solution and your rating of my approach to the problem, I based my code on the fact that if the strings have different length removing one ...
dariosicily's user avatar
  • 3,961
5 votes
2 answers
1k views

Find hamming distance between two Strings of equal length in Java

I have a private class that I want to be able to find the shortest Hamming Distance between two Strings of equal length in Java. The private class holds a char[] ...
LuminousNutria's user avatar
21 votes
3 answers
62k views

Calculate Levenshtein distance between two strings in Python

I need a function that checks how different are two different strings. I chose the Levenshtein distance as a quick approach, and implemented this function: ...
Kyra_W's user avatar
  • 313
1 vote
1 answer
410 views

Programming Challenge from Kattis: Distinctive Characters

I'm currently working on this problem from Kattis. In short, we're supposed to find the string that has the least similarity to any other string given. Every element of a string is either 0 or 1. ...
RoyM's user avatar
  • 183
6 votes
2 answers
6k views

Find a best fuzzy match for a string

I am trying to find a best match for a name within a list of names. I came up with the below code, which works, but I feel that the creation of the intermediate ...
barciewicz's user avatar
4 votes
1 answer
1k views

MySQL JSON diff procedure

I'm building a procedure which compares two JSON objects and return two JSON objects with differences between each (compared keys and values). But I have relatively superficial SQL knowledge, so I ...
Dmytro's user avatar
  • 143
4 votes
1 answer
7k views

Hamming Distance in Python

I was solving this Leetcode challenge about Hamming Distance. Would love feedback on my syntax and code style. Here's the challenge description: The Hamming distance between two integers is the ...
zthomas.nc's user avatar
2 votes
0 answers
102 views

Document distance in JavaScript

I am looking for the fastest way to find document distance. How can I improve this? Split each document into words. replaceAll() is faster than replace() ...
user7331530's user avatar
3 votes
0 answers
454 views

Finding differences in strings with Levenshtein distance and soundex

I am trying to find a way to optimize the code runtime. Improvements I have implemented include using dictionaries, removing redundancies and using str.translate. <...
BernardL's user avatar
  • 131
3 votes
2 answers
244 views

Testing Video Frames for Uniqueness

I'm working on a program that will (hopefully) eventually allow me to perform frame rate analysis like Digital Foundry does. The code below works (as far as I know), but before I iterate on it, I'd ...
Trevor's user avatar
  • 33
4 votes
1 answer
2k views

Code to implement the Jaro similarity for fuzzy matching strings

Problem This code is meant to solve the problem in this software engineering question. To summarize the issue: given a set of strings that are sort of similar, but not similar enough to use regex upon,...
auden's user avatar
  • 421
4 votes
2 answers
128 views

Function to check whether two strings are similar at given %

Since the previous question I posted here was not found as interesting as I expected, I decided to post a new one. I made a function solely for the purpose of having fun. That is, a function that ...
Edenia's user avatar
  • 1,568
7 votes
2 answers
892 views

Calculate Hamming distance between DNA sequences in Ruby

I am requesting a review for my solution to this problem from exercism.io. I'm posting it here since there is not always input on solution submitted through exercism. The problem is as stated: ...
user9503053's user avatar
8 votes
2 answers
10k views

String Similarity using fuzzywuzzy on big data

I have a file in which I was to check the string similarity within the names in a particular column. I use fuzzywuzzy token sort ratio algorithm as it is required for my use case. here is the code, is ...
Rishab Oberoi's user avatar
5 votes
1 answer
422 views

Trie based string indexing with edit distance / Levenshtein in Go

This is my first Go program that I've ever written. The code can also be found here. It allows you to create a search index and add words to it. The twist is that when searching for a word within the ...
Prinzhorn's user avatar
  • 153
3 votes
1 answer
170 views

Levenshtein Distance of transitively similar words

The code's purpose is this: Two words are friends if they have a Levenshtein distance of 1. That is, you can add, remove, or substitute exactly one letter in word X to create word Y. A word’s social ...
Leon Z.'s user avatar
  • 39
9 votes
3 answers
2k views

C++ edit distance / string similarity function based on the Jaro-Winkler algorithm

I wrote a short library function, based on an example from Rosetta, to compare two strings and determine similarity, using Jaro-Winkler. A short copy-paste ready example: main.cpp ...
Stefan's user avatar
  • 813
3 votes
1 answer
373 views

Matching entities in SQL Server to replace iterative Python script

I have a SQL (MS SQL Server) database of ~22 million companies (called target_db in my code). For example: ...
pawelty's user avatar
  • 131
5 votes
1 answer
268 views

My text comparison algorithm works very slow

I tried to create an algorithm (Translation Memory) that finds similarities between texts and try to predict the closest possible translation of the text, but there is a big problem with the working ...
J. Doe's user avatar
  • 59
2 votes
2 answers
399 views

Hamming distance

I am wondering how I can improve the runtime of this code. I was solving this task at leetcode, and came up with this solution. But I got the result that my runtime is 88 ms, which beats a bit more ...
Leff's user avatar
  • 239
1 vote
1 answer
174 views

Comparing two n×m matrices

I have to do a pairwise compare of a couple of text files. They have the following format: ...
swit's user avatar
  • 113
2 votes
1 answer
831 views

Code to calculate similarity between strings - R

I have a large datafile with names and I want to create a similarity distance matrix. With this matrix I want to get similar names that could be the same person (or not) and that I could compare these ...
psoares's user avatar
  • 201
3 votes
0 answers
269 views

Message classification with Levenshtein Distance

I have a Python script that classifies messages. Each message carries a score, which is tallied up later in the script. It looks for messages that look alike, and puts them into a category. ...
tyteen4a03's user avatar
1 vote
0 answers
1k views

Which function is faster levenshtein() or similar_text()?

Brief I wrote two functions using levenshtein() and similar_text(). The functions will find similar words from the dictionary ...
Andreas Hunter's user avatar
4 votes
0 answers
197 views

Minimum number of basic operations to convert str1 into str2

I am to convert a given string into another using only three basic operations, that is by deleting, inserting or replacing a character. Changes can only be made to string 1 and it is given that the ...
Yulan van Oppen's user avatar
2 votes
2 answers
1k views

Calculation of Hamming distance between two adjacency lists

I have written a Java program to calculate the Hamming distance between two adjacency lists. The program calculates the Hamming distance correctly, but it takes a very long time, especially when ...
user avatar
7 votes
1 answer
4k views

Approximate string search in Python

I have a long text (about 6,000,000 chars) and a short text (about 6,000 chars). The long text contains the short text, but not exactly - a small number of words are missing, abbreviated or just ...
Erel Segal-Halevi's user avatar
3 votes
2 answers
1k views

Compare two files and save the result into a pickle file

My code should compare two vectors saved as dictionary (two pickle files) and save the result into a pickle file too. This works but very slowly. For one compare result I'm waiting about 7:20 min. ...
Yunus Simsek's user avatar
3 votes
2 answers
1k views

Damerau Levenshtein Implementation in Kotlin

This is an implementation of the Damerau-Levenshtein distance in Kotlin which I created as an exercise, but might be also useful, if it proves to be correct. The implementation is based on this ...
gil.fernandes's user avatar
5 votes
2 answers
360 views

Test whether the edit-distance of two strings is at most 1

There are three types of edits that can be performed on strings: insert a character, remove a character, or replace a character. EXAMPLES: ...
Eango's user avatar
  • 53