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 胡滿超 閱讀(472) |
評論 (0) |
編輯 收藏
摘要: 通過這篇文章我們主要回答以下幾個問題: 1. LSH解決問題的背景,即以圖片相似性搜索為例,如何解決在海量數(shù)據(jù)中進(jìn)行相似性查找? 2. 圖像相似性查找的連帶問題:相似性度量,特征提取; 3. LSH的數(shù)學(xué)分析,即局部敏感HASH函數(shù)的數(shù)學(xué)原理,通過與、或構(gòu)造提升查找的查...
閱讀全文
posted @
2018-02-24 13:10 胡滿超 閱讀(8867) |
評論 (0) |
編輯 收藏
直接上圖

腦圖源文件下載地址
http://www.shnenglu.com/Files/humanchao/LSH(Locality%20Sensitive%20Hashing).zip
參考文獻(xiàn):
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 胡滿超 閱讀(1067) |
評論 (0) |
編輯 收藏
想轉(zhuǎn)型的都是那些不甘于現(xiàn)狀的,我就是其中之一。
我是2005年畢業(yè),從畢業(yè)前的實習(xí)開始,做CAD二次開發(fā),電氣設(shè)計軟件。
2006年轉(zhuǎn)做無紙辦公軟件,那個年代無紙辦公流行,C++更是主流,感覺也算有前途。
2008年轉(zhuǎn)做Open Office的開發(fā),維護世界級的產(chǎn)品會產(chǎn)生一種自豪感,Open Office本身代碼體量也的確非常大。
2010年轉(zhuǎn)做安全類的產(chǎn)品,從一個模塊級負(fù)責(zé)人,核心程序員,到架構(gòu)師,再到負(fù)責(zé)整體產(chǎn)品線的負(fù)責(zé)人,經(jīng)歷了4年時間。
在我的職業(yè)生涯中時不時就會產(chǎn)生一種莫名的危機感,經(jīng)常會問自己,自己掌握的技術(shù)夠深嗎、是主流的技術(shù)嗎、未來的職業(yè)發(fā)展又在哪里?
2006年一個同事跳槽去了一家大型企業(yè),走的時候跟我們說,做二次開發(fā)沒有前途,出去面試會被人看不起。但是我發(fā)現(xiàn),在具體編碼的過程中,很多經(jīng)驗豐富的程序員甚至不能把一個對話框程序?qū)懙暮芷粒粋€對話框類的實現(xiàn)將界面與邏輯混在一起,沒有太多解耦的思想在里面。后來的工作中悟出一個道理,沒有小角色,只有小演員,只有把現(xiàn)在的事情做好,才能有未來。
2008年我在一個不滿意的環(huán)境中,苦苦的尋找下一步的方向,從坐落在小區(qū)里的公司一直面試到了微軟和IBM這個級別的公司里。被挫了很多次,也積累了很多面試的經(jīng)驗。其間有一家做搜索引擎的公司我沒去成,我的理由只是因為工資沒有任何提高。其實大家跳槽的時候都說是為了職業(yè)發(fā)展,結(jié)果往往是哪里給的條件好就去哪里,而在一般意義上看,高工資與好公司一般都是成正比的。當(dāng)然偶爾也有例外,比如這里提到的做搜索的公司,如果當(dāng)初在08的時候就選擇做搜索引擎,也許后面的故事會很不同。
2010年我擁有了工作5年的工作經(jīng)驗,我發(fā)現(xiàn)一般工作到5年以后才會遇到一些真正的好機會。跳槽去了一家剛剛在創(chuàng)業(yè)板上市不久的公司,做一些安全類的產(chǎn)品。從這一刻開始,由于業(yè)務(wù)的快速發(fā)展和領(lǐng)導(dǎo)的信任,我開始擁有了一些能夠獨當(dāng)一面的能力與鍛煉機會。除了編寫一些從無到有的模塊,我開始關(guān)注架構(gòu)的設(shè)計,團隊培養(yǎng),產(chǎn)品管理等一系列更宏觀的問題。
回到原來的問題,我們?yōu)槭裁匆D(zhuǎn)型,原因總結(jié)如下:
1. 大多數(shù)的程序員職業(yè)起點都偏低,很多人甚至只能從外包做起;
2. 大多數(shù)的程序員做不上主流產(chǎn)品,主流技術(shù),所掌握的都是一些較為落后的技能,靠體力掙錢,而不是靠智力;
3. 很多公司不能給員工穩(wěn)定的成長預(yù)期,過了某一個發(fā)展階段雙方很難找到共贏點;
4. 世界發(fā)展太快,當(dāng)我們還在懵懂之時外面世界已經(jīng)經(jīng)歷了從互聯(lián)網(wǎng),云計算,移動互聯(lián)網(wǎng),大數(shù)據(jù),人工智能,一波又一波的產(chǎn)業(yè)升級。而我們一波都沒趕上。
于是我們要轉(zhuǎn)型。2011年當(dāng)我看到hadoop權(quán)威指南這本書的時候,我感覺大數(shù)據(jù)一起會流行起來,而且大數(shù)據(jù)未來會在各行各業(yè)遍地開花。
可是,留給學(xué)習(xí)的時間真的很少,工作忙碌,下班要顧家。只好擠時間學(xué)習(xí),在上班的路上,坐公交車、坐地鐵,給小孩洗衣服,可以帶著耳機聽視頻,成了唯一的學(xué)習(xí)方式。聽視頻雖然不能學(xué)到太多技術(shù)精髓,但也可以了解不少技術(shù),開闊眼界。
2014年底,我轉(zhuǎn)型做一些也數(shù)據(jù)相關(guān)的工作,做數(shù)據(jù)清洗,分析,建模,治理。我總結(jié)一下轉(zhuǎn)型要做的一些事情以及要學(xué)的東西。
1. 要有行動,只停留在想法層面產(chǎn)生不了任何實質(zhì)上的進(jìn)展;
2. 擠時間,時間對于每一個認(rèn)真生活的人都很寶貴,擠一下吧,少玩玩游戲啥的,總會有的;
3. 要重視學(xué)習(xí),尤其是看書進(jìn)行系統(tǒng)學(xué)習(xí),從網(wǎng)絡(luò)上看到的只言片語做為了解還行,但是不去系統(tǒng)掌握知識,境界很難上到新的臺階;
4. 要注視理論學(xué)習(xí),上班以后最不缺少的就是實踐,天天都在實踐反而凸顯的學(xué)習(xí)理論的重要性;
5. 把主要學(xué)習(xí)時間花在那些最通用、最被廣泛采用的技術(shù)上,如果每天都在學(xué)習(xí)那些其他公司所不需要的領(lǐng)域知識時,說明該跳槽了;
6. 要注重基本的數(shù)據(jù)結(jié)構(gòu)和算法,這些是寫好程序的基礎(chǔ),基礎(chǔ)決定高度,做那些能夠解決困難問題的人,而不是做只能執(zhí)行具體任務(wù)的人。差別在于能不能把現(xiàn)實的工程問題抽象成數(shù)據(jù)與算法。
7. 選一個好的方向,像高并發(fā),分布式系統(tǒng),數(shù)據(jù)庫,大數(shù)據(jù)工具,統(tǒng)計建模,機器學(xué)習(xí),數(shù)據(jù)挖掘都是即有用又缺人的領(lǐng)域,搞好任何一個領(lǐng)域都會有好的發(fā)展;
8. 我感覺能把數(shù)據(jù)分析、機器學(xué)習(xí)、自然語言處理、R語言這些學(xué)好,統(tǒng)計建模依然是很基礎(chǔ)知識,不能跳躍學(xué)習(xí);
9. 學(xué)習(xí)最重要的是入門與堅持,入門可以學(xué)視頻教程,精深要靠應(yīng)用與時間打磨;
就程序員的職業(yè)發(fā)展來看,我總結(jié)自己的一些經(jīng)驗:
1. 1~3年,要學(xué)精一門語言,這并不太難;
2. 3~5年,應(yīng)該關(guān)注軟件的設(shè)計,設(shè)計模式等知識
3. 5~7年,應(yīng)該能獨立完成一個軟件模塊,從需求到測試的全過程。我發(fā)現(xiàn)一般這個階段會遇到一些獲得期權(quán)或者股權(quán)的機會,能不能最終形成收益看運氣吧;
4. 7~10年,爭取可以負(fù)責(zé)更為全面的工作
在這個過程中,像數(shù)據(jù)庫,操作系統(tǒng),并發(fā),多線程,項目管理,產(chǎn)品管理這些知識都需要,掌握的越多越好吧。
開發(fā)一個數(shù)據(jù)產(chǎn)品跟一個傳統(tǒng)軟件產(chǎn)品并沒有太大的本質(zhì)差異,很多技能從事哪個行業(yè)都是需要的。
posted @
2016-07-14 13:24 胡滿超 閱讀(1771) |
評論 (0) |
編輯 收藏
一級國標(biāo)漢字(3755個)
啊阿埃挨哎唉哀皚癌藹矮艾礙愛隘鞍氨安俺按暗岸胺案骯昂盎凹敖熬翱襖傲奧懊澳芭捌扒叭吧笆八疤巴拔跋靶把耙壩霸罷爸白柏百擺佰敗拜稗斑班搬扳般頒板版扮拌伴瓣半辦絆邦幫梆榜膀綁棒磅蚌鎊傍謗苞胞包褒剝薄雹保堡飽寶抱報暴豹鮑爆杯碑悲卑北輩背貝鋇倍狽備憊焙被奔苯本笨崩繃甭泵蹦迸逼鼻比鄙筆彼碧蓖蔽畢斃毖幣庇痹閉敝弊必辟壁臂避陛鞭邊編貶扁便變卞辨辯辮遍標(biāo)彪膘表鱉憋別癟彬斌瀕濱賓擯兵冰柄丙秉餅炳病并玻菠播撥缽波博勃搏鉑箔伯帛舶脖膊渤泊駁捕卜哺補埠不布步簿部怖擦猜裁材才財睬踩采彩菜蔡餐參蠶殘慚慘燦蒼艙倉滄藏操糙槽曹草廁策側(cè)冊測層蹭插叉茬茶查碴搽察岔差詫拆柴豺攙摻蟬饞讒纏鏟產(chǎn)闡顫昌猖場嘗常長償腸廠敞暢唱倡超抄鈔朝嘲潮巢吵炒車扯撤掣徹澈郴臣辰塵晨忱沉陳趁襯撐稱城橙成呈乘程懲澄誠承逞騁秤吃癡持匙池遲弛馳恥齒侈尺赤翅斥熾充沖蟲崇寵抽酬疇躊稠愁籌仇綢瞅丑臭初出櫥廚躇鋤雛滁除楚礎(chǔ)儲矗搐觸處揣川穿椽傳船喘串瘡窗幢床闖創(chuàng)吹炊捶錘垂春椿醇唇淳純蠢戳綽疵茨磁雌辭慈瓷詞此刺賜次聰蔥囪匆從叢湊粗醋簇促躥篡竄摧崔催脆瘁粹淬翠村存寸磋撮搓措挫錯搭達(dá)答瘩打大呆歹傣戴帶殆代貸袋待逮怠耽擔(dān)丹單鄲撣膽旦氮但憚淡誕彈蛋當(dāng)擋黨蕩檔刀搗蹈倒島禱導(dǎo)到稻悼道盜德得的蹬燈登等瞪凳鄧堤低滴迪敵笛狄滌翟嫡抵底地蒂第帝弟遞締顛掂滇碘點典靛墊電佃甸店惦奠淀殿碉叼雕凋刁掉吊釣調(diào)跌爹碟蝶迭諜疊丁盯叮釘頂鼎錠定訂丟東冬董懂動棟侗恫凍洞兜抖斗陡豆逗痘都督毒犢獨讀堵睹賭杜鍍肚度渡妒端短鍛段斷緞堆兌隊對墩噸蹲敦頓囤鈍盾遁掇哆多奪垛躲朵跺舵剁惰墮蛾峨鵝俄額訛娥惡厄扼遏鄂餓恩而兒耳爾餌洱二貳發(fā)罰筏伐乏閥法琺藩帆番翻樊礬釩繁凡煩反返范販犯飯泛坊芳方肪房防妨仿訪紡放菲非啡飛肥匪誹吠肺廢沸費芬酚吩氛分紛墳焚汾粉奮份忿憤糞豐封楓蜂峰鋒風(fēng)瘋烽逢馮縫諷奉鳳佛否夫敷膚孵扶拂輻幅氟符伏俘服浮涪福袱弗甫撫輔俯釜斧脯腑府腐赴副覆賦復(fù)傅付阜父腹負(fù)富訃附婦縛咐噶嘎該改概鈣蓋溉干甘桿柑竿肝趕感稈敢贛岡剛鋼缸肛綱崗港杠篙皋高膏羔糕搞鎬稿告哥歌擱戈鴿胳疙割革葛格蛤閣隔鉻個各給根跟耕更庚羹埂耿梗工攻功恭龔供躬公宮弓鞏汞拱貢共鉤勾溝茍狗垢構(gòu)購夠辜菇咕箍估沽孤姑鼓古蠱骨谷股故顧固雇刮瓜剮寡掛褂乖拐怪棺關(guān)官冠觀管館罐慣灌貫光廣逛瑰規(guī)圭硅歸龜閨軌鬼詭癸桂柜跪貴劊輥滾棍鍋郭國果裹過哈骸孩海氦亥害駭酣憨邯韓含涵寒函喊罕翰撼捍旱憾悍焊汗?jié)h夯杭航壕嚎豪毫郝好耗號浩呵喝荷菏核禾和何合盒貉閡河涸赫褐鶴賀嘿黑痕很狠恨哼亨橫衡恒轟哄烘虹鴻洪宏弘紅喉侯猴吼厚候后呼乎忽瑚壺葫胡蝴狐糊湖弧虎唬護互滬戶花嘩華猾滑畫劃化話槐徊懷淮壞歡環(huán)桓還緩換患喚瘓豢煥渙宦幻荒慌黃磺蝗簧皇凰惶煌晃幌恍謊灰揮輝徽恢蛔回毀悔慧卉惠晦賄穢會燴匯諱誨繪葷昏婚魂渾混豁活伙火獲或惑霍貨禍擊圾基機畸稽積箕肌饑跡激譏雞姬績緝吉極棘輯籍集及急疾汲即嫉級擠幾脊己薊技冀季伎祭劑悸濟寄寂計記既忌際妓繼紀(jì)嘉枷夾佳家加莢頰賈甲鉀假稼價架駕嫁殲監(jiān)堅尖箋間煎兼肩艱奸緘繭檢柬堿鹼揀撿簡儉剪減薦檻鑒踐賤見鍵箭件健艦劍餞漸濺澗建僵姜將漿江疆蔣槳獎講匠醬降蕉椒礁焦膠交郊澆驕嬌嚼攪鉸矯僥腳狡角餃繳絞剿教酵轎較叫窖揭接皆秸街階截劫節(jié)桔杰捷睫竭潔結(jié)解姐戒藉芥界借介疥誡屆巾筋斤金今津襟緊錦僅謹(jǐn)進(jìn)靳晉禁近燼浸盡勁荊兢莖睛晶鯨京驚精粳經(jīng)井警景頸靜境敬鏡徑痙靖竟競凈炯窘揪究糾玖韭久灸九酒廄救舊臼舅咎就疚鞠拘狙疽居駒菊局咀矩舉沮聚拒據(jù)巨具距踞鋸俱句懼炬劇捐鵑娟倦眷卷絹撅攫抉掘倔爵覺決訣絕均菌鈞軍君峻俊竣浚郡駿喀咖卡咯開揩楷凱慨刊堪勘坎砍看康慷糠扛抗亢炕考拷烤靠坷苛柯棵磕顆科殼咳可渴克刻客課肯啃墾懇坑吭空恐孔控?fù)缚诳劭芸菘蘅呖嗫釒煅澘淇蹇婵缈鑹K筷儈快寬款匡筐狂框礦眶曠況虧盔巋窺葵奎魁傀饋愧潰坤昆捆困括擴廓闊垃拉喇蠟臘辣啦萊來賴藍(lán)婪欄攔籃闌蘭瀾讕攬覽懶纜爛濫瑯榔狼廊郎朗浪撈勞牢老佬姥酪烙澇勒樂雷鐳蕾磊累儡壘擂肋類淚棱楞冷厘梨犁黎籬貍離漓理李里鯉禮莉荔吏栗麗厲勵礫歷利傈例俐痢立粒瀝隸力璃哩倆聯(lián)蓮連鐮廉憐漣簾斂臉鏈戀煉練糧涼梁粱良兩輛量晾亮諒撩聊僚療燎寥遼潦了撂鐐廖料列裂烈劣獵琳林磷霖臨鄰鱗淋凜賃吝拎玲菱零齡鈴伶羚凌靈陵嶺領(lǐng)另令溜琉榴硫餾留劉瘤流柳六龍聾嚨籠窿隆壟攏隴樓婁摟簍漏陋蘆盧顱廬爐擄鹵虜魯麓碌露路賂鹿潞祿錄陸戮驢呂鋁侶旅履屢縷慮氯律率濾綠巒攣孿灤卵亂掠略掄輪倫侖淪綸論蘿螺羅邏鑼籮騾裸落洛駱絡(luò)媽麻瑪碼螞馬罵嘛嗎埋買麥賣邁脈瞞饅蠻滿蔓曼慢漫謾芒茫盲氓忙莽貓茅錨毛矛鉚卯茂冒帽貌貿(mào)么玫枚梅酶霉煤沒眉媒鎂每美昧寐妹媚門悶們萌蒙檬盟錳猛夢孟瞇醚靡糜迷謎彌米秘覓泌蜜密冪棉眠綿冕免勉娩緬面苗描瞄藐秒渺廟妙蔑滅民抿皿敏憫閩明螟鳴銘名命謬摸摹蘑模膜磨摩魔抹末莫墨默沫漠寞陌謀牟某拇牡畝姆母墓暮幕募慕木目睦牧穆拿哪吶鈉那娜納氖乃奶耐奈南男難囊撓腦惱鬧淖呢餒內(nèi)嫩能妮霓倪泥尼擬你匿膩逆溺蔫拈年碾攆捻念娘釀鳥尿捏聶孽嚙鑷鎳涅您檸獰凝寧擰濘牛扭鈕紐膿濃農(nóng)弄奴努怒女暖虐瘧挪懦糯諾哦歐鷗毆藕嘔偶漚啪趴爬帕怕琶拍排牌徘湃派攀潘盤磐盼畔判叛乓龐旁耪胖拋咆刨炮袍跑泡呸胚培裴賠陪配佩沛噴盆砰抨烹澎彭蓬棚硼篷膨朋鵬捧碰坯砒霹批披劈琵毗啤脾疲皮匹痞僻屁譬篇偏片騙飄漂瓢票撇瞥拼頻貧品聘乒坪蘋萍平憑瓶評屏坡潑頗婆破魄迫粕剖撲鋪仆莆葡菩蒲埔樸圃普浦譜曝瀑期欺棲戚妻七凄漆柒沏其棋奇歧畦崎臍齊旗祈祁騎起豈乞企啟契砌器氣迄棄汽泣訖掐恰洽牽扦釬鉛千遷簽仟謙乾黔錢鉗前潛遣淺譴塹嵌欠歉槍嗆腔羌墻薔強搶橇鍬敲悄橋瞧喬僑巧鞘撬翹峭俏竅切茄且怯竊欽侵親秦琴勤芹擒禽寢沁青輕氫傾卿清擎晴氰情頃請慶瓊窮秋丘邱球求囚酋泅趨區(qū)蛆曲軀屈驅(qū)渠取娶齲趣去圈顴權(quán)醛泉全痊拳犬券勸缺炔瘸卻鵲榷確雀裙群然燃冉染瓤壤攘嚷讓饒擾繞惹熱壬仁人忍韌任認(rèn)刃妊紉扔仍日戎茸蓉榮融熔溶容絨冗揉柔肉茹蠕儒孺如辱乳汝入褥軟阮蕊瑞銳閏潤若弱撒灑薩腮鰓塞賽三叁傘散桑嗓喪搔騷掃嫂瑟色澀森僧莎砂殺剎沙紗傻啥煞篩曬珊苫杉山刪煽衫閃陜擅贍膳善汕扇繕墑傷商賞晌上尚裳梢捎稍燒芍勺韶少哨邵紹奢賒蛇舌舍赦攝射懾涉社設(shè)砷申呻伸身深娠紳神沈?qū)弸鹕跄I慎滲聲生甥牲升繩省盛剩勝圣師失獅施濕詩尸虱十石拾時什食蝕實識史矢使屎駛始式示士世柿事拭誓逝勢是嗜噬適仕侍釋飾氏市恃室視試收手首守壽授售受瘦獸蔬樞梳殊抒輸叔舒淑疏書贖孰熟薯暑曙署蜀黍鼠屬術(shù)述樹束戍豎墅庶數(shù)漱恕刷耍摔衰甩帥栓拴霜雙爽誰水睡稅吮瞬順?biāo)凑f碩朔爍斯撕嘶思私司絲死肆寺嗣四伺似飼巳松聳慫頌送宋訟誦搜艘擻嗽蘇酥俗素速粟僳塑溯宿訴肅酸蒜算雖隋隨綏髓碎歲穗遂隧祟孫損筍蓑梭唆縮瑣索鎖所塌他它她塔獺撻蹋踏胎苔抬臺泰酞太態(tài)汰坍?dāng)傌澃c灘壇檀痰潭譚談坦毯袒碳探嘆炭湯塘搪堂棠膛唐糖倘躺淌趟燙掏濤滔絳萄桃逃淘陶討套特藤騰疼謄梯剔踢銻提題蹄啼體替嚏惕涕剃屜天添填田甜恬舔腆挑條迢眺跳貼鐵帖廳聽烴汀廷停亭庭挺艇通桐酮瞳同銅彤童桶捅筒統(tǒng)痛偷投頭透凸禿突圖徒途涂屠土吐兔湍團推頹腿蛻褪退吞屯臀拖托脫鴕陀馱駝橢妥拓唾挖哇蛙洼娃瓦襪歪外豌彎灣玩頑丸烷完碗挽晚皖惋宛婉萬腕汪王亡枉網(wǎng)往旺望忘妄威巍微危韋違桅圍唯惟為濰維葦萎委偉偽尾緯未蔚味畏胃喂魏位渭謂尉慰衛(wèi)瘟溫蚊文聞紋吻穩(wěn)紊問嗡翁甕撾蝸渦窩我斡臥握沃巫嗚鎢烏污誣屋無蕪梧吾吳毋武五捂午舞伍侮塢戊霧晤物勿務(wù)悟誤昔熙析西硒矽晰嘻吸錫犧稀息希悉膝夕惜熄烯溪汐犀檄襲席習(xí)媳喜銑洗系隙戲細(xì)瞎蝦匣霞轄暇峽俠狹下廈夏嚇掀锨先仙鮮纖咸賢銜舷閑涎弦嫌顯險現(xiàn)獻(xiàn)縣腺餡羨憲陷限線相廂鑲香箱襄湘鄉(xiāng)翔祥詳想響享項巷橡像向象蕭硝霄削哮囂銷消宵淆曉小孝校肖嘯笑效楔些歇蝎鞋協(xié)挾攜邪斜脅諧寫械卸蟹懈泄瀉謝屑薪芯鋅欣辛新忻心信釁星腥猩惺興刑型形邢行醒幸杏性姓兄兇胸匈洶雄熊休修羞朽嗅銹秀袖繡墟戌需虛噓須徐許蓄酗敘旭序畜恤絮婿緒續(xù)軒喧宣懸旋玄選癬眩絢靴薛學(xué)穴雪血勛熏循旬詢尋馴巡殉汛訓(xùn)訊遜迅壓押鴉鴨呀丫芽牙蚜崖衙涯雅啞亞訝焉咽閹煙淹鹽嚴(yán)研蜒巖延言顏閻炎沿奄掩眼衍演艷堰燕厭硯雁唁彥焰宴諺驗殃央鴦秧楊揚佯瘍羊洋陽氧仰癢養(yǎng)樣漾邀腰妖瑤搖堯遙窯謠姚咬舀藥要耀椰噎耶爺野冶也頁掖業(yè)葉曳腋夜液一壹醫(yī)揖銥依伊衣頤夷遺移儀胰疑沂宜姨彝椅蟻倚已乙矣以藝抑易邑屹億役臆逸肄疫亦裔意毅憶義益溢詣議誼譯異翼翌繹茵蔭因殷音陰姻吟銀淫寅飲尹引隱印英櫻嬰鷹應(yīng)纓瑩螢營熒蠅迎贏盈影穎硬映喲擁傭臃癰庸雍踴蛹詠泳涌永恿勇用幽優(yōu)悠憂尤由郵鈾猶油游酉有友右佑釉誘又幼迂淤于盂榆虞愚輿余俞逾魚愉渝漁隅予娛雨與嶼禹宇語羽玉域芋郁吁遇喻峪御愈欲獄育譽浴寓裕預(yù)豫馭鴛淵冤元垣袁原援轅園員圓猿源緣遠(yuǎn)苑愿怨院曰約越躍鑰岳粵月悅閱耘云鄖勻隕允運蘊醞暈韻孕匝砸雜栽哉災(zāi)宰載再在咱攢暫贊贓臟葬遭糟鑿藻棗早澡蚤躁噪造皂灶燥責(zé)擇則澤賊怎增憎曾贈扎喳渣札軋鍘閘眨柵榨咋乍炸詐摘齋宅窄債寨瞻氈詹粘沾盞斬輾嶄展蘸棧占戰(zhàn)站湛綻樟章彰漳張掌漲杖丈帳賬仗脹瘴障招昭找沼趙照罩兆肇召遮折哲蟄轍者鍺蔗這浙珍斟真甄砧臻貞針偵枕疹診震振鎮(zhèn)陣蒸掙睜征猙爭怔整拯正政幀癥鄭證芝枝支吱蜘知肢脂汁之織職直植殖執(zhí)值侄址指止趾只旨紙志摯擲至致置幟峙制智秩稚質(zhì)炙痔滯治窒中盅忠鐘衷終種腫重仲眾舟周州洲謅粥軸肘帚咒皺宙晝驟珠株蛛朱豬諸誅逐竹燭煮拄矚囑主著柱助蛀貯鑄筑住注祝駐抓爪拽專磚轉(zhuǎn)撰賺篆樁莊裝妝撞壯狀椎錐追贅墜綴諄準(zhǔn)捉拙卓桌琢茁酌啄著灼濁茲咨資姿滋淄孜紫仔籽滓子自漬字鬃棕蹤宗綜總縱鄒走奏揍租足卒族祖詛阻組鉆纂嘴醉最罪尊遵昨左佐柞做作坐座
二級國標(biāo)漢字(3008個)
亍丌兀丐廿卅丕亙丞鬲孬噩丨禺丿匕乇夭爻卮氐囟胤馗毓睪鼗丶亟鼐乜乩亓羋孛嗇嘏仄厙厝厴厥廝靨贗匚叵匭匱匾賾卦卣刂刈刎剄刳劌剴剌剞剡剜蒯剽劂劁劐劓冂罔亻仃仉仂仨仡仫仞傴仳伢佤仵倀傖伉佇佞佧攸佚佝佟佗伲伽佶佴侑侉侃侏佾佻儕佼儂侔儔儼儷俅俚俁俜俑俟俸倩偌俳倬倏倮倭俾倜倌倥倨僨偃偕偈偎傯僂儻儐儺傺僖儆僭僬僦僮儇儋仝氽佘僉俎龠汆糴兮巽黌馘囅夔勹匍訇匐鳧夙兕亠兗亳袞袤褻臠裒稟嬴蠃羸冫冱冽冼凇冖冢冥讠訐訌訕謳詎訥詁訶詆詔詘詒誆誄詿詰詼詵詬詮諍諢詡誚誥誑誒諏諑諉諛諗諂誶諶諫謔謁諤諭諼諳諦諮諞謨讜謖謚謐謫谫譖譙譎讞譫讖卩巹阝阢阡阱阪阽阼陂陘陔陟隉陬陲陴隈隍隗隰邗邛鄺邙鄔邡邴邳邶鄴邸邰郟郅邾鄶郄郇鄆酈郢郜郗郛郫郯郾鄄鄢鄞鄣鄱鄯鄹酃酆芻奐勱劬劭劾哿勐勖勰叟燮矍廴凵凼鬯厶弁畚巰坌堊垡塾墼壅壑圩圬圪圳壙圮圯壢圻坂坩垅坫壚坼坻坨坭坶坳埡垤垌塏埏坰垴垓垠埕塒堝塤埒垸埴埯埸埤埝堋堍埽埭堀堞堙塄堠塥塬墁墉墚墀馨鼙懿艸艽艿芏芊芨芄芎芑薌芙芫蕓芾芰藶苊苣芘芷芮莧萇蓯芩芴芡芪芟芐苧芤苡茉苷苤蘢茇苜苴苒苘茌苻苓蔦茚茆塋煢苠苕茜荑蕘蓽茈莒茼茴茱莛蕎茯荏荇荃薈荀茗薺茭茺茳犖滎蕁茛藎荬蓀葒荮莰荸蒔萵莠莪莓莜蒞荼薟莩荽蕕荻莘莞莨鶯莼菁萁菥菘堇萘萋菝菽菖萜萸萑萆菔菟萏萃菸菹菪菅菀縈菰菡葜葑葚葙葳蕆蒈葺蕢葸萼葆葩葶蔞蒎萱葭蓁蓍蓐驀蒽蓓蓊蒿蒺蘺蒡蒹蒴蒗鎣蕷蔌甍蔸蓰蘞蔟藺蕖蔻蓿蓼蕙蕈蕨蕤蕞蕺瞢蕃蘄蕻薤薨薇薏蕹藪薜薅薹薷薰蘚藁藜藿蘧蘅蘩蘗蘼廾弈夼奩耷奕奚奘匏尢尥尬尷扌捫摶抻拊拚拗拮撟拶挹捋捃掭揶捱捺掎摑捭掬掊捩掮摜揲揸揠撳揄揞揎摒揆掾攄摁搋搛搠搌搦搡摞攖摭撖摺擷擼撙攛搟擐擗擤擢攉攥攮弋忒甙弒卟叱嘰叩叨叻吒吖吆呋嘸囈呔嚦呃吡唄咼吣吲咂咔呷呱呤咚嚀咄呶呦咝哐咭哂咴噠咧咦嘵嗶呲咣噦咻咿哌噲哚嚌咩咪咤噥哏哞嘜哧嘮哽唔哳嗩唣唏唑唧唪嘖喏喵啉囀啁啕唿啐唼唷啖啵啶啷唳唰啜喋嗒喃喱喹喈喁喟啾嗖喑啻嗟嘍嚳喔喙嗪嗷嗉嘟嗑囁嗬嗔嗦嗝嗄嗯嗥嗲噯嗌嗍嗨嗵嗤轡嘞嘈嘌嘁嚶嘣嗾嘀嘧嘭噘嘹噗嘬噍噢噙嚕噌噔嚆噤噱噫噻噼嚅嚓嚯囔囗囝囡圇囫囹囿圄圊圉圜幃帙帔帑幬幘幗帷幄幔幛幞幡岌屺岍岐嶇岈峴岙岑嵐岜岵岢崠岬岫岱岣峁岷嶧峒嶠峋崢嶗崍崧崦崮崤崞崆崛嶸崾崴崽嵬崳嵯嶁嵫嵋嵊嵩嵴嶂嶙嶝豳嶷巔彳彷徂徇徉後徠徙徜徨徭徵徼衢彡犭犰犴獷犸狃狁狎狍狒狨獪狩猻狴狷猁狳獫狺狻猗猓玀猊猞猝獼猢猹猥猬猸猱獐獍獗獠獬獯獾舛夥飧夤夂饣餳飩餼飪飫飭飴餉餑馀餛馇餿饃饈饉馓饌馕庀廡庋庖庥庠庹庵庾庳賡廒廑廛廨廩膺忄忉忖懺憮忮慪忡忤愾悵愴忪忭忸怙怵怦怛怏怍怩怫怊懌怡慟懨惻愷恂恪惲悖悚慳悝悃悒悌悛愜悻悱惝惘惆惚悴慍憒愕愣惴愀愎愫慊慵憬憔憧憷懔懵忝隳閂閆闈閎閔閌闥閭閫鬮閬閾閶鬩閿閽閼闃闋闔闐闕闞丬爿戕氵汔汜汊灃沅沐沔沌汨汩汴汶沆溈泐泔沭瀧瀘泱泗沲泠泖濼泫泮沱泓泯涇洹洧洌浹湞洇洄洙洎洫澮洮洵洚瀏滸潯洳涑浯淶潿浞涓涔浜浠浼浣渚淇淅淞瀆涿淠澠淦淝淙瀋涫淥涮渫湮湎湫溲湟溆湓湔渲渥湄滟溱溘灄漭瀅溥溧溽溻溷潷溴滏溏滂溟潢瀠瀟漤漕滹漯漶瀲潴漪漉漩澉澍澌潸潲潼潺瀨濉澧澹澶濂濡濮濞濠濯瀚瀣瀛瀹瀵灝灞宀宄宕宓宥宸甯騫搴寤寮褰寰蹇謇辶迓迕迥迮迤邇迦逕迨逅逄逋邐逑逍逖逡逵逶逭逯遄遑遒遐遨遘遢遛暹遴遽邂邈邃邋彐彗彖彘尻咫屐屙孱屣屨羼弳弩弭艴弼鬻屮妁妃妍嫵嫗妣妗姊媯妞妤姒妲妯姍妾婭嬈姝孌姣姘姹娌娉媧嫻娑娣娓婀婧婊婕娼婢嬋胬媼媛婷婺媾嫫媲嬡嬪媸嫠嫣嬙嫖嫦嫘嫜嬉嬗嬖嬲嬤孀尕尜孚孥孳孑孓孢駔駟駙騶驛駑駘驍驊駢驪騏騍騅驂騭騖驁騮騸驃驄驏驥驤纟紆紂紇紈纊紜紕紓紺紲紱縐紼絀紿绔絎絳綆綃綈綾綺緋绱緄綞綬綹綣綰緇緙緗緹緲繢緦緶緱縋緡縉縝縟縞縭縊縑繽縹縵縲繆繅纈繚繒韁繾繰繯纘幺畿巛甾邕玎璣瑋玢玟玨珂瓏玷玳珀珉珈珥珙頊琊珩珧珞璽琿璉琪瑛琦琥琨琰琮琬琛琚瑁瑜瑗瑕瑙璦瑭瑾璜瓔璀璁璇璋璞璨璩璐璧瓚璺韙韞韜杌杓杞杈榪櫪枇杪杳枘枧杵棖樅梟枋杷杼柰櫛柘櫳柩枰櫨柙枵柚枳柝梔柃枸柢櫟柁檉栲栳椏橈桎楨桄榿梃栝桕樺桁檜桀欒桊桉栩梵梏桴桷梓桫欞楮棼櫝槧棹欏棰椋槨楗棣椐楱椹楠楂楝欖楫榀榘楸椴槌櫬櫚槎櫸楦楣楹榛榧榻榫榭槔榱槁槊檳榕櫧榍槿檣槭樗樘橥槲橄樾檠橐橛樵檎櫓樽樨橘櫞檑檐檁檗檫猷獒歿殂殤殄殞殮殍殫殛殯殪軔軛轱軻轤軹軼軫轷轢軺軾輊輇輅輒輦輞輟輜輳轆轔軎戔戧戛戟戢戡戥戤戩臧甌瓴瓿甏甑甓攴旮旯旰昊曇杲昃昕昀炅曷昝昴昱昶昵耆晟曄晁晏暉晡晗晷暄暌曖暝暾曛曜曦曩賁貰貺貽贄貲賅贐賑賚賕赍賧賻覘覬覡覿覦覯覲覷牮犟牝牦牯牾牿犄犋犍犏犒挈挲掰搿擘耄毪毳毽毿毹氅氌氆氍氕氘氙氚氡氬氤氪氳攵敕敫牘牒牖爰虢刖肟肜肓肼朊肽肱肫肭肴肷朧胨胩臚胛胂胄胙胍胗朐胝脛胱胴胭膾脎胲胼朕脒豚腡脞脬脘脲腈腌腓腴腙腚腱腠腩靦膃腭腧塍媵膈膂臏滕膣膪臌朦臊膻臁膦歟欷欹歃歆歙颮颯颶颼飆飚殳彀轂觳斐齏斕於旆旄旃旌旎旒旖煬煒燉熗炻烀炷炫炱燁烊焐焓燜焯焱煳煜煨煅煲煊煸煺熘熳熵熨熠燠燔燧燹爝爨灬燾煦熹戾戽扃扈扉礻祀祆祉祛祜祓祚禰祗祠禎祧祺禪禊禚禧禳忑忐懟恝恚恧恁恙恣愨愆愍慝憩憝懋懣戇肀聿沓澩淼磯矸碭砉硨砘砑斫砭砜砝砹礪礱砟砼砥砬砣砩硎硭硤磽砦硐硇硌硪磧碓碚碇磣碡碣碲碹碥磔磙磉磬磲礅磴礓礤礞礴龕黹黻黼盱眄眍盹眇眈眚眢眙眭眥眵眸睞瞼睇脧睚睨睢睥睿瞍睽瞀瞌瞑瞟瞠瞰瞵瞽町畀畎畋畈畛畬畹疃罘罡罟詈罨羆罱罹羈罾盍盥蠲钅釓釔釙釗釕釷釧釤鍆釵釹钚鈦鉅鈑鈐鈁鈧鈄鈥鈀鈺鉦鈷鈳钷鈽鈸鉞鉬鉭鈿鑠鈰鉉鉈鉍鈮鈹鐸銬銠鉺銪鋮鋏鐃铘鐺铞銦鎧銖鋌銩鏵銓鉿鎩銚錚銫銃鐋銨銣鐒錸鋱鏗锃鋰鋯鋨銼鋝锍锎锏鋃鋟鋦錒錆锘錛锝錁錕錮锪锫錈錟錙鍥鍇鍶鍔鍤鎪鍰锿鏤鏘鐨镅鏌鎘鐫镎鎦鎰鎵鑌鏢鏜鏝鏍鏞鏃鏇鏑鐔镢鏷镥鐓鑭鐠镩鏹鐙鑊鐲鐿镲鑣鍾矧矬雉秕秭秣秫稆嵇稃稂稞稔稹稷穡黏馥穰皈皎皓皙皤瓞瓠甬鳩鳶鴇鴆鴣鶇鸕鴝鴟鷥鴯鷙鴰鵂鸞鵓鸝鵠鵒鷴鵜鵡鹋鵪鵯鶉鶘鶚鶿鹛鶩鷂鶼鸚鷓鷚鷯鷦鷲鷸鹱鷺鸛疒疔癤癘疝疬疣疳疴疸痄皰疰痃痂痖痍痣癆痦痤癇痧瘃痱痼痿瘐瘀癉瘌瘞瘊瘥瘺瘕瘙瘛瘼瘢瘠癀瘭瘰癭瘵癃癮瘳癍癩癔癜癖癲癯翊竦穸穹窀窆窈窕竇窠窬窨窶窳衤衩衲衽衿袂袢襠袷袼裉褳裎襝裥裱褚裼裨裾裰褡褙褓褸褊襤褫褶襁襦襻疋胥皸皴矜耒耔耖耜耠耢耥耦耬耩耨耱耋耵聃聆聹聒聵聱覃頇頎頏頡頜潁頦頷顎顓顳顢顙顥颥顰虍虔虬蟣蠆虺虼虻蚨蚍蚋蜆蠔蚧蚣蚪蚓蚩蚶蛄蚵蠣蚰蚺蚱蚯蛉蟶蚴蛩蛺蟯蛭螄蛐蜓蛞蠐蛟蛘蛑蜃蜇蛸蜈蜊蜍蜉蜣蜻蜞蜥蜮蜚蜾蟈蜴蜱蜩蜷蜿螂蜢蝽蠑蝻蝠蝰蝌蝮螋蝓蝣螻蝤蝙蝥螓螯螨蟒蟆螈螅螭螗螃螫蟥螬螵螳蟋蟓螽蟑蟀蟊蟛蟪蟠蟮蠖蠓蟾蠊蠛蠡蠹蠼缶罌罄罅舐竺竽笈篤笄筧笊笫笏筇笸笪笙笮笱笠笥笤笳籩笞筘篳筅筵筌箏筠筮筻筢筲筱箐簀篋箸箬箝籜箅簞箜箢簫箴簣篁篌篝篚篥篦篪簌篾篼簏籪簋簟簪簦簸籟籀臾舁舂舄臬衄舡舢艤舭舯舨舫舸艫舳舴舾艄艉艋艏艚艟艨衾裊袈裘裟襞羝羥羧羯羰羲秈敉粑糲糶粞粢粲粼粽糝糇糌糍糈糅糗糨艮暨羿翎翕翥翡翦翩翮翳糸縶綦綮繇纛麩麴赳趄趔趑趲赧赭豇豉酊酐酎酏酤酢酡酰酩酯釅釃酲酴酹醌醅醐醍醑醢醣醪醭醮醯醵醴醺豕鹺躉跫踅蹙蹩趵趿趼趺蹌跖跗跚躒跎跏跛跆跬蹺蹕跣躚躋跤踉跽踔踝踟躓踮踣躑踺蹀踹踵踽踱蹉蹁蹂躡蹣蹊躕蹶蹼蹯蹴躅躪躔躐躦躞豸貂貊貅貘貔斛觖觴觚觜觥觫觶訾謦靚雩靂雯霆霽霈霏霎霪靄霰霾齔齟齙齠齜齦齬齪齷黽黿鼉隹隼雋雎雒瞿讎銎鑾鋈鏨鍪鏊鎏鐾鑫魷魴鲅鲆鲇鱸穌鮒鱟鮐鮭鮚鮪鮞鱭鮫鲞鱘鯁鱺鰱鰹鰣鰷鯀鯊鯇鯽鯖鯪鯫鯡鯤鯧鲴鯢鯰鯛鲺鯔鲼鰈鱷鰍鰒鰉鳊鳋鰲鰭鰨鰥鰩鰳鰾鱈鰻鳘鳙鱖鱔鱒鱧靼鞅韃鞒鞔韉鞫鞣鞲鞴骱骰骷鶻骶骺骼髁髀髏髂髖髕髑魅魃魘魎魈魍魑饗饜餮饕饔髟髡髦髯髫髻髭髹鬈鬏鬢鬟鬣麼麾縻麂麇麈麋麒鏖麝麟黛黜黝黠黟黢黷黧黥黲黯鼢鼬鼯鼴鼷鼽鼾齄
posted @
2015-02-25 11:16 胡滿超 閱讀(2798) |
評論 (0) |
編輯 收藏
軟件架構(gòu)設(shè)計要關(guān)注哪些要點,我一直在思考這個問題?人類有計劃的做事必有其強列的目的性,軟件開發(fā)活動也不例外。軟件不可能由一個人完成,所以軟件的設(shè)計要分層,分模塊,便于人員分工,專業(yè)的人做專業(yè)的事情。軟件的開發(fā)需要傳承,鐵打的營盤流水的兵,簡單的設(shè)計是優(yōu)秀軟件的共性,用普通人就能理解的設(shè)計原則可以便于理念的傳承。為了傳承,文檔也很重要。文檔是時間流逝中最不容易產(chǎn)生二義性的媒介,好的文檔使經(jīng)驗更好傳播;另外文檔化的工作之于設(shè)計階段,有利于思考的升華和快速成熟,比如將所懂一門知識寫成一本書,仍然需要很多總結(jié)和提升的工作。軟件的發(fā)布需要測試,靠人工驅(qū)動效率太低,那么靠數(shù)據(jù)驅(qū)動的自動化測試能夠大大提高測試的效率。軟件的成果需要市場化,遇到問題要進(jìn)行反饋和解決,日志的設(shè)計很重要。當(dāng)工程師一下子面對幾M甚至幾十M的數(shù)據(jù)時,很難快速理出頭緒。如果通過查看最后幾行,就能明晰程序的動向,那程序的后期質(zhì)量進(jìn)步將變得很順暢。軟件的功能會發(fā)展,合理的抽象才能有效的應(yīng)對變化,當(dāng)我們可以預(yù)料到未來的變化,我們可以通過抽象接口的技術(shù)手段提前應(yīng)對。這樣版本在不斷演進(jìn)中,路不會越走越難。綜上所述,好的軟件設(shè)計需有具備以下特征:1、分層,分模塊2、簡單3、有文檔4、數(shù)據(jù)驅(qū)動5、適量日志6、合理的抽象
posted @
2014-08-28 22:48 胡滿超 閱讀(686) |
評論 (0) |
編輯 收藏
出現(xiàn)這個問題主要是調(diào)用的問題,沒有加入包
./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 胡滿超 閱讀(7519) |
評論 (0) |
編輯 收藏
轉(zhuǎn)自:http://www.shnenglu.com/changshoumeng/archive/2014/05/09/206871.html
posted @
2014-05-19 17:06 胡滿超 閱讀(601) |
評論 (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 胡滿超 閱讀(551) |
評論 (0) |
編輯 收藏
轉(zhuǎn)自:http://blog.163.com/javy1225@126/blog/static/459230342009230115919910/
一.CTime轉(zhuǎn)化為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轉(zhuǎn)化為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()函數(shù)的優(yōu)勢.
posted @
2014-05-13 16:05 胡滿超 閱讀(822) |
評論 (2) |
編輯 收藏
轉(zhuǎn)自:http://blog.codinglabs.org/artic ... -easy.html#jtss-tqq
周末花時間看了一些比特幣原理相關(guān)的資料,雖然不敢說把每個細(xì)節(jié)都完全搞懂了,不過整體思路和關(guān)鍵部分的主要原理還是比較明白。寫一篇文章分享給大家。這篇文章的定位會比較科普,盡量用類比的方法將比特幣的基本原理講出來。這篇文章不會涉及算法和協(xié)議中比較細(xì)節(jié)的部分,打算后面會再寫一篇程序員視角下的比特幣原理,那里會從技術(shù)人員的視角對比特幣系統(tǒng)中較為關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)、算法和協(xié)議進(jìn)行一些講解。
在這篇文章中我會給出一個虛擬的村莊叫“比特村”,整個文章會以講故事的方式,逐步告訴大家比特幣提出的動機、解決了什么問題以及一些關(guān)鍵組件的目標(biāo)和設(shè)計方案。
問題的提出我們先從比特幣產(chǎn)生的動機開始。
以物易物的比特村
話說在這個世界上,有一個叫比特村的小村莊,村莊共有幾百戶人家。這個村莊幾乎與世隔絕,過著自給自足的生活。由于沒有大規(guī)模貿(mào)易,比特村村民一直過著以物易物的生活,也就是說村民之間并沒有使用統(tǒng)一的貨幣,互相間的貿(mào)易基本上就是老張家拿一袋面粉換老李家一只羊,王大嫂拿一筐野果換劉大嬸兩尺布。村民們一直就這么純樸的生活著。

