《维数据重复子串的快速搜索算法研究与实现》由会员分享，可在线阅读，更多相关《维数据重复子串的快速搜索算法研究与实现（28页珍藏版）》请在金锄头文库上搜索。
1、本科毕业论文设计论文设计题目：一维数据重复子串的快速搜索算法研究与实现目 录摘要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
2、程序流程154.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 repetitio
4、n substring 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 t
5、he digital 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 i
6、s of great 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 th
7、e Pyramid 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 / 第一章 绪
8、论1.1 研究背景及意义 随着信息时代的来临,越来越多的数字电子设备进入人们的日常生活,并改变着人们的生活习惯,音频领域也随之面临着革命性的变革。在专业领域,从早期的模拟开盘卡座及黑胶唱片到目前的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,提出了通过分析电网频率的变化,实现篡改音频的鉴定；德国马哥德堡大学,D
12、ittmann教授的研究团队提出了用于确定说话人所处环境的检测方法。从目前已有的文章来看,由于数字音频篡改鉴定的研究起步较晚,尤其是在国的研究成果还很少,主要研究团体包括：交通大学,解放军信息工程大学,工业大学,大学以及理工大学等。 随着录音资料在司法取证中越来越重要,特别是数字音频方面,世界各国的法律机构相继开展数字音频鉴定的研究,并针对音频资料鉴定工作,逐步制定了法律程序和标准。第二章数字音频复制粘贴鉴定背景知识2.1 音频信号预处理2.1.1 音频信号图2.1 音频信号如上图所示,音频信号是Audio带有语音、音乐和音效的有规律的声波频率、幅度变化信息载体。根据声波的特征,音频信息可以分
13、类为规则音频和不规则声音。其中规则音频又可以分为语音、音乐和音效。规则音频是一种连续变化的模拟信号,具有一定的韵律,可用一条连续的曲线来表示,称为声波。声音的三个要素是音调、响度和音色。声波或正弦波有三个重要参数：频率符号为：、幅度符号为：A和相位符号为：,它们共同决定了音频信号的特征。2.1.2 音频信号数字化音频信号数字化是针对以前的模拟信号,即连续信号转变为离散的数字信号,以适应现代信息化社会的需求,只有这样才方便使用计算机来处理。由此我们需要对音频信号进行采样,是指将时间上连续的语音信号进行离散化,获取一个样本序列,于是,需要进行采样和量化。现在我们使用的CD就采用了数字技术,不过它只
14、是简单地把模拟信号加以数字化。为了得到更好效果的数字化信号,首先要对模拟信号进行采样。根据Ny quest采样定律,一般来说采样频率至少是被采样信号最高频率分量的两倍,这是因为采样后可还原的最高信号频率只有采样频率的一半。所以对于高质量的音频信号,其频率围一般是在20Hz-40kHz之间,所以其采样频率必须在40kHz以上。在CD中采用了44.1kHz的采样频率。在对模拟信号采样以后,还必须对其幅度上加以分层。在CD中,其分层以后的幅度信号用16比特的二进制信号来表示,也就是把模拟的音频信号在幅度上分为65,536层。这样,它的动态围就可以达到96分贝=20Log65536。这种直接模数变换的
15、方法也称为PCM编码。直接数字化的最大缺点是比特率非常高。达到44.1x16=705.6kbps,或即88.2kBbps。比特率高就意味着要求的存储容量很大。要记录1分钟的音乐,就需要5.292MB的存储容量。对于两路立体声,就需要10.584MB。而要记录几十分钟的音乐就需要几百兆的存储容量。 模拟信号转换成数字信号称为模/数转换,转换过程主要包括：采样在时间轴上对信号数字化； 量化在幅度轴上对信号数字化；编码。脉冲编码调制PCMPulse Code Modulation是一种模数转换的最基本编码方法,CD-DA就是采用的这种编码方式。如果对某一模拟信号进行采样,则采样后可还原的最高信号频率只有采样频率的一半,或者说只要采样频率高于输入信号最高频率的两倍,就能从采样信号系列重构原始信号。根据该采样理论可知：如果采样频率为40KHz,则记录的最高音频只有20KHz,这样的音质与原始声基本没有差别,正是我们所说的超级高保真音质Super High Fidelity-HiFi。 2.1.3 量化位数量化位是对模拟音频信号的幅度轴进行数字化,它决定了模拟信号数字化以后的动态围。由于计算机按字节运算,一般的量化位数为8位和16位。量化位越高,信号的动态围越大,数字音频信号就越精
