Massive Algorithms: Book Notes

Showing posts with label Book Notes. Show all posts

啊哈算法

解密QQ - d

新学期开始了，小哈是小哼的新同桌（小哈是个小美女哦~），小哼向小哈询问QQ 号，

小哈当然不会直接告诉小哼啦，原因嘛你懂的。所以小哈给了小哼一串加密过的数字，同时

小哈也告诉了小哼解密规则。规则是这样的：首先将第1 个数删除，紧接着将第2 个数放到

这串数的末尾，再将第3 个数删除并将第4 个数放到这串数的末尾，再将第5 个数删除……

直到剩下最后一个数，将最后一个数也删除。按照刚才删除的顺序，把这些删除的数连在一

起就是小哈的QQ 啦。现在你来帮帮小哼吧。小哈给小哼加密过的一串数是“6 3 1 7 5 8 9 2 4”。

int main()

{

int q[102]={0,6,3,1,7,5,8,9,2,4},head,tail;

int i;

//初始化队列

head=1;

tail=10; //队列中已经有9个元素了，tail指向队尾的后一个位置

while(head<tail) //当队列不为空的时候执行循环

{

//打印队首并将队首出队

printf("%d ",q[head]);

head++;

//先将新队首的数添加到队尾

q[tail]=q[head];

tail++;

//再将队首出队

head++;

}

getchar();getchar();

return 0;

}

纸牌游戏——小猫钓鱼

星期天小哼和小哈约在一起玩桌游，他们正在玩一个非常古怪的扑克游戏——“小猫钓

鱼”。游戏的规则是这样的：将一副扑克牌平均分成两份，每人拿一份。小哼先拿出手中的

第一张扑克牌放在桌上，然后小哈也拿出手中的第一张扑克牌，并放在小哼刚打出的扑克牌

的上面，就像这样两人交替出牌。出牌时，如果某人打出的牌与桌上某张牌的牌面相同，即

可将两张相同的牌及其中间所夹的牌全部取走，并依次放到自己手中牌的末尾。当任意一人

手中的牌全部出完时，游戏结束，对手获胜。

Book Note 1: An Introduction to Information Retrieval 读书笔记（一）

An Introduction to Information Retrieval 读书笔记（一）
这本书是 Yahoo! Labs 老大 Dr. P 合著的，近日决定泛读一下.

IR 所谓“方法”其实也就 inverted index 搞来搞去，新的东西不多，都是从别的地方借用过来的感觉。这部分我们整理第一章到第五章的内容，这是关于建立 boolean retrieval 的基本知识。大概的分块如下：

boolean retrieval，第 1-5 章
vector space model 和 evaluation，第 6-8 章
relevence 和几个 specific 的 retrieval 问题，第 9-12 章
machine learning 方法，第 13-18 章
web search 和 link analysis，第 19-21 章

boolean retrieval 要解决的就是一堆“（不）含有 xxx”通过和、或连接起来的 bool 表达式下的 retrieval 问题，这最常用的 inverted index 是相对 forward index 而言：所谓前向索引就是文档编号到所包含内容（如 bag of words 表达）的关系，而倒排索引是 word 对应到哪些文档的关系。对一个较大的语料建立 inverted index 可以用一次 Map/Reduce 实现：

mapper 输入为 doc ID 和内容，输出为 word, doc ID 的 key/value 对；
reducer 拿到的是同一个 word 对应的 doc ID 序列，一般我们将其顺序存储到一个链表结构里面；

为了从 query 关联到对应的链表，我们可以用 hash table 或者 trie。剩下的就是处理两个 list 的交、并实现 and/or 的逻辑，事实上使用按照 doc ID 排序后的链表取交可以使用类似 merge sort 中 merge 的策略，类似的实现并也可如此。那么如果要实现“非”，也可以类似处理，只是判断是否出现在取非的部分。

有了这么一个概念，剩下的就是细化里面的一些步骤，比如抽取单词，这部分我们一般需要一些 NLP 的工具做 tokenize 获得一个一个的 token，然后根据语言做 stemming/lemmatization 这样一些 normalization 的步骤（如大小写转换）。对某些特定的问题，我们知道 stop words 可以在这个过程中去掉避免产生的 posting list 过长。为了加速 posting list 的遍历，往往加入所谓 skip pointers，将 list 分段，如每隔长度的算术平方根个 doc 加一个跳转。那么比较精细的做法往往会存下该词出现在某个文档中的频率甚至位置列表。加入这些东西以后可以做 proximity search（指定单词之间的距离不能超过多少）。

我们可以为某些 search 提供一个字典方便加入对含有 wildcard 类型 query 的支持，这一般会使用 search tree（通过前缀获得）。另一方面我们也会引入 edit distance（也叫 Levenshtein 距离）对输入有误的 query 进行修正。

建立好一个 index 需要动态的维护是一个相对较复杂的问题。增加我们可以继续前面类似的操作；删除一般需要维护一个删除列表，在合适的时候移除（lazy delete 策略）；头疼的是更新 =.=

