计算机专业-一维数据重复子串的快速搜索算法研究与实现.doc

《计算机专业-一维数据重复子串的快速搜索算法研究与实现.doc》由会员分享，可在线阅读，更多相关《计算机专业-一维数据重复子串的快速搜索算法研究与实现.doc（32页珍藏版）》请在沃文网上搜索。

1、 贵州大学本科毕业论文（设计） 第 29 页目录摘要IIAbstractIII第一章 绪论11.1 研究背景及意义11.2 音频篡改鉴定的发展历史11.3 研究现状2第二章 数字音频复制粘贴鉴定背景知识32.1 音频信号预处理32.1.1 音频信号32.1.2 音频信号数字化32.1.3 量化位数42.2 数字音频信号复制粘贴现象52.3 工具介绍62.3.1 VC+6.0介绍62.3.2 MFC类库介绍6第三章 算法原理83.1 金字塔模型83.2 金字塔数据结构93.3 金字塔创建103.4 金字塔的构建顺序113.5 金字塔的比较12第四章 算法实现154.1 程序流程154.2 金字塔

2、构建实现164.3 金字塔比较1实现174.4 金字塔比较2实现184.5 图形界面实现204.5.1 数据生成204.5.2 金字塔生成和比较22第五章 算法结果与分析255.1 算法的意义255.2 算法比较25第六章 结论与展望27参考文献28致 谢29一维数据重复子串的快速搜索算法研究与实现摘要一维数据重复子串的快速搜索算法研究与实现是指：在一维数据中可能存在有意无意的篡改现象，其中复制粘贴手段最为常见，需要快速简单地检索出重复子串。实际意义在于对数字音频数据的鉴定，主要方法用到金字塔算法，原理是构建金字塔后，塔顶元素具有代表下层元素的特点，从塔顶开始比较要比直接比较更节约时间，对庞大

3、音频数据的鉴定具有重要意义。本次研究内容在国内外研究还很少，很难找到相关的文献和书籍，我认为这具有很大研究意义。论文详细介绍了金字塔的构建原理，金字塔比较的详细过程，并进行了金字塔比较方法和原始比较方法的对比，得出的结论是金字塔比较方法能准确的查找重复子串，在数据极其庞大的时侯要比直接比较方法要快，实用性要好。关键字：金字塔，音频数据鉴定，复制粘贴One dimensional data fast substring search algorithm research and realizationAbstractOne dimensional data repetition substrin

4、g fast search algorithm research and realization means: in the one-dimensional data may exist naturally or half unconsciously tampering with the phenomenon, which means the most common copy and paste, need to quickly and easily retrieve repetition substring.Practical significance lies in the digital

5、 audio data identification, the main method used in Pyramid algorithm, principle is the construction of Pyramid, the lower elements representative characteristics of elements, from the top of the tower started to save time more than a direct comparison, the huge audio data identification is of great

6、 significance.The research contents in the domestic and foreign research is few, difficult to find relevant documents and books, I think this has great research significance.This paper introduces the principle of construction of Pyramid Pyramid, a detailed comparison of the process, and the Pyramid

7、the comparison method and the original comparison method contrast, concluded Pyramid comparative method can accurately find the repeated substrings, in data extremely large time than the direct comparison method to fast, practical.Key Word: pyramid，Digital audio appraisal，Copy paste第一章 绪论1.1 研究背景及意义

8、 随着信息时代的来临,越来越多的数字电子设备进入人们的日常生活,并改变着人们的生活习惯,音频领域也随之面临着革命性的变革。在专业领域,从早期的模拟开盘卡座及黑胶唱片到目前的CD,MD,从传统的模拟调音台到现在的数字音频工作站;在娱乐领域,mp3、mp4逐渐取代了模拟的walkman和录音机,DVD取代了传统的录像机种种迹象表明音频技术的数字化时代已经来临。在音频技术领域，人们可以越来越多地拾取音频信号，并利用音频编辑软件对其进行编辑和修改，这种有意或无意的篡改行为对音频数据本身的安全性产生了巨大的威胁。列如一些具有历史意义的录音、国家要求的重要录音、公安机关的重要取证录音.随着数字信息应用用于

