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

Ответ 1

Я предполагаю, что вы храните частоты в виде чисел с плавающей запятой между 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.

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

Ответ 2

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

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

Ответ 3

Что бы я сделал, это масштабировать относительные частоты в виде чисел с плавающей запятой, чтобы их сумма составляла 1,0. Затем я создам массив суммарных итогов на букву, т.е. Число, которое должно быть увенчано, чтобы получить эту букву и все эти "ниже". Скажем, что частота А составляет 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

Даже не псевдокод, а возможный подход:

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

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

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

Ответ 5

Использование двоичного дерева дает вам хороший, чистый способ найти правильную запись. Здесь вы начинаете с карты 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();
  }