随笔 - 89  文章 - 118  trackbacks - 0
<2013年9月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

The following code is better than most of the results returned by baidu or google. Time complexity is O((m+n)/2), Space complexity is O(1).

 1 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
 2 {
 3     int nums1_i = 0, nums2_i = 0; 
 4     int mid1 = 0, mid2 = 0, count = 0;
 5     while (nums1_i < nums1.size() && nums2_i < nums2.size()) 
 6     {
 7         if (count++ > ((nums1.size() + nums2.size()) / 2))    break;
 8         mid1 = mid2;
 9         mid2 = (nums1[nums1_i] < nums2[nums2_i] ? nums1[nums1_i++] : nums2[nums2_i++]);
10     }  
11 
12     while (nums1_i < nums1.size()) 
13     {  
14         if (count++ > ((nums1.size() + nums2.size()) / 2))    break;
15         mid1 = mid2;
16         mid2 = nums1[nums1_i++];
17     }  
18 
19     while (nums2_i < nums2.size()) 
20     {  
21         if (count++ > ((nums1.size() + nums2.size()) / 2))    break;
22         mid1 = mid2;
23         mid2 = nums2[nums2_i++];
24     }  
25 
26     return (nums1.size() + nums2.size()) % 2 == 0 
27         ? (mid1 + mid2) / 2.0
28         : mid2; 
29 }
posted @ 2018-06-26 13:57 胡满超 阅读(441) | 评论 (0)编辑 收藏
     摘要: 通过这篇文章我们主要回答以下几个问题:   1.    LSH解决问题的背景,即以图片相似性搜索为例,如何解决在海量数据中进行相似性查找? 2.    图像相似性查找的连带问题:相似性度量,特征提取; 3.    LSH的数学分析,即局部敏感HASH函数的数学原理,通过与、或构造提升查找的查...  阅读全文
posted @ 2018-02-24 13:10 胡满超 阅读(8799) | 评论 (0)编辑 收藏
直接上图


脑图源文件下载地址
http://www.cppblog.com/Files/humanchao/LSH(Locality%20Sensitive%20Hashing).zip

参考文献:

Website:

[1] http://people.csail.mit.edu/indyk/ (LSH原作者)

[2] http://www.mit.edu/~andoni/LSH/ (E2LSH)


Paper:

[1] Approximate nearest neighbor: towards removing the curse of dimensionality

[2] Similarity search in high dimensions via hashing

[3] Locality-sensitive hashing scheme based on p-stable distributions 

[4] MultiProbe LSH Efficient Indexing for HighDimensional Similarity Search

[5] Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions

Tutorial:

[1] Locality-Sensitive Hashing for Finding Nearest Neighbors

[2] Approximate Proximity Problems in High Dimensions via Locality-Sensitive Hashing

[3] Similarity Search in High Dimensions


Book:

[1] Mining of Massive Datasets
[2] Nearest Neighbor Methods in Learning and Vision: Theory and Practice


Cdoe:

[1] http://sourceforge.net/projects/lshkit/?source=directory

[2] http://tarsos.0110.be/releases/TarsosLSH/TarsosLSH-0.5/TarsosLSH-0.5-Readme.html 

[3] http://www.cse.ohio-state.edu/~kulis/klsh/klsh.htm 

[4] http://code.google.com/p/likelike/ 

[5] https://github.com/yahoo/Optimal-LSH

[6] OpenCV LSH(分别位于legacy module和flann module中)




posted @ 2017-05-24 09:16 胡满超 阅读(1045) | 评论 (0)编辑 收藏

想转型的都是那些不甘于现状的,我就是其中之一。

 

我是2005年毕业,从毕业前的实习开始,做CAD二次开发,电气设计软件。

2006年转做无纸办公软件,那个年代无纸办公流行,C++更是主流,感觉也算有前途。

2008年转做Open Office的开发,维护世界级的产品会产生一种自豪感,Open Office本身代码体量也的确非常大。

2010年转做安全类的产品,从一个模块级负责人,核心程序员,到架构师,再到负责整体产品线的负责人,经历了4年时间。

 

在我的职业生涯中时不时就会产生一种莫名的危机感,经常会问自己,自己掌握的技术够深吗、是主流的技术吗、未来的职业发展又在哪里?

 

2006年一个同事跳槽去了一家大型企业,走的时候跟我们说,做二次开发没有前途,出去面试会被人看不起。但是我发现,在具体编码的过程中,很多经验丰富的程序员甚至不能把一个对话框程序写的很漂亮,一个对话框类的实现将界面与逻辑混在一起,没有太多解耦的思想在里面。后来的工作中悟出一个道理,没有小角色,只有小演员,只有把现在的事情做好,才能有未来。

 

2008年我在一个不满意的环境中,苦苦的寻找下一步的方向,从坐落在小区里的公司一直面试到了微软和IBM这个级别的公司里。被挫了很多次,也积累了很多面试的经验。其间有一家做搜索引擎的公司我没去成,我的理由只是因为工资没有任何提高。其实大家跳槽的时候都说是为了职业发展,结果往往是哪里给的条件好就去哪里,而在一般意义上看,高工资与好公司一般都是成正比的。当然偶尔也有例外,比如这里提到的做搜索的公司,如果当初在08的时候就选择做搜索引擎,也许后面的故事会很不同。

 

2010年我拥有了工作5年的工作经验,我发现一般工作到5年以后才会遇到一些真正的好机会。跳槽去了一家刚刚在创业板上市不久的公司,做一些安全类的产品。从这一刻开始,由于业务的快速发展和领导的信任,我开始拥有了一些能够独当一面的能力与锻炼机会。除了编写一些从无到有的模块,我开始关注架构的设计,团队培养,产品管理等一系列更宏观的问题。

 

回到原来的问题,我们为什么要转型,原因总结如下:

 

1.       大多数的程序员职业起点都偏低,很多人甚至只能从外包做起;

2.       大多数的程序员做不上主流产品,主流技术,所掌握的都是一些较为落后的技能,靠体力挣钱,而不是靠智力;

3.       很多公司不能给员工稳定的成长预期,过了某一个发展阶段双方很难找到共赢点;

4.       世界发展太快,当我们还在懵懂之时外面世界已经经历了从互联网,云计算,移动互联网,大数据,人工智能,一波又一波的产业升级。而我们一波都没赶上。

 

于是我们要转型。2011年当我看到hadoop权威指南这本书的时候,我感觉大数据一起会流行起来,而且大数据未来会在各行各业遍地开花。

 

可是,留给学习的时间真的很少,工作忙碌,下班要顾家。只好挤时间学习,在上班的路上,坐公交车、坐地铁,给小孩洗衣服,可以带着耳机听视频,成了唯一的学习方式。听视频虽然不能学到太多技术精髓,但也可以了解不少技术,开阔眼界。

 

2014年底,我转型做一些也数据相关的工作,做数据清洗,分析,建模,治理。我总结一下转型要做的一些事情以及要学的东西。

 

1.       要有行动,只停留在想法层面产生不了任何实质上的进展;

2.       挤时间,时间对于每一个认真生活的人都很宝贵,挤一下吧,少玩玩游戏啥的,总会有的;

3.       要重视学习,尤其是看书进行系统学习,从网络上看到的只言片语做为了解还行,但是不去系统掌握知识,境界很难上到新的台阶;

4.       要注视理论学习,上班以后最不缺少的就是实践,天天都在实践反而凸显的学习理论的重要性;

5.       把主要学习时间花在那些最通用、最被广泛采用的技术上,如果每天都在学习那些其他公司所不需要的领域知识时,说明该跳槽了;

6.       要注重基本的数据结构和算法,这些是写好程序的基础,基础决定高度,做那些能够解决困难问题的人,而不是做只能执行具体任务的人。差别在于能不能把现实的工程问题抽象成数据与算法。

7.       选一个好的方向,像高并发,分布式系统,数据库,大数据工具,统计建模,机器学习,数据挖掘都是即有用又缺人的领域,搞好任何一个领域都会有好的发展;

8.       我感觉能把数据分析、机器学习、自然语言处理、R语言这些学好,统计建模依然是很基础知识,不能跳跃学习;

9.       学习最重要的是入门与坚持,入门可以学视频教程,精深要靠应用与时间打磨;

 

就程序员的职业发展来看,我总结自己的一些经验:

 

1.       1~3年,要学精一门语言,这并不太难;

2.       3~5年,应该关注软件的设计,设计模式等知识

3.       5~7年,应该能独立完成一个软件模块,从需求到测试的全过程。我发现一般这个阶段会遇到一些获得期权或者股权的机会,能不能最终形成收益看运气吧;

4.       7~10年,争取可以负责更为全面的工作

 

在这个过程中,像数据库,操作系统,并发,多线程,项目管理,产品管理这些知识都需要,掌握的越多越好吧。

 

开发一个数据产品跟一个传统软件产品并没有太大的本质差异,很多技能从事哪个行业都是需要的。

 

posted @ 2016-07-14 13:24 胡满超 阅读(1755) | 评论 (0)编辑 收藏
https://www.packtpub.com/books/content/support/17400

本地下载
posted @ 2016-01-13 11:08 胡满超 阅读(22178) | 评论 (0)编辑 收藏
一级国标汉字(3755个)