9、司法取证的呼声越来越高，数字音频篡改技术逐渐成为国内外学术研究的热点。所以对数字音频数据的研究具有重要意义。计算机数据的存储是以0、1的形式存取的，那么数字音频就是首先将音频文件转化，接着再将这些电平信号转化成二进制数据保存，播放的时候就把这些数据转换为模拟的电平信号再送到喇叭播出。数据形式保存占用空间小、便于携带和传送，但在传递过程中容易会被恶意篡改，而复制粘贴是最简单也是最常见的音频篡改手段，复制粘贴合成后的音频一般靠听觉是不能分辨的，同一个人在同样环境下说同一个字似乎一样的，但实质上两个字的时域和频域都有所不同，加之目前国内外对这种现象的研究还比较少、正处于萌发阶段，因此对这种篡改方式的

10、检测有一定的难度。本次对一维数据重复子串的快速搜索算法的研究，实际意义在于对数字音频信息的鉴定，找出被篡改的地方并还原到自然音频。1.2 音频篡改鉴定的发展历史人们能够记录音频信号的技术已经存在一百多年，但将音频信号作为有效的司法取证是在近40年开始。1960年早期，美国联邦调查局就开始对音频录音内容进行了认证和改善语音清晰度的研究。1974年，“水门事件”的发生，得到很深刻教训，使得音频鉴定受到人们的广泛关注，并逐步发展成为司法科学的一个重要分支。1971年2月，为了防治白宫秘密事件被泄露，尼克松让助手在办公室安装了一套声控录音设备，正是这盘录音带成为最后揭发“水门丑闻”真相的有利证据。因为

11、检查发现这份录音带中存在长达18.5分钟的空白，甚至更多次的修改，这说明有人了为了掩盖事实真相，故意篡改部分录音信息。早期的音频鉴定主要是针对模拟音频信号的鉴定，截止现在已经取得了很好的效果，随着数字时代的到来，数字音频鉴定已经迫在眉睫。1.3 研究现状 音频信号篡改鉴定是二十世纪九十年代后兴起的一个新领域，国外已取得了一些研究成果，国内研究还比较少。在美国的Dartmouth大学以Farid教授为核心的研究团队，根据对篡改音频会引入非自然的高阶相关的性质，取得了较好的检测结果；罗马尼亚的取证工作者Grigoras，提出了通过分析电网频率的变化，实现篡改音频的鉴定；德国马哥德堡大学，Dittm

12、ann教授的研究团队提出了用于确定说话人所处环境的检测方法。从目前已有的文章来看，由于数字音频篡改鉴定的研究起步较晚，尤其是在国内的研究成果还很少，主要研究团体包括：上海交通大学，解放军信息工程大学，哈尔滨工业大学，中山大学以及大连理工大学等。 随着录音资料在司法取证中越来越重要，特别是数字音频方面，世界各国的法律机构相继开展数字音频鉴定的研究，并针对音频资料鉴定工作，逐步制定了法律程序和标准。第二章 数字音频复制粘贴鉴定背景知识2.1 音频信号预处理2.1.1 音频信号图2.1 音频信号如上图所示，音频信号是（Audio）带有语音、音乐和音效的有规律的声波频率、幅度变化信息载体。根据声波的特

13、征，音频信息可以分类为规则音频和不规则声音。其中规则音频又可以分为语音、音乐和音效。规则音频是一种连续变化的模拟信号，具有一定的韵律，可用一条连续的曲线来表示，称为声波。声音的三个要素是音调、响度和音色。声波或正弦波有三个重要参数：频率（符号为：）、幅度（符号为：A）和相位（符号为：），它们共同决定了音频信号的特征。2.1.2 音频信号数字化音频信号数字化是针对以前的模拟信号，即连续信号转变为离散的数字信号，以适应现代信息化社会的需求，只有这样才方便使用计算机来处理。由此我们需要对音频信号进行采样，是指将时间上连续的语音信号进行离散化，获取一个样本序列，于是，需要进行采样和量化。现在我们使用的

