文章归档

这个世界是我们的

土豆是我的兄弟,我们一起长大,一起上小学,上初中,高中,说的搞笑一点,是穿着同一条内裤长大的

土豆很有天赋,很小的时候就会拿着粉笔满屋子的画画而且画的有模有样,可惜爸妈都是农民,身边又没几个知识分子,土豆遇不上伯乐。书法也很好,小学 就已经拿过全国奖,不过没人栽培,现在也就马马虎虎了。还看过很多书,他曾经断断续续地拿过家里一千多块钱,然后全用来买书了,当然,他还不知到一千块钱 是很大一笔数目。他让我看得最多的是卡耐集的文集比如人性的弱点等等,可惜我识字不多,看的少。这些书,对土豆的成长有过很大的影响

土豆原本是农村里睡大街的小屁孩,后来考上了镇上的一所三流小学,四年级的时候又去到了镇上最好的中心小学,小学毕业后,考上了市里最烂的职高,三年后又考上了市里最棒的高中,大学,当然是比较烂了。这是他的人生曲线,土豆的故事太多了

土豆对数学出奇的感兴趣,我曾经翻看过他的手稿本,厚厚的一沓,泛黄的膜皮,渗水的笔迹,记录了土豆小学六年来对各种数学问题的思考与研究,比如,圆心在同一条直线上的连续圆,半径有什么关系

土豆初中的时候还曾经挂名到另外一个学校参加全国赛,拿了将了,后来就不得而知了。

土豆喜欢看书,不喜欢交朋友,性格不算孤僻但是喜欢独来独往,土豆的外号很多,比如化骨龙,因为他很瘦,又比如轻工水上飘,因为土豆不喜欢把时间浪 费在走路上,所以每次吃饭的时候跑得特别快,尤其人多的时候怎么跑都撞不到人,就得了这个称号。我也给他起过花名,因为他笑起来跟女人一个模样,不过他很 少笑,更多的时候,静静的一个人做自己的事

我曾经问过他咱们班上的人,谁谁谁啦,可惜很少有他答得出来的,他对他们很少印象,土豆甚至自己老师的名字都不知道。不过数学老师他是知道的,那个 时候土豆有过很长一段时间的辉煌历史,他对数学,知道的远比别人的多,他老是觉得老师讲的慢,磨磨蹭蹭的,就自己找书看,土豆第一次参加校内竞赛的时候, 考的有很大一部分都是超纲的题目,倒是对土豆来说没什么难度,结果他考了全校第一名,第二名是同班的,差了4分,大红纸贴出来的时候,大家一下子就爆炸开 了,因为第三名已经缩了二十多分了,也是因为这个事情,我和土豆认识了第一个朋友,阿飞,此后一路考试直至毕业,都是土豆第一,然后阿飞跟着第二,不过阿 飞英语要比土豆好。后来高中之后土豆去了高州中学,阿飞跳到了茂名一中,此后就更少有了联系

别人看来,土豆很成熟,懂得很多道理,待人处事方式很不一样,所以土豆虽然没什么朋友,但是很多同学喜欢悄悄地跟他聊心事,哪怕自己失恋了。有一件 事,对土豆的影响很大,这么说来,要追溯到小学的时候了,土豆经常受到班里某几个同学的欺负,而且有一个还跟着土豆一起上了初中。土豆后来跟我回忆说,因 为一件小事,本来不是土豆的错,但是土豆主动给那个人写了一封信,详细地写了很多事情并表示真诚的道歉,我问土豆,你有没有想过他看到这封信会觉得你更好 欺负,土豆说不知到,书上学到的,想尝试一下。很快那个人有了回信,静悄悄地放在了土豆的铅笔盒里,信里同样讲了很多事情,说,没想过你会给我写信,我想 他一定很感动,为了不是自己的过失却站出来向别人道歉,这是一种谦卑。土豆说,原谅别人,就是善待自己

土豆很有理想,虽然他不知到他的理想是什么,不过也正是因为这样,所以他才努力的让自己成长,有朝一日,可以看到外面的世界。我相信每个半夜起来沿着单车棚上厕所的人都忘不了那段奋斗史,一群在路灯下挑灯夜读,卧辛尝胆学子们,是土豆,民开,祖森他们,当然,还有我

