IT博客-puppy居

[ZT]编译原理学习导论

puppy — Sat, 24 Aug 2013 15:50:00 GMT

大学课程为什么要开设编译原理呢？这门课程关注的是编译器方面的产生原理和技术问题，似乎和计算机的基础领域不沾边，可是编译原理却一直作为大学本科的必修课程，同时也成为了研究生入学考试的必考内容。编译原理及技术从本质上来讲就是一个算法问题而已，当然由于这个问题十分复杂，其解决算法也相对复杂。我们学的数据结构与算法分析也是讲算法的，不过讲的基础算法，换句话说讲的是算法导论，而编译原理这门课程讲的就是比较专注解决一种的算法了。在20世纪50年代，编译器的编写一直被认为是十分困难的事情，第一Fortran的编译器据说花了18年的时间才完成。在人们尝试编写编译器的同时，诞生了许多跟编译相关的理论和技术，而这些理论和技术比一个实际的编译器本身价值更大。就犹如数学家们在解决著名的哥德巴赫猜想一样，虽然没有最终解决问题，但是其间诞生不少名著的相关数论。

推荐参考书

虽然编译理论发展到今天，已经有了比较成熟的部分，但是作为一个大学生来说，要自己写出一个像Turboc C,Java那样的编译器来说还是太难了。不仅写编译器困难，学习编译原理这门课程也比较困难。

正是因为编译原理学习相对困难，那么就要求有好的教师和好的教材。教师方面不是我们能自己更改的，而在教材方面我们却可以按自己的意愿来阅读。我下面推荐几本好的编译原理的教材。我推荐的书籍都是国外的经典教材，因为在国内的教材中，确实还没发现什么让人满意的。

第一本书的原名叫《Compilers Principles,Techniques,and Tools》,另外一个响亮的名字就是龙书。原因是这本书的封面上有条红色的龙，也因为这本书在编译原理基础领域确实太有名气了,所以很多国外的学者都直接取名为龙书。最近机械工业出版社已经出版了此书的中文版，名字就叫《编译原理》。该书出的比较早，大概是在85或86年编写完成的，作者之一还是著名的贝尔实验室的科学家。里面讲解的核心编译原理至今都没有变过，所以一直到今天，它的价值都非凡。这本书最大的特点就是一开始就通过一个实际的小例子，把编译原理的大致内容罗列出来，让很多编译原理的初学者很快心里有了个底,也知道为什么会有这些理论，怎么运用这些理论。而这一点是我感觉国内的教材缺乏的东西，所以国内的教材都不是写给愿意自学的读者，总之让人看了半天，却不知道里面的东西有什么用。

第二本书的原名叫《Modern Compiler Design》,中文名字叫做《现代编译程序设计》。该书由人民邮电出版社所出。此书比较关注的是编译原理的实践，书中给出了不少的实际程序代码，还有很多实际的编译技术问题等等。此书另外一个特点就是其“现代”而字。在传统的编译原理教材中，你是不可能看到如同Java中的“垃圾回收”等算法的。因为Java这样的解释执行语言是在近几年才流行起来的东西。如果你想深入学习编译原理的理论知识，那么你肯定得看前面那本龙书，如果你想自己动手做一个先进的编译器，那么你得看这本《现代编译程序设计》。

第三本书就是很多国内的编译原理学者都推荐的那本《编译原理及实践》。或许是这本书引入国内比较早吧，我记得我是在高中就买了这本书，不过也是在前段时间才把整本书看完。此书作为入门教程也的确是个不错的选择。书中给出的编译原理讲解也相当细致，虽然不如前面的龙书那么深入，但是很多地方都是点到为止，作为大学本科教学已经是十分深入了。该书的特点就是注重实践，不过感觉还不如前面那本《现代编译程序设计》的实践味道更重。此书的重点还是在原理上的实践，而非前面那本那样的技术实践。《编译原理及实践》在讲解编译原理的各个部分的同时，也在逐步实践一个现代的编译器Tiny C.等你把整本书看完，差不多自己也可以写一个Tiny C了。作者还对Lex和Yacc这两个常用的编译相关的工具进行了很详细的说明，这一点也是很难在国内的教材中看到的。

推荐了这三本教材，都有英文版和中文版的。很多英文好的同学只喜欢看原版的书，不我的感觉是这三本书的翻译都很不错，没有必要特别去买英文版的。理解理论的实质比理解表面的文字更为重要。

编译原理的实质

前面已经说过，学习编译原理其实也就是学习算法而已，没什么特别的。只不过这些算法的产生已经形成了一套理论。下面我来看看编译原理里面到底有什么高深的理论吧。

几乎每本编译原理的教材都是分成词法分析，语法分析（LL算法，递归下降算法，LR算法），语义分析，运行时环境，中间代码，代码生成，代码优化这些部分。其实现在很多编译原理的教材都是按照85,86出版的那本龙书来安排教学内容的，所以那本龙书的内容格式几乎成了现在编译原理教材的定式，包括国内的教材也是如此。一般来说，大学里面的本科教学是不可能把上面的所有部分都认真讲完的，而是比较偏重于前面几个部分。像代码优化那部分东西，就像个无底洞一样，如果要认真讲，就是单独开一个学期的课也不可能讲得清楚。所以，一般对于本科生，对词法分析和语法分析掌握要求就相对要高一点了。

词法分析相对来说比较简单。可能是词法分析程序本身实现起来很简单吧，很多没有学过编译原理的人也同样可以写出各种各样的词法分析程序。不过编译原理在讲解词法分析的时候，重点把正则表达式和自动机原理加了进来，然后以一种十分标准的方式来讲解词法分析程序的产生。这样的做法道理很明显，就是要让词法分析从程序上升到理论的地步。

语法分析部分就比较麻烦一点了。现在一般有两种语法分析算法，LL自顶向下算法和LR自底向上算法。LL算法还好说，到了LR算法的时候，困难就来了。很多自学编译原理的都是遇到LR算法的理解成问题后就放弃了自学。其实这些东西都是只要大家理解就可以了，又不是像词法分析那样非得自己写出来才算真正的会。像LR算法的语法分析器，一般都是用工具Yacc来生成，实践中完全没有比较自己来实现。对于LL算法中特殊的递归下降算法，因为其实践十分简单，那么就应该要求每个学生都能自己写。当然，现在也有不少好的LL算法的语法分析器，不过要是换在非C平台，比如Java,Delphi,你不能运用YACC工具了，那么你就只有自己来写语法分析器。

