Is there any similarity function to compare two strings and give them a score like scipy cosine similarity for comparing arrays?

Question

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 ?

Answer 1

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)

Answer 2

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.