从头再来
最近在思考相似度推荐的算法，想过不少主意，但觉得最省事的莫过于用Lucene或Sphinx之类的全文检索软件，把每个个体的tag信息放在索引中，用的时候直接去查。搜索引擎可以搞定计算TF/IDF、计算相关性之类的脏活儿，直接返回相关的内容，可谓省时省力。 不过还是我忍不住自己想了一下，感觉也还算简单，今天写一些自己的心得，算是抛一块砖头。相似度计算可以用余弦定理来算。简单来说，我们可以为一个个体找到一组描述其特征的值，比如描述苹果、梨、香蕉，可能有： 苹果： 球形 甜味 红色 多汁 梨： 球形 甜味 黄色 多汁 香蕉： 长形 甜味 黄色 把这些特征编个号，排一下，就可以把这些特征数字化了： 苹果： 1, 2, 3 , 4 梨： 1, 2, 5 , 4 香蕉：6 , 2 , 5 可以把上面每个看做是一个描述该个体特征的向量，这里有6个特征，于是向量是六维的： 苹果： [ 1, 1, 1, 1, 0, 0] 梨： [ 1 , 1, 0, 1, 1, 0 ] 香蕉：[0 [...]
前日买的3本书，今天就到了。捧着沉甸甸的箱子，心里满满的。这次买的书之前有写，三本花了168.4元，卓越亚马逊的VIP帐号连一分钱都没给我省。捧着书的时候想起Livid一个摆满了O’REILLY的书架。大学期间我没买过多少专业方面的译著，今天简单统计了一下，买了博文视点的两本（Web开发敏捷之道第一版、第二版），买了华章的一本（算法导论），图灵教育的两本（数据结构与算法分析、AJAX基础教程），还有O’REILLY的一本（Ajax On Rails）。但是从图书馆借的书那就多了去了，觉得同样是翻译或影印外文，O’REILLY的书最靠谱。 3本书拿回来一看，传说中有70%和第一版不同的《Web开发敏捷之道第二版》，看看目录也没有增加多少东西，有点小失望。但是仔细看一下，确实有不少细节的更新。而且对于AJAX也加入了更多内容，还比较对味。 “Ajax On Rails“是英文版的，也还没有深入地看。主要内容是script.aculo.us和rails的协作。在前两本书中能看到，只要介绍script.aculo.us，就没有漏掉Drag and Drop的实现，而且都还附带了例子，很容易学。 第三本书是《算法导论》，读了前言。同我猜测的一样，越是站在高处看东西就越简单。高中时读霍金的《果壳中的宇宙》，像是在听故事。那个老头子的幽默，影响了我好久。
昨天的比赛，结果出来了，我是三等奖，在14个作品里是第7。先前听到现场同学的消息，以为自己会在前面几名的。不知是评委修改打分了还是怎么了。不过拿奖就赚，运气尚可。 读书改变生活。昨天晚上去卓越亚马逊上买了3本书，现在在琢磨寒假时怎么把厚书运回山西呢。 貌似是去年初看alone买的一本《程序员》，上面说算法方面的书籍时，提到了这本《算法导论》。alone后来借阅过这本书，说上面全是数学，很难理解。而我则看过另一本《计算机程序设计艺术》，感觉确实高深。 不过时代变了，在这一年里，虽然我没有在数学上有啥研究，可是在其他方面觉得有很多进步。总认为人对事物的理解像是一个“层次遍历”的过程，所以现在买来再读，不知道能不能读懂。算法方面的书，和前面说的C语言的书一样，经典著作很难过时。 这本书我也提过很多次了，我没读过。只读过它的第一版。第一版给我的感觉是，rails实在太神奇了。我先从图书馆借来，然后看着不过瘾，自己又去网上买了一本。现在我也经常在上课时拿去教室看。如今，第一版已经被我翻来覆去读了许多次，前些日子也开始了一些实践。但看到这个第二版，还是忍不住买了。图书馆里找不到，也不知道崭新的rails会有怎样的不同。而且，价格还比第一版贵了60%。 这本书本来没打算买，偶然看到却吸引我了。因为最近的一个项目里要用到这两样东西：Ajax&rails，这本书无疑是个好教材。同时里面的script.aculo.us和rails的版本都不算旧。要去上课了，就写到这里吧
在枫之羽的推荐下看了这本《Lucene In Action》，感觉很不错。首先是翻译得比较好（从这个角度看，原版一定很好看）；另一方面，虽然原版作者是老外，书中还是讲到了不少中文切词方面的东西。再者，还写到了Lucene在其他语言平台上的移植，比如CLucene,dotLucene,PLucene,Lupy等等。其中一些知识已经陈旧了——在一个迅速发展的领域，写到书上的知识往往在出版时已经变得陈旧了。针对这个问题，一些作者也在书里给出一个互联网上可访问的地址，分享最新的资源——比如我一直在看的《电子商务》。 其实我已经看了很多Lucene方面的东西，对于Lucene的通常使用也有了概念，只是没有时间来实践。所以看这本书只花了两节课，看完印象最深的是其中一个判断内容相似的算法。其实就是Google黑板报说的那个“余弦定理”——文本包含的各个词及其出现的频率可以构成一个表示该段文本的特征向量，而通过余弦定理可以计算任何两个向量的夹角，夹角越小就说明二者越接近。 貌似没有比这个更好更体现数学之美的算法了，可是，判断两断内容的相似程度是简单的，如果是20万段内容，判断其两两之间的相似程度，又该怎么做呢？进行简单的两两选择，一共会有将近400万条数据，而可以确定的是，其中大部分都是没用的。 很想知道Google当年还有“补充材料”时是怎么判两个网页有重复的，人家服务器里搁的网页可不是十万计的。隐隐觉得这个时候该结合贝叶斯算法——当然肯定不止这些。数学还是不够好，不能马上想到一个可行的解法。 记得今年在北京，某人说，豆瓣里那些相关图书都是用select从数据库里拿出来的 。可爱的回忆。
初探Lucene，学习之中。 昨天下雨，我家的百兆宽带突然就不能上了。所幸昨天还写了第1000篇，不然就遗憾了。不能上网也许并不是坏事，虽然我看不到了想看的人，进不去了我的GTD，可是让我得以把精力放在一些感兴趣的技术上。 昨天我ProjectCamel有点阶段性的成果。得益于泛域名和出神入化的URLRewrite，已经可以准确地显示出站点加载时的桥页。所以今天我放下了活儿，把最后一天留给自己，想看一下Zend_Search。我一直很想好好研究中文分词，可是这个暑假下来居然没有看过一下子Lucene，除了在北京和馒头空对空地来过几次分词的讨论，其他真的一点收获都没有。 不过自己也一直庆幸，我越等到后面，Lucene对中文支持就越完美，就不用自己去操心了。怀着这样的心情，我今天开始看Zend_Search_Lucene了。我成功地把自己以前做ACM写的程序编制成了索引，随便查了两下，效果很让人满意。可是当我把一些中文文档索引之后，问题就来了，根本啥都查不出来 。不是说Nutch（一个可以拿来做搜索引擎的开源程序，和Lucene貌似是一个人写的，世间的大牛不是很多哈）和Lucene都完美支持中文了么？我顿时有种被骗的感觉。 可是那也得做。网上搜来搜去，搜到的基本都是06年上半年的文章。不少牛人用自己的方式在Zend_Search_Lucene中实现了中文分词， 可看看都觉得头大，有的甚至还得给Zend_Lucene打Patch。终于搜到一个今年6月的文章，读了之后，感觉作者在PHP上的功底很不错。文章请看此处，可笑的是。查资料的过程中 ，也发现不少人转载从来不标明出处，唉，国内就这情况，重复内容太多。 那篇文章写得很不错，分词的部分逻辑也相当清晰。使用了简单的二元分词，这样生成的索引会相当大，但至少是可以支持中文的。可是我用来索引文档的时候，都只能索引第一行（处理换行有些问题），然后还有一些字母被无情过滤掉了。所以我对程序做了一些修改， 由于太长了，我就不放在这个blog上了，请移步到我的技术blog查看我修改之后的程序。 需要注意的是，这个分词实现只支持UTF-8编码的。如果需要索引内容的是别的编码格式，可以改一下程序中的某些部分。 二元分词在遇到牛扑这样规模的数据时，没有任何实际意义。特别是在Zend_Search_Lucene的索引优化并不完善时。所以在这个方面，还有很深的挖掘的空间。 关于分词的知识，可以看一下这篇文章和这篇文章（希望大家不要像他这样转载不加出处）。 逆向最大匹配，应该是下一个要钻研的了。
今天在做Camel的时候，对ZF中的Cache的一些初始化选项觉得有些疑惑，于是找来了官方的文档看了看。不看不知道，一看之下才发觉自己之前对ZendCache的使用简直太浅薄了。现在的ZendCache可以对页面某一部分做Cache，也可以对整个页面进行Cache，Cache的保存方式也多种多样，真的很强大。之前我自己对Cache的思考，和他们所做的工作比起来，可以说是微不足道了。 所以牛扑还需要更大的改动。今天我一度动摇，想用Python来重写牛扑，但很快就打消了这个念头。牛扑的架构需要进行更改，我打算大量地使用ZF框架中的组件。这个假期还有些遗憾就是，没有把足够的时间花在看Lucene上。智勇说牛扑啥都搜不出来，这是因为没用全文检索阿。记得那时Tiny还说要送我一个他们在这方面的产品，可那我也得会用阿。 不过，现在做Web开发会觉得顺手很多，因为网络上流行的框架有一大堆，总能找到适合你的一款。若不，说明你已经高超到该自己去写框架了。牛扑几乎所有的方面都需要改进，用户界面、全文检索、缓存算法、数据库结构……回头看自己之前的项目总会觉得千疮百孔。不过，一个一个来吧，我打算把这个拿来做我的毕业设计。 晚上还花了十来分钟，给机器人在互联网的某个角落，安了一个小小的开关。以后机器人掉线，就不需要爬上服务器去改了。只要对那个开关说一个暗语，机器人就会被重新打开。想着你说机器人不见了时可爱的表情，我忍不住就把这个秘密泄漏给了你。
今天参加了一次学校里的ACM比赛，我和popo第一次“强强联手”，可惜，我们那时在集训队的黄金时代被分在了两个队。我怎么也有一个学期没有写过C/C++的程序了，今天也纯粹是为了去混个奖品。 算法对我们学软件的人还是想当重要的，但我的感觉是现在在很多时候数据库几乎把所有的算法方面的任务都承担过去了。虽然在平时写程序也需要注意一些技巧，但都与ACM里讲的这些繁冗的算法没多大关系。 这次出的题比较难，是厦门大学一个很NB的队伍出的。所以主办方为了降低难度，特意增加了一道题。没想到增加的这道题陷进太多，一共只有两个队伍做出来——而且这道题还决定了今天冠军的归属。我们队伍做出了1道题，只提交了一次就命中了，然后幸运地排在了第八名，二等奖。没错，又是二等奖。 我们只做了一道题，排在了二等奖的最后一个。颁奖时很紧张，生怕落在三等奖，所幸11个三等奖并没有我们。二等奖的奖品是一个1G的闪存，正好是我需要的。我在学校的ACM比赛上已经拿了3次闪存了，此外还有耳机、摄像头什么的。拿到了二等奖我和popo还有另一个队友都比较开心，另一个队同样做了1道题只拿到了三等奖——今天的事让我想起我高三物理竞赛的一分之差，想起高考与北京的一分之差，原来幸运和遗憾只有这么点距离。一个朋友的签名说，”Only the strong survive.” 昨天改进了程序，生成了一个V2Read的图书目录，现在的约40W种图书都可以列出来了。下一步我要做的事情就是为它增加更多的图书内容。我的美工水平有限，V2Read的样子实在是太业余了。今天晚上回来总有用脑过度的感觉，睡觉去。
前段时间给我的blog做sitemap，找了一个网站来让它生成。后来感觉每次都找挺麻烦的，想自己写一个生成sitemap的工具。 一开始我想用PHP来写，这样的话生成文件可以直接放在目录下，免去了上传的步骤。但是这个学期C#的作业还没有写。POPO在写一个学生信息管理系统，这样的东西至少对于现在的我来说是没什么意义的。在PHP中这样大型的数据管理做了不少，虽然没有写过C#的，但真的提不起什么积极性。后来想了想，就写一个C#Sitemap生成器好了。 去MSDN查了一下，C#生成XML还是很方便的（我以前用C#生成文本文件怎么也不成功，让我禁不住想用Delphi去了）。把以前写的抓取joyo/dangdang商品价格的一部分程序结果来，拼拼凑凑，一个Sitemap生成器就写好了，虽然看起来那么简陋。 这个Sitemap用的是广搜算法——这个和前段时间的商品抓取，其实中心思想都是老张的。要是老张也去学一个月技术，该是多么恐怖的一个牛人啊。现在我正在用它抓取我的blog的1000个页面，因为网络不够快，所以速度飚不起来。回头会把这个小工具发布出来。
You are currently browsing the 张磊的blog weblog archives for '%e7%ae%97%e6%b3%95' tag.
Longer entries are truncated. Click the headline of an entry to read it in its entirety.