土豆还曾经有过几个很好的朋友,就是所谓的四人帮,土豆,金海,健强,还有文家周,认识文家周是入学第一天晚上的时候,宿舍很热闹,家周和土豆是邻 床,两个人都不出声,土豆在听心灵地图,家周放着别安的歌,然后很奇异的一幕发生了,家周伸直两条腿,使劲往上蹬,手脚像个婴儿一样,土豆肯定觉得家周很 二B,两人相互对视了一眼,就这样认识了

之后,土豆和我上了高州中学,民开去了二中,祖森在一中,还有玮琪,在四中,其余的人,从此断了联系

土豆高一的时候曾经疯狂的迷恋过黑客技术,经常上课不听课就是经常抱着一本黑客X档案或者黑客手册之类的书籍在看,我记得他好像收过一个学弟,叫陈威,这件事说起来有点搞笑

土豆觉得自己水平还行,然后搞了一个团队,叫什么极度深寒二进制网络安全联盟,名字其实是从邪恶八进制那里来的,正好阿威那时候也正在看这类书,两 人一拍即合就成了拍当,土豆觉得光有团队不行,还得有团规,团章,当然了,肯定要收团费的嘛。于是土豆就跑去杂货市买了各种材料,连印章都叫人刻好了,前 前后后花了几百块钱。弄妥了就去找阿威,跟阿威说了入团的事,要了照片,还说,要收5元的团费,其实土豆本来不想收这个钱,只是觉得不收的话觉得阿威可能 怀疑自己是骗子,就象征性地要了5块钱,还跟阿威说,还有几个其他团队的成员,以后让你认识认识,其实谁也没有,土豆有意把团队搞的神秘一点而已,毕竟那 个时候能成为一名黑客是多么牛B哄哄的事情,后来每每我一想起这件事就觉得特别逗笑

土豆成绩倒退得特别厉害,期末考试的时候全科9门加起来都不够400分,我想很大一部分是因为这个原因。我找到土豆,跟他说,你现在看到的,真的是你想要的吗。我说你不应该把时间浪费在这里,如果你真的喜欢,就应该到更高的层次去深造,起码也等上了大学再说。我们触膝盖长谈,谈理想,谈了很长时间,最后土豆接受我的意见,把心思放回到学习上,争取考上好的大学。

土豆又开始过上了三点一线的生活,似乎比以前更安静,更忙了,土豆还是那样记不起班里同学的名字,甚至不常说话,只是在思考自己的问题,土豆学习很 有自己的一套方法,不像其他的同学,他做很少的习题一样可以有效果。相比盲目的去熟练那些公式,土豆更喜欢发现这些自然规律之间的内在关系,土豆更多的时 候是在想和总结。有一次土豆想的深了,想不出来,就去问老师,老师很惊讶,说思路没有问题,不过是微积分的问题,你们还没有学

慢慢地,土豆成绩回到了班上中上水平,高三的时候,已经稳定在班里全十名内,考个自己想要的学校已经不是什么问题了

不过,这个世界有时真会捉弄人,土豆的人生,一如有规律的跌宕起伏不断,我想,那年高考,如果不是因为那一场意外,土豆的人生也不会发生那么大的转变,也许今天,他也可以像很多人一样游走在ACM等赛场里大显身手甚至成为实验室的宠儿。

这一切,似乎与土豆无缘。高考结束后,土豆没有留下任何联系方式,连毕业照都没有拍,自己一个人背起包裹离开了,一走就是两年,杳无音信

再次见到土豆,是我已经快结束大二学业的时候,人在迷茫的时候是不是应该回到原点好好探讨一下,他说很庆幸终于找到自己的理想了,谈话间我还得知他恋爱了,我问他嫂子哪的,他说河南的,我笑着跟他说,那也好,两个人一起奋斗总比一个人更有力量

土豆此后陆陆续续来找过几次我,我察觉得出土豆的上进,他的好强,我有时笑他是平民科学家,土豆说,人离开了实验室,会不会就真的什么也做不出来,我说那当然不是,对土豆来说,所谓科学,是一种信仰,是学术自由

