上一篇:狗池历险记(零、一)

二、故事的开头

  尽管从开篇看来,做矿池是顺理成章的事情,然而故事真实的开头是这样的:

  首先,我们这帮技术宅(D神、R神、H神、M神、F神、S神、X神……)有一个群,平时在群里灌水,偶尔讨论技术。群里的话题是从这天开始变化的——

  • 2013.11.18 早上,R 神发了条微博说,睡觉前买了一个比特币,花了 3000,醒来之后涨到了 3600。见此大家各种膜拜。
  • 2013.11.18 白天,好消息:国内最大的比特币交易平台拿到了风投。于是比特币涨到了 4000 多一个。
  • 2013.11.18 晚上,好消息:美帝公开表示不会取缔比特币。于是比特币一下子飙升到 7000 一个……
  • 此后的若干天,技术宅们一有空就在 YY 怎么从中捞一笔。
  • 2013.11.23 D 神发现了矿池,于是开始天天给我们洗脑做出来可以躺着数钱。
  • 2013.11.26 我终于受不了洗脑,决定推动开发矿池。

三、数据币——走向人生巅峰,要先登上这个小山包

  伟大的 D 神在给我们洗脑要做矿池的时候,心里已经想好了要做“数据币”的矿池。这个数据币又是什么鬼?炒过币的人可能知道除了比特币之外,还存在着很多的山寨币。而数据币只是茫茫币海中一种非常普通的山寨币。

山寨币

  山寨币,其实英文是 alternative coin,其实这两个名字都挺确切的,就看从什么角度去看山寨币了。

  从技术创新角度看,山寨币只是在比特币之上做了点微创新。比特币提出了一整套金融体系,当之无愧是革命性的创新。而山寨币,说白了只是 fork 了比特币的代码,然后改了其中的一些参数而已。比如虚拟币市场中仅次于“金币”比特币的“银币”莱特币,作为最大的山寨币,主要也就三点微创新:改多了货币总额,加速了转账时间,然后把挖矿算法从 SHA-256 改成了 Scrypt。看起来确实挺山寨的。

  但是从应用的角度看,这些参数改动并不是毫无根据的,每个改动都可以成为山寨币的卖点。转账时间更短,可以让虚拟币交易更快捷,提高其实用性。而挖矿算法上,Scrypt 算法更适合 GPU 计算,相对而言更平民化。要知道比特币挖矿就是因为用了 SHA-256 算法,在 2013 年之后算力已经完全被专用集成电路(ASIC)垄断[引用],GPU 矿工根本没法获得收益。算力被垄断,对于虚拟币来说是很危险的,这点上,莱特币相比比特币稍微安全一些。这么看来,山寨币确实也是 alternative 的。

  制造一种山寨币,在技术并不难,难的是推广和运营。比如先要让人相信这个山寨币不是骗钱的(作者没有预挖之类);然后文案上要把“改参数”的故事说好,让人认为这是革命性的创新,值得去投资;最后对于特别山寨的山寨币而言,要想方设法让币上交易平台,上越大的交易平台,大家都认可度就越高。

  对于山寨币,中国比特币首富李笑来也曾公开表示他不会投资山寨币,他认为山寨币的创新和比特币比起来,根本算不上创新,不会长存。其实很多人也都是这个观点,但是芸芸众生就算后知后觉了首富的观点,也不见得就有觉悟不去碰山寨币。因为大家都相信,自己不是最后一个“接盘侠”。

比特币莱特币质数币数据币
btcltc
xpmdtc
SHA-256,ASIC挖矿Scrypt,GPU挖矿质数序列,CPU挖矿质数序列,CPU挖矿

数据币和质数币

  回到数据币,当然也是些微创新。数据币其实是一个在质数币上二次山寨的山寨山寨币。质数币的微创新,主要在其挖矿算法上。它需要矿工挖到足够长的质数链(第一类坎宁安链,第二类坎宁安链,和双坎宁安链)来证明其工作力投入。矿工在投入质数币挖掘的同时,也是在试图挖掘世界上最大的质数序列,有不少世界纪录是质数币创下的[引用1引用2]。从这个角度看,质数币可以算是一种有用的币。

  那数据币又在质数币上加了什么微创新呢?数据币在转账时可以带一句话,或者带个种子文件。以后这条信息就会永远留存在数据币的 P2P 网络中,可以真正的“永流传”,当然前提是一直有人用……

  D 神为什么选了数据币呢?

  第一,质数币或者数据币所用的质数挖掘算法在当时只能使用 CPU 来挖矿。比起比特币的矿卡和莱特币的显卡,CPU 挖矿更难被垄断,更平易近人。其实我们要是去做显卡币,自己都没机器测试。

  第二,数据币一直没有出现公开的矿池。这对于我们来说是个绝佳的切入口。虽说这个山寨币小的连矿池都没人来做,但是从 D 神在数据币矿工群里混了几天所了解的情况来看,矿工的激情以及整个币的体量还是足够养活我们的。

  在干活之前先画个大饼。所有矿池都会宣传自己的挖矿效率,列出最近出了多少区块(区块是挖矿的最小单位,一“块”矿里有 N 个币,N 在一段时间里基本不变)。同时我们也知道矿池的手续费是多少,所以很快就可以算出矿池的收入。当时质数币的第三大矿池(一共就三个),日入过万!YY 着我们从中随便抢点零头,也是非常可观的啊。

