I have a Python script that classifies messages. Each message carries a score, which is tallied up later in the script. It looks for messages that look alike, and puts them into a category.
items =  cats = collections.OrderedDict() # Do some preparation with the messages punctuation_re = re.compile(r"([^\w\s.])") multiple_spaces_re = re.compile(r"\s+") # Load the messages from the CSV with open('sentences.csv', encoding='utf-8') as f: reader = csv.DictReader(f, fieldnames=["message", "score"]) for row in reader: match_desc = re.sub('(\s+)(a|an|and|the|is|are|or|to|on|under|in|about|at|have|had|was|were)(\s+)', '\1', match_desc) match_desc = re.sub(punctuation_re, "", match_desc) match_desc = re.sub(multiple_spaces_re, " ", match_desc) row["match_desc"] = match_desc.strip().lower() items.append(row) # Match the items for item in sorted(items, key=lambda x: len(x["match_desc"])): hasMatch = False if len(item["match_desc"]) <= 5: # Don't bother continue elif len(item["match_desc"]) > 15: # If the string is longer than 15 characters, use Levenshtein distance for k, v in reversed(cats.items()): # If string length difference is greater than maximum Levinshtein distance allowed, skip if (abs(len(item["match_desc"]) - len(k)) > math.ceil(len(item["match_desc"]) * 0.2)): continue # Else compute the Levenshtein distance if item["match_desc"] == k or Levenshtein.distance(item["match_desc"], k) < math.ceil(len(item["match_desc"]) * 0.2): cats[k].append(item) hasMatch = True break else: # Use exact match if item["match_desc"] in cats.keys(): # Exact match cats[item["match_desc"]].append(item) continue if not hasMatch: cats[item["match_desc"]] = [item]
The problem is this script is \$O(n^2)\$, and struggles with large datasets as the script will need to go through more items to find a match. For example, a 70000-message dataset with varying lengths of messages takes 20 minutes on my machine (Python 3.6.3).
Some speedups I've included are:
- Discarding messages that are too short
- Only run Levenshtein distance if the string's lengths are similar (I use python-Levenshtein which is written in C)
OrderedDict()and reversing it so that it's more likely to exit early (as the list of messages is sorted, it's more likely to find a match looking at what's recently inserted)
Are there any avenues of speedups possible that I'm missing?