啊阿埃挨哎唉哀皑癌蔼矮艾碍爱隘鞍氨安俺按暗岸胺案肮昂盎凹敖熬翱袄傲奥懊澳芭捌扒叭吧笆八疤巴拔跋靶把耙坝霸罢爸白柏百摆佰败拜稗斑班搬扳般颁板版扮拌伴瓣半办绊邦帮梆榜膀绑棒磅蚌镑傍谤苞胞包褒剥薄雹保堡饱宝抱报暴豹鲍爆杯碑悲卑北辈背贝钡倍狈备惫焙被奔苯本笨崩绷甭泵蹦迸逼鼻比鄙笔彼碧蓖蔽毕毙毖币庇痹闭敝弊必辟壁臂避陛鞭边编贬扁便变卞辨辩辫遍标彪膘表鳖憋别瘪彬斌濒滨宾摈兵冰柄丙秉饼炳病并玻菠播拨钵波博勃搏铂箔伯帛舶脖膊渤泊驳捕卜哺补埠不布步簿部怖擦猜裁材才财睬踩采彩菜蔡餐参蚕残惭惨灿苍舱仓沧藏操糙槽曹草厕策侧册测层蹭插叉茬茶查碴搽察岔差诧拆柴豺搀掺蝉馋谗缠铲产阐颤昌猖场尝常长偿肠厂敞畅唱倡超抄钞朝嘲潮巢吵炒车扯撤掣彻澈郴臣辰尘晨忱沉陈趁衬撑称城橙成呈乘程惩澄诚承逞骋秤吃痴持匙池迟弛驰耻齿侈尺赤翅斥炽充冲虫崇宠抽酬畴踌稠愁筹仇绸瞅丑臭初出橱厨躇锄雏滁除楚础储矗搐触处揣川穿椽传船喘串疮窗幢床闯创吹炊捶锤垂春椿醇唇淳纯蠢戳绰疵茨磁雌辞慈瓷词此刺赐次聪葱囱匆从丛凑粗醋簇促蹿篡窜摧崔催脆瘁粹淬翠村存寸磋撮搓措挫错搭达答瘩打大呆歹傣戴带殆代贷袋待逮怠耽担丹单郸掸胆旦氮但惮淡诞弹蛋当挡党荡档刀捣蹈倒岛祷导到稻悼道盗德得的蹬灯登等瞪凳邓堤低滴迪敌笛狄涤翟嫡抵底地蒂第帝弟递缔颠掂滇碘点典靛垫电佃甸店惦奠淀殿碉叼雕凋刁掉吊钓调跌爹碟蝶迭谍叠丁盯叮钉顶鼎锭定订丢东冬董懂动栋侗恫冻洞兜抖斗陡豆逗痘都督毒犊独读堵睹赌杜镀肚度渡妒端短锻段断缎堆兑队对墩吨蹲敦顿囤钝盾遁掇哆多夺垛躲朵跺舵剁惰堕蛾峨鹅俄额讹娥恶厄扼遏鄂饿恩而儿耳尔饵洱二贰发罚筏伐乏阀法珐藩帆番翻樊矾钒繁凡烦反返范贩犯饭泛坊芳方肪房防妨仿访纺放菲非啡飞肥匪诽吠肺废沸费芬酚吩氛分纷坟焚汾粉奋份忿愤粪丰封枫蜂峰锋风疯烽逢冯缝讽奉凤佛否夫敷肤孵扶拂辐幅氟符伏俘服浮涪福袱弗甫抚辅俯釜斧脯腑府腐赴副覆赋复傅付阜父腹负富讣附妇缚咐噶嘎该改概钙盖溉干甘杆柑竿肝赶感秆敢赣冈刚钢缸肛纲岗港杠篙皋高膏羔糕搞镐稿告哥歌搁戈鸽胳疙割革葛格蛤阁隔铬个各给根跟耕更庚羹埂耿梗工攻功恭龚供躬公宫弓巩汞拱贡共钩勾沟苟狗垢构购够辜菇咕箍估沽孤姑鼓古蛊骨谷股故顾固雇刮瓜剐寡挂褂乖拐怪棺关官冠观管馆罐惯灌贯光广逛瑰规圭硅归龟闺轨鬼诡癸桂柜跪贵刽辊滚棍锅郭国果裹过哈骸孩海氦亥害骇酣憨邯韩含涵寒函喊罕翰撼捍旱憾悍焊汗汉夯杭航壕嚎豪毫郝好耗号浩呵喝荷菏核禾和何合盒貉阂河涸赫褐鹤贺嘿黑痕很狠恨哼亨横衡恒轰哄烘虹鸿洪宏弘红喉侯猴吼厚候后呼乎忽瑚壶葫胡蝴狐糊湖弧虎唬护互沪户花哗华猾滑画划化话槐徊怀淮坏欢环桓还缓换患唤痪豢焕涣宦幻荒慌黄磺蝗簧皇凰惶煌晃幌恍谎灰挥辉徽恢蛔回毁悔慧卉惠晦贿秽会烩汇讳诲绘荤昏婚魂浑混豁活伙火获或惑霍货祸击圾基机畸稽积箕肌饥迹激讥鸡姬绩缉吉极棘辑籍集及急疾汲即嫉级挤几脊己蓟技冀季伎祭剂悸济寄寂计记既忌际妓继纪嘉枷夹佳家加荚颊贾甲钾假稼价架驾嫁歼监坚尖笺间煎兼肩艰奸缄茧检柬碱硷拣捡简俭剪减荐槛鉴践贱见键箭件健舰剑饯渐溅涧建僵姜将浆江疆蒋桨奖讲匠酱降蕉椒礁焦胶交郊浇骄娇嚼搅铰矫侥脚狡角饺缴绞剿教酵轿较叫窖揭接皆秸街阶截劫节桔杰捷睫竭洁结解姐戒藉芥界借介疥诫届巾筋斤金今津襟紧锦仅谨进靳晋禁近烬浸尽劲荆兢茎睛晶鲸京惊精粳经井警景颈静境敬镜径痉靖竟竞净炯窘揪究纠玖韭久灸九酒厩救旧臼舅咎就疚鞠拘狙疽居驹菊局咀矩举沮聚拒据巨具距踞锯俱句惧炬剧捐鹃娟倦眷卷绢撅攫抉掘倔爵觉决诀绝均菌钧军君峻俊竣浚郡骏喀咖卡咯开揩楷凯慨刊堪勘坎砍看康慷糠扛抗亢炕考拷烤靠坷苛柯棵磕颗科壳咳可渴克刻客课肯啃垦恳坑吭空恐孔控抠口扣寇枯哭窟苦酷库裤夸垮挎跨胯块筷侩快宽款匡筐狂框矿眶旷况亏盔岿窥葵奎魁傀馈愧溃坤昆捆困括扩廓阔垃拉喇蜡腊辣啦莱来赖蓝婪栏拦篮阑兰澜谰揽览懒缆烂滥琅榔狼廊郎朗浪捞劳牢老佬姥酪烙涝勒乐雷镭蕾磊累儡垒擂肋类泪棱楞冷厘梨犁黎篱狸离漓理李里鲤礼莉荔吏栗丽厉励砾历利傈例俐痢立粒沥隶力璃哩俩联莲连镰廉怜涟帘敛脸链恋炼练粮凉梁粱良两辆量晾亮谅撩聊僚疗燎寥辽潦了撂镣廖料列裂烈劣猎琳林磷霖临邻鳞淋凛赁吝拎玲菱零龄铃伶羚凌灵陵岭领另令溜琉榴硫馏留刘瘤流柳六龙聋咙笼窿隆垄拢陇楼娄搂篓漏陋芦卢颅庐炉掳卤虏鲁麓碌露路赂鹿潞禄录陆戮驴吕铝侣旅履屡缕虑氯律率滤绿峦挛孪滦卵乱掠略抡轮伦仑沦纶论萝螺罗逻锣箩骡裸落洛骆络妈麻玛码蚂马骂嘛吗埋买麦卖迈脉瞒馒蛮满蔓曼慢漫谩芒茫盲氓忙莽猫茅锚毛矛铆卯茂冒帽貌贸么玫枚梅酶霉煤没眉媒镁每美昧寐妹媚门闷们萌蒙檬盟锰猛梦孟眯醚靡糜迷谜弥米秘觅泌蜜密幂棉眠绵冕免勉娩缅面苗描瞄藐秒渺庙妙蔑灭民抿皿敏悯闽明螟鸣铭名命谬摸摹蘑模膜磨摩魔抹末莫墨默沫漠寞陌谋牟某拇牡亩姆母墓暮幕募慕木目睦牧穆拿哪呐钠那娜纳氖乃奶耐奈南男难囊挠脑恼闹淖呢馁内嫩能妮霓倪泥尼拟你匿腻逆溺蔫拈年碾撵捻念娘酿鸟尿捏聂孽啮镊镍涅您柠狞凝宁拧泞牛扭钮纽脓浓农弄奴努怒女暖虐疟挪懦糯诺哦欧鸥殴藕呕偶沤啪趴爬帕怕琶拍排牌徘湃派攀潘盘磐盼畔判叛乓庞旁耪胖抛咆刨炮袍跑泡呸胚培裴赔陪配佩沛喷盆砰抨烹澎彭蓬棚硼篷膨朋鹏捧碰坯砒霹批披劈琵毗啤脾疲皮匹痞僻屁譬篇偏片骗飘漂瓢票撇瞥拼频贫品聘乒坪苹萍平凭瓶评屏坡泼颇婆破魄迫粕剖扑铺仆莆葡菩蒲埔朴圃普浦谱曝瀑期欺栖戚妻七凄漆柒沏其棋奇歧畦崎脐齐旗祈祁骑起岂乞企启契砌器气迄弃汽泣讫掐恰洽牵扦钎铅千迁签仟谦乾黔钱钳前潜遣浅谴堑嵌欠歉枪呛腔羌墙蔷强抢橇锹敲悄桥瞧乔侨巧鞘撬翘峭俏窍切茄且怯窃钦侵亲秦琴勤芹擒禽寝沁青轻氢倾卿清擎晴氰情顷请庆琼穷秋丘邱球求囚酋泅趋区蛆曲躯屈驱渠取娶龋趣去圈颧权醛泉全痊拳犬券劝缺炔瘸却鹊榷确雀裙群然燃冉染瓤壤攘嚷让饶扰绕惹热壬仁人忍韧任认刃妊纫扔仍日戎茸蓉荣融熔溶容绒冗揉柔肉茹蠕儒孺如辱乳汝入褥软阮蕊瑞锐闰润若弱撒洒萨腮鳃塞赛三叁伞散桑嗓丧搔骚扫嫂瑟色涩森僧莎砂杀刹沙纱傻啥煞筛晒珊苫杉山删煽衫闪陕擅赡膳善汕扇缮墒伤商赏晌上尚裳梢捎稍烧芍勺韶少哨邵绍奢赊蛇舌舍赦摄射慑涉社设砷申呻伸身深娠绅神沈审婶甚肾慎渗声生甥牲升绳省盛剩胜圣师失狮施湿诗尸虱十石拾时什食蚀实识史矢使屎驶始式示士世柿事拭誓逝势是嗜噬适仕侍释饰氏市恃室视试收手首守寿授售受瘦兽蔬枢梳殊抒输叔舒淑疏书赎孰熟薯暑曙署蜀黍鼠属术述树束戍竖墅庶数漱恕刷耍摔衰甩帅栓拴霜双爽谁水睡税吮瞬顺舜说硕朔烁斯撕嘶思私司丝死肆寺嗣四伺似饲巳松耸怂颂送宋讼诵搜艘擞嗽苏酥俗素速粟僳塑溯宿诉肃酸蒜算虽隋随绥髓碎岁穗遂隧祟孙损笋蓑梭唆缩琐索锁所塌他它她塔獭挞蹋踏胎苔抬台泰酞太态汰坍摊贪瘫滩坛檀痰潭谭谈坦毯袒碳探叹炭汤塘搪堂棠膛唐糖倘躺淌趟烫掏涛滔绦萄桃逃淘陶讨套特藤腾疼誊梯剔踢锑提题蹄啼体替嚏惕涕剃屉天添填田甜恬舔腆挑条迢眺跳贴铁帖厅听烃汀廷停亭庭挺艇通桐酮瞳同铜彤童桶捅筒统痛偷投头透凸秃突图徒途涂屠土吐兔湍团推颓腿蜕褪退吞屯臀拖托脱鸵陀驮驼椭妥拓唾挖哇蛙洼娃瓦袜歪外豌弯湾玩顽丸烷完碗挽晚皖惋宛婉万腕汪王亡枉网往旺望忘妄威巍微危韦违桅围唯惟为潍维苇萎委伟伪尾纬未蔚味畏胃喂魏位渭谓尉慰卫瘟温蚊文闻纹吻稳紊问嗡翁瓮挝蜗涡窝我斡卧握沃巫呜钨乌污诬屋无芜梧吾吴毋武五捂午舞伍侮坞戊雾晤物勿务悟误昔熙析西硒矽晰嘻吸锡牺稀息希悉膝夕惜熄烯溪汐犀檄袭席习媳喜铣洗系隙戏细瞎虾匣霞辖暇峡侠狭下厦夏吓掀锨先仙鲜纤咸贤衔舷闲涎弦嫌显险现献县腺馅羡宪陷限线相厢镶香箱襄湘乡翔祥详想响享项巷橡像向象萧硝霄削哮嚣销消宵淆晓小孝校肖啸笑效楔些歇蝎鞋协挟携邪斜胁谐写械卸蟹懈泄泻谢屑薪芯锌欣辛新忻心信衅星腥猩惺兴刑型形邢行醒幸杏性姓兄凶胸匈汹雄熊休修羞朽嗅锈秀袖绣墟戌需虚嘘须徐许蓄酗叙旭序畜恤絮婿绪续轩喧宣悬旋玄选癣眩绚靴薛学穴雪血勋熏循旬询寻驯巡殉汛训讯逊迅压押鸦鸭呀丫芽牙蚜崖衙涯雅哑亚讶焉咽阉烟淹盐严研蜒岩延言颜阎炎沿奄掩眼衍演艳堰燕厌砚雁唁彦焰宴谚验殃央鸯秧杨扬佯疡羊洋阳氧仰痒养样漾邀腰妖瑶摇尧遥窑谣姚咬舀药要耀椰噎耶爷野冶也页掖业叶曳腋夜液一壹医揖铱依伊衣颐夷遗移仪胰疑沂宜姨彝椅蚁倚已乙矣以艺抑易邑屹亿役臆逸肄疫亦裔意毅忆义益溢诣议谊译异翼翌绎茵荫因殷音阴姻吟银淫寅饮尹引隐印英樱婴鹰应缨莹萤营荧蝇迎赢盈影颖硬映哟拥佣臃痈庸雍踊蛹咏泳涌永恿勇用幽优悠忧尤由邮铀犹油游酉有友右佑釉诱又幼迂淤于盂榆虞愚舆余俞逾鱼愉渝渔隅予娱雨与屿禹宇语羽玉域芋郁吁遇喻峪御愈欲狱育誉浴寓裕预豫驭鸳渊冤元垣袁原援辕园员圆猿源缘远苑愿怨院曰约越跃钥岳粤月悦阅耘云郧匀陨允运蕴酝晕韵孕匝砸杂栽哉灾宰载再在咱攒暂赞赃脏葬遭糟凿藻枣早澡蚤躁噪造皂灶燥责择则泽贼怎增憎曾赠扎喳渣札轧铡闸眨栅榨咋乍炸诈摘斋宅窄债寨瞻毡詹粘沾盏斩辗崭展蘸栈占战站湛绽樟章彰漳张掌涨杖丈帐账仗胀瘴障招昭找沼赵照罩兆肇召遮折哲蛰辙者锗蔗这浙珍斟真甄砧臻贞针侦枕疹诊震振镇阵蒸挣睁征狰争怔整拯正政帧症郑证芝枝支吱蜘知肢脂汁之织职直植殖执值侄址指止趾只旨纸志挚掷至致置帜峙制智秩稚质炙痔滞治窒中盅忠钟衷终种肿重仲众舟周州洲诌粥轴肘帚咒皱宙昼骤珠株蛛朱猪诸诛逐竹烛煮拄瞩嘱主著柱助蛀贮铸筑住注祝驻抓爪拽专砖转撰赚篆桩庄装妆撞壮状椎锥追赘坠缀谆准捉拙卓桌琢茁酌啄着灼浊兹咨资姿滋淄孜紫仔籽滓子自渍字鬃棕踪宗综总纵邹走奏揍租足卒族祖诅阻组钻纂嘴醉最罪尊遵昨左佐柞做作坐座
 
