Случайным образом Генерируйте Буквы Согласно их Частоте Использования?
Как я могу случайным образом генерировать буквы согласно их частоте использования в общей речи?
Любой ценивший псевдокод, но реализация в Java был бы фантастическим. Иначе просто введение по абсолютному адресу в правильном направлении было бы полезно.
Примечание: Я не должен генерировать частоты использования - я уверен, что могу искать это достаточно легко.
5 ответов
Я предполагаю, что вы храните частоты, как числа плавающих точек от 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.
Я надеюсь, что делает Смысл, в противном случае не стесняйтесь просить разъяснений!
То, что я бы сделал, это масштабировать относительные частоты как числа плавающих точек, так что их сумма 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 и выполняют двоичный поиск в массиве для первого числа меньшего, чем ваше случайное число. Затем выберите письмо в этой позиции. Сделанный.
даже не псевдокод, но возможный подход выглядит следующим образом:
Пусть P1, p2, ..., pk - это частоты, которые вы хотите сопоставить.
- Рассчитайте совокупные частоты: P1, P1 + P2, P1 + P2 + P3, ..., 1
- генерируют случайную форму (0,1) номер x
- , проверьте, какой интервал совокупных частот X принадлежит: если оно между, скажем, p1 + .. + pi и p1 + ... + pi + p (i + 1), затем вывод (i + 1) st storm
в зависимости от того, как вы реализуете интервал -Вот, процедура, как правило, более эффективна, если P1, P2, ... отсортированы в порядке уменьшения, поскольку вы обычно найдете интервал, содержащий x раньше.
Использование бинарного дерева дает вам приятный, чистый способ найти правильную запись. Здесь вы начинаете с частоты карты , где ключи являются символами (английскими буквами), а значения являются частотой их возникновения. Это инвертировано, а 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();
}
Один быстрый способ сделать это, чтобы генерировать список букв, где каждая буква появилась в списке в соответствии со своей частотой. Скажем, если «E» использовали 25,6% времени, и ваш список имел длину 1000, у него будет 256 "E" S.
Тогда вы можете просто выбирать пятна из списка с помощью (INT) (Math.random () * 1000) для генерации случайных чисел от 0 до 999.