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
6
votes
1answer
40 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 ...
3
votes
1answer
186 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: ...
7
votes
2answers
123 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. ...
6
votes
0answers
1k views

Edit Distance Implementation

I was doing some reading on the Wagner Fischer algorithm algorithm for computing the edit distance on strings. None of the examples in the literature I have read showed how to recover the edit ...
5
votes
1answer
50 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:...
7
votes
3answers
589 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 ...
3
votes
3answers
4k views

Given two strings, a and b, determine the minimum number of character deletions required to make a and b anagrams

I'm trying to figure out how my code could be improved. I solved a HackerRank problem from the Cracking the Coding Interview section, and am thinking that it should be able to be solved a simpler than ...
2
votes
1answer
955 views

Approximately matching strings to elements in an array

I have two datasets: A list containing about 4200 string elements A list containing about 119,000 string elements I'm taking each element from list 1 and looping through each element in list 2 using ...
10
votes
2answers
7k views

A String.prototype.diff() implementation (text diff)

I just had the idea to develop an algorithm to calculate and highlight the difference between two strings. I know that there are already some libraries to do the job but I just tried to make my own. I ...
5
votes
2answers
818 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[] ...
11
votes
2answers
3k 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: ...
1
vote
1answer
71 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. ...
2
votes
1answer
103 views

Get Levenshtein Distance

Logic based of this site which had a VB example I used as a base. ...
6
votes
2answers
2k 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 ...
2
votes
3answers
4k views

Edit distance between 2 strings

I have written a program that calculates the "cost" of transforming one string into another. I would like you to review it. ...
5
votes
1answer
4k views

Comparing two approximate string matching algorithms in Java

Problem description Given a text \$T[0..n)\$, a pattern \$P[0..m)\$, and a nonnegative integer \$k\$, report all positions \$j \in [0..n)\$ such that \$ed(P, T(j - l..j]) \leq k\$ for some \$l \geq 0\...
3
votes
0answers
55 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 ...
3
votes
1answer
667 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 ...
4
votes
2answers
3k views

Check if two strings are one 'edit' apart using Python

The code below is my solution in python 3 to exercise 1.5 in Cracking the Coding Interview. I would appreciate feedback on both the algorithm (improvements to space and time complexity) and/or coding ...
2
votes
2answers
1k views

Image similarity measure

I'm attempting to speed up my genetic algorithm that modifies images. After searching, I've found that my fitness function is the bottleneck, taking sometimes up to ...
1
vote
0answers
53 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() ...
3
votes
0answers
102 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. <...
6
votes
2answers
319 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: ...
3
votes
2answers
114 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 ...
6
votes
2answers
1k views

Finding the best matching block/patch in Python

I wish to locate the closest matching NxN block within a WxW window centred at location (x,y) of a larger 2D array. The code below works fine but is very slow for my needs as I need to run this ...
5
votes
1answer
160 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 ...
4
votes
1answer
427 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 ...
2
votes
1answer
86 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 ...
1
vote
0answers
183 views

Weighted Jaccard Similarity in Neo4j

I'm very new to Neo4J, and to Jaccard similarity (weighted or non!), so I'd really appreciate someone casting an eye over my code here before I try to use the results. Jaccard similarity for 2 sets ...
4
votes
1answer
803 views

Python softmatcher using difflib impracticably slow

I have a softmatch function (below) that takes a donor list and a new entry and looks to see if the given donor already exists. The data is not exact, so I have to use a softmatch to determine ...
7
votes
2answers
4k 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 ...
4
votes
1answer
121 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 ...
1
vote
0answers
76 views

One-off string detection

Problem spec from CareerCup. Given two strings, return boolean True/False if they are only one edit apart. Edit can be insert/delete/update of only one character in the string. Eg. True xyz,xz xyz,...
2
votes
2answers
7k views

Comparing long lists of strings for the closest match

What's the fastest (quality is important too, but a little less important) way to compare two strings? I'm looking for the most efficient way to compare two strings. Some of the strings I'm comparing ...
5
votes
1answer
1k views

Parsing URLs in Pandas DataFrame

My client needs their Google AdWords destination URL query parsed and the values spell checked to eliminate any typos ("use" instead of "us", etc). I'm pulling the data using the AdWords API and ...
9
votes
3answers
540 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 ...
12
votes
1answer
19k views

String Matching and Clustering

I have a pretty simple problem. A large set of unique strings that are to various degrees not clean, and in reality they in fact represent the same underlying reality. They are not person names, but ...
2
votes
2answers
557 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 ...
2
votes
1answer
460 views

Implementation of Wagner-Fischer-algorithm

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 ...
2
votes
0answers
87 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 ...
2
votes
2answers
299 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 ...
1
vote
1answer
102 views

Comparing two n×m matrices

I have to do a pairwise compare of a couple of text files. They have the following format: ...
2
votes
1answer
519 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 ...
3
votes
0answers
122 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. ...
1
vote
0answers
494 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 ...
3
votes
0answers
78 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 ...
5
votes
2answers
1k views

Clustering nodes with Hamming distance < 3

I want to speed up the following code, which is from an algorithm class. I get a list of 200000 nodes where every node is a tuple of the length of 24 where every item is either a 1 or 0. These ...
7
votes
1answer
3k 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 ...
5
votes
2answers
2k views

Hamming distance between numbers in JavaScript

In Leetcode it states that my runtime is only faster than 38% all of submitted JavaScript solutions. Is there anything I can change to make it more efficient? ...
2
votes
2answers
399 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. ...