Category Archives: 0和1

隐马尔可夫模型及其应用(1)简介&解码问题

隐马尔可夫模型(Hidden Markov Model, HMM)是统计模型,它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析,例如模式识别。

先举一个简单的例子以直观地理解HMM的实质——韦小宝的骰子。

hmm-2 Continue reading

稳定版快速排序算法

我们知道常规的快速排序算法是一个不稳定的算法,也就是两个相等的数排序之后的顺序可能和在原序列中的顺序不同。这是因为当选定一个枢轴(pivot),要把其他数分到小于pivot和大于pivot的两边的时候,不同实现的分法不一样。

下面我实现了一种稳定版快速排序算法,在Partition函数中保持了原序列中所有元素的相对顺序,只把pivot放到了它的正确位置。具体方法是三遍扫描原序列:1)第一遍先把小于pivot的元素按先后顺序放到tmp里,然后把pivot放到它的正确位置tmp[k];2)第二遍把大于pivot的元素按先后顺序追加在tmp里,这样除了pivot以前的其他元素,都保持了和原序列中一样的顺序;3)第三遍把tmp赋值回原数组A。

当排序算法稳定之后,就可以借此统计逆序数了,文件Q5.txt中共包含100000个不同的整数,每行一个数。我们可以使用稳定版快速排序算法对其排序,并统计出其中的逆序数个数。 Continue reading

Huffman编码压缩算法及其实现

哈弗曼编码是一个很经典的压缩算法,压缩率能达到50%,甚至更低。它的基本原理包括四个步骤:

  1. 统计文件中每个字符出现的频率。
  2. 构建一个哈弗曼树。建树的过程是不断的合并频率最小的两个节点,父亲节点的频率为两个孩子节点的频率之和。如此循环直到合并成一个根节点。叶子节点为不同的字符及其频率。
  3. 生成哈弗曼编码。从树根开始对树进行编码,比如进入左孩子的边标记为0,进入右孩子的边标记为1,这里的0和1都是二进制位。这样之后,每个叶子节点都有一个唯一的二进制编码,这就是哈弗曼编码。频率越低的字符哈弗曼编码越长,频率越高的字符哈弗曼编码越短,这样就能起到压缩的效果。
  4. 第二遍扫描文件,把字符转换为对应的哈弗曼编码,保存成压缩文件。

解压缩的过程就是解析二进制位,然后查找哈弗曼树,每找到一个叶子节点,就解析出一个字符,直到解析完所有二进制位。下面详细解释我的C++实现。 Continue reading

还原谷歌PageRank算法真相

之前写了七篇博客详细介绍了搜索引擎的工作原理。彼时的搜索引擎主要讲查询和网页的相关性匹配,是动态的、在线的、实时的。相关性匹配有一个问题,网页很容易作弊,比如可以在一个网页中写满诸如“免费”、“美容”之类的垃圾关键词,进而提升查询相关性。但是用户在查询时,一定希望返回的网页比较权威可信,比如同样搜索“苹果电脑”,排名第一的应该是Apple的官网,而不应该是中关村在线之类的第三方网站。

权威性是一个静态的(或者说变化较慢的)衡量网页重要性的指标。但是应该怎样度量权威性呢,HITS算法使用authority来度量,即指向自身的网页数量越多,则自身的authority值越大。谷歌的PageRank算法是用PageRank值来衡量权威性的。HITS和PageRank一个比较大的区别是HITS和查询有关,而PageRank和查询无关,所以PageRank可以离线计算。下面主要介绍PageRank算法。

PageRank’s thesis is that a webpage is important if it is pointed to by other important pages.

Continue reading

调查问卷的有效性(2)相对误差

\begin{equation}Pr(|\hat{p}-p|\geq 5\%)\leq 5\%\end{equation}

上一回我们讲到当p本身很小的时候,容易被5%(绝对误差)给淹没掉,导致结果的不可信。我们可以引入相对误差,把(1)式转换为如下的不等式

\begin{equation}Pr(|\hat{p}-p|\geq\delta p)\leq\epsilon\end{equation}

同理,我们可以用

\begin{equation}\hat{p}=\frac{x_1+x_2+...+x_n}{n}\end{equation}

代替\hat{p}(建议先看上一篇博客),转换为

\begin{equation}Pr(|X-np|\geq\delta np)\end{equation}

类似的,X=x_1+x_2+...+x_nE(X)=\mu=np,所以(4)式等价为

\begin{equation}Pr(|X-\mu|\geq\delta\mu)\end{equation}

Continue reading

调查问卷的有效性(1)绝对误差

每年春晚过后,央视又要吹嘘说今年春晚收视率创新高了,但是我们总感觉央视在骗我们,因为我是越长大越不看春晚了[笑cry],所以收视率到底是怎么统计出来的,央视的说法是否靠谱呢?

最近的美国大选真是热闹,很多机构都会发放一些调查问卷,然后统计出希拉里或者唐纳德的民众支持率是多少,但是我并没有收到调查问卷,凭什么就得出了民众支持率了,意思是把我排除在民众之外咯?所以引出这样一个问题,调查问卷是否可信,即调查问卷的有效性。

其实,央视统计收视率并不要问全中国14亿人口有多少人看了春晚,他只需要从14亿人口里面随机抽n个人,问一下这n个人里有多少人看了春晚,然后把看的人数除以总数就大概估计出全国的收视率了。同理调查民众支持率也是一样,只需要随机调查n个人的意向,把支持希拉里的人数除以总数就大概得到了希拉里的支持率。

但是你要问了,通过抽样调查出来的收视率和支持率靠谱吗,需要随机抽样多少人才能得到一个比较好的全局近似解呢?今天我们就来解决这个问题。 Continue reading

有趣的交互式证明

你是否想过如下问题:怎样向色盲证明两只袜子的颜色是不一样的?怎样证明两个图是不同构的?怎样证明一个数是二次非剩余的?

咋听起来觉得很有意思吧,色盲是区分不了颜色的,怎么能让他相信两只袜子的颜色不一样呢。图同构问题目前既没有被证明属于P,也没有被证明属于NP-Complete。二次非剩余问题也没有被证明属于NP。

这些听起来很“难”的问题,却可以通过交互式证明进行证明,下面先通过“向色盲证明两只袜子的颜色不同”这个有趣的例子一窥交互式证明的强大。 Continue reading