實物貨幣
終于有一天,村民覺得一直這樣以物易物實在太不方便了,于是村子全員開會,討論如何解決這個問題。有人提議,以便于分割且稀有的東西,例如黃金,作為一般等價物,把其它物品和黃金的對應(yīng)關(guān)系編成一張表格,例如一克黃金對應(yīng)一只羊,一克黃金對應(yīng)一袋面粉等等,此時老張再也不用扛著一袋面粉氣喘吁吁的去老李家換羊了,他只要從家里摸出一克金子,就可以去老李家牽回一只羊,而老李拿著這一克黃金可以從任何愿意出讓面粉的人那里換回一袋面粉,當(dāng)然也可以換取任何和一克黃金等值的物品。
此時比特村進(jìn)入了實物貨幣時代。

符號貨幣
好景不長,過了一段時間,實物貨幣的弊端也出現(xiàn)了。因為比特村附近金礦并不多,開采和冶煉金子太費時費力了。而隨著使用,金子總是不斷會因為磨損、丟失或有人故意囤積而發(fā)生損耗。全村人又一次坐在了一起,開始商討對策。此時有人說,其實大家也不必一定要真的用黃金啊,隨便找張紙,寫上“一克黃金”,只要全村人都認(rèn)同這張紙就等于一克黃金,問題不就解決了。其他人紛紛表示認(rèn)同,但同時也有了新的問題:真實的黃金是需要開采和冶煉的,金礦有限,開采和冶煉也需要成本,所以沒有人可以短期憑空制造大量的黃金,可寫字就不同了,只要我紙夠筆夠,隨便像寫多少寫多少,那這就變成拼誰家里紙多了,搞不好到時一萬張紙才能換一只羊(實際上這就發(fā)生了經(jīng)濟學(xué)上的通貨膨脹)。
大家一想也是啊。不過此時又有人提出了解決方案:這個紙不是誰寫都有效,我們只認(rèn)村里德高望重的老村長寫得,大家都認(rèn)識老村長的字。老村長寫一些紙,同時按照各家黃金存量發(fā)給大家等量的紙,例如老張家有二百克黃金,老村長就發(fā)給老張二百張寫著“一克黃金”的紙,同時將老張家的黃金拿走作為抵押。就這樣,老村長將村里所有黃金收歸到自己的家里,并按各家上交的黃金數(shù)量發(fā)給等值的寫有字的紙。此時村民就可以拿著這些紙當(dāng)黃金進(jìn)行貿(mào)易了,而且大家都認(rèn)得老村長的字,其他人偽造不出來。另外,如果誰的紙磨損太嚴(yán)重,也可拿到老村長那里兌換新的等值的紙,另外老村長承諾任何人如果想要換成真黃金,只要拿紙回來,老村長就會把等值的黃金還給那人。因為老村長寫得紙的黃金量和真實放在家里的黃金量是一樣的,所以只要嚴(yán)格按照銷毀多少紙新寫多少紙的原則,每一張有效的紙總能換回相應(yīng)的真黃金。
此時,比特村進(jìn)入了符號貨幣(紙幣)時代。而老村長就承擔(dān)了政府和銀行的角色。