等学到词法分析和语法分析时候，你可能会出现这样的疑问：“词法分析和语法分析到底有什么？”就从编译器的角度来讲，编译器需要把程序员写的源程序转换成一种方便处理的数据结构（抽象语法树或语法树）,那么这个转换的过程就是通过词法分析和语法分析的。其实词法分析并非一开始就被列入编译器的必备部分，只是我们为了简化语法分析的过程，就把词法分析这种繁琐的工作单独提取出来，就成了现在的词法分析部分。除了编译器部分，在其它地方，词法分析和语法分析也是有用的。比如我们在DOS,Unix,Linux下输入命令的时候，程序如何分析你输入的命令形式，这也是简单的应用。总之，这两部分的工作就是把不“规则”的文本信息转换成一种比较好分析好处理的数据结构。那么为什么编译原理的教程都最终把要分析的源分析转换成“树”这种数据结构呢？数据结构中有Stack, Line,List…这么多数据结构，各自都有各自的特点。但是Tree这种结构有很强的递归性，也就是说我们可以把Tree的任何结点Node提取出来后，它依旧是一颗完整的Tree。这一点符合我们现在编译原理分析的形式语言，比如我们在函数里面使用函树，循环中使用循环，条件中使用条件等等，那么就可以很直观地表示在Tree这种数据结构上。同样，我们在执行形式语言的程序的时候也是如此的递归性。在编译原理后面的代码生成的部分，就会介绍一种堆栈式的中间代码，我们可以根据分析出来的抽象语法树，很容易，很机械地运用递归遍历抽象语法树就可以生成这种指令代码。而这种代码其实也被广泛运用在其它的解释型语言中。像现在流行的Java,.NET，其底层的字节码bytecode,可以说就是这中基于堆栈的指令代码的。

关于语义分析，语法制导翻译，类型检查等等部分，其实都是一种完善前面得到的抽象语法树的过程。比如说，我们写C语言程序的时候，都知道，如果把一个浮点数直接赋值给一个整数，就会出现类型不匹配，那么C语言的编译器是怎么知道的呢？就是通过这一步的类型检查。像C++语言这中支持多态函数的语言，这部分要处理的问题就更多更复杂了。大部编译原理的教材在这部分都是讲解一些比较好的处理策略而已。因为新的问题总是在发生，旧的办法不见得足够解决。

本来说，作为一个编译器，起作用的部分就是用户输入的源程序到最终的代码生成。但是在讲解最终代码生成的时候，又不得不讲解机器运行环境等内容。因为如果你不知道机器是怎么执行最终代码的，那么你当然无法知道如何生成合适的最终代码。这部分内容我自我感觉其意义甚至超过了编译原理本身。因为它会把一个计算机的程序的运行过程都通通排在你面前，你将来可能不会从事编译器的开发工作，但是只要是和计算机软件开发相关的领域,都会涉及到程序的执行过程。运行时环境的讲解会让你更清楚一个计算机程序是怎么存储，怎么装载，怎么执行的。关于部分的内容，我强烈建议大家看看龙书上的讲解，作者从最基本的存储组织，存储分配策略，非局部名字的访问，参数传递，符号表到动态存储分配(malloc,new)都作了十分详细的说明。这些东西都是我们编写平常程序的时候经常要做的事情，但是我们却少去探求其内部是如何完成。

关于中间代码生成，代码生成,代码优化部分的内容就实在不好说了。国内很多教材到了这部分都会很简单地走马观花讲过去，学生听了也只是作为了解，不知道如何运用。不过这部分内容的东西如果要认真讲，单独开一学期的课程都讲不完。在《编译原理及实践》的书上，对于这部分的讲解就恰到好处。作者主要讲解的还是一种以堆栈为基础的指令代码，十分通俗易懂，让人看了后，很容易模仿，自己下来后就可以写自己的代码生成。当然，对于其它代码生成技术，代码优化技术的讲解就十分简单了。如果要仔细研究代码生成技术，其实另外还有本叫做《Advance Compiler Desgin and Implement》,那本书现在由机械工业出版社引进的，十分厚重，而且是英文原版。不过这本书我没有把它列为推荐书给大家，毕竟能把龙书的内容搞清楚，在中国已经就算很不错的高手了，到那个时候再看这本《Advance Compiler Desgin and Implement》也不迟。代码优化部分在大学本科教学中还是一个不太重要的部分，就是算是实践过程中，相信大家也不太运用得到。毕竟，自己做的编译器能正确生成执行代码已经很不错了，还谈什么优化呢？

关于实践

编译原理的课程毕竟还只是讲解原理的课程，不是专门的编译技术课程。这两门课程是有很大的区别的。编译技术更关注实际的编写编译器过程中运用到的技术，而原理的课关注讲解其基本理论。但是计算机科学本身就是一门实践性很强的课程，如果能够学以致用，那才叫真正的学会。李阳在讲解疯狂英语的时候就说到，只要当你会实际中运用一个单词一个词组的时候你才能叫学会了这个单词或者词组，而不是只是知道了它的拼写和意思。其实任何学习都是一样的，如果缺少了实践的结合，你不能算学会。

编译原理的课程主要就是讲解编译器产生的理论和原理，那么很简单，自己写个编译器就是最好的实践过程了。不过你得小心，编译系统可能是所有软件系统中最复杂的系统之一,不然为什么大学里面还会把编译器的编写开成一门叫做编译原理的课程来讲？我很佩服那些学了操作系统原理就开始自己写操作系统，学了编译原理就开始自己写编译器的人们，确实，在中国，敢这么做的学生太少了。且不管你这样做能不能做成功，至少有了这个尝试，会让你的程序设计，系统规划安排的功底增进不少。我下面给出一些关于实践过程中可能会遇到的困难，希望能够在你陷入困境的前帮你一把。

1. Lex和Yacc. 这两工具是作为词法分析很语法分析的工具。如果你自己写一个编译器，我十分不建议你连词法分析这种事情都亲手来写。Lex和Yacc应该是作为每本编译原理的教材的必备内容，可是在国内的教材中缺很少看到。这两个工具是Unix系统下的小东西，如果你要在Windows中运用，那么你最好去下在cygwin这个软件。它是个在Windows下模拟Unix的东东，里面就包含了flex.exe和bison.exe(yacc)这两个工具.这两个工具使用起来还挺麻烦的(其实unix 下的很多十分有用的工具都是这样), 不过在《编译原理与实践》这本书上对于这两个工具的讲解十分详细,还列举了不少实际的例子。

2. 做解释型语言比做生成机器代码的编译器简单。虽然说，做解释型的编译器，像Java那样的，你还得自己去写解释器，不过这样你就不必去查找机器代码的资料了。如果你做生成的最终机器代码编译器可能会遇到问题还有就是寄存器为基础的代码生成方法。前面说过，如果你生成的是以堆栈为基础的代码，那么其代码生成过程十分简单，需要考虑的东西也不多，如果你考虑最终的机器代码生成的话，你必须考虑机器的寄存器如何分配等麻烦的问题。

