Случайности - не случайны. Random с учетом веса

Konstantin
Konstantin Ostrovsky
2019-05-08 10:59:58
17

Наверно, каждый из Вас, так или иначе сталкивался с генераторами псевдослучайных чисел. Эти функции активно используются в играх, веб-сайтах и сложных информационных системах. Чаще всего функция rand уже входит в базовый набор функций языка. В JS - это Math.random, C# - System.Random, Cpp - std::rand, PHP - rand и тд.

Но порой возникают ситуации, когда необходимо контролировать вероятность генерации отдельных элементов. Когда, к примеру, числа в некотором диапазоне должны генерироваться на Х% чаще, чем другие числа.

В этой статье мы рассмотрим алгоритм генерации псевдослучайных чисел с учетом их веса. Все примеры будут приведены на языке JavaScript и С#

Генератор псевдослучайных чисел (ГПСЧ, англ. pseudorandom number generator, PRNG) — алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному). Современная информатика широко использует псевдослучайные числа в самых разных приложениях — от метода Монте-Карло и имитационного моделирования до криптографии. При этом от качества используемых ГПСЧ напрямую зависит качество получаемых результатов. Это обстоятельство подчёркивает известный афоризм математика ORNL Роберта Кавью (англ.)русск.: «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая». Wikipedia

Под понятием вес, следует принимать некоторое число типа float, определяющее коэффициент вероятности выпадания числа при работе алгоритма. 

Для примера предлагаю написать алгоритм генерации букв алфавита с учетом их частотности. 

Частотность — термин лексикостатистики, предназначенный для определения наиболее употребительных слов. Расчёт осуществляется по формуле: , где Freqx — частотность слова «x», Qx — количество словоупотреблений слова «x», Qall — общее количество словоупотреблений. В большинстве случаев частотность выражается в процентах. В словарях частотность слов может отражаться пометками — употребительное, малоупотребительное и т. д. Аналогичным образом определяется частотность для букв. Бо́льшая частотность согласных на данном отрезке текста (например, в стихотворениях) получила название аллитерации. Высокие показатели частотности гласных называются ассонансом. Частотный анализ используется в криптографии для выявления наиболее частотных букв того или иного языка. Частотность слов и букв являлась важнейшим инструментов криптоанализа в эпоху до повсеместного распространения блочных шифров. Не следует путать термины частотность и частота.Wikipedia

Для удобства и наглядности, мы будем использовать JSON для хранения данных. Информацию о "весе" каждой буквы мы можем взять из Wikipedia:

 

#БУКВАУПОТРЕБЛЕНИЙЧАСТОТНОСТЬ
1о5541448110.97%
2е426912138.45%
3а404870088.01%
4и371531427.35%
5н338388816.70%
6т316209706.26%
7с276270405.47%
8р239168254.73%
9в229307194.54%
10л222301744.40%
11к176534693.49%
12м162030603.21%
13д150521182.98%
14п142015722.81%
15у132457122.62%
16я101390852.01%
17ы95959411.90%
18ь87846131.74%
19г85646401.70%
20з83299041.65%
21б80517671.59%
22ч73001931.44%
23й61062621.21%
24х49041760.97%
25ж47469160.94%
26ш36787380.73%
27ю32207150.64%
28ц24388070.48%
29щ18224760.36%
30э16101070.32%
31ф13357470.26%
32ъ1854520.04%
33ё1849280.04%

 

Как мы видим, лидером по употреблению в словах в русском языке, является буква "О". Её частотность более 10%!

Для работы приведем эти данные в формат JSON. Структура будет следующая: [ { буква, вес } , ...].

В итоге получаем следующий JSON:

[
    { "word": "о", "weight": 10.97 },
    { "word": "е", "weight": 8.45 },
    { "word": "а", "weight": 8.01 },
    { "word": "и", "weight": 7.35 },
    { "word": "н", "weight": 6.70 },
    { "word": "т", "weight": 6.26 },
    { "word": "с", "weight": 5.47 },
    { "word": "р", "weight": 4.73 },
    { "word": "в", "weight": 4.54 },
    { "word": "л", "weight": 4.40 },
    { "word": "к", "weight": 3.49 },
    { "word": "м", "weight": 3.21 },
    { "word": "д", "weight": 2.98 },
    { "word": "п", "weight": 2.81 },
    { "word": "у", "weight": 2.62 },
    { "word": "я", "weight": 2.01 },
    { "word": "ы", "weight": 1.90 },
    { "word": "ь", "weight": 1.74 },
    { "word": "г", "weight": 1.70 },
    { "word": "з", "weight": 1.65 },
    { "word": "б", "weight": 1.59 },
    { "word": "ч", "weight": 1.44 },
    { "word": "й", "weight": 1.21 },
    { "word": "х", "weight": 0.97 },
    { "word": "ж", "weight": 0.94 },
    { "word": "ш", "weight": 0.73 },
    { "word": "ю", "weight": 0.64 },
    { "word": "ц", "weight": 0.48 },
    { "word": "щ", "weight": 0.36 },
    { "word": "э", "weight": 0.32 },
    { "word": "ф", "weight": 0.26 },
    { "word": "ъ", "weight": 0.04 },
    { "word": "ё", "weight": 0.04 }
]

