redis - 带 Redis 的马尔可夫链

Question

出于自学目的，我想实现一个马尔可夫链生成器，使用尽可能多的 Redis 和尽可能少的应用程序级逻辑。

假设我想构建一个基于历史深度为 N(比如 2)的频率表的单词生成器。

举个不太有趣的例子，对于bar和baz两个单词的字典，频率表如下(“.”为终止符，数字为权重) :

. . -> b x2. b -> a x2b a -> r x1b a -> z x1a r -> . x1a z -> . x1

当我生成单词时，我从两个终结符的历史开始 。 .

前两个字母只有一种可能的结果，b a。

第三个字母可能是 r 或 z，概率相等，因为它们的权重相等。

第四个字母始终是终止符。

(字典里的单词越长，事情会越有趣。)

无论如何，如何使用 Redis 优雅地做到这一点？

Redis 集有 SRANDMEMBER，但没有权重。

Redis 排序集有权重，但没有随机成员检索。

Redis 列表允许将权重表示为条目副本，但如何与它们进行集合交集？

看起来应用程序代码注定要进行一些数据处理...

Answer 1

您可以使用 redis 排序集完成加权随机选择，方法是根据到目前为止考虑的集合成员的累积概率为每个成员分配一个介于 0 和 1 之间的分数，< em>包括当前成员。
您使用的顺序无关紧要；您可以选择任何对您方便的顺序。然后通过生成一个在 0 和 1 之间均匀分布的随机 float r 并调用

来完成随机选择

ZRANGEBYSCORE zset r 1 LIMIT 0 1,

这将返回得分大于或等于 r 的第一个元素。稍加推理就会使您相信，选择成员的概率因此得到了正确的加权。

不幸的是，分配给元素的分数需要与累积概率成正比这一事实似乎使得难以以保留的方式使用排序集并集或交集操作分数对于随机选择元素的重要性。这部分似乎需要一些重要的应用程序逻辑。