3. 考虑用别人已经生成的语法文件，尽量不要自己动手写词法文件和语法文件.以前一个朋友曾经说过,写出一个好的程序语言的语法定义,就几乎完成了一个编译器的一半.确实是这样,语法文件的编写是个很难的事情.现在网上到处都可以找到比如C语言,C++,Java, Tiny C,Minus C等语言的词法文件和语法文件,你完全可以自己下下来来用.

在《编译原理及实践》的书中，作者给出了一个Tiny C的全部代码.我自我感觉作者的这个编译器做得很不错,相对于其它php,perl等语言的源代码来说,简单得多,容易看懂,而且很清晰地展现了一个完成的编译系统的实现过程.其源代码可以在作者的网站上下载.

后话

编译原理的学习可能算是一个困难的历程,特别是对于那些不对编译系统感兴趣的同学来说.既然它已经作为了大学本科的必修课程,那么就说明的它引申出来的一套理论在整个计算机科学领域还是占有相对重要的地位.

如果我们考究一下历史,就会发现很多被称为程序设计大师的人都是编译领域的高手.写出第一个微型机上运行的Basic语言的比尔盖茨,设计出Delphi的Borland的”世界上最厉害的程序员”, Sun的JAVA之父, 贝尔实验室的C++之父…

puppy 2013-08-24 23:50 发表评论

[ZT]关于哈希表的表大小

puppy — Fri, 29 Mar 2013 09:56:00 GMT

最近我在做一个项目，其中要用到一个数据结构――Hash Table（哈希表），以前只有理论知识，现在实却发现很不简单，所以写下来和大家共分享。

我们知道，哈希表是一个固定大小的数组，数组的每个元素是一个链表（单向或双向）的头指针。如果Key一样，则在一起，如果Key不一样，则不在一起。哈希表的查询是飞快的。因为它不需要从头搜索，它利用Key的“哈希算法”直接定位，查找非常快，各种数据库中的数据结构基本都是它。但带来的问题是，哈希表的尺寸、哈希算法。

哈希表的数组是定长的，如果太大，则浪费，如果太小，体现不出效率。合适的数组大小是哈希表的性能的关键。哈希表的尺寸最好是一个质数，最小的质数尺寸是17。

当然，根据不同的数据量，会有不同的哈希表的大小。对于数据量很时多时少的应用，最好的设计是使用动态可变尺寸的哈希表，那么如果你发现哈希表尺寸太小了，比如其中的元素是哈希表尺寸的2倍时，我们就需要扩大哈希表尺寸，一般是扩大一倍。下面的数库是哈希表变化尺寸时尺寸大小的一个列表。

static int prime_array[] = {
    17,             /* 0 */
    37,             /* 1 */
    79,             /* 2 */
    163,            /* 3 */
    331,            /* 4 */
    673,            /* 5 */
    1361,           /* 6 */
    2729,           /* 7 */
    5471,           /* 8 */
    10949,          /* 9 */
    21911,          /* 10 */
    43853,          /* 11 */
    87719,          /* 12 */
    175447,         /* 13 */
    350899,         /* 14 */
    701819,         /* 15 */
    1403641,        /* 16 */
    2807303,        /* 17 */
    5614657,        /* 18 */
    11229331,       /* 19 */
    22458671,       /* 20 */
    44917381,       /* 21 */
    89834777,       /* 22 */
    179669557,      /* 23 */
    359339171,      /* 24 */
    718678369,      /* 25 */
    1437356741,     /* 26 */
    2147483647      /* 27 (largest signed int prime) */
};

#define PRIME_ARRAY_SIZE (28)

要使用哈希表，就一定要用一个哈希算法，来确定KEY值，这似乎是个很难的事，下面是一个哈希算法：

typedef struct _hTab{
    hLinks* link;    /* 一个链表 */
    int  num;     /* 成员个数 */
    int  size;    /* 表的尺寸 */
} hTab;

static unsigned int
getHashIndex(hTab *tabPtr, const char *key)
{
    unsigned int ha = 0;

    while (*key)
        ha = (ha * 128 + *key++) % tabPtr->size;

return ha;

}

（其中key是一个字符串，hTab就是一个哈希表结构, tabPtr->size是哈希表数组的大小）

这个算法被实施证明是比较不错的，能够达到分散数据的效果，如果你有更好的算法，欢迎和我交流。（litmouse@km169.net ）

puppy 2013-03-29 17:56 发表评论

[ZT]字符串哈希算法比较

puppy — Fri, 29 Mar 2013 09:55:00 GMT

常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。

常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。

Hash函数	数据1	数据2	数据3	数据4	数据1得分	数据2得分	数据3得分	数据4得分	平均分
BKDRHash	2	0	4774	481	96.55	100	90.95	82.05	92.64
APHash	2	3	4754	493	96.55	88.46	100	51.28	86.28
DJBHash	2	2	4975	474	96.55	92.31	0	100	83.43
JSHash	1	4	4761	506	100	84.62	96.83	17.95	81.94
RSHash	1	0	4861	505	100	100	51.58	20.51	75.96
SDBMHash	3	2	4849	504	93.1	92.31	57.01	23.08	72.41
PJWHash	30	26	4878	513	0	0	43.89	0	21.95
ELFHash	30	26	4878	513	0	0	43.89	0	21.95

其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。

经过比较，得出以上平均得分。平均数为平方平均数。可以发现，BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算法本质是相似的。

在信息修竞赛中，要本着易于编码调试的原则，个人认为BKDRHash是最适合记忆和使用的。

BYVoid原创，欢迎建议、交流、批评和指正。

附：各种哈希函数的C语言程序代码

unsigned int SDBMHash(char *str)
{
unsigned int hash = 0;

while (*str)
{
  // equivalent to: hash = 65599*hash + (*str++);
  hash = (*str++) + (hash << 6) + (hash << 16) - hash;
}

return (hash & 0x7FFFFFFF);
}

// RS Hash Function
unsigned int RSHash(char *str)
{
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;

while (*str)
{
  hash = hash * a + (*str++);
  a *= b;
}

return (hash & 0x7FFFFFFF);
}

// JS Hash Function
unsigned int JSHash(char *str)
{
unsigned int hash = 1315423911;

while (*str)
{
  hash ^= ((hash << 5) + (*str++) + (hash >> 2));
}

return (hash & 0x7FFFFFFF);
}

