¿Genera aleatoriamente letras según su frecuencia de uso?

Question

¿Cómo puedo generar letras al azar según su frecuencia de uso en el habla común?

Se agradece cualquier pseudocódigo, pero una implementación en Java sería fantástica. De lo contrario, solo un golpe en la dirección correcta sería útil.

Nota: No necesito generar las frecuencias de uso, estoy seguro de que puedo buscarlo con la suficiente facilidad.

Answer 1

Estoy asumiendo que almacene las frecuencias como números de punto flotante entre 0 y 1 que suman para hacer 1.

Primero debe preparar una tabla de frecuencias acumulativas, es decir, la suma de la frecuencia de esa letra y todas las letras anteriores.

Para simplificar, si se inicia con esta distribución de frecuencias:

A 0.1 
B 0.3 
C 0.4 
D 0.2 

Su tabla de frecuencia acumulativa sería:

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) 

Ahora generar un número aleatorio entre 0 y 1 y ver donde en este enumera ese número miente. Elija la letra que tenga la frecuencia acumulativa más pequeña más grande que su número aleatorio. Algunos ejemplos:

Digamos que elige al azar 0.612. Esta se encuentra entre 0,4 y 0,8, es decir, entre B y C, por lo que elegiría C.

Si su número al azar fue 0,039, lo que viene antes de 0,1, es decir, antes de que A, así que elige A.

espero ¡eso tiene sentido, de lo contrario no dude en pedir aclaraciones!

Answer 2

Una manera rápida de hacerlo sería generar una lista de letras, donde cada letra aparecía en la lista de acuerdo con su frecuencia. Digamos, si "e" se usó el 25.6% del tiempo, y tu lista tenía una longitud de 1000, tendría 256 "e" s.

entonces se podría simplemente elegir al azar los puntos de la lista mediante el uso de (int) (Math.random() * 1000) para generar números aleatorios entre 0 y 999.

Answer 3

Ni siquiera un pseudo-código, pero un posible enfoque es el siguiente:

Let p1, p2, ..., pk ser las frecuencias que desea igualar.

1. calcular las frecuencias acumulativas: p1, p2 p1 +, p1 + p2 + p3, ..., 1
2. generar un uniforme aleatorio (0,1) x número
3. Comprobar que el intervalo de la frecuencias acumuladas x pertenece a: si se trata de entre, por ejemplo, p1 + .. + pi y p1 + ... + PI + P (i + 1), entonces la salida del (i + 1) st carta

Dependiendo sobre cómo implementar el hallazgo de intervalos, el procedimiento suele ser más eficiente si p1, p2, ... se ordenan en orden decreciente, ya que normalmente encontrará el intervalo que contiene x antes.

Answer 4

Lo que haría es escalar las frecuencias relativas como números de coma flotante de modo que su suma sea 1.0. Luego, crearía una matriz de acumulados totales por letra, es decirel número que se debe superar para obtener esa letra y todas las que están "debajo" de ella. Digamos que la frecuencia de A es 10%, b es 2% yz es 1%; entonces su mesa sería algo como esto:

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 

Entonces generan a sí mismo un número aleatorio entre 0,0 y 1,0 y hacer una búsqueda binaria en la matriz para el primer número más pequeño que su número al azar. Luego, elige la letra en esa posición. Hecho.

Answer 5

El uso de un árbol binario le brinda una forma agradable y limpia de encontrar la entrada correcta. Aquí, comienza con un mapa frequency, donde las teclas son los símbolos (letras en inglés), y los valores son la frecuencia de su aparición. Esto se invierte, y se crea un NavigableMap donde las claves son probabilidad acumulativa, y los valores son símbolos. Eso hace que la búsqueda sea fácil.

private final Random generator = new Random(); 

    private final NavigableMap<Float, Integer> table = 
    new TreeMap<Float, Integer>(); 

    private final float max; 

    public Frequency(Map<Integer, Float> frequency) 
    { 
    float total = 0; 
    for (Map.Entry<Integer, Float> 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(); 
    }