分类归档: Algorithm

[转]LZW数据压缩算法的原理分析

src:http://www.cnblogs.com/jillzhang/archive/2006/11/06/551298.html

   我希望通过本文的介绍，能给那些目前不太了解lzw算法和该算法在gif图像中应用，但渴望了解它的人一些启发和帮助。抛砖引玉而已，更希望园子里面兄弟提出宝贵的意见。
1.LZW的全称是什么?
   Lempel-Ziv-Welch (LZW).
2. LZW的简介和压缩原理是什么？
   LZW压缩算法是一种新颖的压缩方法，由Lemple-Ziv-Welch 三人共同创造，用他们的名字命名。它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串表中，用一个数字来表示串，压缩文件只存贮数字，则不存贮 串，从而使图象文件的压缩效率得到较大的提高。奇妙的是，不管是在压缩还是在解压缩的过程中都能正确的建立这个串表，压缩或解压缩完成后，这个串表又被丢 弃。
   LZW算法中，首先建立一个字符串表，把每一个第一次出现的字符串放入串表中，并用一个数字来表示，这个数字与此字符串在串表中的位置有关，并将这个数字 存入压缩文件中，如果这个字符串再次出现时，即可用表示它的数字来代替，并将这个数字存入文件中。压缩完成后将串表丢弃。如"print" 字符串，如果在压缩时用266表示，只要再次出现，均用266表示，并将"print"字符串存入串表中，在图象解码时遇到数字266，即可从串表中查出 266所代表的字符串"print"，在解压缩时，串表可以根据压缩数据重新生成。
3.在详细介绍算法之前，先列出一些与该算法相关的概念和词汇
   1)’Character’: 字符，一种基础数据元素，在普通文本文件中，它占用1个单独的byte，而在图像中，它却是 一种代表给定像素颜色的索引值。
   2)’CharStream’：数据文件中的字符流。
   3)’Prefix’:前缀。如这个单词的含义一样，代表着在一个字符最直接的前一个字符。一个前缀字符长度可以为0,一个prefix和一个character可以组成一个字符串(string),
   4)’Suffix’: 后缀，是一个字符，一个字符串可以由(A,B)来组成，A是前缀,B是后缀,当A长度为0的时候，代表Root，根
   5)’Code:码,用于代表一个字符串的位置编码
   6)’Entry’，一个Code和它所代表的字符串(string)
4.压缩算法的简单示例，不是完全实现LZW算法，只是从最直观的角度看lzw算法的思想
    对原始数据ABCCAABCDDAACCDB进行LZW压缩
    原始数据中，只包括4个字符(Character),A,B,C,D,四个字符可以用一个2bit的数表示，0-A,1-B,2-C,3-D,从最直观的角度看，原始字符串存在重复字符：ABCCAABCDDAACCDB，用4代表AB,5代表CC，上面的字符串可以替代表示为:45A4CDDAA5DB,这样是不是就比原数据短了一些呢！
5.LZW算法的适用范围
   为了区别代表串的值(Code)和原来的单个的数据值(String)，需要使它们的数值域不重合，上面用0-3来代表A-D,那么AB就必须用大于3的 数值来代替，再举另外一个例子，原来的数值范围可以用8bit来表示，那么就认为原始的数的范围是0～255，压缩程序生成的标号的范围就不能为 0～255（如果是0-255，就重复了）。只能从256开始，但是这样一来就超过了8位的表示范围了，所以必须要扩展数据的位数，至少扩展一位，但是这样不是增加了1个字符占用的空间了么？但是却可以用一个字符代表几个字符，比如原来255是8bit,但是现在用256来表示254，255两个数，还是划得来的。从这个原理可以看出LZW算法的适用范围是原始数据串最好是有大量的子串多次重复出现，重复的越多，压缩效果越好。反之则越差，可能真的不减反增了。
6.LZW算法中特殊标记
   随着新的串(string)不断被发现，标号也会不断地增长，如果原数据过大，生成的标号集（string table)会越来越大，这时候操作这个集合就会产生效率问题。如何避免这个问题呢?Gif在采用lzw算法的做法是当标号集足够大的时候，就不能增大 了，干脆从头开始再来，在这个位置要插入一个标号，就是清除标志CLEAR，表示从这里我重新开始构造字典，以前的所有标记作废，开始使用新的标记。