// P. J. Weinberger Hash Function
unsigned int PJWHash(char *str)
{
unsigned int BitsInUnignedInt = (unsigned int)(sizeof(unsigned int) * 8);
unsigned int ThreeQuarters = (unsigned int)((BitsInUnignedInt * 3) / 4);
unsigned int OneEighth  = (unsigned int)(BitsInUnignedInt / 8);
unsigned int HighBits   = (unsigned int)(0xFFFFFFFF) << (BitsInUnignedInt - OneEighth);
unsigned int hash    = 0;
unsigned int test    = 0;

while (*str)
{
  hash = (hash << OneEighth) + (*str++);
  if ((test = hash & HighBits) != 0)
  {
   hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
  }
}

return (hash & 0x7FFFFFFF);
}

// ELF Hash Function
unsigned int ELFHash(char *str)
{
unsigned int hash = 0;
unsigned int x = 0;

while (*str)
{
  hash = (hash << 4) + (*str++);
  if ((x = hash & 0xF0000000L) != 0)
  {
   hash ^= (x >> 24);
   hash &= ~x;
  }
}

return (hash & 0x7FFFFFFF);
}

// BKDR Hash Function
unsigned int BKDRHash(char *str)
{
unsigned int seed = 131; // 31 131 1313 13131 131313 etc..
unsigned int hash = 0;

while (*str)
{
  hash = hash * seed + (*str++);
}

return (hash & 0x7FFFFFFF);
}

// DJB Hash Function
unsigned int DJBHash(char *str)
{
unsigned int hash = 5381;

while (*str)
{
  hash += (hash << 5) + (*str++);
}

return (hash & 0x7FFFFFFF);
}

// AP Hash Function
unsigned int APHash(char *str)
{
unsigned int hash = 0;
int i;

for (i=0; *str; i++)
{
  if ((i & 1) == 0)
  {
   hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
  }
  else
  {
   hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
  }
}

return (hash & 0x7FFFFFFF);
}

puppy 2013-03-29 17:55 发表评论

[ZT]解决哈希（HASH）冲突的主要方法

puppy — Fri, 29 Mar 2013 09:54:00 GMT

虽然我们不希望发生冲突，但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度，而且事先并不知道关键字的具体取值时。冲突就难免会发生。另外，当关键字的实际取值大于哈希表的长度时，而且表中已装满了记录，如果插入一个新记录，不仅发生冲突，而且还会发生溢出。因此，处理冲突和溢出是哈希技术中的两个重要问题。
1、开放定址法
    　用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。
注意：
①用开放定址法建立散列表时，建表前须将表中所有单元(更严格地说，是指单元中存储的关键字)置空。
②空单元的表示与具体的应用相关。
    　按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、线性补偿探测法、随机探测等。
