Марковские цепи с редисом

Question

В целях самообразования я хочу реализовать генератор цепей Маркова, используя как можно больше Redis и как можно меньше логики уровня приложения.

Допустим, я хочу построить генератор слов на основе таблицы частот с глубиной истории N (скажем, 2).

В качестве не очень интересного примера для словаря из двух слов bar и baz таблица частот выглядит следующим образом ("." - терминатор, числа - вес):

. . -> b x2
. b -> a x2
b a -> r x1
b a -> z x1
a r -> . x1
a z -> . x1

Когда я генерирую слово, я начинаю с истории двух терминаторов . .

Существует только один возможный результат для первых двух букв: b a.

Третья буква может быть либо r, либо z с равными вероятностями, поскольку их веса равны.

Четвертая буква - это всегда терминатор.

(с более длинными словами в словаре было бы интереснее.)

В любом случае, как сделать это с Redis элегантно?

Наборы Redis имеют SRANDMEMBER, но не имеют веса.

Сортированные в Redis наборы имеют веса, но не имеют случайного извлечения членов.

Списки Redis позволяют представлять веса в виде копий записей, но как сделать с ними множество пересечений?

Похоже, код приложения обречен на некоторую обработку данных ...

Answer 1

Взвешенный случайный выбор можно выполнить с помощью повторно отсортированного набора, присваивая каждому члену балл от нуля до единицы в соответствии с совокупной вероятностью членов рассматриваемого набора, включая текущего участника.
используемый вами порядок не имеет значения;Вы можете выбрать любой удобный для вас заказ.Затем случайный выбор выполняется путем генерации случайного числа с плавающей запятой r , равномерно распределенного между нулем и единицей, и вызова

ZRANGEBYSCORE zset r 1 LIMIT 01,

, который вернет первый элемент со счетом, большим или равным r .Немного рассуждений должно убедить вас, что вероятность выбора члена, таким образом, взвешена правильно.

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