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

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

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

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

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

分布式虛擬貨幣
這新上任的二狗子是聰明,不過這人有時候是聰明反被聰明誤。有一天二狗子盯著這賬本,心想這全村各戶誰有多少錢就是我說的算,那我豈不是……。于是他頭腦一熱,私自從老張帳下劃了十克金子到自己名下。
本以為天衣無縫,但沒想到老張也有記賬的習慣,有一天他正要付錢卻被二狗子告知賬戶沒錢了。老張核對了一下自己的賬本,明明還有十克啊,于是拿著賬本去找二狗子理論,這一核對發現了那筆未經老張同意的轉賬。
東窗事發!比特村炸開鍋了。二狗子被彈劾是不可避免了,不過通過這件事,大家發現了賬本集中在一個人手里的弊端:
- 這個體系完全依賴于賬本持有人的個人信用,如果這個人不守規矩,隨意篡改賬本,那么整個貨幣系統就會崩潰
- 如果這個人家里失火或者賬本失竊,同樣也會為整個體系帶來毀滅性的打擊
正當人們不知所措時,村里一個叫中本聰的宅男科學家走上了臺,告訴大家他已經設計了一套不依賴任何中央處理人的叫比特幣的虛擬貨幣系統,可以解決上述問題。然后他緩緩講述了自己的方案。
下面我們就來看看中本聰同學是如何設計這套系統的。
基礎設施搭建賬簿公開機制
中本聰首先說明,要對現有賬簿進行如下改造:
- 賬簿上不再記載每戶村民的余額,而只記載每一筆交易。即記載每一筆交易的付款人、收款人和付款金額。只要賬簿的初始狀態確定,每一筆交易記錄可靠并有時序,當前每個人持有多少錢是可以推算出來的。
- 賬簿由私有改為公開,只要任何村民需要,都可以獲得當前完整的賬簿,賬簿上記錄了從賬簿創建開始到當前所有的交易記錄。
此言一出,下面立刻炸鍋了。第一條還無所謂,但是第二條簡直無法接受,因為賬簿可是記錄了所有村民的交易,這樣大家的隱私不全暴露了嗎。
中本聰倒是不慌不忙,拿出了一對奇怪的東西。
身份與簽名機制(公鑰加密系統)
中本聰說,大家不要慌。在他的這套機制下,任何人都不使用真實身份交易,而是使用一個唯一的代號交易。
他展示了手里神奇的東西,說這兩件東西分別叫保密印章和印章掃描器。后面他會給村里每一戶發一個保密印章和一個印章掃描器。兩者的作用如下:
- 保密印章可以在紙上蓋一個章,每個印章蓋出的章都隱含了一個全村唯一的一串字符,但是憑肉眼是看不出來的。也無法通過觀察來制造出相應的印章。
- 印章掃描器可以掃描某個已經蓋好的章,讀出隱含的信息,并在液晶屏上顯示出一串字符。
有了這兩個神奇的東西,大家就可以在不暴露真實身份的情況下進行交易了,而印章隱含的那一串字符就是這戶人家的代號。具體如何巧妙利用保密印章和印章掃描器進行交易,會在下文詳述。
成立虛擬礦工組織(挖礦群體)
下一步,中本聰面向全村招募虛擬礦工,招募要求如下:
- 礦工以組為單位,一組可以是單獨的一戶,也可以是幾戶聯合為一組
- 成為礦工不影響正常使用貨幣
- 礦工每天要花費一定時間從事比特幣“挖礦”活動,但是不同于挖金礦,虛擬礦工不需要拿著工具去野外作業,在家里就可以完成工作
- 礦工有一定可能性獲得報酬,在挖礦活動中付出的努力越多,獲得報酬的可能性越大
- 礦工可以隨時退出,也可以隨時有新的礦工加進來
很快,大約有五分之一的村民加入比特幣礦工組織,共分成了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個小組請求確認。
中本聰規定,當某個小組接到其他小組送來的賬簿紙時,必須立即停下手里的挖礦工作進行賬簿確認。
需要確認的信息有三個:
- 賬簿的編號有效
- 賬簿的前一頁賬簿有效
- 交易清單有效
首先看第一個,這個確認比較簡單。只要將送來的賬簿紙放入編碼生成器進行驗證,如果驗證通過,則編號有效。
第二部分需要將賬簿頁上的“上一頁賬簿紙編號”和這個小組目前保存的有效賬簿最后一頁編號比對,如果相同則確認,如果不同,需要順著已有賬簿向前比對,直到找到這個編號的頁。如果沒有找到指定的“上一頁賬簿紙編號”對應的頁,這個小組會將此頁丟掉。不予確認。
注意,由上面的機制可以保證,如果各個小組手里的賬簿紙是相同的,那么他們都能按同樣的順序裝訂成相同的賬簿。因為后面一張紙的編號總是依賴前面的紙的編號,編碼生成器的機制保證了所有合法賬簿紙的相對先后順序在每個小組那里都是相同的(可能會有分支,但不會出現環,后面細講)。

