Questions tagged [levenshtein-distance]

A metric for measuring the amount of difference between two sequences. The Levenshtein distance allows deletion, insertion and substitution.

Filter by
Sorted by
Tagged with
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 ...
Leonnnn's user avatar
-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 ...
Nathan Allie's user avatar
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 ...
Robin Rousset's user avatar
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 ...
user3585510's user avatar
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 = ...
MMT's user avatar
  • 83
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:...
cadavre's user avatar
  • 1,354
-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"...
Hummer's user avatar
  • 423
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. ...
Fanatic's user avatar
  • 51
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 ...
user22247751's user avatar
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 ...
Filip's user avatar
  • 303
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 ...
xralf's user avatar
  • 3,144
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&...
user2248702's user avatar
  • 2,859
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) ...
curios's user avatar
  • 1
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| ...
curios's user avatar
  • 1
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(...
Chapo's user avatar
  • 2,573
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-...
Boychik's user avatar
  • 73
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,...
Marco-rm-f's user avatar
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 ...
Linear17's user avatar
  • 148
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 ...
anon.for's user avatar
-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/...
Robin Laperriere's user avatar
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, ...
noah's user avatar
  • 35
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 -------...
eggcheesestickscorn's user avatar
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 ...
Kings's user avatar
  • 1
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:...
Ming Hieu's user avatar
  • 169
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 ...
Toto's user avatar
  • 7,541
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 ...
Pepijn Ekelmans's user avatar
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-...
anon.for's user avatar
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 ...
rohit's user avatar
  • 1
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 ...
asunder_score's user avatar
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 ...
AI92's user avatar
  • 397
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 ...
qrif's user avatar
  • 1
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 "+", "-"...
sudoer's user avatar
  • 154
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 ...
Engr. Khuram  Shahzad's user avatar
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....
crazycoder1602's user avatar
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, ...
Maav's user avatar
  • 11
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 ...
killua6914's user avatar
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); ...
Adi's user avatar
  • 27
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: ...
Rou2001's user avatar
  • 31
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 '...
sagardbhangale's user avatar
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 "...
Raluca123's user avatar
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)),...
InsDSt's user avatar
  • 37
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 ...
João's user avatar
  • 7
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&...
Max Singer's user avatar
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 ...
Basil's user avatar
  • 518
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 ...
AvrDragon's user avatar
  • 7,249
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 ...
Joseph Astrahan's user avatar
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 ...
Nullify's user avatar
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", &...
SilviaC's user avatar
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 ...
sophinez's user avatar
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(...
ram_98's user avatar
  • 23

1
2 3 4 5
20