Невізуальні методи захисту сайту від спаму. Частина 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
 

 
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 = 'for sale 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. Висновок
Я показав реалізацію наївного алгоритму пошуку повторюваних підрядків у тексті. Для аналізу можна використовувати як число повторів, так і самі повтори (наприклад, по стоп-слів). Повторю, що в боротьбі зі спамом найбільш ефективні комплексні тести.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.