Генерирование случайных слов в JS

Допустим, у нас возникла идея создать скрипт на JS, который бы генерировал случайные слова (никнеймы).

Начнём для начала с самого простого подхода. Если мы просто будем брать случайные буквы и составлять их них слова, то они будут выглядеть неестественно и неприглядно. Примеры сгенерированных слов:

  • srjxdq
  • moyssj
  • ywtckmw
  • wjvzw
  • xtwey

и т.д.

Как видим, такой подход не позволяет нам генерировать слова, которые хотя бы отдалённо напоминали обычные – получается просто набор бессмысленных букв, который больше походит на пароли. Чтобы придать словам натуральность и “человечность”, нам нужно сделать как минимум две вещи (на мой взгляд):

  1. Исключить появления более двух гласных/согласных при генерировании слова. Данная задача является тривиальной и ее не имеет смысла рассматривать.
  2. Подбирать случайные буквы для слова с учётом их веса. Весами в данном случае будут являться частотность букв в английском языке. Таким образом мы должны уменьшить/увеличить шанс того, что определенная буква попадёт в наше генерируемое слово, и таких редко используемых букв, как, например, Q, Z и X будут встречаться в наших словах гораздо реже, чем E, T, A, O, I, которые по статистике являются самыми частыми в английских словах.

Используя всего два этих подхода, мы генерируем гораздо более “натуральные” слова. Примеры:

screenshot_0.png

Разберём 2-й пункт поподробнее.

Алгоритм выбора случайных элементов массива на основе весов в JS

Относительно простой имплементацией подобного алгоритма является преобразование ряда рациональных чисел s1 (массива), являющимися весами для элементов, в ряд чисел s2, который получается посредством кумулятивного сложения чисел:

equation

const items = [ 'a', 'b', 'c' ]; 
const weights = [ 3, 7, 1 ];
  • Подготавливаем массив весов посредством кумулятивного сложения (то есть список cumulativeWeights, который будет иметь то же количество элементов, что и исходный список весов weights). В нашем случае такой массив будет выглядеть следующим образом:
cumulativeWeights = [3, 3 + 7, 3 + 7 + 1] = [3, 10, 11]

  • Генерируем случайное число randomNumber от 0 до самого высокого кумулятивного значения веса. В нашем случае случайное число будет находиться в диапазоне [0..11]. Допустим, что randomNumber = 8.

  • Проходим с помощью цикла по массиву cumulativeWeights слева направо и выбираем первый элемент, который больше или равен randomNumber. Индекс такого элемента мы будем использовать для выбора элемента из массива элементов

Идея этого подхода заключается в том, что более высокие веса будут “занимать” больше числового пространства. Следовательно, существует более высокая вероятность того, что случайное число попадет в “числовое ведро” с более высоким весом.

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

const weights = [3, 7, 1 ]; 
const cumulativeWeights = [3, 10, 11]; 
// В псевдопредставлении мы можем представить cumulativeWeights следующим образом: 
const pseudoCumulativeWeights = [ 
1, 2, 3, // <-- [3] числа 
4, 5, 6, 7, 8, 9, 10, // <-- [7] чисел 
11, // <-- [1] число 
];

Как видим, более тяжёлые весы занимают более высокое числовое пространство, а следовательно, имеют более высокий шанс быть случайно выбранными. Процентное соотношение шанса выбора для элементов weights будет таким:

Элемент 3: ≈ 27%,

Элемент 7: ≈ 64%,

Элемент 1: ≈ 9%

В общем случае функция выглядит примерно так:

function weightedRandom(items, weights) {
if (items.length !== weights.length) {
throw new Error('Массивы элементов и весов должны быть одинакового размера');
}

if (!items.length) {
throw new Error('Элементы массива не должны быть пустыми');
}
const cumulativeWeights = [];
for (let i = 0; i < weights.length; i += 1) {
cumulativeWeights[i] = weights[i] + (cumulativeWeights[i - 1] || 0);
}

const maxCumulativeWeight = cumulativeWeights[cumulativeWeights.length - 1];

const randomNumber = maxCumulativeWeight * Math.random();

for (let itemIndex = 0; itemIndex < items.length; itemIndex += 1) {
if (cumulativeWeights[itemIndex] >= randomNumber) {
return items[itemIndex];
}
}
}

Как можно еще лучше алгоритм генерации слов?

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

  • satlenl
  • tohhi
  • tiowh
  • aahepw

и т.д.

Самым простым решением этого вопроса является ограничение на чередование более двух гласных/согласных слов:

if (vowelCounter >= maxVowelsInRow) { i -= 1; continue; }

и

if (consonantCounter >= maxConsonantsInRow) { i -= 1; continue; }

Пусть значения maxConsonantsInRow = 1 и maxVowelsInRow = 1, тогда сгенерированные слова будут выглядеть примерно так:

screenshot_1.png

Отмечу здесь, что th и ae являются диграмами, и считаются как одна буква.

Очевидной минус данного подхода заключается в том, что сгенерированные слова получаются более однотипными и с гораздо меньшим вариативным потенциалом.

С полной версией скрипта можно ознакомиться здесь: https://github.com/bernd32/nickname-generator

Tags: ,