1

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

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

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

. . -> b x2
. b -> a x2
巴 -> r x1
巴 -> z x1
阿尔->。x1
阿兹->。x1

当我生成这个词时,我从两个终结者的历史开始. .

前两个字母只有一个可能的结果,b a

第三个字母可能是rz,概率相等,因为它们的权重相等。

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

(字典中的单词越长越有趣。)

无论如何,如何优雅地使用 Redis 做到这一点?

Redis 集有SRANDMEMBER,但没有权重。

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

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

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

4

1 回答 1

1

您可以使用 redis 排序集完成加权随机选择,方法是根据迄今为止考虑的集合成员(包括当前成员)的累积概率为每个成员分配一个介于 0 和 1 之间的分数。 您使用的排序无关紧要;您可以选择任何方便的顺序。然后通过生成均匀分布在零和一之间的随机浮点数r来完成随机选择,并调用

ZRANGEBYSCORE zset r 1 LIMIT 0 1,

这将返回分数大于或等于r的第一个元素。一点点推理应该会让你相信选择成员的概率是正确加权的。

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

于 2016-03-13T05:00:57.843 回答