Questions tagged [levenshtein-distance]
A metric for measuring the amount of difference between two sequences. The Levenshtein distance allows deletion, insertion and substitution.
969
questions
0
votes
0
answers
27
views
The theoretical complexity of Tries and the distances of Levenshtein to suggest similar words
Could someone explain me about the complexity of Trie and the algorithm of the distance of levenshtein? For tries my professor, has one image that says the complexity of it is O(k(logm +1)) where k is ...
-1
votes
0
answers
63
views
Cannot access memory at address 0x4 (unordered_map)
I am writing a spellchecker that uses the Levenshtein Distance algorithm and a hash map for the dictionary. This function is meant to take one string as input, compare it to the entire dictionary and ...
0
votes
0
answers
29
views
Search queries that pass through some filters
I'd like your help because I'm stuck with a function that doesn't work as expected due to the search filter. I know it's the cause of the misfunctions because with a simple one : it does work well. I ...
0
votes
0
answers
28
views
Create embeddings for string matching
I have 4 lists of companies names. Lets take a company Google. In List A, Google is written as Google Ltd, In 2nd list, it is written as Google Inc (extended etc), 3rd contain Beta Gogl (misspelled ...
0
votes
2
answers
68
views
Wrong levenshtein UTF8
From here Levenshtein distance on diacritic characters
I'm using this PHP function to calculate the levenshtein distance for UTF8 characters.
function levenshtein_php($str1, $str2){
$length1 = ...
0
votes
1
answer
50
views
Python: Get substring of a string with a closest match to another string
A nice algorithmic trivia for you today. :)
I have two strings – one is a longer sentence and the another one is shorter sentence that was discovered by LLM within the longer one. Let's see an example:...
-2
votes
2
answers
77
views
What distance measure can I use that factors in order? [closed]
I have a few lists that havethe same IDs that are strings. They are as follows:
list1 = ["1", "2", "3", "4", "5"]
list2 = ["1", "2"...
0
votes
0
answers
45
views
Levenshtein method to extract data from csv
I have a csv file where there are product names, manufacturer, id and review on each product. My problem is in two stages:
IMPT: The review column is real customer input so no standardised format. ...
0
votes
0
answers
60
views
How can I replace the misspelled words or technical language in each string of the dataframe with correct words (Dutch)?
I have a dataframe containing ~400000 rows and multiple columns. On of these columns contain strings of text. After some initial text cleaning I end up with the following subset of my dataframe:
Data ...
0
votes
1
answer
36
views
Ideas for approaching pattern matching/distance problem
I am trying to find an algorithm that is approaching the problem of pattern matching.
Basically, I have two strings that have ordered points. Let's say each point is a different city that you pass. I ...
0
votes
1
answer
99
views
How to detect that two songs on Spotify are the same (have similar name)
I'm using the following code to detect that two songs (same song, but different versions, e.g. typos, or concert variations) on Spotify are the same (have similar name). Is there a better (more ...
0
votes
1
answer
124
views
String similarity algorithms
I am comparing products across multiple stores. I only have access to the product name - which often differs between stores. For example: Store 1 might list a product as "iPhone 14 Midnight 128GB&...
0
votes
0
answers
122
views
levenshtein from pyspark.sql.functions is very slow
I need to do fuzzy match and am using levenshtein pyspark function, as it is inbuilt pyspark function I thought there will be speed advantage over udf. It is very slow, there are about 341 rows(max) ...
0
votes
1
answer
78
views
Levenshtein on dataframe column and input list
New to pyspark and I need to do fuzzy match. Found that levenhenstein is a native function which can do that. I have a dataframe like this:
+----------------+----------------+
| col1| ...
0
votes
0
answers
41
views
workaround for k-means to use levenshtein distance in scikit?
I have tried to apply a custom distance to my kNN model for the reasons I detail below.
Here is my metric:
def distance_fun(df, text_feat, num_feat):
# len(text_feat) levenshtein
# len(...
0
votes
0
answers
17
views
levenshtein formula in search
I am trying to use Levinstein's formula in the search. My task is that if someone writes botmen on the word, they find the closest options. In my case, first should be batman and then superman and x-...
0
votes
1
answer
107
views
Weighted Distance Matrix for QWERTZ Keyboard for Levenshtein Distance Algorithm
I have a weight Matrix for a Levenshtein Distance Algorithm which looks like this
int[,] weights = new int[6, 6]
{
{ 0, 1, 2, 1, 1, 2 },
{ 1, 0, 1, 2, 1, 2 },
{ 2, 1, 0,...
1
vote
1
answer
130
views
How to match two dataframes by applying fuzzy_pandas merge on different columns?
I have an input and a master file in which I first tried doing an exact match using the fpd.fuzzy_merge function, which seems to be working perfectly. Afterwards, I want to start applying the ...
0
votes
1
answer
268
views
How to find out if string contains substring or something similar to it
There is two string, str1 is pattern, str2 is a long text
str1 = 'how to do this weird task'
str2 = 'once upon a time...and smth long'
How to find out if str2 contains str1 or something similar to it ...
-3
votes
1
answer
82
views
What is the utility of the Levenshtein distance?
`So I had a debate with my teacher on what was the best method to quantify how different two given strings are. She told me to use the Levenshtein distance (https://en.wikipedia.org/wiki/...
2
votes
1
answer
466
views
Levenshtein Distance/Custum Function in Google Sheets Query
I added a function
levenshteinDistanceDP(string1,string2)
as a custom function in AppScript. It returns an Integer. Additionally I have the Query in a sheet:
QUERY(Expenses!A1:H;"SELECT A, B, C, ...
1
vote
1
answer
35
views
Correct typos inside a column using word distance
if have a column inside a pandas df containing a bunch of names:
NAME
-------
robert
robert
robrt
marie
ann
I'd like to merge similar ones in order to correct/uniform typos, resulting in:
NAME
-------...
0
votes
0
answers
56
views
How to execute levenshtein distance in PostgreSQL dynamic SQL?
I'm trying to apply Levenshtein distance in PostgreSQL Dynamic SQL. Here is what I put together. This will go into a stored procedure.
The end result is to return the total number of records to the ...
0
votes
0
answers
43
views
Levenshtein distance algorithm's variant: calculate distance to make a string to be longest substring of other
Are there any algorithm similar to Levenshtein distance algorithm, which can be described:
Original: the minimum number of single-character edits required to change one word into the other
What I want:...
0
votes
0
answers
46
views
Hamming distance with swap
I am looking for an algorithm to compute the 'distance' of 2 string of same length. The operations eligible are :
replace a char
swap two char whatever there position is
Hamming distance will fit ...
0
votes
1
answer
58
views
Dutch (or German) compound words in search functions (in PHP)
I have been having an issue with building a search function for a while now that I'm building for a cooking blog.
In Dutch (similar to German), one can add as many compound words together to create a ...
0
votes
0
answers
46
views
How to accelerate dbscan with levenshtein distance matrix? Can it be vectorize?
I have a 2d numpy text array X, where name,surname and 10 columns of smth else
and want to cluster it with custom metric:
def my_leven(x, y): #two rows of array
dist = math.sqrt(np.sum([pow(1-...
0
votes
0
answers
37
views
My fuzzy logic code is taking too long and not giving result
I have a task to remove the duplicate codes from a master data of approx 80K data points .
The duplicate identification can only be done using the 'description' field.
I have tried fuzzy logic - both ...
0
votes
1
answer
90
views
How to find Levenshtein distance between 1 million article titles, where every title is compared to every other title?
I have a large pandas DataFrame consisting of 1 million rows, and I want to get the Levenshtein distance between every entity in one column of the DataFrame. I tried merging the column with itself to ...
1
vote
1
answer
77
views
How would I make clusters from a Levenshtein similarity matrix?
I have a similarity matrix of words and would like to apply an algorithm that can put the words in clusters.
Here's the example I have so far:
from Levenshtein import distance
import numpy as np
...
0
votes
0
answers
86
views
EXCEL: Look for cells in column with fuzzy duplicates
my problem is as follows:
Imagine I have a large Excel dataset that has a company identifier in column (A) and long string texts within cells in column (B). These texts in those cells contain many ...
0
votes
0
answers
70
views
Getting Levenshtein distance from `diifflib.ndiff`
The levenshtein distance algorithm in Python is too slow as I am comparing many strings.
So I want to use difflib.ndiff to do it.
I tried parsing the output by interpreting "+", "-"...
0
votes
0
answers
13
views
A plot showing the edit distance as a line between two cities. The thickness / opacity of the line can be adjusted based on the edit distance score
I have calculate the edit disctance between differents language, as shown below.
Now i am trying to plot showing the edit distance as a line between two cities. The thickness / opacity of the line ...
2
votes
0
answers
390
views
How can I fix ModuleNotFoundError: No module named 'similarity.normalized_levenshtein'?
So I keep having this error ModuleNotFoundError: No module named 'similarity.normalized_levenshtein' in my error log for some reasons.
This is what I was trying to do:
from similarity....
0
votes
0
answers
157
views
Is there any specific way to implement Damerau-Levenshtein distances so they perform better on integer pairs?
Say I have a list of numbers composed of a sequential ID followed by two mod11 check digits, for example:
ls = [191, 272, 353, 434, 515, 604, 787, 868, 949, 1082, 1163, 1244, 1325, 1406,
1597, ...
0
votes
0
answers
84
views
Levenshtein distance between two columns of two different dataframes
Let's say i have two dataframes
Dataframe 1:
ID1
NAME1
1
JUANA
2
LUCAS
3
PEDRO
4
MATIAS
Dataframe 2:
ID2
NAME2
1
JUAN
2
JUANA
3
JUANITA
4
MATIAS
5
MATIA
6
MATIAS
7
MATIAZ
Each one don't ...
0
votes
0
answers
40
views
How to run the levenshtein_distance function using the text_preprocessing variable?
I have a program like this:
$text1 = "Hello, World!";
$text2 = "Levenshtein distance (or edit distance) between two strings";
$preprocessing_text1 = text_preprocessing($text1);
...
3
votes
0
answers
76
views
Minimum edit distance of two documents
I know how to get the minimum edit distance of two short strings like 'abcde' and 'abfde',but how to do the MED of two documents or essays with spaces , tabs , enters or even two codes?
For example:
...
0
votes
1
answer
456
views
Fuzzy Matching 2 DataFrames on multiple columns which includes one column with Float Values
I have 2 DataFrames namely 'Master_data_df' & 'My_records_df'.
I am required to find out records which are missed out from 'Master_data_df' by comparing with 'My_records_df'.
Here the column '...
0
votes
0
answers
266
views
Simple spell checker using Levenshtein distance
I have to implement 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 "...
0
votes
0
answers
38
views
Optimize levenshtein find similarity of string in list of strings
We have the given problem:
a list of 1M rows, each row is a sentence.
we have a list of valid strings. The list length is ~1000.
We need to know if, for all the strings in a given sentence (from (1)),...
0
votes
0
answers
36
views
I need to find the closest name in a list
I had a really big file in this format that I passed into a string.
International Workshop on Collaborative Virtual Environments B3
International 3D System Integration Conference B1
Three-Dimensional ...
0
votes
1
answer
443
views
Matching & Comparing Strings via Levenshtein Distance
I have one table with a static list of "template" strings, and another sheet that updates daily with new "populated" strings.
I want to be able to identify which "template&...
0
votes
1
answer
63
views
Use a custom function as argument to Ecto order_by
I have a function distance/2 which calculates the Levenshtein Distance between two strings.
I would like to use this as an argument for order_by/3 (documentation), so that the result be ordered by ...
1
vote
1
answer
63
views
Fuzzy search with 1 distance does not works for other languages in Solr
I have documents with fields name_en, name_de, name_fr etc. And words cutter in english and mutter in german. If I fuzzy-search with name_en:cuter~1 (with only one t) it works fine, but if I search ...
0
votes
0
answers
35
views
Function for computing percentage of how similar an array of text strings are to each other in javascript
Lets say I have the following array of strings, var = array_of_strings["abc","abcd"]
My goal is to run a function and have this return roughly 75% (0.75). Implying that the ...
0
votes
1
answer
152
views
Is there any way to update maximum characters limit in Levenshtein (Postgresql)?
I am using fuzzystrmatch extension in Postgresql 14.
When I am running below query, it is giving this error message:
ERROR: levenshtein argument exceeds maximum length of 255 characters
SELECT ...
0
votes
1
answer
232
views
How to zip one column of a dataframe (x) with each n columns of another (x1, x2, x3, x4, xn) and calculate lev distance for each pair?
I have a df containing names and urls
data = [
['name1', ''],
['name2', 'name2.com'],
['name3', 'name3.com, name4.com, name5.com' ],
]
df = pd.DataFrame(data, columns=["name", &...
1
vote
1
answer
273
views
How to cluster names
I have a dataset of words in a non-semantic context, basically names. I want to perform an act of grouping all the similar ones (say samantha, samanta, sammanta, samaynta.. ) in the same groups.
Since ...
0
votes
0
answers
625
views
How calculate confidence score for text recognition in ocr
Currently I am working on Vietnamse text recognition in image ocr.
I am struggling with evaluation metric has I don't have any ground truth to calculate the levistance distance or to calculate cer(...