Author Archives: yongxiu

生命的意义

人生很漫长,童年、中年、老年,人的一生经历了很多。

人生又很短暂,弹指一挥间。

有没有想过,你的生活是为了什么,不同的人有不同的回答,我们的追求不同,生活的方式却大体相同。

不知你有没有观察、体会、想过不起眼生命的意义,先说病毒,它们活着的意义是什么?为了理想?呵呵,为了混口饭吃?也不是,它们没有目的,只是找到一个寄主,执行了自身的逻辑任务,把自己复制一份,结束它们生命的方法是将结构彻底破坏,它们的生命就走到了尽头,这就是它们的一生吧。细菌,它们活着的意义是什么?简单的结构,需要食物,通过分裂来延续种族的生命,结束它们生命的办法就是破坏结构,它们的一生也很简单。

好吧,来点高级点的生命,鱼,它们活着为了什么?捕食小鱼小虾,延续自己的生命,捕不到怎么办?死了,死了又如何?Who cares? 鱼会害怕死亡吗?会吧,它们受伤或者被抓到时,我们可以看到它们奋力逃脱,对生存的向往。这么说细菌也会吧,受伤时,它也会补给营养,让自己复原。病毒呢?

人,人的情况有点复杂,受了多年的思想教育,人们崇尚流芳百世,精神永恒,肉体虽然活不了永久,但是他们总是想通过精神上的方式活的久点。

人又很微小,举一个最伟大的人,一个影响了全世界的人,他的影响力那么大,但是对于整个宇宙来说,他是显得多么的渺小,茫茫的宇宙,地球上最伟大的人,连地球——这颗宇宙中的小灰粒都没有什么影响,对于宇宙来说,人的一生啊,连个病毒都算不上。

人的身体又是通过细胞来构成,我们能不能把一个细胞看作一个生命呢?回想我们的每一天,一举一动,都是建立在无数个细胞的共同努力下来完成的,有时我想人的生命真的很脆弱,为了生命人真矫情,你想想自己一天精神状态最好的那几小时,其实我们一天只活了那几小时不是吗?为了那几小时我们的身体足足备给了十几个小时,我们需要进食饮水,来满足那几小时的能量消耗,我们需要巨大的肠胃来暂时托管要排出的废物,需要心脏费力地给血液循环提供动力,需要睡眠来休息大脑,保持大脑的兴奋,即使备给了这么久,那几个小时我们还是要呼吸!为了这几个小时,我们的准备要有多么的充分,人的一生又能有多少个这样的几小时呢?

记忆,记忆真是很美妙的东西,没有了记忆,我们活的再久也毫无意义了,喜怒哀乐全都存在了大脑里,于是那么的小时最后凝聚在了记忆里面,在那里我们保存了自己的经历,在那里见证了我们生活过。

生命的意义是什么?活的伟大,影响他人?活的开心,幸福?经历悲欢离合,酸甜苦辣?新陈代谢?我们从一个旁观者的角度来看,其实人生,只不过是一堆细胞,自我生存,完成了一次时间稍微长那么一点点的新陈代谢,和病毒,细菌有差别,但是,差别不大,呵呵。

The Time Traveler’s Wife

TimeTravellersWifeI read this book for a month. I like this book, better than the Harry Potter.

This book tells a story about a Time Traveler, Henry, he can jump back and forth in time, but he couldn’t control when to jump or jump to when. His wife, Clare, she met Henry during his travel when she is 6 years old, She loves Henry when she is only a little girl, how lucky she is, met the one when she is only a children.

Clare, his wife, she spent her whole life waiting, waiting for Henry’s next appearance, even he is dead, she waits for nearly 40 years for his next short appearance, I think it is too sad so the film changed it. In the film, Henry didn’t leave a note to his wife, Henry says I don’t want you spend your life waiting.

Henry, he is a lucky man, the girl told him that she is the one when they first met, while most of us are not, we doubt, we don’t know when we can’t keep it. Of course, living such a life is terrible, the man now and the man in the future are totally different. The future you told you that you will fall in love with someone, while you are not now, what are you going to do? Waiting? What’s the worse is that the girl loves the future you, she may dislike you now.

Henry died in the end, left an letter, telling Clare that they will meet in the distant future when Clare is an old lady, so the Clare waits, waits for 40 years for his appearance.

What will you do if you already knew the bad result? What will you do if you know that the love story ends in an unhappy way? Should this story ever begin? I chose yes, but I regret it.

I always think I’m a tough guy, there is nothing I can’t stand, but the man like this is week, I devote myself into working, coding, I love my work, I love the computers, the computer has no feeling, it is loyal, it’s reliable, but there is something it doesn’t have, there is something that the computer make you feel more lonely.

I compresse many thoughts into my deep heart, sometimes I want find someone, someone to express my feelings, how bad I am, how pathetic I am, forgetting how strong I am.

The most unforgettable thing was in January, 2010, I flew back home, and lost my cellphone, I was very depressed, found a cab to take me to a hotel, it was midnight, about 3 a.m, every hotel room was very expensive, and I was still far away from my home, every one seemed like bad guys because someone had just stolen my cellphone. I felt so lonely, I wanted to find some help but no one could help me, I felt so helpless and stupid at that moment, I realized how week I am, two and a half years passed, I still remember that night, how helpless, how week I am. Thank you, fate, you taught me how small I am, you taught how pathetic I am.

