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

12 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3
votes
0answers
59 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
0answers
107 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. <...
3
votes
0answers
126 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. ...
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 ...
3
votes
0answers
64 views

Space efficient revision history storage with diffs

I've written a tool to store a files history more efficiently by only generating diffs and storing them whereas whole file would otherwise have to be stored. I would like to to hear about ways to ...
3
votes
0answers
390 views

Edit distance (Optimal Alignment) - follow up

This is a follow up of this question Optimal substructure of ED: Here is the reasoning behind my solution: let \$x = (\alpha _{1},\alpha _{2},\alpha _{3},...,\alpha _{m})\$ and \$y = (\beta_{1},\...
2
votes
0answers
57 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() ...
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 ...
1
vote
0answers
187 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 ...
1
vote
0answers
519 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 ...
1
vote
0answers
158 views

Optimizing Levenshtein Distance with nested loop

Brief illustration: I have 2 classes - tbCustomer and tbDHN which is stored inside a list....
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,...