二级国标汉字(3008个)

亍丌兀丐廿卅丕亘丞鬲孬噩丨禺丿匕乇夭爻卮氐囟胤馗毓睾鼗丶亟鼐乜乩亓芈孛啬嘏仄厍厝厣厥厮靥赝匚叵匦匮匾赜卦卣刂刈刎刭刳刿剀剌剞剡剜蒯剽劂劁劐劓冂罔亻仃仉仂仨仡仫仞伛仳伢佤仵伥伧伉伫佞佧攸佚佝佟佗伲伽佶佴侑侉侃侏佾佻侪佼侬侔俦俨俪俅俚俣俜俑俟俸倩偌俳倬倏倮倭俾倜倌倥倨偾偃偕偈偎偬偻傥傧傩傺僖儆僭僬僦僮儇儋仝氽佘佥俎龠汆籴兮巽黉馘冁夔勹匍訇匐凫夙兕亠兖亳衮袤亵脔裒禀嬴蠃羸冫冱冽冼凇冖冢冥讠讦讧讪讴讵讷诂诃诋诏诎诒诓诔诖诘诙诜诟诠诤诨诩诮诰诳诶诹诼诿谀谂谄谇谌谏谑谒谔谕谖谙谛谘谝谟谠谡谥谧谪谫谮谯谲谳谵谶卩卺阝阢阡阱阪阽阼陂陉陔陟陧陬陲陴隈隍隗隰邗邛邝邙邬邡邴邳邶邺邸邰郏郅邾郐郄郇郓郦郢郜郗郛郫郯郾鄄鄢鄞鄣鄱鄯鄹酃酆刍奂劢劬劭劾哿勐勖勰叟燮矍廴凵凼鬯厶弁畚巯坌垩垡塾墼壅壑圩圬圪圳圹圮圯坜圻坂坩垅坫垆坼坻坨坭坶坳垭垤垌垲埏垧垴垓垠埕埘埚埙埒垸埴埯埸埤埝堋堍埽埭堀堞堙塄堠塥塬墁墉墚墀馨鼙懿艹艽艿芏芊芨芄芎芑芗芙芫芸芾芰苈苊苣芘芷芮苋苌苁芩芴芡芪芟苄苎芤苡茉苷苤茏茇苜苴苒苘茌苻苓茑茚茆茔茕苠苕茜荑荛荜茈莒茼茴茱莛荞茯荏荇荃荟荀茗荠茭茺茳荦荥荨茛荩荬荪荭荮莰荸莳莴莠莪莓莜莅荼莶莩荽莸荻莘莞莨莺莼菁萁菥菘堇萘萋菝菽菖萜萸萑萆菔菟萏萃菸菹菪菅菀萦菰菡葜葑葚葙葳蒇蒈葺蒉葸萼葆葩葶蒌蒎萱葭蓁蓍蓐蓦蒽蓓蓊蒿蒺蓠蒡蒹蒴蒗蓥蓣蔌甍蔸蓰蔹蔟蔺蕖蔻蓿蓼蕙蕈蕨蕤蕞蕺瞢蕃蕲蕻薤薨薇薏蕹薮薜薅薹薷薰藓藁藜藿蘧蘅蘩蘖蘼廾弈夼奁耷奕奚奘匏尢尥尬尴扌扪抟抻拊拚拗拮挢拶挹捋捃掭揶捱捺掎掴捭掬掊捩掮掼揲揸揠揿揄揞揎摒揆掾摅摁搋搛搠搌搦搡摞撄摭撖摺撷撸撙撺擀擐擗擤擢攉攥攮弋忒甙弑卟叱叽叩叨叻吒吖吆呋呒呓呔呖呃吡呗呙吣吲咂咔呷呱呤咚咛咄呶呦咝哐咭哂咴哒咧咦哓哔呲咣哕咻咿哌哙哚哜咩咪咤哝哏哞唛哧唠哽唔哳唢唣唏唑唧唪啧喏喵啉啭啁啕唿啐唼唷啖啵啶啷唳唰啜喋嗒喃喱喹喈喁喟啾嗖喑啻嗟喽喾喔喙嗪嗷嗉嘟嗑嗫嗬嗔嗦嗝嗄嗯嗥嗲嗳嗌嗍嗨嗵嗤辔嘞嘈嘌嘁嘤嘣嗾嘀嘧嘭噘嘹噗嘬噍噢噙噜噌噔嚆噤噱噫噻噼嚅嚓嚯囔囗囝囡囵囫囹囿圄圊圉圜帏帙帔帑帱帻帼帷幄幔幛幞幡岌屺岍岐岖岈岘岙岑岚岜岵岢岽岬岫岱岣峁岷峄峒峤峋峥崂崃崧崦崮崤崞崆崛嵘崾崴崽嵬嵛嵯嵝嵫嵋嵊嵩嵴嶂嶙嶝豳嶷巅彳彷徂徇徉後徕徙徜徨徭徵徼衢彡犭犰犴犷犸狃狁狎狍狒狨狯狩狲狴狷猁狳猃狺狻猗猓猡猊猞猝猕猢猹猥猬猸猱獐獍獗獠獬獯獾舛夥飧夤夂饣饧饨饩饪饫饬饴饷饽馀馄馇馊馍馐馑馓馔馕庀庑庋庖庥庠庹庵庾庳赓廒廑廛廨廪膺忄忉忖忏怃忮怄忡忤忾怅怆忪忭忸怙怵怦怛怏怍怩怫怊怿怡恸恹恻恺恂恪恽悖悚悭悝悃悒悌悛惬悻悱惝惘惆惚悴愠愦愕愣惴愀愎愫慊慵憬憔憧憷懔懵忝隳闩闫闱闳闵闶闼闾阃阄阆阈阊阋阌阍阏阒阕阖阗阙阚丬爿戕氵汔汜汊沣沅沐沔沌汨汩汴汶沆沩泐泔沭泷泸泱泗沲泠泖泺泫泮沱泓泯泾洹洧洌浃浈洇洄洙洎洫浍洮洵洚浏浒浔洳涑浯涞涠浞涓涔浜浠浼浣渚淇淅淞渎涿淠渑淦淝淙渖涫渌涮渫湮湎湫溲湟溆湓湔渲渥湄滟溱溘滠漭滢溥溧溽溻溷滗溴滏溏滂溟潢潆潇漤漕滹漯漶潋潴漪漉漩澉澍澌潸潲潼潺濑濉澧澹澶濂濡濮濞濠濯瀚瀣瀛瀹瀵灏灞宀宄宕宓宥宸甯骞搴寤寮褰寰蹇謇辶迓迕迥迮迤迩迦迳迨逅逄逋逦逑逍逖逡逵逶逭逯遄遑遒遐遨遘遢遛暹遴遽邂邈邃邋彐彗彖彘尻咫屐屙孱屣屦羼弪弩弭艴弼鬻屮妁妃妍妩妪妣妗姊妫妞妤姒妲妯姗妾娅娆姝娈姣姘姹娌娉娲娴娑娣娓婀婧婊婕娼婢婵胬媪媛婷婺媾嫫媲嫒嫔媸嫠嫣嫱嫖嫦嫘嫜嬉嬗嬖嬲嬷孀尕尜孚孥孳孑孓孢驵驷驸驺驿驽骀骁骅骈骊骐骒骓骖骘骛骜骝骟骠骢骣骥骧纟纡纣纥纨纩纭纰纾绀绁绂绉绋绌绐绔绗绛绠绡绨绫绮绯绱绲缍绶绺绻绾缁缂缃缇缈缋缌缏缑缒缗缙缜缛缟缡缢缣缤缥缦缧缪缫缬缭缯缰缱缲缳缵幺畿巛甾邕玎玑玮玢玟珏珂珑玷玳珀珉珈珥珙顼琊珩珧珞玺珲琏琪瑛琦琥琨琰琮琬琛琚瑁瑜瑗瑕瑙瑷瑭瑾璜璎璀璁璇璋璞璨璩璐璧瓒璺韪韫韬杌杓杞杈杩枥枇杪杳枘枧杵枨枞枭枋杷杼柰栉柘栊柩枰栌柙枵柚枳柝栀柃枸柢栎柁柽栲栳桠桡桎桢桄桤梃栝桕桦桁桧桀栾桊桉栩梵梏桴桷梓桫棂楮棼椟椠棹椤棰椋椁楗棣椐楱椹楠楂楝榄楫榀榘楸椴槌榇榈槎榉楦楣楹榛榧榻榫榭槔榱槁槊槟榕槠榍槿樯槭樗樘橥槲橄樾檠橐橛樵檎橹樽樨橘橼檑檐檩檗檫猷獒殁殂殇殄殒殓殍殚殛殡殪轫轭轱轲轳轵轶轸轷轹轺轼轾辁辂辄辇辋辍辎辏辘辚軎戋戗戛戟戢戡戥戤戬臧瓯瓴瓿甏甑甓攴旮旯旰昊昙杲昃昕昀炅曷昝昴昱昶昵耆晟晔晁晏晖晡晗晷暄暌暧暝暾曛曜曦曩贲贳贶贻贽赀赅赆赈赉赇赍赕赙觇觊觋觌觎觏觐觑牮犟牝牦牯牾牿犄犋犍犏犒挈挲掰搿擘耄毪毳毽毵毹氅氇氆氍氕氘氙氚氡氩氤氪氲攵敕敫牍牒牖爰虢刖肟肜肓肼朊肽肱肫肭肴肷胧胨胩胪胛胂胄胙胍胗朐胝胫胱胴胭脍脎胲胼朕脒豚脶脞脬脘脲腈腌腓腴腙腚腱腠腩腼腽腭腧塍媵膈膂膑滕膣膪臌朦臊膻臁膦欤欷欹歃歆歙飑飒飓飕飙飚殳彀毂觳斐齑斓於旆旄旃旌旎旒旖炀炜炖炝炻烀炷炫炱烨烊焐焓焖焯焱煳煜煨煅煲煊煸煺熘熳熵熨熠燠燔燧燹爝爨灬焘煦熹戾戽扃扈扉礻祀祆祉祛祜祓祚祢祗祠祯祧祺禅禊禚禧禳忑忐怼恝恚恧恁恙恣悫愆愍慝憩憝懋懑戆肀聿沓泶淼矶矸砀砉砗砘砑斫砭砜砝砹砺砻砟砼砥砬砣砩硎硭硖硗砦硐硇硌硪碛碓碚碇碜碡碣碲碹碥磔磙磉磬磲礅磴礓礤礞礴龛黹黻黼盱眄眍盹眇眈眚眢眙眭眦眵眸睐睑睇睃睚睨睢睥睿瞍睽瞀瞌瞑瞟瞠瞰瞵瞽町畀畎畋畈畛畲畹疃罘罡罟詈罨罴罱罹羁罾盍盥蠲钅钆钇钋钊钌钍钏钐钔钗钕钚钛钜钣钤钫钪钭钬钯钰钲钴钶钷钸钹钺钼钽钿铄铈铉铊铋铌铍铎铐铑铒铕铖铗铙铘铛铞铟铠铢铤铥铧铨铪铩铫铮铯铳铴铵铷铹铼铽铿锃锂锆锇锉锊锍锎锏锒锓锔锕锖锘锛锝锞锟锢锪锫锩锬锱锲锴锶锷锸锼锾锿镂锵镄镅镆镉镌镎镏镒镓镔镖镗镘镙镛镞镟镝镡镢镤镥镦镧镨镩镪镫镬镯镱镲镳锺矧矬雉秕秭秣秫稆嵇稃稂稞稔稹稷穑黏馥穰皈皎皓皙皤瓞瓠甬鸠鸢鸨鸩鸪鸫鸬鸲鸱鸶鸸鸷鸹鸺鸾鹁鹂鹄鹆鹇鹈鹉鹋鹌鹎鹑鹕鹗鹚鹛鹜鹞鹣鹦鹧鹨鹩鹪鹫鹬鹱鹭鹳疒疔疖疠疝疬疣疳疴疸痄疱疰痃痂痖痍痣痨痦痤痫痧瘃痱痼痿瘐瘀瘅瘌瘗瘊瘥瘘瘕瘙瘛瘼瘢瘠癀瘭瘰瘿瘵癃瘾瘳癍癞癔癜癖癫癯翊竦穸穹窀窆窈窕窦窠窬窨窭窳衤衩衲衽衿袂袢裆袷袼裉裢裎裣裥裱褚裼裨裾裰褡褙褓褛褊褴褫褶襁襦襻疋胥皲皴矜耒耔耖耜耠耢耥耦耧耩耨耱耋耵聃聆聍聒聩聱覃顸颀颃颉颌颍颏颔颚颛颞颟颡颢颥颦虍虔虬虮虿虺虼虻蚨蚍蚋蚬蚝蚧蚣蚪蚓蚩蚶蛄蚵蛎蚰蚺蚱蚯蛉蛏蚴蛩蛱蛲蛭蛳蛐蜓蛞蛴蛟蛘蛑蜃蜇蛸蜈蜊蜍蜉蜣蜻蜞蜥蜮蜚蜾蝈蜴蜱蜩蜷蜿螂蜢蝽蝾蝻蝠蝰蝌蝮螋蝓蝣蝼蝤蝙蝥螓螯螨蟒蟆螈螅螭螗螃螫蟥螬螵螳蟋蟓螽蟑蟀蟊蟛蟪蟠蟮蠖蠓蟾蠊蠛蠡蠹蠼缶罂罄罅舐竺竽笈笃笄笕笊笫笏筇笸笪笙笮笱笠笥笤笳笾笞筘筚筅筵筌筝筠筮筻筢筲筱箐箦箧箸箬箝箨箅箪箜箢箫箴篑篁篌篝篚篥篦篪簌篾篼簏簖簋簟簪簦簸籁籀臾舁舂舄臬衄舡舢舣舭舯舨舫舸舻舳舴舾艄艉艋艏艚艟艨衾袅袈裘裟襞羝羟羧羯羰羲籼敉粑粝粜粞粢粲粼粽糁糇糌糍糈糅糗糨艮暨羿翎翕翥翡翦翩翮翳糸絷綦綮繇纛麸麴赳趄趔趑趱赧赭豇豉酊酐酎酏酤酢酡酰酩酯酽酾酲酴酹醌醅醐醍醑醢醣醪醭醮醯醵醴醺豕鹾趸跫踅蹙蹩趵趿趼趺跄跖跗跚跞跎跏跛跆跬跷跸跣跹跻跤踉跽踔踝踟踬踮踣踯踺蹀踹踵踽踱蹉蹁蹂蹑蹒蹊蹰蹶蹼蹯蹴躅躏躔躐躜躞豸貂貊貅貘貔斛觖觞觚觜觥觫觯訾謦靓雩雳雯霆霁霈霏霎霪霭霰霾龀龃龅龆龇龈龉龊龌黾鼋鼍隹隼隽雎雒瞿雠銎銮鋈錾鍪鏊鎏鐾鑫鱿鲂鲅鲆鲇鲈稣鲋鲎鲐鲑鲒鲔鲕鲚鲛鲞鲟鲠鲡鲢鲣鲥鲦鲧鲨鲩鲫鲭鲮鲰鲱鲲鲳鲴鲵鲶鲷鲺鲻鲼鲽鳄鳅鳆鳇鳊鳋鳌鳍鳎鳏鳐鳓鳔鳕鳗鳘鳙鳜鳝鳟鳢靼鞅鞑鞒鞔鞯鞫鞣鞲鞴骱骰骷鹘骶骺骼髁髀髅髂髋髌髑魅魃魇魉魈魍魑飨餍餮饕饔髟髡髦髯髫髻髭髹鬈鬏鬓鬟鬣麽麾縻麂麇麈麋麒鏖麝麟黛黜黝黠黟黢黩黧黥黪黯鼢鼬鼯鼹鼷鼽鼾齄
posted @ 2015-02-25 11:16 胡满超 阅读(2757) | 评论 (0)编辑 收藏
软件架构设计要关注哪些要点,我一直在思考这个问题?人类有计划的做事必有其强列的目的性,软件开发活动也不例外。