Fate is cruel, especially when you know your fate, Henry can time travel, but he can not change anything, because that’s the fate, it already happened, the god is just playing it as the script. Do you want to know anything about your future? Why would I want to know if I can do nothing with it, one of my friends told me that she believes in fate, everything, everything around us is predestined, I asked why, how did you prove that? She answered no, you can’t prove that, but you can’t prove it’s wrong, yes, I can’t prove it’s wrong, just like the theology, it can explain everything, anything you can’t explain with science can be explained with theology, but I don’t think it is useful, because it can’t predict anything.

What will happen in 5 years? I don’t know, will I live happy and comfortable? I’ve been seeking money for many years, I hope I will have my own business, I hope I can live happy, I hardly dare to hope that I will have a family and children. I just hope that I will not regret when I look back.

What will I say to myself if I can time travel to 5 years ago? I will say “Dude, live your life, you will have a fantastic life!”

记忆,意识与唯心主义

有没有这种感觉,刚刚一觉醒来,有那么一分钟是失忆,什么记忆都没有,然后记忆慢慢回到脑中,浮现了我怎么在这,我接下来要做什么。

审视我们这个世界,你能确定你是自己,为什么,因为记忆。记忆帮助我们确定了接下来需要做什么。《记忆碎片》这部电影就描述了一个只有片段的记忆的人,电影采用了倒叙的方式,这部电影给我的印象深刻,推荐给所有人。还有一部电影叫《第六日》,讲述的是克隆人,很多人借此说克隆人很可怕,克隆技术很可怕,克隆人更应该明令禁止,但是我看到的不是克隆人的可怕,而是影片中的记忆复制的可怕,克隆出另一个斯瓦辛格后,插入了以前的记忆,甚至连克隆人自己都不知道自己是假的,两个人都十分自信自己才是真正的原人。想象一下,有一天我们起床,发现自己的样貌发生了变化,别人告诉你你的记忆不是原来这个身体的人的记忆,但是我会很肯定的说,不可能啊,我还记着我睡觉前在干嘛干嘛,我接下来要去干什么干什么,肯定搞错了。

难道不是记忆才是我们真正的唯一身份证吗?但貌似不是。

从前有支乐队,成员是A, B, C,乐队叫β,后来呢C 走了,来了D,B也走了,来了E,最后A 也走了,来了F,乐队还叫β,成员是D, E, F,乐队的风格也变了,出了很多新专辑,请问这个乐队和那个A, B, C 组成的乐队有关系吗?再来个搞笑的,后来A, B, C 又聚到了一起,重新组成了一支乐队。以此为背景,请看下文。

我曾经和几个好友探讨问题的时候,我问过他们一个问题:“如果未来人类技术发达了,有这么一项技术,就是你老了,技术上可以给你克隆一具身体,把你的记忆复制一份,插入到那具身体里面,在别人的眼里看来,根本分不清谁是造出来,谁是原来的,这样你就可以安心的死了,你认为你的生命得到了延续吗?”就像《致命魔术》里面一样。好多朋友说这显然已经不是原来的我了,不能算作生命延长。于是我又问:“如果可以将你的大脑移植过去,这样算是延长了吧?”朋友说着应该算作延长了。这两者有什么区别呢?一个是copy 过去,一个是move 过去,这样就可以保证最核心的肉体没有发生变化?但是你要知道,我们的身体每时每刻都在发生着新陈代谢,有个说法说“18天人身体上的水分会全部更新一次。其他的新陈代谢,21天内的周期。”这个说法可能不准确,我想表达的意思是,我们身上固有的这些肉体等等,很可能根本不是10年前的那副躯壳,已经完全更新掉了,每个原子都换掉了。为什么我们会说我还是我,甚至我们的观念,信仰,性格,记忆可能都发生了巨大的变化,你还是你吗?

最于极端的例子便是一个人不小心失去了记忆,貌似电视里经常出现,又过了很久,身体的新陈代谢全都更新过了,这个人还是以前的那个人吗?我们找不出一点的关系啊。所以我常常和一个朋友开玩笑说你说你现在过得这么累,说是为了以后能过的好点,假设以后真的过得好了,但是你可以把未来的那个人完全当做另一个人啊,你做的这么好,就为了他,你说你这图什么啊。

我常常觉得,影响我们性格的很大程度上就是因为我们的记忆,虽然人的大脑不一样,大脑终究还是个cpu,执行计算有快有慢,快也快不了哪去,慢也慢不了哪去。最重要的莫过于存储记忆的部分,存储的深度,提取记忆的速度,能否提取出来,直接影响了我们的行为操作。

即使是另外的一份躯壳,如果技术上能够实现将记忆完美的移植过去,包括记忆的深度,记忆的清晰度,我在想有这份记忆的人性格会不会完全一样,当然由于环境的不同,从下一秒开始,他们就开始走两条路线了。

记忆是如此的重要,以至于它才是主导我们行为的东西。

