关于重复词提取的两种算法分析.pdfVIP

第29卷第2期计算机应用Vo.l29No.2

2009年2月JournalofComputerpplicationsFeb.2009

:1001-9081(2009)02-0403-03

蒋华,殷波

(,541004)

(jianghua0773@126.com;raulyinbo@163.com)

:针对重复网页的去重问题,对两种重复词句提取算法进行了系统分析比较。STC算法时间成本上具有优

秀性能,重复序列的倒排索引方法空间复杂度方面更胜一筹。结合STC算法对重复序列方法进行了改进,而面向主

题转载的重复网页,先抽取重复串,然后将重复串作索引进行STC算法的重复抽取。实验结果表明,改进算法保持了

原有空间特性的基础上极大地提高了时间效率。

:重复词句;重复序列;后缀树

:TP391.1:

Newalgorithmbasedonrepeatsequencedeletion

JINGHu,aYINBo

(DepartmentofComputerandControl,GuilinUniversityofElectronicTechnology,GuilinGuangxi541004,China)

bstract:miingatthecurrentde-duplicationalgorithm,stworepeatedsequences(RS)extractingalgorithmswere

comparedandanalyzed.SinceSTChasfavorableperformanceinconsideringtimecostandtheinvertedindexmethodissuperior

intermsofspatialcomplexity,STCwasusedtoimproveRSalgorithm.Expermientresultsshowthatthismethodcanfindsmiilar

Webpagesefficiently.Thisalgorithmcanreachahighprecisioninmono-languagedeletionofduplicatedWebpage,sandthis

algorithmcanalsoreachamaxmiumprecisionwhenitisappliedtodeletionofduplicatedwebpages.

Keywords:repeatedsequences;repeatedsegments;suffixtree

“candrivetruckssafely.Mendrivecarssafely.Mencan

0引言drivetrucks.”

,,,()

,,,,,m=3。1,

。。

stoplist,,,

。,,

。

,

[3]

。

。,

,,