Допустим, у нас возникла идея создать скрипт на JS, который бы генерировал случайные слова (никнеймы).
Начнём для начала с самого простого подхода. Если мы
просто будем брать случайные буквы и составлять их них слова, то они
будут выглядеть неестественно и неприглядно. Примеры сгенерированных
слов:
- srjxdq
- moyssj
- ywtckmw
- wjvzw
- xtwey
и т.д.
Как видим, такой подход не позволяет нам генерировать
слова, которые хотя бы отдалённо напоминали обычные – получается просто
набор бессмысленных букв, который больше походит на пароли. Чтобы
придать словам натуральность и “человечность”, нам нужно сделать как
минимум две вещи (на мой взгляд):
- Исключить появления более двух гласных/согласных при генерировании
слова. Данная задача является тривиальной и ее не имеет смысла
рассматривать.
- Подбирать случайные буквы для слова с учётом их веса. Весами в
данном случае будут являться частотность букв в английском языке. Таким
образом мы должны уменьшить/увеличить шанс того, что определенная буква
попадёт в наше генерируемое слово, и таких редко используемых букв, как,
например, Q, Z и X будут встречаться в наших словах гораздо реже, чем
E, T, A, O, I, которые по статистике являются самыми частыми в
английских словах.
Используя всего два этих подхода, мы генерируем гораздо более “натуральные” слова. Примеры:
Разберём 2-й пункт поподробнее.
Алгоритм выбора случайных элементов массива на основе весов в JS
Относительно простой имплементацией подобного алгоритма является
преобразование ряда рациональных чисел s1 (массива), являющимися весами
для элементов, в ряд чисел s2, который получается посредством
кумулятивного сложения чисел:
const items = [ '🍌', '🍎', '🥕' ];
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];
const pseudoCumulativeWeights = [
1, 2, 3,
4, 5, 6, 7, 8, 9, 10,
11,
];
Как
видим, более тяжёлые весы занимают более высокое числовое пространство,
а следовательно, имеют более высокий шанс быть случайно выбранными.
Процентное соотношение шанса выбора для элементов 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];
}
}
}
Как можно еще лучше алгоритм генерации слов?
Данный скрипт является больше примером использования
алгоритма выбора случайного элемента массива на основе их веса, поэтому я
не стал сильно углубляться в лингвистику и алгоритмы искусственного
интеллекта. Но навскидку сразу бросаются в глаза неприглядные комбинации
некоторых гласных и согласных пар, которые выглядят неестественно и не
встречаются в настоящих словах:
и т.д.
Самым простым решением этого вопроса является ограничение на чередование более двух гласных/согласных слов:
if (vowelCounter >= maxVowelsInRow) {
i -= 1;
continue;
}
и
if (consonantCounter >= maxConsonantsInRow) {
i -= 1;
continue;
}
Пусть значения maxConsonantsInRow = 1 и maxVowelsInRow = 1, тогда сгенерированные слова будут выглядеть примерно так:
Отмечу здесь, что th и ae являются диграмами, и считаются как одна буква.
Очевидной минус данного подхода заключается в том, что
сгенерированные слова получаются более однотипными и с гораздо меньшим
вариативным потенциалом.
С полной версией скрипта можно ознакомиться здесь: https://github.com/bernd32/nickname-generator