存放的 dictionary、index 均可以用某种方式进行压缩，因此有必要研究各种分布。通常认为语料的大小 $T$ 与字典的大小 $M$ 满足 heap’s law，即 $M = kT^b$ ；各个文档中间依照词频排序后对应的比例关系满足 Zipf’s

law，即

。编码方式往往可以利用前缀性质和变长编码。

开源的 lucene为我们提供了一
套建立 boolean retrieval 的机制。我们可以使用 lucene 提供的简单的命令行为一个目录下面的文件建立 index，

java org.apache.lucene.demo.IndexFiles -docs your-docs-dir
java org.apache.lucene.demo.SearchFiles

进行搜索，如果希望修改已有的建立索引、搜索的流程，可以看看对应文件的源代码。

Please read full article from An Introduction to Information Retrieval 读书笔记（一）

Matrix Multiply - 矩阵乘法

两个矩阵 A，B：A 的列数等于 B 的行数，则A、B可以相乘。即，如果 A = （a_ij）是一个m * n的矩阵，B =（b_jk）是一个 n * p 的矩阵，则它们的乘积 C = AB 是 m * p 矩阵 C = （c_ik）。

学过计算机图形学，会发现，不管是二维图形的平移，旋转，缩放，三维图形的取景变换，投影变换等都是通过矩阵乘法来实现，例如，二维点P（x，y）平移（tx，ty）后得到 P’(x’，y’)，可以通过矩阵计算：

$\begin{pmatrix} x'\\ y'\\ 1 \end{pmatrix}= \begin{pmatrix} 1 & 0 & tx\\ 0 & 1 & ty\\ 0 & 0 & 1 \end{pmatrix}\begin{pmatrix} x\\ y\\ 1 \end{pmatrix}$

求矩阵相乘的通用公式为：

$AB_{ij} = \sum_{r = 1}^{n}a_{ir}b_{rj} =a_{i1}b_{1j} + a_{i2}b_{2j}+……+a_{in}+b_{nj}$

还有一个常见用法，求斐波那契数列：

$\inline \begin{pmatrix} 1 & 1\\ 1& 0 \end{pmatrix} * \begin{pmatrix} Fi\\ Fi-1 \end{pmatrix} = \begin{pmatrix} Fi + Fi-1\\ Fi \end{pmatrix} = \begin{pmatrix} Fi+1\\ Fi \end{pmatrix}$

$\inline \begin{vmatrix} 1 &1 \\ 1 & 0 \end{vmatrix} * \begin{vmatrix} 8\\ 5 \end{vmatrix}=\begin{vmatrix} 13\\ 8 \end{vmatrix}$

所以当求 Fn 时可以用求幂来快速求出，而求幂也是建立在矩阵乘法的基础上：

$\begin{vmatrix} 1 &1 \\ 1&0 \end{vmatrix} * \begin{vmatrix} 1 &1 \\ 1&0 \end{vmatrix} * \begin{vmatrix} 1 &1 \\ 1&0 \end{vmatrix} * ……* \begin{vmatrix} 1 &1 \\ 1&0 \end{vmatrix} * \begin{vmatrix} F1\\ F0 \end{vmatrix} = \begin{vmatrix} Fn\\ Fn-1 \end{vmatrix}$

$\inline A = \begin{vmatrix} F1\\ F0 \end{vmatrix}B =\begin{vmatrix} 1 &1 \\ 1& 0 \end{vmatrix}C = \begin{vmatrix} Fn\\ Fn-1 \end{vmatrix}$

$C = B^{n-1}*A$

矩阵相乘有两种方法，普通的矩阵乘法（Matrix Multiply）和Strassen算法。

最普通的矩阵乘法

Matrix operator * (Matrix a, Matrix b) {

    Matrix ret; 

    ret.init(a.n, b.m);

    for (int i = 0; i < a.n; i++) {

        for (int k = 0; k < a.m; k++) if (a.mat[i][k]) {

            for (int j = 0; j < b.m; j++) if (b.mat[k][j]) {

                ret.mat[i][j] = ret.mat[i][j] + a.mat[i][k] * b.mat[k][j];  

                if (ret.mat[i][j] >= mod) {

                    ret.mat[i][j] %= mod;

                }//if

            }//for(j)

        }//for(k)

    }//for(i)

    return ret;

}//乘法

矩阵加法只需简单的将两个矩阵的元素相加：

Matrix operator + (Matrix a, Matrix b) {

    Matrix ret; 

    ret.init(a.n, a.m);

    for (int i = 0; i < a.n; i++) {

        for (int j = 0; j < a.m; j++) {

            ret.mat[i][j] = a.mat[i][j] + b.mat[i][j];

            if (ret.mat[i][j] >= mod) {

                ret.mat[i][j] %= mod;

}

}

}

    return ret;

}//加法

矩阵求幂

