パート3.部分文字列の繰り返し
既に述べたように、サイトをスパムから保護する非視覚的な方法ではテキスト分析が使用されます。 最も一般的なスパム信号の1つは、重複行の存在です。 いつものように、上記の例はCleanTalkの実際のデータから取られています。
このような繰り返しの検索は、リソースを最小限に抑える必要があります。 記事の1部と2部からのテストの後に呼び出され、明示的なスパムを除外し、テキストを分析に適した形式にするとよいでしょう。 ここでは、いくつかの統計情報とサンプルコードを示します。
1.コード例
最も長い繰り返し部分文字列を決定するために使用する関数は、 http：//algolist.manual.ru/search/lrs/naive.phpで説明されている単純なアルゴリズムを使用して作成されます。
出力の例を以下に示します。
s a l e f o r s a l e f o r s a l e
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
s 0 + . . . . . . . . + . . . . . . . . + . . .
a 1 . + . . . . . . . . + . . . . . . . . + . .
l 2 . . + . . . . . . . . + . . . . . . . . + .
e 3 . . . + . . . . . . . . + . . . . . . . . +
4 . . . . + . . . + . . . . + . . . + . . . .
f 5 . . . . . + . . . . . . . . + . . . . . . .
o 6 . . . . . . + . . . . . . . . + . . . . . .
r 7 . . . . . . . + . . . . . . . . + . . . . .
8 . . . . . . . . + . . . . + . . . + . . . .
s 9 . . . . . . . . . + . . . . . . . . + . . .
a 10 . . . . . . . . . . + . . . . . . . . + . .
l 11 . . . . . . . . . . . + . . . . . . . . + .
e 12 . . . . . . . . . . . . + . . . . . . . . +
13 . . . . . . . . . . . . . + . . . + . . . .
f 14 . . . . . . . . . . . . . . + . . . . . . .
o 15 . . . . . . . . . . . . . . . + . . . . . .
r 16 . . . . . . . . . . . . . . . . + . . . . .
17 . . . . . . . . . . . . . . . . . + . . . .
s 18 . . . . . . . . . . . . . . . . . . + . . .
a 19 . . . . . . . . . . . . . . . . . . . + . .
l 20 . . . . . . . . . . . . . . . . . . . . + .
e 21 . . . . . . . . . . . . . . . . . . . . . +
$VAR1 = {
'sale' => 3,
'for sale' => 2
};
対角線のプラスは、見つかった繰り返しを示します。 繰り返しの数は、主なものに平行で、同じ垂直方向の変位を持つ隣接するプラスからの対角線のセグメントの数に等しいことがわかります。
アルゴリズムの実装では、重複文字の実際の検索には少し時間がかかります。 部分文字列を選択してマトリックスの対角線を分析することにより、さらに時間がかかります。 これを行うために、最小繰り返し長のしきい値が導入されました。 また、スペースで始まる繰り返しを考慮する必要がありました。 繰り返しが重複しないようにすることも必要でした。 繰り返しの検索は短いものから長いものまで行われます。
そして、最小限の変更を加えたPerlの関数自体を次に示します。 便宜上、全文が表示され、上記のマトリックスが表示されます。
#!/usr/bin/perl -w use strict; use utf8; use Data::Dumper; binmode(STDOUT, ':utf8'); my $min_longest_repeat_length = 4; my $message = 'sale for sale for sale'; my %longest_repeates = (); get_longest_repeates(\$message, \%longest_repeates); print Dumper(\%longest_repeates); sub get_longest_repeates { my $test_ref = shift; # my $reps_ref = shift; # my @symbols = split //, $$test_ref; my $m_len = scalar @symbols; my @matrix = (); # # for (my $i = 0; $i < $m_len; $i++) { # $matrix[$i] = []; for (my $j = $i; $j < $m_len; $j++) { # $matrix[$i][$j] = 1 if $symbols[$i] eq $symbols[$j]; } } # my %repeats_tmp = (); # my ($i, $j); # , .. for ($i = $m_len - 1; $i > 0; $i--) { my $repeat = ''; my $repeat_pos = undef; my $repeat_temp; for ($j = $i; $j < $m_len; $j++) { if (defined($matrix[$j-$i][$j]) && $matrix[$j-$i][$j] == 1) { $repeat_temp = $repeat; $repeat_temp =~ s/^ //; # if (defined($repeats_tmp{$repeat_temp})) { $repeat_pos = $j - length($repeat_temp); $repeats_tmp{$repeat_temp}{$repeat_pos} = 1; $repeat = $symbols[$j]; } else { $repeat .= $symbols[$j]; } } else { if ($repeat ne '') { $repeat =~ s/^ //; $repeat_pos = $j - length($repeat); if (length($repeat) >= $min_longest_repeat_length) { if (defined($repeats_tmp{$repeat})) { $repeats_tmp{$repeat}{$repeat_pos} = 1; } else { $repeats_tmp{$repeat} = {$repeat_pos => 1}; } } $repeat = ''; } } } if ($repeat ne '') { $repeat =~ s/^ //; $repeat_pos = $j - length($repeat); if (length($repeat) >= $min_longest_repeat_length) { if (defined($repeats_tmp{$repeat})) { $repeats_tmp{$repeat}{$repeat_pos} = 1; } else { $repeats_tmp{$repeat} = {$repeat_pos => 1}; } } $repeat = ''; } } foreach (keys %repeats_tmp){ $$reps_ref{$_} = 1 + scalar keys %{$repeats_tmp{$_}}; } # print "\n"; print ' '; for (my $i = 0; $i < $m_len; $i++) { print ' ' . $symbols[$i]; } print "\n"; print ' '; for (my $i = 0; $i < $m_len; $i++) { printf '%3d', $i; } print "\n"; print "\n"; for (my $i = 0; $i < $m_len; $i++) { print $symbols[$i]; printf '%3d ', $i; for (my $j = 0; $j < $m_len; $j++) { my $value = '.'; $value = '+' if (defined $matrix[$i][$j] && $matrix[$i][$j] == 1); printf(' %1s', $value); } print "\n"; } print "\n"; }
2.繰り返し統計
繰り返しの最小長のしきい値を選択しました（具体的には示しません）。これにより、テストの効率が最大になりました。 繰り返し回数に関する結果は次のとおりです。
| 繰り返し回数 | スパムでは、％ | スパムなし、％ |
|---|---|---|
| 2 | 78.58 | 90.28 |
| 3 | 11.93 | 4.86 |
| 4 | 4.45 | 2.08 |
| 5 | 2,30 | 1.39 |
| 6 | 1.93 | 0 |
| 7 | 0.22 | 0 |
| 8 | 0.37 | 0 |
| 9 | 0,07 | 0 |
3.結論
テキスト内の重複部分文字列を見つけるための単純なアルゴリズムの実装を示しました。 分析には、繰り返しの数と繰り返し自体の両方を使用できます（たとえば、ストップワードによる）。 繰り返しますが、スパムとの戦いでは、複雑なテストが最も効果的です。