Questions tagged [levenshtein-distance]
A metric for measuring the amount of difference between two sequences. The Levenshtein distance allows deletion, insertion and substitution.
909
questions
2
votes
1
answer
47
views
Highlight surrounding cells of selected cell
I am trying to exercise Levenshtein Distance in Excel. To fill the cells, we need to consider the minimum of three cells (left, up-left, and up). It is easy to find minimum of those three if they were ...
0
votes
0
answers
37
views
Cosine similarity between rows of two large dataframes in R
I've two dataframes DF1 and DF2. One of them is a very large DF.
I've created examples DF1 and 2 like this:
library(tidyverse)
A<-rep(c('Mavs', 'Spurs', 'Lakers', 'Cavs', 'Suns'), 1000000)
DF1<-...
0
votes
2
answers
38
views
using Damerau-Levenshtein distance to compare sets of text in code.org
Not very knowledgeable with coding, I usually use block coding and not typing.
I've used many different Levenshtein distance codes I've found online and most of them didn't work for one reason or ...
0
votes
1
answer
33
views
Import of python-levenshtein/levenshtein failed after successfully pip install
after successfully pip install python-Levenshtein I can't import this lib. I tried several import commands, but I'll always get the same error message in VS Code Import "Levenshtein" could ...
0
votes
1
answer
24
views
Efficient way of generating new columns having string similarity distances between two string columns
I have a pandas dataframe with shape (1138812, 14) and columns
['id', 'name', 'latitude', 'longitude', 'address', 'city', 'state',
'zip', 'country', 'url', 'phone', 'categories', '...
0
votes
1
answer
34
views
algorithm to know if inserted, substitued or deleted a character (similar to Levenshtein)
I want to make a function that keeps track of the transformations made to make one string identical to another one
Example:
A = batyu
B = beauty
diff(A,B) has to return:
[[1,"Insert", "...
9
votes
3
answers
204
views
fuzzy version of stringr::str_detect for filtering dataframe
I've got a database with free text fields that I want to use to filter a data.frame or tibble. I could perhaps with lots of work create a list of all possible misspellings of my search terms that ...
1
vote
2
answers
38
views
Stringdist distance unexpectedly large
The following data has the surprising result that it does not match. I was expecting the distance to be 5, but even at 7 I get no match
library(fuzzyjoin)
one <- as.data.frame("Other field ...
0
votes
0
answers
40
views
Levenshtein for multiple words on multiple columns
I'm trying to make search a bit more friendly and wanted to exploit the Levenshtein distance. This works great but if a value in a column has a length of 25 characters long, the distance to only 3 ...
0
votes
0
answers
42
views
How to update different columns matches in the same row?
I have trying to use fuzzywuzzy to do matching. Master.xlsx have a column (namely 'Brand' on the first column of the excel) I would like to match and matching.xlsx have multiple columns needed to be ...
4
votes
2
answers
68
views
Is there an R function to do a pairwise Levenshtein distance calculation of two vectors of strings?
I have two vectors of strings:
a <- c('Alpha', 'Beta', 'Gamma', 'Delta')
b <- c('Epsilon', 'Zeta', 'Eta', 'Theta')
and I would like to compute the Levenshtein distance or edit distance for each ...
1
vote
1
answer
43
views
Exasol SQL Fuzzy Matching function
Good day, all you SQL geniuses out there. I'm running into a bit of an issue. The firm I work at uses EXASOL SQL and I'm trying to get find a function that I can use in order to fuzzy match two ...
0
votes
0
answers
13
views
Is there an algorithm/way to find out how different (or the minimum distance between) 2 list orders?
I have a bunch of items I want to rate in a specific order. For example:
["Person1", "Person2", "Person3", "Person4", "Person5"]
Which can be ordered ...
0
votes
1
answer
46
views
How to replace strings in a dataframe where there is a likely typo
I been working on this for a few hours but no progress on how to automate. I have a dataframe with over 50,000 rows.
Occasionally there is a misspelling like
Rosalind vs Rosalinda
Wong vs Wang
Of ...
0
votes
0
answers
61
views
Find duplicates by LEVENSHTEIN distance
I'm trying to get duplicates with two conditions :
the standard groupBy method (by name and type)
and also by similarities on the name field.
In all articles about this, they always find ...
0
votes
1
answer
95
views
how token sort ratio works?
Can someone explain me how this function of the library fuzzywuzzy in Python works? I know how the Levenshtein distance works but I don't understand how the ratio is computed.
b = fuzz....
0
votes
0
answers
16
views
Comparing string answer for similarity
I am currently working on a bot for our companies rocket chat. One of the features I have planned is sort of a "busy" status for developers.
Basically after you type !youshallnotpass in any ...
0
votes
1
answer
76
views
How to make this IsSimilar(varchar,varchar) function more performant
I need to implement a function to look for similar names. It's for the development of a new system that has migrated the data of a previous system.
One of the features would be that on account ...
0
votes
1
answer
48
views
Plotting Levenshtein distance scores in R
I'm trying to plot the Levenshtein distance scores between 2 list of sequences (amino acid sequences) using something other than a heatmap. This is a code I used to generate a heatmap as an example:
...
0
votes
0
answers
65
views
Finding best match between individual words of two strings
I have a large number of incoming texts from users that I need to match with expected strings. Until now I have been using the Levenshtein ratio for comparing the two strings, from the Levenshtein ...
-1
votes
1
answer
94
views
Delete "almost duplicates" rows of string based on fuzzy matching with a lot of lines (>50 000)
I have 50 000 words like :
add
to add
chicken
a chicken
eat the chicken
to eat
...
And i want to drop the line which have a high fuzzy similarity with other lines.
Then the output should be:
add
to ...
2
votes
2
answers
85
views
Can every solution of the edit distance problem be shown on the matrix obtained from the dynamic programming algorithm?
I watched a video on Youtube explaining how to calculate which operations are used and how many times by going back to 1 from the last cell of the matrix obtained from the dynamic programming ...
0
votes
0
answers
30
views
big data Levenshtein edit distance
as part of a bigger project I am in need of using the edit distance algorithm on very large strings (10^8 chars each), and specifically I need the matrix used in the calculation of the entire edit ...
0
votes
0
answers
33
views
Fuzzy edit distance (typo handling) depending on term length (Apache SOLR or generally)
Are there any general recommendations for fuzzy edit distance (Levenshtein distance) depending on term length?
For instance, if I am searching for "Al Paccino", and I apply edit distance 2 ...
0
votes
0
answers
184
views
Levenshtein Distance in Power Query Using M
I've been using this VBA solution by smirkingman from another similar question for calculating Levenshtein distance between strings. I have a need to translate this to an M code function in Excel ...
0
votes
0
answers
57
views
How to make a function, with a condition of character's numbers, which can find possibles matching words?
I'm begin to Python and i'm trying to make a function, with a condition that finds a row of characters following, between two list of words.
I search something like this:
List1 = ['Birmanie', '...
1
vote
1
answer
30
views
How to find strings of a list in a text with typo's
I'm trying to check if some String in a list are in a given text. But the given text can have some typos. For example let's take this.
text: The brownw focx and the cat are in th eforest.
and my list ...
0
votes
0
answers
49
views
SQLALCHEMY ORM Postgres Dialect Query for Levenshtein Distance
Using SQLAlchemy ORM, Postgres backend, Python 3.7
I am converting many PostgreSQL queries to SA ORM queries.
I have this query:
LEVENSHTEIN_LESS_EQUAL(SUBSTRING(::text FROM 1 FOR 128), ...
0
votes
0
answers
21
views
Checking the similarities between 2 texts and in a dataframe of 100 rows (thus more than 2 sentences)
I have a dataframe of 100 rows and i would like to compare the similarities between the column OriginalTxt and the SummarizedTxt
OriginalTxt
SummarizedTxt
Due to the horizontal pusher system, the ...
0
votes
0
answers
39
views
Recommended String Metric Algorithm for string detection?
We're trying to choose a string metric algorithm for our string comparison program. Which would be the best string metric algorithm if we want to detect misspellings and alteration of the word like ...
0
votes
1
answer
47
views
Trying to check similarity of 2 columns full of strings with Python and Pysimilar or DamerauLevenshtein
I tried to summarize texts with a summarizer! The problem is that I would like to see if these texts are too similar, to do this I could read on google that I could use packages like pysimilar or ...
0
votes
0
answers
9
views
Algorithm or technique for mapping unknown input keys in user data to pre-defined set of output keys
I have files with key-value data as input, which I want to tranform into key-value data with pre-defined keys. The keys in the input data are not pre-defined.
Let me give an example:
file1:
clr -> ...
0
votes
0
answers
51
views
Fuzzy Join with Match Score
I'm trying to compare two files: Customer.xlsx and Employee.xlsx to match on Name AND SSN with a threshold of 0.80. If match is found, drop the ones where a match was not found and create a 3rd file ...
2
votes
0
answers
316
views
How to install python-Levenshtein on Windows? Getting an error when using fuzzywuzzy?
I'm writing a program that returns a list of tuples, each tuple consisting of closely matching strings present in two lists A and B using the python module fuzzywuzzy. However, on running this code, I'...
0
votes
0
answers
33
views
What is the relation between Levenshtein Word Distance and Boyer Moore searching algorithm?
Would they both be considered string matching algorithms?
Say I want to detect how close two strings are, so I want to match them. Thus I would use the Levenshtein Word Distance. However, if the ...
0
votes
1
answer
239
views
Edit Distance w/ operational weights in Python
I am learning about edit distance for the first time and have only been coding for a few months. I'm trying to modify the algorithm such that the different editing operations carry different weights ...
0
votes
0
answers
100
views
Faster efficient string matching in PySpark
In my db, I have a df of hundreds of thousand companies, and I have to retrieve them in another df that contains all companies existing.
To do that, I use PySpark :
def match_names(df_1, df_2):
...
1
vote
0
answers
40
views
What could be the better approach than apply method [closed]
I am working with fuzzy keyword matching
The first dataset consists on 20180 rows and second dataset about 10000 rows
I am using the .apply method to find the match
I am using progress bar to see my ...
0
votes
1
answer
65
views
Pandas - methods for combining similar column values into a larger supergroup
So I have a large dataset, and one of the columns contains values gathered from freetext (so some words are misspelled or similarly spelled). For example:
Diagnosis
----------
headache
headache
...
0
votes
1
answer
337
views
Can anyone explain this code for computing Levenshtein distance?
I was given this code that quickly returns whether the Levenshtein distance between two strings is exactly 2.
def li(s, i):
try:
return s[i]
except IndexError:
return None
...
0
votes
1
answer
77
views
Is there an R function for computing fast Levenshtein distance with threshold (maxDist)
I am looking for an R function, which returns the Levenshtein distance of two strings if the Levenshtein distance is less than a threshold, and saves time by not computing Levenshtein distances larger ...
1
vote
1
answer
70
views
Perfomance for join table with string comparison
I have two large tables and I need to fit them together. Matching should not be a clear comparison. I used trigrams, Levenshtein's formula, but I get very weak performance. Maybe someone can help ...
0
votes
0
answers
25
views
String subclass for phonetic Levenshtein distance
I'm trying to create a string subclass, in order to represent Arpabet symbols as single characters. Here is what I got so far:
import Levenshtein
class ArpabetChar(str):
"""
Class that ...
0
votes
1
answer
43
views
Is levenshtein distance the best tool for the job when I know the proper spelling of a string and historical misspellings?
I have two tables.
Table A has a single entry for each current employee, and contains the proper spelling of each user. There is only ever 80 employees at a given time, but the names themselves change ...
0
votes
0
answers
109
views
Fuzzy Match with pyspark
I have two dataframes(base_x and base_y), the first one has about 1.5 million records while the second one has two million.
These dataframes have records of people and I would like to fuzzy match them....
1
vote
1
answer
279
views
Get all variations of a string using Levenshtein distance
I found a lot of implementation doing the calculation of Levenshtein between 2 strings, but is there any implementation that can generate all variations using Levenshtein distance (max 2) for one ...
1
vote
1
answer
37
views
How to extract the difference given by the Levensthein distance?
The Levensthein distance provides a number which is the total number of differences between two strings. My question is: is it possible to retrieve, instead of the number, what are these differences? ...
0
votes
0
answers
40
views
Levenshtein Distance with Python to compare words
I have a dataset with the column "names" and I duplicate that dataset and made a few mistakes. For example I have "Adidas" and I made "Addas".
i want that if I read the ...
1
vote
2
answers
127
views
How do I efficiently find pairs of strings in a list with low (Damerau-)Levenshtein distance? [closed]
I currently contribute to a certain wiki database that currently has about 500000 entries. Some of these entries have keywords attached. Due to a previous lack of restrictions on the database, people ...
0
votes
1
answer
213
views
How to cluster strings by Hamming or Levenshtein distance
As an exercise, I would like to cluster a set of English words by Hamming or Levenshtein distance. If it is Hamming distance they will all have to be the same length (or padded to the same length) but ...