Category Archives: 程序

使用Matrix67的数据挖掘方法为博客作用词分析

今天早上看到Matrix67的《互联网时代的社会语言学:基于SNS的文本数据挖掘》一文,如获至宝。我很久以前也做过人人网流行的日志中喜欢用哪些词的 实验,不过仅仅使用程序抓取网页和获取二字组合,然后还要依靠人工来筛选正确的词语,这种方法效果并不好,而且最后也没能得出什么非常有趣的结论;而 Matrix67这篇文章非常通俗地讲解了作者使用的中文抽词方法和热度分析方法,这些方法巧妙却不复杂,得到的效果还相当不错,使我不可救药地踏上了亲 自把它实现一遍的征程上。

首先我用Python实现了Matrix67的中文抽词方法,并把这种方法应用在自己博客的rss上,然后把抽取得到的词语按照出现频率排序,得到的结果如下:

什么,我们,自己,大学,东西,可以,没有,作业,我的大学,所以,如果,时间,因为,文章,那么,现在,其实,大作业,比如,知道,障碍,代码……

看起来效果非常不错,于是我又尝试了另外几位朋友的博客。首先是橘子的,结果如下:

面试,公司,然后,什么,最后,没有,开始,应该,时间,测试,题目,这样,项目,怎么,大家,我们,自己,香港,由于,可以,实习,其实……

以及sqybi童鞋的:

算法,没有,诚哥,言叶,世界,置换,页面,可以,网页,自己,内存,如果,已经,所以,列表,我们,之后,因为,什么,开始,那么,过程,页面置换……

(一开始看到“诚哥”这个词语我还以为是哪里抽词出错了,后来仔细看了下sqybi童鞋的博客发现原来这个真的是个词语……)

这段程序的源代码被我放在了gist的上面,有兴趣的同学可以猛击这里。 抽词的结果非常好,但是这个结果还是有些问题:一是直接访问博客的rss只能获取最近10篇左右的文章,样本太小,不能充分反映这个博客的特点;二是各个 博客得到的抽词结果中出现频率较高的一般都是像“可以”、“没有”、“什么”这类非常常用的词语,不同的博客之间的差异不能够鲜明地反应出来。解决前一个 问题的方法是使用Google Reader,在浏览器中输入”http://www.google.com/reader/atom/feed/http://www.liyaos.com/blog/feed?n=100″这种链接便可以获取一个博客最近的100篇文章(需要先登录Google Reader,这使得直接用程序访问变得有点麻烦,不过我直接采用了在浏览器打开这个页面然后保存到本地,再用程序读取),格式为Atom,和rss很 像,也都可以使用Python的feedparser来轻松解析。解决后一个问题,则是Matrix67的文章后半部分提到的贝叶斯方法。

于是我使用前面的程序分析了以下数个博客(排名不分先后,嗯 = =):

把以上博客分析的所有结果作为总的词语库,然后再对每个博客使用Matrix67的文章中给出的概率公式进行计算,然后把得到的词语按照其概率值从大到小排序。以上博客的词语前10名分别为:

优哉·幽斋

我的大学,寻欢,词语,诗音,一段,梦里醉逍遥,大哥,中国人,学期,障碍

(“我的大学”来自《我的大学》系列,“寻欢”、“诗音”和“大哥”来自《多情码农无情码》)

SQYBI.COM

赫萝,诚哥,言叶,你们,罗伦斯,方茴,安竹,季安竹,李暮霭,远子学姐

(……这些都是什么啊……)

伸手即到梦想

期末,接着,成都,排队,假期,实习,福州,香港,世博,一趟

(显然高富帅的生活很丰富啊 = =)

静观己心,厚积薄发

太太,奶奶,三奶奶,姑娘,丫头,未央,老太太,三太太,笑道,素馨

(……………………我快笑惨了)

非人磨墨墨磨人

一个,成为,冯至,拉里,袁枚,里尔克,毛姆,那样,文学,十四

