相似度技术在资料信息化中的应用研究

相似度技术在资料信息化中的应用研究

张德龙，杨鹏

（内蒙古气象信息中心内蒙古呼和浩特010051）

摘要：讨论了目前常用的相似度度量技术：属性计数技术和结构度量技术，通过字符串匹配算法对得到的标记字符串作比较，并根据比较结果给出它们之间匹配程度的数值表示，以此作为文件相似度的度量值。该值越大说明文件越相似，资料信息化过程中存在拷贝的可能性也越高。验证结果表明，该实验系统能检测到资料录入数据中大部分的相似内容。

关键词：气象资料；相似度；度量；算法中图分类号：TP391

文献标识码：A

文章编号：1674－6236（2013）03-0020-04

Techniques of similarities applied research in date information

ZHANG De -long ，YANG Peng

（Inner Mongolia Meteorological Information Center ，Hohhot 010051，China ）

Abstract:This thesis discusses the present techniques of measuring the similarities:Structure metrics and Attribute counting.This research is mainly about how to measure the similarities among file.It compares two strings ，and calculates the similarity values through the matching results.This value will show how similar two files are.The higher the values are ，the more similar the files are.It is more possible that the data is copied.Empirical results indicate that the system can find most similar segments between the two data sets.

Key words:meteorological data ；similarity ；measurement ；algorithm

收稿日期：2012-09-10

稿件编号：201209060

作者简介：张德龙（1978—），男，内蒙古乌兰察布人，硕士，电子工程师。研究方向：气象资料分析与应用。

我国有器测以来，积累了大量的观测气象资料，是气候研究、决策规划的珍贵资源。其大部分以纸质形式记录，大量观测资料均存储在各类报表或自记纸上。为了对历史资料的进一步应用，需要把报表上的资料录入成电子数据。然而在录入过程中可能存在同一台站不同年代，或不同台站间数据相互拷贝的情况。在这种情况下，如果能通过计算机自动、快速地在大量录入文件中检查哪些部分是相同的，就时间而言可完成人工几乎不可能完成的任务，然后在选出的文件中再进行人工参与，大大的减少了审核人员的工作量。

目前，内容相似度度量的技术主要有：属性计数技术和结构度量技术。由于属性计数技术没有考虑文件的结构，只是统计了文件中一些属性信息，所以随着文件复制种类的不断提高（如从不同文件中各选一些组合成文件），其度量结果的准确性就会下降。1976年，Halstead [1]首先提出了用属性计数的方法检测文件的拷贝问题，1977年，Ottenstein [2]使用

Halstead 的方法设计了最早的自动文件拷贝检测系统。结构

度量技术考虑了文件的结构特征，度量结果比较真实地反映了文件之间的相似性。Plague [3]，Sim [4]，YAP3[5]等拷贝检测系统无一例外的都使用了结构度量技术。由于国外大部分成功的拷贝检查系统都采用了结构度量技术，所以本研究结构度量技术。首先对文件作预处理，去掉对相似度度量结果没有影响的部分，接着扫描经预处理后的文件，并对其作简单的语法分析，将其转换为表示文件结构的标记字符串，再通过特定的匹配算法对得到的字符串作比较，并给出它们之间匹配程度的数值表示，以此作为文件数据相似度的度量值。该值越大说明文件数据越相似，存在拷贝的可能性也越高。

1相关算法及技术介绍

文件相似度度量技术中，结构度量技术是通过比较文件

的结构来度量文件数据间的相似度。结构度量技术中，首先将源文件转换为标记串序列，然后通过字符串匹配算法比较得到的标记串，并根据匹配结果给出文件数据相似度的数值表示。这里用到的字符串匹配算法称为结构比较算法，本研究也将采用该算法来匹配表示文件结构的标记串。在讨论

Running Karp -Rabin Greedy String Tiling 算法。算法中用到的

几个基本概念：1）文本串（也称主串），指要在其中查找子字符串的较长的字符串，用T 表示；2）模式串（也称模式），指需要在文本串T 中查找的字符串，用P 表示。通常，文本串T 是较长的字符串，而模式串P 是较短的字符串。

1.1Running Karp-Rabin Greedy String Tiling

1.1.1

算法描述和伪代码

Running Karp -Rabin Greedy String Tiling 算法是基于非

常有名的字符串匹配算法Karp -Rabin [6]。受基于映射（散列）

电子设计工程

Electronic Design Engineering

第21卷

Vol.21

第3期No.32013年2月Feb.2013

－20－