我曾经在想,人类,如果想要实现永久生存,躯体太容易收到伤害,有一种方法,完美解决。类似于《黑客帝国》的模式,我们的大脑直接连接到计算机,计算机为我们模拟这个世界,人活着的意义在于什么?不就是想让自己的大脑充满自己想要的记忆吗,可以啊,计算机帮助你。共产主义怎么实现,就算社会上资源无限,人和人只要相互接触就肯定会有矛盾,如果生活在计算机,甚至不知道自己生活在计算机,每100年为一关,过完一关,游戏暂停让你选择,下一关投胎做什么人,快乐的,痛苦的,奋斗的,穷人,富人,总统,歌星,科学家,乞丐等等等,投胎前暂时暂停记忆,等死了再把这段记忆append 到原来的记忆中,真正做到了无限的生命啊。怎么实现呢,把计算机直接连接到大脑,让大脑决策这个肉体在计算机世界中的行为操作,记忆怎么办?太多了,大脑根本记不住这么多几万辈子的东西,记忆还是放到计算机里吧,大脑想用的时候从计算机里提取,等等,那要大脑干嘛,不就一个速度挺慢的cpu 嘛,计算机模拟一个不就好了,行了,完全不需要人体了,到现在为止,那么计算机里面那个自动模拟人的那个东西还是原来的那个人吗?只是借用了一下人最开始的记忆而已,怎么样才能让他相信自己确实活在计算机里呢,这时万一如果躯体醒了,计算机里面的思维还在思考,这两个人兴许还能谈谈,显然这是两个人啊。还有个办法,现在这两个人相当于软件的代码的两个分支,赶紧把记忆合并吧,合并就又是一个人了。

未来可能就会有一台硕大的计算机,上面有太阳能电池板,它在围绕着太阳旋转,计算机里面住着很多很多的人,每天都在更新着自己的记忆,那里就是天堂吧。

很多时候,你不得不怀疑,这个世界是不是其他的东西都是你想象出来的,你怎么确定别人是有意识的呢?你怎么确定你的记忆不是被移植的呢?你怎么确定不是活在计算机里的呢?有个很有趣的现象是,我们自己以前可能吹过牛,因为经常拿某个段子吹,最后这个段子印在了我们的记忆中,我们自己都已经忘记了这个段子是自己以前编出来吹牛用的,当达到这个阶段的时候,我们已经确信这件事情是真的,我看周正龙就已经达到了这个阶段,他自己已经相信自己看到了老虎,别人说再多已经无用了。

审视这个世界,我们不可能去和未来的自己决断关系,路还是要走的,活好每一天才是我们需要做的,每分每秒都快快乐乐才是真正的赢家啊!

做一个自由的灵魂

信息化的时代,意味着什么?可能意味着如果你够糗,你的事迹会传遍这个世界的每一个角落。我们被这个时代深深的改变了,享受着从未有过的信息洪流,facebook、 MySpace、 twitter 亦或是微博、人人、微信、手机简讯等等等等,由此而来引发的政府监管、网络暴力、人肉搜索、五毛、美狗等等新时代的产物,试想你会多大程度地被这些信息影响着?

一件事,从不同的角度来看就会有不同的看法,我不想举例,因为每个例子其实都会有我自己的主观看法,我们不是当事人,无法了解每一个细节,而尤其是现实社会并没有电视中那么险恶坏到底的罪人,更没有完美的好人。

媒体在其中充当着一个重要的角色,媒体的采访,媒体的评论,要做到客观?每一份媒体都是由人组成,我一直坚信由人来说、做的东西不会是完美,都会有自己的利益在上面,甚至很多媒体为了博得眼球会扭曲一些显而易见的事情。现代的媒体,我们不能指望看到最客观的报道,应该尽力去了解每一方面的观点,容纳每一方观点。

亦或者我们了解的事情的每一个细节,但是我们自己内心中有一个评判的标准,什么是好,什么是坏,每个人都有不同的道德观。

当我们轻而易举地认为富人、明星就应该多捐,甚至为此辱骂、记恨他们的时候,有没有想过我们可能是在以道德的名义耍流氓?

当网络上、周围的人们充斥的对其他集体的某种仇恨的情绪,有没有想过,我们可能仅仅是在维护自己的利益最大化,抛弃了我们自以为一直拥有的公平判断?

有一种人皆为自私的观点我很是赞同,你爱哪个国家?自己的国家。你爱哪个省?自己的省。你爱哪个市?自己的市。你爱哪个家?自己的家。最后都归并到爱自己。你做什么事都其实是有目的的,帮助他人可能是有求于回报,否则则是愉悦自己,体会别人感受帮助的快乐;主动承认自己的错误,比如拾金不昧、比赛中主动告诉裁判是自己的错误,更有可能是为了不让自己收到内心的谴责;你报效祖国、开发西部,是为了让集体更好,提升自己的荣誉感、集体自尊。

如果我们假设有上帝这么一个角色,如果我们站在上帝这个位置来俯视人类社会的时候,会不会有种想笑的感觉,人类社会有这么多荒诞可笑的事情发生,他们把自己分成了不同的民族,不同的国家,把自己由皮肤的颜色又进行了划分,这么做的目的仅仅是为了找对敌人,然后竞争;他们制定了一种规章制度,称之为法律,并且赋予了这个规章制度一种人为寄托的精神,说什么为了维护法律的尊严;他们常常说神圣不可侵犯、自古以来,殊不知几亿年前他们来自同一个母体,他们发源地只有一小块领土;他们有一种集体精神,为了大家的利益,牺牲小我的利益,当然也不能牺牲的太过分了,然而目的其实也是大家的利益提高了,分均到个人利益的提高,亦或是集体的自尊心做怂。他们对集体也有详细的划分,一家三口的这种小集体,亲属集体,朋友集体,城市集体,省集体,国家集体,他们最后想到的才是人类集体。