这时候又有一个问题出现，足够大是多大？这个标号集的大小为比较合适呢？理论上是标号集大小越大，则压缩比率就越高，但开销也越高。 一般根据处理速度和内存空间连个因素来选定。GIF规范规定的是12位，超过12位的表达范围就推倒重来，并且GIF为了提高压缩率，采用的是变长的字 长。比如说原始数据是8位，那么一开始，先加上一位再说，开始的字长就成了9位，然后开始加标号，当标号加到512时，也就是超过9为所能表达的最大数据 时，也就意味着后面的标号要用10位字长才能表示了，那么从这里开始，后面的字长就是10位了。依此类推，到了2^12也就是4096时，在这里插一个清 除标志，从后面开始，从9位再来。
GIF规定的清除标志CLEAR的数值是原始数据字长表示的最大值加1，如果原始数据字长是8，那么清除标志就是256，如果原始数据字长为4那么就是16。另外GIF还规定了一个结束标志END，它的值是清除标志CLEAR再加1。由于GIF规定的位数有1位（单色图），4位（16色）和8位（256色），而1位的情况下如果只扩展1位，只能表示4种状态，那么加上一个清除标志和结束标志就用完了，所以1位的情况下就必须扩充到3位。其它两种情况初始的字长就为5位和9位。此处参照了http://blog.csdn.net/whycadi/
7.用lzw算法压缩原始数据的示例分析
   输入流，也就是原始的数据为:255,24,54,255,24,255,255,24,5,123,45,255,24,5,24,54………………
   这个正好可以看到是gif文件中像素数组的一部分，如何对它进行压缩
   因为原始数据可以用8bit来表示，故清除标志Clear=255+1 =256,结束标志为End=256+1=257，目前标号集为
   0 1 2 3 ………………………………………………………………………255 CLEAR END
   第一步,读取第一个字符为255,在标记表里面查找，255已经存在，我们已经认识255了，不做处理
   第二步,取第二个字符，此时前缀为A,形成当前的Entry为(255,24),在标记集合不存在，我们并不认识255,24好，这次你小子来了，我就记住你，把它在标记集合中标记为258,然后输出前缀A,保留后缀24，并作为下一次的前缀（后缀变前缀)
第三步，取第三个字符为54，当前Entry(24,54),不认识，记录(24,54)为标号259,并输出24,后缀变前缀
    第四部：取第四个字符255,Entry=(54,255),不认识，记录(54,255)为标号260,输出54,后缀变前缀
   第五步   取第5个字符24，entry=(255,24),啊，认识你，这不是老258么，于是把字符串规约为258，并作为前缀
   第六步 取第六个字符255,entry=(258,255)，不认识，记录(258,255)为261,输出258,后缀变前缀
   …….
一直处理到最后一个字符,
用一个表记录处理过程
   CLEAR=256,END=257

第几步 前缀 后缀 Entry 认识(Y/N) 输出 标号
1 255 （，255）
2 255 24 (255,24)       N 255 258
3 24 54 (24,54)       N 24 259
4 54 255    (54,255)       N 54 260
5 255 24 (255,24)       Y
6 258 255 (258,255)       N 258 261
7 255 255 (255,255)       N 255 262

…..
上面这个示例有些不能完整体现，另外一个例子是
原输入数据为:A B A B A B A B B B A B A B A A C D A C D A D C A B A A A B A B …..
采用LZW算法对其进行压缩，压缩过程用一个表来表述为:
注意原数据中只包含4个character,A,B,C,D
用两bit即可表述，根据lzw算法，首先扩展一位变为3为,Clear=2的2次方+1=4; End=4+1=5;
初始标号集因该为

0 1 2 3 4 5
A B C D Clear End

而压缩过程为:

第几步 前缀 后缀 Entry 认识(Y/N) 输出 标号
1 A （，A）
2 A B (A,B)       N A 6
3 B A (B,A)       N B 7
4 A B    (A,B)       Y
5 6 A (6,A)       N 6 8
6 A B (A,B)       Y
7 6 A (6,A)      Y
8 8 B (8,B)        N 8 9
9 B B (B,B)        N B 10
10 B B (B,B)        Y
11 10 A (10,A)        N 10 11
12 A B (A,B)        Y

…..
当进行到第12步的时候，标号集应该为

0 1 2 3 4 5 6 7 8 9 10 11
A B C D Clear End AB BA 6A 8B BB 10A

8.LZW算法的伪代码实现

1STRING = get input character
 2WHILE there are still input characters DO
 3     CHARACTER = get input character
 4     IF STRING+CHARACTER is in the string table then
 5         STRING = STRING+character
 6     ELSE
 7         output the code for STRING
 8         add STRING+CHARACTER to the string table
 9         STRING = CHARACTER
10     END of IF
11END of WHILE
12output the code for STRING
13

9.LZW算法的流程图
没有安visio,画了一个，比较难看，

Read: 1064

[转]磨练构建正则表达式模式的技能

转自:http://www.ibm.com/developerworks/cn/aix/library/au-expressions.html


用于系统管理的正则表达式

级别： 中级

Michael Stutz (stutz@dsl.org), 作者, 顾问

2006 年 8 月 14 日

通过本文的学习，您可以增加一些有用的设计实际正则表达式 (regexp) 的技能。构建正则表达式是任何管理员日常工作中的一部分。为了构造返回所需条件的成功正则表达式，需要学习以模式匹配的角度进行思考，而这种技能需要花大量的时间进行练习。

引言

