維數(shù)據(jù)重復(fù)子串的快速搜索算法研究與實(shí)現(xiàn)畢業(yè)論文-文庫吧資料
2025-07-04 21:51本頁面
【正文】 ，其流程如下圖所示： 程序流程圖 金字塔構(gòu)建實(shí)現(xiàn) 構(gòu)建金字塔時(shí)首先為金字塔分配空間，我們采用動(dòng)態(tài)分配的辦法分配空間，再向分配的空間中填入數(shù)據(jù)，利用兩個(gè)for語句填入數(shù)據(jù)，第一個(gè)for語句給金字塔最底層填入數(shù)據(jù)，第二個(gè)for語句由下往上填入數(shù)據(jù)，其非最底層的金字塔的數(shù)據(jù)由其對(duì)應(yīng)下層的左邊數(shù)據(jù)減去右邊數(shù)據(jù)所得，實(shí)現(xiàn)代碼如下： void applyForPyramid(Pyramid *py,int pyramidSize) //給金字塔分配空間 { int i。 金字塔比較順序圖b再下一步：arrayOfArray[1]不變，arrayOfArray[1].array[0]指向第二層下一個(gè)元素變成arrayOfArray[1].array[1]。其比較順序如下圖所示：首先：arrayOfArray[0]和arrayOfArray[0].array[0] 指向金字塔的最頂層。若直到最底層比較完都沒有不相等的元素，則返回一個(gè)1值，表示兩個(gè)金字塔相等。如下所示： 例如有隨機(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è)金字塔不等，只有在最底層所有元素都相等的情況下才相等。 金字塔的構(gòu)建順序。正如下圖所示： 創(chuàng)建金字塔空間 金字塔創(chuàng)建我們采用的金字塔構(gòu)建是從下往上構(gòu)建的，首先我們確定金字塔的維數(shù)，也就是最下層金字塔的元素的個(gè)數(shù)，然后，根據(jù)金字塔的維數(shù)給arrayOfArray分配空間，給array分配空間。正如下圖形所示： 金字塔生成Array結(jié)構(gòu)體中有兩個(gè)成員，一個(gè)int *array指針，一個(gè)是int arraySize，其中array指向的是arrayOfArray指向的層的元素，array[0]指向的是該層的第一個(gè)元素，array[arraySize1]指向的是該層的最后一個(gè)元素。 金字塔模型 我們需要構(gòu)建的金字塔模型形狀類似于埃及金字塔，從下往上依次變小，就像是一個(gè)龐大的物體一步一步的精簡(jiǎn)，越在頂層就越精華，越具有代表性，其圖如下： 金字塔模型圖 金字塔數(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)體的最下面一層。金字塔算法考慮的是數(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ì)一維數(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ù)的。此外MFC的部分類為MFC/ATL 通用，可以在Win32 應(yīng)用程序中單獨(dú)包含并使用這些類。MFC 提供了MFC App Wizard 自動(dòng)生成框架。 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++血肉相連的部分。 Visual Basic、Visual C 和 Visual C++ 都使用相同的集成開發(fā)環(huán)境 (IDE)，這樣就能夠進(jìn)行工具共享，并能夠輕松地創(chuàng)建混合語言解決方案。 工具介紹 本次論文中設(shè)計(jì)的算法使用VC++，圖形界面使用MFC類庫，本章節(jié)就對(duì)此進(jìn)行簡(jiǎn)單介紹。在把講話下達(dá)的過程中有人惡意把后面的“不”復(fù)制粘貼到前面某段話中則有：“我國(guó)堅(jiān)持長(zhǎng)期不與美國(guó)友好合作”，然后傳遍全球，可能會(huì)引起兩國(guó)友好發(fā)展甚至還會(huì)引發(fā)戰(zhàn)爭(zhēng)。 如此看來音頻數(shù)據(jù)的篡改可能會(huì)影響到原始語音的意思，如果是在軍事通知方面的語音被篡改可能會(huì)照成兩國(guó)進(jìn)入緊急狀態(tài)，司法取證中可能會(huì)讓罪犯逍遙法外。如圖所示： (a)原始語音 （b）復(fù)制粘貼篡改后的語音 在圖中(a)語音表示：“你做的對(duì)，他做的不對(duì)”，(b)語音表示：“你做的不對(duì)，他做的不對(duì)”。模/數(shù)轉(zhuǎn)換圖形比較如下圖： 模擬音頻信號(hào) 數(shù)字音頻信號(hào) 數(shù)字音頻信號(hào)復(fù)制粘貼現(xiàn)象21世紀(jì)已是信息化的社會(huì)，以信息技術(shù)為主要標(biāo)志的高新技術(shù)在整個(gè)經(jīng)濟(jì)中的比重不斷增大，多媒體技術(shù)及產(chǎn)品促進(jìn)了通信、智能、娛樂和計(jì)算機(jī)的融合、以及在國(guó)家執(zhí)政和國(guó)防科技中所占比重越來越大，成為當(dāng)今世界計(jì)算機(jī)產(chǎn)業(yè)發(fā)展的新領(lǐng)域，而多媒體技術(shù)最重要的技術(shù)之一：音頻信息處理技術(shù)，將音頻信息數(shù)字化存入存儲(chǔ)器上，方便了我們保存、遠(yuǎn)距離傳送和復(fù)制粘貼，與此同時(shí)也會(huì)出現(xiàn)有意無意的篡改現(xiàn)象。聲道數(shù)又有單聲道和雙聲道之分。由于計(jì)算機(jī)按字節(jié)運(yùn)算，一般的量化位數(shù)為8位和16位。根據(jù)該采樣理論可知：如果采樣頻率為40KHz，則記錄的最高音頻只有20KHz，這樣的音質(zhì)與原始聲基本沒有差別，正是我們所說的超級(jí)高保真音質(zhì)（Super High FidelityHiFi）。脈沖編碼調(diào)制PCM（Pulse Code Modulation）是一種模數(shù)轉(zhuǎn)換的最基本編碼方法，CDDA就是采用的這種編碼方式。而要記錄幾十分鐘的音樂就需要幾百兆的存儲(chǔ)
外語相關(guān)推薦
鄂ICP備17016276號(hào)-1