人类更是有很多莫名的自尊,他们会自主地掩盖自己的缺点,夸赞自己的优点。当指责他人时,他们有理有据,然而情况相同的发生在自己或者自己所属的集体的身上时,他们又会抛弃自己的道理逻辑。有时候我在想“报恩”这个词,是不是仅仅是为了以后还会获得相应类似的帮助,国家与国家之间,这种利益冲突显得尤为突出,没有永远的敌人,更没有永远的朋友。为什么希望自己的国家,自己的省市繁荣富强,难道不是为了分均到自己的利益或分均自己的自尊?当国际主义战士帮助我们这个集体时,我们高度赞扬,巴不得能有更多的来帮助,但是当我们的一小撮分子帮助他人时,又是怎样的一种情况。

为什么很多在国内天天骂这骂那的跑到国外后突然变得很爱国?怎么说呢,我自己说我家的事或者和我家里人讨论说我家的事——可以,你一个外人说我家的人是不是和我对立。于是乎就有大清国的太监说自己心甘情愿,指责外国大使无权说三道四。一个人到了一个地方,或者到了哪里都会首先找到自己的对立面,他们是白人,他们是别的国家,他们鄙视我们的制度,他们认为我思想迂腐,他们内心把我当成敌人,凭什么?但时间久了融入之后情况就又发生了变化。这种集体之间的冲突,细分最终会细分到个人与个人的冲突,每个人都是冲突的个体,周围都是敌人。

我们再从另一个角度来看,冲突的个体,冲突的集体,这种复杂的冲突圈子正是人类社会总体进步的动力。正是有了国家与国家的区分,省与省的区分,民族与民族的区分,人与人之间互相的对立,有了竞争。国家会为以前的侵略仇恨而奋发图强,民族会为曾经的种族灭绝而奋发图强。面对一帮愚人下属,你是领导人,为了让大家都获利亦或是自己获最大利怎么办?教会他们那种完美的道理太难了,但是人其实都很自私啊,那么灌输简单的仇恨、对立、竞争、自尊思想就会蛮简单的。没有敌人,我们就造一个敌人。在国与国之间的冲突面前,人们注重自己国家的利益最大化,满不讲道理,这种集体的自尊思想可见一斑。人们牺牲自己的个体利益,要么是被逼的(担心不这么做自己的利益会更受损),要么是整体利益提高了,分均到自己的利益也有相应的提高,要么就是寄希望于未来,未来自己的利益会提高,这里说的利益当然那包括什么自豪感等等。

那么这种对立、集体、自私的思想就是错的吗?没有对与错,但是我认为作为有思想的人不能完全认同任何观点,应该有自己的想法。或许我可以乐观地认为世上很多宣扬集体思想、煽动仇恨、宣扬自尊的都是非常有思想,已经清楚了只有这样宣传,教育世人才能够推动世界的进步。

说了这么多,我们究竟应该怎么做?在行为上,人皆自私,我们依旧做自己利益最大化的事,我们依旧做让集体尊严、利益最大化的事。面对其他普通的人,与其费劲口舌给他讲一堆大道理,反倒不如给他灌输仇恨、尊严、道德、集体利益思想,倒也简单,其实也是帮助实现自己利益的最大化。面对另一个集体成员的挖苦嘲笑,我们也就能坦然面对,想想他只不过是实现自己利益最大化的一枚小卒。尝试找找和他重合的集体,找共同的异类集体,和他就站在一起了,如果实在找不到我们重合的集体,那只有等到外星人攻击地球,人类就能够团结一些,找到了一个属于全人类的大集体。

而在思想上,我只想说,我们应该不被任何的已有思想束缚,我想做一个思想的局外人,不被任何政权、尊严、仇恨、大局观、道德影响,做一个自由的灵魂。

搜索引擎内容相关性

最近在看搜索引擎相关书籍,在这里整理下几个IR (Information Retrieval) 的相关算法,便于以后详细分析和学习。这篇打算介绍下几个算法的大概,以后的几篇详细介绍每个算法的使用还有中文分词算法等。

什么是Relevance?首先我们知道互联网有数以万计的网页,每张网页都有内容。作为搜索引擎,它的任务就是通过用户输入的关键词,理解用户的意图,找到用户想找的那张网页内容,将用户最可能需要的网页链接排好序呈献给用户,Relevance 表示的就是用户输入的关键词和每张网页的相关程度,这是一项最关乎用户体验的指标,一个搜索引擎的Relevance 做的越好,说明它的搜索结果排序越好,用户往往在第一项或前几项就能找到自己的期望内容,显然用户就更偏向于使用这款搜索引擎。

不仅仅用在搜索结果,通过Relevance 我们还能再搜索结果中插入广告,将广告放在右侧或上面,这就要求广告的内容和搜索关键词相关程度越高越好。需要注意的是搜索引擎厂商不仅仅会考虑每个客户对关键词的出价是多少,还会考虑如果投放这家客户的广告,用户观看、点击这则广告的效果如何,因为首先广告分几个等级,投放后用户观看到了就需要钱,而如果用户点击的话需要更多的钱,用户如果点击这则广告、甚至点击之后出现购买更能使搜索引擎厂商受益。例如一个客户出一万元买了一个关键词“鞋子”,而他这个广告是关于路由器的,而另一个客户只出一千元,但他的广告是关于鞋子的,这个时候用户点击这则广告的概率显然要大的多,而且很可能还通过点击这则广告购买了产品,路由器的基本不会点,搜索引擎反而赚的少了,总体来说这个时候如果出鞋子的广告,不仅用户体验(找到自己想要的)更好,而且搜索引擎赚的更多。

