8

短いテキスト（電子メール）が既知のテンプレートと一致することを検証する問題を処理するアルゴリズムまたはアルゴリズムスペースを探しています。コーディングはおそらくpythonまたはperlですが、それは柔軟です。

ここに問題があります：

本番データにアクセスできるサーバーは、インターネットに到達する電子メールを送信できる必要があります。

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!

明らかに、電子メールの内容の一部は異なります-敬礼（「ジョン・スミス」）、「2013年2月4日の$ 123.45」、およびトランザクションの行が印刷されます。他の部分（「最後の支払いを受け取りました」）は非常に静的です。テキストの静的な部分を一致させ、動的な部分が特定の妥当な制限内にあることを定量化できるようにしたい（たとえば、印刷されるトランザクション行のほとんどが5であることを知っているかもしれません）。

データの漏えいが心配なので、このテンプレートと一致しない電子メールが送信されないようにしたいのです。電子メールを調べて、期待したものとは異なるものを隔離したいと思います。したがって、このテンプレートマッチングを自動化し、マッチングから十分に離れている電子メールメッセージをブロックする必要があります。

だから問題は、どこでフィルタリングメカニズムを探すのかということです。ベイジアンフィルタリングは、特定のメッセージと非特定のコーパスの間の十分な類似性を検証しようとします。これは、逆の問題の一種です。Perlのテンプレートモジュールのようなものは厳密に一致していますが、入力や比較ではなく、出力用です。単純な「diff」タイプの比較では、制限された動的情報をうまく処理できません。

これらの送信メールメッセージが「アヒルのように震える」かどうかを確認するにはどうすればよいですか？

4

3 に答える 3

4

厳密に一致させるために文法を使用できます。抽象化を容易にするために、正規表現を文法で整理することができます： http ://www.effectiveperlprogramming.com/blog/1479

または、専用の文法エンジンMarpaを使用することもできます。

より統計的なアプローチが必要な場合は、n-gramを検討してください。CURRENCYまず、テキストをトークン化し、変数チャンクをやなどの意味のあるプレースホルダーに置き換えますDATE。次に、n-gramを作成します。これで、 Jaccardインデックスを使用して2つのテキストを比較できます。

トリグラムで機能する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;
}

1つのテキストをテンプレートとして使用し、それをメールと照合することができます。効率的な実装については、 String::Trigramを確認してください。Google Ngram Viewerは、 n-gramマッチングを説明するための優れたリソースです。

于 2013-02-17T16:48:53.470 に答える
3

既存のテンプレートを、たとえばそのテンプレート{% for x in y %}からの想定される出力に対して制御フロー要素と照合する場合は、テンプレート言語を解析する必要があります。これは大変な作業のようです。

一方、検証のために2番目のテンプレートを作成する準備ができている場合は、次のようになります。

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 に答える