两种重复提取算法的研究比较

在利用计算机处理文本信息时,为了能发现大文本信息中的重复词句,本文介绍两种用来发现重复词句的算法——基于后缀树的方法和基于倒排索引的方法。第一种ST算法使用树型数据结构,每个节点表示一个字并且根节点为空。第二种算法应用倒排索引,以及哈希表实现方法（HT）。对同一样本运行仿真后,在时间和空间复杂度上对实验结果进行比较。得出结论,尽管ST算法在考虑到时间成本时要更优,但在空间复杂度方面倒排索引方法更胜一筹。     

DNA序列中基于后继数组索引的LPR查找算法

DNA序列中的重复片段在人类基因研究中有着非常重要的生物意义,因此,查找给定DNA序列中的重复片段是生物序列分析领域中的一个重要课题.基于重复片段的模式提出了新的重复片段定义LPR(largest pattern repetition)和模式单元的概念.对于长度为n的DNA序列,其中的LPR的数量是O(n)数量级的,但提供了与个数可多达n2/4的tandem repeat相同的重复片段信息.基于模式单元设计了可用于重复片段查找的全新索引--后继数组.后继数组有效地降低了索引空间,很好地突破了重复片段查找中的索引空间瓶颈.在后继数组上,通过模式单元可发现构成LPR的全部原子模式,并通过判断相同模式是否在原序列中连续出现完成LPR的查找.理论分析和实验结果均表明,设计的LPR查找算法的时间和空间复杂度均为O(n).     

一种基于逆序匹配重复模式的主题信息提取方法

网页中的信息主要以重复的HTML结构进行组织并形成一致的展现形式,主要研究具备复杂重复模式的网页主题信息块识别,提出一种改进的基于逆序匹配重复模式的算法。该算法依据HTML标签结构和class属性改进DOM树,重构页面的向量空间模型,逆序匹配重复结构模式并完成对主题信息的提取。实验结果表明,该方法能准确识别复杂页面结构中主题重复模式,有效避免非主题重复模式的干扰,有较好的召回率和准确率。     

基于模式识别算法的网页重复信息抽取仿真

当前的网页重复信息抽取方法缺少信息分类步骤,导致传统方法存在抽取全面率低、重复信息比例高以及整体性能差的问题。于是提出基于模式识别算法的网页重复信息抽取方法。利用类间平衡因子和词频获取网页信息的互信息特征。在关联规则的基础上根据网页置信度向量化互信息特征,完成网页信息特征的提取。利用模式识别中的支持向量机对网页信息分类,优化惩罚函数,建立软间隔支持向量机分类器。计算不同类别网页信息的结构相似度和语义相似度,结合上述计算结果获得网页信息相似性,完成网页重复信息的抽取。仿真结果表明,所提方法的抽取全面率高、重复信息比例低,且整体应用性能好,实验结果表明所提方法具有理想的应用效果。     

MD5算法在消除重复网页算法中的应用

Internet用户通过常用搜索引擎获取Web信息时,往往得到了大量的重复网页信息,从而导致搜索效率不高.本文利用MD5算法成熟及可移植性好的特点,提出了一种基于MD5的消除重复网页的算法,实验证明该算法能有效的去除重复网页,时间和空间的复杂度不高,具有较强的实用价值.     

MD5算法在消除重复网页算法中的应用

Internet用户通过常用搜索引擎获取Web信息时,往往得到了大量的重复网页信息,从而导致搜索效率不高。本文利用MD5算法成熟及可移植性好的特点,提出了一种基于MD5的消除重复网页的算法,实验证明该算法能有效的去除重复网页,时间和空间的复杂度不高,具有较强的实用价值。     

网页近似重复检测算法研究

搜索引擎的爬行程序在日益庞大的互联网中采集到的网页包含有大量的重复或近似重复网页,这不仅降低了检索效率,增加了存储空间,还降低了最终用户的体验。本文针对现有的网页近似重复检测技术进行了比较,并重点讨论了改进的模糊哈希算法对网页内容进行近似重复检测。     