14、CD就采用了数字技术，不过它只是简单地把模拟信号加以数字化。为了得到更好效果的数字化信号，首先要对模拟信号进行采样。根据Ny quest采样定律，一般来说采样频率至少是被采样信号最高频率分量的两倍，这是因为采样后可还原的最高信号频率只有采样频率的一半。所以对于高质量的音频信号，其频率范围一般是在20Hz-40kHz之间，所以其采样频率必须在40kHz以上。在CD中采用了44.1kHz的采样频率。在对模拟信号采样以后，还必须对其幅度上加以分层。在CD中，其分层以后的幅度信号用16比特的二进制信号来表示，也就是把模拟的音频信号在幅度上分为65,536层。这样，它的动态范围就可以达到96分贝=20L

15、og65536(6分贝/比特)。这种直接模数(A/D)变换的方法也称为PCM编码。直接数字化的最大缺点是比特率非常高。达到44.1x16=705.6kbps，或即88.2kBbps。比特率高就意味着要求的存储容量很大。要记录1分钟的音乐，就需要5.292MB的存储容量。对于两路立体声，就需要10.584MB。而要记录几十分钟的音乐就需要几百兆的存储容量。 模拟信号转换成数字信号称为模/数转换，转换过程主要包括：采样（在时间轴上对信号数字化）； 量化（在幅度轴上对信号数字化）；编码(按一定格式记录采样和量化后的数字数据)。脉冲编码调制PCM（Pulse Code Modulation）是一种模数

16、转换的最基本编码方法，CD-DA就是采用的这种编码方式。如果对某一模拟信号进行采样，则采样后可还原的最高信号频率只有采样频率的一半，或者说只要采样频率高于输入信号最高频率的两倍，就能从采样信号系列重构原始信号。根据该采样理论可知：如果采样频率为40KHz，则记录的最高音频只有20KHz，这样的音质与原始声基本没有差别，正是我们所说的超级高保真音质（Super High Fidelity-HiFi）。 2.1.3 量化位数量化位是对模拟音频信号的幅度轴进行数字化，它决定了模拟信号数字化以后的动态范围。由于计算机按字节运算，一般的量化位数为8位和16位。量化位越高，信号的动态范围越大，数字音频信号

17、就越精确，但所需要的存贮空间也越大。声道数又有单声道和双声道之分。双声道又称为立体声，在硬件中要占两条线路，音质、音色好，但立体声数字化后所占空间比单声道多一倍。模/数转换图形比较如下图： 图2.2 模拟音频信号 图2.3 数字音频信号2.2 数字音频信号复制粘贴现象21世纪已是信息化的社会，以信息技术为主要标志的高新技术在整个经济中的比重不断增大，多媒体技术及产品促进了通信、智能、娱乐和计算机的融合、以及在国家执政和国防科技中所占比重越来越大，成为当今世界计算机产业发展的新领域，而多媒体技术最重要的技术之一：音频信息处理技术，将音频信息数字化存入存储器上，方便了我们保存、远距离传送和复制粘贴

18、，与此同时也会出现有意无意的篡改现象。在复制粘贴中最常见的是复制音频中某些关键字到同段音频中的其他位置，或是覆盖其他关键字以改变原始音频表达的意思。如图所示：图2.4 (a)原始语音 图2.5（b）复制粘贴篡改后的语音 在图中(a)语音表示：“你做的对，他做的不对”，(b)语音表示：“你做的不对，他做的不对”。(b)是将(a)中的“不”字复制到“对”字之前而得到的篡改语音。 如此看来音频数据的篡改可能会影响到原始语音的意思，如果是在军事通知方面的语音被篡改可能会照成两国进入紧急状态，司法取证中可能会让罪犯逍遥法外。例如在一段军事讲话中讲到：“我国坚持长期与美国友好合作”而在讲话中又讲到“发展中