零、开坑按

  2016年5月2日有新闻报道称,澳大利亚企业家克莱格·莱特(Craig Wright)拿出了一些证据证明了他就是比特币之父“中本聪”。回想起三年前,在比特币最火爆的时候,自己也曾参与其中。这段经历可能非常独特,故在此与大家分享。

  2013 年秋天,大妈们在跳完广场舞后开始讨论比特币。比特币的价格从年初不到 100 元一个,一路飙升到 7000 元一个,深受投机人士的欢迎。就在这样的环境下,我们几个技术宅开始 YY自己能从这一波中捞点什么。当时我们发现了这些致富大法:1. 炒币,缺钱缺运气。2. 挖矿,缺机器,其实也是缺钱。3. 套利,缺钱。4. 做交易平台,似乎政策风险太大了,不敢做。 5. 做矿池,似乎只要技术。对于没钱没背景只有技术的我们来说,显然第五种致富大法,也就是做“矿池”看起来更值得一试。

一、矿池是什么,能吃吗?

  想知道矿池能不能吃,就要先从挖矿说起。“挖矿”是生产比特币的过程,从“挖”这个字不难猜到,“挖矿”是一件费时费力同时需要一定运气的事情。如果用最原始的手段来挖矿,我们需要先下载一个比特币客户端(通常也叫比特币钱包,毕竟一般只用它来放“钱”),等客户端自动同步完比特币网络上的数据后,就会自动开始挖矿。

  从技术上看,挖矿是个什么样的过程呢?简单的说,挖矿就是在算哈希,地球上所有想挖比特币的矿工一起算哈希。大约每 10 分钟,比特币网络就会公布一个基准字符串。收到这个字符串之后,所有挖矿的机器,都要做同一件事情:在这个基准字符串的后面加上一个随机字符串,并且希望这个合成的这个字符串,通过两次 SHA-256 哈希算法后,得到的输出,前面要有足够多的 0。

SHA-256(SHA-256(“基准字符串” + “随机字符串”)) = 000000000000…01011101…

  到目前为止,SHA-256 还没被破解,也就是说,我们还没有办法通过构造原串,得到期望的输出。所以对于我们勤劳朴实的矿工而言,唯一能做的就是,不断地替换随机字符串,直到人品大爆发,随机到我们想要的结果。比如,现在如果要挖到比特币,需要哈希结果中,前面有 67 个 0。这是个什么概念?大概是说,我们如果不停地随机,不停地哈希,会有 2 的 67 次方之一的概率,随机到我们想要的结果,然后就挖到一大块比特币,里面大概有 25 个比特币(具体数值因时间而异)。简单估计一下,$2^{67}=147573952589676412928$,如果我们的机器非常快,1 秒算 1 亿次哈希,那么……运气正常的话,大概需要46795.4 年才能挖到比特币,这可真不是一般人玩得起的。

  既然单干玩不起,那就大家一起来吧,这便有了矿池。矿池就是一堆人一起挖矿,挖到矿之后,根据大家投入的算力按比例分配收益。只要在矿池挖矿的人足够多,小算力的矿工就可以收到小额但是很稳定的收益,而不像独立挖矿的时候那样(行话叫 solo),平时影子都没,突然有一天变成爆发户。矿池的收入模式非常简单,就是手续费提成。这简直就是一个一本万利的项目啊,成本可能就是几台服务器,做出来躺着数钱就行了。

下一篇:狗池历险记(二、三)

前前后后写论文也有将近一年的时间了。这个研究的课题到目前还比较热门,在此分享博士论文。希望读者有所收获,少走一些弯路。

论文下载地址:http://pan.baidu.com/s/1jGWmmZO

感谢赵老师的指导,以及各位老师同学的宝贵建议!

