【文章內(nèi)容簡介】 的復(fù)制粘貼，在語音中憑聽覺是不可能辨別的，實(shí)際情況是沒有兩個(gè)字的發(fā)音數(shù)據(jù)完全一樣的，這就是本次課題需要解決的問題，快速搜索一維數(shù)據(jù)中的重復(fù)子串。 工具介紹 本次論文中設(shè)計(jì)的算法使用VC++，圖形界面使用MFC類庫，本章節(jié)就對(duì)此進(jìn)行簡單介紹。 VC++ VC++ 是一套完整的開發(fā)工具，用于生成 Web 應(yīng)用程序、桌面應(yīng)用程序和移動(dòng)應(yīng)用程序。 Visual Basic、Visual C 和 Visual C++ 都使用相同的集成開發(fā)環(huán)境 (IDE)，這樣就能夠進(jìn)行工具共享，并能夠輕松地創(chuàng)建混合語言解決方案。 另外，這些語言使用 .NET Framework 的功能，它提供了可簡化 ASP Web 應(yīng)用程序和 XML Web services 開發(fā)的關(guān)鍵技術(shù)。 MFC類庫介紹MFC,微軟基礎(chǔ)類(Microsoft Foundation Classes),實(shí)際上是微軟提供,用于在C++環(huán)境下編寫應(yīng)用程序的一個(gè)框架和引擎,VC++是Win DOS下開發(fā)人員使用的專業(yè)C++ SDK(SDK,Standard Soft Ware Develop Kit,專業(yè)軟件開發(fā)平臺(tái)),MFC就是掛在它之上的一個(gè)輔助軟件開發(fā)包,MFC作為與VC++血肉相連的部分。MFC 應(yīng)用程序的總體結(jié)構(gòu)通常由開發(fā)人員從MFC類派生的幾個(gè)類和一個(gè)CWinApp類對(duì)象（應(yīng)用程序?qū)ο螅┙M成。MFC 提供了MFC App Wizard 自動(dòng)生成框架。Windows 應(yīng)用程序中，MFC 的主包含文件為。此外MFC的部分類為MFC/ATL 通用，可以在Win32 應(yīng)用程序中單獨(dú)包含并使用這些類。我們主要是用MFC來關(guān)聯(lián)一個(gè)窗口的動(dòng)作，用來進(jìn)行界面開發(fā)。第三章 算法原理本論文是對(duì)一維數(shù)據(jù)重復(fù)字串搜索法的研究，采用金字塔算法來實(shí)現(xiàn)快速搜索，下面具體介紹設(shè)計(jì)內(nèi)容：由于音頻數(shù)據(jù)數(shù)字化后數(shù)據(jù)都比較龐大，每個(gè)聲音樣本的位數(shù)也很大，結(jié)合實(shí)際情況，數(shù)字音頻數(shù)據(jù)要連續(xù)出現(xiàn)一段重復(fù)現(xiàn)象才說明音頻是重復(fù)的。所以我們在比較時(shí)先要選定長度范圍，在數(shù)據(jù)比較小時(shí)就可以先確定比較長度，再把所有該長度的數(shù)據(jù)進(jìn)行一一比較，這只適用數(shù)據(jù)較小時(shí)的比較。金字塔算法考慮的是數(shù)據(jù)非常龐大的情況，金字塔算法中也要先確定金字塔維數(shù)，然后按一定的規(guī)律構(gòu)建金字塔，頂層數(shù)據(jù)代表下層數(shù)據(jù)性質(zhì)，相當(dāng)于把龐大數(shù)據(jù)的數(shù)據(jù)進(jìn)行優(yōu)化，可以只比較頂層數(shù)據(jù)，如果相同再往下比較，這樣能減少比較數(shù)據(jù)來節(jié)約比較時(shí)間。本章對(duì)該算法原理進(jìn)行了詳細(xì)介紹。 金字塔模型 我們需要構(gòu)建的金字塔模型形狀類似于埃及金字塔，從下往上依次變小，就像是一個(gè)龐大的物體一步一步的精簡，越在頂層就越精華，越具有代表性，其圖如下： 金字塔模型圖 金字塔數(shù)據(jù)結(jié)構(gòu)我們建立兩個(gè)結(jié)構(gòu)體，一個(gè)Array結(jié)構(gòu)體，一個(gè)Pyramid結(jié)構(gòu)體，Pyramid結(jié)構(gòu)體中有一個(gè)Array *arrayOfArray 成員和一個(gè)pyramidSize成員，Array *arrayOfArray成員指針指向結(jié)構(gòu)體Array，其中arrayOfarray[0]指向金子塔最上層，arrayOfarray[pyramidSize1]就指向結(jié)構(gòu)體的最下面一層。pyramidSize表示的是金字塔的維數(shù)，也就是金字塔最下層的數(shù)據(jù)的個(gè)數(shù)（維數(shù)與最下層數(shù)據(jù)個(gè)數(shù)是相等的）。正如下圖形所示： 金字塔生成Array結(jié)構(gòu)體中有兩個(gè)成員，一個(gè)int *array指針，一個(gè)是int arraySize，其中array指向的是arrayOfArray指向的層的元素，array[0]指向的是該層的第一個(gè)元素，array[arraySize1]指向的是該層的最后一個(gè)元素。其中arraySize表示的是該層的元素的個(gè)數(shù)。正如下圖所示： 創(chuàng)建金字塔空間 金字塔創(chuàng)建我們采用的金字塔構(gòu)建是從下往上構(gòu)建的，首先我們確定金字塔的維數(shù)，也就是最下層金字塔的元素的個(gè)數(shù)，然后，根據(jù)金字塔的維數(shù)給arrayOfArray分配空間，給array分配空間。然后在從最下層將數(shù)據(jù)填入到空間里，然后再構(gòu)建倒數(shù)第二層，其構(gòu)建方法為：下層前一個(gè)元素減去后一個(gè)元素，相同規(guī)律依次往上構(gòu)建直到最高層也就是arrayOfArray[0]。 金字塔的構(gòu)建順序。該文件的所有數(shù)據(jù)可以自由生成，在我們點(diǎn)擊生成金字塔的同時(shí)程序內(nèi)部開始從數(shù)據(jù)的第一個(gè)元素構(gòu)建金字塔，用指針2指向所要比較的兩個(gè)金字塔，指針1指向被比較金字塔，指針2指向比較金字塔，剛點(diǎn)擊比較按鈕的時(shí)候指針1不動(dòng)，然后指針2向右移動(dòng)，直到指針2移動(dòng)到最后，這時(shí)指針1向后移動(dòng)一位，表示被比較金字塔向右移動(dòng)一位，再用被比較金字塔與右邊的每一個(gè)金字塔比較一次，如此循環(huán)直到所有數(shù)據(jù)中最右邊數(shù)據(jù)比較完畢為止。如下所示： 例如有隨機(jī)數(shù)據(jù)：92 44 19 23 34 84 72 69 31 2 61 10 20 16 15 39 65 17 96 32 設(shè)定指針指針2，假如金字塔維數(shù)為5則創(chuàng)建如下： 被比較金字塔不動(dòng)，移動(dòng)比較金字塔 依次移動(dòng)比較金字塔直到移到最后一個(gè) 被比較金字塔向后移動(dòng)一個(gè) 比較金字塔移動(dòng)到最后被比較金字塔向后移一位，依次考慮完所有情況： 金字塔的比較比較方法1 在該程序中我們建立比較1的目的是為了和比較2形成一個(gè)對(duì)比，體現(xiàn)2在數(shù)據(jù)龐大的情況下的優(yōu)越性，比較方法是：我們選用兩個(gè)金字塔的最底層的相應(yīng)元素從左向右比較，如果有任意對(duì)應(yīng)部位的兩個(gè)元素不相等，那么就表示兩個(gè)金字塔不等，只有在最底層所有元素都相等的情況下才相等。比較方法2 方法2采用從金字塔最頂端往最底下的比較辦法，最開始arrayOfArray[0]指向的是金字塔中的最頂部第零層，然后arrayOfArray[0].array[0]指向的是最頂層的第一個(gè)數(shù)據(jù)，然后對(duì)兩個(gè)金字塔的相同該部位進(jìn)行比較，如果相等，arrayOfArray[0]變成arrayOfArray[1]，再從array[0]向array[arraySize]進(jìn)行第二層的比較，假如元素全部相等則繼續(xù)往下層比較，在該比較過程中如果出現(xiàn)一個(gè)不相等的元素，則用break跳出循環(huán)，并返回一個(gè)0值，表示金字塔不相等。若直到最底層比較完都沒有不相等的元素，則返回一個(gè)1值，表示兩個(gè)金字塔相等。 我們?nèi)绱吮容^的理由在于金字塔上面的數(shù)據(jù)全部是由金字塔最底層數(shù)據(jù)采用同樣規(guī)則計(jì)算所得，上層元素能代表下層元素，若金字塔上層出現(xiàn)數(shù)據(jù)元素不相等，則表示金字塔最底層肯定不相等，當(dāng)然也有在金字塔上面部分全部相等，金字塔最下面不相等的情況，這是最極端的情況，在數(shù)據(jù)及其龐大并且無規(guī)律的情況下，該比較辦法就有其得天獨(dú)厚的優(yōu)勢，其比較速度也是相對(duì)較快的。其比較順序如下圖所示：首先：arrayOfArray[0]和arrayOfArray[0].array[0] 指向金字塔的最頂層。