隨機音樂的演算法

4 人贊了文章

今天瀏覽Spotify官方博客時被一篇介紹音樂隨機播放演算法的博客吸引，隨後對這個問題小小研究了一下。

隨機播放音樂，這個功能太普通以至於以前從未考慮過其背後實現邏輯。

Random還是shuffle

我們經常使用的隨機播放功能，在外國同行口中並不是叫Random播放，而是叫Shuffle，洗牌的意思。

為什麼不是Random？來看兩個例子。

在Spotify成立之初，他們使用一種叫「Fisher-Yates shuffle」的演算法去產生一個完全隨機（perfectly random ）的播放列表，這個演算法據說非常簡單，只需3行代碼搞定，不過它存在致命弱點。

上圖中，每種顏色代表一位歌手，也就是說我的列表裡有綠色歌手的4首歌，紅色歌手的2首歌，黑色歌手的2首歌。

圖中上下兩行都是運行Fisher-Yates演算法可能產生的播放列表，請問這兩個列表出現的概率哪個更大呢？

答案是一樣大，完全隨機演算法下，每一首歌出現在每個位置的概率是一樣的。你可能認為這怎麼可能，前面已經出現3次綠色歌手的歌了，下一次出現概率應該很小了吧。錯了，演算法是沒有記憶的，除非你告訴它，下一首不允許播放綠色歌手的歌，否則它播放綠色歌手的歌的概率還是50%。

再來看個例子，假設你播放列表裡有10首搖滾樂（A），11首鄉村樂（B），11首爵士樂（C），下面是我自己用Python的random函數生成的序列：

A A A A C C C B C B B A C B C B B B B A B C B A C A C C A A C B

可以看出，這個列表裡前半段和後半段基本上沒有B出現，尤其是前面連續4個A和3個B，這樣的結果是無法令人滿意的，一點均衡性都沒有。

回頭再想，我們為什麼要隨機播放？因為我們不知道要聽什麼，我們想要一個隨性的播放列表，我們不想專門聽某一位歌手的或某一張專輯的曲目，我們不想按照平常循環的順序播放，我們想換換口味有點新意，所以我們把這個選擇權交給軟體本身去做，如果軟體接連給你播放同一個歌手或同一張專輯的曲目，那就違背我們隨機的目的了。所以好的隨機播放列表應該做到均衡分布，同一個流派、同一個歌手、同一種專輯下的音樂彼此之間相距越遠越好。

還是上面這個例子，好的播放列表應該是下面這樣的：

A B C B C A B A C B A C B C A B C A C B A B C A C B A C B C A B

shuffle播放演算法

那麼如何生成上面這個均衡的播放列表呢？博主Martin Fiedler給了一個思路。

1）將列表中的歌曲按流派、歌手、專輯等邏輯範式分組，給這個組裡的音樂設定一個隨機播放順序；

2）接下來把每個分組的曲目通過合併演算法組成一個完整的播放列表。

很簡單吧，僅僅兩步而已。接下來看看合併演算法是怎麼一回事。假設在第一步我們得到了下面的分組：

將每個分組擴充到和最大分組相等的長度，比如給綠色分組填充8首「靜默」歌曲，讓該組長度等於12。填充的時候應盡量讓組中的音樂均衡分布列表中。

每個分組都填充完畢後，就開始合併新列表了，從每個分組的第1列按隨機順序取出歌曲放在新列表中。

再取出第2列按隨機順序取出歌曲放在新列表中。

第3列。需要注意的是，假如第2次取出的是黃-紅-藍，第3次取出藍-黃-紅-綠，那麼就會有兩個藍色分組的歌曲接連出現的情況，這個時候需要把第3次拿出的歌曲首尾互換，最後得出綠-黃-紅-藍的順序。

以上就是shuffle播放背後的大概邏輯了。

參考資料：

1. How to shuffle songs?
2. The art of shuffling music

推薦閱讀：