有什么疑问或者发现什么问题都可以直接在这里评论。

  自认为这是一篇有用的文章,因此在发表之前先放到 arXiv 上,供大家参考,请批评指正。
  论文地址:http://arxiv.org/abs/1507.05523
  实验代码地址:https://github.com/licstar/compare

  准备这篇论文大概花了半年时间,从去年 11 月开始做实验,到今年成文。期间消耗大约 10 万 CPU 小时,然后在几十万个结果里面做人肉数据挖掘,最后得到了一些可能有用的结论。

  看标题就能够猜到论文的大概内容了,就是希望找到一种简单有效的词向量学习方法。怎么会想到做这件苦逼的事情呢?半年之前在我准备上一篇论文的时候(RCNN,强行广告,欢迎引用,文章点此,上面的常用链接里有文章相关信息)有一个意外的发现:选用不同的词向量作为模型的初始值,效果的差异非常大!!!当时正值我已经调了好几天参数,黔驴技穷之时,没想到手滑用错了个词向量,效果突然变 NB 了。这下我就脑洞大开了,要是能搞出个宇宙第一词向量,岂不是以后可以随便灌水?后面的故事肯定就能猜到了,半年之前我掉进这个坑里,只为寻找这个“宇宙第一”词向量。然后我实现了几个主流的词向量模型,遍历了各种语料和参数,榨干了实验室机器的空闲资源跑词向量,从生成的几十万个词向量里寻找规律,最后发现“宇宙第一”词向量应该是不存在的,不过生成一个好用的词向量还是有一定套路可循的。为避免某些读者对后面冗长的文字没有兴趣,我先用最简单的话描述我们发现的这个套路,那就是:

首先根据具体任务,选一个领域相似的语料,在这个条件下,语料越大越好。然后下载一个 word2vec 的新版(14年9月更新),语料小(小于一亿词,约 500MB 的文本文件)的时候用 Skip-gram 模型,语料大的时候用 CBOW 模型。最后记得设置迭代次数为三五十次,维度至少选 50,就可以了。

  似乎结论很“显然”,不过这种简单的策略,真的就这么有效吗?word2vec 在半年前已经是最流行的词向量生成工具了,它之所以能这么流行,除了头上顶着 Google 光环,很大程度上是因为这是一个好用的工具包,而不一定是因为它的效果就是最好的。质疑 word2vec 的效果,是因为它的两个模型(Skip-gram 和 CBOW)相对前人的模型做了大量简化,去掉了词序,又去掉了神经网络的隐藏层,最后变成了一个 log 线性模型。我主观地认为,这些简化是会影响词向量的性能的,毕竟词序很有用(上面提到的我的上一篇论文就是讲这个的,再次广告);然后神经网络的表达能力也比 logistic 回归要强得多。这两部分简化到底会带来多少损失,还是要靠数据来说话。所以我考虑的第一个问题就是,什么模型效果好。前面博客提到过的经典模型(NNLM、LBL、C&W)在 word2vec 出现之前,是最主流的方法。这些方法就保留了词序信息,而且也有隐藏层,都放到一起比较。有了这些模型,还缺一个只保留词序,但没有隐藏层的模型。所以我设计了一个中间模型,叫 Order,保留了词序,但没有隐藏层。最后再加上开源的 GloVe,一共比较了 Skip-gram、CBOW、Order、LBL、NNLM、C&W、GloVe 这 7 个模型。

  那么最严峻的问题来了,怎么样才算好的词向量呢,应该用什么指标来衡量呢?Mikolov 推广 word2vec 的时候,设计了一个经典的指标(king-queen=man-woman),由于有开放的数据集和评测代码,后来大量的工作都只用这一个指标来评价词向量。我觉得只用这个指标肯定是不对的,为什么词向量非得有这种线性平移的特性啊,如果说这是个加分项,还说得过去,但要成为唯一衡量标准,似乎没什么道理。我觉得 GloVe 那篇论文就做的很好,里面比较了一大堆指标。所以我就从根源想起,我们拿词向量是用来干什么呢?①有人拿它寻找近义词或者相关词,直接根据向量空间里的距离远近来判定词的关系。②也有不少早期的工作,直接拿词向量做特征,在现有系统中加入词向量作为特征。特征嘛,就是要个多样性,虽然不知道词向量包含了什么信息,但是说不定就带着新的信息,效果就能提升了。③还有大量基于神经网络的工作,拿词向量作为神经网络的初始值。神经网络的初始值选得好,就有可能收敛到更好的局部最优解。好,就是这三种指标了:语义特性、用作特征、用作初始值。基于这三大类用法,我们具体找了 8 个指标,进行比较,综合评价词向量的性能。(题外话,其实我从一开始就很想找到一个终极指标,用一个指标定江山,但是自从看到这 8 个指标的结果如此不一致之后,我终于放弃了这个念头。)

  为了公平的比较,肯定需要设定一个相同的语料,所有模型都用同样的语料来训练。选个什么语料呢?脑海中的第一反应是:大语料。其实小规模语料(几十兆) Turian 在 2010 年已经做过一些实验了,比较了 C&W 和 HLBL 这两个模型。大规模语料下,结论会不会不一样呢?找了两个大语料,维基百科英文版和纽约时报。此前,主流论点是:语料越大越好。所有语料都堆到一起,不管是什么内容,我语料越大,涵盖的语义信息就越丰富,效果就越好。GloVe 和 C&W 都是这么干的。自然,我也把这两个大语料混合在一起训练了。同时由于好奇心,我还把这两个语料单独拿出来训练词向量。反正就是挂机跑嘛。另一方面,为了验证一下是不是真的语料越大越好,我也在大语料中抽了 10M、100M、1G 词的子集,顺便验证一下别人的结论。说到这里我忍不住剧透了,实验中最意外的结果就是,语料对词向量的影响比模型的影响要重要得多得多得多(重要的事说三遍)。本来我只想固定一个语料,公平比较模型,结果却发现语料比模型重要(抱歉,是四遍)……后来又加了一个小规模的 IMDB 语料,进一步证实了这个结论。实验结果就是这样。

  当然,为了公平比较,还有一些其它的因素需要考虑,比如上下文窗口都开成一样大,词向量的维度也需要统一。还有个很重要的参数,那就是迭代次数。这些词向量模型都是用迭代方法优化的,迭代次数肯定会影响性能。对所有模型固定迭代次数可能不合适,毕竟模型之间的差异还是蛮大的。所以为了省事,我们对所有实验迭代足够多的次数,从 100 次到 10000 次,取最好的那次。做了这个决定之后,人省事了,机器累死了,而且对于每个语料、每个模型、每个参数,还要保留不同迭代次数的词向量,很快就把 3T 硬盘塞满了……一边删数据,一边继续做实验……这种暴力手段肯定是不适合实际应用的,所以我们也努力从实验数据中寻找规律,希望找到一种合适的迭代停止条件。

  最后总结一下,我们认为模型、语料、参数三方面会影响词向量的训练,所以从这三方面入手分析到底应该怎么生成一个好的词向量,论文由此展开。在博客里主要就介绍一下不方便写进论文里的故事和背景。

