# Message classification with Levenshtein Distance

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:
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:

1. Discarding messages that are too short
2. Only run Levenshtein distance if the string's lengths are similar (I use python-Levenshtein which is written in C)
3. Making cats an 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?

• if you need to compare everything to everything else it will be by definition O(n^2). – Ma0 Nov 16 '17 at 16:21
• @Ev.Kounis I'm aware - I'm asking whether there are any early exit possibilities I'm missing in my code that could help speed up the script. – tyteen4a03 Nov 16 '17 at 16:24
• didn't exactly get how the grouping is done. Are the groups pre-defined or are they defined at runtime based on the messages? – Ma0 Nov 16 '17 at 16:28
• Defined at run-time. If a message doesn't exist in cats already it is added; subsequent messages are grouped based on what exists in cats. – tyteen4a03 Nov 16 '17 at 16:29
• but then the order in which the messages is processed plays a role in the outcome. Different order results in a different group "definitions". Like semi-deterministic – Ma0 Nov 16 '17 at 16:41