UNIX® 管理员每天都需要构建和使用正则表达式 (regexp) 进行文本模式匹配。大多数语言都支持正则表达式的某种实现。有的应用程序（如 EMACS）具有正则表达式搜索功能，并且您可以通过各种命令行工具使用正则表达式。无论什么应用程序，构建正确的正则表达式的关键之处在于，识别仅满足 需要匹配的数据的模式，以便在输入中排除其他不必要的内容。

出于这个目的，本文将逐步介绍几种正则表达式模式构建技巧，并介绍它们如何帮助您完成各种常规任务。

使用正则表达式 (regexp)

除非特别说明，否则本文中使用的示例都是扩展可移植操作系统接口（扩展 POSIX）的正则表达式。如果通过命令行（如使用 egrep 实用工具）使用它们，您应该根据需要引用各种正则表达式。请记住，不同的正则表达式实现之间存在一些区别，您可能不得不适应所使用的特定的工具、应用程序或语言中的具体实现。

匹配整行内容

^ 元字符匹配行首，而 $ 匹配行尾，如果将它们组合在一起（如 ^$），它们将匹配空行。（这个表达式的镜像，即 $^，是不可能匹配成功的，它将永远 都无法匹配到有效行。）这个基本的正则表达式是许多复杂正则表达式的基础，如果您还不习惯使用这个基本的正则表达式，那么您应该逐步养成使用它的习惯。使用它来构建匹配整行内容 的模式。

在用户字典文件 (/usr/dict/words) 中搜索是一个很好的基本模式。（有些版本的 UNIX 将用户字典放在 /usr/share/dict/words 中。）

例如，假设您忘记了如何拼写单词 fuchsia。其中是否包含 sh 或 cs 呢？您所知道的只是，它以 fu 开头并以 ia 结尾。

尝试使用这个模式进行搜索：

$ egrep -i '^fu.*ia$' /usr/dict/words

-i 标志表示在搜索过程中不区分大小写。在这个示例中，因为 fuchsia 拼写正确，所以在返回的单词中包括这个单词。

回页首

根据长度匹配行

使用大括号元字符 ({ }) 指定前面的正则表达式匹配多少次，如表 1 所示。当您将它们添加到刚才介绍的整行搜索中时，您可以指定行的长度。

表 1. 大括号元字符的含义

示例 描述
{X} 这个字符对前面的正则表达式匹配 X 次。
{X,} 这个字符对前面的正则表达式匹配 X 或更多 次。
{X,Y} 这个字符对前面的正则表达式匹配至少 X 而不超过 Y 次。

并不是所有扩展正则表达式的实现都支持大括号。此外，根据具体的实现，您可能需要先使用反斜杠对其进行转义。

您可以使用这个正则表达式得到字典中以单词长度为顺序的报告。所获得结果的数目取决于本地系统的字典文件中单词的数目，然而，它应该与清单 1 所示类似。在这个示例中，最常见的单词长度是 9 个字母，该字典中有 32,380 个匹配单词。该字典中不包括 25 个字母或更长的单词，并且最长的单词并不是您认为的 21 个字母长的 disestablishmentarian（有 81 个同样长度的单词，包括 superincomprehensible 和 phoneticohieroglyphic），这个 UNIX 字典中最长的单词有 5 个，包括 pathologicopsychological。

清单 1. 计算字典中 X 个字母的单词的个数

$ for i in `seq 1 32`
>  {
>   echo "There are" `egrep '^.{'$i'}$' /usr/dict/words  
   | wc -l` "$i-letter words in the dictionary."
>  }
There are 52 1-letter words in the dictionary.
There are 155 2-letter words in the dictionary.
There are 1351 3-letter words in the dictionary.
There are 5110 4-letter words in the dictionary.
There are 9987 5-letter words in the dictionary.
There are 17477 6-letter words in the dictionary.
There are 23734 7-letter words in the dictionary.
There are 29926 8-letter words in the dictionary.
There are 32380 9-letter words in the dictionary.
There are 30867 10-letter words in the dictionary.
There are 26011 11-letter words in the dictionary.
There are 20460 12-letter words in the dictionary.
There are 14938 13-letter words in the dictionary.
There are 9762 14-letter words in the dictionary.
There are 5924 15-letter words in the dictionary.
There are 3377 16-letter words in the dictionary.
There are 1813 17-letter words in the dictionary.
There are 842 18-letter words in the dictionary.
There are 428 19-letter words in the dictionary.
There are 198 20-letter words in the dictionary.
There are 82 21-letter words in the dictionary.
There are 41 22-letter words in the dictionary.
There are 17 23-letter words in the dictionary.
There are 5 24-letter words in the dictionary.
There are 0 25-letter words in the dictionary.
There are 0 26-letter words in the dictionary.
There are 0 27-letter words in the dictionary.
There are 0 28-letter words in the dictionary.
There are 0 29-letter words in the dictionary.
There are 0 30-letter words in the dictionary.
There are 0 31-letter words in the dictionary.
There are 0 32-letter words in the dictionary.
$

