前几天看到同学写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 -b 1000M -o extracted >output.txt
  参数 -b 1000M 表示以 1000M 为单位切分文件,默认是 500K。由于最后生成的正文文本不到 600M,把参数设置的大一些可以保证最后的抽取结果全部存在一个文件里。
  

第三步,繁简转换

  维基百科的中文数据是繁简混杂的,里面包含大陆简体、台湾繁体、港澳繁体等多种不同的数据。有时候在一篇文章的不同段落间也会使用不同的繁简字。
  解决这个问题最佳的办法应该是直接使用维基百科自身的繁简转换方法(参照 http://zh.wikipedia.org/wiki/Wikipedia:繁简处理)。不过维基百科网站虽然是开源的,但要把里面的繁简转换功能拆解出来,有一定的难度。
  为了方便起见,我直接使用了开源项目 opencc。参照安装说明的方法,安装完成之后,使用下面的命令进行繁简转换,整个过程大约需要1分钟。
  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画出来的,如果有人知道简单好用的可视化工具,恳请推荐一下。

  重要更新:在@老赵的提醒下,如果在请求中加入“Accept-Encoding: gzip, deflate”,下面的问题就会自动消失。具体见文章末尾。

  两年前我用C#写了一个爬虫类,一直在用。今天终于出错了。让我代码出错的页面是:http://www.hacker.org/challenge/solvers.php?id=1

  这个页面非常之强大,好多简单的爬虫都失效了,比如这段C#代码:

WebClient webClient = new WebClient();
webClient.DownloadData("http://www.hacker.org/challenge/solvers.php?id=1")

  还有php的curl(参考示例),以及Python的opener等,如果直接调用,都会中枪。

  当然,一般的浏览器都能毫无压力正常打开这个页面。

  用上述简易方式下载网页,最后都只能下载到 72k 的内容,但是实际上,这个页面有200多K。剩下的这个内容为什么不能直接抓取到呢?下面来分析一下这朵奇葩,并且给出解决方案。

继续阅读

  这是一个月前的比赛了。一直 YY 着能拿到奖金,直到膝盖中了一箭:事情发生在比赛的最后一天,神一般的提交都诞生于那天,直接破灭了我保住第五的希望。最后一晚上的苦逼挣扎由于编码速度太慢,也没完成理想中质的飞跃。总而言之就是好久不编程,高估了自己的实力,最后花了不少时间没刷到奖。

  简单介绍一下比赛的题目。这次马拉松是一个压缩问题。有一个 pH 测试仪的阵列,摆成 X*Y (其实就是 900*900)的方阵。仪器运行 L(L在60左右)个时间单位,每个时刻记录一下 pH 值。也就是说,一次实验一共记录了 X*Y*L 个实验数据。现在的任务是,压缩这些值,压缩率越高越好。比较有意思的是,比赛允许有损压缩,但是复原以后的值和原值的差、以及差的平方和都有误差限制。

我的方法

  观察数据发现,pH 测试仪里面每个测试点得到的测试结果,在总体上是连续的,不会有太大的变化。于是对于每个测试点的 L 个测试结果,可以采样若干点,并用插值算法对完成复原。
  于是就形成了这样的算法框架:

原始序列: d[0] ... d[L-1]
抽样其中的某些点:d[x_0], d[x_1] ... d[x_n]
用不精确的方式存储:d[x_1]-d[x_0], d[x_2]-d[x_1] ... d[x_n]-d[x_{n-1}], 以及d[x0]。 (x_0 = 0, x_n = L-1)
最后插值产生没存储的点

  由于存储的那些数据是使用 Huffman 编码的,重复的数字越多,压缩率就越高。在比赛中,我使用的“不精确的方式存储”是使用 val/t*t 代替 val。其中 t 是参数,一般在 8 到 20 之间。使用这种方式可以将相邻的 t 个数计入一个数,使用 Huffman 编码时压缩率会有显著地提高。
  这里同时要解决两个参数的优化,抽样的点集(对于每个位置的 pH 仪器使用相同的抽样点)、t。抽样点集可以使用 DP 算法求的在有 n 个抽样点时,最佳的抽样位置在哪(见参考文献,基本类似他的思路。实际上比均匀采点好不了多少,但还是用了)。确定了抽样点之后,穷举 t,找到符合精度要求的压缩率最高的 t。
  经过这两步计算,就可以得到一大堆 <n, t> 对的集合,有着不同的误差和压缩率。从中选取出最佳的搭配即可。最后使用的 n 一般在 10 到 20 之间。

  在实践中,直接对整个数据集进行优化,复杂度较高,不能在 10 秒内完成计算。我先从 X*Y 个仪器中抽样出 1000 个样例仪器,只对这 1000*L 个数据进行压缩,求得参考的 <n, t> 对集合,并选择若干个最优的跑一遍完整的数据,选择在实际数据集上符合误差要求且压缩率最优的。

  只有这些优化还不足以让我刚刚没奖,还有两个重要优化可以提升较多。
  1. 使用多棵 Huffman 树代替一棵树。观察数据可以发现,在各时刻,不同位置的 pH 仪器获得的结果是有一个总体趋势的,可能总体上涨,或者总体下跌。这样的话,在不同的时间用不同的 Huffman 树存储,由于数据的分布更集中了,压缩率会有提升。
  2. 对于某些特殊位置的 pH 仪,使用一套特别的压缩方式。在开放的数据集中,有些数据有一些 pH 仪测试出来的结果不符合主流分布。它们的记录结果随机震荡,非常不适合插值。如图 1 中第二行第五列的黑色区域。由于这部分区域非常难插值,选用较少的抽样点(n)会造成很大的误差(即便这只是 5% 的仪器造成的误差)。这个优化就是,对于这些特殊的位置,采用大量抽样点(甚至不抽样)的方式存储,当然 t 可以选取的比较大;同时对于大部分数据,仍然采用之前描述的方法存储。

  最后就是一大堆常数优化了,模运算打表之类。

  自认为这套框架已经走到基本极限了,从最后的结果来看也是。排在前面的人都有独到之处。

zaq1xsw2tktk 的方法

  赛后,我向 zaq1xsw2tktk 大神请教了他的方法。和我前面描述的方法基本类似,zaq1xsw2tktk 大神也是采样加上 val/t*t 的方式取近似值。不同的是,他在采样时,采样点非常的多,每隔一个位置就设一个采样点。由于采样点非常密集,求差时 0 会非常多。如果误差还没有超过阈值,则会修改某些值,使得连续的 0 变得更多。
  对于生成的差值序列,zaq1xsw2tktk 大神并没有直接使用 Huffman 编码压缩,而是先作了一步预处理。对于连续的 0,只存储 0 的个数。下面是一个 zaq1xsw2tktk 大神提供的例子:

0,0,0,0,0,10,10,0,0,0,0,-10
编成两个序列(5,0,4),(10,10,-10)
5个0 , 一个10 ,0个0,一个10, 4个0,一个-10

  预处理之后,再使用 Huffman 编码压缩,会有巨大的提升。

delicato 的方法

  delicato 在这场比赛中是毫无悬念地夺冠了,比赛排行榜的前面大概是这个样子的:

名次 成绩 handel
1 4143 delicato
2 2649 zaq1xsw2tktk
3 2490 Psyho
4 2479 Celebrandil
5 2204 davies
6 2156 venco
7 2089 licstar

  冠军的方法究竟是什么呢?其实我挣扎了这么久,早应该想到……裸的 SVD。不用多解释了,SVD 就是干这个的。(细节上 delicato 也对震荡激烈的特殊位置的 pH 值做了单独处理。)

总结

  对我来说,处理这种问题很重要的一步就是“看”数据,包括一行行地看,分析其中的关联等等。
  这次我用了两种比较简单的方法可视化数据,第一个图描述了 0 时刻各位置的测试值大小,颜色越亮表示值越大。里面的每个小图表示一个待压缩的文件。
  每张第二个图是相邻两个时刻各位置的变化情况,图片里的每个小图依次描述了某个文件不同时刻的变化情况。绿色表示值变小了,红色表示值变大了。如果仔细观察,会发现里面有比较明显的区域化现象,前面几个小图中能看出一些有规律的方块。另一个规律是变化总是从右下往左上推进的。这两点在比赛中并没有用到,或许能有好的方法可以用上各种数据特征,达到更优的结果。
  最后又回到老问题,遇事总是先 YY,吃了一次又一次的亏。什么时候才会先去找已有工作呢……

图1

图2

辛卯年乙未月己巳日,大局已定。仿三国演义,记下赛事五回。

第一回 山中有寨柠檬香,邪道异术出山狂
第二回 绝世秘籍未相传,独门小式败探花
第三回 光阴有痕巧破译,大象无形气莫测
第四回 山穷水尽疑无路,九易参数又一村
第五回 强强联合遇强敌,人品爆发显王道

继续阅读

  科研间隙,突然想验证一下@郑渊洁提出的公蓝北京、风蓝北京。遂从twitter上抓取美帝使馆数据,并做了一些简单的统计分析。
  统计数据为从去年11月21日至今的共100多天的空气质量数据与风力数据。先上图。


  在PM2.5随时间变化情况图中,我将数据分为工作日和非工作日统计(考虑节假日调休)。很明显,天亮期间休息天的空气质量要明显好于工作日的,从侧面体现了“公蓝北京”。在这样的统计规律下,把户外锻炼的时间安排到周末也是非常合适的~另外有个值得注意的,晚间的空气比白天明显要差,网上能找到很多介绍,如大气对流、植物的净化作用等等。不管怎样,在数据面前,早起锻炼和晚上睡觉前跑个步,都是不合理的。

继续阅读

  从一年前的计算语言学作业开始,我一直没明白,为什么我写的二元语法分词要比一元语法差。两天来我仔细分析了一下之前的实验细节,发现二元语法分词要超过一元语法,可以有两种方式:1.超大的语料;2.强大的平滑算法。

  实验采用北大人民日报1-6月语料,大约700万字,选其中90%作为训练数据,另外10%作为测试数据。先看下实验结果:

分词方法准确率召回率F值
最大正向匹配0.90400.91890.9114
一元语法0.92800.95020.9389
二元语法(+1平滑) 0.90930.92760.9184
二元语法(+eps平滑)0.91020.95290.9311
二元语法(删除插值)0.93170.96150.9463

继续阅读

  晒代码发布前,我们构想了 N 种吸引人来发代码的策略。后讨论认定,如果网站发布初期就有大量的代码作为基础,之后则更有可能吸引人来晒代码。就像某百科和某社区问答建站初期那样。

  本着这个目标,我试着用最简单粗暴的方法,尽可能多地从网上抽取出 ACM 代码。由于很多 ACMer 都会在网上开博客,博客里又很可能会写解题报告,有些解题报告会附上珍贵的 AC 代码。如果能把这里的 AC 代码都抽取出来,效果肯定会很理想。

  下面就简单介绍一下整个代码抽取过程。

系统框架

系统框架

继续阅读