电子书籍管理软件 – calibre

  calibre是一个免费的跨平台电子书籍管理软件,可以完成对各种格式的电子书籍的管理和格式转换。尤其对于拥有手机/iPad等电子阅读器或E Ink设备的同学来说,这个软件尤其具有价值。如果把电子书想象成MP3音乐的话,calibre的功能可以类比于iTunes。它还可以把网络上的新闻或RSS下载转换成电子书格式,同步到相关的阅读设备中,这是一个非常实用的功能。

  calibre可以从Google Books或Amazon等网站下载书籍的元数据,包括书籍的名称、作者、出版社、封面或者读者评价等信息。对中文图书而言,豆瓣上的数据应该是一个不错的书籍元数据来源,所以我就给它加上了这个功能。

  今天发布的0.7.7版本中正式具有了从豆瓣下载书籍元数据的功能,可以从“首选项”->“插件”->“元数据下载插件”中启用它。由于考虑到这个功能只对中国用户比较有价值,所以这个插件默认是被禁用的。

  本来还实现了从豆瓣下载书籍封面的功能,但calibre的作者不喜欢我的实现方法,所以还在进一步讨论合适的实现方法。需要尝鲜的朋友,可以参考我在Launchpad上的calibre-experimental代码树中的版本号为5550-5553的代码改动。

  对这个插件有任何建议或功能改进需求,可以在此留言或去calibre的Trac上提交一个Ticket。

常见字符串算法小结

最近周围很多人对字符串匹配算法比较感兴趣,特别是这次公司内部考试也可以认为是一个字符串查找的问题。

虽然字符串匹配看起来是个很简单、很成熟的问题,但在很多领域都有着很多的应用,比如模式匹配、特征提取等等。

这里对我知道的一些算法做些简单的整理,很不完善,有待改进~~~


1、  字符串匹配,即在字符串S中查找模式字符串P的出现

这个刚学过计算机的人也能写出代码,但事实上这个问题也可以子划分为若干特定问题域,比如,如果有单模式和多模式匹配问题(一个还是多个模式字符串,对于多个模式字符串的可以采用某些优化算法)

对于这类问题,最直接的想法就是在匹配时利用已获得的匹配信息尽可能多地跳过肯定不会匹配的部分,从而把复杂度从O(M*N)减少到线性复杂度。

教科书上的KMP(Knuth-Morris-Pratt)算是很成熟的一个利用这个思路的算法(作者之一就是Knuth大牛),最坏复杂度为O(M+N)(M和N分别为S和P的长度)

其他我知道的类似算法有BM(Boyer-Moore)算法(Snort系统中就用到了BM算法),最坏复杂度为O(M*N),最好复杂度为O(N/M),虽然看起来它的复杂度比KMP更高,但在实际应用中其效率比KMP更高,这也是为什么很多入侵检测系统优先选择BM的原因(理论复杂度和实际复杂度的差别还是很大的,比如最暴力的字符串匹配复杂度为O(M*N),也就是strstr的实现,可在实际应用中它的复杂度一般会退化到O(M+N))

另一个常见算法是WM算法,它的特点是适合于多模匹配问题。

很好的一个整理,大多数常见字符串算法集合:http://www-igm.univ-mlv.fr/~lecroq/string/index.html

WM算法的描述:http://hi.baidu.com/zcsong85/blog/item/8e3a22184c252b0335fa4156.html

2、  Suffix Tree

后缀树算是很常见的字符串数据结构之一了,它在模式匹配中的应用非常多,比如DNA序列检测等。

后缀树的基本思路是是对一个字符串的所有后缀子串以Tries的方式进行描述,从而可以迅速地在后缀树上找出字符串的任意子串。

所以对于已经建立了后缀树的字符串,做字符串查找已经算是非常简单的任务了,同时由于Tries的特点,这种结构可以很方便地处理前/后任意字符串匹配(比如“*ABC”和“ABC*”),为了要处理中间的wildcard,比如ABC*DEF,可以分别查找ABC*和*DEF,然后再取交集即可。

后缀树也很适合于多模匹配问题,但它适用的场景主要是待匹配字符串固定,而模式串未定的场景。

一个利用后缀树的典型应用是LCS(Longest Common Substring)最大公共子串问题。采用动态规划也可以很容易地解决LCS问题,但它的时空复杂度均为O(N*M),对于大多数应用是够了,可是,如果两个字符串是DNA序列,要从中间找出公共子串,O(N*M)的时空复杂度显然是无法接受的。而采用后缀树,复杂度就只是后缀树创建的复杂度,即O(N)

关于Suffix Tree的介绍可以参看:http://homepage.usask.ca/~ctl271/857/suffix_tree.shtml

3、  Aho-Corasick

Aho-Corasick自动机算法是一个非常高效的多模匹配算法,它的基本原理是对多个模式字符串构建有限状态机,而在源字符串中查找的过程则是一个状态机转换的过程。

它的最大缺点是构造状态机的复杂度较高,为O(KM^3)(K为模式串的个数,M为模式串的最大长度),但一旦构造后的查询效率则很高,为O(M*N)(N为源串长度)。

所以该算法很适用于多个模式字符串且模式字符串相对固定的使用场景(在Snort中也有使用),比如很多文本分类算法,需要在目标文本中查找活干特定关键字(features)出现频度,则可以使用A-C算法先对features建立状态机。

顺便说一下,linux下的fgrep也是利用A-C算法实现,虽然我也没想明白为什么需要?

http://en.wikipedia.org/wiki/Aho–Corasick_string_matching_algorithm

关于字符串还有很多其他有意思的话题,比如如何处理wildcard,如果进行regular expression的匹配,如何模糊匹配(在OCR中用到,Item被扫描成了ltem,如何纠正?),等等。

本文网址:http://zoufeiblog.appspot.com/2010/07/1/StrMatch.html

Posted in Uncategorized