（1）线性探查法(Linear Probing)
该方法的基本思想是：
    将散列表T[0..m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：
        d，d+l，d+2，…，m-1，0，1，…，d-1
    　即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到T[d-1]为止。
探查过程终止于三种情况：
    　(1)若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；
    (2)若当前探查的单元中含有key，则查找成功，但对于插入意味着失败；
    　(3)若探查到T[d-1]时仍未发现空单元也未找到key，则无论是查找还是插入均意味着失败(此时表满)。
利用开放地址法的一般形式，线性探查法的探查序列为：
        h_i=(h(key)+i)％m 0≤i≤m-1 //即d_i=i
用线性探测法处理冲突，思路清晰，算法简单，但存在下列缺点：
① 处理溢出需另编程序。一般可另外设立一个溢出表，专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表，查找方法可用顺序查找。
② 按上述算法建立起来的哈希表，删除工作非常困难。假如要从哈希表 HT 中删除一个记录，按理应将这个记录所在位置置为空，但我们不能这样做，而只能标上已被删除的标记，否则，将会影响以后的查找。
③ 线性探测法很容易产生堆聚现象。所谓堆聚现象，就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突，如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ，则当新的记录加入该表时，与这个序列发生冲突的可能性愈大。因此，哈希地址的较长连续序列比较短连续序列生长得快，这就意味着，一旦出现堆聚 ( 伴随着冲突 ) ，就将引起进一步的堆聚。
（2）线性补偿探测法
线性补偿探测法的基本思想是：
将线性探测的步长从 1 改为 Q ，即将上述算法中的 j ＝ (j ＋ 1) % m 改为： j ＝ (j ＋ Q) % m ，而且要求 Q 与 m 是互质的，以便能探测到哈希表中的所有单元。
【例】 PDP-11 小型计算机中的汇编程序所用的符合表，就采用此方法来解决冲突，所用表长 m ＝ 1321 ，选用 Q ＝ 25 。

（3）随机探测
随机探测的基本思想是：
将线性探测的步长从常数改为随机数，即令： j ＝ (j ＋ RN) % m ，其中 RN 是一个随机数。在实际程序中应预先用随机数发生器产生一个随机序列，将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次序，从而可以避免或减少堆聚。基于与线性探测法相同的理由，在线性补偿探测法和随机探测法中，删除一个记录后也要打上删除标记。

2、拉链法
（1）拉链法解决冲突的方法
    　拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于 1，但一般均取α≤1。
【例】设有 m ＝ 5 ， H(K) ＝ K mod 5 ，关键字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外链地址法所建立的哈希表如下图所示：

（2）拉链法的优点
与开放定址法相比，拉链法有如下几个优点：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

（3）拉链法的缺点
    　拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

puppy 2013-03-29 17:54 发表评论

[ZT]常用字符串hash函数总结

puppy — Fri, 29 Mar 2013 09:53:00 GMT

经典字符串常用的Hash函数有：BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等。BKDRHash和APHash是比较优秀的算法。具体要根据应用，是中文、英文还是混合的字符串，选择合适的Hash算法。

代码实现如下：/**
* FileName: allHash.cpp
* Author: ACb0y
* Create Time: 2011年3月20日21:55:53
* Last Modify Time: 2001年3月21日0:00:22
*/
#include
using namespace std;
typedef unsigned int uint;
typedef struct node
{
char * str;
struct node * pNext;
}node;
node * d[1000000];
/**
* 函数名：uint hashValue(char * str, uint hashFunction(char *str));
* 功能：用指定的hash函数求字符串的hash值
* 参数：
*   输入：
*   str (char *): 字符串
*   hashFunction (uint (char * str)): hash函数指针
*  输出：无
* 返回值：得到的hash值
*/
uint getHashValue(char * str, uint hashFunction(char * str))
{
return hashFunction(str) % 1000000;
}
/**
* 函数名： uint SDBM_Hash(char * str);
* 功能：获取字符串的SDBM哈希值
* 参数：
*  输入：str (char *): 字符串
*      输出：无
* 返回值：字符串的SDBM哈希值
*/
uint SDBM_Hash(char * str)
{
uint hash = 0;
while (*str)
{
  hash = (*str++) + (hash << 6) + (hash << 16) - hash;
}
return (hash & 0x7FFFFFFF);
}
/**
* 函数名： uint RS_Hash(char * str);
* 功能：获取字符串的RS哈希值
* 参数：
*  输入：str (char *): 字符串
*      输出：无
* 返回值：字符串的RS哈希值
*/
uint RS_Hash(char * str)
{
uint a = 63689;
uint b = 378551;
uint hash = 0;
while (*str)
{
  hash = hash * a + (*str++);
  a *= b;
}
return (hash & 0x7FFFFFFF);
}
/**
* 函数名： uint JS_Hash(char * str);
* 功能：获取字符串的RS哈希值
* 参数：
*  输入：str (char *): 字符串
*      输出：无
* 返回值：字符串的JS哈希值
*/
uint JS_Hash(char * str)
{
uint hash = 1315423911;
while (*str)
{
  hash ^= ((hash << 5) + (*str++) + (hash >> 2));
}
return (hash & 0x7FFFFFFF);
}
/**
* 函数名： uint PJW_Hash(char * str);
* 功能：获取字符串的RS哈希值
* 参数：
*  输入：str (char *): 字符串
*      输出：无
* 返回值：字符串的PJW哈希值
*/
uint PJW_Hash(char * str)
{
uint BitsInUnignedInt = (uint)(sizeof(uint) * 8);
uint ThreeQuarters = (uint)((BitsInUnignedInt * 3) / 4);
uint OneEighth = (uint)(BitsInUnignedInt / 8);
uint HighBits = (uint)(0x7FFFFFFF) << (BitsInUnignedInt - OneEighth);
uint hash = 0;
uint test = 0;
while (*str)
{
  hash = (hash << OneEighth) + (*str++);
  if ((test = hash & HighBits) != 0)
  {
   hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
  }
}
return (hash & 0x7FFFFFFF);
}
/**
* 函数名： uint ELF_Hash(char * str);
* 功能：获取字符串的RS哈希值
* 参数：
*  输入：str (char *): 字符串
*      输出：无
* 返回值：字符串的ELF哈希值
*/
uint ELF_Hash(char * str)
{
uint hash = 0;
uint x = 0;
while (*str)
{
  hash = (hash << 4) + (*str++);
  if ((x = hash & 0xF0000000L) != 0)
  {
   hash ^= (x >> 24);
   hash &= ~x;
  }
}
return (hash & 0x7FFFFFFF);
}
/**
* 函数名： uint BKDR_Hash(char * str);
* 功能：获取字符串的RS哈希值
* 参数：
*  输入：str (char *): 字符串
*      输出：无
* 返回值：字符串的BKDR哈希值
*/
uint BKDR_Hash(char * str)
{
uint seed = 131; //31, 131, 1313, 13131, 131313 etc...
uint hash = 0;
while (*str)
{
  hash = hash * seed + (*str++);
}
return (hash & 0x7FFFFFFF);
}
/**
* 函数名： uint BKDR_Hash(char * str);
* 功能：获取字符串的RS哈希值
* 参数：
*  输入：str (char *): 字符串
*      输出：无
* 返回值：字符串的BKDR哈希值
*/
uint DJB_Hash(char * str)
{
uint hash = 5381;
while (*str)
{
  hash += (hash << 5) + (*str++);
}
return (hash & 0x7FFFFFFF);
}
/**
* 函数名： uint BKDR_Hash(char * str);
* 功能：获取字符串的RS哈希值
* 参数：
*  输入：str (char *): 字符串
*      输出：无
* 返回值：字符串的BKDR哈希值
*/
uint AP_Hash(char * str)
{
uint hash = 0;
int i;
for (i = 0; *str; ++i)
{
  if ((i & 1) == 0)
  {
   hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
  }
  else
  {
   hash ^= (~((hash) << 11 ^ (*str++) ^ (hash >> 5)));
  }
}
return (hash & 0x7FFFFFFF);
}
/**
* GCC中的字符串Hash函数ext/hash_fun.h
* 函数名： size_t __stl_hash_string(const char * __s);
* 功能：获取字符串的RS哈希值
* 参数：
*  输入：__s (const char *): 字符串
*      输出：无
* 返回值：字符串的哈希值
*/
inline size_t __stl_hash_string(const char * __s)
{
unsigned long __h = 0;
for (; *__s; ++__s)
{
  __h = 5 * __h + *__s;
}
return size_t(__h);
}
/**
* 函数名： void init();
* 功能：初始化node * d数组
* 参数：
*  输入：无
*      输出：无
* 返回值：无
*/
void init()
{
memset(d, 0, sizeof(d));
}
/**
* 函数名： node * getNode();
* 功能：获取一个新的节点的指针
* 参数：
*  输入：无
*      输出：无
* 返回值：新申请的节点的指针
*/
node * getNode()
{
node * pNew = (node *)malloc(sizeof(node));
pNew->pNext = NULL;
pNew->str = NULL;
return pNew;
}
/**
* 函数名： bool insert(char * str, uint hashFunction(char * str));
* 功能：把字符串插入hash容器中
* 参数：
*  输入：
*    str (char *): 字符串
   uint hashFunction(char * str): hash函数
*      输出：无
* 返回值：
*    false: 插入失败
*   true: 插入成功
*/
bool insert(char * str, uint hashFunction(char * str))
{
node * pNew;
pNew = getNode();
if (NULL == pNew)
{
  return false;
}
pNew->str = (char *)malloc(strlen(str) + 1);
strcpy(pNew->str, str);

uint hashValue = getHashValue(str, hashFunction);
if (NULL == d[hashValue])
{
  d[hashValue] = pNew;
}
else
{
  pNew->pNext = d[hashValue];
  d[hashValue]->pNext = pNew;
}
return true;
}
/**
* 函数名：bool query(char * str, uint hashFunction(char * str));
* 功能：hash容器中查找字符串
* 参数：
*  输入：
*    str (char *): 字符串
   uint hashFunction(char * str): hash函数
*      输出：无
* 返回值：
*    查找到的指向str的指针。
*/
char * query(char * str, uint hashFunction(char * str))
{
uint hashValue = getHashValue(str, hashFunction);
if (NULL == d[hashValue])
{
  return NULL;
}
node * pCur = d[hashValue];
while (NULL != pCur)
{
  if (strcmp(pCur->str, str) == 0)
  {
   return pCur->str;
  }
  pCur = pCur->pNext;
}
return NULL;
}
int main()
{
init();
freopen("in.txt", "r", stdin);
int n, k;
char str[1000];
scanf("%d%d/n", &n, &k);
cout << n << " " << k << endl;

while (n--)
{
  gets(str);
  insert(str, BKDR_Hash);
}

while (k--)
{
  gets(str);
  char * pStr = query(str, BKDR_Hash);
  if (NULL == pStr)
  {
   printf("not found!/n");
  }
  else
  {
   printf("find the string = %s/n", pStr);
  }
}
return 0;
}

puppy 2013-03-29 17:53 发表评论

[ZT]stm32串口问题总结

puppy — Fri, 29 Mar 2013 09:49:00 GMT

STM32串口的问题（转帖）

今天在使用USART模块，遇到了一些问题并解决了，于是发贴共享。
问题描述：
在使用USART做串口通讯时，我只把接收中断打开，并设置抢占优先级为最低一个级别，而接收中断上一个优先级处理事情比较多，可能占用了2ms时间。当我使用9600波特率往下位机发送数据，速度非常快，就是一直按回车发！问题就出来，不到1分钟时间，通讯没有反应了。USART配置代码如下：
void uart_config(void)
{
USART_InitTypeDef USART_InitStructure;
USART_InitStructure.USART_BaudRate = UART_GetBaud(BaudRate);
USART_InitStructure.USART_WordLength = USART_WordLength_8b;
USART_InitStructure.USART_StopBits = USART_StopBits_1;
USART_InitStructure.USART_Parity = USART_Parity_No;
USART_InitStructure.USART_HardwareFlowControl = USART_HardwareFlowControl_None;
USART_InitStructure.USART_Mode = USART_Mode_Rx | USART_Mode_Tx;
USART_InitStructure.USART_Clock = USART_Clock_Disable;
USART_InitStructure.USART_CPOL = USART_CPOL_Low;
USART_InitStructure.USART_CPHA = USART_CPHA_2Edge;
USART_InitStructure.USART_LastBit = USART_LastBit_Enable;
/* Configure USART1 */
USART_Init(USART1, &USART_InitStructure);
/* Enable USART1 receive interrupt */
USART_ITConfig(USART1, USART_IT_RXNE, ENABLE);
/* Enable the USART1 */
USART_Cmd(USART1, ENABLE);
}
分析问题：
1.为什么没有通讯了？
通过仿真器仿真，发现程序一直进入接收中断中，由于我没有使用中断发送，于是程序就死在了接收中断，也就没有数据发送到电脑上来。接收中断代码如下：
void UART_Receive(void)
{
//正在处理上一条通讯，接收到数据不处理
if(bRecieveOK)
{
      if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET)
         USART_ClearITPendingBit(USART1, USART_IT_RXNE);
      return;//processing receive data,don't receive again
}
if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET)
{
      if(MoudBusExpir == 0)
      {
         ucRcePtr = 0;
         MoudBusExpir = 20;//50ms
      }
      else
         MoudBusExpir = 20;
      /* Read one byte from the receive data register */
      ucRS485Buff[ucRcePtr++] = USART_ReceiveData(USART1);
      /* Clear the USART1 Receive interrupt */
      USART_ClearITPendingBit(USART1, USART_IT_RXNE);
}
｝
2.为什么会一直跑到接收中断？
断点之后发现(USART_GetITStatus(USART1, USART_IT_RXNE)==RESET的，也就是说没有数据接收到也进了中断，而且在USART配置中我也只打开了接收中断!没有数据送过来应该是不可能进入中断的！
3.响应了什么中断？
我想通过函数(USART_GetITStatus()把所有中断状态都读出来，但失败了，USART_IT_XXX所有中断状态都是RESET!也就是说没有中断也进入到这个中断服务程序来了！?
4.找资料
STM32F10x微控制器参考手册(2009年12月第10版)P541发现如下说明：
也就是说只要接收中断打开，即RXNEIE设置为1，那么ORE中断也自动打开了。
可是USART_GetITStatus(USART1, USART_IT_ORE )== RESET!!!!
找到USART_GetITStatus(USART1, USART_IT_RXNE)函数，发现只有当USART_IT_ERR中断使能时，才能读到ORE中断。
在这里要指出这个BUG：产生ORE中断了，但使用USART_GetITStatus()函数却无法读到这个中断被SET起来！
5.把ORE中断标志位清除
既然找到了是什么中断，那么把相应的中断标志位清除，就应该可以了吧？
USART_ClearITPendingBit(USART1, USART_IT_ORE);
但是，结果是没有任何效果！清除之后，马上读ORE中断状态，USART_GetITStatus(USART1, USART_IT_ORE)==RESET.程序仍然跑死在接收中断。再使用另一个函数USART_GetFlagStatus(USART1, USART_FLAG_ORE) = SET，原来ORE标志位还没有清除。
6.问题解决
为什么清除不掉？头疼了，再找找资料，有发现，在P523页如下图：
接收中断程序改为：
void UART_Receive(void)
{
if (USART_GetFlagStatus(USART1, USART_FLAG_ORE) != RESET)//注意！不能使用if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET)来判断
{
      USART_ReceiveData(USART1);
}
//正在处理上一条通讯，接收到数据不处理
if(bRecieveOK)
{
      if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET)
         USART_ClearITPendingBit(USART1, USART_IT_RXNE);
      return;//processing receive data,don't receive again
}
if(USART_GetITStatus(USART1, USART_IT_RXNE) != RESET)
{
      if(MoudBusExpir == 0)
      {
         ucRcePtr = 0;
         MoudBusExpir = 20;//50ms
      }
      else
         MoudBusExpir = 20;
      /* Read one byte from the receive data register */
      ucRS485Buff[ucRcePtr++] = USART_ReceiveData(USART1);
      /* Clear the USART1 Receive interrupt */
      USART_ClearITPendingBit(USART1, USART_IT_RXNE);
}
｝
总结：
注意问题：1.USART_ITConfig(USART1, USART_IT_RXNE, ENABLE);使能了接收中断，那么ORE中断也同时被开启了。
            2.ORE中断只能使用USART_GetFlagStatus(USART1, USART_FLAG_ORE) 读到(没有使能USART_IT_ERR中断时)
BUG建议：1.在STM32库中，能不能修改USART_GetITStatus()函数对USART_IT_ORE中断的处理？也就是我只要打开了接收中断，那么有ORE中断时，我也能使用USART_GetITStatus(USART1,USART_IT_ORE)读到.

puppy 2013-03-29 17:49 发表评论

[zt]#define的使用方法

puppy — Tue, 26 Mar 2013 06:16:00 GMT

1. 简单的define定义

#define MAXTIME 1000

一个简单的MAXTIME就定义好了，它代表1000，如果在程序里面写

if(i

编译器在处理这个代码之前会对MAXTIME进行处理替换为1000。

这样的定义看起来类似于普通的常量定义CONST，但也有着不同，因为define的定义更像是简单的文本替换，而不是作为一个量来使用，这个问题在下面反映的尤为突出。

2.define的“函数定义”

define可以像函数那样接受一些参数，如下

#define max(x,y) (x)>(y)?(x):(y);

这个定义就将返回两个数中较大的那个，看到了吗？因为这个“函数”没有类型检查，就好像一个函数模板似的，当然，它绝对没有模板那么安全就是了。可以作为一个简单的模板来使用而已。

但是这样做的话存在隐患，例子如下：
#define Add(a,b) a+b;
在一般使用的时候是没有问题的，但是如果遇到如：c * Add(a,b) * d的时候就会出现问题，代数式的本意是a+b然后去和c，d相乘，但是因为使用了define（它只是一个简单的替换），所以式子实际上变成了
c*a + b*d

另外举一个例子：
#define pin (int*);
pin a,b;
本意是a和b都是int型指针，但是实际上变成int* a,b;
a是int型指针，而b是int型变量。
这是应该使用typedef来代替define，这样a和b就都是int型指针了。

所以我们在定义的时候，养成一个良好的习惯，建议所有的层次都要加括号。

3.宏的单行定义（少见用法）

#define A(x) T_##x
#define B（x) #@x
#define C（x) #x

我们假设：x=1，则有：

A(1)------〉T_1
B(1)------〉'1'
C(1)------〉"1"

（这里参考了 hustli的文章）

3.define的多行定义

define可以替代多行的代码，例如MFC中的宏定义（非常的经典，虽然让人看了恶心）

#define MACRO(arg1, arg2) do { \
/* declarations */ \
stmt1; \
stmt2; \
/* ... */ \
} while(0) /* (no trailing ; ) */
关键是要在每一个换行的时候加上一个"\"

4.在大规模的开发过程中，特别是跨平台和系统的软件里，define最重要的功能是条件编译。

就是：
#ifdef WINDOWS
......
......
#endif
#ifdef LINUX
......
......
#endif

可以在编译的时候通过#define设置编译环境

5.如何定义宏、取消宏

//定义宏
#define [MacroName] [MacroValue]
//取消宏
#undef [MacroName]
//普通宏
#define PI (3.1415926)

带参数的宏
#define max(a,b) ((a)>(b)? (a),(b))
关键是十分容易产生错误，包括机器和人理解上的差异等等。

6.条件编译
#ifdef XXX…(#else) … #endif
例如
#ifdef DV22_AUX_INPUT
#define AUX_MODE 3
#else
#define AUY_MODE 3
#endif
#ifndef XXX … (#else) … #endif

7.头文件(.h)可以被头文件或C文件包含；
重复包含（重复定义）
由于头文件包含可以嵌套，那么C文件就有可能包含多次同一个头文件，就可能出现重复定义的问题的。
通过条件编译开关来避免重复包含（重复定义）
例如
#ifndef __headerfileXXX__
#define __headerfileXXX__
…
//文件内容
…
#endif

8.#define的 do{ }while(0) 用法
如果你想在宏中包含多个语句,可能会这样写:
#define do_something() \
do_a(); \
do_b();

这样你就可以用 do_somethin() 来执行一系列操作.
但这样会有个问题: 如果你下面这样用这个宏地话:

if (...)
do_something();

当宏被展开后就变成:

if (...)
do_a();
do_b();

发现问题没? 原代码的目的是想在 if 为真的时候执行 do_a() 和 do_b(), 但现在呢? 只有 do_a() 在条件语句中, do_b() 任何时候都会执行的.

这时你可能会将那个宏改进一下:
#define do_something() { \
do_a(); \
do_b(); \
}

看样子行了, 是吗? 如果我这个宏是这个样子的呢:
#define do_something() { \
if (a) \
do_a(); \
else \
do_b();
}