软件不可能由一个人完成,所以软件的设计要分层,分模块,便于人员分工,专业的人做专业的事情。

软件的开发需要传承,铁打的营盘流水的兵,简单的设计是优秀软件的共性,用普通人就能理解的设计原则可以便于理念的传承。
为了传承,文档也很重要。文档是时间流逝中最不容易产生二义性的媒介,好的文档使经验更好传播;
另外文档化的工作之于设计阶段,有利于思考的升华和快速成熟,比如将所懂一门知识写成一本书,仍然需要很多总结和提升的工作。

软件的发布需要测试,靠人工驱动效率太低,那么靠数据驱动的自动化测试能够大大提高测试的效率。

软件的成果需要市场化,遇到问题要进行反馈和解决,日志的设计很重要。当工程师一下子面对几M甚至几十M的数据时,很难快速理出头绪。如果通过查看最后几行,就能明晰程序的动向,那程序的后期质量进步将变得很顺畅。

软件的功能会发展,合理的抽象才能有效的应对变化,当我们可以预料到未来的变化,我们可以通过抽象接口的技术手段提前应对。这样版本在不断演进中,路不会越走越难。

综上所述,好的软件设计需有具备以下特征:

1、分层,分模块
2、简单
3、有文档
4、数据驱动
5、适量日志
6、合理的抽象
posted @ 2014-08-28 22:48 胡满超 阅读(669) | 评论 (0)编辑 收藏
出现这个问题主要是调用的问题,没有加入包

./bin/hadoop jar FirstJar/WordCount.jar WordCount input output

改成如下的样子就可以了

./bin/hadoop jar FirstJar/WordCount.jar cn.edu.ruc.cloudcomputing.book.chapter03.WordCount input output
posted @ 2014-05-27 19:28 胡满超 阅读(7466) | 评论 (0)编辑 收藏
转自:http://www.cppblog.com/changshoumeng/archive/2014/05/09/206871.html

posted @ 2014-05-19 17:06 胡满超 阅读(577) | 评论 (0)编辑 收藏
You can check socket is connect by net.socket._handle like this code:

var obj = new net.socket;            
if (!obj._handle)
{
    obj.connect(8080, '127.0.0.1', function() {
    send;
    });
}
else
{
    send;
}
posted @ 2014-05-13 16:11 胡满超 阅读(523) | 评论 (0)编辑 收藏

转自:http://blog.163.com/javy1225@126/blog/static/459230342009230115919910/


一.CTime转化为CString

CTime  tmSCan = CTime::GetCurrentTime();

CString szTime = tmScan.Format("'%Y-%m-%d %H:%M:%S'");

这样得到的日期时间字符串就是以"2006-11-27 23:30:59"的格式.这是不是很方便呢?

 //取得CTime中的日期
 CString cstrDate = tmScan.Format("%Y-%m-%d");

 //取得CTime中的时间
 CString cstrTime = tmScan.Format("%H:%M-%S");

二.CString转化为CTime的几种方法

CString   timestr   =   "2000年04月05日";   
  int   a,b,c   ;   
  sscanf(timestr.GetBuffer(timestr.GetLength()),"%d年%d月%d日",&a,&b,&c);   
  CTime   time(a,b,c,0,0,0);     


--------or - ---------------------

 CString   s("2001-8-29   19:06:23");   
  int   nYear,   nMonth,   nDate,   nHour,   nMin,   nSec;   
  sscanf(s,   "%d-%d-%d   %d:%d:%d",   &nYear,   &nMonth,   &nDate,   &nHour,   &nMin,   &nSec);   
  CTime   t(nYear,   nMonth,   nDate,   nHour,   nMin,   nSec);

---- or ------------------------
CString   timestr   =   "2000年04月05日";   
  int   year,month,day;   
  BYTE   tt[5];   
  //get   year   
  memset(tt,   0,   sizeof(tt));   
  tt[0]   =   timestr[0];   
  tt[1]   =   timestr[1];   
  tt[2]   =   timestr[2];   
  tt[3]   =   timestr[3];   
  year=   atoi((char   *)tt);   
    
  //get   month   
  memset(tt,   0,   sizeof(tt));   
  tt[0]   =   timestr[6];   
  tt[1]   =   timestr[7];   
  month   =   atoi((char   *)tt);   
    
  //get   day   
  memset(tt,   0,   sizeof(tt));   
  tt[0]   =   timestr[10];   
  tt[1]   =   timestr[11];   
    
  CTime   time(year,month,day,0,0,0);

从上面来看,很明显使用sscanf()函数的优势.

posted @ 2014-05-13 16:05 胡满超 阅读(794) | 评论 (2)编辑 收藏

转自:http://blog.codinglabs.org/artic ... -easy.html#jtss-tqq

周末花时间看了一些比特币原理相关的资料,虽然不敢说把每个细节都完全搞懂了,不过整体思路和关键部分的主要原理还是比较明白。写一篇文章分享给大家。这篇文章的定位会比较科普,尽量用类比的方法将比特币的基本原理讲出来。这篇文章不会涉及算法和协议中比较细节的部分,打算后面会再写一篇程序员视角下的比特币原理,那里会从技术人员的视角对比特币系统中较为关键的数据结构、算法和协议进行一些讲解。

在这篇文章中我会给出一个虚拟的村庄叫“比特村”,整个文章会以讲故事的方式,逐步告诉大家比特币提出的动机、解决了什么问题以及一些关键组件的目标和设计方案。

问题的提出

我们先从比特币产生的动机开始。

以物易物的比特村

话说在这个世界上,有一个叫比特村的小村庄,村庄共有几百户人家。这个村庄几乎与世隔绝,过着自给自足的生活。由于没有大规模贸易,比特村村民一直过着以物易物的生活,也就是说村民之间并没有使用统一的货币,互相间的贸易基本上就是老张家拿一袋面粉换老李家一只羊,王大嫂拿一筐野果换刘大婶两尺布。村民们一直就这么纯朴的生活着。

实物货币

终于有一天,村民觉得一直这样以物易物实在太不方便了,于是村子全员开会,讨论如何解决这个问题。有人提议,以便于分割且稀有的东西,例如黄金,作为一般等价物,把其它物品和黄金的对应关系编成一张表格,例如一克黄金对应一只羊,一克黄金对应一袋面粉等等,此时老张再也不用扛着一袋面粉气喘吁吁的去老李家换羊了,他只要从家里摸出一克金子,就可以去老李家牵回一只羊,而老李拿着这一克黄金可以从任何愿意出让面粉的人那里换回一袋面粉,当然也可以换取任何和一克黄金等值的物品。

