10 月份的时候原来的域名过期了，没联系上数字游牧计划的人续费，于是打算自己买域名和虚拟主机。联系了几个同学一起买了个虚拟主机。
在 abcx 的推荐下到 godaddy 买了域名。淘宝上有卖 godaddy 的 e-gift card，这样就不需要能支付美元的信用卡就可以直接从 godaddy 的域名了，很方便。遗憾的是 godaddy 没有 .name 域名的注册，看到 .info 一年才 $0.99，于是就改注了一个 .info 的域名。放弃原来的域名还是有点遗憾，不过为了找一个国外的域名注册商而且要足够方便的话也只好这样了。
主机是麻烦 abcx 买的，购买流程就不清楚了。搞定的时候已经是 12 月，学期的最后一个月，各种作业、老板的任务、准备考试导致没有时间更新博客，只是把数据导了过来。在学校上外网要用代理，ssh 连不了外网，所以到考完试的时候也还是懒得去弄了。
就这样一直拖到昨天回家，终于可以把博客再弄起来了。
可怜我在南大浦口待了四年，没有见过计算机系的老教授徐家福先生（唉，孙钟秀先生也没有见过），今天在复旦因徐先生来讲座而得见！
讲座题目是“量子程序设计语言初探”，跟语言相关的东西我都有兴趣，更何况我也想见见徐先生真人。原来还在纠结要不要跷课去听徐先生讲座，结果睡过上课时间，于是有了名不正言不顺跷课去听讲座的理由。而施伯乐老师把原先上课的学生都叫来听讲座了，于是我这次跷课就算是得到了施老师的支持 :)
第一眼见到徐先生还是有点吓到了。虽然知道徐先生 1925 年 11 月生到现在已经是 82 岁高龄，但见到的时候还是担心他的身体状况还能不能给我们做讲座。先生开始讲座时才知道他刚去了 5 天东北，有点感冒，所以喉咙不是很好。这下自然更是担心了。
不过正式开始讲座以后发现这些担心其实还是多余的。先生虽然年级大，但是思路清晰，上来就说明今天讲座的内容，讲多少时间，然后就照着开始的介绍一路讲下来，讲完一段就进行回顾，不会有听着听着不知道讲到哪里的情况。大学里多数老师如果能像徐先生一样上课的话就是学生的福气了。徐先生解释问题简明扼要，定义的阐述也是精确到位，经常援引名家原话典故。没有记错的话他在 45 年去中央大学读书之前在复旦学英语（所以也算是复旦的校友），徐先生的英文不错，讲座时经常提醒我们有些容易读错重音的单词的发音。讲座唯一不足的还是徐先生的声音不够大，当然讲座教室没有准备扩音器实在失败。可能是为了考虑到坐后排的同学听不清，徐先生讲座时前后走动，虽然声音不太大，但是至少教室前半部分的人应该都能听到先生说话。80 多岁高龄的教授讲座依然不坐着，光这一点就令人感动了。
从徐先生身上能够看到什么是治学严谨，而如此高龄仍然做科研更是难得。徐先生说他也是在五年前才开始涉及量子程序设计语言领域，为此专门学了一年的量子力学。实在是佩服徐先生在 77 岁还去学一门没有接触过的学科的精神，我自己是对现在要学一点生物方面的东西就已经叫苦叫累还有点不太情愿，对比之下自然是很惭愧。
讲座中徐先生提到的一点有点令人无奈。中科大做量子计算机有了一点成果了，徐先生去看时发现他们的计算机要进行新的计算时要手工调整输入设备（类似最初使用打卡机编程的计算机），于是问他们能不能把这一步自动化。做这项工作的博士研究生说理论上可行，没有实际做一方面是因为没有大量经费支持，另一方面他们的主要任务不在这里，而是在把量子算法在量子计算机上实现出来，这样才能发出论文。徐先生对此的评论是做研究不应该是为了发论文，而应该是为了是对自然、社会做探索，等研究工作做好了，论文自然就出来了。话是没错，但现在的体制逼得人为论文而战，水文、没有意义的所谓研究工作大量存在。徐先生现在的身份恐怕是难以体会到发论文的压力了，他做研究是可以完全为了对自然、社会做探索，然而他如果还带学生的话，他的学生还是要为论文而战的。
（想起了钟扬老师讲过的 Bardeen, Cooper, Schrieffer 的故事。Bardeen 56 年第一次得了诺贝尔奖后找学生，给每个学生几个问题随便他选哪个做。Schrieffer 拿到这些题目后给他的老师看，他老师说这些题目随便哪个做出来差不多都能得诺贝尔奖。他原先不建议 Schrieffer 做 Bardeen 的学生，因为做那样的问题很可能读了几年之后没有出结果最后都毕不了业。（话说 Bardeen 第一个诺贝尔奖工程性质比较浓，他一直想搞个理论方面的东西再来证明下自己，他可以不管学生能不能毕业。）在知道 Schrieffer 当时还只是 26 岁的时候老师才让他还是去 Bardeen 那里试试吧，说大不了就是浪费这几年时间，反正你还年轻。好在 Schrieffer 也是够聪明的人，57 年开始做 Bardeen 学生以后真的解决了一个问题，结果 72 年的时候他们三人同时获得了诺贝尔物理学奖。做牛人的学生，自己不够了得就得有毕不了业的觉悟；要是自己也够牛，那样大家都好。）
讲座结束的时候连着问了徐先生几个关于函数式设计语言的问题，也算是跟徐先生讲过话了。在南大时留下的遗憾，今天算是弥补了一个 :)
有了 rebuild_db，你可以基本上像使用普通 mp3 播放器一样来使用 shuffle，不再需要 iTunes 那样臃肿的程序。需要注意的它只适用于 1/2 代的 shuffle，是否支持 3 代我没有测试过。可以用于其他 iPod 的类似程序叫 reTune，不过 sourceforge 上的页面貌似挂了。
rebuild_db 说白了就是用一个 Python 程序扫描 shuffle 中的 mp3 文件，然后更新 shuffle 的数据库使得 shuffle 可以找到并播放这些文件。
到这里下载，解压后把 rebuild_db.py 文件拷贝到 shuffle 根目录下就 OK 了。当然你的系统上得有 Python 才能用该程序。
shuffle 的初始化还是只能用 iTunes，这里是我的 2 代 shuffle 初始化后 iPod_Control 的备份，没有 iTunes 而数据库坏了的人可以拿去试试看，下载以后解压到 shuffle 根目录就应该可以了。
想要向 shuffle 添加音乐时只需比普通 mp3 播放器多一步：
建立数据库时程序对文件名的排列不是简单的字典序，对数字的话会根据其数值大小进行排序，这样就避免了 10 出现在 2 之前的情况了。
另外 rebuild_db.py 可以使用一些参数。我觉得重要的有 -r 重新命名文件，这样可以避免中文文件名可能造成的问题。（不过我的文件名都是英文的，所以不知道是不是中文一定会出问题。）
以下可以略过，很多无关紧要而且杂乱的小事而已。
写这个软件的作者不知道是怎么知道 shuffle 的数据库格式的，看了下 iTunes 目录下的文件都是二进制的。
以前给 shuffle 导 mp3 都是用 amarok。amarok 有两个缺点，一是启动慢，而是同步文件多的时候非常慢，不仅传文件慢，刷新数据库也慢。所以上次尝试了下 gtkpod。gtkpod 实在有点糟糕，UI 不好还不去说它，关键是同步的时候总是莫名的死掉，最后 shuffle 的数据库坏了，没法用了。我没 Windows 机器，就算有也懒得装 iTunes，所以想搜搜在 Linux 下修复 shuffle 的办法。修复的办法没有找到，搜到了 rebuild_db，而数据库是找了实验室的本科生 DD 修复的。然后对修复后的 iPod_Control 作了个备份，以后再坏就不用麻烦别人了。
最近败了个拜亚动力的 DT231 Galactic 耳机，最初的动机是实验室的机器 Think Center 的耳机接口在机箱后面，买长线耳机才行，二来是 shuffle 原配耳塞的橡胶老化了，被我扯掉了，第三是硬凑上来的，冬天当耳罩用。
看网上 N 多人说该耳机灵敏度低，用 mp3 难推。我现在就接在 shuffle 上用，音量稍微开大点就成了，没觉得有什么推不动的。要说推不好么我就不知道了，反正听协奏曲什么的气势比原配的耳塞大多了。第一次花这么多钱买一个耳机，对我来说总体效果也不错，银子没有白花。
很想去听 Hilary Hahn 10.19 上海演奏会，可惜复旦的票务西施 MM 没有弄到 90 元的学生票，280 的我可消受不起。省下的 90 块钱打算买 CD 去了。听了这么多音乐，总该多支持下唱片产业了。
很奇怪，本科毕业以后到现在没有多少话题冒出来让我想写东西。
暑假开始时看 Algorithms，书很有趣，讲解清晰，强烈推荐以这本书作为算法的入门教材。这本书让我对算法产生了兴趣，做习题的时候觉得有些收获，但这些收获太小，肯定不值得写出来。
暑假快结束的时候觉得无聊，就开始学 Haskell，觉得这是我见过最为优雅的语言。是的，虽然没有 Lisp 的 read/eval 这样令人赞叹的东西，但 Haskell 更加符合 lambda 演算，所以更为 consistent。个人觉得 Common Lisp 很多地方看起来很丑陋，而且为了利用现有的类库总是需要付出不少努力；而 Scheme 虽然更优雅，但太多的实现真让人无法适从。我没有怎么写过 Lisp 宏，没有很好的理解它，因此使用 s-expression 带来的最大好处我没体会到，反倒是觉得 Lisp 没有语法带来的是相对糟糕的可读性和冗长的代码，至少与 Haskell/Python/Ruby 相比。我觉得使用语法来简化代码，提高可读性是很重要的，Lisp 或许在这方面有最大的潜力，因为你可以针对特定问题构建特定的宏，但前提是你必须知道如何构造这些宏。花更多的时间或许可以获得这样的能力，但对 Lisp 现有实现和可以使用的类库的失望让我放弃了，特别在看到 Haskell 之后。HaskellWiki 上有 project euler 的解答代码，很多次看到别人写的简洁优雅的代码时激动的想写篇题目为 The beauty of Haskell 的文章，却发现自己没法写出那样的代码，也还没有水平能够写出对得起这样题目的文章，于是作罢。（Haskell 也可以写出丑陋的代码，但是用 Haskell 写丑陋的代码会非常痛苦，而且看到别人优雅的代码会刺激你也想写出漂亮的代码来，可惜我的脑子还没转过来，写个简单的程序还要想好久才能开始编码。）
开学以后比较忙，自己想做的事很多又只能停下来。研究方向定为生物信息学，得自学生物方面的一些知识，上数据挖掘和模式识别的时候发现要补习线代和概率统计（大四就想重学这两门课，可惜太懒），还要不少论文要看。估计以后只有零碎的时间能写文章，也不知道会不会像本科时经常遇到有意思的东西。
不过还是要坚持把博客写下去。最初写博客好像写了不少 Linux tips 之类的文章，这个写起来比较快，而且最近因为经常在宿舍登录实验室的机器，还有使用校园网的资源，学到了一些东西，所以最近准备写一些积累到的小 tips。The beauty of Haskell 会作为长期的目标。其他写什么就到时候看了，总之要努力成为一个好的 blogger。
CLRS 上对 Red-Black Tree (RBT) 的介绍简直是一团乱麻，代码又乱，解释又罗嗦，我完全没有实现它的兴趣……
不得不佩服 Robert Sedgewick 啊，他在 Algorithms in C 里先介绍 2-3-4 Tree，把 RBT 作为 2-3-4 Tree 的一种表示方式来介绍 RBT，这样就清楚多了。当然，Sedgewick 本来就是 Red-Black Tree 的发明者之一，他能够讲清楚也就不奇怪了。除了解释清楚以外，Sedgewick 使用递归实现，因此代码很简洁，看起来很舒服。
不过即使如此，Red-Black Tree 还是很复杂，所以即使看了 Sedgewick 的代码以后还是没有自己实现的冲动。好在 Sedgewick 已经考虑过这个问题，其结果就是 Left-Leaning Red-Black Tree。（这份幻灯片做得非常好！Apple 的 Keynote 貌似不错啊。）LLRBT 跟 RBT 的不同之处在于 2-3-4 Tree 的 3-node 在 LLRBT 中只有一种表示方式，因此 LLRBT 减少了 RBT 的插入/删除需要处理的情况数量，从而大大减小了复杂度。RBT 的 Java 迭代实现要用 150 行代码，而递归实现需要 46 行代码，LLRBT 递归则只需要 33 行。删除需要的代码行数也大大减小了，实现难度当然也大大降低了。
我用 Common Lisp 试着实现了 LLRBT，确实很简单。不过我还在想怎样才能迭代实现 LLRBT，找到了 FreeBSD 用头文件实现的 LLRBT，被彻底雷到了，这宏用的太牛了！
Update: 其实 LLRBT 是在好几个月前看到的，最近才想到写出来。FreeBSD 中 LLRBT 实现的作者 Jason Evans 写过一篇文章 ”Left-leaning red-black trees are hard to implement“，不过他写文章时候使用的算法中 4-node 对应 RBT 中向左倾斜的 3 个节点，可能因此比较难以实现。Sedgewick 在后来的幻灯片中更新了算法，4-node 变为平衡的三个节点。Evans 还比较了 LLRBT 和其他树实现的性能，在文章的注释中也提到了他将算法改为迭代所采用的办法。
很久没有更新博客了。做毕设的时候是没时间，做完以后是没了动力。六月马上就要过去了，再不写点这个月就没有文章了。
这次就偷个懒，发一份去年在 Linux 程序设计课上做演讲时所做的幻灯片吧，点这里下载。内容是关于 Unicode 和国际化的。制作这份幻灯片时参考了 Tim Bray 的几篇文章，UTF-8/UTF-16 的 RFC 文档，还有 Arnold Robbins 的 ”Linux Programming by Exmaple“。主要内容有：
wchar_t 和 locale 来解决国际化问题最早开始接触编码的问题是自己写文本编辑器的时候，为了支持中文才去了解这方面的知识。这份幻灯片准备的还是蛮用心的，花了一个多星期的时间。准备这份幻灯片的时候对编码之类的问题算是搞的比较清楚了，自己写的文本编辑器支持 UTF-8 编码了，后来碰到数据库链接、网页乱码之类的问题都可以猜出问题大概出在什么地方，看别人的解决办法也不会觉得不明不白。Unicode 的知识对于写程序来说还是很重要的，可惜老师不会讲这种东西（或许有些老师自己也不是很明白），只好自己花时间去弄明白了。希望这份幻灯片能给希望了解 Unicode 和国际化的人提供一些帮助。请原谅，幻灯片里中英混杂比较厉害。
PS：
毕业快一个星期了，不过最近还在南京待着。出去转了几个学校，除了南农以外，其他从中央大学分出去的学校都去逛了一下。南师的随园很不错，不过还是更喜欢金陵大学的北大楼。看过东南以后觉得当初南大把中央大学的四牌楼校区留给工学院，文理学院搬去金陵大学也不是太遗憾。不知当初设计出金陵大学北大楼的是何许人也，实在是佩服！唯一的遗憾是北大楼后面现在出现了两座高楼，大煞风景，真是可惜！
南大、东南、南师的老校区进校门都是非常相似的，都是两排高大的梧桐树，南林、河海的校区也有不少的梧桐。要说我对这几个学校校园环境的喜欢程度，南大为首，南师其次，东南和南林（学校里有不少漂亮的树林）并列第三，河海虽然为末，但也不错。
论文准备了两个星期，修改了好几次，今天终于答辩了。
记得去年查师兄答辩时穿的是红色 T 恤，今天我也特意选了红色的 T 恤，不过答辩的房间是 625 而不是 614。回想去年答辩时自己只是听众，而今天自己要作为答辩人，不由感慨时间过得真是快。
8:30 答辩开始。毕设是关于访问控制机制里的安全模型的设计和实现，这种东西 10 几分钟要想讲清没那么容易，而我为答辩做的准备也不是太充分，讲的时候感觉有点乱。感觉讲的有点挫，演示虽然很顺利，但是因为毕设的主要工作是在内核里，能看到的效果也就是 root 用户的权限被限制了，还有我们的访问控制机制确实是生效了。答辩的老师对访问控制之类的东西可能也不是很熟，没有问我什么太技术性的问题，问到的问题都轻松回答了。没想到就这么结束了，比我想像的要失败一些……
同时答辩的同学全部答辩结束以后老师讨论结果。等待的时候有那么一点点担心因为答辩时失败的表现而出岔子，不过公布结果时论文被刘嘉老师表扬为是这两年里本科一辩论文中他看到的最好的，听到这个称赞还是很开心的，不过也有点心虚。刘老师欠我的一件 IBM 的纪念 T 恤就此也不打算去追着要了，说不定他也记得这事，所以就故意表扬我一下，让我不再追究。
本科学业到今天就结束了，距离离校还有 20 多天。想起来下个星期还有一次小提琴课，这样算的话学业也还没有结束。然而总还是会要离开的，要好好珍惜最后这段日子了。
看到很多人在博客里谈这次博客，为灾区的人祈福，觉得自己什么连在博客上都没有写上些什么真是不该。
5.12 下午在机房写论文，三点的时候看到 Google Reader 订阅的草莓上有消息说有地震。开始时有点怀疑，后来看到的美国地震监测网站上的消息说震级有 7.5 级而且网上开始有照片发出来才开始相信。
遇难人数从刚开始确定的 2000 多人一下子飚升到 12000 多人，实在是太令人震惊了，第一次看到一次灾难能够在如此短的时间内夺去这么多人的生命！这种时候真的能够感觉到生命是脆弱的。
灾区的人们生活因此而遭到破坏，我这里一切都安然无恙，或许该感到庆幸吧。为如此之多同胞的遭遇感到同情应该是一个有心有肺的正常人都会有的情绪吧，然而除了祝福受灾的人以外无法直接为他们做些什么。学校开始组织捐款，下次去力行馆的时候把身上的零钱都捐出来吧。
昨天晚上去南京文化艺术中心听了维也纳爱乐弦乐独奏家乐团的音乐会，生平第一次听音乐会，也算是长见识了。
这个弦乐独奏家乐团一共 11 人，六个小提琴演奏家，两个中提琴和大提琴，还有一个低音提琴。（查了一下，低音提琴又叫大贝司，贝司指的是低音吉他。）宣传说这个乐团的主要成员来自维也纳爱乐乐团，去听的时候发现海报上的音乐家们比实际的看起来要年轻，估计海报上是很早以前的照片，而且其中有几个（大概是 3 个，都是小提琴手）比较年轻的面孔是海报上没有的。演奏曲目和宣传海报上的一样，莫扎特的 D 大调弦乐嬉游曲，罗西尼的弦乐协奏曲，巴赫的 D 小调双小提琴协奏曲还有柴可夫斯基的小夜曲。巴赫和莫扎特的都曾经听过，也是很喜欢的曲子，其他的两首都是陌生的。
买的是 180 的票，13 排，还算靠前，但在最边上，离舞台大概三、四十米的样子。因为是第一次听音乐会，所以也不知道昨天的音响效果究竟如何，总之比我用 iPod 听要好。而这个级别的演奏家我自然也是挑不出什么刺来，评论的话也没有那个水平。小提琴老师说乐队演奏要让声音像丝绸一样，昨天确实感受到了，看演奏家们一起配合演奏出动听的旋律出来是很享受的，也很赞叹他们的技巧。
现场的好处还在于可以看到音乐家们实际演奏的样子，看到他们如何用动作交流来配合。这些对我这样稍微学过一点小提琴的人来说也是很有趣的。一个细节是高个子的小提琴手坐着拉小提琴时不用把右腿向后挪，这个比较爽，可以坐的很舒服。另外一个细节是用脚打拍子的只有首席，而且只有在乐曲在节奏很快的时候才会打拍子。很羡慕他们的右手手腕在运弓时可以那样柔软，但是运弓又很有力。低音提琴手演奏起来也很有趣，运弓的方式跟其他提琴差别很大，弓子不用与琴弦相垂直运动，是一个可爱的大个老先生演奏的，得一直站着，难为他了。
上半场最后一首巴赫的双小提琴协奏曲演奏完三个乐章以后马上加演了一个乐章，不知道是哪首曲子（听不懂首席说的话），非常忧伤的一首曲子。同去的 Ann 第一次听巴赫的双小提琴协奏曲，很有感觉，而对加演的这首曲子更是感动。最后加演的三首中两首是施特劳斯的（施特劳斯跟维也纳爱乐乐团的关系果然不一般啊），一首是完全拨弦的（可惜我不知道名字），另外是一首波尔卡舞曲。拨弦的那首演奏时很有意思，演奏低音提琴的大爷原来站在舞台右侧，演奏时拿了一个声音像碰铃的乐器漫步走到乐队前面，随着节奏敲出了几声银铃一般的声音，而最后一下敲到了自己的手指，然后便回到原位，拿着提琴到舞台后面去了。乐曲快要结束的时候，老大爷又从舞台左侧出来了，在最后一个音的时候做了个很夸张的像是要摔倒的动作，实在是很可爱。加演的最后一首是闪闪的红星，听到如此熟悉的曲子全场都跟着一起用掌声来打拍子了。（这个好像也是维也纳爱乐乐团在新年音乐会演奏结束曲拉德斯基进行曲时候的惯例。）
听音乐会礼仪上还是有点讲究的，Ann 在这方面就比我在行，正装出席，而我连正装都没有一套，结果只能穿着休闲衬衫、牛仔裤和运动鞋去，好在周围的人多数也没有穿得太正式，不然就太突兀了。另外每一首曲子的乐章间隔时不该鼓掌，昨天虽然在开场前和第一首曲子结束后在广播中有告知听众，但还是有人在乐章之间鼓掌，只有到了最后一首小夜曲的乐章间隔，可能是由于曲子本身的原因，大家都不好意思去打破宁静的氛围而没有在乐章间隔鼓掌。而谢幕时怎样鼓掌表示请求加演，什么时候应该站起来 Ann 也不是很清楚，以后要找个行家扫盲。到了上海听音乐会的机会会比较多，到时候不能在这种事情上面丢人。
有时会 YY 遇到个会拉小提琴的女朋友。听过今天的音乐会想，如果如愿的话以后婚礼的时候和要和她一起演奏巴赫的双小提琴协奏曲。不过巴赫的曲子据说很难演奏，再加上要与乐队配合不是件简单的事，以上 YY 情节的最后一部分恐怕是没有机会实现了。最后贴一个巴赫的双小提琴协奏曲第一乐章的视屏。
今天谈下技术。介绍一个蛮有趣的数据结构 Ternary Search Tree，我毕设里的关键代码就依赖于这个数据结构。
这个数据结构的思路 1960 年左右就有了，不过其实际使用价值一直被忽略了。Jon Bentley 和 Robert Sedgewick 在 1997 年发表的论文 Fast Algorithms for Sorting and Searching Strings 中利用这个数据结构实现了针对字符串的快速排序和查找算法，网页上除了论文以外还有实现和测试代码。后来他们又专门针对 Ternary Search Tree 发表了一篇文章，Dr. Dobb 上有在线版本。我是在 Robert Sedgewick 的《Algorithms in C, 3rd edition》中 Radix Search Tree 这一章看到这个数据结构的，这本书将 multi-way branching tries 和 TST 放在一起进行介绍，把 TST 作为 multi-way branching tries 的另一种表现形式来看待，另外也将 TST 和 digital search tries 进行了比较。这里只是对这个数据结构进行概述，详细内容还是看作者的论文去。
Ternary Search Tree 的主要应用场景如下：字符串作为 key，每个字符串的长度不定，需要一种支持动态集合操作的数据结构以便能够快速的通过 key 查找到其对应的 value。用 hash table 的话可以做到快速的搜索，但是有两个缺点，一是随着保存的字符串的增多，需要重新构建 hash table 以保证快速的查找，二是 hash table 中不维护 key 之间的顺序关系。使用平衡 Binary Search Tree (BST) 两个问题都能解决，但是查找的速度相对 hash table 变慢了。如果使用 digital search trie 的话查找虽然非常快，但是需要的内存空间太大。
Ternary Search Tree 结合了 BST 和 trie 两者的优点，利用它还可以很容易的实现 partial-match searching, near-neighbor searching 这样的字符串搜索操作。而且 TST 本身非常简单，实现起来也很容易。与 BST 相比，TST 中每个节点存放的不是整个 key，而只是 key 中的一个字符。而对 tries，只需要进行一点小的修改就得到了 TST。（用 trie 描述起来比较方便，如果不知道 tries 的话可以先看下 trie 是什么。）
插入 key 的时候，从树根作为当前节点开始（树为空的时候树根为 nil），一个字符一个字符的递归执行下面过程。
搜索的过程和插入类似，把 key 一个字符一个字符的和树中节点保存的字符进行比较，同样从树根开始递归执行。
对 TST 性能的最坏情况分析在 “The Analysis of Hybrid Trie Structures” 这篇论文中，不过这篇论文下不到。对失败的查找，字符比较次数往往远小于其中包含的字符个数。使用 hash table 的话仅计算 hash 值就需要访问 key 中的所有字符（比如这里的 string hashing function），而且得到 hash value 之后还得检查 search key 与实际保存的 key 是否相等。所以 TST 的不成功的搜索比 hash table 更快。
论文的两位作者提供的 C 源代码里给出了迭代的插入和搜索的实现。对插入还作了优化，通过预先分配内存池的办法避免了内存分配成为性能瓶颈。对于数据的保存使用了一点 hack，通过 type cast 直接用叶节点的 mid 指针保存 value。因为 char 默认为 unsigned (至少 gcc 如此)，所以保存 ‘\0’ 的节点的 mid 和 left 肯定不会指向节点（right 节点可能指向树的节点），所以可以利用他们来保存 value。示例代码直接将 key 保存在叶节点中，但实际上 key 保不保存都没关系，除非以后要用到。对示例代码还有一点要说明的是递归版本和迭代版本有一点小差别，递归版本在实现遇到相同的 key 的时候会将新 value 的存入，而迭代的版本则不会。
对于 partial-match search, near-neighbor search 我就不罗嗦了，论文作者肯定比我说的清楚多了。我毕设里面使用的 search 也是标准 search 的一个小变种。我的 TST 中的 key 是文件系统的路径（假设文件系统用 UTF-8 编码，所以树的节点存放 char 就 OK 了），给定一个 search key (path)，如果 TST 中存有 search path 的祖先目录，我希望能够找到与之距离最近的祖先目录。用 TST 来实现这个操作也是非常容易的，有兴趣的可以自己想一下 :-)
TST 也有可以改进的地方。插入过程中，往往到了末尾的字符的时候树种的每一个节点都只有一个 mid 字节点，也就是所谓的 one-way branching，这导致了使用多余的空间，而且对于成功的搜索速度也不一定是最优的。一种改进办法是在接近字符串的尾部使用 multi-way branching 来减少需要的 node，不过怎样确定在什么地方开始 multi-way branching 比较麻烦，而且还要处理多种节点类型的情况。另一种方法是使用 PATRICIA 的思想，在每个节点上再存一个索引，表示其存放的字符是 key 中的第几个字符，比较的时候直接将其与 key 中的特定字符进行比较而不是一个一个的往下比较。这样一来减少了使用的节点，二来对成功的查找，如果保存着的两个 key 之间有几个连续的相同字符就可以跳过这些字符，直接跳到能够区分出这两个不同字符串的字符位置。但这样要求树中也保存 key，在找到节点之后还不要比较一下 search key 和 TST 中保存的 key 是否相同才能决定是否是成功的查找。
发现描述数据结构算法之类的东西还是挺麻烦的，看别人的文章的时候不觉得，自己写的时候就发现难了，也不知道写的能不能让人明白了。欢迎提出建议 :-)