2
$\begingroup$

I want to compare strings and give them score based on how similar the content is in them just like comparing two arrays in scipy cosine similarity.

For example :

string one : 'Pair of women's shoes'

string two : 'women shoes' pair'

Logically I would want a high score between the two strings. Is there any way to do so ? I am comparing array of strings with another array in a single column in my dataframe. I want to find similar rows this way. Can this be achieved ?

$\endgroup$

2 Answers 2

1
$\begingroup$

You can try the Levenshtein Distance. From Wikipedia this is the abstract

In information theory, linguistics and computer science, the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other.

Then you can use this Python function to compute it yourself or just install a Python package that does it for you

memo = {}
def levenshtein(s, t):
    if s == "":
        return len(t)
    if t == "":
        return len(s)
    cost = 0 if s[-1] == t[-1] else 1

    i1 = (s[:-1], t)
    if not i1 in memo:
        memo[i1] = levenshtein(*i1)
    i2 = (s, t[:-1])
    if not i2 in memo:
        memo[i2] = levenshtein(*i2)
    i3 = (s[:-1], t[:-1])
    if not i3 in memo:
        memo[i3] = levenshtein(*i3)
    res = min([memo[i1]+1, memo[i2]+1, memo[i3]+cost])

    return res
print(levenshtein("Python", "Pethno"))
print(levenshtein("Pair of women's shoes","women shoes' pair"))

>> 3
>> 16

Source code for the above snippet

Or if you want to do it directly on your DataFrame, you can do it like that

df['LD'] = df.apply(lambda row: levenshtein(row['text1'], row['text2']), axis=1)
$\endgroup$
2
$\begingroup$

Levenshtein distance is computationally expensive and therefore slow for large datasets. For a faster method, you can use sci-kit learn's CountVectorizer or TfidfVectorizer to get frequencies of n-grams for each string. This will produce a frequency matrix, which you can then use as the input for sklearn.metrics.pairwise_distances(), which will give you a pairwise distance matrix. Note that with a distance matrix, values closer to 0 are more similar pairs (while in a cosine similarity matrix, values closer to 0 are less similar pairs).

See this blogpost for a nice tutorial on how to go about this.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.