不但如此,我们还可以通过像Google Adsense 的这种平台,发布分享广告,帮助中小网站获利,这个时候更需要Relevance,通过Relevance 算法我们能够找到对应于一张网页的内容最适合这张网页的广告,什么是最适合,和内容相关(当然还要考虑很多其它因素:用户当前通过搜索什么关键词进入到这张网页、用户所在的地区,如果还能结合用户通过社交网络发布的状态、他好友的选择就更好了)!用户看到文章后看到广告能够对广告有印象,甚至去点击。当然也有一些广告无需和内容太相关,例如Nike 的广告,它甚至都不期望用户去点,因为Nike 的广告更多的是希望能对用户产生印象,用户看到Nike 的广告能在下次购买运动品牌的时候更喜欢选择这个品牌。

以上展示了Relevance 的重要性,我们能看到它不仅仅关乎一款搜索引擎的好坏,更关乎这款搜索引擎的盈利,它的重要性可见一斑。

一说到搜索结果排序,可能很多人首先想到的就是PageRank,诚然PageRank 对搜索结果的排序起了非常大的作用,有了Google 这样伟大的公司。根据PageRank,PR值越高代表这张网页质量越高,高质量的网页排在最前面往往符合用户的需求,但是有两点:首先PageRank 是建立在HyperLink 之上的,对于一堆独立出来的,或者说没有HyperLink的文章内容,我们需要其它的算法来判断找出用户最想要的文章;在现代的搜索结果排序中我们不能仅仅依靠PageRank,Relevance 中的很多算法能帮助找出用户之最想要。

基本需求已经确定,看看我们手头有什么数据,从程序输入输出的角度来看我们要做出什么,输入是什么?海量的网页内容,英文的网页包括由单词组成的文章,中文的假设也已经分好词都是由词汇组成的文章,还有就是用户输入的关键词,当然这个关键词也是经过处理好的。输出时什么?尽量多的不遗漏的和关键词相关的网页链接,最重要的是它们和关键词的相关性(前后顺序)。

初始工作,海量的网页内容和用户的输入都有一个初始的修改工作,例如将一些is, are, I 去掉,这些词过于常见,基本每张网页都会出现,不应纳入我们的检索系统。中文的文章比较头痛,需要进行分词操作,因为检索的过程必须是以词汇为单位,例如上段的第一句话“基本需求已经确定”,需要被分解成“基本/需求/已经/确定”,这样当我们搜索“基本”的时候,可能就会出项上述这句话的结果。建立索引,将这些词汇建立一张表,通过这张索引,我们能够很快地找到这篇文章等等。

布尔检索:对用户的输入关键词检索,查看每张网页是否有上述的关键词,如果有那么这篇文章就符合要求,我们就要显示出来,缺点明显,类似于一个Find 工具,区别不出两篇文章都包含用户输入的关键词的差别。

向量空间检索:考虑权值,对于每个关键词,判断这个词在一篇文章中的权值,权值的算法有很多,例如我们可以将权值简单地考虑成出现的次数,还可以考虑一个词的重要性,重要性分数乘以出现的次数,没有这个关键词则权值为0。根据检索的词,判断谁的总分数最高,则它最符合要求。

BM25算法:用公式描述的手段,基于海量的数据,计算每个关键词分数,文档的分数,相应于检索关键词计算它们相关性程度。基本公式

2ddc5e204a1aa0069ca9c744b39fa3eb

9e44aac1ad6e4fd74bc1d4f1afabb401

公式1:score(DQ), 我们所要计算的评分,即为给定搜索关键词Q(Query) 和给定文档D(Document) 的相关程度,分数越高表示相关度越高。f(qi, D):在给定文档D 中,某一个语素qi 出现的频率。nn 个关键词。|D|:给定文档D 的长度。avgdl,索引中所有文档长度。另外两个参数k1 b 用来调整精准度,一般情况下我们取k1 = 1.2 ~ 2.0,b = 0.75。

公式2:用来计算公式1中IDF(qi ) 的值。N,索引中文档的总数目。n(qi ),索引中包含语素qi 的文档的总书目。

Query Likelihood Model: 基于一般语言模型的文本检索,一般来说语言模型的研究任务是:已知文本序列中前面(i-1) 个词汇,第i 个词汇为单词w 的可能性有多大。统计语言模型,Ponte 和Croft 最初提出的语言模型检索方法现在经常被称为“查询条件概率模型”。这个模型假设用户头脑中有一个能够满足他的信息需求的理想文档,用户从这个理想文档中抽取词汇作为查询条件,用户所选择的查询条件词汇能够将这个理想文档同文档集合中其他文档区分开来。这样查询条件可以看作是由理想文档生成的能够表征该理想文档的文本序列。由这个假设我们可以看出信息检索系统的任务被转化为判断文档集合中每个文档与理想文档哪个最接近的问题。给定一个文档集合与用户查询条件Q,存在一个未知的相关模型R,相关模型R 为相关文档中出现的词汇赋予一个概率值P(w|R)。这样相关文档被看作是从概率分布P(w|R) 中随机抽样得到的样本。通过词汇的概率分布来分析判断文章的话题,对于话题很重要的词汇通常具有很高的概率值(相对于文章的其他词汇)。