最后是如何確認交易清單有效,其實也就是要確認當前每筆交易的付款人有足夠的余額支付這筆錢。由于交易信息里包含這筆錢是如何來的,還包含了記錄來源交易的賬單編號。例如,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%作為手續費支付給生成賬簿頁的小組,各個小組會挑選手續費高的交易單優先確認。
礦工如果越來越多,比特幣生成速度會變快嗎
不會。中本聰解釋,雖然可以任意加入和退出礦工組織,導致礦工人數變化,每個礦工也會拿到一個編碼生成器,不過我已經在編碼生成器中加入了調控機制,當前工作的編碼生成器越多,每個機器的效率就越低,保證新賬簿頁生成速率不變。
雖然每個人的代號是匿名的,但如果泄露了某個人的代號,賬簿又是公開的,豈不是他的所有賬目都查出來了
確實是這樣的。例如你要和某人交易,必然要要到他的代號才能填寫交易單。因為收款人一欄要填入那人的代號。不過中本聰說可以提供無限制的保密印章,建議每一次交易用不同的保密印章,這樣查賬簿就追查不到同一個人的所有賬目了。
答疑完畢。
說明本文用通俗比喻的方式講解了比特幣的運行機制。有幾點需要說明:
- 為了便于理解,我做了很多簡化,因此有些機制細節和實際的比特幣可能不完全相同。但總體思想和關鍵原理是一致的。
- 由于很多計算機世界的東西(如公鑰體系、網絡傳輸)在現實世界中并沒有特別好的對等物,所以故事里難免有一些生硬和不合常理的細節。
- 本文描述的是比特幣網絡本身的技術原理和運作機制,當在如Mtgox這種買賣市場中進行比特幣交易時,市場做了中間代理,并不遵從上述機制
參考- Bitcoin: A Peer-to-Peer Electronic Cash System
- https://bitcoin.it
- 云風的BLOG: Bitcoin 的基本原理
- 易懂的比特幣工作機理詳解
posted @
2014-02-13 10:36 胡滿超 閱讀(502) |
評論 (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 胡滿超 閱讀(617) |
評論 (0) |
編輯 收藏
檢索模型與搜索排序
最重要的兩個因素,用戶查詢與網頁相關性,網頁鏈接情況
檢索模型:用戶查詢與網頁相關性
布爾模型,向量空間模型,概率模型,語言模型,機器學習排序算法
布爾模型:數據基礎是集合論,搜索結果過于粗糙,無法量化搜索詞與文檔之前的相關性
向量空間模型:把文檔看做是由T維特征組成的一個向量,最常用的是以單詞作為特征,實際應用中,文檔的維度相當高(成千上萬)
將查詢和文檔之間的內容相似性作為相關性的替代
計算相似性,使用COSINE,計算查詢詞特征權值與文檔中每個特征權值向量的點積
特征權重:由詞頻Tf,逆文檔頻率IDF確定
詞頻Tf:Wtf=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模型是目前最成功的內容排序模型
k1,k2,K均為經驗設置的參數,fi是詞項在文檔中的頻率,qfi是詞項在查詢中的頻率。
K1通常為1.2,通常為0-1000
K的形式較為復雜
K=
上式中,dl表示文檔的長度,avdl表示文檔的平均長度,b通常取0.75BM25F模型:是典型的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 胡滿超 閱讀(596) |
評論 (0) |
編輯 收藏
詞典壓縮:減小詞典的內存占用
好的壓縮算法:壓縮率,壓縮速度,解壓速度(最重要)
一元編碼
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 胡滿超 閱讀(863) |
評論 (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 胡滿超 閱讀(538) |
評論 (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 胡滿超 閱讀(589) |
評論 (0) |
編輯 收藏