Продолжение статьи Невизуальные методы защиты сайта от спама
Как уже говорилось, невизуальные методы защиты сайта от спама используют анализ текста. Один из часто встречающихся сигналов спама — это наличие повторяющихся строк. Как всегда, приведённые примеры взяты из реальных данных компании CleanTalk.
Поиск таких повторов должен быть минимально ресурсоёмким. Лучше, если он будет вызываться после тестов из 1 и 2 частей статьи, которые отсеют явный спам и приведут текст к виду, пригодному для анализа. Здесь я приведу некоторую статистику, а также пример кода.
Используемая нами функция определения самых длинных повторяющихся подстрок сделана по наивному алгоритму, описанному тут http://algolist.manual.ru/search/lrs/naive.php
Пример вывода представлен ниже.
Плюсами на диагоналях отмечены найденные повторы. Видно, что число повторов равно числу отрезков диагоналей из смежных плюсов, параллельных главной и имеющих одинаковое смещение по вертикали.
В реализации алгоритма собственно поиск повторяющихся символов занимает немного. Больше времени делается именно анализ диагоналей матрицы с выделением подстрок. Для этого был введен порог минимальной длины повтора. Также пришлось учесть повторы, начинающиеся с пробелов. Необходимо также было обеспечить, чтобы повторения не пересекались между собой. Поиск повторов делается от коротких к длинным.
А вот и сама функция на Perl с минимальными изменениями. Для удобства приведён полный текст, выводящий матрицу выше.
Нами был подобран порог минимальной длины повтора (его я не привожу специально), давший максимальную эффективность в тестах. Его результаты по числу повторов таковы:
Я показал реализацию наивного алгоритма поиска повторяющихся подстрок в тексте. Для анализа можно использовать как число повторов, так и сами повторы (например, по стоп-словам). Повторю, что в борьбе со спамом наиболее эффективны комплексные тесты.
Часть 3. Повторы подстрок
Как уже говорилось, невизуальные методы защиты сайта от спама используют анализ текста. Один из часто встречающихся сигналов спама — это наличие повторяющихся строк. Как всегда, приведённые примеры взяты из реальных данных компании 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. Заключение
Я показал реализацию наивного алгоритма поиска повторяющихся подстрок в тексте. Для анализа можно использовать как число повторов, так и сами повторы (например, по стоп-словам). Повторю, что в борьбе со спамом наиболее эффективны комплексные тесты.
Поделиться с друзьями
Loki3000
Что-то я не понял. Согласно алгоритму, у строки
повторяемость будет такая же, как у строки
znaeff
Такая строка будет только на главной диагонали. А алгоритм саму главную диагональ не проверяет:
for ($i = $m_len - 1; $i > 0; $i--) {
Если бы было $i >= 0, то проверял бы.