最近土豆一次过来,我们在学校的体育馆大汗淋漓地跑了几圈球场,吃完饭,我送了送土豆,回来的路上自己一个人静静的踹步在这个大学的校园里,上大学这么多年,很少有现在这样的心境了,想想我们过去的二十年,不禁感概万千

土豆来了短信,说:这个世界不止是有你们,我也可以改变世界

是的,只要不放弃,这个世界就是我们的

文本压缩的思考

最近断断续续花了很多时间在研究文本压缩领域,没有说是数据而是文本,是因为文本在特定的场合和环境可以有更大的改进和性能提升,比如基于 ASCII码和Unicode的就可以设计得截然不同,仅用一种方案来对不同的场景产生应用,是要付出一定的代价的比如性能。而且,不同的语言又会有不一 样的表现形式,这对垂直式的压缩技术来说是一种新的挑战。

因为业务需要,我希望可以实现一种更快的压缩算法,尤其是在解码方面要有不俗的速度表现。

我尝试过对哈夫曼编码进行一些细节上的改进,但是效果不太明显,哈夫曼编码的特点就是即使极限情况下也是能够保证绝对的压缩,当然能压缩多少倒是不 一定。编码过程比较块,难点就是对于这种比特流的存储方式,解码时必须单个比特地亦步进行,耗时特别长,是我不能接受的。研究算法远不是纸上谈兵那么简 单,不是随便在纸上画一棵二叉树就能解决问题领悟到信息论的奥秘。离开实际的应用研究不存在太大的意义,所以我们要清楚面临的需求以及对算法作出何种改进

 

lz77算法比传统的范式哈夫曼可能花费的时间更长一些,毕竟哈夫曼编码只需执行一次遍历就可以统计出编码模型而lz77则需要花费更多的时间在建 立字典和回溯检索上面。不过,lz77最大的特色就是解码特别的快,与其他编码相比解码速度完全不在一个数量级上面。lz77及其变种大部分的实现都是等 长编码,是建立在字节级别上的,不是比特流,本质上速度就有很大的优势。更重要的是,lz77每解码一个字符只需向前查看一次滑动缓冲区,总的时间复杂度 是Θ(n),线性

Gzip就是lz77很成功的一个例子,不过,网上说的那点也太简单了简直不值一谈,Gzip精妙的地方在于对算法做了很多有利的改进,我猜的,因为不管我怎么设计,以及优化,总是赶不上gzip的速度,事实证明,gzip真的很优秀

在滑动窗口也就是字典的设计上,我没有使用哈稀表而是用了一个二维数组来对任意字符进行索引,一方面我懒得搞那么复杂,而且二维数组似乎更加直观因为我主要基于单字。数组保存了对在滑动窗口里出现的所有字符的索引,而且采用了插入排序来改善查询的性能

到目前为止,整个实现最值得探讨的问题,在于滑动窗口的大小以及设计能够匹配的最大的长度,是关乎压缩效果最重要的一方面

从语言的角度来看,中文又不同于英文,英文里最常见的字符如 the,of,to,and 等在极短的滑动窗口里也可以有很好的匹配效果,但是中文就不一样了,还要取决于不同字符集的实现,滑动窗口要更大一些。这里就回出现一个性能项瓶的问题, 窗口规模与匹配的最大长度是成线性比例关系的,如果滑动窗口设计的太大,即使能匹配到好的长度,程序也要花费太多的时间在Match上面,而且大量的数据 可以表明,不是所有的字符串都能够找到最优匹配的,很多情况是,在小的窗口模式下,比如31或者63,能匹配成功的平均长度是1到2位左右,也就是说,2 个比特就足以完成保存匹配长度的工作,默认我设置了3bit,是因为我发现3bit的长度和31的窗口更有压缩上的优势

最终的测试结果是,相比较gzip的实现,压缩大约80M的文本语料库,平均时间为 1.413s,解压为 0.248s,压缩率是48.5%,而gzip的测试结果是,平均时间为 0.998s,解压为 0.131s,压缩率达到25%

我一直很好奇gzip是怎么做到的,如果我用多线程的话效果是不是会好一点。

目前所知,硬件层来说使用磁盘阵列可以提高io的效率,对压缩也是有好处的。

