8

我正在寻找一种算法，甚至是一种算法空间来处理验证短文本（电子邮件）与已知模板匹配的问题。编码可能是 python 或 perl，但这很灵活。

这是问题所在：

有权访问生产数据的服务器需要能够发送将到达 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!

显然，某些电子邮件内容会有所不同——称呼（“John Smith”）、“2/4/13 上的 $123.45”以及打印出交易的行。其他部分（“我们收到了您的最后一笔付款”）非常静态。我希望能够匹配文本的静态部分并量化动态部分是否在某些合理的范围内（例如，我可能知道要打印的最多交易行是 5 行）。

因为我担心数据泄露，所以我想确保与此模板不匹配的电子邮件永远不会消失 - 我想检查电子邮件并隔离任何与我预期不符的邮件。所以我需要自动化这个模板匹配并阻止任何离匹配足够远的电子邮件。

所以问题是，我在哪里寻找过滤机制？贝叶斯过滤试图验证特定消息和非特定语料库之间的足够相似性，这是一种相反的问题。Perl 的 Template 模块之类的东西非常匹配——但用于输出，而不是用于输入或比较。简单的“差异”类型比较不能很好地处理有限的动态信息。

我如何测试这些传出的电子邮件是否“像鸭子一样嘎嘎”？

4

3 回答 3

4

您可以使用语法进行紧密匹配。可以在语法中组织正则表达式以便于抽象：http ://www.effectiveperlprogramming.com/blog/1479

或者您可以使用专用的语法引擎Marpa。

如果您想要更统计的方法，请考虑n-grams。首先，标记文本并用有意义的占位符替换变量块，比如CURRENCYand DATE。然后，构建n-gram。现在您可以使用Jaccard 索引来比较两个文本。

这是一个适用于三元组的 Pure-Perl 实现：

#!/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;
}

您可以使用一个文本作为模板并将其与您的电子邮件相匹配。检查String::Trigram以获得有效的实现。Google Ngram Viewer是一个很好的资源来说明n-gram匹配。

于 2013-02-17T16:48:53.470 回答
3

如果您想将预先存在的模板与例如控制流元素（例如{% for x in y %}从它的假定输出）匹配，您将不得不解析模板语言 - 这似乎需要做很多工作。

另一方面，如果您准备为验证目的编写第二个模板 - 例如：

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\.

...这只是正则表达式语法的简单扩展，将一些东西组合在一起非常简单，可以验证：

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)

无论如何，上面的示例都不是有史以来最伟大的 Python 代码，但它足以让您了解总体思路。

于 2013-02-15T17:25:36.763 回答
2

我会选择“最长的公共子序列”。可以在此处找到标准实现：

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

如果您需要更好的算法和/或更多关于字符串不精确匹配的其他想法，标准参考书是这本书：

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

不要被标题所迷惑。计算生物学主要是关于长字符串（也称为 DNA 序列）的大型数据库的匹配。

于 2013-02-18T18:44:36.363 回答