—————-枯燥开始的分割线—————-

  简单列举一下文章的贡献。
  模型方面,因为所有的词向量模型都是基于分布式分布假说的(distributional hypothesis):拥有相似上下文的词,词义相似。这里有两个对象,一个是我们需要关注的词(目标词),另一个是这个词对应的上下文。所以,我们从两个角度去总结模型:1.目标词和上下文的关系,2.上下文怎么表示。在这种分类体系下,我们对现有的主流词向量模型进行了总结和比较,发现,目标词和上下文的关系主要有两种,大多数模型都是根据上下文,预测目标词。而 C&W 模型则是对目标词和上下文这一组合,打分。实验发现,通过上下文预测目标词的模型,得到的词向量,更能捕获替换关系(paradigmatic)。在上下文的表示方面,我们分析了几种表示方法之后,发现可以通过模型复杂程度对这些模型进行排序。排序之后,实验结果就容易解释了:简单的模型(Skip-gram)在小语料下表现好,复杂的模型在大语料下略有优势。从实践中看,word2vec 的 CBOW 模型在 GB 级别的语料下已经足够好。我前面提到的 Order 模型,加入了词序信息,其实很多时候比 CBOW 更好,不过带来的提升并不大。

  语料方面,很多论文都提到语料越大越好,我们发现,语料的领域更重要。领域选好了,可能只要 1/10 甚至 1/100 的语料,就能达到一个大规模泛领域语料的效果。有时候语料选的不对,甚至会导致负面效果(比随机词向量效果还差)。文章还做了实验,当只有小规模的领域内语料,而有大规模的领域外语料时,到底是语料越纯越好,还是越大越好。在我们的实验中,是越纯越好。这一部分实验数据比较丰富,原文相对清楚一些。

  参数方面,主要考虑了迭代次数和词向量的维度。其实词向量都是迭代算法,一般迭代算法都需要多迭代几次。旧版的 word2vec 只迭代了一次,效果很受限制,换新版就好了(也欢迎用我们论文实验的方法,用 AdaGrad 优化,相比原版 word2vec 的学习速率下降法,这样还能在之前的基础上继续迭代)。然后迭代次数怎么选呢?机器学习里很常用的迭代停止指标是看验证集的损失是否到达峰值,认为这个时候模型开始过拟合了。按照这个方法,我们可以从训练语料中分出一个验证集看损失函数的变化。但是实验中我们发现,这种策略并不好。主要原因就是,训练词向量的目标是,尽可能精确地预测目标词,这一目标和实际任务并不一致。所以更好的方法是,直接拿实际任务的验证集来做终止条件。如果实际任务做起来很慢(比如 NER 任务的开源实现大概做一次要两小时),文章还给了一种参考的方法,随便挑一个任务当验证集用,一般都比损失函数靠谱。
  词向量的维度则只有一些实验结果。做词向量语义分析任务的时候,一般维度越大效果越好。做具体 NLP 任务(用作特征、用作神经网络初始化)的时候,50 维之后效果提升就比较少了。这部分的结果很依赖于具体任务的实现,或许用上了更先进的神经网络优化方法,词向量作为初始值带来的影响又会有新的结论。

