Reddit排名算法工作原理 -- 算法 -- IT技术博客大学习 -- 共学习共进步！

您现在的位置：首页 --> 算法 --> Reddit排名算法工作原理

Reddit排名算法工作原理

浏览:2257次出处信息

这是一篇继《Hacker News 排名算法工作原理》之后的又一篇关于排名算法的文章。这次我将跟大家探讨一下Reddit的文章排名算法和评论排名算法的工作原理。Reddit使用的算法也是很简单，容易理解和实现。这篇文章里我将会对其进行深入分析。

首先我们关注的是文章排名算法。第二部分将重点介绍评论排名算法，Reddit的评论排名跟文章排名使用的不是同一种算法(这点跟Hacker News不一样)，Reddit的评论排名算法非常有趣，它是由xkcd的作者Randall Munroe发明的。

深入研究文章排名算法代码

Reddit的源代码是开源的，你可以下载它的任意代码。它是用Python写成的，代码放在这里。里面的排名算法部分是用Pyrex实现的，这是一种开发Python的C语言扩展的编程语言。这里用Pyrex主要是出于速度的考虑。我用纯Python重写了他们的Pyrex实现，这样更容易阅读。

Reddit缺省的排名是’热门‘排名，实现代码如下：

#Rewritten code from /r2/r2/lib/db/_sorts.pyx

from datetime import datetime, timedelta
from math import log

epoch = datetime(1970, 1, 1)

def epoch_seconds(date):
    """Returns the number of seconds from the epoch to date."""
    td = date - epoch
    return td.days * 86400 + td.seconds + (float(td.microseconds) / 1000000)

def score(ups, downs):
    return ups - downs

def hot(ups, downs, date):
    """The hot formula. Should match the equivalent function in postgres."""
    s = score(ups, downs)
    order = log(max(abs(s), 1), 10)
    sign = 1 if s > 0 else -1 if s < 0 else 0
    seconds = epoch_seconds(date) - 1134028003
    return round(order + sign * seconds / 45000, 7)

这个“热门“排名算法用数学公式表达是下面这个样子(我从SEOmoz找到了它，但我怀疑他们未必是原作者)：

reddit_cf_algorithm

文章提交时间对排名的影响

文章提交时间对排名的影响可以总结为以下几点：

提交时间对排名影响巨大，越新的文章排名会越高
文章排名得分不会随时间的流逝而降低，但新文章会比老文章获得更高的分。这跟Hacker News的排名算法有很大区别，它的得分会随时间流逝而降低。

下面是一个图片，表现的是具有相同支持和反对的票数，但时间不同的文章的排名得分情况：

reddit_score_time

对数加强

Reddit在‘热门’排名中使用了对数函数来强化前几票的份量。基本是这个原理：

前10个赞成票的份量和后面100个的份量，以及再后面1000票的份量是相同的，以此类推

下面是效果图：

reddit_log_function

如果不使用对数加强，则分数会是这样：

reddit_without_log

反对票对排名的影响

Reddit是少数几个能投反对票的网站之一。就像你从代码里看到的，一篇文章的的’得分‘定义如下：

up_votes - down_votes

这就是说，我们可以把它表现为下图：

reddit_up_down

这种计算方式会对既有很的赞成票，又有很多反对票的文章(比如很有争议的文章)带来重大影响，它们可能会比那些只有很少赞成票的文章获得更低的分数。这也就说明了为什么小猫小狗之类的帖子(以及其它无争议的文章)会获得如此高的评分。

对Reddit文章排名算法的总结

提交时间是一项非常重要的指标，新文章比老文章得分更高
头10个赞成票的份量和后100个的份量相同。获得10个赞成票和获得50个赞成票的排名很接近
具有相近赞成票和反对票数的有争议文章会比只获得赞成票的排名低。

Reddit评论排名算法工作原理

xkcd网站的Randall Munroe是Reddit网站上的‘最佳文章’排名算法的发明者。他写了一篇很好的文章来解释它。

reddit’s new comment sorting system

你应该读一读这篇文章，它以很通俗的语言解释了这个算法。这篇的文章的重点是：

‘热门‘排名算法对评论进行排名不是很有效，它会显得对早期的评论过于偏爱。
在一个评论系统中，我们的目的是找出最佳评论，不论它是什么时间提交的。
1927年Edwin B. Wilson找到了一种很好的算法，被叫做”Wilson score interval”，它可以被用于“信任排序(the confidence sort)”
信任排序把文章的获得的票数当作全体读者的一个抽样统计——就像一次民意测验。
《How Not To Sort By Average Rating》这篇文章对这种信任评级算法做了详细的解释，绝对值得一读！

深入分析评论排序代码

Reddit里的信任排序算法是在_sorts.pyx这个文件里实现的，我用纯Python重写了它们的Pyrex实现(同时去掉了其中的缓存优化代码)：

#Rewritten code from /r2/r2/lib/db/_sorts.pyx

from math import sqrt

def _confidence(ups, downs):
    n = ups + downs

    if n == 0:
        return 0

    z = 1.0 #1.0 = 85%, 1.6 = 95%
    phat = float(ups) / n
    return sqrt(phat+z*z/(2*n)-z*((phat*(1-phat)+z*z/(4*n))/n))/(1+z*z/n)

def confidence(ups, downs):
    if ups + downs == 0:
        return 0
    else:
        return _confidence(ups, downs)

信任排序使用Wilson score interval算法，它的数学表达式是这样的：

wilsons_score_interval

在上面的公式中，各个参数的定义如下：

p是支持票的百分比
n总票数
zα/2是正态分布(1-α/2)分位数

我们对上面的介绍做一些总结：

信任排序是把票数看作一次全体读者的抽样调查
信任排序会给一条评论一个临时评级，认为它有85%的可信度
票数越多，可信度越高
Wilson’s interval算法能很好的处理票数很少和低端概率情况

Randall在他的文章里对信任排序的工作原理给了一个很好的例子：

如果一条评论只有一个赞成票和0个反对票，它有100%的支持率，但因为投票数太少，系统将会把它放在排名底部。但如果它有10个赞成票，而其只有1个反对票，那系统将会把它放到比具有40个赞成票和20个反对票的评论更高的排名上——可以推断出，当这个评论获得40个赞成票时，它极有可能获得的反对票会少于20。这种算法最好的部分是，如果推断错了，那它会很快的获得更多的数据来证明，因为它已经被排到了顶部。