BLUEFLY

It’s been long time ago when I decided to build an online collection of dictionaries and after much effort novadict.com has come online finally during this national day vacation. Thanks to those who helped me around the internet and it didn’t take too much time to make this possible.

All the resources were gathered from internet and the only additional work was to clean up the data and make a user interface. What I was proud about was that the data I’ve gathered are very detailed and comprehensive and novadict.com is very competitive to be the biggest online collection of dictionaries ever in history (Note that only Simplified Chinese and English related terms are opened for the time being).

Due to large datasets have to serve and very limited hardware capacity (only 180MB RAM and limited CPU resource), novadict.com can’t be stable. Lots of optimization work has been done including specialized term searching index and hash based key-value storage engine, and it was still a very challenging job to make any improvements within such limited environment. It also has affected my standalone blog site hosted on the same box.

One of the reasons why I created novadict.com is the open and share spirit, though it is still much of personal interests. Hopefully novadict.com could be helpful to you. Have fun.

This blog post tries to document the babylon glossary(dictionary) file(.bgl) format specifications. The BGL files are not much encrypted or protected and basically they’re just gzip compressed files.

Some demonstrations are coded with PHP. Python or C might be better but PHP is enough to do this job and has syntax similar to C that can be easily understood by most programmers.

1. File signatures and gzip header

Babylon files start with 4-byte signatures:

• 0×1234001  indicates it was released officially by babylon
• 0×1234002  indicates it’s third-party generated
• 0×1234003  .bdc file, seems kind of uncompressed glossary file. *NOT tested yet*

The bytes at offset 0×04 and 0×05 are 2-byte unsigned short integer points to gzip header, and from that header the rest of the file are gzip compressed. Note that BGL uses big-endian for all.

Here is the PHP code to decompress a BGL file:

2. The decompressed BGL file consists of records, and each record has a 1-byte header. The low nibble of that header indicates the record type and the high nibble holds indication of record length, with the following rules:

• high nibble >= 4: subtract 4: that is the length
• high nibble < 4: add 1: that is the number of following bytes for the record length (big-endian)

The code to get record length:

After tested lots of BGL files the following record types are identified:

• 0×00
• 0×01  term
• 0×02
• 0×03
• 0×04
• 0×05
• 0×06
• 0x0a  term
• 0x0b

1. 0×01 and 0x0a are for term entities, and are the most often used types. This kind of records can be divided into three parts: term, definition and alternatives. The term part has a 1-byte header for length, and the definition part has a 2-byte header for length(big-endian), and the rest are alternatives. Within the alternatives parts each alternative has a 1-byte header for its length. (Note that not all the terms have alternatives)
   The code to get term, definition and alternatives:
   
   A well organized definition (here ‘well organized’ means the officially released BGL file) usually has two sections (and in this order): translation(or explanation), attributes(optional, not necessary). 

   ***the following part was not distilled from reverse engineering and not strictly tested***

   There is usually a 1-byte delimiter (0×14) between the two sections in a definition. Here the first occurred char(0×14) is used as real delimiter(0×14 might also appear as length indicator). There will be no attributes section if no delimiter is found.

   The PHP code to separate translation and attributes:
   

   The translation(or explanation) section normally is texts with different encoding; Each attribute within the attributes section has a 1-byte specifier, structured as described below::

   • high nibble < 4 : low nibble is attribute id:
     • high nibble ==0 : the following 1 byte is attribute value
     • high nibble > 0 : the following 1 byte indicates the length for attribute value
   • high nibble >=4 : the next following 1 byte is attribute id
     • specifier > 0x4f : attribute is the rest
     • specifier <= 0x4f : subtract 0x3f, that is the length for attribute length

   The PHP code to extract all attributes:
   

To be continued

something about double array trie tree with xsplit and text similarity calculation