基本可以分为以上几大类,每种类别又分为很多细小的改进等,可以发现,基本上所有都是基于海量的数据进行判断几个因素:关键词的分数、文章关键词的频率、文章质量、语言模型。发展方向肯定是越来越注重文章的内容,希望计算机能够按照人类思考方式来理解文章的内容,通过搜索输入的Query,找到最能符合的文章。

总结来说,做出一款搜索引擎其实不是非常难,但是做一个好的搜索引擎则是一个浩瀚的工程,每个细小的步骤每年都有无数个科学家,无数个会议,无数篇学术报告,paper 来专攻某一领域。像TREC(Text REtrieval Conference) 会议就是文本检索领域人气最旺、最权威的评测会议。相关性的提高有时是枯燥的,几个月的奋斗,提高程度并不明显,用户的体验或许依旧如此,需要考虑的因数不仅仅是关键词与内容相关性,还有地域性,时间等等一系列。涉及的知识领域包括统计、机器学习、数据挖掘等等。

写这篇文章,督促自己深挖掘上述的几个算法和改良的算法,多挖挖相关论文,新年快乐~

 

References

http://en.wikipedia.org/wiki/Relevance_(information_retrieval)

Search Engines: Information Retrieval in Practice

The PageRank Citation Ranking: Bringing Order to the Web

http://en.wikipedia.org/wiki/Pagerank

http://en.wikipedia.org/wiki/Okapi_BM25

http://summerbell.iteye.com/blog/494227

当年做的蛮开心的一个小程序


回顾了一下,发现自己这么久以来做了很多的项目,参与到了很多的项目,也有上10万行代码的项目,但发现自己做的最开心的其实是一个数独游戏,在那个游戏也不是去增加程序的功能的快乐,而是去提高算法效率上收获了很多,之后又尝试去做象棋,体会到为了提高效率的辛苦,甚至后来为了参加比赛而写代码,在读取写入文件榨取那么几毫秒的时间。再后来养成了一定的习惯,无论写完什么,之后总是前后考虑对效率的影响,是否已经发挥到了极限,是否还可以继续提高效率,减小内存的开支,有的时候走在路上,睡觉前,上课走神的时候甚至都会考虑一下,也许这就是代码的乐趣吧!

如今想来,刚开始其实不懂,很多的时候是为了项目而做项目,于是做了一个又一个网站,但如今看来那些算什么呢,感触最深的是自己用了什么什么框架写了多少多少行代码,窃窃自喜,但突然发现大牛写了一个框架去给别人使用的时候发现了自己多么的愚蠢。

回想这个数独游戏,是在2010年初写的,界面操作模仿数独博士,现在看来也还算很不错的,当时花了很长的时间去提高它的效率,记得有一道题目,是专门针对普通算法的题,普通的穷举基本卡死,要4、5秒钟,后来我降到1秒,降到200ms,降到50ms,最后降到了5ms,这其中的乐趣不是能描述出来的。界面也花了很大的功夫,很多时候为了一个小控件的使用方法,自定义控件,图片的颜色,GDI+,windows消息机制,google了好久,此后的好久我再写MFC程序的时候都要翻翻这个小程序找到一些用法。程序中使用了3个customer control,自己定义样式,属性,事件,其实很多人抱怨MFC控件少,老,陈旧,都是片面的,现在的桌面程序还没有几个完全是.NET写的,当自己创建一个控件,然后使用,会发现MFC的健壮性,扩展性直到如今都是那么值得称赞。

但是后来又没有完成所有功能,好像是累了,懒了,不愿写了,功能都是重复的,就是填代码了,缺少了刚开始的兴奋,所以就没写完。但也可以玩一玩,还是蛮有趣的。

现在我就把它开源出来,给那些MFC的初学者一个小例子,希望能够帮助到一些人,环境是VS2008 SP1

项目地址:http://code.google.com/p/sudoku-xiu/

浅谈公钥密码

前篇文章谈到一个非对称密钥加密系统,觉得很是神奇,一直想找一个实例,最近查阅了一些资料,google了一下,找到一些,分享一下。

它的用途有很多,数字证书啊,https啊,我感触最深的就是那个ssl加密,感觉很神奇,试想你和网站中间的路由一直在监听你们的传输数据,甚至从发送证书开始,只要通过ssl加密,它就不能窃取了(当然没那么绝对)。

首先看左图,有一个RSA看到了吧,他是很关键的一个密码加密系统,gmail网站有一个公钥,它是对所有人公开的,任何访问它的人都可以得到,用它可以进行加密;然后它还有一个密钥,通过密钥就可以对加密内容解密,gmail的任务是保管好密钥,任何人都不能得到。

大家可能会在网上搜到两个大素数的积分解困难等关键字,却不太明白具体的原理,我在这儿举个例子,例子是在一本叫《公钥密码学》上看到的,很简单,能让我们懂得基本原理。

参数生成:

(1) 选取两个大素数p和q (保密)

(2) 计算n=pq(公开的系统参数),γ=(p-1)(q-1)(保密)

(3) 随机选取整数e(公开的加密密钥),使得gcd(e, γ)=1

(4) 计算d(保密,私人密钥),使得ed≡1(mod γ),即d=e-1(mod γ)

(5) 加密:c=me mod n

