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
4
votes
2answers
371 views

Edit distance implementation

This problem is taken from the book Introduction to Algorithms, Third Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein: In order to transform one source string ...
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
1answer
150 views

Efficiently calculating differences between file using diff file

I'm using SVNKit to get diff information between two revisions. I'm using the diff utility to generate a diff file, however I still need to parse it into numbers. I implemented a solution, but it is ...
3
votes
1answer
1k views

Matlab implementation of Needleman-Wunsch algorithm

This code (an implementation of the path finding Needleman-Wunsch algorithm), given two sequences, correctly aligns and calculates the similarity of them. For example, given two sequences: AAA,CCC ...
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
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 ...
1
vote
1answer
563 views

Hamming distance in Scala

Problem Write a program that can calculate the Hamming difference between two DNA strands. GAGCCTACTAACGGGAT CATCGTAATGACGGCCT ^ ^ ^ ^ ^ ^^ Code ...
4
votes
3answers
2k views

Making as many unique strings as possible by removing two characters

I'm attempting a programming challenge type task in C#, where the goal is to determine how many unique strings can be obtained by removing two characters. The prompt for the task implied that I should ...
2
votes
2answers
130 views

Name-deduplicating class

Recently I asked a question on Programming SE about public vs private methods fo unit testing, which generated a lot of interesting responses. I only posted a skeleton of the code there, as it was a ...
2
votes
2answers
81 views

A sequence of mistakes

This question is part of a series solving the Rosalind challenges. For the previous question in this series, see The Genetic Code. The repository with all my up-to-date solutions so far can be found ...
3
votes
3answers
870 views

Calculate the Hamming difference between two DNA strands

Write a program that can calculate the Hamming difference between two DNA strands. GAGCCTACTAACGGGAT CATCGTAATGACGGCCT ^ ^ ^ ^ ^ ^^ The Hamming distance between these two DNA ...
1
vote
1answer
2k views

Levenshtein distance with edit sequence and alignment in Java

I have this program that computes a Levenshtein distance of the two input strings, their edit sequence, and the alignment: LevenshteinEditDistance.java: ...
3
votes
1answer
341 views

Making the Levenshtein distance code cleaner

I was writing an implementation of Levenshtein distance in Python and I found my code really ugly. Have you any idea how to make it more elegant? ...
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\...
2
votes
3answers
250 views

Duplicate Line Finder

I recently wrote a program that reads a plain text file, and compares every line and alerts you if any are similar, based on a float value that you pass in to a function. ...
3
votes
1answer
282 views

String similarity calculation

For string similarity, it is defined as longest common prefix length. For example, "abc" and "abd" is 2, and "aaa" and "aaab" is 3. The problem is calculate the similarity of string S and all its ...
3
votes
2answers
218 views

Comparison function for strings

I got a function that has as input 2 strings, computes the string similarity of all the combinations and give back and output the highest similarity. For example, "you are" and "are you" will have 1 ...
5
votes
2answers
845 views

Find no of swaps needed to club identical elements of array together

I have created a solution for the problem as below: Given a string S consisting of letters 'O' and 'Z'. Calculate the minimum number of changes required such that all O's are adjacent to each ...
6
votes
2answers
1k views

Jaccard distance between strings in Rust

The Jaccard distance between two sets is the size of their intersection divided by the size of their union. For example, the distance between {1, 2, 3} and ...
3
votes
2answers
167 views

Iterate over large amount of words in Python

I wrote a program that should check a dictionary that contains about 50000 other dictionaries. In those dictionaries, one of the keys has a list of words as value. Now, I iterate over those words, ...
22
votes
5answers
10k views

Algorithm to transform one word to another through valid words

I have been practicing backtracking and I wanted to know how I can improve my code. For eg, I don't want to use global. Also, I am not sure if my code will work for all the cases. ...
0
votes
1answer
224 views

Wagner-Fischer algorithm

Please let me know if there is any other optimal way of doing this. ...
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 ...
4
votes
2answers
157 views

Recognizing a sequence read through OCR software

I am trying to recognize a sentence that I have read through optical character recognition software. This code will eventually run on a Raspberry Pi. I know for certain that it's meant to be one of a ...
4
votes
2answers
2k views