(虽然不知道博主在说什么,但是看起来好厉害的样子)

学而时嘻之

学家,根本,能力,原子,经济学,际上,最好,我认为,科研,辐射

(这篇博客的文章里讲什么学家的都有……所以“学家”就被当作词了,看来是信息熵的阈值还不够大,不过我的实验样本也不够大所以把阈值调大效果不一定会更好……)

宇宙的心弦

原理,怪物,动量,定义,几何,力学,角动量,收益,量子,液氮

(一看就知道学什么的……)

考据癖

考据,起床,笑声,星期五,胡克,培根,说法,蚊子,发音,星座

(考据癖什么都考啊……)

嗯,这个结果相当有趣的吧。

PS:本来还想拿来韩寒、蒋方舟的博客分析一下,但是这两个家伙的新浪博客都不提供全文阅读,只好作罢。

Common Lisp学习笔记(1):语法和语义

按:本文是我在阅读Peter Seibel所著的Common Lisp教程Practical Common Lisp(免费在线阅读地址:http://gigamonkeys.com/book/)的学习笔记。本篇主要依据于原书的第四章Syntax and Semantics,主要的内容也如其题目所描述,是Common Lisp的语法和语义。

之前已经在这个博客上发表过《Common Lisp学习笔记(0):从SLIME开始》,不过后来由于课业比较忙,虽然还是能抽出些时间继续阅读这本书,但是一直没来得及写一些后续的笔记。而在这期间,我发现竟然有一位名叫田春的程序员翻译了这本书,并且在今年10月出版,于是我也购买了这本书。既然前面阅读英文原版得到的东西在现在已经记得不太牢靠,我打算凭借这本中译本来帮助我回忆这些内容,形成这些笔记,同时我依然会拿英文原版做对照。

注意虽然Common Lisp是Lisp的一种方言,二者并不相等,不过为了方便起见下文中我不会对Common Lisp和Lisp做太多刻意区分,大多数情况下以Lisp代指Common Lisp。

目录

Continue reading

Common Lisp学习笔记(0):从SLIME开始

按:本文是我在阅读Peter Seibel所著的Common Lisp教程Practical Common Lisp(免费在线阅读地址:http://gigamonkeys.com/book/)的学习笔记。这篇文章的主要内容包括Common Lisp的介绍以及如何搭建Common Lisp编程环境(SBCL + Emacs + SLIME)两部分。因为本文并不怎么涉及Common Lisp的具体知识,所以编号为0。

目录

Continue reading

Fedora 15搭建LAMP环境中可能遇到的问题

LAMP是Linux + Apache + MySQL + PHP这组黄金组合的简称,在网站开发中极为流行。在Fedora这个红帽系的Linux发行版下面搭建LAMP环境是非常简单的,只需要使用yum就可以轻松安装Apache、MySQL以及PHP。但是实际上仅仅使用yum安装这些东西往往是不够的,譬如你可能会发现你所安装的PHP缺少很多扩展,或者MySQL数据库里的表名存在大小写敏感不符合你的习惯,或者在Apache对文件的读写权限上遇到一些非所期的结果,等等。这篇文章记录了一些我在自己的Fedora 15系统上搭建LAMP环境时所遇到的问题和最后的解决方法,因为我这人比较懒散,所以这些方法都是我自己看来最简单的解决方法。其他Linux发行版也可以以此为参考(只是参考!)。

索引:

Continue reading

寻找只出现了2次的数字

在一个存放着数字的数组里,有一个数字出现了2次,其余的都出现了3次,如何找到那个出现了2次的数字?

这是在知乎上看到的一个很有趣的问题。 看到这题我立刻就想到了另一个经典的问题,即在一堆数据里,有一个数字出现了奇数次,其他数据都出现了偶数次,如何找到那个出现了奇数次的数据?一个正常 人的第一反应九成九是哈希,但是事实上这个问题存在一个非常简单、而且时间复杂度非常低的方法,即把所有的数据异或起来,最后的结果就是我们要找的数据。

这个方法乍看也许很玄妙,但其实原理很简单,即两个相同的数异或的结果是0。把所有的数据异或起来,出现了偶数次的数据都在自己和自己异或的过程中湮灭了,于是最后只剩下那个出现了奇数次的数据站在那儿茕茕孑立。

但是如果某个数组里只有一个数出现了为偶数的2次,其余的都出现了为奇数的3次应该怎么办?我一开始囿于成见想了很久怎么用异或来做这件事情,最终 结果是恍然悟出我在做一件多么愚蠢的事情——异或的结果只能让我们想要找的那个数变得如羚羊挂角,无迹可求。想要不借助于哈希这种无聊的办法而得到这题的 答案,必须要使用一种运算让一个数一但出现了3次,就会自我抵消掉。

下面的这个办法不是我想出来的,而是知乎上的一位牛人所给出的。即把所有的数据当作一个3进制数,然后在每一位上,把所有的数据这一位的3进制数加起来,乘以2再对3取模,最后得到的3进制数的值(也就是对应的10进制数)就是我们需要的答案。

这个巧妙算法的原理同样也很简单。一个数字如果出现了3次,那么把3个它加起来一定是3的倍数,即对3取模为0。但是如果一股脑把所有数据加起来再 对3取模,我们只能得到0,1,2三种值,明显离我们的答案存在的可能性相差甚远。所以这个方法又采取了另一个巧妙的思想即把所有数据看作3进制数,然后 在每一位上利用这个原理来处理。这和之前我们提到的那个题目用二进制运算异或有异曲同工之妙。

下面是我用ruby写的一种该算法的实现,具体的实现细节可能和原算法所描述的稍有不同,但主要思想是一致的。

事实上在这个问题上我们还能更进一步地思考,如果一陀数据里只有一个数出现了偶数次,其余的数都出现了奇数次,如何找到那个出现了偶数次的数据?欢迎各位在这里给出你思考的答案。

人人网最流行的那些日志都用什么词

今天读书的时候被启发,想要写一个程序校内网蛋疼文章过滤器,写了一部分发现工作量有点大。恰恰想起过去曾经读到过一篇叫《东风何处是人间》的很有意思的文章,于是转念一想,正好拿起前面写了一部分的程序统计了下校内上那些分享量最高的日志的用词频率。

我用python写了一个程序抓取校内分享栏目里给出的分享量最高的120篇文章,然后对其中所有两字词的出现频率进行统计,最后排序并进行人工筛选。于是这篇《人人网最流行的那些日志都用什么词》出炉了!下面给出统计结果,本人不作任何评论;源代码则附在文章的最后,各位可以在此基础上进一步发掘(以及,我不保证我写的代码没bug……)。

实意名词TOP15:

1,帅哥,295次

2,男人,184次

3,中国,178次

4,孩子,174次

5,蟑螂,171次

6,女人,140次

7,韩国,136次

8,朋友,135次

9,世界,118次

10,时间,113次

11,咖啡,108次

11,妈妈,108次

13,生活,97次

14,永远,96次

15,幸福,95次

注:虽然这里把这些词语算作实意名词,但实际上在文中出现的时候它们未必是以名词形式出现的,譬如“永远”一词,想必大多数出现都不是名词;又如“生活”一词,既可以是名词又可以是动词,所以它在此榜单和下面一张榜单上都有名字。

Continue reading

《如果要我出程设题》官方参考答案

前几天作《如果要我出程设题》,本漫思所启而作,不意众猿兄媛妹抬爱,竟得一时风靡。然原文实乃随笔所作,多有未审之处,网上诸君引经而论,竟见余 之所未见,发余之所未发,实令余既难免汗颜之处,亦多有拜服之叹,故知浩哉华夏,吾道不孤。今撰此参考答案一份,虽以官方之名,终是一家之言,唯送诸此嚣 嚣尘世,以待高士斧正。

题目原文链接:http://liyaos.com/blog/programexam/

一,选择题:

1, ABC皆对。这题只是送分而已,不同的角度看待二进制思想这一名词,自会得出不同的答案。伏羲氏以阴阳两爻和天地人三才创立先天八卦阵,可以看作是 3bit的二进制数,即二进制思想之启蒙;但伏羲氏毕竟是传说中的人物,而后世作后天八卦阵以及推演周易六十四卦的周文王不但在历史上的可信程度大了很 多,而且还把3bit二进制数推广到了6bit,此二进制思想更完善,如果对二进制思想的定义较高,周文王显然是更好的答案;如果要求二进制思想必须是完 整的思想体系的话,那么还是莱布尼茨这位兄台更加准确。柏拉图虽持二元之论,但此与二进制思想相差尤远,故不采。

2, D,指针。“指”为指针,“物”为数据。

3, C,java/javascript。单从表面上可以看出来,题目中两组对应关系都是名字相似却本质毫无联系的事物,因此java和javascript 这组对应关系更加类似。此外这两组对应关系出自一副对联,曰:“蔺相如,司马相如,名相如,实不相如;魏无忌,长孙无忌,彼无忌,此亦无忌”,将此对联与 这一组对应关系相较,岂不暗合!

4, B,分治。破其合纵,远交近攻,收买重臣,分而治之。

5, C,记忆化搜索。用毛线标记出已经走过的路径。

6, A,神经网络。题目里面扯上这个电影主要是想开阔下自己出题的思路。电影里这个机器人了解事物要靠学习,显然是强人工智能,但其学习的过程并不类似遗传算法所应表现出来的,所以神经网络最为接近。

7, D,不会定义自己的需求。A和B显然是以偏概全,问题纠结于C和D两个选项。齐王渴望士,但却不知道自己渴望什么样的士,这更接近于软件工程中客户不会定 义自己的需求的情形;而按照我自己的理解,倘若齐王知道什么是士,却无法讲出来什么是士,这才叫做“不会下定义”。故此题答案为D。

8, C,衍生类未重载。不理解的同学烦请自行查阅“卵有毛”这个命题是怎么推导出来的。

9, A,继承。这个有疑问吗?

10, C,统一接口。张居正改革以前明朝的赋税制度是非常混乱的,其一条鞭法极重要的一点便是将各种杂七杂八的赋税徭役统一了起来,即统一接口。泛型编程在于可以接受各种数据类型,与此不符。

二,匹配题:

A1 – B3(将东西南北逐一穷举);

A2 – B2(关键为“蓦然回首”一句);

A3 – B5(不解释……);

A4 – B1(讥讽南明福王及其府下臣子只知贪图眼前光景);

A5 – B4(将飞鸟的动作拆分成无数部分,则飞鸟的每一刻的影子都是重新生成的,是不动的。其实这题我本来想用“镞矢之疾,有不行不止之时”这一句的,却鬼使神差地写下了这一句)。

三,阅读理解:

1,微软亚洲研究院。

2,斐波那契数列中每一项是前两项之和,是一个单调递增序列,而且越到后面其增长越快,所以搭配了“漫延”这个词语。这象征了我对“你”的思念每一 天都如同和把之前的叠加在一起,这般与日俱增,而终如洪水般“漫延”。亦有人提出斐波那契数列的通项公式是由无理数构成,但每一项却都是有理数,这种因既 无理而果又有理的纠结恰恰很好地诠释了思念之情的意义。我要承认这后面一点我身为作者也未曾想到。

(其实写的时候我并没有想太多,所以文囿同学“其实这就是作者信笔所至之处,比喻虽甚不恰当,到底无伤大雅”的评价还是很正确的……)

3,作者写这句话其实是表达了他对他学的软件工程概论课程的感慨……搞软工的人,你们懂的。

4,过去在哪儿听说算法有不变性这一特征,但是这个说法似乎不太严谨,这里我倾向于采用高德纳(即Donald E. Knuth)的提出的“明确性”(或者说被翻译出的)这一说法。

5,匈牙利算法是二分图匹配算法,对每个点通过寻找可增广路改进的方式得到最大匹配。原文用“牵手”形容匹配,用“画面”一词将算法过程中的某一步匹配定格,这个匹配是否问最终匹配并不重要,重要的只是此刻。

这里顺带贴出杨弋大神的第5题答卷:“匈牙利算法的特点是一旦牵手了就永远有手签,每次增广路经过自己的时候还会换一个。所以该作者喜欢牵手画面其实喜欢的是将来一直有手牵的可能性,与文中的“你”是谁没有关系……”(我对天发誓这不是作者的原意 = =||)

对付NYTimes的石头剪刀布Novice Computer的出招表

题目中涉及到的电脑AI在这里:

http://www.nytimes.com/interactive/science/rock-paper-scissors.html?hp

里面电脑AI分为两种,Novice和Veteran,前者是根据你的出招习惯来出招,后者是根据之前所有对战的统计数据来出招。虽然从名字上来看 Novice是初学者,Veteran是老将,但是真正玩起来老将未必比初学者强大,因为全人类的出招习惯实在不能说很靠谱……但是另一方面,如果你本身 就没有出招习惯,或者说出招习惯本身就是一个圈套呢?

这就是击败Novice电脑的思想。而我用了一个最无赖的方法便是本地写了一段代码模拟Novice电脑的算法(算法思想在它的网站上点击See What Computer is Thinking便可以看到),也就是说,Novice电脑根据某算法判断我的出招习惯然后出招克制,我也用同样的方法计算我的出招习惯然后反其道而行 之。

当然这是获胜的方法,但未必是胜率最大的方法。如果伪造自己的出招习惯是否能造成一个循环,而又是否可以找到一个胜率最大的循环,这类的问题也还颇有可以进一步思考之处。

下面给出一张我用自己写的一个本地程序计算出来的一种出招表,以及我用这个出招表得到的结果,有兴趣的同学可以尝试一下,并把你的胜率情况告诉我。
注意:出招表大概在10回合以后开始发挥威力。

Round 1 : Scissors
Round 2 : Paper
Round 3 : Paper
Round 4 : Scissors
Round 5 : Scissors
Round 6 : Paper
Round 7 : Paper
Round 8 : Rock
Round 9 : Rock
Round 10 : Scissors
Round 11 : Rock
Round 12 : Scissors
Round 13 : Scissors
Round 14 : Rock
Round 15 : Paper
Round 16 : Scissors
Round 17 : Paper
Round 18 : Rock
Round 19 : Scissors
Round 20 : Scissors
Round 21 : Scissors
Round 22 : Scissors
Round 23 : Paper
Round 24 : Rock
Round 25 : Paper
Round 26 : Paper
Round 27 : Scissors
Round 28 : Paper
Round 29 : Scissors
Round 30 : Rock
Round 31 : Rock
Round 32 : Paper
Round 33 : Rock
Round 34 : Scissors
Round 35 : Paper
Round 36 : Scissors
Round 37 : Scissors
Round 38 : Rock
Round 39 : Rock
Round 40 : Rock
Round 41 : Scissors
Round 42 : Scissors
Round 43 : Scissors
Round 44 : Paper
Round 45 : Scissors
Round 46 : Scissors
Round 47 : Scissors
Round 48 : Rock
Round 49 : Scissors
Round 50 : Paper

如果要我出程设试题

一,选择题(皆为单选):

1,以下谁是二进制思想的最早提出者?

a,伏羲;b,姬昌;c,莱布尼茨;d,柏拉图。

2,以下哪个概念和公孙龙的《指物论》中的“指”字含义相近?

a,变量;b,数组;c,对象;d,指针。

3,蔺相如,司马相如;魏无忌,长孙无忌。下列哪一组对应关系与此类似?

a,PHP,Python;b,JSP,servlet;c,java,javascript;d,C,C++。

4,秦始皇吞并六国采用了以下哪种算法思想?

a,递归;b,分治;c,迭代;d,模拟。

5,雅典王子忒修斯勇闯克里特岛斩杀米诺牛的时候采用了以下哪种算法?

a,动态规划;b,穷举;c,记忆化搜索;d,Dijkstra算法。

6,印度电影《宝莱坞机器人之恋》中的机器人七弟采用的智能算法最有可能是以下哪一种?

a,神经网络;b,遗传算法;c,模拟退火;d,穷举算法。

7,《公孙龙子》记载:“齐王之谓尹文曰:‘寡人甚好士,以齐国无士,何也?’尹文曰:‘愿闻大王之所谓士者。’齐王无以应。”这说明了齐王:

a,昏庸无道;b,是个结巴;c,不会下定义;d,不会定义自己的需求。

8,惠施曾提出过“卵有毛”的命题,以下哪一项是导致这个错误命题的原因:

a,混淆了命名空间;b,引入了错误的包;c,衍生类未重载;d,调用了危险的指针。

9,下面哪种面向对象的方法可以让你变得富有?

a,继承;b,封装;c,多态;d,抽象。

10,明朝时期张居正改革的一条鞭法的主要思想是:

a,面向过程;b,万物皆数;c,统一接口;d,泛型编程。

二,匹配题(分析A中的句子所体现的算法,和B中的算法一一匹配):

A:

1,江南可采莲,莲叶何田田,鱼戏莲叶间。鱼戏莲叶东,鱼戏莲叶西,鱼戏莲叶南,鱼戏莲叶北。——汉乐府《江南》

2,众里寻他千百度,蓦然回首,那人却在灯火阑珊处。——辛弃疾《青玉案》

3,从前有座山,山里有座庙,庙里有个老和尚,再给小和尚讲故事,故事内容是:从前有座山,山里有座庙,庙里有个老和尚,再给小和尚讲故事,故事内容是:从前有座山,山里有座庙,庙里有个老和尚,再给小和尚讲故事,故事内容是……

4,只劝楼台追后主,不愁弓矢下残唐。——孔尚任《桃花扇》

5,飞鸟之影,未尝动也。——《庄子》

B:

1,贪心;

2,回溯;

3,穷举;

4,分治;

5,递归;

三,阅读理解(阅读下文,回答后面的问题):

爱在程序间

作曲:周杰伦;作词:梦里醉逍遥

美国的贝尔实验室设计了最初的C语言
刻在UNIX操作系统距今已有三四十年
你在屏幕前凝视数据的缱绻
我却在旁轻轻敲打键盘把你的梦想展现
循环 递归 贪心 动规 是谁的从前
喜欢在匈牙利算法中你我牵手的画面
经过MSRA门前我以大牛之名许愿
思念像斐波那契数列般漫延
当软工沦落在设计的文档间
算法依旧是永垂不朽的诗篇
我给你的爱写在程序间
深藏在最长不下降子序列里面
几万组数据流过后发现
我的心依然不变
我给你的爱写在程序间
深藏在最长不下降子序列里面
用无尽的代码刻下了永远
那已保存千年的誓言
一切又重演
我算了很多遍
时间复杂度还是趋于无限
我只想要这样永远链接在你的身边

1,题目中的MSRA是什么的缩写?

2,试赏析“思念像斐波那契数列般漫延”一句。

3,请结合时代背景,谈谈你对“当软工沦落在设计的文档间,算法依旧是永垂不朽的诗篇”一句的理解。

4,“几万组数据流过后发现,我的心依然不变”一句体现了算法的什么特性?

5,就“喜欢在匈牙利算法中你我牵手的画面”一句,谈谈你对匈牙利算法的理解。