此时比特村进入了实物货币时代。

符号货币

好景不长,过了一段时间,实物货币的弊端也出现了。因为比特村附近金矿并不多,开采和冶炼金子太费时费力了。而随着使用,金子总是不断会因为磨损、丢失或有人故意囤积而发生损耗。全村人又一次坐在了一起,开始商讨对策。此时有人说,其实大家也不必一定要真的用黄金啊,随便找张纸,写上“一克黄金”,只要全村人都认同这张纸就等于一克黄金,问题不就解决了。其他人纷纷表示认同,但同时也有了新的问题:真实的黄金是需要开采和冶炼的,金矿有限,开采和冶炼也需要成本,所以没有人可以短期凭空制造大量的黄金,可写字就不同了,只要我纸够笔够,随便像写多少写多少,那这就变成拼谁家里纸多了,搞不好到时一万张纸才能换一只羊(实际上这就发生了经济学上的通货膨胀)。

大家一想也是啊。不过此时又有人提出了解决方案:这个纸不是谁写都有效,我们只认村里德高望重的老村长写得,大家都认识老村长的字。老村长写一些纸,同时按照各家黄金存量发给大家等量的纸,例如老张家有二百克黄金,老村长就发给老张二百张写着“一克黄金”的纸,同时将老张家的黄金拿走作为抵押。就这样,老村长将村里所有黄金收归到自己的家里,并按各家上交的黄金数量发给等值的写有字的纸。此时村民就可以拿着这些纸当黄金进行贸易了,而且大家都认得老村长的字,其他人伪造不出来。另外,如果谁的纸磨损太严重,也可拿到老村长那里兑换新的等值的纸,另外老村长承诺任何人如果想要换成真黄金,只要拿纸回来,老村长就会把等值的黄金还给那人。因为老村长写得纸的黄金量和真实放在家里的黄金量是一样的,所以只要严格按照销毁多少纸新写多少纸的原则,每一张有效的纸总能换回相应的真黄金。

此时,比特村进入了符号货币(纸币)时代。而老村长就承担了政府和银行的角色。

中央系统虚拟货币

又过了几年,老村长由于每天都要核对大量的旧纸币,写新的纸币,还要把各种账目仔细做好记录。一来二去,老村长操劳过度不幸驾鹤西去了。

比特村再次召开全体大会,讨论应该怎么办。此时老村长的儿子二狗子自告奋勇接过了父亲的笔,承担起货币发行的责任。这个年轻的村长二狗子很聪明,他做了几天,发现好像也不用真的写那么多纸。完全可以这样:村民把纸币都交上来,销毁,但是二狗子会记录下每户上交的纸币数量。以后如果要进行付钱,例如老张要拿一克金子向老李换一只羊,就一起给二狗子打个电话,说明要将老张名下的一克金子划归老李名下,二狗子拿出账本,看看老张名下是否有一克金子,如果有就在老张的名下减掉一克,在老李的名下加上一克,这样就完成了支付,此时老李在电话中听到二狗子确认转账完成,就可以放心让老张把羊牵走了。

此时比特村进入了中央系统虚拟货币时代。每个村民都不需要用实物支付,支付过程变成了二狗子那边维护的账本上数字的变更。

分布式虚拟货币

这新上任的二狗子是聪明,不过这人有时候是聪明反被聪明误。有一天二狗子盯着这账本,心想这全村各户谁有多少钱就是我说的算,那我岂不是……。于是他头脑一热,私自从老张帐下划了十克金子到自己名下。

本以为天衣无缝,但没想到老张也有记账的习惯,有一天他正要付钱却被二狗子告知账户没钱了。老张核对了一下自己的账本,明明还有十克啊,于是拿着账本去找二狗子理论,这一核对发现了那笔未经老张同意的转账。

东窗事发!比特村炸开锅了。二狗子被弹劾是不可避免了,不过通过这件事,大家发现了账本集中在一个人手里的弊端:

  • 这个体系完全依赖于账本持有人的个人信用,如果这个人不守规矩,随意篡改账本,那么整个货币系统就会崩溃
  • 如果这个人家里失火或者账本失窃,同样也会为整个体系带来毁灭性的打击

正当人们不知所措时,村里一个叫中本聪的宅男科学家走上了台,告诉大家他已经设计了一套不依赖任何中央处理人的叫比特币的虚拟货币系统,可以解决上述问题。然后他缓缓讲述了自己的方案。

下面我们就来看看中本聪同学是如何设计这套系统的。

基础设施搭建

账簿公开机制

中本聪首先说明,要对现有账簿进行如下改造:

  1. 账簿上不再记载每户村民的余额,而只记载每一笔交易。即记载每一笔交易的付款人、收款人和付款金额。只要账簿的初始状态确定,每一笔交易记录可靠并有时序,当前每个人持有多少钱是可以推算出来的。
  2. 账簿由私有改为公开,只要任何村民需要,都可以获得当前完整的账簿,账簿上记录了从账簿创建开始到当前所有的交易记录。

此言一出,下面立刻炸锅了。第一条还无所谓,但是第二条简直无法接受,因为账簿可是记录了所有村民的交易,这样大家的隐私不全暴露了吗。

中本聪倒是不慌不忙,拿出了一对奇怪的东西。

身份与签名机制(公钥加密系统)

中本聪说,大家不要慌。在他的这套机制下,任何人都不使用真实身份交易,而是使用一个唯一的代号交易。

他展示了手里神奇的东西,说这两件东西分别叫保密印章和印章扫描器。后面他会给村里每一户发一个保密印章和一个印章扫描器。两者的作用如下:

  • 保密印章可以在纸上盖一个章,每个印章盖出的章都隐含了一个全村唯一的一串字符,但是凭肉眼是看不出来的。也无法通过观察来制造出相应的印章。
  • 印章扫描器可以扫描某个已经盖好的章,读出隐含的信息,并在液晶屏上显示出一串字符。

有了这两个神奇的东西,大家就可以在不暴露真实身份的情况下进行交易了,而印章隐含的那一串字符就是这户人家的代号。具体如何巧妙利用保密印章和印章扫描器进行交易,会在下文详述。

成立虚拟矿工组织(挖矿群体)

下一步,中本聪面向全村招募虚拟矿工,招募要求如下:

  • 矿工以组为单位,一组可以是单独的一户,也可以是几户联合为一组
  • 成为矿工不影响正常使用货币
  • 矿工每天要花费一定时间从事比特币“挖矿”活动,但是不同于挖金矿,虚拟矿工不需要拿着工具去野外作业,在家里就可以完成工作
  • 矿工有一定可能性获得报酬,在挖矿活动中付出的努力越多,获得报酬的可能性越大
  • 矿工可以随时退出,也可以随时有新的矿工加进来

很快,大约有五分之一的村民加入比特币矿工组织,共分成了7个组。

建立初始账簿(创世块)

下面,中本聪宣布,先根据二狗子手里的账簿,把抵押的所有黄金按账簿记录的余额退还给每位村民,然后彻底销毁这本账簿。

然后,中本聪拿出一本新账簿,在账簿的第一页上记录了一些交易记录,特别的是,这些记录的付款人一栏全都是“系统”,而收款人分别是每个印章对应的隐含字符,代表初始时刻,系统为每一户默认分配了一定数量比特币,但是数量非常少,都只有几枚,甚至有些不幸的村户没有获得比特币。

接着中本聪说,由于目前市面上比特币非常少,大家可以先回到用黄金做货币的时代,由于我不是村长,我也没有权利强迫大家一定要承认比特币,大家可以自行决定要不要接受比特币。不过随着比特币的流动和矿工的活动,比特币会慢慢多起来。

支付与交易

做了这么多铺垫,终于说到重点了,下面说一下在这样一个体系下如何完成支付。以老张付给老李10个比特币为例。

付款人签署交易单

为了支付10个比特币,老张首先要询问老李的标识字符串,例如是“ABCDEFG”,同时老张也有一个标识字符串例如是“HIJKLMN”,然后老张写一张单子,内容为“HILKLMN支付10比特币给ABCDEFG”,然后用自己的保密印章改一个章,将这张单子交给老李。另外为了便于追溯这笔钱的来源,还要在单子里注明这笔钱的来源记在哪一页,例如这个单子里,老张的10比特币来自建立账簿时系统的赠送,记录在账簿第一页。

收款人确认单据签署人

老李拿到这个单子后,需要确认这个单子确实是来自“HIJKLMN”这个人(也就是老张)签署的,这个并不困难。因为单子上必须有保密章,老李拿出印章扫描器,扫一下章,如果液晶屏显示出的字符和付款人字符是一致的(这里是“HIJKLMN”),就可以确认单子确实是付款人签署的。这是因为根据保密印章的机制,没有其他人可以伪造印章,任何一个人只要扫描一下印章,都可以确认单子的付款人和盖章人是否一致。

收款人确认付款人余额

这个系统到目前还是很有问题。通过保密印章,收款人虽然可以确认付款人确实签署了这份单子,但是无法自行确认付款人是否有足够的余额支付。之前的中央虚拟货币系统中,二狗子负责检查付款人的余额,并通知收款人交易是否有效,现在把二狗子开了,谁来负责记账和确认每笔交易的有效性呢?

之前说过,中本聪设计的这个系统是分布式货币系统,不依赖任何中央人物,所以不会有一个或少数几个人负责这件事,最终承担这份工作的是之前所提到的矿工组织。老张、老李和全村其他任何使用比特币进行交易的村民都依赖矿工组织的工作才能完成交易。

矿工的工作

矿工的工作是整个系统的核心,也是最复杂性最高的地方。下面逐步介绍矿工的工作内容和目的。

矿工的工具

俗话说,工欲善其事,必先利其器。比特币矿工虽然不用铁撅、铁锨和探照灯等工具,不过也要有一些必备的东西。

初始账簿。每个组首先自己复制一份初始账簿,初始账簿只有一页,记录了系统的第一次赠送

空账簿纸。每个小组有若干账簿纸,每一页纸上仅有账簿结构,没有填内容,具体内容的书写规则后面讲述。下面是一张空账簿纸的样子,各个字段的意义后面会说到

编码生成器(哈希函数)。中本聪又向矿工组织的每个组分发了若干编码生成器,这个东西很神奇,将一页账簿填好内容的账簿纸放入这个机器,机器会在账簿纸的“本账单编号”一栏自动打印一串由“0”和“1”组成的编号,共256个。最神奇的是,编号生成器有如下功能:

  • 生成的编号仅与账簿纸上填入的内容有关,与填写人、字体、填写时间等因素均无关
  • 内容相同的账簿纸生成的编号总是相同,但是如果内容哪怕只改一个字符,编号就会面目全非
  • 编码生成器在打印编码时还需要将所有填入账簿纸的交易单放入,机器会扫描交易单和填入交易单的一致性,尤其是保密印章,如果发现保密印章和付款人不一致,会拒绝打印编码
  • 将一张已打印的账簿纸放入,机器会判定编号是否是有效的机器打印,并且判定编号和内容是否一致,这个编号无法伪造
  • 交易单收件箱。每个矿工小组需要在门口挂一个箱子用于收集交易单。
  • 公告板。每个矿工小组同样需要一个公告板公示一些信息。

有了上面的工具,矿工组织就可以开工了!

收集交易单

中本聪规定,每笔交易的发起人,不但要将交易单给到收款人,还要同时复制若干份一模一样的交易单投递到每个矿工小组的收件箱里。

矿工小组的人定期到自己的收件箱里把收集到的交易单一并取出来。

填写账簿

此时小组的人拿出一张空的账簿纸,把这些交易填写到“交易清单”一栏,同时找到当前账簿最后一页,将最后一页的编号抄写到“上一张账单编号一栏”。注意还有个“幸运数字”,可以随便填上一个数字,如12345。然后,将这样账簿纸放入编号生成器,打印好编号,一张账簿就算完成了。

如果你以为矿工的工作就这么简单,那就大错特错了,中本聪有个变态的规定:只有编号的前10个数均为0,这页账簿纸才算有效。