19、国家现在还不如与发达国家经济发达”。在把讲话下达的过程中有人恶意把后面的“不”复制粘贴到前面某段话中则有：“我国坚持长期不与美国友好合作”，然后传遍全球，可能会引起两国友好发展甚至还会引发战争。这个“不”从同一人在相同环境下发出的，这种完全的复制粘贴，在语音中凭听觉是不可能辨别的，实际情况是没有两个字的发音数据完全一样的，这就是本次课题需要解决的问题，快速搜索一维数据中的重复子串。2.3 工具介绍 本次论文中设计的算法使用VC+6.0开发平台，图形界面使用MFC类库，本章节就对此进行简单介绍。2.3.1 VC+6.0介绍 VC+6.0 是一套完整的开发工具，用于生成 ASP.NET Web 应

20、用程序、桌面应用程序和移动应用程序。 Visual Basic、Visual C# 和 Visual C+ 都使用相同的集成开发环境 (IDE)，这样就能够进行工具共享，并能够轻松地创建混合语言解决方案。 另外，这些语言使用 .NET Framework 的功能，它提供了可简化 ASP Web 应用程序和 XML Web services 开发的关键技术。2.3.2 MFC类库介绍MFC,微软基础类(Microsoft Foundation Classes),实际上是微软提供,用于在C+环境下编写应用程序的一个框架和引擎,VC+是Win DOS下开发人员使用的专业C+ SDK(SDK,Stan

21、dard Soft Ware Develop Kit,专业软件开发平台),MFC就是挂在它之上的一个辅助软件开发包,MFC作为与VC+血肉相连的部分。MFC 应用程序的总体结构通常由开发人员从MFC类派生的几个类和一个CWinApp类对象（应用程序对象）组成。MFC 提供了MFC App Wizard 自动生成框架。Windows 应用程序中，MFC 的主包含文件为Afxwin.h。此外MFC的部分类为MFC/ATL 通用，可以在Win32 应用程序中单独包含并使用这些类。我们主要是用MFC来关联一个窗口的动作，用来进行界面开发。第三章 算法原理本论文是对一维数据重复字串搜索法的研究，采用金字

22、塔算法来实现快速搜索，下面具体介绍设计内容：由于音频数据数字化后数据都比较庞大，每个声音样本的位数也很大，结合实际情况，数字音频数据要连续出现一段重复现象才说明音频是重复的。所以我们在比较时先要选定长度范围，在数据比较小时就可以先确定比较长度，再把所有该长度的数据进行一一比较，这只适用数据较小时的比较。金字塔算法考虑的是数据非常庞大的情况，金字塔算法中也要先确定金字塔维数，然后按一定的规律构建金字塔，顶层数据代表下层数据性质，相当于把庞大数据的数据进行优化，可以只比较顶层数据，如果相同再往下比较，这样能减少比较数据来节约比较时间。本章对该算法原理进行了详细介绍。3.1 金字塔模型 我们需要构建

23、的金字塔模型形状类似于埃及金字塔，从下往上依次变小，就像是一个庞大的物体一步一步的精简，越在顶层就越精华，越具有代表性，其图如下：图3.1 金字塔模型图3.2 金字塔数据结构我们建立两个结构体，一个Array结构体，一个Pyramid结构体，Pyramid结构体中有一个Array *arrayOfArray 成员和一个pyramidSize成员，Array *arrayOfArray成员指针指向结构体Array，其中arrayOfarray0指向金子塔最上层，arrayOfarraypyramidSize-1就指向结构体的最下面一层。pyramidSize表示的是金字塔的维数，也就是金字塔最下

