redis - Redis を使用したマルコフ連鎖

Question

独学の目的で、Redis をできるだけ多く使用し、アプリケーション レベルのロジックをできるだけ少なくして、マルコフ連鎖ジェネレーターを実装したいと考えています。

履歴の深さ N (たとえば、2) の頻度表に基づいて、単語ジェネレーターを作成したいとしましょう。

あまり興味深い例ではありませんが、 と という 2 つの単語の辞書のbar頻度baz表は次のようになります ("." はターミネータ、数字は重みです)。

. . -> b×2
. b -> a x2
ba -> r x1
ba -> z x1
ar -> . x1
az -> . x1

単語を生成するときは、2 つのターミネーターの履歴から始めます. .

最初の 2 文字の可能な結果は 1 つだけb aです。

重みが等しいため、3 番目の文字は または のいずれrかであり、確率は同じです。z

4 番目の文字は常にターミネータです。

（辞書に長い単語があると、より興味深いものになります。）

とにかく、これを Redis でエレガントに行う方法は?

Redis セットにはSRANDMEMBERがありますが、重みはありません。

Redis の並べ替えられたセットには重みがありますが、ランダムなメンバーの取得はありません。

Redis リストでは重みをエントリのコピーとして表すことができますが、それらとの交差を設定するにはどうすればよいですか?

アプリケーションコードは、何らかのデータ処理を行う運命にあるようです...

Answer 1

現在のメンバーを含む、これまでに考慮されたセットのメンバーの累積確率に従って、各メンバーに 0 と 1 の間のスコアを割り当てることにより、redis の並べ替えられたセットで加重ランダム選択を実行できます。 使用する順序は関係ありません。ご都合のよい順序をお選びいただけます。ランダムな選択は、 0 と 1 の間で均一に分散されたランダムな浮動小数点数rを生成し、

ZRANGEBYSCORE zset r 1 LIMIT 0 1,

r以上のスコアを持つ最初の要素を返します。このようにメンバーを選択する確率が正しく重み付けされていることは、少し推論するだけで納得できます。

残念ながら、要素に割り当てられたスコアが累積確率に比例する必要があるという事実は、要素のランダム選択のスコアの有意性を保持する方法で、並べ替えられた集合の結合または交差演算を使用することを困難にしているように思われます。 . その部分には、いくつかの重要なアプリケーション ロジックが必要なようです。