Matrix operator ^ (Matrix a, int b) {

    Matrix ret = a,  tmp = a;

    ret.init_e();

    for ( ; b; b >>= 1) {

        if (b & 1) {

            ret = ret * tmp;

}

        tmp = tmp * tmp;

}

    return ret;

}//

幂求和，即求S = A + A² + A³ +… + A^k ，同样的二分思想，但是利用递归，可以很快求出：

//递归幂求和

//用二分法求矩阵和,递归实现  

Matrix Power_Sum1(Matrix a, int b) {

    Matrix ret = a;

    ret.init_e();

    if (b == 1) {

        return a;

    } else if (b & 1) {

        return (a ^ b) + Power_Sum1(a, b - 1);

    } else {

        return Power_Sum1(a, b >> 1) * ((a ^ (b >> 1)) + ret);

}

}

//非递归幂求和

Matrix Power_Sum2(Matrix a, int b) {

    int k = 0 ,ss[32];

    Matrix tp1, tp2, ret;

    tp1 = tp2 = ret = a;

    ret.init_e();

    while (b) { 

        ss[k++] = b & 1;

        b >>= 1;

}

    for (int i = k - 2; i >= 0; i--) {

        tp1 = tp1 * (tp2 + ret);

        tp2 = tp2 * tp2;

        if (ss[i]) {

            tp2 = tp2 * a;

            tp1 = tp1 + tp2;

}

}

    return tp1;

}

二、Strassen算法

Strassen算法核心思想是分治，是一种递归算法，运行时间为O（n^lg7） = O（n^2.81），当 n 很大时，优化很明显，在普通的矩阵乘法中，C = A * B，按照：

$C[i,j] = \sum_{k = 1}^{n}A[i, k] * B[k, j]$

每计算一个元素C[i，j]，需要做 n 个乘法和 n – 1 次加法。因此，求出矩阵 C 的 n²个元素所需的计算时间为0（n^3）。Strassen算法的分治体现在：假设 n 是 2 的幂，将将矩阵A，B和C中每一矩阵都分块成为 4 个大小相等的子矩阵，每个子矩阵都是n / 2 × n / 2的方阵。由此可将方程C = AB重写为:

$\begin{vmatrix} C_{0} &C_{1}\\ C_{2} &C_{3} \end{vmatrix} = \begin{vmatrix} A_{0} &A_{1}\\ A_{2} &A_{3} \end{vmatrix} \times \begin{vmatrix} B_{0} &B_{1}\\ B_{2} &B_{3} \end{vmatrix}$

由此可得

$C_{0} = A_{0} * B_{0} + A_{1} * B_{2}\\~~~~~ C_{1} = A_{0} * B_{1} + A_{1} * B_{3}\\~~~~~ C_{2} = A_{2} * B_{0} + A_{3} * B_{2}\\~~~~~ C_{3} = A_{2} * B_{1} + A_{3} * B_{3}$

可以看出，进行了8次乘法，4次加法，当子矩阵的阶大于2时，为求2个子矩阵的积，可以继续将子矩阵分块，直到子矩阵的阶降为2，利用这个简单的分治策略，最后可以得出：T（n） = 8T（n / 2) + O（n²），但是这个式子的解任然为T（n）= O（n³），和普通的方法效率一样，没有任何提高，原因是上边的四个式子并没有减少矩阵乘法的次数（乘法极其耗费时间，学过底层二进制计算的，必然了解，而加减操作非常轻松），所以改进算法的关键是，减少乘法次数。

Strassen算法的高效之处，就在于，它成功的减少了乘法次数，将8次乘法，减少到7次。不要小看这减少的一次，每递归计算一次，效率就可以提高1 / 8，比如一个大的矩阵递归5次后，（7 / 8）⁵ = 0.5129，效率提升一倍。不过，这只是理论值，实际情况中，有隐含开销，并不是最常用算法，《算法导论》中给出四条理由：1）隐含的常数因子比简单的O（n3）方法中的常数因子要大。2）矩阵是稀疏矩阵时，为稀疏矩阵设计的方法更快。还有两点已经被缓解，可以不考虑。所以，稠密矩阵上的快速矩阵乘法实现一般采用Strassen算法。

M1 = (A0 + A3) × (B0 + B3)

M2 = (A2 + A3) × B0

M3 = A0 × (B1 – B3)

M4 = A3 × (B2 – B0)

M5 = (A0 + A1) × B3

M6 = (A2 – A0) × (B0 + B1)

M7 = (A1 – A3) × (B2 + B3)

C0 = M1 + M4 – M5 + M7

C1 = M3 + M5

C2 = M2 + M4

C3 = M1 – M2 + M3 + M6

求解M1，……，M7总共7次乘法，其他都是加法和减法，比如将C0扩展开后，最后结果是，C0 = A0 * B0 + A1 * B2，《算法导论》里有一句奇怪的话：“现在我们还不清楚Strassen当时是如何找出算法正常运行的关键——子矩阵乘积”，一次乘法的消失过程真的这么吊诡？

Please read full article from Matrix Multiply - 矩阵乘法