中央系統(tǒng)虛擬貨幣
又過了幾年,老村長由于每天都要核對大量的舊紙幣,寫新的紙幣,還要把各種賬目仔細(xì)做好記錄。一來二去,老村長操勞過度不幸駕鶴西去了。
比特村再次召開全體大會,討論應(yīng)該怎么辦。此時老村長的兒子二狗子自告奮勇接過了父親的筆,承擔(dān)起貨幣發(fā)行的責(zé)任。這個年輕的村長二狗子很聰明,他做了幾天,發(fā)現(xiàn)好像也不用真的寫那么多紙。完全可以這樣:村民把紙幣都交上來,銷毀,但是二狗子會記錄下每戶上交的紙幣數(shù)量。以后如果要進(jìn)行付錢,例如老張要拿一克金子向老李換一只羊,就一起給二狗子打個電話,說明要將老張名下的一克金子劃歸老李名下,二狗子拿出賬本,看看老張名下是否有一克金子,如果有就在老張的名下減掉一克,在老李的名下加上一克,這樣就完成了支付,此時老李在電話中聽到二狗子確認(rèn)轉(zhuǎn)賬完成,就可以放心讓老張把羊牽走了。
此時比特村進(jìn)入了中央系統(tǒng)虛擬貨幣時代。每個村民都不需要用實物支付,支付過程變成了二狗子那邊維護的賬本上數(shù)字的變更。