一种处理B^＋树重复键值的方法

当前B^＋树索引结构常采用“溢出页”处理重复出现的键值,易于实现,但存在严重的空间浪费。该文通过改进索引结构的定义,使B^＋树能够显式支持重复键值,并给出相应算法。实验证明,采用该方法的B^＋树能有效减少索引文件的大小,使B^＋树满足更多数据库索引的需求。     

基于QSA数组计算序列中所有NE重复模式的算法

序列中重复模式的识别与提取算法在数据挖掘、模式识别、数据压缩、生物信息学等领域中具有广泛的实际应用。提出一种全新的基于QSA数组计算所有带有约束条件的NE重复模式的算法RPT。算法设计中充分考虑了NE重复模式的特征,以建立特征和重复模式检测结果之间的统计联系;算法中的约束条件包括最小周期pmin和最大间距gmax,其可用于筛选符合条件的NE重复模式,并可按照递增序输出所有NE重复模式的出现位置。与已有的基于后缀索引的算法相比,此算法的空间效率得到了提高。在分类属性数据样本集上进行的实验表明,算法RPT对生物序列尤其是DNA序列以及维吾尔语Web文本中NE重复模式的识别与提取都很有效。     

基于HTML标记和长句提取的网页去重算法

提出了一种高效的算法来去除互联网上的重复网页。该算法利用HTML标记过滤网页中的干扰信息,然后提取出能表征一张网页的长句作为网页的特征。通过分析两张网页所共享长句的数量,来判断两张网页是否重复。该算法还利用红黑树对网页的长句进行索引,从而把网页去重过程转换为一个搜索长句的过程,减小了算法的时间复杂度。实验结果表明该算法能够高效,准确地去除重复的网页。     

改进的基于布尔模型的网页查重算法

提出一种基于布尔模型的网页查重算法,利用布尔模型寻找适当的特征,建立索引以减少网页文档之间的比较次数.实验验证了这种算法的性能,并取得了较好的效果.     

基于傅立叶变换的网页去重算法

去除重复网页可以提高搜索引擎的搜索精度,减少数据存储空间。目前文本去重算法以关键词去重、语义指纹去重为主,用上述算法进行网页去重时容易发生误判。通过对字符关系矩阵进行K L展开,将每个字符映射成为一个数值,然后对这个数值序列做离散傅立叶变换,得到每个网页的傅立叶系数向量,通过比较傅立叶系数向量差异实现对网页的相似度判断。实验结果表明该方法可对网页实现较好的去重。     

基于字集特征向量的网页消重改进算法

基于MD5算法计算数字指纹的网页消重算法简单而高效,在网页消重领域应用比较广泛。但是由于MD5算法是一种严格的信息加密算法,在文章内容变动很少的情况下得出的指纹结果完全不同,导致基于这种算法的网页消重技术召回率不是很高。提出了两种基于字集特征向量的网页消重改进算法,把文章内容映射到字集空间中去,计算字集空间距离来判断文章是否相似。提出的算法具有良好的泛化能力,段落中存在的调整语序和增删改个别字不会影响到对相似段落的识别,大大提高了网页消重算法的召回率。实验结果表明,算法的时间复杂度为[O(n)],空间复杂度为[O(1)],适合应用于大规模网页消重。     

STEM: a suffix tree-based method for web data records extraction

To automatically extract data records from Web pages, the data record extraction algorithm is required to be robust and efficient. However, most of existing algorithms are not robust enough to cope with rich information or noisy data. In this paper, we propose a novel suffix tree-based extraction method (STEM) for this challenging task. First, we extract a sequence of identifiers from the tag paths of Web pages. Then, a suffix tree is built on top of this sequence and four refining filters are proposed to screen out data regions that might not contain data records. To evaluate model performance, we define an evaluation metric called pattern similarity and perform rigorous experiments on five real data sets. The promising experimental results have demonstrated that the proposed STEM is superior to the state-of-the-art algorithms like MDR, TPC and CTVS with respect to precision, recall and pattern similarity. Moreover, the time complexity of STEM is linear to the total number of HTML tags contained in Web pages, which indicates the potential applicability of STEM in a wide range of Web-scale data record extraction applications.     