块排序压缩的数学原理

也叫 BWT 转换,严格来说不属于一个压缩算法,是压缩领域的辅助技术,BWT 的目的仅仅是将信息转换得更加适合压缩而已。BWT 巧妙的地方在于,只要精心设计,除了增加少额的计算量外,没有任何其他的开销。因为他的输出仅仅是将原有字符的排列顺序作了特定的安排

为了描述方便,举个简单点的例子,比如,即将处理的序列是 S = abraca ,S 的长度 N = 6,将 S 向右旋转一位,S 的末尾移动到 S 的首部,形成一个新的序列 S’ ,再将 S’ 向右移动一位再次产生新的序列 S”,重复这个步骤,直到得到一个 N*N 的矩阵 M,对 M 按字典排序,得到 M’ ,取矩阵 M’ 的最后一列作为输出,如下:

注意上面红色的 # 号,是一个辅助转换的结束符号,目的是为了标记原序列 S 属于 M’ 中的第几行,这个很重要,如果不使用结束标记符,就必须另外维护一个索引值,排序结果也会不一样,但是最终还原的字符序列是相同的。

逆转的过程更有意思,也非常简单,我们知道输出的序列 L=#rcaaba,L是表示矩阵 M’ 的最后一个序列,同理,F 是第一个,逆转的过程是从 L 恢复到整个 M’ 的过程,#号所在的 Row 就是原字符序列 S,因为 M’ 经过字典排序,自然 F 也是有序的

定理:对于包含 N 个字符的任意序列 S,按照 BWT 规则产生矩阵 M,对 M’ 进行字典排序得到 M’,假设 F 是 M’ 的第一列字符,L 是 M’ 的最后一列字符,若 F 是有序的,则 L 是唯一的。

从转换的过程我们知道,对于矩阵 M’ ,每行,每列所包含的元素都是相同的,也就是说,不考虑字典序,F 与 L 中的所有字符都存在一一对应的关系 T,在这里 L=#rcaaba ,所以 F=aaabcr#,则 T={6,5,4,0,1,3,2}

T 的计算过程有个需要注意的地方,L 与 F 中不是每个字符都是唯一的,也许有 N 个字符 value 相同,但是其实 index 不一样,L

»» 继续阅读全文

Crash

这是一部多元探究人类的心里与情绪反映的细腻之作。

故事透过地方检察官一家,经营商店的波斯商人,墨西哥锁匠,两个劫车混混,一个菜鸟警官与中年韩籍夫妇……

等等这样的角色,在短短36个小时间

经由间接,直接,甚至是不经意的互动,呈现出人们在不同时间与场景之中的情绪反映,以及这些情绪反映的联动关系对人们的命运、态度与观点所产生的影响 ……

“ ……

你知道,在很多城市里,你和别人擦肩而过,或者偶尔别人撞撞你。可是在洛杉矶没有人会碰到你的身体,我们总是躲在钢筋和玻璃的后面。或许是我们太怀念那种触感,以致需要通过剧烈碰撞才来体会得到…”

正是这部电影所要传达给我们思考的主题

香农熵与大脑学习

信息是个抽象的概念,我们常说信息很多或者很少,但是很难说清出信息到底有多少,比如一篇800字的文章有多少信息量。

直到 1948 年,信息论之父 C. E. Shannon 在其发表的论文 A Mathematical Theory of Communication 中第一次将热力学的熵引入到信息论,并用数学语言阐明了概率与信息冗余度的关系。

在通信领域,大家知道,通信链路传输的是比特流,通信的双方均会事先遵守某种人为约定,比如,00 表示“我”,01 表示“爱”,10 表示“老”,11 表示“婆”,所以如果 A 给 B 发送 00011011,B 就会知道 A 说了一句话:“我爱老婆”

Shannon 指出,任何信息都存在冗余,冗余大小与信息中每个符号(数字、字母或单词)的出现概率或者说不确定性有关。什么是冗余,冗余就是多余重复的东西,比如,通 信的 A 端给 B 连续发了 1000 次 00011011 比特序列,那么就有 999 次是多余的,实质上 A 只需给 B 传输一次,然后告诉 B 要重复多少遍就行。

