??xml version="1.0" encoding="utf-8" standalone="yes"?> Website: [1] http://people.csail.mit.edu/indyk/ QLSH原作者) 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 Cdoe: [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 LSHQ分别位于legacy module和flann module中)
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 }
]]>
]]>
脑图源文件下载地址
参考文献:
[2] Nearest Neighbor Methods in Learning and Vision: Theory and Practice
]]>
https://gith
]]>
我是2005q毕业,从毕业前的实习开始,?/span>CAD二次开发,甉|设计软g?/span>
2006q{做无U办公YӞ那个q代无纸办公行Q?/span>C++更是LQ感觉也有前途?/span>
2008q{?/span>Open Office的开发,l护世界U的产品会生一U自豪感Q?/span>Open Office本n代码体量也的非常大?/span>
2010q{做安全类的品,从一个模块负责人,核心E序员,到架构师Q再到负责整体品线的负责hQ经历了4q时间?/span>
在我的职业生涯中时不时就会生一U莫名的危机感,l常会问自己Q自己掌握的技术够深吗、是L的技术吗、未来的职业发展又在哪里Q?/span>
2006q一个同事蟩槽去了一家大型企业,走的时候跟我们_做二ơ开发没有前途,出去面试会被人看不v。但是我发现Q在具体~码的过E中Q很多经验丰富的E序员甚至不能把一个对话框E序写的很漂亮,一个对话框cȝ实现界面与逻辑混在一P没有太多解耦的思想在里面。后来的工作中悟Z个道理,没有角Ԍ只有演员,只有把现在的事情做好Q才能有未来?/span>
2008q我在一个不满意的环境中Q苦苦的L下一步的方向Q从坐落在小区里的公怸直面试到了微软和IBMq个U别的公叔R。被挫了很多ơ,也积累了很多面试的经验。其间有一家做搜烦引擎的公司我没去成,我的理由只是因ؓ工资没有M提高。其实大家蟩槽的时候都说是Z职业发展Q结果往往是哪里给的条件好去哪里Q而在一般意义上看,高工资与好公怸般都是成正比的。当然偶也有例外,比如q里提到的做搜烦的公司,如果当初?/span>08的时候就选择做搜索引擎,也许后面的故事会很不同?/span>
2010q我拥有了工?/span>5q的工作l验Q我发现一般工作到5q以后才会遇C些真正的好机会。蟩槽去了一家刚刚在创业板上市不久的公司Q做一些安全类的品。从q一d始,׃业务的快速发展和领导的信任,我开始拥有了一些能够独当一面的能力与锻炼机会。除了编写一些从无到有的模块Q我开始关注架构的设计Q团队培养,产品理{一pd更宏观的问题?/span>
回到原来的问题,我们Z么要转型Q原因ȝ如下Q?/span>
1. 大多数的E序员职业v炚w偏低Q很多h甚至只能从外包做P
2. 大多数的E序员做不上L产品Q主技术,所掌握的都是一些较后的技能,靠体力挣钱,而不是靠智力Q?/span>
3. 很多公司不能l员工稳定的成长预期Q过了某一个发展阶D双方很难找到共赢点Q?/span>
4. 世界发展太快Q当我们q在應|之时外面世界已经l历了从互联|,云计,Ud互联|,大数据,人工Q一波又一波的产业升。而我们一波都没赶上?/span>
于是我们要{型?/span>2011q当我看?/span>hadoop权威指南q本书的时候,我感觉大数据一起会行hQ而且大数据未来会在各行各业遍地开花?/span>
可是Q留l学习的旉真的很少Q工作忙,下班要顾家。只好挤旉学习Q在上班的\上,坐公交R、坐地铁Q给孩z衣服,可以带着x听视频,成了唯一的学习方式。听视频虽然不能学到太多技术精髓,但也可以了解不少技术,开阔眼界?/span>
2014q底Q我转型做一些也数据相关的工作,做数据清z,分析Q徏模,ȝ。我ȝ一下{型要做的一些事情以及要学的东西?/span>
1. 要有行动Q只停留在想法层面生不了Q何实质上的进展;
2. 挤时_旉对于每一个认真生zȝ人都很宝贵,挤一下吧Q少玩玩游戏啥的QM有的Q?/span>
3. 要重视学习,其是看书进行系l学习,从网l上看到的只a片语做ؓ了解q行Q但是不ȝl掌握知识,境界很难上到新的台阶Q?/span>
4. 要注视理论学习,上班以后最不缺的是实践Q天天都在实践反而凸昄学习理论的重要性;
5. 把主要学习时间花在那些最通用、最被广泛采用的技术上Q如果每天都在学习那些其他公司所不需要的领域知识Ӟ说明该蟩槽了Q?/span>
6. 要注重基本的数据l构和算法,q些是写好程序的基础Q基军_高度Q做那些能够解决困难问题的hQ而不是做只能执行具体d的h。差别在于能不能把现实的工程问题抽象成数据与法?/span>
7. 选一个好的方向,像高q发Q分布式pȝQ数据库Q大数据工具Q统计徏模,机器学习Q数据挖掘都是即有用又缺人的领域Q搞好Q何一个领域都会有好的发展Q?/span>
8. 我感觉能把数据分析、机器学习、自然语a处理?/span>R语言q些学好Q统计徏模依然是很基知识Q不能蟩跃学习;
9. 学习最重要的是入门与坚持,入门可以学视频教E,_深要靠应用与时间打;
q序员的职业发展来看,我ȝ自己的一些经验:
1. 1~3q_要学_一门语aQ这q不太难Q?/span>
2. 3~5q_应该x软g的设计,设计模式{知?/span>
3. 5~7q_应该能独立完成一个Y件模块,从需求到试的全q程。我发现一般这个阶D会遇到一些获得期权或者股权的ZQ能不能最lŞ成收益看q气吧;
4. 7~10q_争取可以负责更ؓ全面的工?/span>
在这个过E中Q像数据库,操作pȝQƈ发,多线E,目理Q品管理这些知识都需要,掌握的越多越好吧?/span>
开发一个数据品跟一个传lY件品ƈ没有太大的本质差异,很多技能从事哪个行业都是需要的?/span>
一.CTime转化为CString
CTime tmSCan = CTime::GetCurrentTime();
CString szTime = tmScan.Format("'%Y-%m-%d %H:%M:%S'");
q样得到的日期时间字W串是?2006-11-27 23:30:59"的格?q是不是很方便呢?
//取得CTime中的日期
CString cstrDate = tmScan.Format("%Y-%m-%d");
//取得CTime中的旉
CString cstrTime = tmScan.Format("%H:%M-%S");
?CString转化为CTime的几U方?/span>
CString timestr = "2000q?4?5?;
int a,b,c ;
sscanf(timestr.GetBuffer(timestr.GetLength()),"%dq?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 = "2000q?4?5?;
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()函数的优?
在这文章中我会l出一个虚拟的村庄?#8220;比特?#8221;Q整个文章会以讲故事的方式,逐步告诉大家比特币提出的动机、解决了什么问题以及一些关键组件的目标和设计方案?/p>问题的提?/span> 我们先从比特币生的动机开始?/p> 话说在这个世界上Q有一个叫比特村的村庄,村庄共有几百户h家。这个村庄几乎与世隔l,q着自给自的生zR由于没有大规模贸易Q比Ҏ村民一直过着以物易物的生z,也就是说村民之间q没有用统一的货币,互相间的贸易基本上就是老张家拿一袋面_换老李家一只羊Q王大嫂拿一{野果换刘大婶两布。村民们一直就q么U朴的生zȝ?/p> l于有一天,村民觉得一直这样以物易物实在太不方便了Q于是村子全员开会,讨论如何解决q个问题。有人提议,以便于分割且E有的东西Q例如黄金,作ؓ一般等LQ把其它物品和黄金的对应关系~成一张表|例如一克黄金对应一只羊Q一克黄金对应一袋面_等{,此时老张再也不用扛着一袋面_气喘吁吁的去老李家换了Q他只要从家里摸Z克金子,可以去老李家牵回一只羊Q而老李拿着q一克黄金可以从M愿意面粉的h那里换回一袋面_,当然也可以换取Q何和一克黄金等值的物品?/p> 此时比特村进入了实物货币时代?/p> 好景不长Q过了一D|_实物货币的弊端也出现了。因为比Ҏ附近金矿q不多,开采和冶炼金子太费时费力了。而随着使用Q金子L不断会因为磨损、丢失或有h故意囤积而发生损耗。全村h又一ơ坐在了一P开始商讨对{。此时有Q其实大家也不必一定要真的用黄金啊Q随便找张纸Q写?#8220;一克黄?#8221;Q只要全村h都认同这张纸q于一克黄金,问题不就解决了。其他hUL表示认同Q但同时也有了新的问题:真实的黄金是需要开采和冶炼的,金矿有限Q开采和冶炼也需要成本,所以没有h可以短期凭空刉大量的黄金Q可写字׃同了Q只要我U够W够Q随便像写多写多少Q那q就变成D安U多了,搞不好到时一万张U才能换一只羊Q实际上q就发生了经学上的通货膨胀Q?/p> 大家一想也是啊。不q此时又有h提出了解x案:q个U怸是谁写都有效Q我们只认村里d高望重的老村长写得,大家都认识老村长的字。老村长写一些纸Q同时按照各安金存量发l大家等量的U,例如老张家有二百克黄金,老村长就发给老张二百张写着“一克黄?#8221;的纸Q同时将老张家的黄金拿走作ؓ抉|。就q样Q老村长将村里所有黄金收归到自己的家里,q按各家上交的黄金数量发l等值的写有字的U。此时村民就可以拿着q些U当黄金q行贸易了,而且大家都认得老村长的字,其他Z造不出来。另外,如果谁的U磨损太严重Q也可拿到老村镉K里兑换新的等值的U,另外老村长承ZQ何h如果惌换成真黄金,只要拿纸回来Q老村长就会把{值的黄金q给那h。因村长写得纸的黄金量和真实放在家里的黄金量是一LQ所以只要严格按照销毁多纸新写多少U的原则Q每一张有效的U总能换回相应的真黄金?/p> 此时Q比Ҏq入了符可币(U币Q时代。而老村长就承担了政府和银行的角艌Ӏ?/p> 又过了几q_老村长由于每天都要核对大量的旧纸币,写新的纸币,q要把各U̎目仔l做好记录。一来二去,老村长操劌度不qR鹤西M?/p> 比特村再ơ召开全体大会Q讨论应该怎么办。此时老村长的儿子二狗子自告奋勇接q了父亲的笔Q承担v货币发行的责仅R这个年ȝ村长二狗子很聪明Q他做了几天Q发现好像也不用真的写那么多U。完全可以这P村民把纸币都交上来,销毁,但是二狗子会记录下每户上交的U币数量。以后如果要q行付钱Q例如老张要拿一克金子向老李换一只羊Q就一L二狗子打个电话,说明要将老张名下的一克金子划归老李名下Q二狗子拿出账本Q看看老张名下是否有一克金子,如果有就在老张的名下减掉一克,在老李的名下加上一克,q样完成了支付Q此时老李在电话中听到二狗子确认{账完成,可以放心让老张把羊牵走了?/p> 此时比特村进入了中央pȝ虚拟货币时代。每个村民都不需要用实物支付Q支付过E变成了二狗子那边维护的账本上数字的变更?/p> q新上Q的二狗子是聪明,不过qh有时候是聪明反被聪明误。有一天二狗子盯着q̎本,心想q全村各戯有多钱是我说的算Q那我岂不是……。于是他头脑一热,U自从老张帐下划了十克金子到自己名下?/p> 本以为天衣无~,但没惛_老张也有记̎的习惯,有一天他正要付钱却被二狗子告知̎h׃。老张核对了一下自q账本Q明明还有十克啊Q于是拿着账本L二狗子理论,q一核对发现了那W未l老张同意的{账?/p> 东窗事发Q比Ҏ炸开锅了。二狗子被弹劾是不可避免了,不过通过qg事,大家发现了̎本集中在一个h手里的弊端: 正当Z不知所措时Q村里一个叫中本聪的宅男U学家走上了収ͼ告诉大家他已l设计了一套不依赖M中央处理人的叫比特币的虚拟货币系l,可以解决上述问题。然后他~缓讲述了自qҎ?/p> 下面我们来看看中本聪同学是如何设计q套pȝ的?/p>基础设施搭徏 中本聪首先说明,要对现有账簿q行如下攚w: 此言一出,下面立刻炔R了。第一条还无所谓,但是W二条简直无法接受,因ؓ账簿可是记录了所有村民的交易Q这样大家的隐私不全暴露了吗?/p> 中本聪倒是不慌不忙Q拿Z一对奇怪的东西?/p> 中本聪说Q大家不要慌。在他的q套机制下,M人都不用真实n份交易,而是使用一个唯一的代号交易?/p> 他展CZ手里奇的东西,说这两g东西分别叫保密印章和印章扫描器。后面他会给村里每一户发一个保密印章和一个印章扫描器。两者的作用如下Q?/p> 有了q两个神奇的东西Q大家就可以在不暴露真实w䆾的情况下q行交易了,而印章隐含的那一串字W就是这户h家的代号。具体如何y妙利用保密印章和印章扫描器进行交易,会在下文详述?/p> 下一步,中本聪面向全村招募虚拟矿工,招募要求如下Q?/p> 很快Q大U有五分之一的村民加入比特币矿工l织Q共分成?个组?/p> 下面Q中本聪宣布Q先Ҏ二狗子手里的账簿Q把抉|的所有黄金按账簿记录的余额退q给每位村民Q然后彻底销毁这本̎ѝ?/p> 然后Q中本聪拿出一本新账簿Q在账簿的第一上记录了一些交易记录,特别的是Q这些记录的付款Z栏全都是“pȝ”Q而收ƾh分别是每个印章对应的隐含字符Q代表初始时刻,pȝ为每一户默认分配了一定数量比特币Q但是数量非常少Q都只有几枚Q甚x些不q的村户没有获得比特币?/p> 接着中本聪说Q由于目前市面上比特币非常少Q大家可以先回到用黄金做货币的时代,׃我不是村长,我也没有权利大家一定要承认比特币,大家可以自行军_要不要接受比特币。不q随着比特币的动和矿工的zdQ比特币会慢慢多h?/p>支付与交?/span> 做了q么多铺垫,l于说到重点了,下面说一下在q样一个体pM如何完成支付。以老张付给老李10个比特币Z?/p> Z支付10个比特币Q老张首先要询问老李的标识字W串Q例如是“ABCDEFG”Q同时老张也有一个标识字W串例如?#8220;HIJKLMN”Q然后老张写一张单子,内容?#8220;HILKLMN支付10比特币给ABCDEFG”Q然后用自己的保密印章改一个章Q将q张单子交给老李。另外ؓ了便于追溯这W钱的来源,q要在单子里注明q笔q来源记在哪一,例如q个单子里,老张?0比特币来自徏立̎时pȝ的赠送,记录在̎第一c?/p> 老李拿到q个单子后,需要确认这个单子确实是来自“HIJKLMN”q个人(也就是老张Q签|的Q这个ƈ不困难。因为单子上必须有保密章Q老李拿出印章扫描器,扫一下章Q如果液晶屏昄出的字符和付ƾh字符是一致的Q这里是“HIJKLMN”Q,可以确认单子确实是付款人签|的。这是因为根据保密印章的机制Q没有其他h可以伪造印章,M一个h只要扫描一下印章,都可以确认单子的付款人和盖章人是否一致?/p> q个pȝ到目前还是很有问题。通过保密印章Q收ƾh虽然可以认付款人确实签|了q䆾单子Q但是无法自行确认付ƾh是否有够的余额支付。之前的中央虚拟货币pȝ中,二狗子负责检查付ƾh的余额,q知收款Z易是否有效,现在把二狗子开了,谁来负责记̎和确认每W交易的有效性呢Q?/p> 之前说过Q中本聪设计的这个系l是分布式货币系l,不依赖Q何中央h物,所以不会有一个或数几个责这件事Q最l承担这份工作的是之前所提到的矿工组l。老张、老李和全村其他Q何用比特币q行交易的村民都依赖矿工l织的工作才能完成交易?/p> 矿工的工作是整个pȝ的核心,也是最复杂性最高的地方。下面逐步介绍矿工的工作内容和目的?/p> 俗话_工欲善其事,必先利其器。比特币矿工虽然不用铁撅、铁锨和探照灯等工具Q不q也要有一些必备的东西?/p> 初始账簿。每个组首先自己复制一份初始̎,初始账簿只有一,记录了系l的W一ơ赠?/p> I̎纸。每个小l有若干账簿U,每一늺上仅有̎结构,没有填内容,具体内容的书写规则后面讲q。下面是一张空账簿U的样子Q各个字D늚意义后面会说?/p> ~码生成器(哈希函数Q。中本聪又向矿工l织的每个组分发了若q编码生成器Q这个东西很奇Q将一̎填好内容的账簿U放入这个机器,机器会在账簿U的“本̎单编?#8221;一栏自动打C串由“0”?#8220;1”l成的编P?56个。最奇的是Q编L成器有如下功能: 有了上面的工P矿工l织可以开工了Q?/p> 中本聪规定,每笔交易的发起hQ不但要交易单l到收款人,q要同时复制若干份一模一L交易单投递到每个矿工组的收件箱里?/p> 矿工组的h定期到自q收g里把收集到的交易单一q取出来?/p> 此时组的h拿出一张空的̎纸Q把q些交易填写?#8220;交易清单”一栏,同时扑ֈ当前账簿最后一,最后一늚~号抄写?#8220;上一张̎单编号一?#8221;。注意还有个“q运数字”Q可以随便填上一个数字,?2345。然后,这栯̎纸攑օ~号生成器,打印好编P一张̎就完成了?/p> 如果你以为矿工的工作p么简单,那就大错牚w了,中本聪有个变态的规定Q只有编L?0个数均ؓ0Q这̎纸才算有效?/p> Ҏ之前对编L成器的描qͼ要修改编P只能修改账簿U的内容Q?#8220;交易清单”?#8220;上一张̎纸~号”是不能随便改的,那么只能改幸q数字了。于是ؓ了生成有效的账簿U,组里的矿工׃断抄写̎纸Q但每张U的q运数字都不同,然后不断的重复将U放入编码器Q如果生成的~号不符合规定,q张U就废了,重复q个q程直到生成一串有效的~号?/p> 我们知道Q如果编L每一个数字都是随机的Q那么^均写1000多张q运数字不同的纸才能获得一个有效的~号?/p> q就奇怪了Q这些矿工ؓ什么要拼命q这看似无意义的事情呢?q记得之前说q矿工有报酬吧,q就是矿工的动力了。中本聪规定Q每一张̎纸的交易清单第一条交易ؓ“pȝl这个小l支?0个比特币”。也是_如果你生成了一张有意义的̎纸Qƈ且被所有挖矿小l接受了Q那么就意味着q条交易也被接受了,你的挖矿组获得?0个比特币?/p> q就是矿工被叫做矿工的原因,也是Z么之前说随着交易和矿工的zdQ比特币的数量会不断增多。例如下面是一个挖矿过E,q个组的公共比特币帐号?#8220;UVWXYZ”?/p> 在幸q数字尝试到“533”Ӟpȝ生成了一|效̎ѝ?/p> 当某挖矿组q运的生成了一张有意义的̎,Z得到奖励Q必ȝ刻请其它组认自己的工作。前面说q,当前村里?个挖矿组Q所以这个小l必d有效账簿U誊?份快马加鞭送到其他6个小l请求确认?/p> 中本聪规定,当某个小l接到其他小l送来的̎纸Ӟ必须立即停下手里的挖矿工作进行̎确认?/p> 需要确认的信息有三个: 首先看第一个,q个认比较单。只要将送来的̎纸攑օ~码生成器进行验证,如果验证通过Q则~号有效?/p> W二部分需要将账簿上?#8220;上一̎纸~号”和这个小l目前保存的有效账簿最后一늼h对,如果相同则确认,如果不同Q需要顺着已有账簿向前比对Q直到找到这个编Lc如果没有找到指定的“上一̎纸~号”对应的页Q这个小l会此丢掉。不予确认?/p> 注意Q由上面的机制可以保证,如果各个组手里的̎纸是相同的Q那么他们都能按同样的顺序装订成相同的̎ѝ因为后面一张纸的编hL依赖前面的纸的编P~码生成器的机制保证了所有合法̎纸的相对先后顺序在每个组那里都是相同的(可能会有分支Q但不会出现环,后面l讲Q?/p> 最后是如何认交易清单有效Q其实也是要确认当前每W交易的付款人有_的余额支付这W钱。由于交易信息里包含q笔钱是如何来的Q还包含了记录来源交易的账单~号。例如,HIJKLMN要给ABCDEFG10个比特币Qƈ注明了这10个比特币来自之前OPQRST支付lHIJKLMN的一W交易,认旉先要认之前q笔交易是否存在Q同时还要检查HIJKLMN在这之前没有这10个比特币支付l别人。这一切确认后Q这W交易有效性就被确认了?/p> 其中W一W是pȝ奖励l生成这̎的组?0个,q笔交易大家都默认承认,后面的只要按照上q方法追溯,可以确认HIJKLMN是否当前真有10个比特币支付lABCDEFG?/p> 如果完成了所有了上述验证q全部通过Q这个小l就认可了上q̎纸有效Q然后将q张账簿Uƈ入小l的主̎,舍弃目前正在q行的工作,后面的挖矿工作会Zq本更新后的主̎本进行?/p> 对于挖矿组来说Q当账簿UR出dQ如果后面有收到其他组送来的̎纸Q其“上一̎纸~号”׃前送出ȝ账簿U,那么pCZ们的工作成功被其他小l认可了Q因为已l有组Z他们的̎纸l箋工作了。此Ӟ可以_略的说可以认ؓ已经得到?0个比特币?/p> 另外QQ何一个小l当新生成有效̎纸或确认了别的组的̎纸Ӟ将最新被q个组承认的交易写到公告牌上,那么收款人只要发现相关交易被各个组认可了,基本可以认W钱已经C自己的̎上,后面他就可以在付ƾ时钱的来源指向这W交易了?/p> 以上是整个比特币的支付体系。下面我们来分析一下,q个体系Z么可以工作下去,以及q个体系可能面的风险?/p>工作机制分析 虽然上面阐述了比特币的基本运作规则,但是村民们还是有不少疑问。所以中本聪同学专门开了个{疑会,解答常见问题。下面ȝ一下村民最集中兛_的问题?/p> 注意在上面的q行机制中,各个挖矿组是ƈ行工作的Q因此完全可能出现这L情况Q某组收到两䆾不一L账簿,它们都基于当前这个小l的主̎的最后一,q且内容也都完全合法Q怎么办? 关于q个问题Q中本聪同学_组不应该以U性方式组l̎,而应该以树状l织账簿QQ何时刻,都以当前最长分支作Z账簿Q但是保留其它分支。D个例子,某小l同时收到A、B两䆾账簿,l核都是合法的Q此时小l应该将两页以分叉的形式l织hQ如下图所C: 黑色表示当前账簿d。此Ӟ可以随便选择一个页作ؓ当前d支,例如选择AQ?/p> 此时如果有一个新的̎K是基于A的,那么q个dgl下去: 如果q个d一直这么gl下去,表示大家基本都以AZqԌB׃被遗忘。但是也有可能忽然B变成更长了: 那么我们需要将B分支作ؓ当前dQ基于这个分支进行后l工作?/p> 从局部来看,虽然在某一时刻各个组的̎主q可能存在不一_但大方向是一致的Q那些偶由于不同步产生的小分支Q会很快被没在历史中?/p> 关于q个问题Q中本聪同学_只要挖矿l织中大多数人是诚实的,q个pȝ可靠,具体分几个方面给予答复?/p> 首先Q基于保密印章机Ӟ没有伪造他n份进行付ƾ,因ؓ~码生成器在打印~码时会核对所有交易单的保密印章,印章和付ƾh不一致会拒绝打印?/p> 而且诚实的矿工也不会承认不合法的交易Q如某笔交易付款方余额不够)?/p> 所以只有一U可能的d行ؓQ即在收ƾh认收款后,从另一条分支上建立另外的交易单Q取消之前的付款Q而将同一W钱再次付款l另一个hQ即所谓的double-spending问题Q。下面同L一个例子说明这个问题?/p> 先假设有一个攻击者拥?0个比特币Q他准备这W钱同时支付l两名受完A和BQƈ都得到承认?/p> W一步,d者准备从受害者A手里?0比特币的黄金Q他{v交易单给受害者AQ{10个比特币l受完A?/p> W二步,q笔交易在最新的账簿中被确认,q被各个挖矿组公告出来。受害hA看到公告Q确认比特币到̎Q给了攻击?0个比特币{值的黄金?/p> W三步,d者找到̎,从包含刚才交易的账簿늚前一做Z个分支,生成更多的̎单页Q超q刚才的分支。由于此时刚才攻击者制造的分支变成了主q分支,而包含受完A得到q分支变成了旁支,因此挖矿l织不再承认刚才的{账,受害者A得到?0比特币被取消了?/p> W四步,d者可以再ơ签|交易单Q将同一W钱支付l受完B。受完B认钱到账后Q支付给d者等值黄金?/p> xQ攻击者将10个比特币׃两次Q从两名受害者那里各购得{值黄金。攻击者还可以如法炮制Q取消与受害者B的{账,同一W钱再支付给其他?#8230;… 关于q种dQ中本聪l出的解x案是Q徏议收ƾh不要在公告挂出时立即认交易完成Q而是应该再看一D|_{待各个挖矿组再挂?张确认̎,q且之前的̎没有被取消Q才认钱已到̎?/p> 中本聪解释道Q之前设定变态的~号规则Q正是ؓ了防御这一炏V根据前面所qͼ生成有效账簿不是那么简单的Q要p大量的h力反复试不同的幸q数字,而且q程完全是碰q气。如果某账簿包含你收到q认Qƈ且在后面又gl了6个,那么d者想要在落后6늚情况下从另一个分支赶当前主分支是非常困隄Q除非攻击者拥有非常多的h力,过其他所有诚实矿工的人力之和?/p> 而且Q如果攻击者有如此多h力,与其p么大力气搞这U攻击,q不如做良民挖矿来的收益大。这׃动机上杜l了d的Ş成?/p> 中本聪说Q这一Ҏ也想C。前面忘了说了,我给矿工l织的操作细则手册会说明Q刚开始我们协议每生成一̎,奖励组50个比特币Q后面,每当账簿增加21,000,奖励减半,例如当达?10,000后Q每生成一̎奖?5个比特币Q?20,000后Q每生成一奖?2.5个,依次cLQ等账簿辑ֈ6,930,000后Q新生成账簿就没有奖励了。此时比特币全量Uؓ21,000,000个,q就是比特币的总量Q所以不会无限增加下厅R?/p> 到时Q矿工的收益会由挖矿所得变为收取手l费。例如,你在转̎时可以指定其?%作ؓ手箋Ҏ付给生成账簿늚组Q各个小l会挑选手l费高的交易单优先确认?/p> 不会。中本聪解释Q虽然可以Q意加入和退出矿工组l,D矿工人数变化Q每个矿工也会拿C个编码生成器Q不q我已经在编码生成器中加入了调控机制Q当前工作的~码生成器越多,每个机器的效率就低Q保证新账簿는成速率不变?/p> 实是这L。例如你要和某h交易Q必然要要到他的代号才能填写交易单。因为收ƾh一栏要填入那h的代受不q中本聪说可以提供无限制的保密印章,每一ơ交易用不同的保密印章,q样查̎就q查不到同一个h的所有̎目了?/p> {疑完毕?/p>说明 本文用通俗比喻的方式讲解了比特币的q行机制。有几点需要说明:以物易物的比Ҏ
实物货币
W号货币
中央pȝ虚拟货币
分布式虚拟货?/h2>
账簿公开机制
w䆾与签名机Ӟ公钥加密pȝQ?/h2>
成立虚拟矿工l织Q挖矿群体)
建立初始账簿Q创世块Q?/h2>
付款人签|交易单
收款人确认单据签|h
收款人确认付ƾh余额
矿工的工?/h2>
矿工的工?/h3>
攉交易?/h3>
填写账簿
认账簿
账簿认反馈
核心问题{疑
如果同时收到两䆾合法的̎K怎么办?
如果挖矿组有h伪造̎怎么?/h3>
比特币会一直增加下去,岂不是会严重通货膨胀
没有奖励后,没人做矿工了,岂不是没人帮忙确认交易了
矿工如果来多Q比特币生成速度会变快吗
虽然每个人的代号是匿名的Q但如果泄露了某个h的代P账簿又是公开的,岂不是他的所有̎目都查出来了
参?/span>
]]>
k1,k2,K均ؓl验讄的参敎ͼfi是词在文档中的频率Q?/span>qfi是词在查询中的频率?/span>
K1通常?/span>1.2Q通常?/span>0-1000
K的Ş式较为复?/span>
K=
1 | 0 |
2 | 10 |
3 | 110 |
4 | 1110 |
5 | 11110 |