Данные подготовлены, настало время разобрать наш алгоритм. Алгоритм будет оперировать 4-мя переменными:

  • values - набор данных, с которыми будет работать наш алгоритм;
  • total - общий вес всех элементов;
  • currentWeight - промежуточная переменная, которая будет использоваться для хранения веса;
  • rndWeight  - случайный средний вес, всех элементов, полученный с использованием функции random.

Разберем алгоритм. Для этого разделим его работу на несколько этапов:

  • Вычислить общий вес элементов;
  • Найти случайный вес из общего веса элементов;
  • Перебирать элементы, складывая их вес, пока случайный вес не будет достигнут.

Вот такая простая, но очень полезная функция теперь у Вас в арсенале!

Реализация алгоритма на языке JavaScript

/**
    Генерация случайного элемента с учетом веса
    @param array values [{word, weight}, ...]
    @return string word
**/
function randomWithWeight ( values )
{    
    
    // Создаем переменные
    let total = 0,
    currentWeight = 0,
    rndWeight = 0;

    // Вычисляем общий вес
    for(let item of values) total += item.weight;

    // Находим случайный вес
    rndWeight = Math.floor(Math.random() * total)
    
    // Перебираем все элементы, пока не достигнем нужного веса
    for (let item of values)
    {
        currentWeight += item.weight; // Прибавляем вес текущего элемента массива к временной переменной
        if ( currentWeight >= rndWeight ) // Прерываем генерацию и возвращаем букву
            return item.word;
    }
}

var words = [{ "word": "о", "weight": 10.97 }, { "word": "е", "weight": 8.45 }, { "word": "а", "weight": 8.01 }, { "word": "и", "weight": 7.35 }, { "word": "н", "weight": 6.70 }, { "word": "т", "weight": 6.26 }, { "word": "с", "weight": 5.47 }, { "word": "р", "weight": 4.73 }, { "word": "в", "weight": 4.54 }, { "word": "л", "weight": 4.40 }, { "word": "к", "weight": 3.49 }, { "word": "м", "weight": 3.21 }, { "word": "д", "weight": 2.98 }, { "word": "п", "weight": 2.81 }, { "word": "у", "weight": 2.62 }, { "word": "я", "weight": 2.01 }, { "word": "ы", "weight": 1.90 }, { "word": "ь", "weight": 1.74 }, { "word": "г", "weight": 1.70 }, { "word": "з", "weight": 1.65 }, { "word": "б", "weight": 1.59 }, { "word": "ч", "weight": 1.44 }, { "word": "й", "weight": 1.21 }, { "word": "х", "weight": 0.97 }, { "word": "ж", "weight": 0.94 }, { "word": "ш", "weight": 0.73 }, { "word": "ю", "weight": 0.64 }, { "word": "ц", "weight": 0.48 }, { "word": "щ", "weight": 0.36 }, { "word": "э", "weight": 0.32 }, { "word": "ф", "weight": 0.26 }, { "word": "ъ", "weight": 0.04 }, { "word": "ё", "weight": 0.04 }];

// Генерируем 50 случайных элементов
for (var i = 50; i >= 0; i--)
    console.log(randomWithWeight(words));

 

Реализация алгоритма на языке C#

using System.Collections.Generic;
using System.Collections;
using System;

[Serializable]
// Вспомогательная структура данных для хранения элементов массива
public class WordInsert
{
  public string word;
  public float weight;
}

/**
    Генерация случайного элемента с учетом веса
    @param array data [{word, weight}, ...]
**/
public class RandomWeight
{
  private WordInsert[] WordsList = null;

  RandomWeight(WordInsert[] data) {
        WordsList = data;
  }


  public string GetRandom() {
    // Создаем переменные
    float total = 0;
    float currentWeight = 0;
    float rndWeight = 0;

    // Вычисляем общий вес
    foreach(WordInsert i in WordsList) total += i.weight;

    // Находим случайный вес
    rndWeight = UnityEngine.Random.Range(1, total);

    // Перебираем все элементы, пока не достигнем нужного веса
    foreach (WordInsert word in WordsList)
    {
        currentWeight += word.weight;  // Прибавляем вес текущего элемента массива к временной переменной
        if ( currentWeight >= rndWeight )  // Прерываем генерацию и возвращаем букву
            return word.word;
    }

    return ""; // Подстраховка
  }
}