Случайно генерировать письма в соответствии с их частотой использования? - PullRequest
Новая
       14

Случайно генерировать письма в соответствии с их частотой использования?

10 голосов
/ 27 января 2010

Как я могу генерировать буквы случайным образом в соответствии с их частотой использования в обычной речи?

Любой псевдокод приветствуется, но реализация в Java была бы фантастической. В противном случае было бы полезно просто ткнуть в правильном направлении.

Примечание: мне не нужно генерировать частоты использования - я уверен, что смогу найти это достаточно легко.

Ответы [ 5 ]

18 голосов
/ 27 января 2010

Я предполагаю, что вы сохраняете частоты в виде чисел с плавающей запятой между 0 и 1, которые составляют 1.

Сначала вы должны подготовить таблицу кумулятивных частот, т. Е. Сумму частоты этой буквы и всех букв перед ней.

Для упрощения, если вы начнете с этого распределения частот: 

A  0.1
B  0.3
C  0.4
D  0.2

Ваша таблица кумулятивных частот будет: 

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)

Теперь сгенерируйте случайное число от 0 до 1 и посмотрите, где в этом списке лежит это число. Выберите букву с наименьшей суммарной частотой, превышающей ваше случайное число. Некоторые примеры:

Скажем, вы случайно выбрали 0,612. Это лежит в диапазоне от 0,4 до 0,8, то есть между B и C, поэтому вы должны выбрать C.

Если ваше случайное число было 0,039, то есть до 0,1, т. Е. До A, поэтому выберите A.

Надеюсь, это имеет смысл, в противном случае не стесняйтесь просить разъяснений!

11 голосов
/ 27 января 2010

Один из быстрых способов сделать это - создать список букв, где каждая буква появляется в списке в соответствии с ее частотой. Скажем, если бы «е» использовалось 25,6% времени, а ваш список имел длину 1000, он имел бы 256 «е».

Тогда вы можете просто случайным образом выбирать точки из списка, используя (int) (Math.random() * 1000), чтобы генерировать случайные числа от 0 до 999.

5 голосов
/ 27 января 2010

Что бы я сделал, это масштабировал относительные частоты как числа с плавающей запятой так, чтобы их сумма равнялась 1,0. Затем я создал бы массив из совокупных итогов за букву, то есть число, которое должно быть на вершине, чтобы получить это письмо и все те, что "под" ним. Скажем, частота A составляет 10%, b составляет 2% и z составляет 1%; тогда ваш стол будет выглядеть примерно так: 

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

Затем вы генерируете случайное число между 0,0 и 1,0 и выполняете двоичный поиск в массиве по первому числу, меньшему, чем ваше случайное число. Затем выберите букву в этой позиции. Готово.

4 голосов
/ 27 января 2010

Даже не псевдокод, но возможный подход заключается в следующем:

Пусть p1, p2, ..., pk - частоты, которым вы хотите соответствовать.

  1. Рассчитать совокупные частоты: p1, p1 + p2, p1 + p2 + p3, ..., 1
  2. Генерация случайного равномерного (0,1) числа x
  3. Проверьте, какому интервалу кумулятивных частот x принадлежит: если он находится, скажем, между p1 + .. + pi и p1 + ... + pi + p (i + 1), то выведите (i + 1) st письмо

В зависимости от того, как вы реализуете поиск интервала, процедура обычно более эффективна, если p1, p2, ... отсортированы в порядке убывания, потому что вы обычно найдете интервал, содержащий x раньше.

2 голосов
/ 28 января 2010

Использование бинарного дерева дает вам хороший, чистый способ найти правильную запись. Здесь вы начинаете с карты frequency, где ключи - это символы (английские буквы), а значения - частота их появления. Это инвертируется, и создается NavigableMap, где ключи представляют собой совокупную вероятность, а значения являются символами. Это облегчает поиск. 

  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();
  }
...