Generare casualmente lettere in base alla loro frequenza d’uso?

Come posso generare lettere in modo casuale in base alla loro frequenza di utilizzo nel parlato comune?

Ogni pseudo-codice è apprezzato, ma un’implementazione in Java sarebbe fantastica. Altrimenti sarebbe utile solo un colpo nella giusta direzione.

Nota: non ho bisogno di generare le frequenze di utilizzo, sono sicuro di poterlo controllare abbastanza facilmente.

Suppongo che tu memorizzi le frequenze come numeri in virgola mobile tra 0 e 1 per ottenere 1 totale.

Per prima cosa dovresti preparare una tabella di frequenze cumulative, cioè la sum della frequenza di quella lettera e di tutte le lettere precedenti.

Per semplificare, se inizi con questa distribuzione di frequenza:

 A 0.1 B 0.3 C 0.4 D 0.2 

La tabella delle frequenze cumulative potrebbe essere:

 A 0.1 B 0.4 (= 0.1 + 0.3) C 0.8 (= 0.1 + 0.3 + 0.4) D 1.0 (= 0.1 + 0.3 + 0.4 + 0.2) 

Ora generi un numero casuale tra 0 e 1 e vedi dove in questo elenco si trova quel numero. Scegli la lettera che ha la frequenza cumulativa più piccola più grande del tuo numero casuale. Qualche esempio:

Supponiamo che tu scelga a caso 0,612. Questo si trova tra 0,4 e 0,8, cioè tra B e C, quindi scegli C.

Se il tuo numero casuale era 0.039, quello prima di 0.1, cioè prima di A, quindi scegli A.

Spero che abbia senso, altrimenti non esitate a chiedere chiarimenti!

Un modo rapido per farlo sarebbe quello di generare un elenco di lettere, in cui ogni lettera appariva nell’elenco in base alla sua frequenza. Supponi, se “e” fosse usato il 25,6% delle volte e la tua lista avesse lunghezza 1000, avrebbe 256 “e” s.

Quindi è ansible selezionare in modo casuale dei punti dall’elenco usando (int) (Math.random() * 1000) per generare numeri casuali compresi tra 0 e 999.

Quello che vorrei fare è scalare le frequenze relative come numeri in virgola mobile tali che la loro sum sia 1.0. Quindi creerei una serie di totali cumulativi per lettera, ovvero il numero che deve essere completato per ottenere quella lettera e tutti quelli “sotto”. Supponi che la frequenza di A sia 10%, b sia 2% e z sia 1%; allora il tuo tavolo sarebbe simile a questo:

 0.000 A ; from 0% to 10% gets you an A 0.100 B ; above 10% is at least a B 0.120 C ; 12% for C... ... 0.990 Z ; if your number is >= 99% then you get a Z 

Quindi si genera un numero casuale compreso tra 0.0 e 1.0 e si esegue una ricerca binaria nell’array per il primo numero più piccolo del numero casuale. Quindi scegli la lettera in quella posizione. Fatto.

Neanche uno pseudo-codice, ma un ansible approccio è il seguente:

Lascia che p1, p2, …, pk siano le frequenze che vuoi abbinare.

  1. Calcola le frequenze cumulative: p1, p1 + p2, p1 + p2 + p3, …, 1
  2. Generare un numero uniforms di uniformi (0,1) x
  3. Controlla quale intervallo delle frequenze cumulative x appartiene a: se è tra, diciamo, p1 + .. + pi e p1 + … + pi + p (i + 1), quindi emette la lettera (i + 1)

A seconda di come si implementa la ricerca dell’intervallo, la procedura è solitamente più efficiente se p1, p2, … sono ordinati in ordine decrescente, perché di solito si trova prima l’intervallo contenente x.

L’uso di un albero binario offre un modo semplice e pulito per trovare la voce giusta. Qui, si inizia con una mappa di frequency , in cui le chiavi sono i simboli (lettere inglesi) e i valori sono la frequenza della loro occorrenza. Questo viene invertito e viene creata una NavigableMap dove le chiavi sono probabilità cumulative e i valori sono simboli. Ciò rende la ricerca facile.

  private final Random generator = new Random(); private final NavigableMap table = new TreeMap(); private final float max; public Frequency(Map frequency) { float total = 0; for (Map.Entry e : frequency.entrySet()) { total += e.getValue(); table.put(total, e.getKey()); } max = total; } /** * Choose a random symbol. The choices are weighted by frequency. */ public int roll() { Float key = generator.nextFloat() * max; return table.higherEntry(key).getValue(); }