举个例子,系统 S 内存在多个事件 S = {E1,…,En},每个事件可能出现的概率为 P = {p1, …, pn},则每个事件本身(信息本体)的量为: Ie = − log2pi(对数以2为底,单位是比特(bit))

如英语有26个字母,假如每个字母在文章中出现次数平均的话,每个字母的信息量为:

而汉字常用的有2500个,假如每个汉字在文章中出现次数平均的话,每个汉字的信息量为:

这就是 Shannon 的理论信息极限,相比使用 utf-8 字符集来传输,每个英文字符可节省的极限信息量是 8 – 4.7 = 3.3bit,而汉字则是 24 – 11.3 = 12.7 bit(注:在 utf-8 字符集里,用 8 bit来表示一位英文字符,用 24bit 来表示一个汉字) 。

-------------------------------------------------------------------------------------

OK,如果你能明白我上面说的,那就可以想得到,事实上信息处理的过程和大脑学习是多么的相似,人脑包括两个功能体,一个负责存储信息,一个负责处理信 息。今天我只想讨论大脑如何接受新知识的过程,假设信息的本体是“知识点”,这就有,人脑的学习过程其实就是不断存储新知识点的过程。

但是不同的大脑,对新知识接受的方式不同,等同与上面提到的通信约定,在计算机程序里相当于你取决于何种信息处理的算法。不同的算法,处理结果是不 一样的,比如说,你不一定要约定 00 表示“我”,你可以这样假定,0 表示“我”,100 表示“爱”,101表示“老”,然后 110

»» 继续阅读全文

格式化字符串

这是在 mozilla open source 代码里发现的一个问题,目前还不确信是不是个BUG

c99引入了uintptr_t,uintmax_t 这样的标准数据类型,我们知道 printf() 函数对于常见的数据类型都有一个对应的 length modifier 用于格式化输出,int 的是 d,ptrdiff_t 的是 t,但是对于非标准的 pid_t,uintmax_t 等就没有对应的 length modifier 了。在c89的世界里,解决这种问题的常规化方案是强制类型转换到尽可能大的整数类型,比如这个 pid_t,POSIX 只要求它是一个 signed integer type,所以转化成 long 就OK了:

C++代码

  1. pid_t pid;
  2. printf("%ldn", (long )pid);

不过,c99新引了另一种方式,就是使用宏来替代 length modifier,例如 uint32_t,uintmax_t 可以使用 PRIu32 和 PRIuMAX,这些宏可以在 <inttypes.h> 中看到其定义(在 glibc 源代码中对应 sysdeps/generic/inttypes.h)。有兴趣的可以直接去看一下源代码,其实就是对已有的 format conversion 进行的宏封装。显然,第二种方式更优雅,但最近发现了一种更加优秀的方式,虽然看起来绕了一些弯路

