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

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

Cualquier pseudocódigo se aprecia, 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 frecuencias de uso, estoy seguro de que puedo buscarlo lo suficientemente fácil.

Supongo que almacenas las frecuencias como números de coma flotante entre 0 y 1 ese total para hacer 1.

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

Para simplificar, si comienza con esta distribución de frecuencia:

 A 0.1 B 0.3 C 0.4 D 0.2 

Su tabla de frecuencia acumulada 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 genere un número aleatorio entre 0 y 1 y vea en qué parte de esta lista se encuentra ese número. Elija la letra que tenga la frecuencia acumulativa más pequeña más grande que su número aleatorio. Algunos ejemplos:

Digamos que escoge al azar 0.612. Esto se encuentra entre 0.4 y 0.8, es decir, entre B y C, por lo que elegiría C.

Si su número aleatorio fue 0.039, eso viene antes de 0.1, es decir, antes de A, entonces elija A.

Espero que tenga sentido, de lo contrario, siéntase libre de pedir aclaraciones.

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.

Luego, puede elegir al azar puntos de la lista usando (int) (Math.random() * 1000) para generar números aleatorios entre 0 y 999.

Lo que haría es escalar las frecuencias relativas como números de punto flotante de modo que su sum sea 1.0. Luego, crearía una matriz de los totales acumulados por letra, es decir, el número que debe superarse 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 tu mesa se vería así:

 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 

Luego genere usted mismo un número aleatorio entre 0.0 y 1.0 y haga una búsqueda binaria en la matriz para el primer número más pequeño que su número aleatorio. Luego, elige la letra en esa posición. Hecho.

Ni siquiera un pseudocódigo, pero un posible enfoque es el siguiente:

Deje que p1, p2, …, pk sean las frecuencias que quiere unir.

  1. Calcule las frecuencias acumuladas: p1, p1 + p2, p1 + p2 + p3, …, 1
  2. Genera un número aleatorio uniforme (0,1) x
  3. Compruebe a qué intervalo de las frecuencias acumulativas pertenece x: si se encuentra entre, por ejemplo, p1 + .. + pi y p1 + … + pi + p (i + 1), luego envíe la (st + 1) letra st

Dependiendo de cómo implemente la búsqueda 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.

El uso de un árbol binario le brinda una forma agradable y limpia de encontrar la entrada correcta. Aquí, comienza con un mapa de 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 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(); }