《高等数据结构》项目报告书

'课程期末论文论文标题：Trie结构实现的英文搜索引擎课程名称：高等数据结构与算法分析课程编号：SF03014_01学生姓名：李鹤学生学号：1108521204所在学院：计算机科学与工程学院学习专业：软件工程课程教师：周娅2012年02月27日 一．系统概述随着现代社会互联网的发展，搜索技术已经成为人们关注互联网信息不可或缺的一项技术。人们总是希望通过简简单单几个字就可以查询到自己关注的信息。早在1990年，蒙特利大学的学生AlanEmtage就开发了一个信息的搜索引擎---Archie，由于当时没有互联网，大家都是靠FTP进行传输的，所以此程序搜索的信息基于FTP的。到了1994年，Lycos出现才使搜索引擎具有了划时代的意义，其中的实现的网络爬虫可以帮助搜索引擎进行信息扩充。1994年4月，yahoo的出现才标志着搜索引擎进入了迅速发展的膨胀期。此后，google，百度慢慢成为了搜索引擎行业的头老大。此次课程设计重点就是完全模拟一个搜索引擎的全过程，从网络爬虫的设计，到网页信息的下载，处理，提取，把网页信息中的单词全部提取出来，通过这些单词建立一棵TRIE树，所有的单词都是建立在这棵树上，查询也是通过这棵trie进行的。该搜索引擎主要分成两大部分：1.网络爬虫，即从主站点下载寻所需要的网页内容到服务器硬盘上，并把下载的网页的物理地址和所在网站的URL地址关联起来，建立地址-链接索引表。2.Trie树结构的实现，即通过java程序算法实现一棵可以自由查询单词的数据结构，在此之前需要对下载的网页进行内容的处理，满足需要之后，分词进行插入来完成一颗标准的trie树。二．需求分析2.1任务概述本次课程设计是实现一个搜索引擎，主要分成两个部分，一是网络爬虫部分，二是trie树的部分。网络爬虫主要实现的功能是通过多线程把一个站点的相应深度的网站地址连接全部下载一下来，再通过地址连接把相应的网站下载内容下载下来。这些网页在硬盘的地址需要和它的URL地址相应的联系起来，这样以便后面构造trie树的时候使用。同时在爬虫阶段，直接把所需要的网页下载到硬盘中。由于此引擎只是为了模拟，所以在搜索阶段只是把网页的内容进行检索，其他格式的的信息没有考虑在内。通过建立一张地址-URL表的文件，把网页在硬盘中的地址和其代表的URL地址连接起来。Trie树的构造阶段首先需要把HTML网页文件进行处理，那些布局用的标签语言全部清除掉，这些标签语言对于文件的信息帮助很少，但不是绝对，例如在以下标签中：在name为Keywords的标签中，Content显示了该页面以及该网站的关键字，这些关键字能帮助网络爬虫最快的知道该页面显示什么内容。在大型的搜索引擎中，有选择式的爬行就通过这个标签的内容来决定是否需要爬行该网站。 标签语言的清除通过正则表达式的构造。程序中对标签的处理主要包括几个方面：script标签，style标签，html标签，特殊符号，过多的空格，以及一些制表符等。Trie树的实现需要克服的问题有几项：1.trie节点的数据结构；2.如何遍历整棵树；3.如何确定该单词已经查到了；4.url地址链表怎样关联起来。2.2任务目标此次课程设计的任务主要在两个方面：一，通过网络爬虫把相应站点的相应层次内容下载下来并创建地址-UrL表；二，建立供查询用的Trie结构。2.3输入要求搜索引擎的输入方面主要有三个参数：1）需要爬行的Url地址，必须是符合标准的地址，否则不能通过正则表达式的筛选；2）需要爬行的深度，每个网站我们不需要完全爬行，完全爬行是很浪费资源的；3）由于此系统的局限性，我们需要事先添加好需要查询的单词。2.4环境描述本系统采用的是java语言，jdk1.6平台。Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由SunMicrosystems公司于1995年5月推出的Java程序设计语言和Java平台（即JavaSE,JavaEE,JavaME）的总称。Java技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于个人PC、数据中心、游戏控制台、科学超级计算机、移动电话和互联网，同时拥有全球最大的开发者专业社群。在全球云计算和移动互联网的产业环境下，Java更具备了显著优势和广阔前景。Java中提供了对于网络编程众多的基础包和类，比如URL类、InetAddress类、正则表达式，这为我们的搜索引擎实现提供了良好的基础，使我们可以专注于搜索引擎本身的实现，而不需要因为这些基础类的实现而分心。概要设计三概要设计3.1基本设计概念与处理流程首先通过URL爬虫程序对指定站点进行爬行，把爬行得到的页面下载到本机硬盘上存储起来。并把网页的硬盘上的存储地址和URL地址关联起来存储到本机的硬盘TXT上面。通过java中的正则表达式把网页中的无关系的标签语言进行处理，得到纯净的Web版本的txt文件，即全部含有的是需要的信息。通过txt文件读取程序对Web版本的txt文件进行适当行数的读取，用于给trie树的构造减轻一次性的压力。文本内容准备好之后，便可以通过调用程序来完成trie树的构造，构造调用只需要每个单词带着自己的URL地址加进去就行。Trie树构造完毕，通过实现预设的查询单词，完成一次查询，并查找相关的网页URL地址。 处理过程如下：3.2结构本程序一共分为八个部分，结构图如下： AnalysisUrlFile分析FilepathIndex文件，并存储在内存中GetWeb爬取网页信息，生成并存储FilepathIndex文件ReadtheHtml读取WebTXT文件中的数据并控制读取的行数RetrieveALLWord过滤掉无用的标签语言，并把单词逐个输出SimpleBloomFilter去重算法Trie构造trie结构GenerateTree实现所有过程的总程序TestMain测试程序，调用所有过程四详细设计与编程实现4.1多线程实现Java爬虫程序网站是大规模页面的集合，搜索引擎充当着内容的主要发现机制。为了能提供搜索，搜索引擎使用网络爬虫（又被称作网络机器人、网络蜘蛛等）不断抽取页面中链接及建立索引所需的相关内容，从而进行信息的搜集，随着搜索引擎的发展，越来越多的网络爬虫系统被开发用来搜集信息，爬虫的性能及所搜集到的信息质量直接影响着搜索引擎的最终检索效果。对于实际的爬虫而言，首先爬行线程需要解析已经下载的页面，抽取下一次爬行所必需的链接以及解析获取建立索引等需要的其他相关信息。其次，在实际的下载过程中，无法避免会遇到一些重复的信息，比如重复的URLs以及重复的网页内容。Java爬虫程序从指定主页开始，按照指定的深度抓取该站点域名下的网页并维护简单索引。参数：privatestaticintwebDepth=2;//爬虫深度。主页的深度为1，设置深度后超过该深度的网页不会抓取。privateintintThreadNum=10;//线程数。开启的线程数。抓取时也会在程序源文件目录下生成一个report.txt文件记录爬虫的运行情况，并在抓取结束后生成一个fileindex.txt文件维护网页文件索引。本程序用到了多线程(静态变量和同步)，泛型，文件操作，URL类和连接，Hashtable类关联数组，正则表达式及其相关类。运行时需使用命令行参数，第一个参数应使用http://开头的有效URL字符串作为爬虫的主页，第二个参数（可选）应输入可转换为int型的字符串（用Integer.parseInt(Strings)静态方法可以转换的字符串，如3作为爬虫深度，如果没有，则默认深度为2。不足之处是：只考虑了href=href="href="后加绝对url的这三种情况(由于url地址在网页源文件中情况比较复杂，有时处理也会出现错误)，还有相对url和window.open("的情况没有考虑。异常处理程序也只是简单处理。 4.2地址链接去重BloomFilter算法Bloom-Filter一般用于在大数据量的集合中判定某元素是否存在。例如邮件服务器中的垃圾邮件过滤器。在搜索引擎领域，Bloom-Filter最常用于网络蜘蛛(Spider)的URL过滤，网络蜘蛛通常有一个URL列表，保存着将要下载和已经下载的网页的URL，网络蜘蛛下载了一个网页，从网页中提取到新的URL后，需要判断该URL是否已经存在于列表中。此时，Bloom-Filter算法是最好的选择。Bloom-Filter算法的核心思想就是利用多个不同的Hash函数来解决“冲突”。计算某元素x是否在一个集合中，首先能想到的方法就是将所有的已知元素保存起来构成一个集合R，然后用元素x跟这些R中的元素一一比较来判断是否存在于集合R中；我们可以采用链表等数据结构来实现。但是，随着集合R中元素的增加，其占用的内存将越来越大。试想，如果有几千万个不同网页需要下载，所需的内存将足以占用掉整个进程的内存地址空间。即使用MD5，UUID这些方法将URL转成固定的短小的字符串，内存占用也是相当巨大的。4.3IndexFile文件分析算法索引链接文件是由XML形式存储的，这样就便于程序进行读取。在indexfile文件进行保存时，文件的格式如下：每一个链接的网页地址和网页链接存储在一个标签下面；下载到硬盘上的网页地址在下面，该网页的Url地址在标签下面。实现代码： 由于IndexFile文件格式很固定，且形式简单，所以在读取的时候就没用递归循环进行处理，而是采用了简单的双层循环，即可保证所有的节点都扫描到。IndexFile文件格式：实现fileindex文件扫描代码：1.加载所需要扫描的XML文件：2.获取该文件根目录下的所有节点，返回的为节点列表：3.循环扫描节点列表下的所有节点：4.如果判断一个节点为WEB节点，那么接下来的工作就是继续获取它的子节点： 5.设置两个布尔变量，当Filepath和Url都更新的时候再进行存储：6.扫描获取需要的节点，并保存在临时变量里：在Filepath和Url这对值的存储上，采用了ArrayList，每一个Object存储一对值。每一个Object实例化为一个String[]数组，String[]实例化的时候只开辟两个空间进行存储Filepath和Url。arrayFileindexStrings.add(newString[]{tempfilepathString,tempurlString});4.4Html文件标签字符去除每一个Html文件都包含有很多的标签，这些标签用于网页的排版，数据的控制等，对于网页信息是没有任何意义的。所以，需要把这些标签全部清除掉。程序中对标签的处理主要包括几个方面：script标签，style标签，html标签，特殊符号，过多的空格，以及一些制表符等。主要方法就是采用java中的正则表达式实现的。由于引擎只能对英文进行处理，所以空格处理方面必须是处理掉过多的空格，不是所有的空格，如果处理掉所有的空格，就会出现单词拼写混乱。StringregEx_blank="+";//定义多个空格的正则表达式 处理完Html文件之前，我们需要把下载下来的Html文件读到内存中。但是大多数情况下，html文件是非常庞大的txt文件，有的甚至会远远超过String类型的大小。这种情况下，我们需要设计一个专门针对Html过大的读取文件的类。每次读取设定一个参数，即读取的行数。既然一次不能把一个html文件全部读取出来，那么在标签处理这一块，也需要做相应的改动。读取文件一般都是一行一行的读，测试的时候我们可以设定一次读取十行再返回。但是问题在于下次再读的时候系统怎么知道上次读到哪里了。解决的办法就是把BufferedReader设定成全局变量，一次实例化之后，只要是在有效地范围内，它都可以保存记录读取的进度。每次只要调用读取函数，自然就是接着上一次的位置。把BufferedReader设定成全局变量：控制读取的行数，避免一次读取太多，系统处理不过来： 在文件处理这一块上，我们需要做一个循环，来把需要读取的数据分批处理掉。循环自然有终止，当返回出来的值为null，我们可以确定，文件已经读取完毕。这时，处理系统可以终止此次循环，去处理下一个Html文件。这样分批量的处理数据防止一次读入过多的数据结构溢出，很好的保护了程序正常的运行。4.4Trie的实现搜索引擎用trie树做基本的数据结构，相当于维护一个很大的单词表，每当查找到一个单词的时候就可查看与这个单词相关的URL。由于java中没有指针这一说，所以书本上传统的树形结构的定义在这里需要修改。需要克服的问题有几项：1.trie节点的数据结构；2.如何遍历整棵树；3.如何确定该单词已经查到了；4.url地址链表怎样关联起来。1.且不说C++中的指针在java中如何实现，单纯说建立一个节点所必须的有几项内容：1.该节点所代表的字母；2.它的子项集合。每个节点只代表一个字母，所以此处数据结构我们选用的是char类型。在子项集合的表示方面，在C#中首先想到的就是利用泛型List来实现各个object的链接。在java中，首选arrayList和LinkedList。从问题的本源开始考虑，建立的trie树大部分操作就是查询和插入，基本不涉及删除和随机访问（每次访问都是从根节点开始的）。所以再从arrayList和Linkedlist的属性来看，linkedList非常符合这种数据结构。2.节点建立完毕，整棵树的构建就是每个节点都保存着自己的数据值和子节点的地址链接。根节点不存任何数据，每个子节点最多也就有26个子节点。根据此次设计的特点，每次的查找必然要进行广度优先的策略。这就确定了节点数据结构也必然需要有一个方法来遍历自己的子节点并且根据给出的字母返回包含该字母的子节点，如果没有就创建新的子节点。3. 一棵trie建立起来之后，只是一些字母通过各种连接在一起。假如不加任何标示的东西，我们只可以确定，在每一次深度查找后，当该节点为叶节点时，所走过的路径为一个完整的单词。但是实际情况中，有些单词包含在其他单词的前缀中，例如am和ambulance，如果同时把这两个单词输入到trie中，可能电脑无法知道，当遍历到第三层的时候已经是一个单词了。这时候我们需要为每一个节点建立一个布尔标示位，表示遍历到该位置是否是一个单词。这样，根据标示位，电脑就可以知道此处是否产生一个单词。1.既然可以再节点中添加标示位来标示是否成词，那么也可以添加一个链表来表示与此单词相关的所有链接。根据trie在此系统中的应用，每一次的添加之前，可能这个单词已经存在这里了，我们所需要做的就是把地址链接挂在这个节点上，便于以后对该节点的查找。Node节点的结构如下：五测试方法与运行结果测试截图1此次文件的读取中，设定的读取行数为3行。引擎首先把文档进行处理，如图所示，处理之前为带有标签语言的字符串和处理之后的字符串。 下表为截屏的实际输出信息：-----------------------------一次文件读取开始，并处理-----------------------------处理之前的文本: