«

»

mar 08

Un semplice generatore di spam con le catene di Markov

Oggi pomeriggio ho fatto una cosa che non facevo da un pò di tempo: Dedicarmi alla Toy-programming ,scrivere un codice assolutamente inutile giusto per il gusto di farlo.

Il codice che ho scritto è un generatore di spam che permette di generare un testo apparentemente sensato a partire da un testo sensato preso come modello senza fare nessun tipo di analisi della sintassi.

Per fare questo ho scritto un algoritmo che sfrutta le catene di Markov.

L’idea è quella di dividere le singole frasi in due parti: un prefisso formato da un numero costante di parole e un suffisso formato da una singola parola.
L’algoritmo costruisce un testo associando a ogni prefisso un suffisso scelto in maniera casuale tra i suffissi che seguono quel prefisso nel testo originale.

La probabilità di estrazione di un suffisso dipende dal numero di occorrenze di quella coppia prefisso-suffisso nel testo originale.

La profondità del prefisso influenza la casualità del testo: un numero basso genera molte possibilità di accoppiamento ma un numero alto genera frasi più verosimili, credo che per la lingua italiana la dimensione ideale del prefisso sia 3.

Malgrado sia molto semplice ,molto stupido e assolutamente incapace di analizzare la sintassi un generatore del genere riesce a costruire testi che sembrano sensati e che riescono a passare attraverso molti filtri antispam e addirittura a scalare le classifiche dei motori di ricerca.

A volte quando cerco qualcosa che effettivamente non esiste su Google vado a finire in pagine generate in questo modo e molti dei commenti di spam che riescono a passare attraverso i filtraggi sono spam markoviano.

Per ottenere un risultato verosimile è importante scegliere come modello un testo abbastanza complesso e con parole complicate e ambigue quasi in ogni frase, avrei voluto usare il mio libro di testo di teoria dei segnali ma avrei dovuto passarlo a scanner…quindi ho ripiegato su qualcosa di più semplice: Kant

Dando in pasto all’algoritmo la pedagogia di Kant si ottengono risultati del genere:

Si deve dunque sottoporre i fanciulli si abbiano a trattare come schiavi.  In quanto al rospo, è questo un animale innocuo al pari di una foresta si mantiene diritto, per la distanza, vuoi per la società che si può in certo modo chiamare fisica, bisogna soprattutto curare lo svolgimento della umanità, e far si ch’ella diventi non solo più abile, ma ancora più morale, da ultimo, cosa molto strana che alcuni genitori, dopo aver giudicato con un’occhiata di potervi riuscire senza pericolo. Ma la disciplina consiste semplicemente nello spogliar l’uomo della sua libertà. Fa d’uopo avvezzarsi ai rifiuti, alla resistenza, e va dicendo. La massima tantum scimus quantum memoria tenemus (tanto sappiamo quanto riteniamo a memoria) ha certo la sua ragione l’attira dalla parte opposta. Egli dunque potrebbe divenire moralmente buono o cattivo secondo l’utile proprio. Le massime della. condotta umana vanno desunte dall’uomo stesso. Devesi cercare per tempo a diffidare di questo o di loro stessi.

Ho realizzato un applet che usa questo algoritmo qui

Per migliorare i risultati dell’analisi analizzo solo righe con più di n parole (dove n è dato dalla variabile taglio)

package markov;

import java.io.BufferedReader;
import java.io.IOException;
import java.util.Hashtable;
import java.util.Random;
import java.util.Vector;

/**
 *
 * @author darshan
 */
class Chain {
    int lunghezza;
    int taglio;
    int profondita;
	static final String NONWORD = "\n";// "word" that can't appear
    /**
     * statetab: lista dei suffissi
     * statetab è una hashmap associa ad ogni prefisso (serie di parole) un suffisso (altra serie di parole)
     */
    Hashtable<vector<string>,Vector<string>> statetab ;
	Vector<string> prefix ;
	static Random rand = new Random();

    public Chain(int lunghezza, int profondita,int taglio) {
        this.profondita=profondita;
        this.taglio=taglio;
        this.lunghezza=lunghezza;
        statetab = new Hashtable();
        prefix = generaprefisso(profondita, NONWORD);
    }

    public void analizza(BufferedReader input) throws IOException{
        build(input,taglio);
    }

    public String produci(){
        return generate(lunghezza);
    }

    /**
     * estrae le singole parole dal file e le infila nell hashmap
     * @param in
     * @throws java.io.IOException
     */
    protected void build(BufferedReader in, int taglio) throws IOException
    {
        int nrighe=0;
        String riga;
        String[] parole;
        int n;
        while ((riga = in.readLine()) != null) {
             nrighe++;
             parole= riga.split(" ");
             n=parole.length;
             if(n>taglio)for(int a=0;a<n;a++)add(parole[a]);
        }
        add(NONWORD);
    }

    /**
     * Chain add: add word to suffix list, update prefix
     * @param word
     */
    void add(String word)
    {
        Vector<string> suf = statetab.get(prefix);
        if (suf == null) {
            suf = new Vector();
            statetab.put((Vector)prefix.clone(), suf);
        }
        suf.addElement(word);
        prefix.removeElementAt(0);
        prefix.addElement(word);
    }

    public Vector generaprefisso(int n, String str){
        Vector temp=new Vector();
        for (int i = 0; i < n; i++)
            temp.addElement(str);
        return temp;
    }
    /**
     * Chain generate: generate output words
     * @param nwords
     * @return
     */
    protected String generate(int nwords) throws Error
    {
        StringBuilder output=new StringBuilder("");
        prefix = generaprefisso(profondita, NONWORD);
        for (int i = 0; i < nwords; i++) {
            Vector<string> s = statetab.get(prefix);
            if (s == null) {
                throw new Error("Questo non dovrebbe succedere!");
            }
            int r = rand.nextInt(s.size());
            String suf = s.elementAt(r);
            if (suf.equals(NONWORD))
                break;
            output.append(" "+suf);
            prefix.removeElementAt(0);
            prefix.addElement(suf);
        }
        return output.toString();
    }
}

Il codice del main è molto semplice

package markov;

import java.io.BufferedReader;
import java.io.FileReader;

/**
 *
 * @author darshan
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws Exception {
        String nomefile="/home/darshan/Codice/markovspammer/pedagogia.txt";
        int parole=250;
        int profondita=2;
        int taglio=3;
        if(args.length>0 && args[0].length()>3)nomefile=args[0];
        if(args.length>1)parole=Integer.parseInt(args[1]);
        if(args.length>2)profondita=Integer.parseInt(args[2]);
        if(args.length>3)taglio=Integer.parseInt(args[3]);

        BufferedReader file=new BufferedReader(new FileReader(nomefile));
        Chain markov= new Chain(parole,profondita,taglio);
        markov.analizza(file);
        String stringa=markov.produci();
        System.out.println(stringa);
    }

}

Il codice è vagamente ispirato da quello presente nel libro “The Pratice Of Programming” di Kerninghan e Pike, un libro che consiglierei a tutti di leggere.

La demo, che nel frattempo ho convertito in Dart, è disponibile qui

Share Button

2 comments

  1. Nicola

    Ciao! L’applet non funge!!
    Ho bisogno di generare dello spam quanto prima!

    Grazie mille!

  2. Vincenzo La Spesa

    interessante… al posto del file php c’è un bel file vuoto -.-”

    ho ricreato la pagina dell’applet da capo

    http://www.thedarshan.com/home/MarkovJApplet.html

Commenti disabilitati.