这么使用:

if (...)
do_something();
else {
...
}

宏展开后:
if (...)
{
if (a)
do_a();
else
do_b();
}; else {
}

注意到第二个 else 前边那个分号了吗?

所以有人想到了用 do { } while (0) 来解决这个问题, do {} while 语句是需要分号来结束的, 另外, 现代编译器的优化模块能够足够聪明地注意到这个循环只会执行一次而将其优化掉.

综上所述, do { } while(0) 这个技术就是为了类似的宏可以在任何时候使用.

注: 如果你看过 linux 内核源代码, 这个技巧非常常见

puppy 2013-03-26 14:16 发表评论

基础啊！基础！联合体不能在定义时初始化，也不能作为函数参数赋值

puppy — Wed, 20 Mar 2013 06:44:00 GMT

puppy 2013-03-20 14:44 发表评论

【转】直面经典：重温KMP（不着一图，尽得精髓）

puppy — Wed, 20 Apr 2011 03:39:00 GMT

KMP算法，每一个初学者都曾被它搞迷糊，在数据结构教材上，这个算法出现的如此之早，你怎能指望一个还没搞懂二叉树遍历的人来理解KMP呢，记得越快，忘得越快。直到多年以后回过头来看看，这才发现KMP算法如神谕般震撼了我。实在无法想象当初Knuth、Pratt、Morris三人竟然同时发现了它。