回页首

匹配单词

围绕字符 < 和 > 是非常有用的模式构造器：它们将要匹配的整个单词 括起来，这表示，它们不会匹配带括号的模式，除非该模式本身就是一个单词。单词 定义为两侧由非单词字符描述的、任意数目组成单词的字符（数字、字母和下划线字符）。非单词字符包括下面的所有字符：

  • 行首
  • 空白字符
  • 标点符号
  • 行尾
  • 任何除字母、数字或下划线以外的字符

这些围绕字符可以节省大量的时间，但是它们常常没有被充分地利用，可能是因为并非所有的正则表达式实现都支持它们。如果您的正则表达式实现支持它们，那么您应该逐步养成使用它们的习惯。

将需要单独匹配的单词括起来，如下所示：

<system>

这个示例中的正则表达式不会匹配单词 ecosystem、systemic 或 system/70，也不会匹配模式 system 出现在行中任意位置的那些行，它将仅仅 匹配 system 作为独立的单词出现的那些行。

围绕字符与圆括号中的分组结合在一起，可以用来匹配部分 单词。

要匹配包含以 pre 开头 的单词的那些行，可以使用：

<(pre).*>

前面的示例将匹配包含单词 preface 和 preposterous 的行，但不会匹配 spread 或 Dupre。

回页首

匹配重复单词

这里介绍一种使用单词围绕字符匹配重复单词的快速方法，重复单词表示一个单词在空格之后再次出现。您还可以使用逆向引用，这是大多数流行的正则表达式实现中的一种递归特性，它可以匹配模式本身的某一部分。（将模式中需要引用的部分使用圆括号括起来，然后使用反斜杠加上需要进行引用的围绕字符编号来调用逆向引用：1 表示第一个圆括号分组，2 表示第二个圆括号分组，依此类推。）

要查找重复的单词，搜索在任意数目的空格之后再次出现该单词的情况，可以通过对第一个使用圆括号的部分进行逆向引用来实现：

(<.*>)( )+1

这个示例匹配缩写形式和任何类型的单词，但是它不会匹配由标点符号分隔的重复单词，如 It’s been a long, long time。

要匹配所有的重复单词，包括由空格和 任意标点符号分隔的重复单词，可以使用下面的表达式：

(<.*>).?( )+1

如果需要对这些正则表达式使用 grep，则务必使用 -i 标志，以便在搜索中不区分大小写。

回页首

匹配小时

让我们再来看另外一类常见的问题：时间和日期。这里介绍了一些设计匹配正确模式的正则表达式所需要考虑的事项。

您无法搜索任何两位的数字来匹配分钟和秒，因为它们仅仅是从 0 到 59，要匹配它们，您需要使用方括号将表示十位和个位的范围括起来：

  • 要匹配标准的 12 或 24 小时格式的小时，可以使用下面的表达式：
    (([0-1]?[0-9])|([2][0-3])):([0-5][0-9])(:[0-5][0-9])?
  • 要匹配 12 小时 AM/PM 格式、带或不带秒数的时间，甚至匹配大写或小写、不带后缀 AM 或 PM 标识符的时间，可以使用下面的表达式：
    ([^0-9])([0-1]?[0-9]){1}(((:([0-5]){1}([0-9]){1}){1,2})|(( )?([AP]M)|([ap]m)))?

如果在上一个示例中没有开始的否定语句，它将匹配不带冒号的时间，这将取决于输入数据，可能会匹配中波广播电台（在美国称为调幅 AM 电台），如 1450 AM。

回页首

匹配月份

匹配 12 个月中的任何月份需要一个使用 | 操作符进行分隔的列表，但有时会使用不同的方式对日期进行缩写：

  • 要查找完整拼写或三字母缩写的 12 个月份，可以使用下面的表达式（位于一行）：
    Jan(uary)?|Feb(uary)?|Mar(ch)?|Apr(il)?|May|Jun(e)?|Jul(y)?|
    Aug(ust)?|Sep(tember)?|Oct(ober)?|Nov(ember)?|Dec(ember)?
  • 您可以加以想象并搜索完整拼写或三字母缩写的变形，即仅当后面紧跟着一个空格或点号的情况，可以使用下面的表达式（位于一行）：
    Jan(uary| |.)|Feb(uary| |.)|Mar(ch| |.)|Apr(il| |.)|May( |.)|Jun(e| |.)|Jul(y| |
    .)|Aug(ust| |.)|Sep(tember| |.)|Oct(ober| |.)|Nov(ember| |.)|Dec(ember| |.)

请注意，在上面的这两个示例中，May 是一个特殊的例外。在所有的月份中，它是唯一的完整拼写与三字母缩写相同的月份，所以成功的匹配必须包含这两种变形中的任何一种 作为其缩写，因此像“Mayflower”这样的单词不会导致误报。