24、层的数据的个数（维数与最下层数据个数是相等的）。正如下图形所示：图3.2 金字塔生成Array结构体中有两个成员，一个int *array指针，一个是int arraySize，其中array指向的是arrayOfArray指向的层的元素，array0指向的是该层的第一个元素，arrayarraySize-1指向的是该层的最后一个元素。其中arraySize表示的是该层的元素的个数。正如下图所示： 图3.3 创建金字塔空间3.3 金字塔创建我们采用的金字塔构建是从下往上构建的，首先我们确定金字塔的维数，也就是最下层金字塔的元素的个数，然后，根据金字塔的维数给arrayOfArray分配空间，给

25、array分配空间。然后在从最下层将数据填入到空间里，然后再构建倒数第二层，其构建方法为：下层前一个元素减去后一个元素，相同规律依次往上构建直到最高层也就是arrayOfArray0。3.4 金字塔的构建顺序我们所做该程序的金字塔数据的来源全部来自一个叫input.txt文件。该文件的所有数据可以自由生成，在我们点击生成金字塔的同时程序内部开始从数据的第一个元素构建金字塔，用指针1、2指向所要比较的两个金字塔，指针1指向被比较金字塔，指针2指向比较金字塔，刚点击比较按钮的时候指针1不动，然后指针2向右移动，直到指针2移动到最后，这时指针1向后移动一位，表示被比较金字塔向右移动一位，再用被比较金

26、字塔与右边的每一个金字塔比较一次，如此循环直到所有数据中最右边数据比较完毕为止。如下所示： 例如有随机数据：92 44 19 23 34 84 72 69 31 2 61 10 20 16 15 39 65 17 96 32 设定指针1、指针2，假如金字塔维数为5则创建如下： 被比较金字塔不动，移动比较金字塔 依次移动比较金字塔直到移到最后一个 被比较金字塔向后移动一个 比较金字塔移动到最后被比较金字塔向后移一位，依次考虑完所有情况： 3.5 金字塔的比较比较方法1 在该程序中我们建立比较1的目的是为了和比较2形成一个对比，体现2在数据庞大的情况下的优越性，比较方法是：我们选用两个金字塔的最底

27、层的相应元素从左向右比较，如果有任意对应部位的两个元素不相等，那么就表示两个金字塔不等，只有在最底层所有元素都相等的情况下才相等。比较方法2 方法2采用从金字塔最顶端往最底下的比较办法，最开始arrayOfArray0指向的是金字塔中的最顶部第零层，然后arrayOfArray0.array0指向的是最顶层的第一个数据，然后对两个金字塔的相同该部位进行比较，如果相等，arrayOfArray0变成arrayOfArray1，再从array0向arrayarraySize进行第二层的比较，假如元素全部相等则继续往下层比较，在该比较过程中如果出现一个不相等的元素，则用break跳出循环，并返回一个

28、0值，表示金字塔不相等。若直到最底层比较完都没有不相等的元素，则返回一个1值，表示两个金字塔相等。 我们如此比较的理由在于金字塔上面的数据全部是由金字塔最底层数据采用同样规则计算所得，上层元素能代表下层元素，若金字塔上层出现数据元素不相等，则表示金字塔最底层肯定不相等，当然也有在金字塔上面部分全部相等，金字塔最下面不相等的情况，这是最极端的情况，在数据及其庞大并且无规律的情况下，该比较办法就有其得天独厚的优势，其比较速度也是相对较快的。其比较顺序如下图所示：首先：arrayOfArray0和arrayOfArray0.array0 指向金字塔的最顶层。 图3.4 金字塔比较顺序图a下一步：ar

29、rayOfArray0移动到下一层就会变成arrayOfArray1，arrayOfArray0.array0移动到下一层就会首先指向第一个元素变成arrayOfArray1.array0。 图3.5 金字塔比较顺序图b再下一步：arrayOfArray1不变，arrayOfArray1.array0指向第二层下一个元素变成arrayOfArray1.array1。 图3.6 金字塔比较顺序图c依次往下比直到有不相等就回跳出循环。第四章 算法实现 该算法的实现使用VC+6.0 开发平台，使用MFC实现界面，具体实现在经过第三章对算法原理的分析后，将实现部分分为以下几部分：4.1 程序流程在打开