我们假设一个场景，你手上拿着一串红蓝两种颜色的珠子，墙上挂着一串更长的珠子，同样是红蓝两色的,你的任务就是找出和你手中珠子排列顺序相同的一段。

最简单也最容易想到的方法，就是从墙上第一颗开始，拿手中的珠子挨个去和墙上珠子去比，都相同那就OK了，不相同再从墙上第二颗开始，以此类推。（文章中我就不给代码了，需要代码的直接跳到正文最后去复制）

有人会想：如果我手里的珠子都是红色的，我还用这种方法，我傻呀？对，Knuth当年也是这样想的。
你看，假设你手里是连续的100颗红色珠子，墙上从第一颗开始是99颗红色珠子，那么当你比到第100颗你才发现少了一颗，你要从第二颗开始再去数一遍吗？没人会这么做，除了程序员。

当然，正常人都要从第100颗之后再去找连续的红色珠子。有了这样的觉悟，我们可以开始进入KMP算法了。

现在抛开珠子的比喻，我们开始用术语："串"，现在手上的珠子称为模式串，墙上的珠子称为主串。任务就是从主串当中寻找模式串。为了突出KMP算法的优势，我们的串都是由0和1组成的。

原始方法的最大问题就是，每当不匹配，就要回头再做比较，这个术语叫回溯。KMP算法用一种巧妙的方法避免了主串的回溯。也就是说，主串从头到尾只需要扫描一遍。（现在还没有办法连模式串都不回溯，所以下文说到回溯均指主串的回溯）

