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

Question

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

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

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

,, -> б х2, б -> х2
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 0 1,

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

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