Menu

TL;DR

approfondimento di /r/ItalyInformatica

I testi generati ovvero le catene di Markov

Per chi non mi conoscesse, sono /u/timendum , il creatore di /u/italy_SS , cioè il /r/SubredditSimulator per i contenuti in Italiano.

In questo articolo cercherò di spiegarvi il meccanismo dietro la generazione di testi casuali usati in questi due subreddit.

Cosa sono le catene di Markov

Le catene di Markov sono un concetto di matematica/probabilità; non starò qui a fare enunciazioni formali, tranquilli, cerchiamo solo di capire il concetto.

Un catena di Markov è una situazione il cui futuro dipende solo dallo stato attuale, cioè se so cosa sta succedendo adesso, sono in grado di determinare la probabilità di quello che succederà in futuro.

L’esempio che preferisco è il Gioco dell’Oca: sapendo solo che sei alla casella X, ad esempio 20, possiamo calcolare la probabilità della tua prossima posizione: per 1/12 sarai alla 22, per 2/12 alla 23 e così in avanti; chiaramente dovremmo tenere conto delle caselle speciali, quelle che mandano avanti o indietro, rendendo quindi il modello interessante.

Il termine più generico sarebbe processo di Markov, si usa catene quando il numero degli stati non è infinito.

Nell’informatica

Nella pratica come vogliamo rappresentare una catena di Markov nel nostro codice?

La scelta più semplice è un \”array associativo\”, quindi una Map (es: Java o Rust) o un dictionary (es: Python) o un Object (es: Javascript).

La chiave sarà lo stato attuale, come valore abbiamo un elenco di elementi {probabilità, prossimo stato}.

Ad esempio possiamo rappresentare così una catena: stato: [(%, prossimo), ...] dove:

  • stato è lo stato attuale, ad esempio il numero della casella nel gioco dell’oca
  • seguono quindi un elenco di possibili stati futuri [futuro1, futuro2, futuro3, ...] definiti come (%, prossimo)
  • % è la probabilità assoluta che questo caso si verifichi: ad esempio 1/12, quindi lo 8,3333%
  • prossimo prossimo è il prossimo stato che si verificherà con la probabilità appena elencata, ad esempio la casella 21.

I testi generati

La scrittura, semplificando abbastanza, si presta abbastanza bene ad essere modellata da una catena di Markov:
la prossima parola che scrivo sarà fortemente legata all’ultima che ho scritto.

Quello che possiamo fare è cercare un corpus, cioè un testo abbastanza grande da prendere come sorgente e modellare una catena di Markov.

Per fare un esempio ho preso il secondo paragrafo del precedente articolo su tl;dr

> Sappiamo che le password devono essere lunghe, devono essere complesse e solo una di queste due proprietà non basta: avere la stessa password per ogni sito web, sappiamo, non è cosa giusta. Tutte queste accortezze per cosa? Per non farsi rubare le password ovviamente: ma se volessi provarci?

Ecco come risulterà il nostro modello, nella forma esemplificata sopra, di parola: [(%, prossima), ...]:

  • sappiamo: [(100%; che)]
  • che: [(100%, le)]
  • le: [(100%, password)]
  • password: [(33%, devono), (33%, per), (33%, ovviamente)]
  • per: [(33%, ogni), (33%, cosa), (33%, non)]
  • cosa: [(50%, giusta), (50%, per)]
  • essere: [(50%, lunghe), (50%, complesse)]
  • queste: [(50%, due), (50%, accortezze)]
  • eccetera…

Fatto questo possiamo generare un testo casuale partendo dal modello.

  1. Prendiamo la parola di partenza, nel nostro modella abbiamo solo sappiamo
  2. Da sappiamo, il prossimo passo forzato è che
  3. Da che, c’è solo le
  4. Da le, c’è solo password
  5. Per password abbiamo più possibilità, \”tiro il dado\” ed estraggo per
  6. Anche da per ci sono più parole, ognuna con 1/3 di probabilità, estraggo casualmente cosa
  7. Da cosa estraggo giusta
  8. E così in avanti..

Risultato:

> Sappiamo che le password per cosa giusta. Tutte queste due proprietà non farsi rubare le password devono essere complesse e solo una di queste accortezze per cosa?

E da qui?

Ci sono ancora moltissime cose da considerare:

  • prima di tutto non abbiamo deciso come spezzare una frase dall’altra
  • ci servirebbero anche due “parole” speciali per segnare l’inizio e il termine della frase
  • dovrebbero decidere se fare un confronto tra parole case sensitive o meno
  • dovremmo decidere se includere eventuali segni di punteggiatura (virgola, punti di domanda, etc) nel nostro modello o meno
  • vorremmo scartare frasi troppo simili al testo originale (e come misuriamo quanto simili?)

L’autore originale, /u/Deimorz , ed io abbiamo usato il python e la libreria markovify.

Partire è facilissimo e, se parti con un testo abbastanza grande, i risultati sono già apprezzabili, se ovviamente vi piace il nonsense.

(grazie a /u/cancrena)

Scritto da u/timendum 

Link ai commenti

 

Crackare password? Facciamolo!

Questo articolo sarà un po’ diverso dagli altri: oltre a parlarvi dell’argomento (Crackare password n.d.r.), voglio proporvi una piccola sfida.

Sappiamo che le password devono essere lunghe, devono essere complesse e solo una di queste due proprietà non basta: avere la stessa password per ogni sito web, sappiamo, non è cosa giusta. Tutte queste accortezze per cosa? Per non farsi rubare le password ovviamente: ma se volessi provarci? Vi è mai capitato di crackare password?

(altro…)

Entrare nella community di Envato? Difficile ma si può!

Envato, con oltre 1 milione di utenti, è sicuramente uno dei più grandi market mondiali per quanto riguarda la vendita di contenuti multimediali quali temi per ogni cms, plugins, addons, audio, video, app totalmente modificabili dall’utente finale se acquistati. In envato troviamo themeforest, videohive, graphicriver, audiojungle, 3docean, photodune, codecanyon. Se vuoi guadagnare qualcosa dal tuo codice, Envato è quello che fa per te (o quasi). In questo articolo vorrei raccontare la mia breve esperienza su cosa e come ho fatto per farmi accettare un plugin WooCommerce in Envato.

(altro…)

Diritto alla riparazione: informazioni e consigli utili

Ci troviamo in un’epoca in cui il concetto di proprietà di un oggetto sta cambiando, in alcuni aspetti in maniera subdola e che non ci aspetteremmo: il “diritto alla riparazione” dei nostri dispositivi.
Siamo oggi circondati da telefoni, tablet, indossabili, portatili che ogni giorno diventano più sofisticati, compatti, costosi e delicati.
Quando acquistiamo uno di questi, la facilità o, al contrario, l’impossibilità di poter intervenire sugli elementi che li compongono per ripararli o migliorarli sono fattori che difficilmente consideriamo, ma a cui da consumatori dovremmo fare più attenzione, per diversi motivi.

(altro…)

Anti-DDoS Amazon Web Services Infrastructure

Con oltre un milione di clienti in 190 paesi, Amazon Web service è sicuramente una delle collezioni di servizi di cloud hosting più utilizzate. Nei clienti, troviamo aziende protagoniste nel mondo dell’informatica come Adobe, Vodafone e molte altre. “ Da grandi poteri derivano grandi responsabilità”, stessa frase vale se si offrono servizi che devono stare online 24 h su 24.

(altro…)