High performance fuzzy string comparison in Python, use Levenshtein or difflib [closed]

by

In case you’re interested in a quick visual comparison of Levenshtein and Difflib similarity, I calculated both for ~2.3 million book titles:

import codecs, difflib, Levenshtein, distance

with codecs.open("titles.tsv","r","utf-8") as f:
    title_list = f.read().split("\n")[:-1]

    for row in title_list:

        sr      = row.lower().split("\t")

        diffl   = difflib.SequenceMatcher(None, sr[3], sr[4]).ratio()
        lev     = Levenshtein.ratio(sr[3], sr[4]) 
        sor     = 1 - distance.sorensen(sr[3], sr[4])
        jac     = 1 - distance.jaccard(sr[3], sr[4])

        print diffl, lev, sor, jac

I then plotted the results with R:

enter image description here

Strictly for the curious, I also compared the Difflib, Levenshtein, Sørensen, and Jaccard similarity values:

library(ggplot2)
require(GGally)

difflib <- read.table("similarity_measures.txt", sep = " ")
colnames(difflib) <- c("difflib", "levenshtein", "sorensen", "jaccard")

ggpairs(difflib)

Result:
enter image description here

The Difflib / Levenshtein similarity really is quite interesting.

2018 edit: If you’re working on identifying similar strings, you could also check out minhashing–there’s a great overview here. Minhashing is amazing at finding similarities in large text collections in linear time. My lab put together an app that detects and visualizes text reuse using minhashing here: https://github.com/YaleDHLab/intertext

More Related Contents:

  1. Efficient string matching in Apache Spark
  2. Comparing two .txt files using difflib in Python
  3. Regex for existence of some words whose order doesn’t matter
  4. Check if string matches pattern
  5. String similarity metrics in Python [duplicate]
  6. Search for string allowing for one mismatch in any location of the string
  7. Remove ends of string entries in pandas DataFrame column
  8. python – regex search and findall
  9. Rewrite multiple lines in the console
  10. df.append() is not appending to the DataFrame
  11. seaborn is not plotting within defined subplots
  12. CMD opens Windows Store when I type ‘python’
  13. Cannot return results from stored procedure using Python cursor
  14. Example of the right way to use QThread in PyQt?
  15. How can I use a conditional expression (expression with if and else) in a list comprehension? [duplicate]
  16. Write dictionary of lists to a CSV file
  17. django.db.utils.OperationalError Could not connect to server
  18. Is there an easy way to make sessions timeout in flask?
  19. Version number comparison in Python
  20. Count occurrences of each of certain words in pandas dataframe
  21. Python3 correct way to import relative or absolute?
  22. Python/Pandas convert string to time only
  23. Transparency for Poly3DCollection plot in matplotlib
  24. How can we use Selenium Webdriver in colab.research.google.com?
  25. Relations on composite keys using sqlalchemy
  26. Python string.join(list) on object array rather than string array
  27. How do I get the weights of a layer in Keras?
  28. Is there a way of drawing a caption box in matplotlib
  29. Using a comparator function to sort
  30. How can I process command line arguments in Python? [duplicate]

Leave a Comment