Count chars difference between two strings

Given two strings with the same length, we check how many chars on the same positions are different. For example: ABCD and ABBD should return 1. Here is a link to a gist with tests, to have a better ...
4
votes
3answers
210 views

Console app to compare all directory names for similarity

I just got the urge to write a small console app to compare all directories name for similarity. I have > 3000 directories and over time some of them are really similar, eg. an update: Test Case ver 1 ...
4
votes
2answers
2k views

Change one word into another by picking words that differ by one character

There is a file with two words with the same length. Call them first and last. Also there is a file - dictionary with a lot of different words. The task is to find shortest chain of words from ...
5
votes
1answer
139 views

Levenshtein Distance with Haskell Vectors and Memoization

Is the following an effective way to implement the Levenshtein Distance with Haskell vectors? ...
3
votes
1answer
731 views

Word ladder solution in Java using matrix

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that only one letter can be changed at a time and each intermediate word ...
7
votes
1answer
270 views

Java WordLadder Program

I wrote a program that calculates the minimum number of rungs of a "word ladder" between a starting word and an ending word. The function minlinks() takes in 3 ...
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. ...
4
votes
3answers
2k views

Sorting movie search results by similarity

I want to sort "movie search results" to get most probable movie that match "search". Input example: CARS.2.2011.720P.AC3.mkv I have a NameMatcher class ...
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 ...
2
votes
1answer
92 views

Find files with similar contents

I'm not normally a C programmer but thought I'd take a shot at making something useful. This is a C utility I wrote to judge how similar several files are using the algorithm I think ...
4
votes
1answer
265 views

Finding the minimum number of required deletions to have a non-repeating string

I wrote code for the following problem: Given a string, print out the number of deletions required so that the adjacent alphabets are distinct. Please suggest different methods by which I can ...
7
votes
3answers
12k views

One character diff - string comparison

The question was: Create an algorithm to check if two strings differ by one character. This wasn't my interview, so I tried to understand the question. Options: just compare the chars one by one,...
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 ...
3
votes
1answer
3k views

Finding a word ladder using Breadth First Search

This is a LeetCode problem called Word Ladder: Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, where only one letter can ...
3
votes
3answers
1k views

Basic T-SQL to compare two same length strings

I've come up with the following T-SQL to compare similar same length strings. Example usage would be: OCR returns a value which is expected to be in the database. PATINDEX is used to check the value'...
7
votes
4answers
651 views

Python code for detecting a single item moved in a list

I need to write a function that takes an original list of unique values and a resulting list: [0,1,2,3] [0,3,1,2] and detect that only a single element was moved ...
14
votes
3answers
2k views

The Love-Letter Mystery

Problem Statement James got hold of a love letter that his friend Harry has written for his girlfriend. Being the prankster that James is, he decides to meddle with it. He changes all the words ...
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 ...
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 ...
10
votes
2answers
702 views

Comparing client lists with Cross Joins

I've written a query to compare the clients in our database with the people in a list that I've received. It needs to check if anyone from the list is one of our clients. I've created a temporary ...
4
votes
2answers
1k views

Simple fuzzy text search algorithm

Basically, this code takes a keyword and an array of strings, then sorts them based on two things: the number of characters shared with the key, and the distance between them.(As a side note, would ...
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 ...
4
votes
2answers
704 views

“Edit distance” UVA programming challenge

I'm trying to solve a programming challenge for fun. The programming challenge is here and my solution for the same can be found here. It currently causes an exceeded time limit. ...
2
votes
1answer
495 views

Is this the most efficient way to track word changes in a string?

I'm working on a writing platform and am using a modified version of the Levenshtein distance algorithm to track a writer's engagement with their writing. It tracks not only words added to their ...
2
votes
2answers
1k views

Optimizing SPOJ edit distance solution

I was doing a standard problem of DP (dynamic programming) on SPOJ Edit Distance using Python. ...
1
vote
1answer
158 views

Edit distance function

Could you please help me to review my first function (modified from an example) in terms of best practice, coding style suggestions and any obvious language mistake/improvements? ...