Similarity between two words

I'm looking for a Python library that helps me identify the similarity between two words or sentences.

I will be doing Audio to Text conversion which will result in an English dictionary or non dictionary word(s) ( This could be a Person or Company name) After that, I need to compare it to a known word or words.

Example:

1) Text to audio result: Thanks for calling America Expansion will be compared to American Express.

Both sentences are somehow similar but not the same.

Looks like I may need to look into how many chars they share. Any ideas will be great. Looks a functionality like Google search "did you mean" feature.

The closest would be like Jan has mentioned inhis answer, the Levenstein's distance (also popularly called the edit distance).

In information theory 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 (i.e. insertions, deletions or substitutions) required to change one word into the other.

It is a very commonly used metric for identifying similar words. Nltk already has an implementation for the edit distance metric, which can be invoked in the following way:

import nltk
nltk.edit_distance("humpty", "dumpty")


The above code would return 1, as only one letter is different between the two words.

• Lavenshtien's distance is the worst algorithm that you can use if NLP is what you intend to do. If 2 synonyms have a different character set, LD will perform very poorly in those cases. – It's a trap Feb 10 '18 at 5:24

Apart from very good responses here, you may try SequenceMatcher in difflib python library.

https://docs.python.org/2/library/difflib.html

import difflib

a = 'Thanks for calling America Expansion'
b = 'Thanks for calling American Express'

seq = difflib.SequenceMatcher(None,a,b)
d = seq.ratio()*100
print(d)
### OUTPUT: 87.323943


Now Consider the below code:

a = 'Thanks for calling American Expansion'
b = 'Thanks for calling American Express'

seq = difflib.SequenceMatcher(None,a,b)
d = seq.ratio()*100
print(d)
### OUTPUT: 88.88888


Now you may compare the d value to evaluate the similarity.

• If you feel that seq.ratio() is slow, you can use seq.quick_ratio() – Nabin Aug 18 '19 at 3:22

If your dictionary is not too big a common approach is to take the Levenshtein distance, which basically counts how many changes you have to make to get from one word to another. Changes include changing a character, removing a character or adding a character. An example from Wikipedia:

lev(kitten, sitting) = 3

• k itten -> s itten
• sitt e n -> sitt i n
• sittin -> sittin g

Here are some Python implements on Wikibooks.

The algorithm to compute these distances is not cheap however. If you need to do this on a big scale there are ways to use cosine similarity on bi-gram vectors that are a lot faster and easy to distribute if you need to find matches for a lot of words at once. They are however only an approximation to this distance.

• (+1) for the Lev. distance metric. nltk comes with a ready-made implementation. Cosine similarity isn't a good string-similarity measure IMHO :) – Dawny33 Jul 4 '16 at 8:29
• I agree that it's much worse than the Levenshtein distance but if you need fuzzy matching between 2 datasets of millions it can actually do that in a reasonable time due to needing some tricks plus matrix multiplication – Jan van der Vegt Jul 4 '16 at 11:48
• @Dawny33 I would disagree. Not only has cosine similarity worked very quick for me but also very accurately given that the right n-gram was used. – Mohit Motwani Jul 1 '19 at 13:44

An old and well-known technique for comparison is the Soundex algorithm. The idea is to compare not the words themselves but approximations of how they are pronounced. To what extent this actually improves the quality of the results I don't know.

However it feels a bit strange to apply something like Soundex to results from a speech-to-text recognition engine. First you throw away information about how the words are pronounced, then you try to add it back again. It would be better to combine these two phases.

Hence, I expect the state of the art technology in this area to do that, and be some form of adaptive classification, e.g. based on neural networks. Google does return recent research on Speech Recognition with Neural Networks.

I think the function get_close_matches in module difflib could be more suitable for such a requirement.

get_close_matches(word, possibilities, n=3, cutoff=0.7)

possibilities -> is the list of words
n = maximum number of close matches
cutoff = accuracy of matches.

data=["drain","rain","brain","stackexchange"]

word="rainnn"

if len(get_close_matches(w, data,  n=3, cutoff=0.7)) > 0:
return data[get_close_matches(w, data,  n=3, cutoff=0.7)[0]]


This piece of code will return the best first match and that will be word rain.

You can featurize both sentences and then look at cosine similarity between their feature representations.

To featurize text, there are many methods you can use; from simple counting-based operators like TFIDF to word embeddings like word2vec or more complex language models like BERT.

The TextWiser Library might come in handy if you want to experiment with several text featurization methods including their transformations for dimensionality reduction like SVD, LDA, UMAP etc.

Here is a usage example:


# Conceptually, TextWiser is composed of an Embedding, potentially with a pretrained model,
# that can be chained into zero or more Transformations
from textwiser import TextWiser, Embedding, Transformation, WordOptions, PoolOptions

# Data
documents = ["Some document", "More documents. Including multi-sentence documents."]

# Model: TFIDF min_df parameter gets passed to sklearn automatically
emb = TextWiser(Embedding.TfIdf(min_df=1))

# Model: TFIDF followed with an NMF + SVD
emb = TextWiser(Embedding.TfIdf(min_df=1), [Transformation.NMF(n_components=30), Transformation.SVD(n_components=10)])

# Model: Word2Vec with no pretraining that learns from the input data
emb = TextWiser(Embedding.Word(word_option=WordOptions.word2vec, pretrained=None), Transformation.Pool(pool_option=PoolOptions.min))

# Model: BERT with the pretrained bert-base-uncased embedding
emb = TextWiser(Embedding.Word(word_option=WordOptions.bert), Transformation.Pool(pool_option=PoolOptions.first))

# Features
vecs = emb.fit_transform(documents)


You can easily switch between different Embedding and Transformation options and see how they impact your downstream tasks, in your case, the similarity between the sentences.

Notice you can even chain the Transformations; e.g., NMF followed by SVD operation.

Disclaimer: I am a member of the TextWiser team.

• It seems to me that the question is about similarity in audio, not similarity in meaning. Don't you think so? – Amit Keinan Apr 8 at 17:18
• You're absolutely correct! This was to complement the answer from the other direction. – skadio Apr 8 at 20:38