C++代码

  1. /* Make sure BUFSIZE is large enough. */
  2. #define UMAX2S_BUFSIZE 21
  3. static char *
  4. umax2s(uintmax_t x, char *s)
  5. {
  6. unsigned i;
  7. /* LINTED */
  8. assert(sizeof(uintmax_t) <= 8);
  9. i = UMAX2S_BUFSIZE - 1;
  10. s[i] =

    »» 继续阅读全文

深入浅出c指针

指 针(pointer)是对“数据对象或函数”的一种引用,它记录了一个“对象或函数”的“内存地址和类型”。通俗地说,指针是一个变量,为了区分普通的变 量(普通的变量内存空间存储的是数值,而指针存储的却是计算机内存空间的某个地址),网络上很多资料对这个概念的叫法不一,有时叫指针,有时叫指针变量, 实质上都是同一个东西,指针本身就是一个变量,指针变量从语法的角度上看算不算重复累赘?

指针有很多用处,灵活性极强,比如,在C里,如果需要处理大量的数据的话,使用指向数据的指针比直接处理数据本身更经济和高效,又比如,你不需要移动内存中的数据就能对大量的记录进行排序,此外,利用指针,还能实现各种甚至非常复杂动态数据结构等等

声明指针

通常来说,指针的指向一般有几种:非数组对象,数组对象,函数,我们后面会更进一步地讨论“指向数组和函数”的指针,现在首先来看看,如何声明一个“指向非数组对象”的指针,语法描述如下:

C++代码

  1. type * [类型的限定符] 名称 [=初始值]

在 声明中,type * 不同于 type,type 表示需要声明的是一个普通变量,而 type * 声明的是一个指针,该指针指向 type类型的对象 ;[]表示参数具有可选性,比如 [=初始值] 表示在声明对象的同时初始值是可有可无的;类型的限定符,一般有const,volatile,restrict 等,关于指针类型的限定符,可以自行参考,这里不做详细描述;名称被声明为一个指针对象,其数据类型为 type * ;

举个例子,声明一个指针p和变量k: int *p; 在上面这个声明里,我们可以得出很多有用的信息:

  1. p是指针,而不是 *p
  2. int * 是指针的类型,而 int 是指针所指向的类型,int * 的意思是说,我所指向的对象的数据类型必须为 int (当类型不一样时,某些编译器可能会进行隐式转换)
  3. 指针p 是一个变量,在32位机里,有4字节长的内存空间

在讲解指针的之前,我们先来解释一下有关指针的几个重要而且容易混乱的概念:

  1. 指 针:指针是一种非常特殊的变量,特殊的地方在于,一方面指针的内存空间并非用来保存有效数据,而是存储着另外一个对象或者函数的内存地址;另外一方面,不 管指针所指向的对象类型是什么,指针作为变量,自身的内存空间大小是一样的,换句话说,char * 型和 int *型的指针所占用的空间大小相同,在32位的计算机上,通常是4个字节长,刚好32位
  2. 指针的类型:既然指针也是变量,自然有自己的数据 类型,不同的是,普通变量的类型描述是 type ,而指针的类型描述是 type * ,指针的类型只有一个作用,它给计算机指出了自己所指向的必须是什么类型的对象,事实上,如果你强行将int *类型的指针指向一个 char 类型的对象,那么编译器会发生隐式类型转换
  3. 指针所指向的类型:如果这个指针是指向对象的,那么指针所指向的类型就是该对象的类型;如果这个指针是指向一个函数的,那么这个指针所指向的类型就是该函数的返回值类型
  4. * :要区别 * 的两种用法,在表达式里,* 是间接运算符,比如,对于指针 p ,那么*p的运算结果就是指针 p 所指向的对象的值(计算机是这样计算的,遇到 *p 指令时,p是指针,然后读取变量 p 的值,把这个值作为一个内存地址,寻址到这个值所在的内存区域,再读取出这个区域所存储的数据 β,那么 β 就是指针 p 所指向的对象的值);而在指针声明里,* 并不是运算符,而是声明符的一部分,它给计算机指出:我要声明的是指针而不是普通变量
  5. & :取址运算符,意思就是说,可以取得一个对象的内存地址,但是也有值得注意的地方,比如:假定变量 k 的数据类型是 char ,那么 &k 的结果产生一个 char

    »» 继续阅读全文

毕业细语

高考结束,没有毕业典礼,同学们都陆陆续续回家了。有很多人还会回来,但也有不少人,将很少回来,甚至也许再也不会回来。或许,很难再见到他们了。 整个学校也安静下来了,难得的宁静。 教室里顿时变得空空荡荡。往日的人、书,如今都离开了。往日熟悉的笑脸也都离开了。这里,肯定还会热闹起来,但已经不再是我那60个昔日同窗了。望着仅剩的桌子和凳子,感觉心里很失落。就这样结束了?桌子和凳子,黑板和粉笔,你们的静默,是否也是在失落与感伤? 或许因为安排的事情太多没有时间,或许因为我自己不知道从何开口,所以,毕业了,也没有和同学们正式说过离别感言、赠言什么的。是否有些不够完整? 只顾着给他们写毕业留言,居然忘了把我的毕业纪念册也给他们,请他们写留言给我。真是不该! 毕业,说明我们长大了,学到了不少东西。这是好事!应该高兴! 但愿,在三年里,作为他们人生中的过客,能落幕他们心里依稀的回忆。 祝愿,他们在未来的日子里,继续健康成长,道路越走越宽,创造美好的未来!

第 13 页,共 13 页« 最新...910111213