当匹配模式前面的字符不是空格或行首时，这些示例还是会失败（返回误报的结果）。这不太可能会出现在英语散文中，但是可能出现在程序源代码中，因为其中可能使用了像 NumOct 这样的变量名。

要修复这些问题，可以执行下面的操作：

  • 使用圆括号将整个正则表达式括起来，并在它的前面加上另一个限定符，用于匹配行首或者空格字符，如下所示（位于一行）：
    (^| )(Jan(uary| |.)|Feb(uary| |.)|Mar(ch| |.)|Apr(il| |.)|
    May( |.)|Jun(e| |.)|Jul(y| |.)|Aug(ust| |.)|Sep(tember| |
    .)|Oct(ober| |.)|Nov(ember| |.)|Dec(ember| |.))
  • 另一种完成这个任务的方法是，在该正则表达式的前面加上一个限定符，以匹配非文字数字的字符，如下所示（位于一行）：
    ([^A-Za-z0-9])(Jan(uary| |.)|Feb(uary| |.)|Mar(ch| |.)|
    Apr(il| |.)|May( |.)|Jun(e| |.)|Jul(y| |.)|Aug(ust| |.)|
    Sep(tember| |.)|Oct(ober| |.)|Nov(ember| |.)|Dec(ember| |.))

但是仍然存在潜在的问题，对于搜索整篇英文散文，这些示例并不可靠，因为它们可能返回错误的匹配结果，如“Janelle”或“Augury”这样的单词。要修复这个问题，您必须使用单词围绕字符将每个月份括起来。

本文开头提到，正确的正则表达式应该仅返回需要匹配的数据，以便在输入中排除其他不必要的内容。这种措词是经过仔细考虑的，因为对于构建正则表达式来说，这与上下文有关。对于有些情况，前面的示例非常适合，无需添加额外的单词围绕字符。在其他的情况下，可以对其进行相当程度的简化，例如，如果您正在搜索仅包含大写的日期数值数据的日志文件，那么只需要使用像 [A-S] 这样的正则表达式来匹配包含月份名称的行。

回页首

匹配日期

您可以结合一些表 1 所示的数量匹配来匹配日期。

要匹配“month, day, years”，可以使用下面的正则表达式（因为撇号字符是该正则表达式的一部分，所以必须使用双引号将它括起来，如下所示）：

"[A-Za-z]{3,10}.? [0-9]{1,2}, ([0-9]{4}|'?[0-9]{2})"

这个正则表达式匹配 9 种不同的日期格式：

  1. MONTH [D]D, YY
  2. MONTH [D]D, 'YY
  3. MONTH [D]D, YYYY
  4. MON. [D]D, YY
  5. MON. [D]D, 'YY
  6. MON. [D]D, YYYY
  7. MON [D]D, YY
  8. MON [D]D, 'YY
  9. MON [D]D, YYYY

这个正则表达式的误报包括“Order 99, 99”，要消除这些误报，可以将这个正则表达式与用于月份的正则表达式结合起来，如上所述，以便能够仅匹配实际的月份名称。另外，更改数值范围以避免错误的匹配，并且通过使逗号成为可选项，重复了 18 种可能的格式。

这将得到一个很长的正则表达式。尝试下面的表达式：

