3
\$\begingroup\$

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:

  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?

\$\endgroup\$
  • \$\begingroup\$ if you need to compare everything to everything else it will be by definition O(n^2). \$\endgroup\$ – Ev. Kounis Nov 16 '17 at 16:21
  • \$\begingroup\$ @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. \$\endgroup\$ – tyteen4a03 Nov 16 '17 at 16:24
  • \$\begingroup\$ didn't exactly get how the grouping is done. Are the groups pre-defined or are they defined at runtime based on the messages? \$\endgroup\$ – Ev. Kounis Nov 16 '17 at 16:28
  • \$\begingroup\$ 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. \$\endgroup\$ – tyteen4a03 Nov 16 '17 at 16:29
  • \$\begingroup\$ 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 \$\endgroup\$ – Ev. Kounis Nov 16 '17 at 16:41

Your Answer

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

Browse other questions tagged or ask your own question.