8

I'm looking for an algorithm or even an algorithm space that deals with the problem of validating that short text (email) matches known templates. Coding will probably be python or perl, but that's flexible.

Here's the problem:

Servers with access to production data need to be able to send out email that will reach the Internet:

Dear John Smith,

We received your last payment for $123.45 on 2/4/13. We'd like you to be aware of the following charges:
      $12.34 Spuznitz, LLC on 4/1
      $43.21 1-800-FLOWERS on 4/2
As always, you can view these transactions in our portal. 
Thank you for your business!

Obviously some of the email contents will vary - the salutation ("John Smith"), "$123.45 on 2/4/13", and the lines with transactions printed out. Other parts ("We received your last payment") are very static. I want to be able to match the static portions of the text and quantify that the dynamic portions are within certain reasonable limits (I might know that the most transaction lines to be printed is 5, for example).

Because I am concerned about data exfiltration, I want to make sure email that doesn't match this template never goes out - I want to examine email and quarantine anything that doesn't look like what I expect. So I need to automate this template matching and block any email messages that are far enough away from matching.

So the question is, where do I look for a filtering mechanism? Bayesian filtering tries to verify a sufficient similarity between a specific message and a non-specific corpus, which is kind of the opposite problem. Things like Perl's Template module are a tight match - but for output, not for input or comparison. Simple 'diff' type comparisons won't handle the limited dynamic info very well.

How do I test to see if these outgoing email messages "quack like a duck"?

3
  • 3
    What's wrong with just matching with regexp?
    – boxed
    Feb 15, 2013 at 13:00
  • You could find the longest common subsequence between the email to very and the template (or even between the email to verify and another email). The result should be the same or nearly the same for all emails. Bonus: It will find exactly what parts you need to examine if you quarantine the email.
    – ikegami
    Feb 17, 2013 at 10:45
  • Use a grammar-based parser generator.
    – Apalala
    Feb 18, 2013 at 13:22

3 Answers 3

4
+100

You could use grammars for a tight matching. It is possible to organize regexps in grammars for easier abstraction: http://www.effectiveperlprogramming.com/blog/1479

Or you could use a dedicated grammar engine Marpa.

If you want a more statistic approach, consider n-grams. First, tokenize text and replace variable chunks by meaningful placeholders, like CURRENCY and DATE. Then, build the n-grams. Now you can use Jaccard index to compare two texts.

Here is a Pure-Perl implementation which works on trigrams:

#!/usr/bin/env perl
use strict;
use utf8;
use warnings;

my $ngram1 = ngram(3, tokenize(<<'TEXT1'));
Dear John Smith,

We received your last payment for $123.45 on 2/4/13. We'd like you to be aware of the following charges:
      $12.34 Spuznitz, LLC on 4/1
      $43.21 1-800-FLOWERS on 4/2
As always, you can view these transactions in our portal. 
Thank you for your business!
TEXT1

my $ngram2 = ngram(3, tokenize(<<'TEXT2'));
Dear Sally Bates,

We received your last payment for $456.78 on 6/9/12. We'd like you to be aware of the following charges:
      $123,43 Gnomovision on 10/1
As always, you can view these transactions in our portal. 
Thank you for your business!
TEXT2

my %intersection =
    map { exists $ngram1->[2]{$_} ? ($_ => 1) : () }
    keys %{$ngram2->[2]};
my %union =
    map { $_ => 1 }
    keys %{$ngram1->[2]}, keys %{$ngram2->[2]};

printf "Jaccard similarity coefficient: %0.3f\n", keys(%intersection) / keys(%union);

sub tokenize {
    my @words = split m{\s+}x, lc shift;

    for (@words) {
        s{\d{1,2}/\d{1,2}(?:/\d{2,4})?}{ DATE }gx;
        s{\d+(?:\,\d{3})*\.\d{1,2}}{ FLOAT }gx;
        s{\d+}{ INTEGER }gx;
        s{\$\s(?:FLOAT|INTEGER)\s}{ CURRENCY }gx;
        s{^\W+|\W+$}{}gx;
    }

    return @words;
}