"([^A-Za-z0-9])(Jan(uary| |.)|Feb(uary| |.)|Mar(ch| |.)|
Apr(il| |.)|May( |.)|Jun(e| |.)|Jul(y| |.)|Aug(ust| |.)|
Sep(tember| |.)|Oct(ober| |.)|Nov(ember| |.)|
Dec(ember| |.)) [0-3]?[0-9]{1}(,)? ([0-9]{4}|'?[0-9]{2})"

同样，根据您的需要仔细设计正则表达式。匹配模式通常比较容易，这是因为它存在于特定输入的上下文中，而不是因为它可能独立于数据集而存在。后代人将会发现，前面那个很长的正则表达式中仍然存在 Y10K 错误，因为它能匹配的最大可能的年份为 9999。

回页首

匹配整数

正如您在前几个示例中看到的，使用方括号中的范围可以很好地匹配数值。

要匹配任意长度的整数，可以在数值范围后面加上 +；要包括负值，可以在它的前面加上可选的负号（连字号）匹配：

-?[0-9]+

前面的例子可以匹配 0，因为 0 是指定范围中可选的字符。

对于数值匹配，使用圆括号将某些部分括起来也非常有效。要匹配任意的十进制数值，可以使用包含小数点加上一个或多个数值的可选围绕字符，以此对前面的正则表达式进行扩展：

-?[0-9]+(.[0-9]+)?

可以使用方括号指定十进制数值的小数位数。例如，要匹配小数位数为 5 或更多小数位数的正数值，可以使用下面的表达式：

[^-][0-9]+.([0-9]){5,}

回页首

更多实际的匹配

范围加上使用括号括起来的元字符，在查找符合任何特定格式的数值时非常有用。将前面介绍的一些技术结合起来，可以构建匹配各种数据的正则表达式：

  • 要匹配美国的电话号码，可以使用：
    ((([2-9][0-9]{2}))? ?|[2-9][0-9]{2}(?:-?| ?))[2-9][0-9]{2}[- ]?[0-9]{4}

    这个正则表达式可以匹配美国 15 种格式的电话号码：

    1. (NPA) PRE-SUFF
    2. (NPA) PRE SUFF
    3. (NPA) PRESUFF
    4. (NPA)PRE-SUFF
    5. (NPA)PRE SUFF
    6. (NPA)PRESUFF
    7. NPA PRE-SUFF
    8. NPA PRE SUFF
    9. NPA PRESUFF
    10. NPAPRE-SUFF
    11. NPAPRE SUFF
    12. NPAPRESUFF
    13. PRE-SUFF
    14. PRE SUFF
    15. PRESUFF

    它还可以匹配美国免费 WATS 号码，尽管 1-800 的“1-”前缀或其他的免费号码不是匹配的一部分，但它本身可以匹配 10 位的数值。对于以 1 或 1+ 开头的美国号码和任意数目的空格，也完全一样，长途电话拨号前缀本身无法匹配，但是只要它后面跟着实际的号码，这个正则表达式就能够将其找出来。

  • 要匹配两或三位域的电子邮件地址，可以尝试下面的表达式：
    <[^@]+>@[a-zA-Z_.]+?.[a-zA-Z]{2,3}
  • 要匹配如今所有流行的 URL，可以使用下面的正则表达式：
    (((http(s)?|ftp|telnet|news)://|mailto:)[^()[:space:]]+)

    这个表达式可以正常运行，但是匹配 URL 并不像您想象的那么简单。匹配任何可能的 URL 的正则表达式，如 RFC 1738 中的定义，发表在“Regexp for URLs”（请参见参考资料部分）一文中，它非常巨大并且看起来令人生畏。现在应该将它合并为一个 [:url:] 类（如果有用于处理类似数据种类的各种新的类，如 [:email:]，那就好了）。

回页首

结束语

本文涉及到一些用于编写正则表达式的模式构建技术，以及如何使用它们来完成管理员时常碰到的特定类型数据匹配的工作。在此过程中，向您介绍了大量有价值的实际正则表达式，您可以将它们添加到自己的管理工具库中。

参考资料

学习

Read: 1000

[转]澄清Java（接口与继承）

计算机学院研二的兄弟与我讨论Java，一见面，几个问题全是关于接口，接口有什么用？为什么要用接口？什么时候该使用接口？很庆幸他们不是问我 Java如何连接SQL Server，或者是如何开发J2EE应用，这类问题有杀伤力，避之则吉。今年计算机学院本科有个毕业设计课题是做J2ME，选这个题目的学生在5月末都还在苦着脸研究java.util.*这个包，这个这个……唉。

大多数人认为，接口的意义在于顶替多重继承。众所周知Java没有c 那样多重继承的机制，但是却能够实作多个接口。其实这样做是很牵强的，接口和继承是完全不同的东西，接口没有能力代替多重继承，也没有这个义务。接口的作用，一言以蔽之，就是标志类的类别（type of class）。把不同类型的类归于不同的接口，可以更好的管理他们。OO的精髓，我以为，是对对象的抽象，最能体现这一点的就是接口。为什么我们讨论设计模式都只针对具备了抽象能力的语言（比如c 、java、c#等），就是因为设计模式所研究的，实际上就是如何合理的去抽象。（cowboy的名言是“抽象就是抽去像的部分”，看似调侃，实乃至理）。

设计模式中最基础的是工厂模式（Factory），在我最近的一个很简单的应用中，我想尽量的让我的程序能够在多个数据库间移植，当然，这涉及很多问题，单是如何兼容不同DBMS的SQL就让人头痛。我们不妨先把问题简单化，只考虑如何连接不同的数据库。

假设我有很多个类，分别是Mysql.java、SQLServer.java、Oracle.java、DB2.java，他们分别连接不同的数据库，统一返回一个Connection对象，并且都有一个close方法，用于关闭连接。只需要针对你的DBMS，选择不同的类，就可以用了，但是我的用户他会使用什么数据库？我不知道，我希望的是尽量少的修改代码，就能满足他的需要。我可以抽象如下接口：
package org.bromon.test;
public interface DB
{
java.sql.Connection openDB(String url,String user,String password);
void close();
}

这个接口只定义两个方法，没有任何有实际意义的代码，具体的代码由实作这个接口的类来给出，比如Mysql.java：

Package org.bromon.test;
import java.sql.*;
public class Mysql implements DB
{
private String url=”jdbc:mysql:localhost:3306/test”;
private String user=”root”;
private String password=””;
private Connection conn;
public Connection openDB(url,user,password)
{
//连接数据库的代码
}

public void close()
{
//关闭数据库
}
}

类似的当然还有Oracle.java等等，接口DB给这些类归了个类，在应用程序中我们这样定义对象：

org.bromon.test.DB myDB;

使用myDB来操作数据库，就可以不用管实际上我所使用的是哪个类，这就是所谓的“开-闭”原则。但是问题在于接口是不能实例化的， myDB=new DB()，这样的代码是绝对错误的，我们只能myDB=new Mysql()或者myDB=new oracle()。麻烦了，我还是需要指定具体实例化的是哪个类，用了接口跟没用一样。所以我们需要一个工厂：

package org.bromon.test;
public class DBFactory
{
public static DB Connection getConn()
{
Return(new Mysql());
}
}

所以实例化的代码变成：myDB=DBFactory.getConn()；
这就是23种模式中最基础的普通工厂(Factory)，工厂类负责具体实例化哪个类，而其他的程序逻辑都是针对DB这个接口进行操作，这就是“针对接口编程”。责任都被推卸给工厂类了，当然你也可以继续定义工厂接口，继续把责任上抛，这就演变成抽象工厂(Abstract Factory)。

整个过程中接口不负责任何具体操作，其他的程序要连接数据库的话，只需要构造一个DB对象就OK，而不管工厂类如何变化。这就是接口的意义—-抽象。

继承的概念不用多说，很好理解。为什么要继承呢？因为你想重用代码？这绝对不是理由，继承的意义也在于抽象，而不是代码重用。如果对象 A有一个run()方法，对象B也想有这个方法，所以有人就Class B extends A。这是不经大脑的做法。如果在B中实例化一个A，调用A的Run()方法，是不是可以达到同样的目的？如下：
Class B
{
A a=new A();
a.run();
}

这就是利用类的聚合来重用代码，是委派模式的雏形，是GoF一贯倡导的做法。

那么继承的意义何在？其实这是历史原因造成的，最开始的OO语言只有继承，没有接口，所以只能以继承来实现抽象，请一定注意，继承的本意在于抽象，而非代码重用（虽然继承也有这个作用），这是很多Java烂书最严重的错误之一，它们所造成的阴影，我至今还没有完全摆脱，坏书害人啊，尤其是入门类的，流毒太大。什么时候应该使用继承？只在抽象类中使用，其他情况下尽量不使用。抽象类也是不能实例化的，它仅仅提供一个模版而已，这就很能说明问题。

软件开发的万恶之源，一是重复代码而不是重用代码，二是烂用继承，尤以c 程序员为甚。Java中取缔多重继承，目的就是制止烂用继承，实是非常明智的做法，不过很多人都不理解。Java能够更好的体现设计，这是让我入迷的原因之一。

Read: 25

补码是什么？

用[ｘ]表示机器数（原码），ｘ是真值（二进制）
   ｘ＝+0.1001,则[ｘ]原＝0.1001
ｘ＝-0.1001,则[ｘ]原＝1.1001

对于0，原码中有“+0”、“-0”之分，故有两种形式：
[+0]原=0.000…0
[-0]原=1.000…0

采用原码表示法简单易懂，但它的最大缺点是加法运算复杂。这是因为，当两数相加时，如果是同号则数值相加；如果是异号，则要进行减法。而在进行减法时还要比较绝对值的大小，然后大数减去小数，最后还要给结果选择符号。

为了解决这些矛盾，人们找到了补码表示法。机器数的补码可由原码得到。如果机器数是正数，则该机器数的补码与原码一样；如果机器数是负数，则该机器数的补码是对它的原码（除符号位外）各位取反，并在未位加1而得到的。

负数用补码表示时，可以把减法转化为加法。这样，在计算机中实现起来就比较方便
[ｘ]补＝ {   ｘ　　　　　　　1＞ｘ≥0
      {   2＋ｘ＝2－|ｘ|　0≥ｘ≥－1

   ｘ＝+0.1011,则[ｘ]补＝0.1011
ｘ＝-0.1011,则[ｘ]补＝10+ｘ＝10.0000-0.1011＝1.0101

对于0，[＋0]补＝[－0]补＝0.0000             　(mod 2)

例子中是以定点小数为例。

补码的原理可以用钟表来描述

如设标准时间为4点正；一只表已经7点了，为了校准时间，可以采用两种方法：一是将时针退 7-4=3 格；一是将时针向前拨12-3=9格。即7-3和7+9(mod12)等价，因此，把负数用补码表示的mod2操作，可以把减法转化为加法。

Read: 958

计算机寄存器

寄存器是中央处理器内的其中组成部份。寄存器是有限存贮容量的高速存贮部件，它们可用来暂存指令、数据和位址。在中央处理器的控制部件中，包含的寄存器有指令寄存器(IR)和程序计数器(PC)。在中央处理器的算术及逻辑部件中，包含的寄存器有累加器(ACC)。
寄存器（Register）

寄存器是内存阶层 中的最顶端，也是系统操作资料的最快速途径。寄存器通常都是以他们可以保存的 位元 数量来估量，举例来说，一个 "8 位元寄存器" 或 "32 位元 寄存器"。寄存器现在都以寄存器档案 的方式来实作，但是他们也可能使用单独的正反器、高速的核心内存、薄膜内存 以及在数种机器上的其他方式来实作出来。

寄存器通常都用来意指由一个指令之输出或输入可以直接索引到的暂存器群组。更适当的是称他们为 "架构寄存器"。

例如，x86 指令及定义八个 32 位元寄存器的集合，但一个实作 x86 指令集的 CPU 可以包含比八个更多的寄存器。

寄存器是CPU内部的元件，寄存器拥有非常高的读写速度，所以在寄存器之间的数据传送非常快。

寄存器的用途：

1.可将寄存器内的数据执行算术及逻辑运算。

2.存于寄存器内的地址可用来指向内存的某个位置，即寻址。

3.可以用来读写数据到电脑的周边设备。

8086 有8个8位数据寄存器，

这些8位寄存器可分别组成16位寄存器：

AH&AL＝AX：累加寄存器，常用于运算；

BH&BL＝BX：基址寄存器，常用于地址索引；

CH&CL＝CX：计数寄存器，常用于计数；

DH&DL＝DX：数据寄存器，常用于数据传递。

为了运用所有的内存空间，8086设定了四个段寄存器，专门用来保存段地址：

CS（Code Segment）：代码段寄存器；

DS（Data Segment）：数据段寄存器；

SS（Stack Segment）：堆栈段寄存器；

ES（Extra Segment）：附加段寄存器。

当一个程序要执行时，就要决定程序代码、数据和堆栈各要用到内存的哪些位置，通过设定段寄存器 CS，DS，SS 来指向这些起始位置。通常是将DS固定，而根据需要修改CS。所以，程序可以在可寻址空间小于64K的情况下被写成任意大小。 所以，程序和其数据组合起来的大小，限制在DS 所指的64K内，这就是COM文件不得大于64K的原因。8086以内存做为战场，用寄存器做为军事基地，以加速工作。

除了前面所提的寄存器外，还有一些特殊功能的寄存器：

IP（Intruction Pointer）：指令指针寄存器，与CS配合使用，可跟踪程序的执行过程；

SP（Stack Pointer）：堆栈指针，与SS配合使用，可指向目前的堆栈位置。

BP（Base Pointer）：基址指针寄存器，可用作SS的一个相对基址位置；

SI（Source Index）：源变址寄存器可用来存放相对于DS段之源变址指针；

DI（Destination Index）：目的变址寄存器，可用来存放相对于 ES 段之目的变址指针。

还有一个标志寄存器FR（Flag Register）,有九个有意义的标志(

OF: 溢出标志位OF用于反映有符号数加减运算所得结果是否溢出。如果运算结果超过当前运算位数所能表示的范围，则称为溢出，OF的值被置为1，否则，OF的值被清为0.

DF: 方向标志DF位用来决定在串操作指令执行时有关指针寄存器发生调整的方向。

IF: 中断允许标志IF位用来决定CPU是否响应CPU外部的可屏蔽中断发出的中断请求。但不管该标志为何值，CPU都必须响应CPU外部的不可屏蔽中断所发出的中断请求，以及CPU内部产生的中断请求。具体规定如下：

(1)、当IF=1时，CPU可以响应CPU外部的可屏蔽中断发出的中断请求；

(2)、当IF=0时，CPU不响应CPU外部的可屏蔽中断发出的中断请求。

TF: 状态控制标志位是用来控制CPU操作的，它们要通过专门的指令才能使之发生改变

SF: 符号标志SF用来反映运算结果的符号位，它与运算结果的最高位相同。在微机系统中，有符号数采用补码表示法，所以，SF也就反映运算结果的正负号。运算结果为正数时，SF的值为0，否则其值为1。

ZF: 零标志ZF用来反映运算结果是否为0。如果运算结果为0，则其值为1，否则其值为0。在判断运算结果是否为0时，可使用此标志位。

AF: 下列情况下，辅助进位标志AF的值被置为1，否则其值为0：

(1)、在字操作时，发生低字节向高字节进位或借位时；

(2)、在字节操作时，发生低4位向高4位进位或借位时。

PF: 奇偶标志PF用于反映运算结果中“1”的个数的奇偶性。如果“1”的个数为偶数，则PF的值为1，否则其值为0。

CF: 进位标志CF主要用来反映运算是否产生进位或借位。如果运算结果的最高位产生了一个进位或借位，那么，其值为1，否则其值为0。)

以上是8086寄存器的整体概况, 自80386开始，PC进入

32bit时代，其寻址方式，寄存器大小, 功能等都发生了变化, 要想学习这方面知识请参考相应资料.

Read: 846