收藏的一些资料

[size=x-large][/size]             网络爬虫
摘 要：网络爬虫是目前比较流行的一种网页检索工具，其设计和实现也需要不断优化和改进。通过描述网络爬虫设计与实现中所碰到的问题，提供解决这些问题的方法，并给出实现这些目标的网络爬虫设计方法，提供该设计的Java 语言版实现。　　关键词：网络爬虫；链接检索；文字匹配；爬虫设计；多线程引言　　目前，对于全球大多数互联网用户来说，搜索引擎是其准确获得所需要信息或者知识的最有效的工具。但是对于所有的搜索引擎来说，最重要的性能指标有两个：查全率和查准率。查全率与搜索引擎搜集的网页数量和质量有关。　　本文介绍的是用于搜集网页， 提高查全率的最重要的工具—网络爬虫(Web Crawler)的设计与实现。网络爬虫的主要作用是搜集互联网的网页，也可以用它来定期搜集某个网站的内容，跟踪判断网站的发展，或者做站内搜索引擎。从网络爬虫的工作原理来看，“网络爬虫”是一个比较形象的名字，它是在互联网内，通过网页链接，从当前网页爬到下一个网页来进行网页内容搜集的工具。它所需完成的工作[1]如下：(1)在一个网页上，获取网页的标题和网页中的摘要；（2）将搜集到的网页标题，链接，网页的摘要放入数据库中；(3)根据当前网页的内容，搜集网页中的链接信息，并根据链接顺序搜索相应链接网页的内容。1 Web Crawler 中的若干问题不同的Web Crawler，在设计的时候侧重各有不同，本文所介绍的Web Crawler 在设计的时候主要考虑解决以下几个问题：(1)Web Crawler 遍历网页中的所有链接，并且能对所搜索的网页进行搜索深度的限制；(2)Web Crawler 能够提取出网页中的摘要和标题信息，并且保存到数据库中；(3)要求能够对已有的搜索引擎的搜索结果再优化，提高所设计的Crawler 的扩展能力；(4)要求能够采用多线程的方式，提高搜索的效率。针对前述的四个目标，在设计Crawler 的时候，具体考虑了如下一些问题。首先Crawler 的搜索深度的问题，网页中的链接关系是相当复杂的，一组网页之间可以互相包含，网页A 中的链接可以指向网页B，同时网页B 中的链接也可以指向网页A。因此，网页的搜索深度必须作一定的限制，不能无限制的递归搜索；其次网页的搜索方式也有差别，有些爬虫采用广度优先策略 (BFS)，有些采用了深度优先策略(DFS)[2]，考虑到实现时采用多线程，且所设计的Crawler需在搜索的深度上作了限制，所以采用深度搜索的方式。对于搜集所有url 链接，可以有不同的方式，本文采用的正则表达式。尽管具体的实现有多种方式，搜集链接也可以采用后面所提到的HtmlParser 包，但是采用正则表达式，是一种方便，快捷的手段，Java 语言也提供对正则表达式的支持。多线程程序是编程中比较复杂的问题，除了对线程的调试比较困难外，对线程所使用的资源的控制也同样复杂。在Java 平台下对多线程的编程有充分支持，因此在设计Crawler 的多线程实现时，采用了Synchronous 关键字，原子数(AtomicInteger)和线程池[3]，通过使用线程池，在应用启动的时候，设置所需创建的线程数量，一旦线程池为空，则挂起当前请求，等待空闲的线程出现；原子数则可以保证程序中的计数以互斥的方式操作，保证了递增和递减操作的原子性；而Synchronous 保证了不同线程在访问数据的时候不会出现两个线程同时访问一个数据。本文中实现的Crawler 中第三个考虑的问题就是获取网页的内容、提取网页摘要信息和标题信息。网页内容的获取方式有多种，比较常用的就是想网页发出一个Http 请求，并获取返回的字符流。考虑到实现这种请求/响应方式的复杂性，本文采用了HtmlParser[4]包来具体实现网页内容的获取。对于标签的获取采用两种方式，一种是采用HtmlParser包来获取，另外一种提取文本的方式也可以使用正则表达式[5]，在构造合适的正则表达式时，需要考虑到标签的特殊结构，为了提高文字的抽取效率，可以对一段html 源码首先过滤掉一些不需要的标签。采用HtmlParser 包除了能够获得网页的内容外，该包还能提供一系列的获取网页内容的工具类，获取特定标签，并通过标签筛选规则的运用，获取包含有文字的标签，提取出其中的文字作为摘要；对于标题通过获取<title>标签，获得网页的标题。2 Web Cralwer 的设计本节介绍Web Crawler 的设计，包括类的设计和时序图的设计。本文所实现的Web Crawler 采用MVC 的设计方式，前台设计成Web 页面，发送Web 请求；后台Servlet 接受前台发送过来的请求。在后台，有如下几部分的内容：描述数据实现的ICrawlerModel 接口及其实现；表示多线程搜索的ICrawler 接口、AbstractCrawler 和MultipleThreadCrawler 类；工具类IParser 接口和HtmlParser 类；表示链接的数据结构Link 和LinkDepth 类；以及存储结果的DbAccess 类。上述类的实现都是采用Java，数据库使用MySQL，除此以外还要用Tomcat Web 服务器，如图1 所示。前台的设计使用jsp+jQuery 的方式，jQuery 是一种javascript 工具包，提供对ajax 的支持，能够实现无刷新的页面布局。Ajax 是目前一种流行的设计网页的方式。后台采用Servlet 运行方式，获取前台通过ajax 方式提交的参数，根据不同的选择（可能是关键词的搜索，也可能是某一个网址的搜索）进行处理。MultipleThreadCrawler 实现了抽象类AbstractCrawler，它是Crawler 实现的核心内容，主要对每一次的搜索数据的处理，多线程的协调等。在该类中实现两个私有类Worm 和TextExtractor，前者实现对网页链接的搜索，并填充入Model中的toVisitUrls 数据结构中，后者则是对当前搜索的网页提取标题和摘要信息。MaxDepthModel 是一个存储数据的类，其包括已经访问过的Url 和未访问过的Url，并且提供向数据结构中填充未访问的Url。采用接口的方式，也是为了能够在今后扩展具体实现。HtmlParser 提供了对文本解析的方法，图2 给出的用户提交待搜索的网站的时序图：3 Web Crawler 的实现本文设计的Web Crawler 采用Java 语言和MySql 来实现，作为开源工具的组合，被应用在很多重要的领域。除了前述提到的实现细节外，在获取html 文本中的url 链接时使用了正则表达式，可以提高文字的匹配速率和程序的运行效率（采用Java 包匹配往往比较复杂）。同时在抽取html 文本的文字信息时，也使用了这种技术，由于正则表达式表述的灵活性，并没有一种能够适合所有情况的匹配表达式，只有在实践过程中不断改进和优化。

