在学习hadoop的时候在网上搜到这么篇bo 免费的晚餐--google技术学习http://www.blogjava.net/calvin/archive/2007/01/31/96844.html
如果说Google的搜索引擎是免费的早餐，Gmail们是免费的午餐的话， http://labs.google.com/papers/ 就是Google给开发人员们的一份免费的晚餐。 不过，咋看着一桌饭菜可能不知道从哪吃起，在自己不熟悉的领域啃英文也不是一件愉快的事情。
一、一份PPT与四份中文翻译 幸好，有一位面试google不第的老兄，自我爆发搞了一份Google Interal的PPT： http://cbcg.net/talks/googleinternals/index.html ，大家鼠标点点就能跟着他匆匆过一遍google的内部架构。
然后又有崮崮山路上走9遍(http://sharp838.mblogger.cn)与美人他爹( http://my.donews.com/eraera/)，翻译了其中最重要的四份论文：
- 《MapRedue:在超大集群上的简易数据处理》http://avindev.googlepages.com/mapreduce.doc--Simplified Data Processing on Large Clusters
- 《The Google File System》 http://avindev.googlepages.com/gfs.doc
- 《海量数据分析：Sawzall并行处理》 http://avindev.googlepages.com/sawzall.doc--Interpreting the Data: Parallel Analysis with Sawzall
- 《Bigtable:结构化数据的分布存储系统》http://my.donews.com/eraera/2006/09/26/swogzstwtqdnwlfrzgsljctkjsbrtu...--A Distributed Storage System for Structured Data
二、Google帝国的技术基石
Google帝国，便建立在大约45万台的Server上，其中大部分都是"cheap x86 boxes"。而这45万台Server，则建立于下面的key infrastructure：
1.GFS(Google File System): GFS是适用于大规模分布式数据处理应用的分布式文件系统，是Google一切的基础，它基于普通的硬件设备，实现了容错的设计与极高的性能。 李开复说：Google最厉害的技术是它的storage。我认为学计算机的学生都应该看看这篇文章http://avindev.googlepages.com/gfs.doc （再次感谢翻译的兄弟)。 它以64M为一个Chunk(Block)，每个Chunk至少存在于三台机器上，交互的简单过程见:
2.MapReduce MapReduce是一个分布式处理海量数据集的编程模式，让程序自动分布到一个由普通机器组成的超大集群上并发执行。像Grep-style job，日志分析等都可以考虑采用它。 MapReduce的run-time系统会解决输入数据的分布细节，跨越机器集群的程序执行调度，处理机器的失效，并且管理机器之间的通讯请求。这样的模式允许程序员可以不需要有什么并发处理或者分布式系统的经验，就可以处理超大的分布式系统得资源。 我自己接触MapReduce是Lucenehttp://lucene.apache.org/hadoop是Lucene之父Doug Cutting的又一力作，是Java版本的分布式文件系统与Map/Reduce实现。 Hadoop的文档并不详细，再看一遍Google这篇中文版的论文http://avindev.googlepages.com/mapreduce.doc ，一切清晰很多(一次感谢翻译的兄弟)。 孟岩也有一篇很清晰的博客：Map Reduce - the Free Lunch is not over?http://www.mengyan.org/blog/archives/2006/11/15/138.html
3.BigTable BigTable 是Google Style的数据库，使用结构化的文件来存储数据。 虽然不支持关系型数据查询，但却是建立GFS/MapReduce基础上的，分布式存储大规模结构化数据的方案。 BigTable是一个稀疏的，多维的，排序的Map，每个Cell由行关键字，列关键字和时间戳三维定位．Cell的内容是一个不解释的字符串。 比如下表存储每个网站的内容与被其他网站的反向连接的文本。 反向的URL com.cnn.www(www.cnn.com )是行的关键字；contents列存储网页内容，每个内容有一个时间戳；因为有两个反向连接，所以archor列族有两列:anchor: cnnsi.com和anchhor:my.look.ca，列族的概念，使得表可以横向扩展，archor的列数并不固定。 为了并发读写，热区，HA等考虑，BigTable当然不会存在逗号分割的文本文件中，，是存储在一种叫SSTable的数据库结构上，并有BMDiff和Zippy两种不同侧重点的压缩算法。 4.Sawzall Sawzall是一种建立在MapReduce基础上的领域语言，可以被认为是分布式的awk。它的程序控制结构(if,while)与C语言无异，但它的领域语言语义使它完成相同功能的代码与MapReduce的C++代码相比简化了10倍不止。
1 proto "cvsstat.proto"
2 submits: table sum[hour: int] of count: int;
3 log: ChangelistLog = input;
4 hour: int = hourof(log.time)
5 emit submits[hour] <- 1;
天书吗?慢慢看吧。
我们这次是统计在每天24小时里CVS提交的次数。
首先它的变量定义类似Pascal (i:int=0; 即定义变量i，类型为int，初始值为0)
1:引入cvsstat.proto协议描述，作用见后。
2:定义int数组submits 存放统计结果，用hour作下标。
3.循环的将文件输入转换为ChangelistLog 类型，存储在log变量里，类型及转换方法在前面的cvsstat.proto描述。
4.取出changlog中的提交时间log.time的hour值。
5.emit聚合，在sumits结果数组里，为该hour的提交数加1，然后自动循环下一个输入。
居然读懂了，其中1、2步是准备与定义，3、4步是Map，第5步是Reduce。
三. 小结： 本文只是简单的介绍Google的技术概貌，大家知道以后除了可作谈资外没有任何作用，我们真正要学习的骨血，是论文里如何解决高并发，高可靠性等的设计思路和细节.....
2007年3月29日星期四
2007年3月15日星期四
Metaphone Algorithm
Lawrence Philips' Metaphone Algorithm is an algorithm which returns the rough approximation of how an English word sounds.
该算法为输入的文字提供了一个英语语音发声散列。它会根据单字的发音而不是拼写生成代码。有助于提供用户支持、字典、查询、web搜索，或建立系谱等。
http://aspell.net/metaphone/里面有各个版本此算法的实现
该算法为输入的文字提供了一个英语语音发声散列。它会根据单字的发音而不是拼写生成代码。有助于提供用户支持、字典、查询、web搜索，或建立系谱等。
http://aspell.net/metaphone/里面有各个版本此算法的实现
2007年3月13日星期二
2007年3月9日星期五
失去幸福只是一念之间
A在家附近的H城上大学，认识了比她大几岁的的B，相恋3年。
B在H城有房有车有稳定的好工作，人也不错。
A毕业后在H城找了份工作，和B住在了一起，半年一年后打算结婚。
双方的父母都非常喜欢他们孩子的另一半。
说到这里看官们都会觉得挺圆满的阿，是吧？
--------------------------阴沉的分割线------------------------------------------
A在工作的时候认识了比她大几岁的C。
C单身，长得帅气，家境很好，自己在S城，K城等大城市有很多事业生意。
A初对其有好感，C也开始对A发起攻势，A接受了C的追求（也许A对与B间渐渐平淡的爱情习惯，只是笔者观点）
就这样交往了半年，当然B不知道。
A还是住在H城，工作时或是假期能见C。
C总是很忙，经常去外地出差。在A眼里，B能更好的照顾她，而C不能。
A觉得自己很爱C，但是对B也有感情。如果要她离开B，她也做不到。
于是她给自己一年的时间来做选择
可是有一天，A忽然发现自己 -----------怀了C的孩子
A告诉了C，C要她离开H城离开B，到S城和C领证，把孩子生下来
A很痛苦，她这时候才发现，当真要做出选择离开B的时候，才发现自己对B的感情是多么地深
她觉得怎么也离不开B。
---------------------------End分割线----------------------
真实的故事，大致就是这样，鄙人表述差劲，不过都是客观叙述
看官莫怪，请抓住重点：
有何看法？
A该怎么选择？（笔者注：A怀上C的孩子只有A和C知道，当然笔者也算，不过笔者是局外人可忽略）
B在H城有房有车有稳定的好工作，人也不错。
A毕业后在H城找了份工作，和B住在了一起，半年一年后打算结婚。
双方的父母都非常喜欢他们孩子的另一半。
说到这里看官们都会觉得挺圆满的阿，是吧？
--------------------------阴沉的分割线------------------------------------------
A在工作的时候认识了比她大几岁的C。
C单身，长得帅气，家境很好，自己在S城，K城等大城市有很多事业生意。
A初对其有好感，C也开始对A发起攻势，A接受了C的追求（也许A对与B间渐渐平淡的爱情习惯，只是笔者观点）
就这样交往了半年，当然B不知道。
A还是住在H城，工作时或是假期能见C。
C总是很忙，经常去外地出差。在A眼里，B能更好的照顾她，而C不能。
A觉得自己很爱C，但是对B也有感情。如果要她离开B，她也做不到。
于是她给自己一年的时间来做选择
可是有一天，A忽然发现自己 -----------怀了C的孩子
A告诉了C，C要她离开H城离开B，到S城和C领证，把孩子生下来
A很痛苦，她这时候才发现，当真要做出选择离开B的时候，才发现自己对B的感情是多么地深
她觉得怎么也离不开B。
---------------------------End分割线----------------------
真实的故事，大致就是这样，鄙人表述差劲，不过都是客观叙述
看官莫怪，请抓住重点：
有何看法？
A该怎么选择？（笔者注：A怀上C的孩子只有A和C知道，当然笔者也算，不过笔者是局外人可忽略）
2007年3月7日星期三
Levenshtein Distance
The Levenshtein distance algorithm is used In Class FuzzyQuery
What is Levenshtein Distance?[http://www.merriampark.com/ld.htm]
Levenshtein distance (LD) is a measure of the similarity between two strings, which we will refer to as the source string (s) and the target string (t). The distance is the number of deletions, insertions, or substitutions required to transform s into t. For example, If s is "test" and t is "test", then LD(s,t) = 0, because no transformations are needed. The strings are already identical.
If s is "test" and t is "tent", then LD(s,t) = 1, because one substitution (change "s" to "n") is sufficient to transform s into t. The greater the Levenshtein distance, the more different the strings are.
Levenshtein distance is named after the Russian scientist Vladimir Levenshtein, who devised the algorithm in 1965. If you can't spell or pronounce Levenshtein, the metric is also sometimes called edit distance.
The Levenshtein distance algorithm has been used in:
Spell checking、Speech recognition 、DNA analysis 、Plagiarism detection
FuzzyQuery distance formula = 1 - distance/min(textlen,targetlen)
FuzzyQuery enumerates all terms in an index to find terms within theallowable threshold. Use this type of query sparingly, or at least with theknowledge of how it works and the effect it may have on performance.
What is Levenshtein Distance?[http://www.merriampark.com/ld.htm]
Levenshtein distance (LD) is a measure of the similarity between two strings, which we will refer to as the source string (s) and the target string (t). The distance is the number of deletions, insertions, or substitutions required to transform s into t. For example, If s is "test" and t is "test", then LD(s,t) = 0, because no transformations are needed. The strings are already identical.
If s is "test" and t is "tent", then LD(s,t) = 1, because one substitution (change "s" to "n") is sufficient to transform s into t. The greater the Levenshtein distance, the more different the strings are.
Levenshtein distance is named after the Russian scientist Vladimir Levenshtein, who devised the algorithm in 1965. If you can't spell or pronounce Levenshtein, the metric is also sometimes called edit distance.
The Levenshtein distance algorithm has been used in:
Spell checking、Speech recognition 、DNA analysis 、Plagiarism detection
FuzzyQuery distance formula = 1 - distance/min(textlen,targetlen)
FuzzyQuery enumerates all terms in an index to find terms within theallowable threshold. Use this type of query sparingly, or at least with theknowledge of how it works and the effect it may have on performance.
2007年3月3日星期六
Lucene2.0以后的Field构造变化
看《lucene in action》时，对文中的示例代码实践时发现Field的一些方法不存在(Field.text, Field.Keyword...)。怀疑是书中采用的版本过老。我下来的是最新的2.1版本(17 February 2007 - Release 2.1 available)。查看了下其附带的api doc，Field类方法中的确没有书上的。取而代之的是直接使用Field的构造函数，共有5种构造函数：
Field(String name, byte[] value, Field.Store store)
Field(String name, Reader reader)
Field(String name, Reader reader, Field.TermVector termVector)
Field (String name, String value, Field.Store store, Field.Index index)
Field (String name, String value, Field.Store store, Field.Index index, Field.TermVector termVector)
依照doc说明用新构造函数试写了一下，得到新旧的方法对应：
Field.Index-----Field.Store-------- 说明
TOKENIZED---------- YES--------- 被分词索引且存储(Field.Text)
TOKENIZED----------- NO--------- 被分词索引但不存储(Field.Unstored)
NO--------------------- YES--------- 附属物。如URL等(Field.UnIndexed)
UN_TOKENIZED------Y/N-------- 不被分词作为一个整体(Field.Keyword)
NO----------------------NO----------不用
信息检索工具库
年前接到一个情报搜索的项目，由于客户需要两周内出Demo试用，于是和标哥利用Rss搜集资料应付完回家过年。
年后回来的任务就是切切实实的做个信息搜集、分析和搜索的核心模块来替换掉原来糊弄的Rss搜集模块。项目需求也不是很急，于是可以静下心来找找相关内容学习学习。况也没有过做这方面的经验，扫盲是必须的- -
先打算看看信息检索方面的dd。站在dev的立场上找了找信息检索工具库：lucene, egothor, Xapian...恩，就拿lucene开看好了，原因么有三：一是写java多了，c++丢得差不多了，于是先把Xapian给T了；二是egothor和lucene虽然都很不错，但是后者以前好歹是看过点的，也知道Nutch，上手比较快；三大概就是lucene的资料比较好找吧。。。。。。
另外提下MG4J，这个提供建立java信息检索库所需要的底层支持。主要是对收集到的数据进行分析的dd。觉得也许项目以后要对爬到的网页数据进行一定的自定义分析操作，再结合信息检索工具提供查找服务。等补完lucene再来看看这个dd吧，网址列在这里备忘@@... http://mg4j.dsi.unimi.it/
年后回来的任务就是切切实实的做个信息搜集、分析和搜索的核心模块来替换掉原来糊弄的Rss搜集模块。项目需求也不是很急，于是可以静下心来找找相关内容学习学习。况也没有过做这方面的经验，扫盲是必须的- -
先打算看看信息检索方面的dd。站在dev的立场上找了找信息检索工具库：lucene, egothor, Xapian...恩，就拿lucene开看好了，原因么有三：一是写java多了，c++丢得差不多了，于是先把Xapian给T了；二是egothor和lucene虽然都很不错，但是后者以前好歹是看过点的，也知道Nutch，上手比较快；三大概就是lucene的资料比较好找吧。。。。。。
另外提下MG4J，这个提供建立java信息检索库所需要的底层支持。主要是对收集到的数据进行分析的dd。觉得也许项目以后要对爬到的网页数据进行一定的自定义分析操作，再结合信息检索工具提供查找服务。等补完lucene再来看看这个dd吧，网址列在这里备忘@@... http://mg4j.dsi.unimi.it/
订阅：
评论 (Atom)