30、该程序界面的时候，我们需要完成两个步骤，首先需要输入金字塔数据来源的文件名，也就是input.txt，然后要设置构成金字塔的维数，最后点击生成金字塔，程序就会自动生成“数据个数-维数+1”个金字塔，然后选择比较1或者2来比较金字塔是否相等，它会将结果输出，在每种比较方法比较完成后会自动跳出比较用时，并且在此时可以选择是否查看金字塔信息，其流程如下图所示： 图4.1 程序流程图4.2 金字塔构建实现 构建金字塔时首先为金字塔分配空间，我们采用动态分配的办法分配空间，再向分配的空间中填入数据，利用两个for语句填入数据，第一个for语句给金字塔最底层填入数据，第二个for语句由下往上填入数据，其非

31、最底层的金字塔的数据由其对应下层的左边数据减去右边数据所得，实现代码如下： void applyForPyramid(Pyramid *py,int pyramidSize) /给金字塔分配空间 int i;py-arrayOfArray = new ArraypyramidSize; /给指向层的指针分配空间py-pyramidSize = pyramidSize;for( i = 0 ; i pyramidSize ; i+ )/给指向每层内的数据指针分配空间 py-arrayOfArrayi.array = new inti+1 ;py-arrayOfArrayi.arraySize =

32、 i + 1 ; void createPyramidByArray(Pyramid *py,int array) /在分配空间中填入数据 int i,j;for( i = 0 ; i arrayOfArraypy-pyramidSize - 1.arraySize ; i + ) /给最底层填入数据 py-arrayOfArraypy-pyramidSize - 1.arrayi = arrayi ; for( i = py-pyramidSize - 2 ; i = 0 ; i - ) /从下往上，给金字塔每层填入数据for( j = 0 ; j arrayOfArrayi.arraySi

33、ze ; j+)py-arrayOfArrayi.arrayj=py-arrayOfArrayi+1.arrayj+1 - py-arrayOfArrayi+1.arrayj ; /金字塔构建成功4.3 金字塔比较1实现第一种比较方法相对简单，我们作为对比方法与比较2进行对比，其实现利用for语句让两个金字塔对底层的相应数据进行比较，如果相等则返回1，如果不相等则返回0，在比较1按钮的相应程序中调用下面程序，获得其返回值判断两金字塔是否相等，其具体代码如下： int ComparePyramid(Pyramid &pyOne,Pyramid &pyTwo) int i;if(pyOne.pyr

34、amidSize != pyTwo.pyramidSize )return -1;elsefor( i = 0 ; i pyOne.arrayOfArraypyOne.pyramidSize-1.arraySize ; i+ )if(pyOne.arrayOfArraypyOne.pyramidSize-1.arrayi!= pyTwo.arrayOfArraypyTwo.pyramidSize-1.arrayi )break; /判断是否相等的条件if( ( i pyOne.pyramidSize ) | ( i = pyOne.pyramidSize & pyOne.arrayOfArra

35、ypyOne.pyramidSize-1.arraypyOne.pyramidSize-1!= pyTwo.arrayOfArraypyTwo.pyramidSize-1.arraypyTwo.pyramidSize-1 ) )return 1;elsereturn 0;4.4 金字塔比较2实现 比较采用自顶向下比较，利用两个for语句控制流程，第一个for语句控制层数循环，第二个for语句控制每层内的数据的循环比较，一旦遇到不相等的数据，立即用break跳出循环，跳出内层循环后判断是否正常跳出，如果是正常跳出，则继续往下层比较，如果是利用break非正常跳出，则跳出该函数并返回0。在跳出外层