到这里，产生了两个疑问：不回溯是可能的吗？任何情况下都可以不回溯吗？
第一个问题，我们前面已经肯定了，就是某些情况下，例如连续100个1时，我们不需要回溯。
第二个问题，我们的担心是，例如前5个相同，第6个不同，难道你能直接从主串第7个开始和模式串比较？万一从第2个开始恰好和模式串匹配，你就漏掉了。

而KMP的神奇就在于，如果第6个不同，那么接下来我会拿模式串的第1个至第5个之间的一个来和主串第6个比较，至于具体是哪个，由next值决定，这个后面再说。
这个方法保险吗？何止保险，万无一失！这就证明给你看：
当第6个失配时，有五种情况：
模式串前4个与主串第6个之前的相同
模式串前3个与主串第6个之前的相同
模式串前2个与主串第6个之前的相同

模式串前1个与主串第6个之前的相同

模式串前0个与主串第6个之前的相同

无论主串与模式串如何变化，总也逃不出这五种情况，而这五种情况的后续比较方法正好就是拿模式串1至5中间的的一个来继续比较。例如前4个相同，那当然从第5个开始比较；而前面没有相同的，那自然从模式串第1个开始。

这就说明了，任何情况下，主串都不需要回溯，前提是我们拥有next值。

（等等，你忽略了一个问题，如果next值是跟主串有关系怎么办？）
（Re：之前的比较已经说明了一个问题，模式串前5个与主串是相同的，主串这部分已经没有利用价值了，就算要回溯我在模式串上进行就可以了，这个解释总该满意了吧？）

好了，KMP算法可以开始工作了。
方法如下：
1 一开始还像原始方法那样，挨个比较。
2 等失配时，假设这时是主串的第i个，模式串的第j个，拿模式串的next(j)个继续和主串第i个进行比较
2.1 如果相同，那么再挨个比下去
2.1 如果不同，那么重复步骤2
3 比到模式串的最后一位仍然相同，则完成任务
4 比到主串的最后一位仍然未完成任务，则放弃

第2步的next(j)我们看做是一个函数，你不要管它为什么这样神奇，总之如果它能告诉你究竟是哪一个，你就只管用就没错了。

呵呵，看起来仿佛是神的指引呀：你只管比，出错了让神来告诉你由哪一个接着比。
这就是KMP算法了。打完收功。

-----------------------------------------------
（但是，还没有说next(j)怎么出来的呀，这样也行啊？）
其实next(j)的求法才是KMP算法最关键的地方，要理解了它，才算是理解了KMP呀！
我们来探索一下next(j)内部的原理。
前面已经提到，其实next(j)与主串一点关系也没有，这告诉我们，只需要模式串就能生成next(j)。
这么说，next(j)的值完全可以看成一个函数，它的自变量是模式串和失配位置j。
假设某一个模式串里，next(6) = 3的话，这意味着什么呢？
就是说如果第6个位置失配了，那么我直接拿模式串第3个来和主串第6个比较，之所以能这么比，只有可能是模式串的第1、2个和主串的第4、5个是匹配的，但是主串的4、5个和模式串的4、5个也是匹配的，由相等关系的传递性，我们得知模式串的1、2个和4、5个是匹配的。

这给了我们提示，如果模式串内部存在相同的片段，例如123和345相同，或者12和56相同等等这样的情况，那么我们就可以在后一个相同片段的结束出失配时，从前一个相同片段的结束处继续比较。
而如果不存在相同的片段，那么就说明主串失配位置之前的部分不会再有匹配了（否则矛盾了），我们可以从主串失配位置的后一个位置继续比较了。

这样的一对相同片段恰好要从模式串的第一个开始，这样给了我们便利，只需要：
模式串第1个和第2个开始依次比较，

然后第1个和第3个开始依次比较，然后是第1个和第4个，依次类推，就能找到全部可能的相同片段了。
凑巧，这也恰好是一个找寻模式串的任务，自己既是主串又是模式串。
上述的自我比较过程中，在每一次比较相同时，我们都可以记下一个next值，
而出现失配时，我们从主串的下个位置重新开始比，等等，想起什么来了，对，主串不需要回溯。我们不是记下了前一个next值吗？
而如果第一次就不同呢，所以我们进行一个规定，next(1)=0，next(2)=1，这样在第1个和第2个比较时，next(2)的值已经有了，随后每一个比较都已经有了当前位置的next值了。这里next值为0是表示失配位置前不可能有匹配了，这时主串从失配位置的后一个继续比，而这个位置的next值我们同样记为0。

这样看起来，寻找next值的过程和KMP本身比较的过程何其相似呀！
不过我们注意到一点，它们并不需要相似，实际上求next值的过程不用KMP方法，用原始方法一样可以求出来，但是要麻烦一些，需要后一趟比较不要把前一趟记下的next值覆盖了。

至此KMP算法的精髓应该介绍完了吧，还剩下最后一点，就是所谓的next修正值。
这个是在求next值的过程中修正的，不修正也不影响匹配结果，修正算是一种优化吧！
具体说来，修正是这么回事：

如果在j出失配时，不是要跳到next(j)吗？而如果又失配了，不是要跳到next(next(j))吗，如果又失配，就跳到next(next(next(j)))……
为了省略不停的跳的过程，我们注意到，如果第j个和第next(j)个是相同的，那么j失配了，next(j)一定失配。既然这样，那又何必再比呢，所以计录next值的时候，就判断一下是否相同，如果相同，就直接使用上一个next值。

至此，KMP算是全部结束完毕了。代码网上满天飞，我这就不给了。

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/oyd/archive/2008/10/20/3110435.aspx

puppy 2011-04-20 11:39 发表评论

S3C2440下UDA1341驱动源代码(linux-2.6.26)

puppy — Fri, 10 Oct 2008 11:41:00 GMT

摘要: 主要是luofuchong和zhongtianhua大侠 linux-2.6.22下的源代码,做了少许修改,可配合mplayer-1.0rc2使用环境为: linux-2.6.26 s3c2440 uda1341在我的板子上是可以工作的.另外, L3MODE L3CLCOK L3DATA需要定义成具体硬件上的IO引脚, 代码中已经用宏做了定义了,简单... 阅读全文

puppy 2008-10-10 19:41 发表评论