分布式虛擬貨幣
這新上任的二狗子是聰明,不過這人有時候是聰明反被聰明誤。有一天二狗子盯著這賬本,心想這全村各戶誰有多少錢就是我說的算,那我豈不是……。于是他頭腦一熱,私自從老張帳下劃了十克金子到自己名下。
本以為天衣無縫,但沒想到老張也有記賬的習(xí)慣,有一天他正要付錢卻被二狗子告知賬戶沒錢了。老張核對了一下自己的賬本,明明還有十克啊,于是拿著賬本去找二狗子理論,這一核對發(fā)現(xiàn)了那筆未經(jīng)老張同意的轉(zhuǎn)賬。
東窗事發(fā)!比特村炸開鍋了。二狗子被彈劾是不可避免了,不過通過這件事,大家發(fā)現(xiàn)了賬本集中在一個人手里的弊端:
- 這個體系完全依賴于賬本持有人的個人信用,如果這個人不守規(guī)矩,隨意篡改賬本,那么整個貨幣系統(tǒng)就會崩潰
- 如果這個人家里失火或者賬本失竊,同樣也會為整個體系帶來毀滅性的打擊
正當(dāng)人們不知所措時,村里一個叫中本聰?shù)恼锌茖W(xué)家走上了臺,告訴大家他已經(jīng)設(shè)計了一套不依賴任何中央處理人的叫比特幣的虛擬貨幣系統(tǒng),可以解決上述問題。然后他緩緩講述了自己的方案。
下面我們就來看看中本聰同學(xué)是如何設(shè)計這套系統(tǒng)的。
基礎(chǔ)設(shè)施搭建賬簿公開機制
中本聰首先說明,要對現(xiàn)有賬簿進(jìn)行如下改造:
- 賬簿上不再記載每戶村民的余額,而只記載每一筆交易。即記載每一筆交易的付款人、收款人和付款金額。只要賬簿的初始狀態(tài)確定,每一筆交易記錄可靠并有時序,當(dāng)前每個人持有多少錢是可以推算出來的。
- 賬簿由私有改為公開,只要任何村民需要,都可以獲得當(dāng)前完整的賬簿,賬簿上記錄了從賬簿創(chuàng)建開始到當(dāng)前所有的交易記錄。
此言一出,下面立刻炸鍋了。第一條還無所謂,但是第二條簡直無法接受,因為賬簿可是記錄了所有村民的交易,這樣大家的隱私不全暴露了嗎。
中本聰?shù)故遣换挪幻Γ贸隽艘粚ζ婀值臇|西。
身份與簽名機制(公鑰加密系統(tǒng))
中本聰說,大家不要慌。在他的這套機制下,任何人都不使用真實身份交易,而是使用一個唯一的代號交易。
他展示了手里神奇的東西,說這兩件東西分別叫保密印章和印章掃描器。后面他會給村里每一戶發(fā)一個保密印章和一個印章掃描器。兩者的作用如下:
- 保密印章可以在紙上蓋一個章,每個印章蓋出的章都隱含了一個全村唯一的一串字符,但是憑肉眼是看不出來的。也無法通過觀察來制造出相應(yīng)的印章。
- 印章掃描器可以掃描某個已經(jīng)蓋好的章,讀出隱含的信息,并在液晶屏上顯示出一串字符。
有了這兩個神奇的東西,大家就可以在不暴露真實身份的情況下進(jìn)行交易了,而印章隱含的那一串字符就是這戶人家的代號。具體如何巧妙利用保密印章和印章掃描器進(jìn)行交易,會在下文詳述。
成立虛擬礦工組織(挖礦群體)
下一步,中本聰面向全村招募虛擬礦工,招募要求如下:
- 礦工以組為單位,一組可以是單獨的一戶,也可以是幾戶聯(lián)合為一組
- 成為礦工不影響正常使用貨幣
- 礦工每天要花費一定時間從事比特幣“挖礦”活動,但是不同于挖金礦,虛擬礦工不需要拿著工具去野外作業(yè),在家里就可以完成工作
- 礦工有一定可能性獲得報酬,在挖礦活動中付出的努力越多,獲得報酬的可能性越大
- 礦工可以隨時退出,也可以隨時有新的礦工加進(jìn)來
很快,大約有五分之一的村民加入比特幣礦工組織,共分成了7個組。
建立初始賬簿(創(chuàng)世塊)
下面,中本聰宣布,先根據(jù)二狗子手里的賬簿,把抵押的所有黃金按賬簿記錄的余額退還給每位村民,然后徹底銷毀這本賬簿。
然后,中本聰拿出一本新賬簿,在賬簿的第一頁上記錄了一些交易記錄,特別的是,這些記錄的付款人一欄全都是“系統(tǒng)”,而收款人分別是每個印章對應(yīng)的隱含字符,代表初始時刻,系統(tǒng)為每一戶默認(rèn)分配了一定數(shù)量比特幣,但是數(shù)量非常少,都只有幾枚,甚至有些不幸的村戶沒有獲得比特幣。
接著中本聰說,由于目前市面上比特幣非常少,大家可以先回到用黃金做貨幣的時代,由于我不是村長,我也沒有權(quán)利強迫大家一定要承認(rèn)比特幣,大家可以自行決定要不要接受比特幣。不過隨著比特幣的流動和礦工的活動,比特幣會慢慢多起來。
支付與交易做了這么多鋪墊,終于說到重點了,下面說一下在這樣一個體系下如何完成支付。以老張付給老李10個比特幣為例。
付款人簽署交易單
為了支付10個比特幣,老張首先要詢問老李的標(biāo)識字符串,例如是“ABCDEFG”,同時老張也有一個標(biāo)識字符串例如是“HIJKLMN”,然后老張寫一張單子,內(nèi)容為“HILKLMN支付10比特幣給ABCDEFG”,然后用自己的保密印章改一個章,將這張單子交給老李。另外為了便于追溯這筆錢的來源,還要在單子里注明這筆錢的來源記在哪一頁,例如這個單子里,老張的10比特幣來自建立賬簿時系統(tǒng)的贈送,記錄在賬簿第一頁。

