《批量图片下载器设计论文.doc》由会员分享，可在线阅读，更多相关《批量图片下载器设计论文.doc（54页珍藏版）》请在三一办公上搜索。
1、Mass picture downloader图片批量下载器 摘 要批量下载图片可以方便用户从一个网站下载大量图片，节省用户时间，给用户带来便利。本文设计和实现一个基于正则表达式的图片批量下载器。本文首先在分析网上现有的图片下载器的工作原理及运行结果的基础之上，针对原有的爬虫搜索所有URL的下载方式所存在的不合理性与盲目性，基于正则表达式对URL进行判定和解析，设计了新的图片下载器的总体架构，且该架构主要包括爬虫模块和正则表达式自动产生模块两个部分。本文对爬虫模块的设计和实现原理进行了详细阐述。爬虫模块设计新的下载方式，要求用户指定的正则表达式为图片URL的提取标准，使得程序可以更快搜索并下载
2、下来图片。程序根据用户指定的正则表达式再结合爬虫程序来提取出一个网页中的地址，直到到达指定层数，最后执行下载。在分析URL的同时，程序亦建立网站层次树，以便用户查看那些未下载成功的图片在网站上的确切位置，从而可以选择重新下载。本文详细介绍了正则表达式自动模块的设计和实现，该模块通过用户输入的，从而得到一个比较高效的正则表达式，以供图片批量下载器使用。并且程序对一个正规的图片网站执行下载，运行结果表明，该程序能够快速准确的完成用户指定的下载任务，且使用较为方便，大大节省了用户的时间。论文最后对全文做出了总结，并对未来研究方向进行了展望。关键词：图片下载，正则表达式，爬虫程序，动态规划算法，规范
3、，JAVAMass picture downloaderAbstractMass picture downloader is a software that can save users time by downloading thousands of pictures from a website automatically.This thesis is about the design and the realization of the mass picture downloader.A new architecture of the software has been built，wh
4、ich includes two parts called crawler and regular expression generator.Basing on the analysis of the working mechanism and the results of existent mass picture downloaders，This thesis describes a new way that is different from traditional blindly search on URLs using a Crawler.The new way is based o
5、n the analysis to the URLs by using regular expression.This thesis describes the design and the realization of the crawler in detail.A new way has been designed for the crawler part.In the new way，a regular expresssion appointed by the user is used to extract the URLs from a webpage，which，indeed，mak
6、e the search and downloading much faster.The program extracts a URL from a webpage according to the regular expression，then gets the content of the webpage indexed by the extracted URL，and then analyzes the content of the webpage by using the regular expresssion next layer，until reaches the designat
7、ed layer count.During the analysis of the URLs，a websiteTree is being built，in order to do the users a favor when they want to see the address of the downloading-unfinished pictures.This thesis also describes the design and the realization of the regular expression generator in detail. The regular e
8、xpression generator provides regular expression that generated through the URLs input by the users to the crawler to make it work.Then the program is put into practice-download pictures from a large picture website，the result shows that the program works well.At last，this thesis makes a summary abou
9、t the program，and gives an expectation about the future.Key Words: picture downloader，regular expression，crawler，dynamic programming，URL specification，Java目 录图片批量下载器II摘 要IIAbstractIII1 绪论11.1 课题研究背景及意义11.1.1 研究背景11.1.2 研究意义21.2 国内研究现状21.3 研究的主要内容31.4 论文组织结构31.5 本章小结42 图片批量下载器的总体架构设计52.1 总体设计52.2 关键模
10、块简介52.2.1 爬虫模块52.2.2 正则表达式自动产生器模块62.3 本章小结63 爬虫程序的整体设计和实现及相关技术要点73.1 爬虫程序的整体设计和实现73.2 相关技术要点133.2.1 检查重复URL133.2.2 将相对地址转化为绝对地址143.2.3 将一张图片下载下来的函数163.3 本章小结174 正则表达式自动产生器184.1 基于动态规划的最优字符串比对算法184.1.1 字符串比对定义184.1.2 字符串比对问题的动态规划解法184.2 正则表达式自动产生器总体设计和实现224.2.1 假设和规定224.2.2 自动产生正则表达式的问题分析和基本思路224.2.3
11、 正则表达式自动产生器设计和实现254.3 程序测试结果324.4 本章小结345 结论与展望355.1 工作总结355.2 工作展望35致谢36参考文献37附录A381 绪论1.1 课题研究背景及意义1.1.1 研究背景目前，随着多媒体技术的发展，对信息的表现形式逐步趋向多元化，其中数字图片是信息传递的主要形式之一。对于喜欢收藏各种精美数字图片的人而言，下载少量图片可以通过浏览器简单的右键保存到本地硬盘，但是如果要下载一个网站上成千上万张图片，手工一张一张保存，已经是不可能的事，更何况目前大多数图片网站，一张图片要点击平均3-4次才能得到真正想要的图片。于是针对该种状况，设计一款图片批量下载
12、工具，方便用户批量下载网站的图片，节省用户时间。目前，互联网上图片网站都具有如下特征：1.网站排版很有规则，网站的层次结构鲜明且固定，比如：用户从进入一个网站到看到他所想要的图片，所要点击的次数都是固定的，这就成为可以采用正则表达式层来进行URL匹配的前提条件。2.目前绝大多数网站，都没有采用反盗链技术，这就使得爬虫程序能够运行成为可能。3.绝大多数网站，如果从用户每一次深层次的点击角度来看待，那么处于同一层的多个URL具有相似性，这就使正则表达式的精确匹配成为可能。4.几乎所有网站，表示下一页的方式都是固定不变的，比如：一个网站的下一页都用一个按钮，或者一个文字超链接等等，这就使递归的分析下
13、一页成为可能。5.网页上链接重复的情况，目前看来，全部发生在同一层里面，也就是说，仅有同一层才可能出现重复URL的情况。在上述背景下，论文将对如何设计爬虫程序和如何正确的提取出正则表达式进行研究，详细阐述可行方案和实现机制，旨在探求能够高效方便的批量下载图片的方法。1.1.2 研究意义图片在目前的信息传输过程中起到重要的作用，丰富多彩的图片能够更加直观，更加有效的表达出信息，本课题的研究意义就在于能够帮助用户高效的，批量的从大型图片网站上搜集各种精美图片，整个搜集过程要实现自动化后台操作，从而使用户摆脱重复而繁重的右击保存操作，节约用户宝贵的时间。1.2 国内研究现状目前网上流传的图片下载器种
14、类繁多，技术也比较成熟，基本上都是基于传统爬虫技术，比较好的例如：globalFetch图片下载器，picture downloader 等等。picture downloader是一款功能齐全的图片下载软件，可以新建下载任务，输入给定的可用URL，图片大小，关联网址级数及网址URL所具有的特征文件夹名和特征后缀名，就可以开始下载任务，根据用户指定的关联网址级数，该工具从当前网页搜索指定深度的网页。该软件还可以与百度搜索引擎相关联，将用户提交的图片搜索信息以表单形式提交给百度，然后在其内置浏览器中显示结果。globalFetch也有类似的功能。但是美中也有不足之处，具体情况如下：1. 目前我所
15、见到的几款图片下载器，基本上都是基于类似于搜索引擎一样，搜索所有图片链接，然后将所有图片统统下载下来，然而，有可能这么多图片并不是用户所想要的，用户的需求可能是，用户只对网站上的一个系列或其中的某个人物的图片感兴趣，所以我想在针对某一主题进行特定下载方面进行改进。2. 目前我所见到的几款图片下载器，虽然设定了限制条件，但还是有按钮图片等被批量下载下来，存在错误下载格式的问题，所以我想在针对某一主题进行特定下载方面进行对此改进。3. 目前我所见到的几款图片下载器，都是基于分析网页上url地址，根据特征来提取网址，但是，目前非常多的网站采用反盗链功能，让分析网页链接这一方法完全失效，如果图片下载器
16、遇到这种网站，根本不会下载任何东西。4.也有一些软件自带批量下载功能，比如迅雷中的下载全部链接功能，以及QQ浏览器中的提取图片功能，但以上都只能单纯的提取当前网页的图片，无法对网站进行深层次的搜索。参考文献1指出：文件伪装是目前采用的最多的反盗链技术，一般会结合服务器端的动态脚本(JSP)。实际上，用户请求的文件地址，只是一个经过伪装的脚本文件，这个脚本文件会对用户的请求作出认证，一般会检查Session，Cookie或 HTTP_REFERER作为判断是否为盗链的依据。而真实的文件隐藏在用户不能够访问的地方，只有用户通过验证后才会返回该用户。目前有许多网站采用反盗链技术，这一技术的采用，使得
17、一般的爬虫程序无法正常运行，由于反盗链使得爬虫无法获得可用链接，就需要采用其它方法。1.3 研究的主要内容本文研究的主要内容包括爬虫程序的构建和如何根据用户输入的URL来提取出准确的正则表达式两大内容。最后，把程序应用于一个大型图片网站中，实现批量下载，从而验证模型和算法是合理的、有效的。1.4 论文组织结构全文共分为四章，其中：第一章 是绪论部分，首先简单概括了课题的来源和背景，然后论述了国内研究现状，最后根据来源和背景提出了程序研究的主要问题和内容，并阐述了程序的意义以及论文的组织结构。第二章 介绍了图片下载器的总体架构设计。第三章主要论述了程序主体爬虫程序的总体设计方案。首先讨论了程序需
18、求并根据程序需求分析提出了程序总体解决方案。随后，详细描述了在爬虫程序执行过程中要解决的关键问题的设计和实现，包含如何防止重复下载，如何通过正则表达式提取出URL，如何构建网站层次树等等。第四章主要论述了程序附属正则表达式产生器的总体设计方案。首先描述了正则表达式产生器需求分析提出了程序总体解决方案。随后，详细描述了提取正则表达式过程中要解决的关键问题的设计和实现。第四章最后针对实际图片网站给出了程序测试结果，以验证程序的正确性。第五章总结全文，并展望了未来发展方向。1.5 本章小结本章详细描述了本课题的所处的背景，由于这些背景因素的存在，使得本课题的实现成为可能。本章接着提出了本课题的研究意
19、义，分析了国内的研究现状和所取得的研究成果，并列举出相关示例加以阐述，最后提出了本文的主要研究内容及论文的结构。2 图片批量下载器的总体架构设计2.1 总体设计图片批量下载器主要由网站爬虫程序和正则表达式自动产生程序组成，正则表达式产生程序负责从用户统计输入的URL中提取出这些URL的特征正则表达式，然后加入到爬虫程序的正则表达式队列中，作为提取某一层后台页面的URL的标尺。爬虫程序就是根据正则表达式队列中的URL正则表达式对一个网站进行一层一层的剥离，直到正则表达式队列指定的层数。图片批量下载器的总体架构设计如图2-1所示。图2-1 图片批量下载器的总体架构设计2.2 关键模块简介2.2.1
20、 爬虫模块爬虫程序是本课题的主体程序，该模块工作时首先接受用户输入的一个入口页，然后再接受用户通过正则表达式自动产生器得到的一层URL的正则表达式，用户输入完毕之后，爬虫程序开始根据用户输入的每一层的正则表达式提取出下一层URL，接着在下一层，这样循环，直到指定层数。2.2.2 正则表达式自动产生器模块该模块是专门针对上述爬虫程序开发的模块，此模块的功能主要是根据用户统计输入的URL进行特征提取，最后得到一个较为准确的URL正则表达式，然后再提供给爬虫程序使用。2.3 本章小结本章通过系统总体协作图简要介绍了图片下载器的整体架构，以及两个关键模块的主要功能。3 爬虫程序的整体设计和实现及相关技
21、术要点爬虫程序是本课题的主体程序，本章详细阐述了如何根据1.1.1 的背景条件来有效设计爬虫程序，并详细描述了其实现。其他关键技术要点也给出了响应的设计与实现。3.1 爬虫程序的整体设计和实现传统爬虫从一个或若干初始网页的URL开始，获得初始网页上的URL，在抓取网页的过程中，不断从当前页面上抽取新的URL放入队列，直到满足系统的一定停止条件。本程序的爬虫基于传统爬虫的设计理念，但是由于本程序的需求的具有特殊性，即：用户登陆一个图片网站，大多数情况下，用户不可能想要下载该网站上的所有图片，更多的情况是下载其中的一类，那么，如果采用传统的爬虫，就会严重影响搜索速度，而且下载下来的并不一定是用户所
22、想要的。基于这个情况，可行的解决办法是：程序运行之前，用户首先输入一系列的正则表达式，每一个正则表达式能够代表该层要提取的URL的特征，用户进入入口页之后， 根据当前层的正则表达式提取出URL，然后再以提取出的URL为基础，应用第二层正则表达式，这样，直到正则表达式层数结束，也就提取出了最终的图片URL。但是，基本上所有的图片网站的某一个主题都不止一页，有可能向后有100页，那么在运行上述爬虫的时候，程序中间还要检测当前分析页是否存在下一页的链接，如果存在，那么还要将下一页当作同一级的网页来处理，直到一个网页中没有下一页的地址，或者该地址指向自身。在爬虫程序递归分析网页的同时，可以同步构造出网
23、页的层次结构，即：在分析当前URL指示的网页里面的内容的时候，如果发现了子URL，那么就将该子URL加入到ArrayList WebSiteTree里面，并将该子URL在WebSiteTree里的位置加入到当前URL的子节点位置数组里面，然后将该子URL的父节点的位置设为当前URL在WebSiteTree里的位置，如此循环反复，就完成了网站层次结构的构建。由上述，从而得到如下算法：关键变量，类和方法的声明：Class TreeNodeint father;/此变量保存此节点的父节点在数组中的位置int selfRealPos;/此变量保存此节点本身在数组中的位置URlValue=0;/所保存的
24、URL字符串里面的字符相加得到的整数值String address;/该节点保存的URL字符串ArrayList childrenPos;/该节点的所有孩子节点在数组中的位置Class RepeatedTreeNodeTreeNode follower;/后来的重复节点TreeNode victim;/原来的节点ArrayList WebSiteTree;/网站层次树ArrayList layerAddressContainer;/保存一层的全部URL节点ArrayList regularExpression;/正则表达式层ArrayList RepeatedInfo;/存储重复节点Array
25、ListLinskArray;/临时变量，保存下一层所有URLint layerCount;/记录现在处于第几层Stack path;/此栈记录了深度爬虫算法里面的路径函数recursionAnalyzer()用来根据给定的URL和正则表达式层来递归得出下一层所有的URL，并返回ArrayList类型参数算法1：根据一个输入的URL得到该URL对应的网页上下一层所有URL，即函数 ArrayListrecursionAnalyzer(入口页节点，表示下一页的字符串，layerCount，regularExpression，RepeatedInfo，WebSiteTree)读入入口页指定的URL
26、的网页内容;if(有下一页)同时检测是否存在重复URL，如果下一页与前面的URL没有重复说明下一页有效;根据layerCount所指定的正则表达式层里的正则表达式找有没有匹配的URL;if(有匹配的URL)同时检测是否存在重复URL;if(没有重复)将该节点加入到LinskArray里面;将该节点加入到WebSiteTree里面，构建网页目录层次;else 根据栈的内容将重复URL的层次地址打印出来，并打印出与哪个 URL重复，并打印出那个URL的层次地址;如果有下一页，递归调用recursionAnalyzer(下一页的地址节点，表示下一页的字符串，layerCount，regularExp
27、ression，RepeatedInfo，WebSiteTree，RepeatedInfo)对下一页所指的网页进行分析;Return LinskArray;算法2：广度爬虫算法输入：入口页输出：所有图片的URL简要算法逻辑：首先初始化各变量;while(layerCountregularExpression.size()for(int i=0;ilayerAddressContainer.size();i+)ArrayListtemp=a.recursionAnalyzer(参数略);/该函数返回分析第一层的结果，也就是第二层的所有URL打印出每个URL的层次地址if(RepeatedInfo
28、.size()0)/意味着有重复情况处理重复的情况;将temp里面的内容在存储到layerAddressContainer里面，供下次循环使用;layerCount+;算法3：深度爬虫算法输入：入口页输出：下载图片简要算法逻辑：首先初始化各变量;public void CORE_DEPTH_FIRST_FETCHING(入口页地址，正则表达式层，layerCount等参数)if(layerCount=regularExpression.size()/所有层都已分析完毕，递归出口对地址进行预处理;根据栈的内容打印出层次地址;开始下载;以上两算法：深度优先爬虫算法和广度优先爬虫算法，是本程序实现下
29、载的两种方式。广度优先爬虫算法在搜索的时候以广延性为首要目标，它的好处显而易见，在分析一个网站的时候，可以让用户实时的了解每个网页的情况，比如，该网页上有多少个用户所关心的链接URL地址等等，用户还可以清晰的看到整个网站的组织结构。但是，广度优先爬虫算法也存在严重的缺点，就是占据存储容量很大，这也是构建网站结构的代价。深度优先爬虫算法在搜索的时候以纵深搜索为首要目标，这种方式无需保存整个网站层次结构，每次递归运行，仅仅需要保存纵深路径上的节点个数。但是这种方式，在与用户交互性方面不如广度优先爬虫算法，用户在下载过程中不能全面了解网站的结构。下面是对两种搜索方式的占据空间数值比较：前提条件：一个
30、入口页，上面有S个超链接，并有a页，每一个链接点进去之后，出来的网页上面仍有S个超链接，也是有a页，这样以此类推。用户需要点击n次才可以看到最终的图片。广度优先爬虫算法由于要保存前一层的超链接以用来分析下一层的超链接，所以要要同时保存两层的URL，又由于要确保分析下一层URL时不会加入重复URL，平衡二叉树需要保存下一层的所有URL，所以，采用广度优先爬虫算法分析第k层时，内存在任意时刻最多要保存个URL记录。深度优先爬虫算法以纵深搜索为首要目标，所以每次只保存一条URL记录，直到到达最底层。由于广度优先爬虫算法是以层为目标，所以里面的重复检查时，AVL树里面只要保存一层的内容，等到一层分析完
31、毕，就可以将AVL树清空，以便进行下一次的重复检查，与之不同的是深度优先爬虫算法无所谓一层是否结束，不到最后，任何层都无法结束。所以深度优先爬虫算法AVL树要保存所有的URL节点，不存在清空的情况。所以，采用深度优先爬虫算法，分析的时候需要保存n条URL记录，正常情况下，深度优先爬虫算法AVL树占用空间在分析最后一个URL的时候达到最大值，也就是AVL树保存了所有的URL，这时内存要保存*a个URL记录，远小于广度优先时内存占用最大值 。以上分析了爬虫程序的核心算法，爬虫程序核心是作为公有类PicFetchManners里面的公有方法BREADTH_FIRST_FETCHING()和DEPTH
32、_FIRST_FETCHING()两个函数实现。两种算法具体实现核心代码参见附录A。3.2 相关技术要点 3.1节详细阐述了本课题的主体程序-爬虫程序的整体设计和实现，并探讨了两种爬虫方式的优缺点，本程序对两种爬虫方式均给予了实现，在实现过程中，遇到了很多技术难点，这一节，将在上一节的基础之上，详细介绍重要技术点的设计思路和实现，并会给出相应伪代码。3.2.1 检查重复URL首先进行关键变量声明：ArrayList RepeatedInfo /保存所有的产生重复的U RL节点class RepeatedTreeNodeTreeNode follower;/后来的与前面某个节点重复的节点Tree
33、Node victim;/受害者节点一个网页上难免存在许多相同的URL指向相同的内容，如果不进行重复判断，爬虫程序将重复分析许多URL，重复下载许多图片，浪费了网络带宽，增加了程序运行时间。本程序采用了AVL树来对每个URL节点进行检查，由于AVL树的平衡性，使得查找的速度非常迅速。设计：对于一个URL字符串，通过将其里面的字符全部相加，得到一个整数值URlValue，URlValue就作为AVL树每个节点的数值，此外，AVL树的每个节点还有一个链表URLTreeNodeArray，用来保存URlValue相同的所有节点。如果一个新的节点到达，那么首先用AVL树二分查找，如果没有找到，则new
34、一个新的节点并插入到AVL树里面;如果找到，接着遍历URLTreeNodeArray，如果URLTreeNodeArray里不存在，就将该节点插入到URLTreeNodeArray，如果URLTreeNodeArray里已经存在，说明这个URL已经产生重复，将此URL加入到RepeatedInfo里面，添加节点的形式为：new RepeatedTreeNode(重复的节点，在AVL树中的已经存在的节点);如此构造的目的是，如果产生重复，程序要立即打印出与哪个节点重复，该节点的层次地址，而这些信息都存储在AVL树中的已经存在的节点里面。向AVL树插入节点在整体上耗费 O(log n) 时间，搜索
35、AVL树亦消耗 O(log n) 时间，然后对每个节点中URLTreeNodeArray的搜索消耗O(k)，所以上述设计总的时间代价最多O(log(n+k)。检查重复URL作为公有类BST类里面的BSTInsert()函数实现。3.2.2 将相对地址转化为绝对地址 制作网站时，为了网页的通用性，普遍采用了相对地址来指示网页的位置，爬虫程序无法使用单纯的相对地址，必须将相对地址转换为绝对地址。为了使正则表达式在提取URL的时候有更准确的界限，用户输入的正则表达式往往是以href=或者src=这样开头，这样就不会造成地址界限确定不准的情况。算法4：相对地址转绝对地址算法输入：任何地址输出：绝对地址
36、简要算法逻辑：关键变量声明：URL fullpathContainstem;/这个URL指示了包含相对地址的那个网页String tem;/表示任何类型的地址String TRANSFORM_A_RELATIVEPATH_TO_ABSOLUTEPATH(String tem，URL fullpathContainstem)首先判断给地址是否是 href= 或者是 src=的类型地址如果是，就将里面真正的地址完全提取出来，且不含引号;/下面就是判断是否是绝对路径;if(不是绝对路径，那就是相对路径)/相对路径的情况如果开头是以 /，那么表示这个路径是根目录，直接在前面加上fullpathCont
37、ainstem主机名和协议名即可，并赋给tem;如果包含././等，则表示取fullpathContainstem表示的URL的上面几级目录，然后再加上tem的文件名并赋给tem;如果不以/或者是./开头，而是ima/tt.htm这种，或直接tt.htm，那么就表示这样的目录和这样的文件在fullpathContainstem相同的工作目录中，只要将fullpathContainstem的文件部分替换成ima/tt.htm，或tt.htm即可，其余部分不变，并赋给tem;return tem;/这时的tem，已经变成了可以直接使用的绝对路径了将相对地址转化为绝对地址的功能是作为公有类recur
38、sionSearchTheWebPage的TRANSFORM_A_RELATIVEPATH_TO_ABSOLUTEPATH()方法实现。这样，就可以将相对地址转化为绝对地址，具体实现参见附录A。3.2.3 将一张图片下载下来的函数本程序最基本的方法是下载一张图片的方法，首先要对图片的URL进行分解，得到图片的文件名，然后检测该文件名在当前文件夹中是否已经存在，一般来说，在已经避免重复下载的情况下，能够下载下来相同文件名的图片的情况非常少见，如果文件名相同，图片内容也可能不同，比如许多网站的文件名仅仅以数字命名:1.jpg，2.jpg等等，这样就容易造成上述情况，所以，在下载前，如果检测到该文件
39、名已经存在，那么本程序采用的方法是，取当前系统时间作为字符串加到该文件名后面，这样，就避免了以后再出现重复的情况。下面开始下载，基本方法是：URL url = new URL(urlName);URLConnection connection = url.openConnection();connection.connect();BufferedImage image=ImageIO.read(url);该过程要抛出3种异常：IOException 无法从网络读取数据异常;IllegalArgumentException 用户输入的URL或者本地路径名格式非法异常;自定义SizeExcepti
40、on 图片分辨率异常，由于图片分辨率过小产生的异常;下载单图片函数作为公有类ExplicitDownloadManners里的downloadSingleImg()方法实现。3.3 本章小结本章首先介绍了爬虫程序的整体设计思路，并详细描述了两种爬虫深度爬虫和广度爬虫的伪代码实现，然后比较了两种方式的优缺点。从第二小节开始，介绍了爬虫算法实现中遇到的主要技术点，本文对每个技术点的设计和实现都进行了精要的描述。4 正则表达式自动产生器4.1 基于动态规划的最优字符串比对算法4.1.1 字符串比对定义为字符集上的两个序列。A与B的序列比对是一个在中2*k字符矩阵M(k=m，n)，使得M中没有列完全有
41、短横线组成，并且对M中的第一行和第二行的全部短横线进行移动而得到的结果序列分别与A和B相同。例如：如果A=abcd和B=cbd，他们的一个可能的比对是：a b c - d- - c b d同样这样的两个序列的另一个可能的比对是：a b c dc b - d4.1.2 字符串比对问题的动态规划解法 定义得分函数设两个字符，令表示x与y的比对得分，如果x，y相同，那么=2;如果x与y不相同但是都不是 - ，=1;如果x或者y是 - ，那么=-1。 问题的数学模型A和B 的2序列比对问题描述为找到具有最多得分的两序列最优比对。采用递归公式可将此问题公式化。令整数表示与之间的最优比对对应的最高得分，其
42、中1im，1jn。那么，可以表示如下：表示两个空字符串相比较，得分为0; 表示字符串与一个为空的B进行比对，那么比对只有如下情况： - - - - 。 表示如果和比对可以产生最高得分，那么必须在和之间要产生最优比对。表示如果 和 - 比对可以产生最高得分，那么必须在和之间要产生最优比对。 表示如果和 - 比对可以产生最高的得分，那么必须在和之间产生一个最优比对。有了上面的声明，下面得到字符串比对问题解法的递归式： 算法5：寻找字符串比对算法输入：两个URL字符串输出：两者的最优比对简要算法逻辑：根据上面递归式，于是得到了两字符串比对解法的伪代码:得分函数:Int f(char a，char b
43、)Int score;If(a=- | b =-)score=-1;else if(a=b)score=2;else score=1;return score;比对函数：HighestScore(x，y)m-lengthx;n-lengthy;for i-1 to mdo ci，0 -0for j-0 to ndo c0，j -0for i-1 to mfor j=max)Max= Aij-1+f(-，yj);Bij=;If(Ai-1j+f(xi，-)=max)Max= Ai-1j+f(xi，-);Bij=; return c and b;下面是通过回溯数组b来将X和Y的最优比对打印出来打印X的比对：TraceBackPrint(b，X，i，j)If i=0 or j=0 Then returnIf bi，j= then TraceBackPrint(b，X，i-1，j-1) Print xiElse if bi，j= Then TraceBackPrint(b，X，i-1，j)Else TraceBackPrint(b，X，i，j-1) Print -同理可得：打印Y 的比对TraceBa