根据之前对编号生成器的描述,要修改编号,只能修改账簿纸的内容,而“交易清单”和“上一张账簿纸编号”是不能随便改的,那么只能改幸运数字了。于是为了生成有效的账簿纸,小组里的矿工就不断抄写账簿纸,但每张纸的幸运数字都不同,然后不断的重复将纸放入编码器,如果生成的编号不符合规定,这张纸就算废了,重复这个过程直到生成一串有效的编号。

我们知道,如果编号的每一个数字都是随机的,那么平均写1000多张幸运数字不同的纸才能获得一个有效的编号。

这就奇怪了,这些矿工为什么要拼命干这看似无意义的事情呢?还记得之前说过矿工有报酬吧,这就是矿工的动力了。中本聪规定:每一张账簿纸的交易清单第一条交易为“系统给这个小组支付50个比特币”。也就是说,如果你生成了一张有意义的账簿纸,并且被所有挖矿小组接受了,那么就意味着这条交易也被接受了,你的挖矿小组获得了50个比特币。

这就是矿工被叫做矿工的原因,也是为什么之前说随着交易和矿工的活动,比特币的数量会不断增多。例如下面是一个挖矿过程,这个小组的公共比特币帐号为“UVWXYZ”。

在幸运数字尝试到“533”时,系统生成了一页有效账簿。

确认账簿

当某挖矿小组幸运的生成了一张有意义的账簿,为了得到奖励,必须立刻请其它小组确认自己的工作。前面说过,当前村里有7个挖矿组,所以这个小组必须将有效账簿纸誊抄6份快马加鞭送到其他6个小组请求确认。

中本聪规定,当某个小组接到其他小组送来的账簿纸时,必须立即停下手里的挖矿工作进行账簿确认。

需要确认的信息有三个:

  1. 账簿的编号有效
  2. 账簿的前一页账簿有效
  3. 交易清单有效

首先看第一个,这个确认比较简单。只要将送来的账簿纸放入编码生成器进行验证,如果验证通过,则编号有效。

第二部分需要将账簿页上的“上一页账簿纸编号”和这个小组目前保存的有效账簿最后一页编号比对,如果相同则确认,如果不同,需要顺着已有账簿向前比对,直到找到这个编号的页。如果没有找到指定的“上一页账簿纸编号”对应的页,这个小组会将此页丢掉。不予确认。

注意,由上面的机制可以保证,如果各个小组手里的账簿纸是相同的,那么他们都能按同样的顺序装订成相同的账簿。因为后面一张纸的编号总是依赖前面的纸的编号,编码生成器的机制保证了所有合法账簿纸的相对先后顺序在每个小组那里都是相同的(可能会有分支,但不会出现环,后面细讲)。

最后是如何确认交易清单有效,其实也就是要确认当前每笔交易的付款人有足够的余额支付这笔钱。由于交易信息里包含这笔钱是如何来的,还包含了记录来源交易的账单编号。例如,HIJKLMN要给ABCDEFG10个比特币,并注明了这10个比特币来自之前OPQRST支付给HIJKLMN的一笔交易,确认时首先要确认之前这笔交易是否存在,同时还要检查HIJKLMN在这之前没有将这10个比特币支付给别人。这一切确认后,这笔交易有效性就被确认了。

其中第一笔是系统奖励给生成这页账簿的小组的50个,这笔交易大家都默认承认,后面的只要按照上述方法追溯,就可以确认HIJKLMN是否当前真有10个比特币支付给ABCDEFG。

如果完成了所有了上述验证并全部通过,这个小组就认可了上述账簿纸有效,然后将这张账簿纸并入小组的主账簿,舍弃目前正在进行的工作,后面的挖矿工作会基于这本更新后的主账本进行。

账簿确认反馈

对于挖矿小组来说,当账簿纸送出去后,如果后面有收到其他小组送来的账簿纸,其“上一页账簿纸编号”为自己之前送出去的账簿纸,那么就表示他们的工作成功被其他小组认可了,因为已经有小组基于他们的账簿纸继续工作了。此时,可以粗略的说可以认为已经得到了50个比特币。

另外,任何一个小组当新生成有效账簿纸或确认了别的小组的账簿纸时,就将最新被这个小组承认的交易写到公告牌上,那么收款人只要发现相关交易被各个小组认可了,基本就可以认为这笔钱已经到了自己的账上,后面他就可以在付款时将钱的来源指向这笔交易了。

以上就是整个比特币的支付体系。下面我们来分析一下,这个体系为什么可以工作下去,以及这个体系可能面临的风险。

工作机制分析

虽然上面阐述了比特币的基本运作规则,但是村民们还是有不少疑问。所以中本聪同学专门开了个答疑会,解答常见问题。下面总结一下村民最集中关心的问题。

核心问题答疑

如果同时收到两份合法的账簿页怎么办?

注意在上面的运行机制中,各个挖矿小组是并行工作的,因此完全可能出现这样的情况:某小组收到两份不一样的账簿页,它们都基于当前这个小组的主账簿的最后一页,并且内容也都完全合法,怎么办?

关于这个问题,中本聪同学说,小组不应该以线性方式组织账簿,而应该以树状组织账簿,任何时刻,都以当前最长分支作为主账簿,但是保留其它分支。举个例子,某小组同时收到A、B两份账簿页,经核算都是合法的,此时小组应该将两页以分叉的形式组织起来,如下图所示:

黑色表示当前账簿主干。此时,可以随便选择一个页作为当前主分支,例如选择A:

此时如果有一个新的账簿页是基于A的,那么这个主干就延续下去:

如果这个主干一直这么延续下去,表示大家基本都以A为主干,B就会被遗忘。但是也有可能忽然B变成更长了:

那么我们就需要将B分支作为当前主干,基于这个分支进行后续工作。

从局部来看,虽然在某一时刻各个小组的账簿主干可能存在不一致,但大方向是一致的,那些偶尔由于不同步产生的小分支,会很快被淹没在历史中。

如果挖矿小组有人伪造账簿怎么办

关于这个问题,中本聪同学说,只要挖矿组织中大多数人是诚实的,这个系统就可靠,具体分几个方面给予答复。

首先,基于保密印章机制,没有人能伪造他人身份进行付款,因为编码生成器在打印编码时会核对所有交易单的保密印章,印章和付款人不一致会拒绝打印。

而且诚实的矿工也不会承认不合法的交易(如某笔交易付款方余额不够)。

所以只有一种可能的攻击行为,即在收款人确认收款后,从另一条分支上建立另外的交易单,取消之前的付款,而将同一笔钱再次付款给另一个人(即所谓的double-spending问题)。下面同样用一个例子说明这个问题。

先假设有一个攻击者拥有10个比特币,他准备将这笔钱同时支付给两名受害者A和B,并都得到承认。

第一步,攻击者准备从受害者A手里买10比特币的黄金,他签署交易单给受害者A,转10个比特币给受害者A。

第二步,这笔交易在最新的账簿页中被确认,并被各个挖矿小组公告出来。受害人A看到公告,确认比特币到账,给了攻击者10个比特币等值的黄金。

第三步,攻击者找到账簿,从包含刚才交易的账簿页的前一页做出一个分支,生成更多的账单页,超过刚才的分支。由于此时刚才攻击者制造的分支变成了主干分支,而包含受害者A得到钱的分支变成了旁支,因此挖矿组织不再承认刚才的转账,受害者A得到的10比特币被取消了。

第四步,攻击者可以再次签署交易单,将同一笔钱支付给受害者B。受害者B确认钱到账后,支付给攻击者等值黄金。

至此,攻击者将10个比特币花了两次,从两名受害者那里各购得等值黄金。攻击者还可以如法炮制,取消与受害者B的转账,将同一笔钱再支付给其他人……

关于这种攻击,中本聪给出的解决方案是,建议收款人不要在公告挂出时立即确认交易完成,而是应该再看一段时间,等待各个挖矿小组再挂出6张确认账簿,并且之前的账簿没有被取消,才确认钱已到账。

中本聪解释道,之前设定变态的编号规则,正是为了防御这一点。根据前面所述,生成有效账簿页不是那么简单的,要花费大量的人力反复试不同的幸运数字,而且过程完全是碰运气。如果某账簿页包含你收到钱的确认,并且在后面又延续了6个,那么攻击者想要在落后6页的情况下从另一个分支赶超当前主分支是非常困难的,除非攻击者拥有非常多的人力,超过其他所有诚实矿工的人力之和。

而且,如果攻击者有如此多人力,与其花这么大力气搞这种攻击,还不如做良民挖矿来的收益大。这就从动机上杜绝了攻击的形成。

比特币会一直增加下去,岂不是会严重通货膨胀

中本聪说,这一点我也想到了。前面忘了说了,我给矿工组织的操作细则手册会说明,刚开始我们协议每生成一页账簿,奖励小组50个比特币,后面,每当账簿增加21,000页,奖励就减半,例如当达到210,000页后,每生成一页账簿奖励25个比特币,420,000页后,每生成一页奖励12.5个,依次类推,等账簿达到6,930,000页后,新生成账簿页就没有奖励了。此时比特币全量约为21,000,000个,这就是比特币的总量,所以不会无限增加下去。

没有奖励后,就没人做矿工了,岂不是没人帮忙确认交易了

到时,矿工的收益会由挖矿所得变为收取手续费。例如,你在转账时可以指定其中1%作为手续费支付给生成账簿页的小组,各个小组会挑选手续费高的交易单优先确认。

矿工如果越来越多,比特币生成速度会变快吗

不会。中本聪解释,虽然可以任意加入和退出矿工组织,导致矿工人数变化,每个矿工也会拿到一个编码生成器,不过我已经在编码生成器中加入了调控机制,当前工作的编码生成器越多,每个机器的效率就越低,保证新账簿页生成速率不变。

虽然每个人的代号是匿名的,但如果泄露了某个人的代号,账簿又是公开的,岂不是他的所有账目都查出来了

确实是这样的。例如你要和某人交易,必然要要到他的代号才能填写交易单。因为收款人一栏要填入那人的代号。不过中本聪说可以提供无限制的保密印章,建议每一次交易用不同的保密印章,这样查账簿就追查不到同一个人的所有账目了。

答疑完毕。

说明

本文用通俗比喻的方式讲解了比特币的运行机制。有几点需要说明:

  1. 为了便于理解,我做了很多简化,因此有些机制细节和实际的比特币可能不完全相同。但总体思想和关键原理是一致的。
  2. 由于很多计算机世界的东西(如公钥体系、网络传输)在现实世界中并没有特别好的对等物,所以故事里难免有一些生硬和不合常理的细节。
  3. 本文描述的是比特币网络本身的技术原理和运作机制,当在如Mtgox这种买卖市场中进行比特币交易时,市场做了中间代理,并不遵从上述机制
参考
  1. Bitcoin: A Peer-to-Peer Electronic Cash System
  2. https://bitcoin.it
  3. 云风的BLOG: Bitcoin 的基本原理
  4. 易懂的比特币工作机理详解
posted @ 2014-02-13 10:36 胡满超 阅读(485) | 评论 (0)编辑 收藏
搜索引擎在查找时主要考虑两方面因素:网页和查询的相关性、网页的重要性
链接分析解决网页重要性的问题
网页中最重要的三个要素,出链(Out Link),入链(In Links),锚文字
链接分析算法
1、随机游走模型:对直接跳转和远程跳转两种用户浏览行为进行抽象的概念模型,用户从当前网页到达某网页的概率
2、子集传播模型:把网页划分为若干子集,给予子集内网页初始权值,根据链接关系,按照一定方式将权值传递到其他网页
不同子集传播模型在如下方面存在差异:
1)如何定义特殊子集合
2)在确定了特殊子集合所具有的性质后,如果对子集内的网页赋初始
3)从特殊子集合将其分值传播到其他网页时,采取何种传播方式
PageRank算法
除了考虑到入链数量的影响,还参考了网页质量因素
数量假设:在Web图模型中,如果一个页面节点接收到的其他网页指向的入链数量越多,那么这个页面越重要
质量假设:质量高的页面会通过链接向其他页面传递更多的权重
算法开始赋予每个网页相同的重要性得分,通过迭代递归计算来更新每个页面节点的PageRank得分,直到稳定为止
远程跳转:解决链接陷阱的通用方式,在网页向外传递分值时,不限于向出链所指网页传递,也可以以一定的概率向任意其他网页跳转(虚拟边,权值通过虚拟边向外传递)
HITS(Hypertext Induced Topic Selection)算法