收款人確認(rèn)單據(jù)簽署人
老李拿到這個單子后,需要確認(rèn)這個單子確實是來自“HIJKLMN”這個人(也就是老張)簽署的,這個并不困難。因為單子上必須有保密章,老李拿出印章掃描器,掃一下章,如果液晶屏顯示出的字符和付款人字符是一致的(這里是“HIJKLMN”),就可以確認(rèn)單子確實是付款人簽署的。這是因為根據(jù)保密印章的機制,沒有其他人可以偽造印章,任何一個人只要掃描一下印章,都可以確認(rèn)單子的付款人和蓋章人是否一致。
收款人確認(rèn)付款人余額
這個系統(tǒng)到目前還是很有問題。通過保密印章,收款人雖然可以確認(rèn)付款人確實簽署了這份單子,但是無法自行確認(rèn)付款人是否有足夠的余額支付。之前的中央虛擬貨幣系統(tǒng)中,二狗子負(fù)責(zé)檢查付款人的余額,并通知收款人交易是否有效,現(xiàn)在把二狗子開了,誰來負(fù)責(zé)記賬和確認(rèn)每筆交易的有效性呢?
之前說過,中本聰設(shè)計的這個系統(tǒng)是分布式貨幣系統(tǒng),不依賴任何中央人物,所以不會有一個或少數(shù)幾個人負(fù)責(zé)這件事,最終承擔(dān)這份工作的是之前所提到的礦工組織。老張、老李和全村其他任何使用比特幣進(jìn)行交易的村民都依賴礦工組織的工作才能完成交易。
礦工的工作
礦工的工作是整個系統(tǒng)的核心,也是最復(fù)雜性最高的地方。下面逐步介紹礦工的工作內(nèi)容和目的。
礦工的工具
俗話說,工欲善其事,必先利其器。比特幣礦工雖然不用鐵撅、鐵锨和探照燈等工具,不過也要有一些必備的東西。
初始賬簿。每個組首先自己復(fù)制一份初始賬簿,初始賬簿只有一頁,記錄了系統(tǒng)的第一次贈送
空賬簿紙。每個小組有若干賬簿紙,每一頁紙上僅有賬簿結(jié)構(gòu),沒有填內(nèi)容,具體內(nèi)容的書寫規(guī)則后面講述。下面是一張空賬簿紙的樣子,各個字段的意義后面會說到

編碼生成器(哈希函數(shù))。中本聰又向礦工組織的每個組分發(fā)了若干編碼生成器,這個東西很神奇,將一頁賬簿填好內(nèi)容的賬簿紙放入這個機器,機器會在賬簿紙的“本賬單編號”一欄自動打印一串由“0”和“1”組成的編號,共256個。最神奇的是,編號生成器有如下功能:
- 生成的編號僅與賬簿紙上填入的內(nèi)容有關(guān),與填寫人、字體、填寫時間等因素均無關(guān)
- 內(nèi)容相同的賬簿紙生成的編號總是相同,但是如果內(nèi)容哪怕只改一個字符,編號就會面目全非
- 編碼生成器在打印編碼時還需要將所有填入賬簿紙的交易單放入,機器會掃描交易單和填入交易單的一致性,尤其是保密印章,如果發(fā)現(xiàn)保密印章和付款人不一致,會拒絕打印編碼
- 將一張已打印的賬簿紙放入,機器會判定編號是否是有效的機器打印,并且判定編號和內(nèi)容是否一致,這個編號無法偽造
- 交易單收件箱。每個礦工小組需要在門口掛一個箱子用于收集交易單。
- 公告板。每個礦工小組同樣需要一個公告板公示一些信息。
有了上面的工具,礦工組織就可以開工了!
收集交易單
中本聰規(guī)定,每筆交易的發(fā)起人,不但要將交易單給到收款人,還要同時復(fù)制若干份一模一樣的交易單投遞到每個礦工小組的收件箱里。
礦工小組的人定期到自己的收件箱里把收集到的交易單一并取出來。
填寫賬簿
此時小組的人拿出一張空的賬簿紙,把這些交易填寫到“交易清單”一欄,同時找到當(dāng)前賬簿最后一頁,將最后一頁的編號抄寫到“上一張賬單編號一欄”。注意還有個“幸運數(shù)字”,可以隨便填上一個數(shù)字,如12345。然后,將這樣賬簿紙放入編號生成器,打印好編號,一張賬簿就算完成了。
如果你以為礦工的工作就這么簡單,那就大錯特錯了,中本聰有個變態(tài)的規(guī)定:只有編號的前10個數(shù)均為0,這頁賬簿紙才算有效。
根據(jù)之前對編號生成器的描述,要修改編號,只能修改賬簿紙的內(nèi)容,而“交易清單”和“上一張賬簿紙編號”是不能隨便改的,那么只能改幸運數(shù)字了。于是為了生成有效的賬簿紙,小組里的礦工就不斷抄寫賬簿紙,但每張紙的幸運數(shù)字都不同,然后不斷的重復(fù)將紙放入編碼器,如果生成的編號不符合規(guī)定,這張紙就算廢了,重復(fù)這個過程直到生成一串有效的編號。
我們知道,如果編號的每一個數(shù)字都是隨機的,那么平均寫1000多張幸運數(shù)字不同的紙才能獲得一個有效的編號。
這就奇怪了,這些礦工為什么要拼命干這看似無意義的事情呢?還記得之前說過礦工有報酬吧,這就是礦工的動力了。中本聰規(guī)定:每一張賬簿紙的交易清單第一條交易為“系統(tǒng)給這個小組支付50個比特幣”。也就是說,如果你生成了一張有意義的賬簿紙,并且被所有挖礦小組接受了,那么就意味著這條交易也被接受了,你的挖礦小組獲得了50個比特幣。
這就是礦工被叫做礦工的原因,也是為什么之前說隨著交易和礦工的活動,比特幣的數(shù)量會不斷增多。例如下面是一個挖礦過程,這個小組的公共比特幣帳號為“UVWXYZ”。

在幸運數(shù)字嘗試到“533”時,系統(tǒng)生成了一頁有效賬簿。
確認(rèn)賬簿
當(dāng)某挖礦小組幸運的生成了一張有意義的賬簿,為了得到獎勵,必須立刻請其它小組確認(rèn)自己的工作。前面說過,當(dāng)前村里有7個挖礦組,所以這個小組必須將有效賬簿紙謄抄6份快馬加鞭送到其他6個小組請求確認(rèn)。
中本聰規(guī)定,當(dāng)某個小組接到其他小組送來的賬簿紙時,必須立即停下手里的挖礦工作進(jìn)行賬簿確認(rèn)。
需要確認(rèn)的信息有三個:
- 賬簿的編號有效
- 賬簿的前一頁賬簿有效
- 交易清單有效
首先看第一個,這個確認(rèn)比較簡單。只要將送來的賬簿紙放入編碼生成器進(jìn)行驗證,如果驗證通過,則編號有效。
第二部分需要將賬簿頁上的“上一頁賬簿紙編號”和這個小組目前保存的有效賬簿最后一頁編號比對,如果相同則確認(rèn),如果不同,需要順著已有賬簿向前比對,直到找到這個編號的頁。如果沒有找到指定的“上一頁賬簿紙編號”對應(yīng)的頁,這個小組會將此頁丟掉。不予確認(rèn)。
注意,由上面的機制可以保證,如果各個小組手里的賬簿紙是相同的,那么他們都能按同樣的順序裝訂成相同的賬簿。因為后面一張紙的編號總是依賴前面的紙的編號,編碼生成器的機制保證了所有合法賬簿紙的相對先后順序在每個小組那里都是相同的(可能會有分支,但不會出現(xiàn)環(huán),后面細(xì)講)。

最后是如何確認(rèn)交易清單有效,其實也就是要確認(rèn)當(dāng)前每筆交易的付款人有足夠的余額支付這筆錢。由于交易信息里包含這筆錢是如何來的,還包含了記錄來源交易的賬單編號。例如,HIJKLMN要給ABCDEFG10個比特幣,并注明了這10個比特幣來自之前OPQRST支付給HIJKLMN的一筆交易,確認(rèn)時首先要確認(rèn)之前這筆交易是否存在,同時還要檢查HIJKLMN在這之前沒有將這10個比特幣支付給別人。這一切確認(rèn)后,這筆交易有效性就被確認(rèn)了。
其中第一筆是系統(tǒng)獎勵給生成這頁賬簿的小組的50個,這筆交易大家都默認(rèn)承認(rèn),后面的只要按照上述方法追溯,就可以確認(rèn)HIJKLMN是否當(dāng)前真有10個比特幣支付給ABCDEFG。
如果完成了所有了上述驗證并全部通過,這個小組就認(rèn)可了上述賬簿紙有效,然后將這張賬簿紙并入小組的主賬簿,舍棄目前正在進(jìn)行的工作,后面的挖礦工作會基于這本更新后的主賬本進(jìn)行。
賬簿確認(rèn)反饋
對于挖礦小組來說,當(dāng)賬簿紙送出去后,如果后面有收到其他小組送來的賬簿紙,其“上一頁賬簿紙編號”為自己之前送出去的賬簿紙,那么就表示他們的工作成功被其他小組認(rèn)可了,因為已經(jīng)有小組基于他們的賬簿紙繼續(xù)工作了。此時,可以粗略的說可以認(rèn)為已經(jīng)得到了50個比特幣。
另外,任何一個小組當(dāng)新生成有效賬簿紙或確認(rèn)了別的小組的賬簿紙時,就將最新被這個小組承認(rèn)的交易寫到公告牌上,那么收款人只要發(fā)現(xiàn)相關(guān)交易被各個小組認(rèn)可了,基本就可以認(rèn)為這筆錢已經(jīng)到了自己的賬上,后面他就可以在付款時將錢的來源指向這筆交易了。
以上就是整個比特幣的支付體系。下面我們來分析一下,這個體系為什么可以工作下去,以及這個體系可能面臨的風(fēng)險。
工作機制分析雖然上面闡述了比特幣的基本運作規(guī)則,但是村民們還是有不少疑問。所以中本聰同學(xué)專門開了個答疑會,解答常見問題。下面總結(jié)一下村民最集中關(guān)心的問題。
核心問題答疑
如果同時收到兩份合法的賬簿頁怎么辦?
注意在上面的運行機制中,各個挖礦小組是并行工作的,因此完全可能出現(xiàn)這樣的情況:某小組收到兩份不一樣的賬簿頁,它們都基于當(dāng)前這個小組的主賬簿的最后一頁,并且內(nèi)容也都完全合法,怎么辦?
關(guān)于這個問題,中本聰同學(xué)說,小組不應(yīng)該以線性方式組織賬簿,而應(yīng)該以樹狀組織賬簿,任何時刻,都以當(dāng)前最長分支作為主賬簿,但是保留其它分支。舉個例子,某小組同時收到A、B兩份賬簿頁,經(jīng)核算都是合法的,此時小組應(yīng)該將兩頁以分叉的形式組織起來,如下圖所示:

黑色表示當(dāng)前賬簿主干。此時,可以隨便選擇一個頁作為當(dāng)前主分支,例如選擇A:

此時如果有一個新的賬簿頁是基于A的,那么這個主干就延續(xù)下去:

如果這個主干一直這么延續(xù)下去,表示大家基本都以A為主干,B就會被遺忘。但是也有可能忽然B變成更長了:

那么我們就需要將B分支作為當(dāng)前主干,基于這個分支進(jìn)行后續(xù)工作。

從局部來看,雖然在某一時刻各個小組的賬簿主干可能存在不一致,但大方向是一致的,那些偶爾由于不同步產(chǎn)生的小分支,會很快被淹沒在歷史中。
如果挖礦小組有人偽造賬簿怎么辦
關(guān)于這個問題,中本聰同學(xué)說,只要挖礦組織中大多數(shù)人是誠實的,這個系統(tǒng)就可靠,具體分幾個方面給予答復(fù)。
首先,基于保密印章機制,沒有人能偽造他人身份進(jìn)行付款,因為編碼生成器在打印編碼時會核對所有交易單的保密印章,印章和付款人不一致會拒絕打印。
而且誠實的礦工也不會承認(rèn)不合法的交易(如某筆交易付款方余額不夠)。
所以只有一種可能的攻擊行為,即在收款人確認(rèn)收款后,從另一條分支上建立另外的交易單,取消之前的付款,而將同一筆錢再次付款給另一個人(即所謂的double-spending問題)。下面同樣用一個例子說明這個問題。
先假設(shè)有一個攻擊者擁有10個比特幣,他準(zhǔn)備將這筆錢同時支付給兩名受害者A和B,并都得到承認(rèn)。
第一步,攻擊者準(zhǔn)備從受害者A手里買10比特幣的黃金,他簽署交易單給受害者A,轉(zhuǎn)10個比特幣給受害者A。

第二步,這筆交易在最新的賬簿頁中被確認(rèn),并被各個挖礦小組公告出來。受害人A看到公告,確認(rèn)比特幣到賬,給了攻擊者10個比特幣等值的黃金。

第三步,攻擊者找到賬簿,從包含剛才交易的賬簿頁的前一頁做出一個分支,生成更多的賬單頁,超過剛才的分支。由于此時剛才攻擊者制造的分支變成了主干分支,而包含受害者A得到錢的分支變成了旁支,因此挖礦組織不再承認(rèn)剛才的轉(zhuǎn)賬,受害者A得到的10比特幣被取消了。

第四步,攻擊者可以再次簽署交易單,將同一筆錢支付給受害者B。受害者B確認(rèn)錢到賬后,支付給攻擊者等值黃金。