—————-枯燥结束的分割线—————-

  完全公平以及全面的比较是很难做到的,我们也在尽可能尝试逼近这个目标,希望这些结论会有用。请批评指正。当然,也非常非常欢迎引用~~~~~

  一直觉得量子计算很神秘。从各种消息看来说什么量子计算机利用平行宇宙来计算,有超强的并行能力,穷举解决一切问题等等。真是越听越玄乎。维基百科和知乎上的一些解答还是看得让人茫然。

  几天前上古神犇JYY推荐《Algorithms》一书的第十章作为量子计算的通俗入门读物。阅后豁然开朗,不敢独享,略做笔记。

  普通计算机一个比特(bit)可以表示 0 或者 1。而量子具有不确定性,这使得一个量子比特(qubit)需要描述成 $ \alpha_0 \left|0\right\rangle + \alpha_1 \left|1\right\rangle $(量子比特的 0 状态记作 $\left|0\right\rangle$,1 状态记作 $\left|1\right\rangle$),其中 $ \left|\alpha_0\right|^2 + \left|\alpha_1\right|^2 = 1 $。也就是表示了这个量子比特有 $\left|\alpha_0\right|^2$ 的概率是 $\left|0\right\rangle$,有 $\left|\alpha_1\right|^2$ 的概率是 $\left|1\right\rangle$。这里面的 $\alpha_0$ 和 $\alpha_1$ 都是复数,所以要先取模再平方才是其概率(感谢 @shuyechengying 的指出)。
  推广到两个量子比特为: $ \alpha_0 \left|00\right\rangle + \alpha_1 \left|01\right\rangle + \alpha_2 \left|10\right\rangle + \alpha_3 \left|11\right\rangle $。同样系数的模的平方和为 1。

  这里就能看出量子计算的 NB 之处了,普通计算机 $n$ 比特可以描述 $2^n$ 个整数之一,而 $n$ 个量子比特可以同时描述 $2^n$ 个复数(一个 $2^n$ 维的复数向量)。

  如果仅仅是有表达向量的能力,传统的向量机就可以搞定。量子计算机之所以能成为量子计算机,更在于其对于量子比特的特殊计算操作。一个很著名的计算单元是 Hadamard gate,输入 $ \alpha_0 \left|0\right\rangle + \alpha_1 \left|1\right\rangle $,输出 $ \frac{\alpha_0 + \alpha_1}{\sqrt{2}} \left|0\right\rangle + \frac{\alpha_0 – \alpha_1}{\sqrt{2}} \left|1\right\rangle $。不要小看这个操作,即使仅仅对 $n$ 个量子比特中的第一位进行了 Hadamard gate 运算,所有的 $2^n$ 个系数都会改变(书上有简单的证明)。这里有个量子纠缠的概念,没去深究了,大意就是量子的特性会让这些运算比向量机的逐元素运算要强大很多。

  最后,薛定谔的猫要出场了。怎么把计算结果从混沌的量子态变成我们可理解的结果呢?这就需要“观测”。每次观测,量子就会塌缩到 $\left|0\right\rangle$ 或者 $\left|1\right\rangle$,按照 $\left|\alpha_0\right|^2$、$\left|\alpha_1\right|^2$ 的概率。反复测几次就知道结果了。但可惜的是,量子存在一个 No-cloning theorem,这就导致了我们不能简单地“反复观测”量子计算的结果了,而需要反复计算+观测。

  借助量子计算机,FFT 的复杂度可以降低到 $O(\log ^2 (n))$,甚至连读一遍数据的 $O(n)$ 时间都不用,因为只要 $log(n)$ 个量子比特就可以描述 n 维向量了。利用高性能的 FFT,因子分解的复杂度可以达到 sub-exponential time [Shor’s algorithm],RSA 加密就失效了。

  但是传说中量子计算机目前还是不能有效地解 NPC 问题,可以参考维基百科 BQP 的介绍。

  总结一下,从我目前理解来看,量子计算的优势主要在因子分解上(借助更快的 FFT)。对于传统的 NPC 问题,量子计算机目前还是束手无策的。当然这种强大的表达能力和计算能力还是非常有潜力的。

  我也就看懂了这些,至少不觉得量子计算这么无敌了。最后,还是建议看原书,写的非常清楚。

  这篇博客是我看了半年的论文后,自己对 Deep Learning 在 NLP 领域中应用的理解和总结,在此分享。其中必然有局限性,欢迎各种交流,随便拍。

  Deep Learning 算法已经在图像和音频领域取得了惊人的成果,但是在 NLP 领域中尚未见到如此激动人心的结果。关于这个原因,引一条我比较赞同的微博。