之前发布了一个PHP的分词扩展xsplit(http://code.google.com/p/xsplit)，只是在主页简单说了一下用法，下面再做点实用解释，不讲理论。

xsplit的分词实际上主要是基于双数组trie树的结构，算是trie树的一个变种，常用做搜索树，也是一种确定有限自动机（deterministic finite automaton）。顾名思义，双数组trie树利用数组保存状态，效率也更高一些（数组的操作效率比复杂的数据结构高）。trie树一般在NLP（natural language processing）用的较多一些。

xsplit作为一个PHP扩展，最初主要是考虑到当时的应用场景以web居多，并且采用PHP作为上层逻辑控制语言，使用上比较方便，开发效率更高一些。当然也可以作成Python，Ruby等的扩展。xsplit同时也提供了基于双数组trie树的操作接口，common prefix search和exact match search。

common prefix search的理解很简单，比如有一句话叫“中华人民共和国”，在我们的词典里有“中华”，“中华人民”，“中华人民共和国”这三个词，如果用以下函数：

$result=xs_search('中华人民共和国', XS_SEARCH_CP);

这时就会得到“中华”，“中华人民”，“中华人民共和国”这个三个词，因为他们有共同的前缀（prefix），这就是为什么叫common prefix search。

如果是exact match search

$result=xs_search('中华人民共和国', XS_SEARCH_EM);

则只会返回“中华人民共和国”这一个词，也就是所谓的精确（exact match）查找（完全匹配）。

这两个功能，在统计词频或者做一些基于双数组trie树的应用时非常有用。

另外，xsplit还加入了simhash和hamming distance的计算，这个是计算文本相似度有用到的。印象当中这个还算是比较棘手的问题，无论是聚类还是自动分类，似乎都是机器学习（machine learning）像什么SVM用到的比较多。而基于simhash的计算，原理比较简单，效率要高很多，处理大规模数据的时候比较有优势。

这些都可以参考Google的一篇论文： http://research.google.com/pubs/archive/33026.pdf

传统的hash算法，同样的数据或者同样的文本，可以得到相同的一个hash value，这对于检查文本是否完全相同比较方便。但是对于相似的文本，比如两段文字，他们只是少量的个别词语不同，如何计算相似度就比较麻烦了。而simhash的作用就是，相似的文本会有一个相似的hash value，这里的相似不是说他们的大小差不多，而是hamming distance很小。关于hamming distance，汉明距离，可以看一下百度百科的解释 http://baike.baidu.com/view/725269.html，不难理解。

实际上，simhash在计算的时候，需要将文本tokenize（呃我现在也不知道tokenize中文里到底怎么理解好，分词？分解？）。英文一般就是按照空格分开，中文的话还是需要分词，如果按照单个汉字来计算，效果很不理想，这个我都有实验过。中文除了分词，还需要将无用的标点符号，特殊符号等等都去掉，这些对simhash的计算都有影响。另外，simhash在计算的时候，还支持每个token设定权重，比如在中文里就是给某些关键词设定较高的权重，我试了之后发现效果似乎不升反降，所以在xsplit里每一个token的权重都是相同的。这也是我为什么把simhash的相关计算函数放在一个分词扩展里的。

这个东西有什么用？举个很简单的例子，我有一个site可以让每个用户提交新闻（比如digg之类的），但是我不想用户提交重复的新闻。于是在数据库里保存的时候，每一条新闻有一个simhash的字段，当有用户提交新的news的时候就去数据库里利用simhash检查一下，如果相似度过高，就禁止提交或者是待审核状态。这样就大大减少了重复信息。

看到这里也许有的朋友会问，每次提交都去检查相似度，还需要计算hamming distance，当数量很大的时候岂不是会有效率问题。是会遇到这样的问题，除了刚才的遍历，还有就是用类似枚举的方法。如果hamming distance的阈值为3（这是实际检验有效的阈值），一个simhash是64 bit，所有小于等于3的组合大概有40000多，这样就把每次计算的probe控制在40000多次。但是如果数据规模仍然很大的话，这还不是一个理想的方法，具体怎么解决，请读一下刚才贴的那个Google的paper里的第三章吧，内容很详细，全文最后还有个比较。

偶然发现了这个帖子，http://www.phpx.com/thread-121134-1-2.html，居然根本没有印象自己曾翻译过关于CakePHP框架的介绍。看日期是2006-7-22，放到这里留个纪念吧

The CakePHP Framework

前几天要做一个tcp server，本想用twisted，却发现官网无论如何也打不开，以为被墙，便用了node.js。大概只用了一天多点的工作时间和600多行代码就完成了一个小型的tcp server，感觉不错，就对node.js稍作了一些了解。

先简单介绍一下node.js。从源码的deps可以看出，三方依赖主要有

• libev
• libeio
• v8
• c-ares
• http_parser

node.js实际上就是v8引擎（去除DOM部分）+ 异步网络IO模型 + 少量必要的三方类库。

v8大概不需多说，应该是目前最出色的Javascript引擎。v8实际上是ECMAScript（ECMA-262）标准的一个C++实现，常见的Javascript是一个遵循ECMAScript标准的脚本语言。这里需要稍微澄清一下，很多人在看到Javascript时，非常容易局限在浏览器中Javascript的概念，其实这只是一种语言在浏览器中的应用——Javascript跟lua，python，PHP的层级差不多——all scripting languages。个人感觉ECMA标准的脚本语言用起来还是很不错的，用来搭建上层的应用逻辑非常方便。

异步网络IO模型及其相关实现近几年一直是热门话题，可以看这里和这里，个人感觉基本上就是epoll/kqueue + 单进程。这种模型在实际中也很常见，redis，nginx，haproxy也都是这样的结构。

看得出node.js并不复杂：一个很流行的语言引擎 + 一个很流行的网络IO模型，所以用它做东西，应该是不错的开发效率 + 不错的运行效率。由于Javascript的特性，使得的node.js对HTTP支持很好，但这次做的实际上一个tcp server，接受的数据是二进制数据流（HTTP是纯文本），一些细节需要注意。

• 如果数据是二进制数据，使用net类库创建server时，需要设置socket.setEncoding(‘binary’)，以保证接受的数据是二进制流；同样，写数据时需要socket.write(response, ‘binary’)，保证发送的数据是二进制。其官方文档（目前0.4.7）只提到了ascii，utf-8和base64三种encoding，实际上还有ucs2和binary模式。
• Javascript本身是一种弱类型语言，对于unpack和pack二进制数据并不是很方便，可以使用这里的一个类库jDataView，用起来挺方便的。
• node.js好像并没有CRC的类库，可以用一些纯Javascript的实现，查看这里。另：貌似一些叫做CRC-ITU的算法，实际上是FCS，CRC的一种，frame check sequence，一个16 bit的checksum。
• node.js的MySQL库不少，试了很多，由于并不习惯ORM类型的，感觉node-mysql-libmysqlclient用起来还不错。

总的来说，node.js很潮也很年轻，需要更完善的发展和支持，具体表现如何还需实际应用后再定。

PS:

node.js常用modules：  https://github.com/joyent/node/wiki/modules

node.js的一些资源： https://github.com/joyent/node/wiki/Community

npm： https://github.com/isaacs/npm

/*

偶遇Serenata Immortale (相关专辑)，听来颇有回味，遂将相关制作公司的资料稍做整理，方便感兴趣的朋友了解。所有内容均来自互联网，并进行了翻译与整理。与Immediate Music类似的公司还有Two Steps From Hell，X-ray Dog，Audio Machine，Epic Score等，网上也有不少比较完整的相关音乐资源可以找到。总的来说此类音乐的气势比较恢弘，场感和现代节奏感强，有点史诗般的风格，偶尔听下也算是别有一番风味。

*/

Immediate Music是位于洛杉矶圣摩尼卡的一家音乐创作公司，为各种商业电影预告片提供高端的音乐而为人所知。 自1992年起，Immediate Music开始为好莱坞的各大工作室提供音乐素材，其中一些较著名的电影包括《地狱男孩》，《阿凡达》，《钢铁侠》，《加勒比海盗》，《鬼妈妈》，《吸血鬼助手》，《X战警》，《黑客帝国》系列，《狼人》以及《哈利波特》系列。

2007年，Immediate Music公司因在20届冬季奥运会上为各种体育节目提供音乐而被授予Emmy奖项。2008年Immediate Music获得BMI award奖项。

由于在电影预告片音乐制作方面的积累、影响和启发，Immediate Music公司成立了自己的摇滚乐队，叫做Globus。Globus乐队曾在英格兰的温布利成功的举行了演唱会，并以此为契机在美国相继进行了表演。

2009年6乐27日，Immediate Music举办了一场叫做《Trailer Music Live》的音乐会，由一个完整的交响乐队（大型管弦乐队）和合唱团进行了表演，曲目包括《加勒比海盗》《蜘蛛侠》《指环王》等电影预告片中的音乐。Globus乐队也进行了献唱。

公司创始人之一Yoav Goren对这场音乐会做出如下评价：“演出在伦敦获得了空前的热情，这让我们感觉有必要将这场演唱会带入美国。大规模的管弦乐队、合唱团以及摇滚乐队，将电影中的音乐从荧屏搬上了舞台，磅礴恢弘的气势，史诗般的意境，现代音乐的节奏感，《Trailer Music Live》给各个年龄段的影迷带来了一种独特的体验与享受”。

Immediate Music对外公开发行的专辑并不多，包括：

《Immediate – Trailerhead》2008

《Trailerhead – SAGA》2010

以及Gloubs的一张专辑

《Globus – Epicon》2009

最近抽空把之前做的一些小工具整理了一下，放到Google Code上open source，一方面是想与大家分享一下，一方面是想或许能够让更多的人参与进来，一起把它们做的更好。

这两个小project，一个是全文检索相关，一个是中文分词相关，说起来其实差不多，但力求做到简单、实用。其实这两个project在中文检索，以及中文相关的处理方面还是蛮有用的，关键在于怎么用和一些外围的配套工作，这里就不再多说了。

sphinx-for-chinese: http://code.google.com/p/sphinx-for-chinese/

sphinx是一个性能不错的C++全文检索引擎，大概它的优势就是比较专注性能和与MySQL的结合。sphinx-for-chinese实际上是对sphinx添加了中文分词模块。中文分词采用MMSEG算法，在算法实现和一些细节上下了很多力气，我想它大概是最快的MMSEG实现之一了。

xsplit: http://code.google.com/p/xsplit/

一个中文分词的PHP扩展，基于MMSEG算法，也提供正向最大匹配方法，可以在分词的时候指定不同的资源，并提供基于双数组trie树的一些字符匹配功能。个人感觉xsplit的优势，一个是分词速度快，再一个就是功能完善、灵活，使用简单一些，并且提供信息相似度simhash的计算，加上PHP扩展的形式，能在很多领域里方便使用。