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

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

Часть 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

$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. Статистика повторов

Нами был подобран порог минимальной длины повтора (его я не привожу специально), давший максимальную эффективность в тестах. Его результаты по числу повторов таковы:

3. Заключение

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

Автор: CleanTalk Anti-Spam

Источник