@王威廉:Steve Renals算了一下icassp录取文章题目中包含deep learning的数量,发现有44篇,而naacl则有0篇。有一种说法是,语言(词、句子、篇章等)属于人类认知过程中产生的高层认知抽象实体,而语音和图像属于较为底层的原始输入信号,所以后两者更适合做deep learning来学习特征。
2013年3月4日 14:46

  第一句就先不用管了,毕竟今年的 ACL 已经被灌了好多 Deep Learning 的论文了。第二句我很认同,不过我也有信心以后一定有人能挖掘出语言这种高层次抽象中的本质。不论最后这种方法是不是 Deep Learning,就目前而言,Deep Learning 在 NLP 领域中的研究已经将高深莫测的人类语言撕开了一层神秘的面纱。
  我觉得其中最有趣也是最基本的,就是“词向量”了。

  将词用“词向量”的方式表示可谓是将 Deep Learning 算法引入 NLP 领域的一个核心技术。大多数宣称用了 Deep Learning 的论文,其中往往也用了词向量。

继续阅读

  前几天看到同学写matlab代码时,随手写上tic、toc就记录了时间,甚感震惊——居然计时函数可以如此简洁。
  一般写 C 程序测速时,需要先记录起始时间,然后在结束时再次记录时间,并输出时间差。算起来要3行代码才能完成一个计时任务。一般用起来倒也不算麻烦,但是在寻找程序热点的时候,每几行代码就加入一段冗长的计时代码,会非常的碍眼。
  在此诱惑之下,我写了一个简单的计时器,使用时只需在开始计时时写上“tic”,后面每个需要计时的节点写上“toc”,在需要的时候使用“tictoc(stdout);”就可以输出各部分的运行时间。输出的格式形如“line 12-15: 0.87”。
  经过简单的预判断,程序可以支持 Windows 和 Linux,一般自己写点小程序够用了。
  程序也有一些缺陷,比如只支持单文件,不能在并行的程序快内使用。另外如果需要获得更好的精度及效率,Windows 下应使用 QueryPerformanceCounter(),Linux 下应使用 clock_gettime(),替代 getTime() 的实现。

  P.S. 如果想知道程序的热点,使用 Intel Amplifier 是一个很好的选择,可以看精确到行的耗时,也可以查看程序的并行程度,有针对性地提高性能。在官网上可以下载并免费申请一个月的试用 license。

继续阅读

  很久很久以前,当我想用 C 语言处理中文时,遇到了一些麻烦:C 语言中的 char 只占用 1 字节,但是 GBK 编码的汉字会占用两个字节。如果直接使用 char,会遇到一些非常神奇的问题,比如“页苑估”字符串中含有“吃饭”子串[1]。处理 GBK 编码其实也挺简单,判断一下,如果发现某个 char 的最高位是1,就和下一个 char 合起来考虑。偷懒的办法就是预处理一遍,把合并后的结果存到 short int(其实还有 wchar_t 这种专用的宽字符变量类型,使用时需要注意在 Windows 下是2字节,而在 Linux 下是4字节) 里,这样每个变量就可以表示一个字符了。

  当我知道 C#、Java 的 char 是一个 16 位的存储单元时,我就开始天真的以为“终于一个 char 可以表示一个汉字了”。虽然之后也听说了 C# 和 Java 中的 char 是以 Unicode 的形式存储的(确切的说,是 UTF-16),但是对一个 char 表示一个字符的观念,一直没有改变,直到昨天膝盖中了一箭……

  我在处理维基百科语料时,想统计一下里面出现了多少种不同的字符。随手就写了一个逐 char 的循环,统计之后输出 <char, 出现次数> 的二元组。 结果写文件的时候,抛出了这个异常:

未经处理的异常: System.Text.EncoderFallbackException: 无法将位于索引 551 处的 Unicode 字符 \uD86A 转换为指定的代码页。

  搜索良久,没发现有人遇到这个问题。只好开始猜想,是不是有些字符能用 UTF-16 表示,但不能用 UTF-8 表示?又或许有些 char 不能独立存在?

  第二个猜想在 Unicode 的官网找到了答案[2],同时也否定了第一个猜想:

The Unicode Standard encodes characters in the range U+0000..U+10FFFF, which amounts to a 21-bit code space. Depending on the encoding form you choose (UTF-8, UTF-16, or UTF-32), each character will then be represented either as a sequence of one to four 8-bit bytes, one or two 16-bit code units, or a single 32-bit code unit.

  里面涉及了两个要点。1. Unicode 编码的范围是固定的,Unicode 字符可以选用 UTF-8、UTF-16、UTF-32 这些编码方式来存储,也就是说这三种编码方式可以无损转换。2. 一个 Unicode 字符,在使用 UTF-16 编码方式存储时,会使用1个或两个码元(code unit),也就是 C# 里面的 char。

  于是有些Unicode字符,在 UTF-16 编码方式下,需要用两个码元来表示。在维基百科里找到一个例子:“𪚥”。这个字就需要两个码元来表示。UTF-16 把表示这种字的两个码元称作“代理对(surrogate pair)”,代理对由高位代理和低位代理组合而成,下面的 C# 代码展示了这个分解过程。

var str = "𪚥";
Console.WriteLine(str.Length);
Console.WriteLine(Char.IsHighSurrogate(str[0]));
Console.WriteLine(Char.IsLowSurrogate(str[1]));

  那是不是一个 Unicode 字符就是一个显示字符呢?答案居然是“否”!

  世界上还有“组合字符[4]”这种神一般的存在,最常见的一个肯定很多人都见过“ส้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้”。用来破坏排版的神器。这真的是一个显示字符,不信的话,你可以把它复制下来粘贴到 Word 里,看看是不是占了一个字符的位置。当然,一些比较弱的软件可能不能正常显示这个字符。组合字符一般是用来给拉丁文加重音符号等附加符号的,比如 Ä = A + ¨,也可以在一个字符后面加入一堆附加符号,形成刚才那个神器的效果。

  当然,C#这样的高级语言处理显示字符也是比较方便的,使用 StringInfo [5]类即可,比如下面的代码会输出 39、1。想要逐字符提取可以用 StringInfo 类中的其它方法,非常方便。Java 中应该也有类似的方法,没去调研。

var str = "ส้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้้";
Console.WriteLine(str.Length);
StringInfo si = new StringInfo(str);
Console.WriteLine(si.LengthInTextElements);

  最后,在@trouger 的帮助下,我们发现 UTF-8 编码[6]在多字节时,各字节的首位均是 1。利用这一点,如果我想用 C 语言写一个简单的程序,把 UTF-8 编码的文件按照空格分割(或者任意ASCII字符),直接使用 C 语言的 char 就可以完全胜任,无需考虑复杂的编码方式。

[1] 百度之星2007程序设计大赛 两场初赛题目点评 http://www.baiduer.com.cn/2007-06/1207.html
[2] UTF-8, UTF-16, UTF-32 & BOM http://www.unicode.org/faq/utf_bom.html
[3] 码元 – 维基百科 http://zh.wikipedia.org/wiki/码元
[4] 组合字符 – 维基百科 http://zh.wikipedia.org/wiki/组合字符
[5] StringInfo Class http://msdn.microsoft.com/en-us/library/system.globalization.stringinfo.aspx
[6] UTF-8 – 维基百科 http://zh.wikipedia.org/wiki/UTF-8

  最近做实验需要较大规模的中文语料,很自然的就想到使用维基百科的中文数据。

  使用维基百科做训练语料有很多好处:

  1. 维基百科资源获取非常方便,有 Wiki Dump 可以直接下载,所有的最新备份都在里面。最近的一次备份是3月底,也就是5天前。相比之下,其他很多语料都需要用爬虫抓取,或者付费获得。
  2. 维基百科的文档解析有非常多的成熟工具,直接使用开源工具即可完成正文的提取。
  3. 维基百科的质量较高,而且领域广泛(比较适合我要做的问题)。

  当然,缺点也有:最主要的就是数量较少,相比国内的百度百科、互动百科等,数据量要少一个数量级。

  直接切入正题。
  