36、for循环之后，判断层数是否比较完毕，如果比较完毕则表示两金字塔相等，返回1，其流程图如下： 图4.2 比较方法2实现流程图 实现代码如下： int ComparePyrami(Pyramid &pyOne,Pyramid &pyTwo) int i;int j;if(pyOne.pyramidSize != pyTwo.pyramidSize ) /判断比较的两个金字塔维数是否相等 return -1; else for(i=0;ipyOne.pyramidSize;i+) /外层for循环控制的层数比较 for(j=0;jpyOne.arrayOfArrayi.arraySize;j+)

37、/内层for循环 if(pyOne.arrayOfArrayi.arrayj!=pyTwo.arrayOfArrayi.arrayj)break; /出现不相等，跳出内循环 if(jpyOne.arrayOfArrayi.arraySize-1)|(pyOne.arrayOfArrayi.arrayj!=pyTwo.arrayOfArrayi.arrayj)return 1; /判断是否正常跳出内循环，不是返回0 return 0; 4.5 图形界面实现4.5.1 数据生成 在运行算法时我们要做的第一步是随机数据的生成，界面如下：图4.3 随机数生成a 在数据获取时先确定获取数据个数，然后确定

38、随机数范围，本算法选择int型范围（-3276832767），最后选择输出文件名，点击获取。图4.4 随机数生成b 获取数据保存到input.txt中，如图：图4.5 随机数文件4.5.2 金字塔生成和比较 首先选择需要比较的数据文件，如input.txt图4.6 金字塔生成 数据读入后确定点金字塔维数，然后程序选文件中的数据以金字塔维数为底层数据构建金字塔，若文件中数据个数为N，金字塔维数选择20则生成金字塔数为：N-20+1 选择金字塔比较方法，本算法有两种比较方法,选择比较1则选择直接比较金字塔最底层数据，选择比较2则选择从金字塔最顶层依次向下层比较。并且在选择每种比较方法时会记录当前时

39、间，比较完成时也记录时间，最后计算出比较时间显示在比较结果下方。如下图：图4.7 金字塔比较结果在比较完成后，输出结果显示框会显示相等的金字塔和所选比较方法的比较时间，然后就可以选择要查看的金字塔信息，显示查看金字塔的最底层数据图4.8 金字塔信息显示最后可以看见有多少金字塔相等和确定比较结果的正确性。第五章 算法结果与分析 本章主要是对本次算法的意义和两种比较对比介绍。5.1 算法的意义 本次论文是对一维数据重复子串的快速搜索算法研究与实现。在当前数字化信息化时代，各种庞大的数据需要我们去处理，有时候需要各种各样的修改，复制粘贴是最为常见的行为，同时也伴随着恶意的篡改，但很多时候我们需要原始

40、的数据，此时就需要我们能寻找一种快速方法搜索重复现象。由于数字信息化时代的来临，网络时代的需要，数字技术日趋成熟，很多以前模拟信号都向数字信息转变。顺应计算的的处理原理，什么数字、文字、图像、语音，包括虚拟现实，及可视世界的各种信息等，实际上通过采样定理都可以用0和1来表示，这样数字化以后的0和1就是各种信息最基本、最简单的表示。由此看来，数字化信息的普及，我们的研究：“一维数据重复子串的快速搜索算法研究与实现”更加具有了实用性，所涉及的领域更为广泛，虽然本次把数字音频数据的重复子串的搜索作为研究对象，但是针对数字化的很多领域都有实用性。5.2 算法比较下面我们对本次算法所采用的两种比较方法进