至此,攻擊者將10個比特幣花了兩次,從兩名受害者那里各購得等值黃金。攻擊者還可以如法炮制,取消與受害者B的轉(zhuǎn)賬,將同一筆錢再支付給其他人……
關(guān)于這種攻擊,中本聰給出的解決方案是,建議收款人不要在公告掛出時立即確認(rèn)交易完成,而是應(yīng)該再看一段時間,等待各個挖礦小組再掛出6張確認(rèn)賬簿,并且之前的賬簿沒有被取消,才確認(rèn)錢已到賬。
中本聰解釋道,之前設(shè)定變態(tài)的編號規(guī)則,正是為了防御這一點。根據(jù)前面所述,生成有效賬簿頁不是那么簡單的,要花費大量的人力反復(fù)試不同的幸運數(shù)字,而且過程完全是碰運氣。如果某賬簿頁包含你收到錢的確認(rèn),并且在后面又延續(xù)了6個,那么攻擊者想要在落后6頁的情況下從另一個分支趕超當(dāng)前主分支是非常困難的,除非攻擊者擁有非常多的人力,超過其他所有誠實礦工的人力之和。
而且,如果攻擊者有如此多人力,與其花這么大力氣搞這種攻擊,還不如做良民挖礦來的收益大。這就從動機上杜絕了攻擊的形成。
比特幣會一直增加下去,豈不是會嚴(yán)重通貨膨脹
中本聰說,這一點我也想到了。前面忘了說了,我給礦工組織的操作細(xì)則手冊會說明,剛開始我們協(xié)議每生成一頁賬簿,獎勵小組50個比特幣,后面,每當(dāng)賬簿增加21,000頁,獎勵就減半,例如當(dāng)達(dá)到210,000頁后,每生成一頁賬簿獎勵25個比特幣,420,000頁后,每生成一頁獎勵12.5個,依次類推,等賬簿達(dá)到6,930,000頁后,新生成賬簿頁就沒有獎勵了。此時比特幣全量約為21,000,000個,這就是比特幣的總量,所以不會無限增加下去。
沒有獎勵后,就沒人做礦工了,豈不是沒人幫忙確認(rèn)交易了
到時,礦工的收益會由挖礦所得變?yōu)槭杖∈掷m(xù)費。例如,你在轉(zhuǎn)賬時可以指定其中1%作為手續(xù)費支付給生成賬簿頁的小組,各個小組會挑選手續(xù)費高的交易單優(yōu)先確認(rèn)。
礦工如果越來越多,比特幣生成速度會變快嗎
不會。中本聰解釋,雖然可以任意加入和退出礦工組織,導(dǎo)致礦工人數(shù)變化,每個礦工也會拿到一個編碼生成器,不過我已經(jīng)在編碼生成器中加入了調(diào)控機制,當(dāng)前工作的編碼生成器越多,每個機器的效率就越低,保證新賬簿頁生成速率不變。
雖然每個人的代號是匿名的,但如果泄露了某個人的代號,賬簿又是公開的,豈不是他的所有賬目都查出來了
確實是這樣的。例如你要和某人交易,必然要要到他的代號才能填寫交易單。因為收款人一欄要填入那人的代號。不過中本聰說可以提供無限制的保密印章,建議每一次交易用不同的保密印章,這樣查賬簿就追查不到同一個人的所有賬目了。
答疑完畢。
說明本文用通俗比喻的方式講解了比特幣的運行機制。有幾點需要說明:
- 為了便于理解,我做了很多簡化,因此有些機制細(xì)節(jié)和實際的比特幣可能不完全相同。但總體思想和關(guān)鍵原理是一致的。
- 由于很多計算機世界的東西(如公鑰體系、網(wǎng)絡(luò)傳輸)在現(xiàn)實世界中并沒有特別好的對等物,所以故事里難免有一些生硬和不合常理的細(xì)節(jié)。
- 本文描述的是比特幣網(wǎng)絡(luò)本身的技術(shù)原理和運作機制,當(dāng)在如Mtgox這種買賣市場中進(jìn)行比特幣交易時,市場做了中間代理,并不遵從上述機制
參考- Bitcoin: A Peer-to-Peer Electronic Cash System
- https://bitcoin.it
- 云風(fēng)的BLOG: Bitcoin 的基本原理
- 易懂的比特幣工作機理詳解
posted @
2014-02-13 10:36 胡滿超 閱讀(503) |
評論 (0) |
編輯 收藏
搜索引擎在查找時主要考慮兩方面因素:網(wǎng)頁和查詢的相關(guān)性、網(wǎng)頁的重要性
鏈接分析解決網(wǎng)頁重要性的問題
網(wǎng)頁中最重要的三個要素,出鏈(Out Link),入鏈(In Links),錨文字
鏈接分析算法
1、隨機游走模型:對直接跳轉(zhuǎn)和遠(yuǎn)程跳轉(zhuǎn)兩種用戶瀏覽行為進(jìn)行抽象的概念模型,用戶從當(dāng)前網(wǎng)頁到達(dá)某網(wǎng)頁的概率
2、子集傳播模型:把網(wǎng)頁劃分為若干子集,給予子集內(nèi)網(wǎng)頁初始權(quán)值,根據(jù)鏈接關(guān)系,按照一定方式將權(quán)值傳遞到其他網(wǎng)頁
不同子集傳播模型在如下方面存在差異:
1)如何定義特殊子集合
2)在確定了特殊子集合所具有的性質(zhì)后,如果對子集內(nèi)的網(wǎng)頁賦初始值
3)從特殊子集合將其分值傳播到其他網(wǎng)頁時,采取何種傳播方式
PageRank算法
除了考慮到入鏈數(shù)量的影響,還參考了網(wǎng)頁質(zhì)量因素
數(shù)量假設(shè):在Web圖模型中,如果一個頁面節(jié)點接收到的其他網(wǎng)頁指向的入鏈數(shù)量越多,那么這個頁面越重要
質(zhì)量假設(shè):質(zhì)量高的頁面會通過鏈接向其他頁面?zhèn)鬟f更多的權(quán)重
算法開始賦予每個網(wǎng)頁相同的重要性得分,通過迭代遞歸計算來更新每個頁面節(jié)點的PageRank得分,直到穩(wěn)定為止
遠(yuǎn)程跳轉(zhuǎn):解決鏈接陷阱的通用方式,在網(wǎng)頁向外傳遞分值時,不限于向出鏈所指網(wǎng)頁傳遞,也可以以一定的概率向任意其他網(wǎng)頁跳轉(zhuǎn)(虛擬邊,權(quán)值通過虛擬邊向外傳遞)
HITS(Hypertext Induced Topic Selection)算法
Authority頁面:某個領(lǐng)域或者某個話題相關(guān)的高質(zhì)量網(wǎng)頁
Hub頁面:指向很多Authority頁面
基本假設(shè)1:一個好的Authority頁面會被很多好的Hub頁面指向
基本假設(shè)2:一個好的Hub頁面會向向很好的Authority頁面
算法步驟:
1、將查詢提交給某個現(xiàn)有的搜索引擎,或檢索系統(tǒng),提取排名靠前的結(jié)果(根集)
2、在根集的基礎(chǔ)上,對其擴充(凡是與根集內(nèi)網(wǎng)頁有直接鏈接指向關(guān)系的網(wǎng)頁都被擴充進(jìn)來)
3、在根集+擴充網(wǎng)頁,尋找好的Hub頁面與好的Authority頁面
4、初始情況下,在沒有更多可利用信息前,把所有頁面兩個權(quán)值都設(shè)置為1
5、以相互增強的關(guān)系等原則進(jìn)行多輪迭代計算,每輪迭代計算更新每個頁面的兩個權(quán)值,直到權(quán)值穩(wěn)定為止
HITS算法不僅在搜索引擎領(lǐng)域應(yīng)用,在自然語言處理,社交分析也有較好的效果
HITS算法的不足:計算效率較低、主題漂移,易被作弊者操縱結(jié)果,結(jié)果不穩(wěn)定(添加刪除個別網(wǎng)頁或者改變少數(shù)鏈接關(guān)系,對排名影響會很大)
HITS算法與PageRank算法比較
1、HITS與用戶輸入查詢相關(guān),PageRank與查詢無關(guān)
2、HITS計算效率低,PageRank離線計算,在線直接使用計算結(jié)果,計算效率高
3、HITS為局部計算,適合在客戶端,PageRank為全局計算,適合步驟在服務(wù)器端
4、HITS適合處理具體用戶查詢,PageRank處理適合處理寬泛的用戶查詢
5、HITS算法在計算時,為每個頁面計算兩個分值,PageRank只需計算一個分值,在搜索引擎領(lǐng)域,更重要Authority權(quán)值,其他應(yīng)用領(lǐng)域Hub分值也很重要
6、從反作弊角度說,PageRank從機制上優(yōu)于HITS
7、PageRank比HITS計算過程更穩(wěn)定,原因是PageRank計算時的遠(yuǎn)程跳轉(zhuǎn)
SALSA算法
很多實驗數(shù)據(jù)表明,SALSA是目前最好的鏈接分析算法之一
計算流程分兩個階段:
1、確定計算對象集合,與HITS類似
1)擴展網(wǎng)頁集合,在收到用戶查詢后,利用現(xiàn)有搜索引擎或檢索系統(tǒng)獲取根集,并擴展
2)轉(zhuǎn)換為無向二分圖,一個子集合Hub集合,Authority集合
2、鏈接關(guān)系傳播過程,在這一階段采納了隨機游走模型
在權(quán)值傳播過程中,權(quán)值是被所有鏈接平均分配的
HITS模型關(guān)注的是Hub和Authority之間的節(jié)點相互增強關(guān)系
SALSA實際上關(guān)注的是Hub-Hub及Authority-Authority之間的節(jié)點關(guān)系
Authority集合內(nèi)從某個節(jié)點i轉(zhuǎn)移到另一個節(jié)點j的概率,i與j之間概率是不同的,非對稱
在二分圖中,對于Authority集合內(nèi)的某個節(jié)點來說,一定可以通過Hub子集合的節(jié)點中轉(zhuǎn)后再次返回本身
建立好Authority節(jié)點關(guān)系圖后,即可利用隨機游走模型來計算每個節(jié)點的Authority權(quán)值
SALSA將搜索結(jié)合排序問題進(jìn)一步轉(zhuǎn)換為求Authority節(jié)點矩陣的主秩問題,無需迭代,計算速度快
決定Authority權(quán)值的4個因子:
1)Authority子集合中包含的節(jié)點總數(shù)
2)網(wǎng)頁i所在連通圖中的節(jié)點個數(shù)
3)網(wǎng)頁i所在連通圖中包含的入鏈總數(shù)
4)網(wǎng)頁i的入鏈個數(shù)
SALSA算法的特點:
1、SALSA算法無需像HITS算法一樣迭代計算,計算速度快
2、解決了HITS主題漂移的問題,搜索質(zhì)量優(yōu)于HITS
主題敏感PageRank
該算法被Google使用在個性化搜索服務(wù)中,非常適合作為個性化搜索的技術(shù)方案
用戶會對某些領(lǐng)域感興趣,同時當(dāng)瀏覽某個頁面時,這個頁面也是與某個主題相關(guān),跳轉(zhuǎn)時,更傾向于點擊和當(dāng)前頁面主題類似的鏈接
主題敏感PageRank是將用戶興趣,頁面主題及鏈接所指向網(wǎng)頁與當(dāng)前網(wǎng)頁主題的相似程度綜合考慮而建立模型
該算法引入16種主題類型,對于某個網(wǎng)頁來說,對應(yīng)某個主題類型都有相應(yīng)的PageRank分值
主題敏感的PageRank與主題相關(guān),在接收到用戶查詢后,主題敏感PageRank還需要利用分類器,計算該查詢隸屬于事先定義好的16個主題的相似度,并在排序時利用此相似度信息
計算流程:
1、離線的分類主題PageRank數(shù)值計算,計算網(wǎng)頁對于16個分類的相似度
將網(wǎng)頁劃分為兩個集合,一個ODP對應(yīng)分類主題對應(yīng)的所有網(wǎng)頁S,剩下的網(wǎng)頁為另一個集合T
通過鏈接關(guān)系,從S向T傳遞權(quán)重,即計算網(wǎng)頁所屬類別的概率
2、在線利用算好的PageRank分值,來評估網(wǎng)頁和用戶查詢的相似度
通過計算查詢詞所屬類別的概率*網(wǎng)頁所屬類別的概率,得出兩者相關(guān)性的分值,進(jìn)行排序
HillTop算法
1、從海量的互聯(lián)網(wǎng)網(wǎng)頁中通過一定的規(guī)則選出專家頁面子集合,并單獨為其建立索引
2、接收用戶發(fā)出的查詢請求時,根據(jù)用戶查詢的主題,從專家頁面子集合中找出部分相關(guān)性最強的專家頁面,對每個專家頁面計算相關(guān)性得分
3、根據(jù)目標(biāo)頁面(從索引系統(tǒng)中中取到的頁面)和這些專家頁面的鏈接關(guān)系 對目標(biāo)頁面進(jìn)行排序
4、整合相關(guān)專家頁面和得分較高的目標(biāo)頁面作為搜索結(jié)果,返回給用戶
從屬組織頁面:主機IP地址的前3個網(wǎng)段相同,網(wǎng)站域名中的主域名相同
專家頁面
1、與某個主題相關(guān)的高質(zhì)量頁面
2、這些頁面的鏈接所指向的頁面相互之間是非從屬組織頁面
3、這些被指向的頁面大多數(shù)是與專家頁面主題相近
HillTop可以與某個排序算法相結(jié)合,不適合作為一個獨立的網(wǎng)頁排序算法來使用,因為當(dāng)無法得到一個足夠大的專家頁面時,會返回空結(jié)果。
步驟1:專家頁面搜索
從1億4千萬網(wǎng)頁中,篩選出250萬作為專家頁面,專家頁面特征:
1、頁面中至少包含K個出鏈,K可以人為指定
2、K個出鏈指向的所有頁面相互之間的關(guān)系,都符合非從屬組織頁面
對專家頁面單獨建索引,且只對關(guān)鍵字段(Key Phrase)進(jìn)行索引,關(guān)鍵字段包含3類信息:網(wǎng)頁標(biāo)題,H1標(biāo)簽內(nèi)文字和URL錨文字
關(guān)鍵字段有影響范圍(可以支配Qualify的鏈接),依次為,標(biāo)題->H1標(biāo)簽->URL錨文字
在計算網(wǎng)頁排序時,對查詢字段在不同的關(guān)鍵字段中,會使用不同的權(quán)值
系統(tǒng)接收到用戶查詢Q,將對專家頁面進(jìn)行打分,主要考慮以下3類信息:
1、關(guān)鍵字段包含了多少詞
2、關(guān)鍵片段本身的類型,即關(guān)鍵字段的類型
3、用戶查詢和關(guān)鍵詞的失配率,即關(guān)鍵字段中不屬于查詢的單詞個數(shù)占關(guān)鍵片段總單詞個數(shù)的比率
步驟2:目標(biāo)頁面排序
Hilltop算法包含的基本假設(shè):一個目標(biāo)頁面如果是滿足用戶查詢的高質(zhì)量搜索結(jié)果,其充分必要條件是該目標(biāo)頁面有高質(zhì)量專家頁面鏈接指向
為保證上述假設(shè)的成立,Hilltop算法在這個階段需要對專家頁面的出鏈仔細(xì)進(jìn)行甄別,以保證查詢時,選出那些和查詢密切相關(guān)的目標(biāo)頁面。
在進(jìn)行傳遞分值之前,首先需要對鏈接關(guān)系進(jìn)行整理,能夠獲得專家頁面分值的目標(biāo)頁面需要滿足以下兩點要求:
條件1、至少需要兩個專家頁面有鏈接指向目標(biāo)頁面,且兩個專家頁面不能是從屬組織頁面
能夠獲得傳遞分值的目標(biāo)頁面一定有多個專家頁面鏈接指向,目標(biāo)頁面所獲得的總傳播分值是每個有鏈接指向的專家頁面所傳遞的分值之和
條件2、專家頁面和所指向的目標(biāo)頁面不能是從屬組織頁面
目標(biāo)頁面權(quán)值計算步驟:
1、找到專家頁面中那些能夠支配頁面的關(guān)鍵片段集合S
2、統(tǒng)計S中包含用戶查詢詞的關(guān)鍵片段個數(shù)T,T越大權(quán)值越大
3、專家頁面給目標(biāo)頁面?zhèn)鬟f分值:E*T,E為專家頁面本身在第一階段計算得到的相關(guān)得分,T為b步驟計算分值
對于包含多個查詢詞的用戶請求,則每個查詢詞單獨計算,將多個查詢詞的傳遞分值累加
Hilltop算法存在與HITS算法類似的計算效率問題,隨著專家頁面集合的增大
其他改進(jìn)算法
1、智能游走模型(Intelligent Surfer Model)
判斷網(wǎng)頁包含的鏈接所指向的網(wǎng)頁內(nèi)容和用戶查詢的相關(guān)性,以此來改善鏈接分析效果
2、偏置游走模型(Biased Sufer Model)
智能游走模型考慮的是網(wǎng)頁內(nèi)容和用戶查詢的相關(guān)性,而偏游走模型考慮的是鏈接指向的網(wǎng)頁內(nèi)容和當(dāng)前瀏覽網(wǎng)頁內(nèi)容之間的相似性
3、PHITS算法(Probability Analogy of HITS)
PHITS是對HITS算法的直接改進(jìn)。PHITS算法認(rèn)為不同鏈接其傳遞權(quán)值的能力應(yīng)該是不同的,PHITS需要計算兩個頁面S和T之間鏈接的連接強度
鏈接的強度依據(jù)頁面S和T之間相似度確定
4、BFS算法(Backward Forward Step)
對SALSA算法的擴展,對HITS算法的限制
解除了SALSA算法只允許直接相鄰網(wǎng)頁才能有影響的限制,只要網(wǎng)頁S和T可通達(dá),即可對網(wǎng)頁T施加影響,如果網(wǎng)頁S距離網(wǎng)頁T距離越遠(yuǎn),那么網(wǎng)頁S的影響就隨著距離增大而呈現(xiàn)衰減
posted @
2013-11-12 14:06 胡滿超 閱讀(620) |
評論 (0) |
編輯 收藏
檢索模型與搜索排序
最重要的兩個因素,用戶查詢與網(wǎng)頁相關(guān)性,網(wǎng)頁鏈接情況
檢索模型:用戶查詢與網(wǎng)頁相關(guān)性
布爾模型,向量空間模型,概率模型,語言模型,機器學(xué)習(xí)排序算法
布爾模型:數(shù)據(jù)基礎(chǔ)是集合論,搜索結(jié)果過于粗糙,無法量化搜索詞與文檔之前的相關(guān)性
向量空間模型:把文檔看做是由T維特征組成的一個向量,最常用的是以單詞作為特征,實際應(yīng)用中,文檔的維度相當(dāng)高(成千上萬)
將查詢和文檔之間的內(nèi)容相似性作為相關(guān)性的替代
計算相似性,使用COSINE,計算查詢詞特征權(quán)值與文檔中每個特征權(quán)值向量的點積
特征權(quán)重:由詞頻Tf,逆文檔頻率IDF確定
詞頻Tf:Wtf=a+(1-a)*Tf/Max(Tf)
a取0.4效果較好
逆文檔頻率因子:文檔集合范圍的一種全局因子,特征單詞之間的相對重要性
有研究者進(jìn)一步分析認(rèn)為:IDF代表了單詞帶有的信息量的多少(熵),其值越高,說明其信息含量越多,越有價值
IDFk=log(N/nk)
N代表文檔集合中總共有多少個文檔,nk代表特征單詞k在其中多少個文檔中出現(xiàn)過
Weight_word=Tf*IDF,特征權(quán)值越大,越可能是好的指示詞
查詢詞在某個文檔中的詞頻越高,在其他文檔中出現(xiàn)的詞頻越低,這個詞的權(quán)值越高
向量空間模型是經(jīng)驗型的模型,靠直覺和經(jīng)驗不斷摸索完善,缺乏明確的理論指導(dǎo)改進(jìn)方向
概率排序原理:給定一個用戶查詢,如果搜索系統(tǒng)能夠在搜索結(jié)果排序時按照文檔和用戶需求的相關(guān)性由高到低排序,那么這個搜索系統(tǒng)的準(zhǔn)確性是最優(yōu)的。
將P(D|R)/P(D|NR)大小進(jìn)行降序排列,得到搜索相關(guān)性排序
二元獨立模型
二元假設(shè):一遍文檔在由特征進(jìn)行表示的時候,以特征“出現(xiàn)”和“不出現(xiàn)”兩種情況來表示
詞匯獨立假:文檔中出現(xiàn)任意一個詞在文檔的分布概率不依賴于其他單詞是否出現(xiàn)
BMI模型:基于二元假設(shè)推導(dǎo)而出,對于單詞特征,只考慮是否在文檔中出現(xiàn)過,而了考慮單詞的權(quán)值
P(D|R)/P(D|NR) = pi(1-si)/si(1-pi)
log( pi(1-si)/si(1-pi) )
pi代表第i個單詞在相關(guān)文檔集合內(nèi)出現(xiàn)的概率,在二元假設(shè)下,可以用包含這個單詞的相關(guān)文檔個數(shù)ri除以相關(guān)文檔總數(shù)R來估算,pi=ri/R
si代表第i個詞在不相關(guān)文檔集合內(nèi)出現(xiàn)的概率,可以用包含這個單詞的不相關(guān)文檔個數(shù)ni-ri,除以不相關(guān)文檔總數(shù)(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))
其含義:對于同時出現(xiàn)在用戶查詢Q和文檔D中的單詞,累加每個單詞的估值,其和就是文檔D和查詢相關(guān)性度量值
BM25模型
在BIM模型的基礎(chǔ)上,考慮了單詞在查詢中的權(quán)值及單詞在文檔中的權(quán)值,擬合出綜合上述考慮因素的公式,并通過引入一些經(jīng)驗參數(shù)
BM25模型是目前最成功的內(nèi)容排序模型
k1,k2,K均為經(jīng)驗設(shè)置的參數(shù),fi是詞項在文檔中的頻率,qfi是詞項在查詢中的頻率。
K1通常為1.2,通常為0-1000
K的形式較為復(fù)雜
K=
上式中,dl表示文檔的長度,avdl表示文檔的平均長度,b通常取0.75BM25F模型:是典型的BM25改進(jìn)算法
將文檔內(nèi)容切換成不同的部分,為不同的部分賦予不同的權(quán)重
語言模型方法:借鑒語音識別領(lǐng)域采用的語言模型技術(shù),將語言模型和信息檢索相互融合
為每個文檔建立一個語言模型,語言模型代表了單詞或者單詞序列在文檔中的分布情況
對于查詢中的單詞來說,每個單詞都對應(yīng)一個抽取概率,將這些單詞的抽取概率相乘就是文檔生成查詢的總體概率
一般采用數(shù)據(jù)平滑方式解決數(shù)據(jù)稀疏問題
用戶提交查詢Q,文檔集合內(nèi)所有文檔都計算生成Q的概率,然后按照生成概率值由大到小排序,就是搜索結(jié)果
HMM,隱馬爾科夫語言模型、相關(guān)模型、翻譯模型是在基本語言模型的改進(jìn)
語言模型檢索方法效果略優(yōu)于精調(diào)參數(shù)的向量空間模型,與BM25等概率模型效果相當(dāng)
通過理論推導(dǎo),可以得出:語言模型檢索方法的排序公司符合概率模型的概率排序原理,類似向量空間模型Tf*IDF
機器學(xué)習(xí)排序
為何興起較晚:
1、其他模型和方法,考慮的因素較少,人工進(jìn)行公式擬合完全可行,效果尚可
2、機器學(xué)習(xí)需要大量訓(xùn)練數(shù)據(jù),用戶點擊記錄可以當(dāng)做機器學(xué)習(xí)方法訓(xùn)練數(shù)據(jù)的一個替代品
機器學(xué)習(xí)排序系統(tǒng)的4個步驟:
人工標(biāo)注訓(xùn)練數(shù)據(jù):用戶點擊記錄來模擬人工打分機制
文檔特征抽取:查詢詞在文檔中的詞頻、查詢詞的IDF信息,網(wǎng)頁入鏈數(shù)量,網(wǎng)頁出鏈數(shù)量,網(wǎng)頁PageRank值,網(wǎng)頁URL長度,查詢詞的Proximity值(文檔中多大的窗口內(nèi)可以出現(xiàn)所有查詢詞)
學(xué)習(xí)分類函數(shù)
在實際搜索系統(tǒng)中采用機器學(xué)習(xí)模型
機器學(xué)習(xí)方法
1、單文檔方法
對單獨的一篇文檔轉(zhuǎn)換為特征向量,機器學(xué)習(xí)系統(tǒng)根據(jù)從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)到的分類或回歸函數(shù)對文檔打分,打分結(jié)果為最后得分
在訓(xùn)練過程中,當(dāng)打分大于一定的閾值,為相關(guān)文檔,否則為不相關(guān)文檔。
2、文檔對方法
通過訓(xùn)練,對文檔順序關(guān)系是否合理進(jìn)行判斷,判斷兩個文檔的得分
使用SVM,BOOST,神經(jīng)網(wǎng)絡(luò),都可以做為學(xué)習(xí)方法
缺點,只考慮了兩個文檔對的相對先后順序,卻沒有考慮文檔出現(xiàn)的搜索列表中的位置
不同的查詢,相關(guān)文檔數(shù)量差異很大,對機器學(xué)習(xí)系統(tǒng)的效果造成評價困難
3、文檔列表方法
將每個查詢對應(yīng)的所有搜索結(jié)果列表作為一個訓(xùn)練實例
通過搜索結(jié)果排列組合的概率分布,訓(xùn)練評分函數(shù)
搜索質(zhì)量評價標(biāo)準(zhǔn):對于搜索引擎更加關(guān)注精確率
精確率:本次搜索結(jié)果中相關(guān)文檔所占本次搜索返回的所有文檔的比例
招回率:本次搜索結(jié)果中相關(guān)文檔占整個集合中所有相關(guān)文檔的比例
P@10指標(biāo):在搜索結(jié)果排名最先前的頭10個文檔中有多大比例是相關(guān)的
MAP:AP兼顧了排在前列的相關(guān)性和系統(tǒng)招架率,MAP多組查詢的AP平均值
posted @
2013-11-04 12:56 胡滿超 閱讀(598) |
評論 (0) |
編輯 收藏
詞典壓縮:減小詞典的內(nèi)存占用
好的壓縮算法:壓縮率,壓縮速度,解壓速度(最重要)
一元編碼
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的整數(shù)次冪,所有小于Avg中最接近Avg的數(shù)值
變長壓縮算法SimpleX
Simple9: 32位比特位,4個比特為管理數(shù)據(jù)存儲區(qū),28個比特壓縮數(shù)據(jù)存儲區(qū)
Simple9的28位有9種表示形式
Simple16: 28位有16種表示形式,并且通過非當(dāng)項完全固定長度,解決數(shù)據(jù)區(qū)有浪費位的情況
PForDelta:目前解壓速度最快的一種倒排文件壓縮算法
1,對待編碼的連續(xù)K個數(shù)值(一般為128),確定10%的大數(shù)數(shù)值,根據(jù)70%小數(shù)確定奪取的比特寬度,確定整個序列
2,對原始數(shù)據(jù)遍歷,將大數(shù)放置到尾端,并轉(zhuǎn)換成鏈表結(jié)構(gòu)的序列
3、將所有數(shù)字壓縮到隊列中
文檔編號重排序
網(wǎng)頁的文檔ID+單詞詞頻信息,文檔ID使用D-Gap進(jìn)行編碼
將內(nèi)容越相似的網(wǎng)頁,在編排文檔號時越相鄰
海量數(shù)據(jù)文本聚類速度較慢,將URL相似的網(wǎng)頁聚合在一起,假設(shè)同一個網(wǎng)站的很多頁面表達(dá)的主題內(nèi)容是近似的
靜態(tài)索引裁剪:主動拋棄一部分不重要的信息(索引項)來達(dá)到數(shù)據(jù)壓縮的效果
以單詞為中心的索引裁剪:
判斷單詞與文檔的相似性,每個詞典中的單詞,其對應(yīng)的倒排排列中至少保留K個索引項,還要保留若干富余項目
實驗證明,如果首先對所有索引項的原始得分減去得分最低索引項的得分,再采取(對K個項進(jìn)行折扣,乘一個折扣因子,得出閾值a,剩下的大于a保留)方法進(jìn)行裁剪,效果會大大提升
因為
索引項得分分差相關(guān)不大,比較集中在某個區(qū)間,所以減掉得分最低項
以文檔為中心的索引裁剪:更為常用
在建立索引之前進(jìn)行數(shù)據(jù)預(yù)處理,把與文檔主題表達(dá)不相關(guān)的單詞拋棄,如停用詞
posted @
2013-11-04 12:56 胡滿超 閱讀(864) |
評論 (0) |
編輯 收藏
單詞詞典
1、哈希加鏈表
2、樹形結(jié)構(gòu):B樹或者B+樹
倒排列表:
單詞+文檔號,詞頻,出現(xiàn)的位置
文檔號一般采用差值存儲,以節(jié)省空間
建立索引
1、兩遍文檔遍歷法
第一遍,收集全局統(tǒng)計信息,文檔數(shù)N,每個文檔包含不同單詞數(shù)M,每個單詞在多少個文檔中出現(xiàn)過的信息DF,通過這些信息可以計算出最終索引的大小
第二遍,在建立好的內(nèi)存中建立索引,從磁盤讀取文檔并解析文檔是最消耗時間的步驟
2、排序法
始終在內(nèi)存中分配固定大小的空間,用來存放詞典信息和索引中間結(jié)果,當(dāng)分配空間消耗光的時候,把中間結(jié)果寫入磁盤,清空內(nèi)存數(shù)據(jù)進(jìn)行下一輪索引
中間結(jié)果排序,排序前,文檔ID,單詞ID,單詞頻率
排序后,單詞ID(主鍵),文檔ID(次鍵)
合并中間結(jié)果,把中間結(jié)果文件進(jìn)行合并,按單詞ID寫入最終結(jié)果文件
3、歸并法
在中間結(jié)果排序完成以后,把字典信息也寫入文檔中,這樣全額使用內(nèi)存
在建立中間索引中,實際單詞,文檔編號,詞頻
合并時,針對每個單詞的倒排列表進(jìn)行合并,形成最終的詞典信息
動態(tài)索引
倒排索引:詞典在內(nèi)存里,倒排列表存儲在磁盤文件中
臨時索引:詞典和倒排列表都在內(nèi)存中,當(dāng)有新文檔加入時,放到臨時索引中
刪除文檔列表:當(dāng)文檔內(nèi)容被更改時,系統(tǒng)認(rèn)為舊文檔被刪除,增加一篇新文檔
當(dāng)用戶輸入查詢時,先從找倒排索引+臨時索引,去掉刪除文檔列表中的文檔結(jié)果
索引更新策略
1、完全重建策略:當(dāng)新增文檔達(dá)到一定數(shù)量后,新老索引合并重建,適合小文檔集合,主流商業(yè)搜索引擎一般也采用此方式來維護
2、再合并策略:當(dāng)新增文檔達(dá)到一定數(shù)量后,新老索引合并重建,此時老索引還在被使用,由于老索引有序,所以合并策略執(zhí)行較快,但是讀老索引,建新索引,也需要較多IO時間,比較耗時
3、原地更新策略:在建立老索引時,在老索引倒排列表中留有一定的余地,新加入索引直接追加到預(yù)留空間,實驗數(shù)據(jù)表明,更新效率比再合并策略低
4、混合策略:將單詞根據(jù)不同性質(zhì)進(jìn)行分類,對其索引采取不同的索引更新策略,長倒排列表單詞采取原地更新策略(讀寫開銷大),短倒排列表采取再合并策略(讀寫開銷不算太大)
查詢處理
1、一次一文檔,找到包含關(guān)鍵字的所有文檔集合,一次計算一個文檔的得分,依次計算所有文檔,計算后一般采用優(yōu)先隊列對分?jǐn)?shù)進(jìn)行排序
2、一次一單詞,一次計算一個單詞的得分,并把結(jié)果以文檔編寫為關(guān)鍵值,以hash表存儲得分,計算所有文檔得分后,對hash表進(jìn)行排序
跳躍指針
在存儲倒排索引文檔編號時,通常使用跳躍指針節(jié)省空間,跳躍指針分塊使用根號L為長度效果較好
多字段索引:對網(wǎng)頁的不同區(qū)域進(jìn)行字段劃分,進(jìn)行索引
1、多索引方式,對每個不同的字段分別建立索引
2、倒排列表方式,把字段信息存儲到倒排列表項中
3、擴展列表方式,把每個字段出現(xiàn)的位置記錄到一張列表里,倒排索引找到單詞后,判斷單詞的位置是否在某字段范圍中
短語查詢:本質(zhì)上是如何在索引中維護單詞順序關(guān)系或位置信息
1、位置信息索引,通過位置信息判斷兩個詞是否為短語關(guān)系,適合常規(guī)短語
2、雙詞索引,首詞+下詞,只對計算代價高的短語建立雙詞索引,一般短語通過常規(guī)手段達(dá)到目的
3、短語索引,缺點無法將所有短語都建好索引,從用戶查詢?nèi)罩净蚓W(wǎng)頁本身挖掘短語,適合熱門短語
4、混合方法,用戶查詢->短語索引->雙詞索引->常規(guī)索引
分布式索引:多臺機器協(xié)作完成索引
1、按文檔劃分,每臺機器負(fù)責(zé)對某個文檔子集建立索引
2、按單詞劃分,將單詞分別傳送給服務(wù)器1,計算結(jié)果后,再傳送給服務(wù)器2,一次一單詞的查詢處理方式
posted @
2013-09-16 14:01 胡滿超 閱讀(540) |
評論 (0) |
編輯 收藏
二、網(wǎng)絡(luò)抓蟲
網(wǎng)頁頁面劃分為5個部分:
1、已下載
2、已過期
3、待下載
4、可知網(wǎng)頁集合,未下載,但可索引
5、不可知網(wǎng)頁集合,暗網(wǎng)網(wǎng)頁
爬蟲分三種類型:
1、批量型:有明確的抓取范圍和目標(biāo),當(dāng)達(dá)到這個目標(biāo)后停止抓取
2、增量型:不斷抓取,抓取到以后定期更新
3、垂直型:抓取特定行業(yè)網(wǎng)頁
優(yōu)秀爬蟲的特性:高性能、可擴展(良好的并發(fā)性)、健壯性、友好性(遵守Robot協(xié)議)
評價爬蟲質(zhì)量的標(biāo)準(zhǔn):覆蓋率,時新性,重要性
抓取策略:優(yōu)先選擇重要網(wǎng)頁進(jìn)行抓取
1、寬度優(yōu)先遍歷策略,雖然機械,但是效果好,隱含了一些網(wǎng)頁優(yōu)秀級的假設(shè)
2、非完全PageRank策略,對已下載網(wǎng)頁集合,加上待抓取URL,形成網(wǎng)頁集合,進(jìn)行PageRank計算,將待抓取按得分進(jìn)行排序
3、OCIP策略,在線頁面重要性計算,待下載頁面都分配相同的cash,下載后把頁面擁有的現(xiàn)金平分給包含的鏈接,
待抓取URL則根據(jù)手頭現(xiàn)金排序,優(yōu)先下載最充裕網(wǎng)頁。計算速度快,適合實時計算,效果略優(yōu)于寬度優(yōu)先
4、大站優(yōu)先策略,哪個網(wǎng)站等等下載的頁面最多,則優(yōu)先下載這些鏈接,效果略優(yōu)于寬度優(yōu)先
網(wǎng)頁更新策略
1、歷史參考策略,過去頻繁更新的網(wǎng)頁,將來也會頻繁更新,利用泊松過程
抓取策略應(yīng)該忽略掉廣告或?qū)Ш降确侵匾獏^(qū)域的頻繁變化,集中在主題內(nèi)容的變化探測和建模
2、用戶體驗策略,對搜索結(jié)果排名靠前,更新以后對搜索質(zhì)量(排名)的影響較大的頁面進(jìn)行更新
3、聚類抽樣策略,先對網(wǎng)頁進(jìn)行聚類,對同一類網(wǎng)頁采用相同的更新頻率
聚類特征:
靜態(tài)特征,頁面的內(nèi)容,圖片數(shù)量,頁面大小,鏈接深度,PageRank值
動態(tài)特征,隨著時間的變化 ,靜態(tài)特征的變化情況
聚類抽樣策略效果好于前述兩種,但是對億計網(wǎng)頁進(jìn)行聚類,難度較大
暗網(wǎng)抓取
將暗網(wǎng)數(shù)據(jù)從數(shù)據(jù)庫中挖掘出來,百度的“阿拉丁”計劃就是解決此問題
查詢組合:Google提出富含信息查詢模板技術(shù),使用富含信息查詢模板進(jìn)行查詢,獲取有效的網(wǎng)頁結(jié)果
富含信息查詢模板:對于某固定的查詢模板來說,如果給模板內(nèi)每個屬性都賦值,形成不同的查詢組合,其返回內(nèi)容差異較大,則這個查詢模板為富含信息查詢模板
分布式爬蟲
主從分布式:URL服務(wù)器容易成為整個系統(tǒng)的瓶頸
對等分布式:沒有URL服務(wù)器存在,每臺抓取服務(wù)器的分工成為問題,對網(wǎng)址的主域名進(jìn)行哈希計算,之后對m服務(wù)器數(shù)量取模,把計算后的模和抓取服務(wù)器號匹配
一致性哈希算法:將網(wǎng)站主域名進(jìn)行哈希,映射到0~2^32之間某個數(shù)值,抓取服務(wù)器負(fù)責(zé)這個環(huán)狀序列的一個片段的抓取,抓取內(nèi)容由上一個服務(wù)器進(jìn)行循環(huán)轉(zhuǎn)發(fā)
posted @
2013-09-13 11:10 胡滿超 閱讀(590) |
評論 (0) |
編輯 收藏