sub ngram {
    my ($size, @words) = @_;
    --$size;

    my $ngram = [];
    for (my $j = 0; $j <= $#words; $j++) {
        my $k = $j + $size <= $#words ? $j + $size : $#words;
        for (my $l = $j; $l <= $k; $l++) {
            my @buf;
            for my $w (@words[$j..$l]) {
                push @buf, $w;
            }
            ++$ngram->[$#buf]{join(' ', @buf)};
        }
    }

    return $ngram;
}

You can use one text as a template and match it against your emails. Check String::Trigram for an efficient implementation. Google Ngram Viewer is a nice resource to illustrate the n-gram matching.

3
  • Thank you, good answer - not because it provided me with the One True Answer, but it helped me understand the solution space better so I can tinker.
    – gowenfawr
    Feb 19, 2013 at 22:41
  • You're welcome :) There's no one-size-fit-all answers for natural language processing anyway, even the simpler tasks require some tinkering.
    – creaktive
    Feb 19, 2013 at 23:12
  • @gowenfawr, I've just discovered the Template::Extract module. Suddenly, it reminded me of LAPIS, a Lightweight Structured Text Processing DSL.
    – creaktive
    Mar 8, 2013 at 13:49
3

If you want to match a pre-existing template with e.g. control flow elements like {% for x in y %} against a supposed output from it, you're going to have to parse the template language - which seems like a lot of work.

On the other hand, if you're prepared to write a second template for validation purposes - something like:

Dear {{customer}},

We received your last payment for {{currency}} on {{full-date}}\. We'd like you to be aware of the following charges:
(      {{currency}} {{supplier}} on {{short-date}}
){,5}As always, you can view these transactions in our portal\. 

... which is just a simple extension of regex syntax, it's pretty straightforward to hack something together that will validate against that:

import re

FIELDS = {
    "customer": r"[\w\s\.-]{,50}",
    "supplier": r"[\w\s\.,-]{,30}",
    "currency": r"[$€£]\d+\.\d{2}",
    "short-date": r"\d{,2}/\d{,2}",
    "full-date": r"\d{,2}/\d{,2}/\d{2}",
}

def validate(example, template_file):
    with open(template_file) as f:
        template = f.read()
    for tag, pattern in FIELDS.items():
        template = template.replace("{{%s}}" % tag, pattern)
    valid = re.compile(template + "$")
    return (re.match(valid, example) is not None)

The example above isn't the greatest Python code of all time by any means, but it's enough to get the general idea across.

3
  • 1
    I'm not a Python expert, but it seems that there is a library for grammar-based parsing which could be helpful: pyparsing
    – creaktive
    Feb 17, 2013 at 16:52
  • 1
    @creaktive I think grammar-based parsing is overkill for this problem ... but to each their own :-) Feb 18, 2013 at 16:58
  • However, you actually did implemented a simple grammar, from scratch ;)
    – creaktive
    Feb 18, 2013 at 18:03
2

I would go for the "longest common subsequence". A standard implementation can be found here:

http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_subsequence

If you need a better algorithm and/or lots of additional ideas for inexact matching of strings, THE standard reference is this book:

http://www.amazon.com/Algorithms-Strings-Trees-Sequences-Computational/dp/0521585198

Don't be fooled by the title. Compuatational biology is mostly about matching of large database of long strings (also known as DNA sequences).

3
  • Did you mean Longest Common Substring? Because subsequence is NP-hard, which means that it should be used very, very carefully on batch tasks!
    – creaktive
    Feb 18, 2013 at 19:32
  • Why do you think LCS is NP hard? Wikipedia lists P time algorithms for it that are even better than O(n^2) (n=length of the longer sequence).
    – Udo Klein
    Sep 28, 2015 at 9:26
  • I was referring to Longest Common Subsequence. Longest Common Substring is OK, indeed.
    – creaktive
    Sep 29, 2015 at 20:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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