基于缩进轮廓的HTML文档重复模式挖掘方法

HTML文档重复模式挖掘是找到Web页面编码模版的关键,是Web数据自动抽取和Web内容挖掘的基础。传统的基于字符串匹配和树匹配的重复模式挖掘方法虽然具有较高的精确度,但是其性能对于处理海量的Web页面来说仍然是一个挑战。为了提高性能,提出了一种基于缩进轮廓的HTML文档重复模式挖掘方法。该方法首先定义了缩进轮廓模型,是一种由HTML文档每行代码的缩进值及行首的HTML标签构成的数据结构,它是HTML文档的一种简化抽象;该方法通过检测缩进轮廓中的串联重复波段,间接地挖掘HTML文档中的重复模式。实验表明,该方法不但具有较高的精确度,而且较明显地提升了性能。     

Effectively finding relevant Web pages from linkage information

This paper presents two hyperlink analysis-based algorithms to find relevant pages for a given Web page (URL). The first algorithm comes from the extended cocitation analysis of the Web pages. It is intuitive and easy to implement. The second one takes advantage of linear algebra theories to reveal deeper relationships among the Web pages and to identify relevant pages more precisely and effectively. The experimental results show the feasibility and effectiveness of the algorithms. These algorithms could be used for various Web applications, such as enhancing Web search. The ideas and techniques in this work would be helpful to other Web-related research.     

EFFICIENT METHODOLOGIES TO HANDLE HANGING PAGES USING VIRTUAL NODE

In this article we first explain the knowledge extraction (KE) process from the World Wide Web (WWW) using search engines. Then we explore the PageRank algorithm of Google search engine (a well-known link-based search engine) with its hidden Markov analysis. We also explore one of the problems of link-based ranking algorithms called hanging pages or dangling pages (pages without any forward links). The presence of these pages affects the ranking of Web pages. Some of the hanging pages may contain important information that cannot be neglected by the search engine during ranking. We propose methodologies to handle the hanging pages and compare the methodologies. We also introduce the TrustRank algorithm (an algorithm to handle the spamming problems in link-based search engines) and include it in our proposed methods so that our methods can combat Web spam. We implemented the PageRank algorithm and TrustRank algorithm and modified those algorithms to implement our proposed methodologies.     

基于网页正文结构和特征串的相似网页去重算法

为了减少重复网页对用户的干扰,提高去重效率,提出一种新的大规模网页去重算法。首先利用预定义网页标签值建立网页正文结构树,实现了层次计算指纹相似度;其次,提取网页中高频标点字符所在句子中的首尾汉字作为特征码;最后,利用Bloom Filter算法对获取的特征指纹进行网页相似度判别。实验表明,该算法将召回率提高到了90%以上,时间复杂度降低到了O(n)。     

基于本体实现对网页文本的自动主题分类

提出了一种实现对中文网页进行自动分类的平衡差值法，它利用本体中主题概念的层次结构和主题词、特征项的各种语义关系，降低了分类算法的复杂性和计算量。试验表明，该方法可以获得85％以上的网页分类准确率。     

基于超链接的镜像页面比较策略研究

Web中存在大量的镜像页面,这会严重影响分析的结果,并且占据大量的空间和资源,严重影响了计算的效率,因此,如何去除这些镜像页面是社区发现技术中的一个重要的问题。对基于纯链接的镜像页面去除方法进行了分析,并证明了只需出度邻近的页面进行比较,并提出了页面邻近区域的比较方法,按照Web页面的分布理论,设计了比较策略的方法。实验结果证明,大大减少了比较的次数,提高了效率。