41、行对比分析。我们对以下几种情况进行实验并进行数据统计：表5.1 比较时间对比由表中数据不难看出，当数据在500个时，在金字塔维数变化增大的同时比较1和比较2的比较时间变化不大，总体上比较2和比较1相比，比较1相对较快；当数据增大到1000个时，随金字塔维数增大的同时比较1和比较2的比较时间各自都有增大的趋势，但总体上来看比较1和比较2的比较时间区别不大；数据扩大到10000时，在金字塔维数增大的同时比较1和比较2的比较时间各自都有明显的增大，但是比较2的时间要小于比较1的时间。通过比较可得出结论，当数据相对较小时，我们只需采用比较1，直接比较数据会快于金字塔比较方法，而在数据较大时比较2也就是

42、金字塔自顶向下的比较要比直接比较节约时间，并且是数据越庞大，金字塔比较方法更具有优越性。第六章 结论与展望 本次毕业设计是我在大学以来难得的理论与实际相结合的机会，它不同于以前教学中的实验、课程设计等实践环节，是对我们大学四年所学知识的一个综合的训练及考核，是对所学知识的应用能力和大学所学理论知识对实践技能相结合的全面的检验。并对我们如何根据要做的课题对现有的资料进行理解和运用的能力的考核。真正做到了理论联系实际，把以前所学的知识综合贯通进行实践，并在实践中不断学习和自我完善。 通过这次一维数据重复子串快速搜索的研究，运用金字塔快速比较法的设计，让我摆脱了单纯的理论知识的学习方式，更加熟练了所

43、学知识的运用，增强了我的综合实践能力、发现问题和解决问题的能力，遇到问题懂得了时间计划和分步骤进行重要性，遇到棘手问题时应该向专业人员咨询和积极查找资料，同时在这几个月的的锻炼使我的意志和耐心也得到了很大程度的提升。在数字音频数据的鉴定研究过程中，由于相关知识功底不牢，遇到很多头疼的问题，但在老师和同学的帮助下，完成了论文预定的要求。在整个毕业设计过程中，使我在各个方面都有了很大的提高，特别是在理论和实践结合方面使我受益匪浅，使大学里学习的理论知识在根本上得到一次最完整的实践和提高，也为我即将面临的工作奠定了很好的基础。同时，这次毕业设计让我深深认识到自己各个方面的不足之处，本着提高动手能力以

44、及检测四年所学知识的目的，我严格要求自己，每一环节都认真对待，定期向知道老师报告进展情况和请教不懂的地方，得以完成任务。在以后的工作中，我们也必须进一步深化在实践中去丰富理论，完善知识结构。由于环境条件的影响，理论与实践还是有一定的差距，这也要求我们在实践中注意检验的积累。由于时间仓促，基本达到了本次论文需要，我认为金字塔算法还有很多需要改进的地方，首先算法本身还有待于优化，数据太庞大时所需内存太大，然后是在数据庞大时比较时间还不够快。但是数字化的普及，我认为此算法具有很大研究价值，我希望毕业后继续对金字塔算法深入研究，实现一个能得到大众满意，能在司法鉴定上排上用场的软件。参考文献1朱妹丽.三

45、种篡改情况下的音频鉴定方法研究D.大连：大连理工大学，2010.2李剑琴，杨晓宏，张雪梨，等. 数字音频素材的制作与运用M. 北京：国防工业出版社，2004.11803胡 航. 语音信号处理（修订版）M. 哈尔滨：哈尔滨工业大学出版社，2002. 130.4杨路明.C语言程序设计M.北京：北京邮电大学出版社，2005.20125.5张志明. C+语言与面向对象程序设计M. 重庆：重庆大学出版社，2006.87254.6王晓东.计算机算法设计与分析M.北京：电子工业出版社，2001.1088.7严蔚敏，吴伟民.数据结构M.北京：清华大学出版社，2007.36189.8李庆扬,王能超,易大义.数值分析M.北京：清华大学出版社，2008.56150.9靳明明.基于C_NET实现金字塔算法的研究A.河南：河南理工大学，2011.10钟玉琢.多媒体技术基础及应用M.北京：清华大学出版社，2006.5211.11于帆，赵妮，闫谦时.面向对象程序设计C+教程M.北京：科学出版社，2009.12Cast