原帖的地址在stackoverflow.com List of Free Programming books (compiled): How to Design Programs: An Introduction to Computing and Programming 25 Free Computer Science Ebooks Free Tech Books MindView Inc (List of Free Books) Wikibooks: Programming Cheat Sheets (Free) CodePlex List of Free E-Books Book Training – On Video! Sofware Program Managers Network – Free EBooks EBook Share [...]
原文地址：http://docs.jboss.org/netty/3.1/guide/html_single/ The Netty Project 3.1 User Guide The Proven Approach to Rapid Network Application Development 3.1.5.GA, r1772 序言 1. 问题 2. 方案 第一章. 开始 1.1. 开始之前 1.2. 抛弃协议服务 1.3. 查看接收到的数据 1.4. 响应协议服务 1.5. 时间协议服务 1.6. 时间协议服务客户端 1.7. 流数据的传输处理 1.7.1. Socket Buffer的缺陷 1.7.2. 第一种方案 1.7.3. 第二种方案 1.8. 使用POJO代替ChannelBuffer 1.9. 关闭你的应用 1.10. 总述 第二章. 架构总览 2.1. 丰富的缓冲实现 [...]
一般来说，我们会使用正规表达式来做字符串匹配，今天在网上浏览的时候，看到了有人用正则表达式来检查一个数字是否为素数（质数），让我非常感兴趣，这个正则表达式如下所示： /^1?$|^(11+?)\1+$/ 要使用这个正规则表达式，你需要把自然数转成多个1的字符串，如：2 要写成 “11”， 3 要写成 “111”, 17 要写成“11111111111111111”，这种工作使用一些脚本语言可以轻松的完成。 一开始我对这个表达式持怀疑态度，但仔细研究了一下这个表达式，发现是非常合理的，下面，让我带你来细细剖析一下是这个表达式的工作原理。 首先，我们看到这个表达式中有“|”，也就是说这个表达式可以分成两个部分：/^1?$/ 和 /^(11+?)\1+$/ * 第一部分：/^1?$/， 这个部分相信不用我多说了，其表示匹配“非空串”以及字串中不只一个“1”的字符串。 * 第二部分：/^(11+?)\1+$/，这个部分是整个表达式的关键部分。其可以分成两个部分，(11+?) 和\1+$，前半部很简单了，匹配以“11”开头的并重复0或n个1的字符串，后面的部分意思是把前半部分作为一个字串去匹配还剩下的字符串1次或多次（这句话的意思是——剩余的字串的1的个数要是前面字串1个数的整数倍）。 通过上面的分析，我们知道，第二部分是最重要的，对于第二部分，举几个例子， 示例一：判断自然数8。我们可以知道，8转成我们的格式就是“11111111”，对于(11+?)，其匹配了“11”，于是还剩下“111111”，而\1+$正好匹配了剩下的“111111”，因为，“11”这个模式在“111111”出现了三次，符合模式匹配，返回true。取反（^），所以，得到false，于是这个数不是质数。 示例二：判断自然数11。转成我们需要的格式是“11111111111”（十一个1），对于(11+?)，其匹配了“11”（前两个1），还剩下“111111111”（九个1），而\1+$无法为“11”匹配那“九个 1”，因为“11”这个模式并没有在“九个1”这个串中正好出现N次。于是，我们的正则表达式引擎会尝试下一种方法，先匹配“111”（前三个1），然后把“111”作为模式去匹配剩下的“11111111”（八个1），很明显，那“八个1”并没有匹配“三个1”多次。所以，引擎会继续向下尝试……直至返回false。 通过示例二，我们可以得到这样的等价数算算法，正则表达式会匹配这若干个1中有没有出现“二个1”的整数倍，“三个1”的整数倍，“四个1”的整数倍……，而，这正好是我们需要的算素数的算法。现在大家明白了吧。 下面，我们用perl来使用这个正规则表达式不停地输出素数：（关于perl的语法我就不多说了） perl -e’$|++;(1 x$_)!~/^1?$|^(11+?)\1+$/&&print”$_ “while ++$_’ 另外，让我们来举一反三，根据上述的这种方法，我们甚至可以用正则表达式来求证某方式是否有解，如： * 二元方程：17x + 12y = 51 判断其是否有解的正则表达式是：^(.*)\1{16}(.*)\2{11}$ * 三元方程：11x + 2y + 5z = 115 判断其是否有解的正则表达式是：^(.*)\1{10}(.*)\2{1}(.*)\3{4}$ 大家不妨自己做做练习，为什么上述的两个正则表达式可以判断方程是否有解。如果无法参透其中的奥妙的话，你可以读读这篇英文文章。 转自 cool shell ： http://coolshell.cn/?p=2704
翻译来自：唐福林 博客雨 http://blog.fulin.org/2010/05/vp8_first_in_depth_tech_analysis.html 注1：文章来自：http://x264dev.multimedia.cx/?p=377 ，一个 H264 开发者对 VP8 的深入分析。 注2：在Google翻译基础上试译，不足之处请多包涵，欢迎各种建议和意见 The first in-depth technical analysis of VP8 首次深入技术分析 Back in my original post about Internet video, I made some initial comments on the hope that VP8 would solve the problems of web video by providing a supposed patent-free video format with significantly better compression than [...]
转自： http://blog.i5un.com/item/21 翻译自Mozilla的网站。 这篇论文讨论了组合三种不同的检测方法来实现自动字符集检测。 A composite approach to language/encoding detection) Shanjian Li (shanjian@netscape.com) Katsuhiko Momoi (momoi@netscape.com) Netscape Communications Corp. [ 注：这篇论文最初发表在19届国际Unicode会议(19th International Unicode Conference)(San Jose)。那以后，我们的实现经受住了时间和实际应用的检验，并且，我们还作了许多改进。一个主要的变化是我们现在使用正序列来检测单字节字符集，参见 4.7和4.7.1节。这篇论文写于通用字符集检测代码集成到Moailla主代码前(参见第8节)。自此以后，字符集检测代码被合并到了代码树中。如想 查看最新的实现，请在Mozilla的代码树中查看相应代码。作者 - 2002年11月25日。] 1.概要： 这篇论文提供三种自动检测的方法来判定无明显字符集声明的文档的编码。我们将分别讨论每种方法的优点和缺点，并且提供了一种复合后的，更有效的方法 来检测编码，这样，三种检测方法就可以互为补充。我们认为自动检测在使浏览器用户避免经常使用编码菜单手动选择编码上很有用，同时在编码菜单很少出现的情 况下，提供了更合理的处理方式。我们假设，文档转化到Unicode对用户是透明的。无论字符编码采用的是某种Unicode编码还是本地编码，用户仅需 知道字符最终显示是正确的就行。好的自动编码检测能有效的帮助用户处理大部分的编码事项，而无需用户手动参与。 2.背景： 自从进入计算机时代以来，人们创造了许多使用计算机数据表示的编码方案来表达不同的文字/字符集。随着全球化和Internet的发展，跨语言和区 域的信息交换越来越重要。但是现存的多种编码方案对此是一个屏障。Unicode提供了通用的编码解决方案，但是，迄今为止，各种各样的因素使它并没有代 替现存的区域编码方案。除了W3C和IETF建议使用UTF-8作为缺省编码，比如XML，XHTML，RDF。因此，现今的国际化软件不仅要处理 Unicode编码，还要处理其它多种不同的编码方式。 我们当前的工作是在开发Internet浏览器的环境中开展的。为了处理如今Web上使用不同编码的各种语言，我们做了许多努力。为了获取正确的显 示结果，浏览器需要利用HTTP服务器返回的编码信息，网页或者是最终用户通过选择编码菜单而得到的编码方式。此外，大部分用户没有能力手动的通过编码菜 单来进行操作。如果没有编码信息的话，网页有时就会显示为“垃圾”字符，用户就无法得到他们想要的信息。这最终会导致用户认为他们的浏览器有故障或有 Bug。 由于越来越多的Internet标准协议指定Unicode作为缺省的编码方式，网页将会不容置疑的转向使用Unicode来编码。好的通用自动检 测方法可以对这种转向提供重要的贡献，因为它们工作很自然，无需用户使用编码菜单。在这种情况下，渐进的转向将会以用户不易察觉的方式进行，这是由于，对 用户来说，网页总会显示正确，他们无需考虑使用编码菜单。这种平滑的转变将使编码对用户来说越来越不需要关注。自动检测在这种场景中将很关键。
12530 PC客户端 咪咕 (页面最下方有一个很不显眼的下载链接) 搜索 原本计划是今天上线内测，20号正是随资源库后台一起上线，其实昨晚就已经替换掉了正式服务器上原来的接口。正因为昨晚悄无声息的上线，原本已经下班走到 家门口的我们，又被电话叫回公司，来解决一个刚刚发现的bug。 音乐搜索，第一期还没有特别做歌词的搜索，只对歌手名，歌曲名，专辑名做优化，加上数据量本身就很小（一共才不到100万首歌），只好在查询上做文章。我们当前一共设置了十层查询 Query： 1。精确匹配：歌手，歌曲，专辑，不分词字段，去掉前后多余空格，精确匹配 2。过滤后的精确匹配：歌手，歌曲，专辑，过滤字段，去掉所有特殊字符，英文转成小写，精确匹配 3。拼音全量匹配：歌手，歌曲，专辑，拼音全量字段，去掉所有非英文字符，英文转成小写，精确匹配 4。同音纠错匹配：歌手，歌曲，专辑，拼音全量字段，只对含中文的搜索词使用，中文转拼音，英文转小写，去掉所有特殊字符，精确匹配 5。拼音首字母匹配：歌手，拼音首字母字段，中文转拼音首字母，英文转小写，去掉所有特殊字符，精确匹配 6。前缀匹配：歌手，歌曲，专辑，不分词字段，去掉前后多余空格，英文转小写，前缀匹配 7。分词Must匹配：歌手，歌曲，专辑，（歌词），分词字段，分词，词之间使用Must连接，分词匹配 8。分词Should匹配：歌手，歌曲，专辑，（歌词），分词字段，分词，词之间使用Should连接，分词匹配 9。合并分词匹配：歌手＋歌曲＋专辑 分词字段，分词，（当前使用 Should 连接），分词匹配 10。模糊匹配：歌手，歌曲，专辑，分词字段，去掉前后多余空格，英文转小写，模糊匹配， 包含中文时模糊度：0.65 全英文模糊度：0.85 其中模糊匹配还分了两级： a 拼音纠错 b 模糊查询，包括中文模糊和英文模糊（模糊度不一样） 当前拼音模糊是使用组合的办法来实现的： 1。建索引的时候，拼音全量字段里建的是字段的准确拼音，包括多音字的组合 2。搜索的时候，将用户输入的关键词转成拼音，在拼音全量字段里搜 3。模糊的时候，将用户输入关键词转成的拼音，按照模糊规则：n-l 互换，zh-z, ch-c, sh-s 互换，an-ang, en-eng, in-ing, on-ong 互换，每次只换一个（当前只支持模糊度为1的拼音模糊查询），如果有多个可以替换的点，则返回的结果为一个数组组合，然后使用 精确匹配在拼音全量字段进行查询 还有一种做法： 首先定义个所谓的拼音标准化过程： n->l，zh->z, ch->c, sh->s ，an->ang, en->eng, in->ing, on->ong 不是互换，而是单向替换。 将一个拼音串的所有可替换点都替换后，得到的一个串，称为标准化串。 1。建索引的时候，歌曲名，歌手名，专辑名各新增一个标准化串字段，按”,”分词（多音字），存储字段的拼音标准化串 2。搜索的时候，将用户输入的关键词转成拼音，在拼音全量里面搜索 [...]
假设我们定义了一个变量为： file=/dir1/dir2/dir3/my.file.txt 我们可以用 ${ } 分别替换获得不同的值： ${file#*/}：拿掉第一条 / 及其左边的字串：dir1/dir2/dir3/my.file.txt ${file##*/}：拿掉最后一条 / 及其左边的字串：my.file.txt ${file#*.}：拿掉第一个 . 及其左边的字串：file.txt ${file##*.}：拿掉最后一个 . 及其左边的字串：txt ${file%/*}：拿掉最后一条 / 及其右边的字串：/dir1/dir2/dir3 ${file%/*}：拿掉第一条 / 及其右边的字串：(空值) ${file%.*}：拿掉最后一个 . 及其右边的字串：/dir1/dir2/dir3/my.file ${file%%.*}：拿掉第一个 . 及其右边的字串：/dir1/dir2/dir3/my 记忆的方法为： # 是去掉左边(在键盘上 # 在 $ 之左边) % 是去掉右边(在键盘上 % 在 $ 之右边) 单一符号是最小匹配；两个符号是最大匹配。 还可以按下标取指定长度的子串： ${file:0:5}：提取最左边的 5 个字?：/dir1 ${file:5:5}：提取第 5 个字右边的连续 5 个字：/dir2 我们也可以对变量值里的字串作替换： ${file/dir/path}：将第一个 [...]
RSync 算法是澳大利亚人 Andrew Tridgell （samba的作者）发明的，按照 Andrew Tridgell 自己的话，这个算法只需要半个小时就能够理解，但是花费了他几年时间才研究出来。 Rsync 算法大概原理：（目标：把 HostA 上的FileNew 同步到 HostB 上 FileOld） 1) Host-B把File-Old划分成不重合的大小为K字节的若干块，不足K字节的结尾部分加上Padding，然后对每一块求弱Hash和强Hash。弱Hash就是说很有可能两个不同的块Hash值相同，但是计算起来快，而且这里要求这个弱Hash能够Rolling，也就是说已知字节1到字节K这个块的Hash值，能够很快的计算出字节2到字节K+1这个块的Hash值，往前Roll一个字节，计算很快；强Hash就是可以认为不同块肯定有不同 Hash值，Rsync用的是MD4。我们让WH表示弱Hash,SH表示强Hash。 2) Host-B把每个块的WH和SH值发送给Host-A。 3) 该Host-A上场了，他的运算量比较大。Host-A对File-New每一个长度为K的块（也就是以每个字节开头的长度为K的块）计算WH，计算出来之后和Host-B发送过来的WH匹配，如果发现有相同的，再计算这个块的SH进行匹配，如果还是相符，说明这个块在File-Old里面也存在。假如 File-New长度为N，那么Host-A要处理大约(N-K)个块，这里可见用两个Hash算法的作用，WH用来做初步比较，而且因为它可以 Rolling，所以能够很快筛选掉大多数不匹配，对于漏网之鱼，也躲不过SH的筛选。 4) 通过上面的计算，Host-A可知道，File-New中哪些块和File-Old中的块相同，这样自然也可以计算出哪些不同，Host-A把这些不同encode一下送给Host-B。 5) Host-B收到Host-A送来的数据，decode，就得到了File-New相对于File-Old的改变，于是获得了File-New。 整个过程只需要一个round-trip（一个来回的通信），而且可以精确的得到一个字节级别的差别，Host-A的运算量相对要大一些。 Rsync的实现已经是*inx上面的一个重要工具，所以，当Microsoft在Windows 2003 Server上推出DFSR(Distributed File System Replication)时，Open Source Community颇有嘘声。其实DFSR采用的是RDC(Remote Differential Compression)算法，和RSync相差很大，并没有抄袭RSync。 RSync有学院气息（这个算法本来就是Andrew Tridgell的博士论文），结果很完美，File-New和File-Old每一个字节的差别都计算出来了，但是Host-A和Host-B的计算量不对等，大部分的计算都集中在Host-A上。RDC和RSync相比方向上有点不同，RDC并不追求计算出字节级别的diff，而是用较少的运算求出数据块级别的 diff。 RDC算法要求Host-A和Host-B通过一致的规则对File-New和File-Old分别进行分块，然后对每个块计算 SH，Host-B把每个块的SH值发给Host-A，Host-A对两组SH进行diff，就可以知道有哪些块不同，哪些块被删掉了，哪些块被添加了。 RDC的关键在于分块规则，也使用WH，要让同一规则应用于File-Old和File-New的时候，分出来的块能够尽量体现出区别。 比如File-Old包含“I Love Playing Basketball”， File-New是“I Like Playing Football”。 如果是RSync算法，Host-A能够计算出准确的差别，“I [...]
新公司上班，公司在双井地铁站附近的九龙花园居民区里，住则住在百子湾家园，一个只有一条路通向外面的封闭地方。每天上下班由小蔡接送，除了车子不密封，早晚稍微有点冷以外，一切都还好。 继续为 nginx 增加 deflate 压缩支持。公司居然用的是 nginx 0.7.33 的最新开发版本，虽然不时的有 502 bad gateway 出现，但老高不以为然。打开0.7.33 代码一看，比 0.6 版本的整洁了许多，gzip 添加头，尾的动作都被封装到了单独的函数中了，再也不是一个大函数从头写到尾了，有进步。 起初是想为 deflate 压缩单独写一个与 gzip 平行的模块，拿原先 gzip 模块的 c 文件（src/http/modules/ngx_http_gzip_filter_module.c）一通 “搜索”－“替换”，编译通过了，但新模块死活没有被调用。想想也是，http 请求头的处理不在这个 c 文件里面，只改这个文件，当然不会有效果了。 接下来就把原来的 gzip c 文件一通猛改，添加头的函数直接 return，添加尾的函数也去掉具体添加的动作，最后再把 Content-Encoding 改过来，一测试，呵呵，还真的省下来 18 个字节！ 但这样以来 gzip 就不支持了。更严重的是，如果（虽然可能性比较小），一个客户端只支持 gzip，不支持 deflate，那么它就无法解析请求的结果。在查看 src/http/ngx_http_core_module.c 里的 ngx_http_gzip_ok 函数的时候，终于发现了对于客户端提交的 header 里面的 accept encoding 的判断处理： ngx_strcasestrn(r->headers_in.accept_encoding->value.data, “gzip”, [...]
新东家还没有报道，就安排先做一个小任务：把 nginx 的 gzip 换成 deflate ，问为什么，老大说能省 18 个字节。 在baidu上搜了好久，搜到的中文基本上都是讲 apache 的 gzip（apache 1.3） 和 deflate（apache 2.x）的配置的，仅有的几个跟 nginx 相关的，也逃不出配置文件的范畴。至于原理，算法等等，只有去 Google 英文资料了。 换了关键词，直接搜 zlib ，终于找到一些有用的东西，在 http://www.cppblog.com/jinq0123/archive/2007/07/09/HttpCompressConv.html 处看到这样一段话： deflate与gzip解压的代码几乎相同，应该可以合成一块代码。 区别仅有： deflate使用inflateInit()，而gzip使用inflateInit2()进行初始化，比 inflateInit()多一个参数: -MAX_WBITS，表示处理raw deflate数据。因为gzip数据中的zlib压缩数据块没有zlib header的两个字节。使用inflateInit2时要求zlib库忽略zlib header。在zlib手册中要求windowBits为8..15，但是实际上其它范围的数据有特殊作用，见zlib.h中的注释，如负数表示raw deflate。 Apache的deflate变种可能也没有zlib header，需要添加假头后处理。即MS的错误deflate (raw deflate).zlib头第1字节一般是0×78, 第2字节与第一字节合起来的双字节应能被31整除，详见rfc1950。例如Firefox的zlib假头为0×7801，python zlib.compress()结果头部为0x789c。 再去检查 zlib.h 中的注释说明，在 zlib-1.2.3/zlib.h Line 500 的地方发现这样一段话： The windowBits parameter is the base two [...]