(6) 解密:m=cd mod n

举一个实际的例子:

p = 11, q = 23,则 n = pq = 253

γ=(p-1)(q-1) = 220

选取加密密钥 e = 3,显然gcd(3, 220) = 1,求得 d = 147。

对于明文 m = 165,有密文 c ≡ 165 * 165 * 165 mod 253 ≡ 110

对于密文 c = 110,有明文 m ≡ 110^147 mod 253 ≡ 165

看,上述就是一个简单加密,解密的例子,你可能会说p, q岂不是很容易猜出来,请记住“两个素数的积分解困难”,很大的!

完成这步之后,客户端浏览器按照服务器的只是生成128位的RC4对称密钥,你可能会问,这个时候为什么不用非对称的?因为效率!非对称虽然有很多的好处,但是有效率限制,再说双方通过RC4传输,通过刚才的非对称加密已经保证这个RC4密钥的安全性了,为什么还要再用非对称呢。

当然这个RC4不是绝对的,服务器也可能要求使用别的加密方法,例如微软的live用的是128位的AES,QQ邮箱用了256位的AES,但他们都是对称密钥加密。

顺便再提一嘴MD5,本来和密码没什么关系,但是学习的过程中,仿佛在说不可能有两个MD5一样的不同文件。我就一直在想,如果通过一个128位的字符串就能表示几G的电影,岂不是说任何文件都能压缩到128个字节,或者说128位字符串能表示所有文件?

其实是我的理解错误,MD5的算法网上有很多,大家看一下就会发现,确实文件之修改一点点都会造成MD5的值发生变化。

它的要求是:
对任何给定的码h,寻找x使得H(x)=h在计算上,是不可行的,称为单项性;
对任何给定的分组x,寻找不等于x的y,使得H(y)=H(x)在计算上是不可行的。称为弱抗冲突;
寻找对任何的(x,y)对,使得H(y)=H(x)在计算上是不可行的,称为强抗冲突;

看,上述的都是强调在计算上,上网搜一下MD5碰撞,你就会发现存在两个不同文件MD5值相同。

好,今天到这里,文章可能有疏漏,请指正!

ArchLinux折腾记

Arch[ɑ:tʃ] Linux,是一种以轻量简洁为设计理念的Linux发行版。其开发团队秉承简洁、优雅、正确和代码最小化的设计宗旨。虽然可能没有Gentoo简洁,但肯定比Gentoo简单多了,我也是看到周围很多人都在使用这款linux,手痒痒也试玩了一下,折腾了2两天累死我了,感想是没点毅力千万别折腾这玩意,水平不见得有提高,装叉的代价实在有点高。

先说说我的环境,已经有个Windows 7,不可能卸载,原先还有个Fedora。首先在windows下删掉了Fedora分区,然后下载了ArchLinux的安装镜像iso文件,按照网上说的,装上了很多人说的Universal-USB-Installer,但是不好使,U盘启动不能被识别,试了很多其它的工具也都不行,最后用UltraISO将镜像文件烧到了U盘,开机启动可以识别(注意UltralISO写入方式选择USB-HDD,网上说选择USB-ZIP兼容性好但是我这里开机不识别)。

然后就是普通的安装方式了,网上有详细的图解教程,但是有一点,我遇到了一个问题就是硬盘分区安装文件用的是cfdisk,但是cfdisk提示我的硬盘什么结尾错误,就是不能打开,网上说解决办法是格式化整个硬盘,这不扯淡吗。。。没办法,退出安装进程,在U盘的linux下用fdisk命令新建、格式化分区,首先是:fdisk /dev/sda,然后n一个500M大小的boot分区,再n一个2G的swap分区,其他的是根目录,w命令写入。写入之后mkfs -t ext3 /dev/sda6,以ext3格式化那个boot分区,再mkswap /dev/sda7格式化swap分区,mkfs -t ext4 /dev/sda8格式化跟目录分区。然后再次进入arch/setup,这回就不用选那个Manually Partition Hard Device了,直接进入Configure block devices那个。然后选择对应的filesystem type。 然后的安装就顺利多了,最后有一个grub安装在哪里,记得选择/dev/sda,不带1,即第一个选项,当初我傻傻的选择了boot分区,结果可想而知。

接下来就是最痛苦的,由于一些原因,我的计算机必须链接vpn才能上网,没错,国内网也得连vpn。于是花了很长时间痛苦的寻找命令行下链接vpn的方法,其间别提多抓狂了。甚至想过先把xorg用别的电脑下下来然后放到这里安装。。。

我的最终解决方法:首先用别的电脑下一个pptpsetup安装包,archlinux官网就有,然后用pacman -U 命令,网上刚开始说用pacman -A,我不知道那是什么时候的,反正我这里是不行,必须用-U,期间还有点小挫折,由于系统默认选择的中文,pacman安装显示错误乱马,无奈又改成了英文,原来我自己建的vpn文件导致安装错误,删除即可。装完pptpsetup之后

pptpsetup –create vpnname –server x.x.x.x –username yourusername –password yourpassword –encrypt –start

建立一个vpn连接,然后pon vpnname即连接了,这时候如果ifconfig应该能看到ppp0了,但是注意vpn连接了,你的网却不走vpn通道,这时候还要一个命令,将路由设成走vpn

route add default dev ppp0