Authority页面:某个领域或者某个话题相关的高质量网页
Hub页面:指向很多Authority页面
基本假设1:一个好的Authority页面会被很多好的Hub页面指向
基本假设2:一个好的Hub页面会向向很好的Authority页面
算法步骤:
1、将查询提交给某个现有的搜索引擎,或检索系统,提取排名靠前的结果(根集)
2、在根集的基础上,对其扩充(凡是与根集内网页有直接链接指向关系的网页都被扩充进来)
3、在根集+扩充网页,寻找好的Hub页面与好的Authority页面
4、初始情况下,在没有更多可利用信息前,把所有页面两个权值都设置为1
5、以相互增强的关系等原则进行多轮迭代计算,每轮迭代计算更新每个页面的两个权值,直到权值稳定为止
HITS算法不仅在搜索引擎领域应用,在自然语言处理,社交分析也有较好的效果
HITS算法的不足:计算效率较低、主题漂移,易被作弊者操纵结果,结果不稳定(添加删除个别网页或者改变少数链接关系,对排名影响会很大)
HITS算法与PageRank算法比较
1、HITS与用户输入查询相关,PageRank与查询无关
2、HITS计算效率低,PageRank离线计算,在线直接使用计算结果,计算效率高
3、HITS为局部计算,适合在客户端,PageRank为全局计算,适合步骤在服务器端
4、HITS适合处理具体用户查询,PageRank处理适合处理宽泛的用户查询
5、HITS算法在计算时,为每个页面计算两个分值,PageRank只需计算一个分值,在搜索引擎领域,更重要Authority权值,其他应用领域Hub分值也很重要
6、从反作弊角度说,PageRank从机制上优于HITS
7、PageRank比HITS计算过程更稳定,原因是PageRank计算时的远程跳转

SALSA算法
很多实验数据表明,SALSA是目前最好的链接分析算法之一
计算流程分两个阶段:
1、确定计算对象集合,与HITS类似
1)扩展网页集合,在收到用户查询后,利用现有搜索引擎或检索系统获取根集,并扩展
2)转换为无向二分图,一个子集合Hub集合,Authority集合
2、链接关系传播过程,在这一阶段采纳了随机游走模型
在权值传播过程中,权值是被所有链接平均分配的
HITS模型关注的是Hub和Authority之间的节点相互增强关系
SALSA实际上关注的是Hub-Hub及Authority-Authority之间的节点关系
Authority集合内从某个节点i转移到另一个节点j的概率,i与j之间概率是不同的,非对称
在二分图中,对于Authority集合内的某个节点来说,一定可以通过Hub子集合的节点中转后再次返回本身
建立好Authority节点关系图后,即可利用随机游走模型来计算每个节点的Authority权值
SALSA将搜索结合排序问题进一步转换为求Authority节点矩阵的主秩问题,无需迭代,计算速度快
决定Authority权值的4个因子
1)Authority子集合中包含的节点总数
2)网页i所在连通图中的节点个数
3)网页i所在连通图中包含的入链总数
4)网页i的入链个数
SALSA算法的特点
1、SALSA算法无需像HITS算法一样迭代计算,计算速度快
2、解决了HITS主题漂移的问题,搜索质量优于HITS
主题敏感PageRank
该算法被Google使用在个性化搜索服务中,非常适合作为个性化搜索的技术方案
用户会对某些领域感兴趣,同时当浏览某个页面时,这个页面也是与某个主题相关,跳转时,更倾向于点击和当前页面主题类似的链接
主题敏感PageRank是将用户兴趣,页面主题及链接所指向网页与当前网页主题的相似程度综合考虑而建立模型
该算法引入16种主题类型,对于某个网页来说,对应某个主题类型都有相应的PageRank分值
主题敏感的PageRank与主题相关,在接收到用户查询后,主题敏感PageRank还需要利用分类器,计算该查询隶属于事先定义好的16个主题的相似度,并在排序时利用此相似度信息
计算流程:
1、离线的分类主题PageRank数值计算,计算网页对于16个分类的相似度
     将网页划分为两个集合,一个ODP对应分类主题对应的所有网页S,剩下的网页为另一个集合T
     通过链接关系,从S向T传递权重,即计算网页所属类别的概率
2、在线利用算好的PageRank分值,来评估网页和用户查询的相似度
     通过计算查询词所属类别的概率*网页所属类别的概率,得出两者相关性的分值,进行排序
HillTop算法
1、从海量的互联网网页中通过一定的规则选出专家页面子集合,并单独为其建立索引
2、接收用户发出的查询请求时,根据用户查询的主题,从专家页面子集合中找出部分相关性最强的专家页面,对每个专家页面计算相关性得分
3、根据目标页面(从索引系统中中取到的页面)和这些专家页面的链接关系 对目标页面进行排序
4、整合相关专家页面和得分较高的目标页面作为搜索结果,返回给用户
从属组织页面:主机IP地址的前3个网段相同,网站域名中的主域名相同
专家页面
1、与某个主题相关的高质量页面
2、这些页面的链接所指向的页面相互之间是非从属组织页面
3、这些被指向的页面大多数是与专家页面主题相近
HillTop可以与某个排序算法相结合,不适合作为一个独立的网页排序算法来使用,因为当无法得到一个足够大的专家页面时,会返回空结果。
步骤1:专家页面搜索
从1亿4千万网页中,筛选出250万作为专家页面,专家页面特征:
1、页面中至少包含K个出链,K可以人为指定
2、K个出链指向的所有页面相互之间的关系,都符合非从属组织页面
对专家页面单独建索引,且只对关键字段(Key Phrase)进行索引,关键字段包含3类信息:网页标题,H1标签内文字和URL锚文字
关键字段有影响范围(可以支配Qualify的链接),依次为,标题->H1标签->URL锚文字
在计算网页排序时,对查询字段在不同的关键字段中,会使用不同的权值
系统接收到用户查询Q,将对专家页面进行打分,主要考虑以下3类信息:
1、关键字段包含了多少词
2、关键片段本身的类型,即关键字段的类型
3、用户查询和关键词的失配率,即关键字段中不属于查询的单词个数占关键片段总单词个数的比率
步骤2:目标页面排序
Hilltop算法包含的基本假设:一个目标页面如果是满足用户查询的高质量搜索结果,其充分必要条件是该目标页面有高质量专家页面链接指向
为保证上述假设的成立,Hilltop算法在这个阶段需要对专家页面的出链仔细进行甄别,以保证查询时,选出那些和查询密切相关的目标页面。
在进行传递分值之前,首先需要对链接关系进行整理,能够获得专家页面分值的目标页面需要满足以下两点要求:
条件1、至少需要两个专家页面有链接指向目标页面,且两个专家页面不能是从属组织页面
能够获得传递分值的目标页面一定有多个专家页面链接指向,目标页面所获得的总传播分值是每个有链接指向的专家页面所传递的分值之和
条件2、专家页面和所指向的目标页面不能是从属组织页面
目标页面权值计算步骤
1、找到专家页面中那些能够支配页面的关键片段集合S
2、统计S中包含用户查询词的关键片段个数T,T越大权值越大
3、专家页面给目标页面传递分值:E*T,E为专家页面本身在第一阶段计算得到的相关得分,T为b步骤计算分值
对于包含多个查询词的用户请求,则每个查询词单独计算,将多个查询词的传递分值累加
Hilltop算法存在与HITS算法类似的计算效率问题,随着专家页面集合的增大
其他改进算法
1、智能游走模型(Intelligent Surfer Model)
判断网页包含的链接所指向的网页内容和用户查询的相关性,以此来改善链接分析效果
2、偏置游走模型(Biased Sufer Model)
智能游走模型考虑的是网页内容和用户查询的相关性,而偏游走模型考虑的是链接指向的网页内容和当前浏览网页内容之间的相似性
3、PHITS算法(Probability Analogy of HITS)
PHITS是对HITS算法的直接改进。PHITS算法认为不同链接其传递权值的能力应该是不同的,PHITS需要计算两个页面S和T之间链接的连接强度
链接的强度依据页面S和T之间相似度确定
4、BFS算法(Backward Forward Step)
对SALSA算法的扩展,对HITS算法的限制
解除了SALSA算法只允许直接相邻网页才能有影响的限制,只要网页S和T可通达,即可对网页T施加影响,如果网页S距离网页T距离越远,那么网页S的影响就随着距离增大而呈现衰减
posted @ 2013-11-12 14:06 胡满超 阅读(594) | 评论 (0)编辑 收藏
检索模型与搜索排序
最重要的两个因素,用户查询与网页相关性,网页链接情况
检索模型:用户查询与网页相关性
布尔模型,向量空间模型,概率模型,语言模型,机器学习排序算法

布尔模型:数据基础是集合论,搜索结果过于粗糙,无法量化搜索词与文档之前的相关性

向量空间模型:把文档看做是由T维特征组成的一个向量,最常用的是以单词作为特征,实际应用中,文档的维度相当高(成千上万)
将查询和文档之间的内容相似性作为相关性的替代
计算相似性,使用COSINE,计算查询词特征权值与文档中每个特征权值向量的点积
特征权重:由词频Tf,逆文档频率IDF确定
词频TfWtf=a+(1-a)*Tf/Max(Tf)
a取0.4效果较好
逆文档频率因子:文档集合范围的一种全局因子,特征单词之间的相对重要性
有研究者进一步分析认为:IDF代表了单词带有的信息量的多少(熵),其值越高,说明其信息含量越多,越有价值
IDFk=log(N/nk)
N代表文档集合中总共有多少个文档,nk代表特征单词k在其中多少个文档中出现过
Weight_word=Tf*IDF,特征权值越大,越可能是好的指示词
查询词在某个文档中的词频越高,在其他文档中出现的词频越低,这个词的权值越高
向量空间模型是经验型的模型,靠直觉和经验不断摸索完善,缺乏明确的理论指导改进方向
概率排序原理:给定一个用户查询,如果搜索系统能够在搜索结果排序时按照文档和用户需求的相关性由高到低排序,那么这个搜索系统的准确性是最优的。
将P(D|R)/P(D|NR)大小进行降序排列,得到搜索相关性排序

二元独立模型

二元假设:一遍文档在由特征进行表示的时候,以特征“出现”和“不出现”两种情况来表示
词汇独立假:文档中出现任意一个词在文档的分布概率不依赖于其他单词是否出现

BMI模型:基于二元假设推导而出,对于单词特征,只考虑是否在文档中出现过,而了考虑单词的权值
P(D|R)/P(D|NR) = pi(1-si)/si(1-pi)
log( pi(1-si)/si(1-pi) )
pi代表第i个单词在相关文档集合内出现的概率,在二元假设下,可以用包含这个单词的相关文档个数ri除以相关文档总数R来估算,pi=ri/R
si代表第i个词在不相关文档集合内出现的概率,可以用包含这个单词的不相关文档个数ni-ri,除以不相关文档总数(N-R)来估算,si=(ni-ri)/(N-R)
加上平滑处理
log((ri+0.5)/(R-ri+0.5)
/
(ni-ri+0.5)/((N-R)-(ni-ri)+0.5))
其含义:对于同时出现在用户查询Q和文档D中的单词,累加每个单词的估值,其和就是文档D和查询相关性度量值

BM25模型
在BIM模型的基础上,考虑了单词在查询中的权值及单词在文档中的权值,拟合出综合上述考虑因素的公式,并通过引入一些经验参数
BM25模型是目前最成功的内容排序模型
http://hi.csdn.net/attachment/201011/30/0_12911307384w69.gif

k1,k2,K均为经验设置的参数,fi是词项在文档中的频率,qfi是词项在查询中的频率。

K1通常为1.2,通常为0-1000

K的形式较为复杂

