14
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – It's a trap Feb 10 '18 at 5:24
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If you feel that seq.ratio() is slow, you can use seq.quick_ratio() $\endgroup$ – Nabin Aug 18 at 3:22
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (+1) for the Lev. distance metric. nltk comes with a ready-made implementation. Cosine similarity isn't a good string-similarity measure IMHO :) $\endgroup$ – Dawny33 Jul 4 '16 at 8:29
  • $\begingroup$ 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 $\endgroup$ – Jan van der Vegt Jul 4 '16 at 11:48
  • 1
    $\begingroup$ @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. $\endgroup$ – Mohit Motwani Jul 1 at 13:44
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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