第一步,下载中文的 Wiki Dump

  链接是:http://download.wikipedia.com/zhwiki/latest/zhwiki-latest-pages-articles.xml.bz2。这个压缩包里面存的是标题、正文部分,如果需要其他数据,如页面跳转、历史编辑记录等,可以到目录下找别的下载链接。
  

第二步,使用 Wikipedia Extractor 抽取正文文本

  Wikipedia Extractor 是意大利人用 Python 写的一个维基百科抽取器,使用非常方便。下载之后直接使用这条命令即可完成抽取,运行了大约半小时的时间。
  bzcat zhwiki-latest-pages-articles.xml.bz2 | python WikiExtractor.py -b1000M -o extracted >output.txt
  参数 -b1000M 表示以 1000M 为单位切分文件,默认是 500K。由于最后生成的正文文本不到 600M,把参数设置的大一些可以保证最后的抽取结果全部存在一个文件里。
  

第三步,繁简转换

  维基百科的中文数据是繁简混杂的,里面包含大陆简体、台湾繁体、港澳繁体等多种不同的数据。有时候在一篇文章的不同段落间也会使用不同的繁简字。
  解决这个问题最佳的办法应该是直接使用维基百科自身的繁简转换方法(参照 http://zh.wikipedia.org/wiki/Wikipedia:繁简处理)。不过维基百科网站虽然是开源的,但要把里面的繁简转换功能拆解出来,有一定的难度。
  为了方便起见,我直接使用了开源项目 opencc。参照安装说明的方法,安装完成之后,使用下面的命令进行繁简转换,整个过程大约需要1分钟。(opencc新地址 2016-10-11更新)
  opencc -i wiki_00 -o wiki_chs -c zht2zhs.ini
  命令中的 wiki_00 这个文件是此前使用 Wikipedia Extractor 得到的。

  到此为止,已经完成了大部分繁简转换工作。实际上,维基百科使用的繁简转换方法是以词表为准,外加人工修正。人工修正之后的文字是这种格式,多数是为了解决各地术语名称不同的问题:

他的主要成就包括Emacs及後來的GNU Emacs,GNU C 編譯器及-{zh-hant:GNU 除錯器;zh-hans:GDB 调试器}-。

  对付这种可以简单的使用正则表达式来解决。一般简体中文的限定词是 zh-hans 或 zh-cn,在C#中用以下代码即可完成替换:

s = Regex.Replace(s, @"-\{.*?(zh-hans|zh-cn):([^;]*?);.*?\}-", @"$2");

  由于 Wikipedia Extractor 抽取正文时,会将有特殊标记的外文直接剔除,最后形成类似这样的正文:

西方语言中“数学”(;)一词源自于古希腊语的()

  虽然上面这句话是读不通的,但鉴于这种句子对我要处理的问题影响不大,就暂且忽略了。最后再将「」「」『』这些符号替换成引号,顺便删除空括号,就大功告成了!

  通过上述方法得到的维基百科简体中文纯文本语料约 528M。

  半年没写博客。这次分享一下我的两份数据可视化的作品。
  强烈建议点击看原图,比缩略图好看多了。

一、好友关系图


  这个图是看了一篇报道(Facebook实习生画出全球好友关系可视化地图,下文称“原图”)之后抓取了国内一家社交网络的数据照着做的。
  其实原理非常简单,搜集了足够多的好友关系,及用户所在的城市,在这两个城市之间连上一条边。如果两个城市之间的好友越多,线也就越亮。和原作一样,最后会根据城市之间的距离衰减,距离近的城市,线条会亮一些。
  原图在我看来非常 cool,居然直接通过好友关系描绘出了海岸线,而我的这个图里无奈只能自己描上了国境线。可视化确实是数据分析的良师益友啊,在这个图里,也可以看到一些有趣的东西。比如线条最密集的长三角、珠三角;无数城市与帝都紧密联系;还有西部城市低调地和东部城市保持了千丝万缕的联系。
  为了方便查看,我把一些重要城市的地名也标上了,可以对照着挖掘一下。

二、北京吃货地图


  绝对不是打广告,但是看着这个图基本上就可以指导你,馋了可以去哪逛逛。
  数据来自大众点评的点评数据。每一份点评在店铺的位置做一次记录,然后使用 红-橙-黄-绿-蓝 的渐变色,根据每个地方点评的数据量,染上相应的颜色。最后叠加上地图,就成了。
  吃货们的集体智慧是不会错的,看图中西单、王府井、中关村、南锣鼓巷、后海、簋街、五道口、国贸,都一片红啊。
  还有另一个版本,直接计算方圆500米里的点评数,画出来就成这样。变得很Q了……

  这两幅图都是C#编程+PS画出来的,如果有人知道简单好用的可视化工具,恳请推荐一下。