K=http://hi.csdn.net/attachment/201011/30/0_1291130766F92C.gif 

上式中,dl表示文档的长度,avdl表示文档的平均长度,b通常取0.75
BM25F模型:是典型的BM25改进算法
将文档内容切换成不同的部分,为不同的部分赋予不同的权重
语言模型方法:借鉴语音识别领域采用的语言模型技术,将语言模型和信息检索相互融合
为每个文档建立一个语言模型,语言模型代表了单词或者单词序列在文档中的分布情况
对于查询中的单词来说,每个单词都对应一个抽取概率,将这些单词的抽取概率相乘就是文档生成查询的总体概率
一般采用数据平滑方式解决数据稀疏问题
用户提交查询Q,文档集合内所有文档都计算生成Q的概率,然后按照生成概率值由大到小排序,就是搜索结果
HMM,隐马尔科夫语言模型、相关模型、翻译模型是在基本语言模型的改进
语言模型检索方法效果略优于精调参数的向量空间模型,与BM25等概率模型效果相当
通过理论推导,可以得出:语言模型检索方法的排序公司符合概率模型的概率排序原理,类似向量空间模型Tf*IDF
机器学习排序
为何兴起较晚:
1、其他模型和方法,考虑的因素较少,人工进行公式拟合完全可行,效果尚可
2、机器学习需要大量训练数据,用户点击记录可以当做机器学习方法训练数据的一个替代品
机器学习排序系统的4个步骤
人工标注训练数据:用户点击记录来模拟人工打分机制
文档特征抽取:查询词在文档中的词频、查询词的IDF信息,网页入链数量,网页出链数量,网页PageRank值,网页URL长度,查询词的Proximity值(文档中多大的窗口内可以出现所有查询词)
学习分类函数
在实际搜索系统中采用机器学习模型
机器学习方法
1、单文档方法
对单独的一篇文档转换为特征向量,机器学习系统根据从训练数据中学习到的分类或回归函数对文档打分,打分结果为最后得分
在训练过程中,当打分大于一定的阈值,为相关文档,否则为不相关文档。
2、文档对方法
通过训练,对文档顺序关系是否合理进行判断,判断两个文档的得分
使用SVM,BOOST,神经网络,都可以做为学习方法
缺点,只考虑了两个文档对的相对先后顺序,却没有考虑文档出现的搜索列表中的位置
不同的查询,相关文档数量差异很大,对机器学习系统的效果造成评价困难
3、文档列表方法
将每个查询对应的所有搜索结果列表作为一个训练实例
通过搜索结果排列组合的概率分布,训练评分函数
搜索质量评价标准:对于搜索引擎更加关注精确率
精确率:本次搜索结果中相关文档所占本次搜索返回的所有文档的比例
招回率:本次搜索结果中相关文档占整个集合中所有相关文档的比例
P@10指标:在搜索结果排名最先前的头10个文档中有多大比例是相关的
MAP:AP兼顾了排在前列的相关性和系统招架率,MAP多组查询的AP平均值
posted @ 2013-11-04 12:56 胡满超 阅读(574) | 评论 (0)编辑 收藏
词典压缩:减小词典的内存占用
好的压缩算法:压缩率,压缩速度,解压速度(最重要)
一元编码
10
210
3110
41110
511110
Elias Gamma:
x=2^e+d
e+1:一元编码
d:二元编码
Elias Delta:
x=2^e+d
e+1:再使用Elias Gamma编码一次
d:二元编码
Golomb & Rice
因子1=(X-1)/b,因子1+1,一元编码
因子2=(X-1) mod b,使用二元编码,编码宽度在log(b)
Golomb: b=0.69*Avg(序列平均值)
Rice:2的整数次幂,所有小于Avg中最接近Avg的数值
变长压缩算法SimpleX
Simple9: 32位比特位,4个比特为管理数据存储区,28个比特压缩数据存储区
Simple9的28位有9种表示形式
Simple16: 28位有16种表示形式,并且通过非当项完全固定长度,解决数据区有浪费位的情况
PForDelta:目前解压速度最快的一种倒排文件压缩算法
1,对待编码的连续K个数值(一般为128),确定10%的大数数值,根据70%小数确定夺取的比特宽度,确定整个序列
2,对原始数据遍历,将大数放置到尾端,并转换成链表结构的序列
3、将所有数字压缩到队列中
文档编号重排序
网页的文档ID+单词词频信息,文档ID使用D-Gap进行编码
将内容越相似的网页,在编排文档号时越相邻
海量数据文本聚类速度较慢,将URL相似的网页聚合在一起,假设同一个网站的很多页面表达的主题内容是近似的
静态索引裁剪:主动抛弃一部分不重要的信息(索引项)来达到数据压缩的效果
以单词为中心的索引裁剪
判断单词与文档的相似性,每个词典中的单词,其对应的倒排排列中至少保留K个索引项,还要保留若干富余项目
实验证明,如果首先对所有索引项的原始得分减去得分最低索引项的得分,再采取(对K个项进行折扣,乘一个折扣因子,得出阈值a,剩下的大于a保留)方法进行裁剪,效果会大大提升
因为
索引项得分分差相关不大,比较集中在某个区间,所以减掉得分最低项
以文档为中心的索引裁剪:更为常用
在建立索引之前进行数据预处理,把与文档主题表达不相关的单词抛弃,如停用词
posted @ 2013-11-04 12:56 胡满超 阅读(816) | 评论 (0)编辑 收藏
单词词典
1、哈希加链表
2、树形结构:B树或者B+树
倒排列表:
单词+文档号,词频,出现的位置
文档号一般采用差值存储,以节省空间
建立索引
1、两遍文档遍历法
第一遍,收集全局统计信息,文档数N,每个文档包含不同单词数M,每个单词在多少个文档中出现过的信息DF,通过这些信息可以计算出最终索引的大小
第二遍,在建立好的内存中建立索引,从磁盘读取文档并解析文档是最消耗时间的步骤
2、排序法
始终在内存中分配固定大小的空间,用来存放词典信息和索引中间结果,当分配空间消耗光的时候,把中间结果写入磁盘,清空内存数据进行下一轮索引
中间结果排序,排序前,文档ID,单词ID,单词频率
排序后,单词ID(主键),文档ID(次键)
合并中间结果,把中间结果文件进行合并,按单词ID写入最终结果文件
3、归并法
在中间结果排序完成以后,把字典信息也写入文档中,这样全额使用内存
在建立中间索引中,实际单词,文档编号,词频
合并时,针对每个单词的倒排列表进行合并,形成最终的词典信息
动态索引
倒排索引:词典在内存里,倒排列表存储在磁盘文件中
临时索引:词典和倒排列表都在内存中,当有新文档加入时,放到临时索引中
删除文档列表:当文档内容被更改时,系统认为旧文档被删除,增加一篇新文档
当用户输入查询时,先从找倒排索引+临时索引,去掉删除文档列表中的文档结果
索引更新策略
1、完全重建策略:当新增文档达到一定数量后,新老索引合并重建,适合小文档集合,主流商业搜索引擎一般也采用此方式来维护
2、再合并策略:当新增文档达到一定数量后,新老索引合并重建,此时老索引还在被使用,由于老索引有序,所以合并策略执行较快,但是读老索引,建新索引,也需要较多IO时间,比较耗时
3、原地更新策略:在建立老索引时,在老索引倒排列表中留有一定的余地,新加入索引直接追加到预留空间,实验数据表明,更新效率比再合并策略低
4、混合策略:将单词根据不同性质进行分类,对其索引采取不同的索引更新策略,长倒排列表单词采取原地更新策略(读写开销大),短倒排列表采取再合并策略(读写开销不算太大

查询处理
1、一次一文档,找到包含关键字的所有文档集合,一次计算一个文档的得分,依次计算所有文档,计算后一般采用优先队列对分数进行排序
2、一次一单词,一次计算一个单词的得分,并把结果以文档编写为关键值,以hash表存储得分,计算所有文档得分后,对hash表进行排序
跳跃指针
在存储倒排索引文档编号时,通常使用跳跃指针节省空间,跳跃指针分块使用根号L为长度效果较好
多字段索引:对网页的不同区域进行字段划分,进行索引
1、多索引方式,对每个不同的字段分别建立索引
2、倒排列表方式,把字段信息存储到倒排列表项中
3、扩展列表方式,把每个字段出现的位置记录到一张列表里,倒排索引找到单词后,判断单词的位置是否在某字段范围中
短语查询:本质上是如何在索引中维护单词顺序关系或位置信息
1、位置信息索引,通过位置信息判断两个词是否为短语关系,适合常规短语
2、双词索引,首词+下词,只对计算代价高的短语建立双词索引,一般短语通过常规手段达到目的
3、短语索引,缺点无法将所有短语都建好索引,从用户查询日志或网页本身挖掘短语,适合热门短语
4、混合方法,用户查询->短语索引->双词索引->常规索引
分布式索引:多台机器协作完成索引
1、按文档划分,每台机器负责对某个文档子集建立索引
2、按单词划分,将单词分别传送给服务器1,计算结果后,再传送给服务器2,一次一单词的查询处理方式
posted @ 2013-09-16 14:01 胡满超 阅读(517) | 评论 (0)编辑 收藏
二、网络抓虫

网页页面划分为5个部分:
1、已下载
2、已过期
3、待下载
4、可知网页集合,未下载,但可索引
5、不可知网页集合,暗网网页
爬虫分三种类型:
1、批量型:有明确的抓取范围和目标,当达到这个目标后停止抓取
2、增量型:不断抓取,抓取到以后定期更新
3、垂直型:抓取特定行业网页
优秀爬虫的特性:高性能、可扩展(良好的并发性)、健壮性、友好性(遵守Robot协议)
评价爬虫质量的标准:覆盖率,时新性,重要性
 
抓取策略:优先选择重要网页进行抓取
1、宽度优先遍历策略,虽然机械,但是效果好,隐含了一些网页优秀级的假设
2、非完全PageRank策略,对已下载网页集合,加上待抓取URL,形成网页集合,进行PageRank计算,将待抓取按得分进行排序
3、OCIP策略,在线页面重要性计算,待下载页面都分配相同的cash,下载后把页面拥有的现金平分给包含的链接,
待抓取URL则根据手头现金排序,优先下载最充裕网页。计算速度快,适合实时计算,效果略优于宽度优先
4、大站优先策略,哪个网站等等下载的页面最多,则优先下载这些链接,效果略优于宽度优先

网页更新策略
1、历史参考策略,过去频繁更新的网页,将来也会频繁更新,利用泊松过程
抓取策略应该忽略掉广告或导航等非重要区域的频繁变化,集中在主题内容的变化探测和建模
2、用户体验策略,对搜索结果排名靠前,更新以后对搜索质量(排名)的影响较大的页面进行更新
3、聚类抽样策略,先对网页进行聚类,对同一类网页采用相同的更新频率
聚类特征:
静态特征,页面的内容,图片数量,页面大小,链接深度,PageRank值
动态特征,随着时间的变化 ,静态特征的变化情况
聚类抽样策略效果好于前述两种,但是对亿计网页进行聚类,难度较大

暗网抓取
将暗网数据从数据库中挖掘出来,百度的“阿拉丁”计划就是解决此问题
查询组合:Google提出富含信息查询模板技术,使用富含信息查询模板进行查询,获取有效的网页结果
富含信息查询模板:对于某固定的查询模板来说,如果给模板内每个属性都赋值,形成不同的查询组合,其返回内容差异较大,则这个查询模板为富含信息查询模板

分布式爬虫
主从分布式:URL服务器容易成为整个系统的瓶颈
对等分布式:没有URL服务器存在,每台抓取服务器的分工成为问题,对网址的主域名进行哈希计算,之后对m服务器数量取模,把计算后的模和抓取服务器号匹配
一致性哈希算法:将网站主域名进行哈希,映射到0~2^32之间某个数值,抓取服务器负责这个环状序列的一个片段的抓取,抓取内容由上一个服务器进行循环转发
posted @ 2013-09-13 11:10 胡满超 阅读(556) | 评论 (0)编辑 收藏
仅列出标题  下一页