| kobe's profileKobeSoftPhotosBlogLists |  Tools  Help |
|
July 29 奔腾不再 时间很有限，可是还是忍不住写一点，说起奔腾，对于我们这一代的人来说简直就是像初恋情人一样另人回味，如今，它就要走了，怎么能不撰文加以纪念呢？
奔腾前传：
最早玩电脑还是那土土的苹果机，那时还经常传出某某学生因为多动了一下键盘，被老师从机房拖出去的事（可能那时候的机器对于老师学校来说太重要了）。自己拥有的第一台电脑是94年的80486 DX66，记得那时候最开心的事就是带一堆软盘到同学家去考游戏。这台电脑带给我的最大收获就是熟练的掌握了使用PC TOOLS,GAMEMASTER改游戏，无论是改游戏存档还是改内存数据（当时并不知道数据是放内存里的）都练的巨熟。 奔腾一： 95年到，WINDOWS95来了，记得那时有几个几年前就能用GWBASIC写猫捉老鼠游戏的能人，天天讨论着WIN95安装啥的，我却还傻傻享受着我的DOS游戏。中考结束，我利用假期把仙剑穿了三遍，抽出时间陪同学一起疯狂的赶装机疯，奔腾133是那时候的主流，内存的主流是16M，不少同学买奔133的唯一目的就是能装WIN95、能玩超时空游俠、古墓丽影。96年初，vincent家装了个P166，32M内存，我那个羡慕啊，至今清晰得记得从村里带回的那块芯片的价格：3600 RMB 奔腾二： 你是否还记得那个奔腾MMX的广告，穿着五颜六色衣服的太空人代表着多媒体时代。不过那时的我转向了TV GAME，整天琢磨的是SFC、MD，和这个奔二的时代几乎毫无关系。不过在一个暑假里，为了能玩新出的FIFA98，我去村里租了一台P2 233，终于搭上了P2的末班车。 奔腾三： 上大学了，终于攒足了足够的理由说服家里更新电脑，舍去那台心爱的DX66,迎来了新宠P3 550。这台电脑太重要了，我终于不用再去网吧实现红警、星际梦了。尽管后来这台电脑被我使的连风扇都不转了，我还是强忍着主板的温度报警，硬是把它虐到了大四毕业。其实它更多的贡献是，我在它身上学到了编程，并利用编程赚到了一生第一笔自己的钱。真要谢谢这个P3兄弟了。 奔三维持了多年，不知从什么时候开始，几年前想都不敢想的1G主频，现在已经成为了现实，128M的内存居然成为了过时配置，连买显卡都要看显存了。这就是奔四时代的到来。大学里的买电脑潮，几乎都是围绕奔三展开的，会攒台电脑简直是那时候很自豪的一件事，尤其在泡妞时贼管用（经常有女生打电话过来，能帮我攒台电脑吗），和海龙的小商小贩斗智斗勇也成为了家常便饭。 奔三带来了网络，人们知道了上网，知道了伊妹，知道了QQ，同时害怕起了"黑客"无聊的累；奔三带来了游戏，人们知道了红警，知道了星际，知道了暴雪，同时包起了网吧老板的夜；奔三带来了网游，人们知道了MUD，知道了传奇，知道了奇迹，同时养肥了个叫陈天桥的人。 各色各样的人在奔三的时代里有失有得。 奔腾四： 随着大四即将技术，同学中逐渐有了奔四1.5、1.7，我的奔四时代是随着那台P4 2.2的笔记本来的，并伴随了我三年多。 奔腾不再：
终于等到了奔腾不再奔腾的这一天，随着热闹的双核时代到来，它被宣布要离我们远去了，“酷睿2”马上登场了。整整十年，1996到2006，奔腾这个词伴随了80一代的成长，使我们能够自恋地保持着时代青年的称谓。在这棵叫奔腾的芯片上，不仅仅跑着Gates的宝贝和亿万的程序，它安慰了多少人的孤独，享受了多少人的无聊，赐给了多少人的欢愉，沟通了多少人的世界，承载了多少人的梦想，带来了多少人的财富。 可以肯定的是，我的下一台电脑将不会再有奔腾的标志，也许就连那个Intel Inside都不会出现，没准换成了Intel Outside & AMD instead，但是Intel奔腾带给我们的记忆是无论如何也抹不掉的。 谢谢你，奔腾！ July 17 算法心经.数学的应用.微分的应用终于有了空闲，来写微分的应用，有一点怎么强调都不过分，限于本人水平有限，可能你觉得的很重要的应用或者很常见的应用，我这里并没有提及，那么请你跟贴或者给我写信，帮我完善一下，谢先。 讲微分的应用，一定要先看微分的意义；微分的意义在很多方面有很多种解释，比如在直线上可以理解为斜率，曲线上经过再求导可以扩展为曲率等。不过我想有一点意义应该是几乎本质的，那就是微分是求一个对象对另一对象的变化程度，换句话说可以理解为一对象对一个对象的影响。比如就X2来说： X2对X求导=2x，说明其对于X的变化率为2X X2对X2求导=1，说明X2永远和X2相等 上面的话，尤其第二句几乎废话，不过可以更好的揭示这个性质，那就是求导微分并不能只理解对对X求导套公式，其内涵为对任何一个对象的变化程度。 有了这个理解，我们来看一个具体的应用，来推导一下伟大的神经元学习网络的误差反传算法。 写过这个误差反传算法的人，可能不计其数，不过真正理解这个公式的来源的人就不多，原因就是归结于书上那些复杂的数学符号，下面对该问题的分析中，我不会写一个数学公式，完全用大白话来show一下微分的威力。 分析误差反传算法，有一个必须的步骤，就是理解梯度下降算法，梯度下降很好理解，就是要求最优值的时候永远沿着正比且与导数符号相反的方向就能逼近最优值。这句话不好理解，确实我打出来都费劲，但举一个例子就明白了，有一座山谷，我们要寻找这个山谷的最低点，那么就必须在下坡时，一直往前走，但是很遗憾，我们可能走过了这个点，那么当再上坡时（走过了），往回走。而每次走的距离都和坡度成正比，可以想象，当快到山谷时，那里几乎平地了，坡度很小，自然我们的步伐也变慢了，这样反复的逼近最优值。 这种逼近迭代的思想太重要，它贯彻了数值分析的始终。这种思想再升华就是，最优算法我求不出来，但我知道改进的方向。熟悉图论的朋友马上就想到了，其实图论里面最大流、最大匹配、最佳匹配，很多思想都源与此，可以说不管是数值算法还是非数值算法，有些精髓是相通的。 转回来再说梯度下降，有下降就有上升，的确，就像上山，每次都沿着坡度走，直到找到最高峰，这也是SVM最优算法的实现方法之一。 过了梯度下降这关，剩下的就好说了，神经元网络的表现实质是啥？是用一堆权值矩阵，来模拟线性或者非线性的式子。 A D B E C F A、B、C代表n层的三个节点，D、E、F代表n+1层的三个节点，假设A、B、C就是输入，D、E、F就是输出，那么输入输出的关系就是用A、B、C到D、E、F这个3*3的权值矩阵来模拟的，怎么模拟？ D=A*w11+ B*w21 + C*w31 E=A*w12 + B*w22 + C*w32 F=A*13 + B*w23 + C*w33 我们想要的结果就是适合的w11到w33这9个权值，可以达到我们模拟输出的效果。 伟大的思想往往在算法设计时起到指导作用，我们不知道怎么选这9个权值，但是如果给权值们一个初值，而以后按照改进的方向走，次次迭代，逼近我们想要的理想结果，不就达到目的了嘛。 现在思路有了，给权值初值，然后按照一定的原则对权值做修改，直到收敛。 但是，怎么修改呢，按照爬山的想法，我们得按照坡度的方向来走，那么到这里的应用，就是按照误差对权值到微分来走。误差就是最终的输出结果和我们的D、E、F得到结果的平方差。其实具体到平方差不平方差都不重要，重要的是误差是由D、E、F来计算的。 现在我们的目的就是求误差对w11到w33的微分，以w11为例： A -w11-> D A通过w11作用到D，那么误差对w11的导，可以看成误差对D的导，再乘以D对w11的导（这是微分方程里面一个常用技巧） D对w11的导，很好求，用我们开始的微分意义来说，就是w11对D的影响，很显然是A，因为w11只通过A对D有影响；那么剩下的唯一的关键就是如何求误差对D的导数了。 如果D是最后一层，那么该值很明显，直接拿误差的式子（比如平方和）对D求到即可。但是如果D所在的不是最后一层，那么误差对D求导怎么办呢？（因为误差是最后一层，所以当D是中间层是不好办）
注意了，误差反传这四个字的意义就来源于下面的解释： “当一个对象X，通过一些代理对象，对另一个对象Y起作用时，那么对象X对对象Y的作用实际就是代理对象对Y的作用之和对X的微分” 等价这里： “当D，通过下一层的节点们H、I、G，对误差起作用时，那么D对误差的作用，实际上就是H、I、G对误差的作用之和对D的微分” 如果不理解没关系，只要能看懂有这个意思即可，就是求D对误差的作用，就必须要求D的下一层的节点们对误差的作用，而求D的下一层的节点对误差的作用，就要求下下层对误差的作用，依此往后推。而最后一层的误差对节点的作用最好求，所以才会从最后一层计算误差。 这就是误差反传的来历。 再举一个俗例子做补充，一个杂技表演有几个人组成，这个杂技表演失误的概率实际上是由这几个人各自的失误的概率来影响的，那么杂技表演的误差概率就得从这几个人的失误概率往下推，等理于误差反传。
这个神经元网络的公式推导，是我所能想到的最完美体现微分涵义的实际软件应用，从梯度下降到误差反传，无一不深度包含这微分运算的数学本质。 当然，作为高等数学基础中基础的微分，对于很多理论都有基础作用，泰勒公式、拉格朗日中值，都以微分做起点，这里不做介绍了。高数中考高分容易，但是能把高等数学思想和计算机程序设计联系起来就不那么简单了，这也就是那些大师为什么称做大师的原因吧。 下篇：概率的应用 July 09 算法心经.数学的应用.积分的应用算法心经：
前几天，一个好友告诉我，他要写一本书，叫《编程低手箴言》，我马上管他要地址去看看，出乎意料，写得比我想象得好。后来我就自己在想，是不是也应该把我平时的一些心得写出来呢？越越冲动，既然有了想法，那内容选什么呢？既然讲给别人听，就要拿自己拿手的，也就是最有把握的，要不一贴出来被人们拍死就麻烦了。所以，我把题材选为了讲算法，名字嘛，就姑且叫《算法心经》好了。 写出点东西，勇气是必不可少的，像CSDN有个知名作者，写过一个什么关于矩阵的新见解，马上被无数潜水的高手们拍得半死，其实我一看很多的批评也没什么道理，即使有道理的也纠缠在名字这种taste differ的范围内，不过因为缺少勇气，他再也不出这个矩阵的续篇了。我就不同，也许差点水平，但绝不差勇气。写这个东东除了给别人看外，也是对自己平时遇到的一些很有意思的问题的总结，如果大家发现了什么不妥，请马上帮我指出来。 讲算法的资料太多了，大多老一套，贪婪、分枝、限界等，如果想按这个套路学，那大家都去看MIT的算法导论好了，我再写出来也是copy。既然是原创，就要有点新意，下面的内容完全按我对各种算法的思路总结来整理，保证您看着一个与众不同。另外介于本人的水平有限，所有例子只对我碰上读过的感觉有用的问题举例，嫌不够深入的朋友抱歉。 废话少说，开始... 一，数学的应用：
我在抱本数学书看时，经常有同学问我，“看这玩意干啥子？“我答曰：”有用“，又问：“有啥用”，我托腮沉思半天，只挤出“反正有用”这种教条结论。的确，地球人都知道数学和计算机关系暧昧，但具体到哪有交集，又说不清楚，我看可能有两个原因：1，还不到能理解到数学用处的水平。2，使数学后，没有归纳总结。我想大多数人属于后者，为了弥补这点，我把平时用到数学的地方总结出来，让大家看看数学的威力。 积分的应用
微积分是高等数学的基础，但我们搞程序的平时使到微积分的时候实在少之又少，反正我大四以前根本没有用到微积分（编写什么插值求积分那种程序不算），果真如此吗？？？ 微积分的威力发挥在算法分析上，你会算法分析吗？会的话，肯定会体会到。看看积分的例子： “有一个无序数列，每次遍历整个数列查找一个数，然后删除之，重复这个步骤直到数列为空，问这个算法的效率？” 这个你一眼就看出效率了，遍历的次数从1个增加到n个，那么平均是n/2个，一共执行n次，所以效率是n*n/2，也就是O(n*n)，呵呵，很简单，惬意的笑。但细想一想，为什么这里能把n除以2呢？是因为n是个线性函数，所以在计算时可以用它的中间值来计算。这种中间值概念的应用很普遍，很多算法效率的计算有需要，回忆在quick sort的效率分析里，因为整个数列里的每个数与第一个数（比较数）交换的概率相同，那就是绝对的线性关系（函数为常数），所以才可以用，2*T(k)代替T(k)+T(n-k)。 其实这题也可以用积分来算，效率实际上就是把n在1到n上取积分，也就是n*n/2，和先前的答案一样，注意这里，积分本身是一个连续的数学概念，这里扩展到离散求积分。
我们把上面的例子改改： “有一个有序数列，每次用二分查找找到其中一个值，删除之，重复这个步骤直到数列为空，问这个算法的效率？“ 想啊想啊，二分效率是log(n)，从log(n)降到log(1)，那么和先前的一样，效率是中间值*n，就是log(n)/2*n，也就是O(n*log(n))，我赶紧握着你的手说，“恭喜你，蒙对了！”，最终的答案确实是O(n*log(n))，但绝不是这么出来的，因为log函数不是线性函数，你绝对不能用中间值代替来进行计算。 哦！那该怎么计算呢？积分来了。上面的算法实际是对log操作从1增加到n，在数学上实际是离散的对log函数做1到n的积分，也就是对log(n)积分。那log(n)的积分怎么算呢？用Udi的《算法导引》的估计法，我们先估计其积分是n*n，我们对n*n求导 D(n*n)=2*n>log(n) 我们的估计大了，那么是不是n*log(n)呢？ D(n*log(n)) = D(n)*log(n) + n*D(log(n)) = log(n)+ n*1/n=log(n) +1 哇！我们对了，n*log(n)求导就是log(n)再和一个常数相加，于是可以判断log(n)的积分就是和n*log(n)一个等级的，于是，答案出来了，这个算法的效率是n*log(n)，这就是积分的威力。 下节我们来看微分的应用... July 02 毕业论文：搜索引擎欢迎大家下载阅读并交流，说明4点：
1，基于论文的写作要求，有些冗余内容，推荐以PPT为主，WORD文件为辅
2，增强摘要算法，空闲文件偏移分配（为解决定长索引结构的空白区域问题）为新增内容，未在论文和PPT中提及
3，由于在写作中认识的不断加深，对于二级索引的定义有些模糊，现统一为对一级索引表的次关键码索引仍为一级索引，对一级索引文件进行分段索引为二级索引
4，分词内容参考ICTCLAS论文
阅读指引 创新点：
1，UNICODE文件名系统
2，散列二级索引结构
3，PAGERANK二维函数收敛
4，矩阵法网页排重
阅读指引 目录：
第一章 绪论 1
1.1 正则匹配 1
1.2 递推下降分析 2 1.3 隐马模型 3 1.4 索引数据库 4 1.5 数值计算矩阵特征向量 6 1.6 MVC模式 7 1.7 WINDOWS进程通信 9 第二章 系统总体设计 12
2.1 问题的提出 12
2.2 系统总体结构 14 第三章 系统详细设计与实现 17
3.1 网络蜘蛛 17
3.1.1 网络蜘蛛的实现 17 3.1.2. 网络蜘蛛的特点 18 3.2 多线程下载模块 19 3.2.1 下载模块工作流程 19 3.2.2 线程队列分配 19 3.2.3 UNICODE文件名操作 21 3.3 HTML语法解析器 22 3.5.1 语法解析器的目的 22 3.3.2 语法解析器的实现 23 3.4 分词 25 3.5 二级索引数据库 27 3.5.1 二级索引结构的实现 27 3.5.2 结构增强 29 3.5.3 性能评估 30 3.6 Web Service 31 3.6.1 性能评估 32 3.6.2 摘要算法 32 3.7 划词搜索 34 3.8 Pagerank 36 3.8.1 PAGERANK概念 36 3.8.2 计算Pagerank 37 3.8.3 二维线性收敛方法 39 3.8.4 测试结果 40 3.9 HITS算法 42 3.9.1 HITS算法的提出 42 3.9.2 HITS算法的实现 45 3.10 网页排重 47 第四章 结论 50
附 录 53
致 谢 60
研究成果及发表的学术论文 61
作 者 和 导 师 简 介 62
|
|
|