数据结构系列教程------精讲（JAVA版）

数据结构系列教程------精讲（JAVA版）接触不少程序员，都能够独立的作一下小型应用系统，和他们交谈起来才发现，他们纯粹是程序员，对基础的掌握太差，比喻java程序员，就是对jdk和各种框架特别的熟悉，能够熟练的运用其中的各种包、类以及一些组件，确实能做出一下系统来，但是涉及到一些特殊的设计方法来就不行了，对基础掌握太差，包括现在的很多培训，都是灌输这些所谓的实际应用的东西，学好基础才是最关键的东西，学一门语言很快，没有很好的基础、清晰的思路只能照葫芦画瓢了，为此，笔者结合自己的学习经验写了系列教程，主要包括数据结构的全部内容：线性表、树、图、数组、集合、矩阵、排序、查找、哈希表，并将java的设计思想、方法及一些常见的算法、设计模式贯穿其中，希望能给初学者一个很好的帮助，由于本人水平有限，同时请大家给与批评指正！第一讲 线性表   数据结构包括数据的逻辑结构、储存结构以及对数据的操作，线性表的含义就是：除了第一个和最后一个数据元素，其他的只有一个前驱元素和一个后继元素，如下图：   A--->B--->C--->D这个就是一个最简单的线性表的实例，结合定义可以很好的理解的，数据结构中最常见的就是提到抽象数据类型，所谓抽象数据类型就是在基本数据类型支持下用户新设计的数据类型，通俗的说就是用户对基本数据类型（整型、浮点型等等）的组合应用成自己的一种新型的数据类型，也就是java中接口和抽象类，这么说可能有些不妥，不过这样最好理解，前面讲到数据结构包括对数据的操作，这个设计数据结构的最终目的，下面我们就讲讲java数据结构中的线性表的设计思想。由于线性表的数据集合可以表示为序列：A1,A2,A3……….An-1,每个元素的类型都是任意的，对于这个集合的操作可以归结如下：(1)求出当前集合中数据元素个数（size）;(2)向当前数据集合任意位置插入新的数据(insert);(3)删除当前数据集合中的任意数据(delete);(4)获取当前数据集合中的任意数据(getData);(5)判断当前数据集合是否为空;，由于存在很多不同形式的线性表结构，对其操作方式当然也不一样，这样就要求设计一个大家都能使用的数据类型，由前面的讲述大家就可以想到必须要设计一个抽象数据类型，也就是一个接口，这时可能有人问为什么不设计一个抽象类阿？这个问题留个大家思考，可以到论坛发表。Java中可以这样定义这个接口：public interface List {/*** @author 天意*/       public void insert(int i,Object obj ) throws Exception;//在任意位置插入数据       public Object delete(int i) throws Exception;//删除任意位置的数据       public Object getData(int i) throws Exception;//获取任意位置的数据       public int size();// 获取当前集合的大小       public boolean isEmpty();//判断当前集合是否为空}，由于所有线性表的操作都是围绕以上而来的，所以上面的接口就可以通用于所有线性表了，这就告诉大家在设计程序时要做好充分的考虑，强调一个“广”字。线性表包括顺序表和链式表，首先讲一下顺序表，顺序表顾名思义，就是数据元素按一定组合在一起的，逻辑上相邻的元素在物理储存上也是相邻的，如下如示例：A0 A1 A2 A3 A4 A5 ……   
0       1          2         3        4         5                maxSize-1结合这个图我们可以想到：首先建立这个表就必须有个初始大小，然后才能对他就行实际操作，插入操作时可能会出现表已满、插入位置不存在的情况，删除时可能出现表已空、删除的元素不存在的情况，获取时可能出现要求的元素不存在的情况，考虑这些因素就可以设计这个顺序表的操作类了SeqList.java，具体内容如下：public class SeqList implements List {       /**        * @author 天意        */       final int defaultSize=10;//默认为10个，你可以自己随便改       int maxsize;       int size;       Object[] listArray;       public SeqList(){              initiate(defaultSize);       }       public SeqList(int size){              initiate(size);       }       private void initiate(int sz) {              //初始化              maxsize=sz;              size=0;              listArray=new Object[sz];       }       public void insert(int i, Object obj) throws Exception {              // 在i位置插入obj对象     if(size==maxsize){            throw new Exception("顺序表无法插入");     }     if (i<0||i>size){            throw new Exception("参数错误");     }     for(int j=size;j>i;j--)            listArray[j]=listArray[j-1];         listArray[i]=obj;         size++;       }       public Object delete(int i) throws Exception {              // 删除i位置的元素              if (size==0){                     throw new Exception("顺序表已空无法删除！");              }              if(i<0||i>size-1){                     throw new Exception("参数错误！");              }              Object it=listArray[i];              for(int j=i;j<size-1;j++)                     listArray[j]=listArray[j+1];              size--;              return it;       }       public Object getData(int i) throws Exception {              // 获取i位置的元素并返回              if(i<0||i>=size){                     throw new Exception("参数错误！");              }              return listArray[i];              }       public int size() {              //获得大小              return size;       }       public boolean isEmpty() {              // 判断是否为空              return size==0;       }       public int MoreDataDelete(SeqList L,Object x)throws Exception{              int i;              int tag=0;              for( i=0;i<L.size;i++){                     if(x.equals(L.getData(i))){                            L.delete(i);                            i--;                            tag=1;                     }                                   }              return tag;       }}，以上就可以实现顺序表的所有操作了，你可以自己试一下，这里要说明的是，因为顺序表中储存的对象类型可以任意，所以设计时一定要使用Object类，当然有时为了限定具体类型你可以重写这个类然后抛出相应的异常即可，这个顺序表的效率分析工作留给大家，大家可以到论坛跟贴，下一讲链式表！

线性表的概念大家应该还记得，链式表是线性表的一个分类，当然也具备线性表的所有特性了，只不过它的结构方式特异而已，也就是和链子似的，和顺序表的不同之处在于链式表引入对象应用，就是其他语言中的指针，每个链子（我自己的说法）包含一个数据元素(element)和一个指针域(next)，这个链子就称为节点，通俗的说有很多节点连接成的线性表就是链式表，根据其结构方式又可以分为单链表、单循环链表、双向链表，还有一种不常用的仿真链表，所有的链表都有一个共同的特征，都是由节点组成，根据前一章的思想我们很自然的会想到要构造一个节点类Node.java：public class Node {/*** @author 张钰*/       Object element;//数据元素    Node next;    Node(Node nextval){            next=nextval;    }   Node(Object obj,Node nextval){        element=obj;        next=nextval;   }public Object getElement() {       return element;}public void setElement(Object obj) {       element = obj;}public Node getNext() {       return next;}public void setNext(Node nextval) {       next = nextval;}public String toString(){       return element.toString();}   ,节点类的构造就是为了实现链表的操作，链表最常见的是单链表，单链表就是其每个节点都只有一个指向直接后继节点的指针，其中包括带头节点的和不带头节点的，根据单链表的结构我们可以设计如下的类LinList.java（注意和java中的LinkList不一样，LinkList是个线性结构容器，提供线性表、堆栈、队列等操作）：/*** @author 张钰**/public class LinList implements List {       Node head;//头指针       Node current;//当前节点位置       int size;//数据元素个数       LinList(){              head=current=new Node(null);           size=0;       }       public void index(int i) throws Exception{ //定位元素             if(i<-1||i>size-1){                    throw new Exception("参数错误");             }             if(i==-1) return;             current=head.next;             int j=0;             while((current!=null)&&j<i){                    current=current.next;                    j++;             }       }       public void insert(int i, Object obj) throws Exception {              // 插入           if(i<0||i>size){                  throw new Exception("参数错误");           }           index(i-1);           current.setNext(new Node(obj,current.next));           size++;       }       public Object delete(int i) throws Exception {              // 删除              if (size==0){                     throw new Exception("链表已空无元素可删除！");              }              if(i<0||i>size-1){                     throw new Exception("参数错误");              }              index(i-1);              Object obj=current.next.getElement();              current.setNext(current.next.next);              size--;              return obj;       }              public Object getData(int i) throws Exception {              // 获取元素              if(i<-1||i>size-1){                     throw new Exception("参数错误");              }              index(i);              return current.getElement();       }              public int size() {              // 获取元素个数              return size;       }       /* （非 Javadoc）        * @see List#isEmpty()        */       public boolean isEmpty() {              // 判断是否为空              return size==0;       }}，设计说明：(1)构造函数完成三件事：创建头节点，使head和current均表示所创建的头节点，置s ize为0；(2)定位成员函数index(int i)的实现，其设计方式是：用一个循环过程从头开始计数寻找第i个节点；顺序表和单链表的比较：顺序表和单链表的逻辑功能完全一样，但是两者的应用背景以及不同情况下的使用效率略有不同，顺序表的主要优点就是支持随机读取，以及内存空间利用效率高，顺序表的主要特点就是需要给出数组的最大数据元素个数，而这通常很难准确做到，另外，顺序表的插入和删除操作时需要移动较多的数据元素，单链表的缺点就是每个节点中都有个指针，所以其空间利用率略低于顺序表，单链表不支持随机读取。单链表另一种常见的形势就是循环单链表，其结构特点就是链表中最后一个节点的指针不再是结束标记，而是指向整个链表的第一个节点，从而使单链表形成一个环，，就是在构造函数中增加head.next=head，在定位函数index(i)中，把循环结束条件current!=null换成current!=head，这样最后一个节点就循环到第一个了！链表最常见的一个应用就是循环双链表，java中的LinkedList就是通过循环双链表来实现的，其长度可以随着数据元素的增减很容易的变化，LinkedList提供了线性表、堆栈、队列、双端队列等数据结构所要求的全部成员函数，例如addFirst()和removeFirst()就是支持堆栈所要求的成员函数，这里就不过多讲解了，回到循环双链表，双向链表中每个节点包括三个域：element、next、prior，其中element是数据元素，next是指向后继节点的对象应用，prior是指向前驱节点的对象应用，prior element next
设p为第i个节点，则p.next为第i+1个节点，p.next.prior==p,这就是双向链表的方式，结合前面的内容，双向链表类的设计留给大家，有兴趣的同学可以和我一起讨论！最后还有仿真链表，链式储存结构中，实现元素之间的关系靠的是指针，但是也可以用数组来构造仿真链表，方法是在数祖中增加一个（或两个）int类型的变量域，这些变量用来表示后一个或前一个元素在数组中的下标，这就是仿真链表，其应用不是很多，这里就不多介绍，有兴趣的同学可以研究，下一讲：堆栈和队列！


第三讲 堆栈和队列
堆栈和队列都是特殊的线性表，他们的逻辑关系完全相同，差别是线性表的插入和删除操作不受限制，而堆栈只能在栈顶插入和删除，队列只能在队尾插入、队头删除，堆栈和队列都可以分别用顺序储存结构和链式存储结构，堆栈的操作主要有入栈、出栈、取栈顶元素、是否为空，可以设计通用接口Stack..ava如下：/*** @author**/public interface Stack {    public void push(Object obj) throws Exception;//把数据元素obj插入堆栈    public Object pop()throws Exception;//出栈，删除栈顶元素并返回    public Object getTop()throws Exception;//获取栈顶元素    public boolean notEmpty();//判断是否为空}下面就不同的结构展开：(一)顺序堆栈   具有顺序储存结构的堆栈称为顺序堆栈，顺序堆栈和顺序表的数据成员是相同的，只是顺序堆栈的入栈和出栈操作只能在当前栈顶进行，其结构可以参考下图：栈底                                栈顶a0 a1 a2 a3 a4    
satck                                         top=5             maxStackSize-1stack表示顺序堆栈储存数据的数组，a0、a1等表示已经入栈的数据，a0比a1先入栈，maxStackSize表示顺序堆栈数组stack的最大元素个数，top表示顺序堆栈的stack的当前栈顶的下标，设计顺序堆栈类如下SeqStack.java：/*** @author**/public class SeqStack implements Stack {       /*        * @see Stack#push(java.lang.Object)        */    final int defaultSize=10;    int top;    Object[] stack;    int maxStackSize;    public SeqStack(){           initiate(defaultSize);    }    public SeqStack(int sz){           initiate(sz);    }       private void initiate(int sz) {              // 初始化              maxStackSize=sz;              top=0;              stack=new Object[maxStackSize];       }       public void push(Object obj) throws Exception {              // 插入堆栈         if(top==maxStackSize){                throw new Exception("堆栈已满！");         }         stack[top]=obj;         top++;       }       /*        * @see Stack#pop()        */       public Object pop() throws Exception {              // 出栈              if(top==0){                     throw new Exception("堆栈已空！");              }              top--;              return stack[top];       }       /*        * @see Stack#getTop()        */       public Object getTop() throws Exception {              // 获取栈顶数据              if(top==0){                     throw new Exception("堆栈已空！");              }              return stack[top-1];       }       /*        * @see Stack#notEmpty()        */       public boolean notEmpty() {              // 判断是否为空              return (top>0);       }}(二) 链式堆栈链式堆栈具有链式存储结构，用节点构造链，，每个节点由两个域组成，一个是存放数据元素的域element，另一个是存放下一个节点的对象引用域也就是指针域next,堆栈有两端，插入数据和删除元素的一端为栈顶，另一端为栈底，链式堆栈都不带头节点（大家可以思考一下为什么？），链式堆栈类的设计LinStack.java：public class LinStack implements Stack{Node head;//堆栈头int size;//节点个数public void LinStack(){head=null;size=0;}public void push(Object obj){//入栈head=new Node(obj,head);//新节点为栈顶}public Object pop() throws Exception{ //出栈if(size==0){throw new Exception(“堆栈已空”);}Object obj=head.element;//取原栈顶元素head=head.next;//原栈顶节点脱链Size--;Return obj;}public Boolean notEmpty(){return head!=null; //是否空}public Object getTop(){return head.element; //取栈顶元素}}，堆栈由于其操作的特殊性而存在，在很多地方能起到独特的作用，比喻中缀表达式转换成后缀表达式，编译软件中的括号匹配问题（eclipse中就很好）都是使用堆栈的特殊性来设计算法，具体的问题大家可以和我一起交流！下面讲讲队列，队列的特点就是从队尾插入、队头删除，也是一种特殊的线性表，队列的操作和堆栈一样主要有：入队列、出队列、取队头数据元素、是否为空，队列的接口类Queue.java可以设计如下：/*** @author**/public interface Queue{public void append(Object obj) throws Exception;public Object delete()throws Exception;public Object getFront() throws Exception;public Boolean notEmpty();}(三)顺序队列具有顺序结构的队列就叫顺序队列，顺序队列存在假溢出问题，就是一个队列最大存储为6个元素，现在有a0 a1 a2 a3 a4 a5六个元素入队列了，然后又有a0 a1 a2三个元素出队列了，这样剩下的三个元素占据的还是队列的后三个位置，这时候要是有新的元素入队列就会出现数组越界，而事实上队列没有满，这就是假溢出问题，出现问题的原因就是队尾rear和队头front的值不能由所定义数组下界值自动转化成上界值而产生的，解决的办法就是把顺序队列所使用的储存空间构造成一个逻辑上首尾相连的循环队列，当队尾rear和队头front达到maxSize-1后，再自加1自动到0，这样就不会出现队列数组头部已空但队尾因数组下标越界而引起的溢出的假溢出问题，解决顺序循环队列的队列满和队列空状态判断问题通常三种方法：  1．少用一个储存空间，以队尾rear加1等于队头front为队列满的判断条件，即此时队列满的判断条件为：(rear+1)%maxSize=front，队列空的条件为：rear=front；   2．设置一个标志位，添加一个标志位，设标志位为tag，初始时置tag=0，每当入队列操作成功时就置tag=1，出队列操作成功时标志tag=0，那么此时队列满的判断条件是：rear= =front && tag= =1，队列空的判断条件是：rear==front && tag= =0；   3．设置一个计数器，添加一个计数器count，初始count=0，每当入队列操作成功时count加1，每当出队列操作成功count减1，这样计数器不仅有标示功能还有计数功能，此时判断队列满的条件是：count>0 && rear= =front，队列空的条件是：count= =0；上面三种方法很明显最好的是第三种使用计数器的方法，采用这种计数器的办法可以设计顺序循环队列的类SeqQueue.java如下：   public class SeqQueue implements Queue{      static final int defaultSize=10;      int front;      int rear;      int count;      int maxSize;      Object[] data;      public SeqQueue(){     initiate(defaultSize);}public SeqQueue(int sz){initiate(sz);}public void initiate(int sz){maxSize=sz;front=rear=0;count=0;data=new Object[sz];}public void append(Object obj) throws Exception{   if(count>0 && front= =rear){throw new Exception(“队列已满！”);}data[rear]=obj;rear=(rear+1)%maxSize;count++}public Object delelte() throws Exception{         if(count= =0){    throw new Exception(“队列已空！”);}Object temp=data[front];front=(front+1)%maxSize;count- -return temp;}public Object getFront() throws Exception{    if(count= =0){    throw new Exception(“队列已空”);}return data[front];}public Boolean notEmpty(){   return count!=0;}}以上就是顺序队列的java表示，大家可以自己做些例子测试一下，队列还有一种就是链式队列，链式队列就是具有链式结构的队列，链式队列通常设计成不带头节点的结构，结合以前的链式表可以很容易设计出链式队列的类，这个任务就留给大家了，队列就是一种从队尾进入队头删除的特殊的顺序表，设计时还考虑了一种优先级队列，就是给队列中的每个元素添加一个优先级标示，出队列时按优先级从高到低的顺序进行，这就是优先级队列，在系统进程管理中的应用很广泛，这个优先级队列这里不做过多的阐述，有兴趣的同学可以研究研究，也可以和我一起探讨！