这时候你如果ping google.com,显示未知网络,恭喜你,又碰到和我一样的错误,这时候修改/etc/resolv.conf,即dns配置,从别的计算机拷一个dns写进去,然后再ping一下试试,我这个时候经过一天的折腾已经可以ping通了。

好了,能联网就简单多了,接下来就按网上的很多示例,你如果愿意安装xorg也行,然后我这里安装完gnome后又出现startx无法打开,黑屏,显卡驱动的问题,安装xf86-video-intel,xf86-input-keyboard,xf86-input-mouse然后再startx,应该就能看到了。

好,以上就是我安装arch的血泪史,如果你没碰到上述问题,我只能说恭喜。。。

ps:经过安装各种软件之后,我发现我的arch和原先的fedora已经差不多了。。。

ssl和https协议详解

把这几天学习到的关于ssl和https协议的内容在这里分享一下,适合一些像我一样的网络协议初学者。

ssl协议的起源和历史我就不再多说了,就是那个Netscape 网景公司开发的,它的作用主要是提供了一种安全传输方式,我们知道网上有很多的时候需要我们去输入用户名和密码,那么假设我们自己的电脑防病毒还可以,但是用户名和密码肯定还是要通过互联网来传到服务器那里,这个步骤就要经过很多的路由等,如果明文传输,就可以在你的局域网内或者通过的路由中监听,窃取你的用户名密码。

SSL协议位于TCP/IP协议与各种应用层协议之间。当我们打开一个https的网页时,步骤如下:

1. 客户端通过SSL协议把服务器需要的客户端的SSL版本信息,加密算法设置,会话数据,发送给服务器。

2. 服务器通过SSL协议把自己的SSL的版本信息,加密算法设置,会话数据和其他通信需要的信息发给客户端。服务器也把服务器的证书发给客户端,另外如果客户端请求服务器资源需要客户端认证,服务器端就会请求客户端的证书。

3. 客户端使用这些服务器发来的信息认证服务器。如果服务器不能被认证,那么客户将被提示一个警告,并且通知客户不能建立加密和认证连接。如果服务器被成功认证,客户端将进入第四步。

4. 使用到目前为止的所有数据生成握手过程。客户端(和服务器合作之下)为会话创建一个pre-master secret(一个用在对称加密密钥生成中的 46 字节的随机数字)。使用服务器的公共密钥加密(在第二步的服务器的证书中获得公共密钥),然后把这个加了密的pre-master secret发送给服务器。

5. 如果服务器请求客户端认证(在握手过程是可选项),客户端也需要标记一个特殊的数据包,客户端和服务器都知道的。在这个过程中,客户端发送一个通过pre-master secret加密过的标记的数据包和客户端自己的证书给服务器。

6. 如果服务器请求了客户端的认证,那么服务器就要尝试去认证客户端。(具体的看客户端认证细节)如果客户端认证不通过,会话将被终止。如果客户端被认证通过,服务器将使用私有密钥解密pre-master secret,然后执行一系列步骤生成master secret

7. 客户端和服务器端使用master secret去生成会话密钥。会话密码是在ssl 会话的时候对称密钥被用来加密,解密信息校验信息完整性的密钥。(检查会话过程中任何数据改变)

8. 客户端发送一个信息给服务器端,通知服务器端未来的信息将被会话密码加密,然后客户端发送一个单独(加密)信息指示客户端部分的握手会话已经完成。

9. 服务器发送一个信息通知客户端未来的会话信息将被会话密码加密,然后服务器发送一个单独(加密)信息指示服务器部分的握手部分已经完成

10. SSL握手结束,开始正式会话。客户端和服务器端使用对称会话密钥加密解密数据并且互相传送校验完整性。

11. 这是一个正常的操作过程和加密隧道。在任何时候,当内部或者外部触发条件(不是自动就是用户手动),任何一端就要从新协商会话,所有的流程将从新开始。

有几个问题我在学过之后一直在考虑:

1. 如果中间的路由从双方发送证书的时候就开始监听的话呢,是否就可以窃取内容了?

答:否,服务器那边有一个非对称密钥加密系统,首先他将公开密钥发送给客户端,客户端接收之后为会话创建一个pre-master secret(一个用在对称加密密钥生成中的 46 字节的随机数字),然后用服务器发送过来的公开密钥加密,然后将加密后的内容发送给服务器,这两个阶段,如果有人监听,即使窃取到也没办法,首先公开密钥对所有人其实都是公开的,用公开密钥加密后的内容是非常非常难解密的,只有用服务器自己有的私有密钥解密才可以。服务器获取到46字节的随机数字之后,通过这个来对将来要发送的加密内容加密,而这个解密方法之后对应的那个客户端才知道,钥匙是通过公开密钥加密的,其他人都不知道,所有就保证了内容的安全性。

2. 我们自己建设的网站有时会使用没有正式证书的ssl加密,浏览器会提醒用户,默认建议关闭,证书是必要的吗?

答:经过认证的证书其实就是确保网站的真实性,还有一些专门的使地址栏显示为绿色的也都是确保网站的真实性,防止一些页面一模一样的钓鱼网站。

3. 用ssl协议之后,我们输入用户名密码就绝对安全了吗?

答:否,ssl协议只能保证server和client传输之间的安全,如果你的电脑有木马病毒,例如监听键盘,浏览器恶意插件等,ssl可管不了这些。。。还有如果server收到攻击,它的信息流失丢掉,这也不能保证的。