Продолжение статьи Невизуальные методы защиты сайта от спама

Часть 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. Заключение

Я показал реализацию наивного алгоритма поиска повторяющихся подстрок в тексте. Для анализа можно использовать как число повторов, так и сами повторы (например, по стоп-словам). Повторю, что в борьбе со спамом наиболее эффективны комплексные тесты.