第一篇：音頻分類總結(jié)(算法綜述)

總結(jié)音頻分類的算法

剛開始對(duì)音頻分割還有特征提取有些自己的想法，感覺應(yīng)該能夠分清楚，但是當(dāng)開始查閱文獻(xiàn)的時(shí)候，發(fā)現(xiàn)對(duì)他們兩個(gè)的概念越來越模糊。很多時(shí)候他們是重疊的。后來我在一篇文獻(xiàn)里找到這句話。覺得應(yīng)該是這個(gè)道理：

音頻數(shù)據(jù)的分類是一個(gè)模式識(shí)別的問題，它包括兩個(gè)基本方面：特征選擇和分類。

音頻分割是在音頻分類的基礎(chǔ)上從音頻流中提取出不同的音頻類別，也就是說在時(shí)間軸上對(duì)音頻流按類別進(jìn)行劃分。分類是分割的前提和基礎(chǔ)。對(duì)音頻流的準(zhǔn)確分割是最終的目的。

于是我找了一下比較典型的分類算法

比較典型的音頻分類算法包括最小距離方法、支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)、決策樹方法和隱馬爾可夫模型方法等。

1．最小距離法。(典型的音頻分類算法)最小距離分類法的優(yōu)點(diǎn)是概念直觀，方法簡單，有利于建立多維空間分類方法的幾何概念。在音頻分類中應(yīng)用的最小距離分類法有k近鄰(k—Nearest Neighbor，簡稱K—NN)方法和最近特征線方法(Nearest Feature，簡稱NFL))等。

k近鄰方法的思想是根據(jù)未知樣本X最近鄰的k個(gè)樣本點(diǎn)的類別來確定X的類別。為此，需要計(jì)算X與所有樣本x。的距離d(x，x。)，并且從中選出最小的k個(gè)樣本作為近鄰樣本集合KNN，計(jì)算其中所有屬于類別Wj的距離之和，并且按照以下判別規(guī)則進(jìn)行分類：?C(x)?argminC?{W1,...,Wn}

?d(x,xi),其中，C為類別集合由于k近鄰方法利用了更多的樣本信息確定它的類別，k取大一些有利于減少噪聲的影響。但是由于k近鄰方法中需要計(jì)算所有樣本的距離，因此當(dāng)樣本數(shù)目非常大的時(shí)候，計(jì)算量就相當(dāng)可觀。取k=l時(shí)，k近鄰方法就退化為最近鄰方法。

最近特征線方法是從每一類的樣本子空間中選取一些原型(Prototype)特征點(diǎn)，這些特征點(diǎn)的兩兩連線稱為特征線(Feature Line)，這些特征線的集合用來表示原先每一類的樣本子空間。

設(shè)類C的原型特征點(diǎn)集合:,其中Nc為類C的原型特征點(diǎn)數(shù)目，則對(duì)應(yīng)的特征線的數(shù)目為Sc，而類C的特征線集合

{|XicXjc|1?i,j?Nc，i?j} i≠jl構(gòu)成類C的特征線空間，它是類C的特征子空間。—般所選取的原型特征點(diǎn)的數(shù)目比較少，因此特征線的數(shù)目也比較少。未知樣本X與特征線XicXjc的距離定義為x在XicXjc上的投影距離，如圖4所示，而X與類別C的距離為X與類C的特征線空間中的所有特征線的最短距離。

2．神經(jīng)網(wǎng)絡(luò)(Neural Network)。

在使用神經(jīng)網(wǎng)絡(luò)進(jìn)行音頻分類時(shí)，可以令輸入層的節(jié)點(diǎn)與音頻的特征向量相對(duì)應(yīng)，而輸出層的節(jié)點(diǎn)對(duì)應(yīng)于類別Ci。，如圖5所示。在訓(xùn)練時(shí)，通過對(duì)訓(xùn)練樣本集中的樣本進(jìn)行反復(fù)學(xué)習(xí)來調(diào)節(jié)網(wǎng)絡(luò)，從而使全局誤差函數(shù)取得最小值。這樣，就可以期望該網(wǎng)絡(luò)能夠?qū)π螺斎氲拇诸悩颖綯輸出正確的分類Ci。

3．支持向量機(jī)(support Vector Machine，簡稱為SVM)。

支持向量機(jī)是Vapnik等人提出的以結(jié)構(gòu)風(fēng)險(xiǎn)最小化原理(Stuctural Risk Minimization Principle)為基礎(chǔ)的分類方法。該方法最初來自于對(duì)二值分類問題的處理，其機(jī)理是在樣本空間中尋找—個(gè)將訓(xùn)練集中的正例和反例兩類樣本點(diǎn)分割開來的分類超平面，并取得最大邊緣(正樣本與負(fù)樣本到超平面的最小距離)，如圖6所示。該方法根據(jù)核空間理論將低維的輸入空間數(shù)據(jù)通過某種非線性函數(shù)(即核函數(shù))映射到—個(gè)高維空間中，并且線性判決只需要在高維空間中進(jìn)行內(nèi)積運(yùn)算，從而解決了線性不可分的分類問題。

根據(jù)不同的分類問題，可以選用不同的核函數(shù)，常用的核函數(shù)有三種：

① 項(xiàng)式核函數(shù):

② 徑向基核函數(shù):

③ Sigmoid核函數(shù)：

SVM訓(xùn)練算法主要有三類：二次規(guī)劃算法，分解算法，增量算法。

4．決策樹方法

決策樹是一種結(jié)構(gòu)簡單、搜索效率高的分類器。這類方法以信息論為基礎(chǔ)，對(duì)大量的實(shí)例選擇重要的特征建立決策樹，如圖7所示。

最優(yōu)決策樹的構(gòu)造是一個(gè)NP完全(NPComepleteness)問題，其設(shè)計(jì)原則可以形式化地表示為

其中T為特定的決策樹結(jié)構(gòu)，F(xiàn)和d分別為分枝結(jié),為在數(shù)據(jù)集合點(diǎn)的特征子集和決策規(guī)則，D為所有的訓(xùn)練數(shù)據(jù)，D上選取特征集合F和決策規(guī)則d訓(xùn)練得到的結(jié)構(gòu)為T的決策樹的分類錯(cuò)誤?的條件概率。因此，決策樹的構(gòu)造過程可以分為三個(gè)問題：選取合適的結(jié)構(gòu)，為分枝結(jié)點(diǎn)選取合適的特征子集和決策規(guī)則。常用的決策樹構(gòu)造方法有非回溯的貪心(Greedy)算法和梯度上升算法。

5.隱馬爾可夫模型(Hidden Markov Model，簡HMM)方法。

隱馬爾可夫模型(HMM)的音頻分類性能較好，它的分類對(duì)象是語音(speech)、音樂(music)以及語音和音樂的混合(speech+music)共3類數(shù)據(jù)，根據(jù)極大似然準(zhǔn)則判定它們的類別，最優(yōu)分類精度可達(dá)90.28％。

HMM本質(zhì)上是一種雙重隨機(jī)過程的有限狀態(tài)自動(dòng)機(jī)(stochastic finite-state automata)，它具有刻畫信號(hào)的時(shí)間統(tǒng)計(jì)特性的能力。雙重隨機(jī)過程是指滿足Markov分布的狀態(tài)轉(zhuǎn)換Markov鏈以及每一狀態(tài)的觀察輸出概率密度函數(shù)，共兩個(gè)隨機(jī)過程。HMM可以用3元組來表示：入；(A，B，?)，其中A是狀態(tài)Si到Sj的轉(zhuǎn)換概率矩陣，B是狀態(tài)的觀察輸出概率密度，?是狀態(tài)的初始分布概率。

第二篇：分類算法總結(jié)

分類算法

數(shù)據(jù)挖掘中有很多領(lǐng)域，分類就是其中之一，什么是分類，分類就是把一些新得數(shù)據(jù)項(xiàng)映射到給定類別的中的某一個(gè)類別，比如說當(dāng)我們發(fā)表一篇文章的時(shí)候，就可以自動(dòng)的把這篇文章劃分到某一個(gè)文章類別，一般的過程是根據(jù)樣本數(shù)據(jù)利用一定的分類算法得到分類規(guī)則，新的數(shù)據(jù)過來就依據(jù)該規(guī)則進(jìn)行類別的劃分。

分類在數(shù)據(jù)挖掘中是一項(xiàng)非常重要的任務(wù)，有很多用途，比如說預(yù)測，即從歷史的樣本數(shù)據(jù)推算出未來數(shù)據(jù)的趨向，有一個(gè)比較著名的預(yù)測的例子就是大豆學(xué)習(xí)。再比如說分析用戶行為，我們常稱之為受眾分析，通過這種分類，我們可以得知某一商品的用戶群，對(duì)銷售來說有很大的幫助。

分類器的構(gòu)造方法有統(tǒng)計(jì)方法，機(jī)器學(xué)習(xí)方法，神經(jīng)網(wǎng)絡(luò)方法等等。常見的統(tǒng)計(jì)方法有knn算法，基于事例的學(xué)習(xí)方法。機(jī)器學(xué)習(xí)方法包括決策樹法和歸納法，上面講到的受眾分析可以使用決策樹方法來實(shí)現(xiàn)。神經(jīng)網(wǎng)絡(luò)方法主要是bp算法，這個(gè)俺也不太了解。文本分類，所謂的文本分類就是把文本進(jìn)行歸類，不同的文章根據(jù)文章的內(nèi)容應(yīng)該屬于不同的類別，文本分類離不開分詞，要將一個(gè)文本進(jìn)行分類，首先需要對(duì)該文本進(jìn)行分詞，利用分詞之后的的項(xiàng)向量作為計(jì)算因子，再使用一定的算法和樣本中的詞匯進(jìn)行計(jì)算，從而可以得出正確的分類結(jié)果。在這個(gè)例子中，我將使用庖丁分詞器對(duì)文本進(jìn)行分詞。目前看到的比較全面的分類算法,總結(jié)的還不錯(cuò).2.4.1 主要分類方法介紹解決分類問題的方法很多[40-42]，單一的分類方法主要包括：決策樹、貝葉斯、人工神經(jīng)網(wǎng)絡(luò)、K-近鄰、支持向量機(jī)和基于關(guān)聯(lián)規(guī)則的分類等；另外還有用于組合單一分類方法的集成學(xué)習(xí)算法，如Bagging和Boosting等。（1）決策樹

決策樹是用于分類和預(yù)測的主要技術(shù)之一，決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法，它著眼于從一組無次序、無規(guī)則的實(shí)例中推理出以決策樹表示的分類規(guī)則。構(gòu)造決策樹的目的是找出屬性和類別間的關(guān)系，用它來預(yù)測將來未知類別的記錄的類別。它采用自頂向下的遞歸方式，在決策樹的內(nèi)部節(jié)點(diǎn)進(jìn)行屬性的比較，并根據(jù)不同屬性值判斷從該節(jié)點(diǎn)向下的分支，在決策樹的葉節(jié)點(diǎn)得到結(jié)論。

主要的決策樹算法有ID3、C4.5（C5.0）、CART、PUBLIC、SLIQ和SPRINT算法等。它們?cè)谶x擇測試屬性采用的技術(shù)、生成的決策樹的結(jié)構(gòu)、剪枝的方法以及時(shí)刻，能否處理大數(shù)據(jù)集等方面都有各自的不同之處。（2）貝葉斯 貝葉斯（Bayes）分類算法是一類利用概率統(tǒng)計(jì)知識(shí)進(jìn)行分類的算法，如樸素貝葉斯（Naive Bayes）算法。這些算法主要利用Bayes定理來預(yù)測一個(gè)未知類別的樣本屬于各個(gè)類別的可能性，選擇其中可能性最大的一個(gè)類別作為該樣本的最終類別。由于貝葉斯定理的成立本身需要一個(gè)很強(qiáng)的條件獨(dú)立性假設(shè)前提，而此假設(shè)在實(shí)際情況中經(jīng)常是不成立的，因而其分類準(zhǔn)確性就會(huì)下降。為此就出現(xiàn)了許多降低獨(dú)立性假設(shè)的貝葉斯分類算法，如TAN（Tree Augmented Na?ve Bayes)算法，它是在貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上增加屬性對(duì)之間的關(guān)聯(lián)來實(shí)現(xiàn)的。

（3）人工神經(jīng)網(wǎng)絡(luò)

人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Networks，ANN）是一種應(yīng)用類似于大腦神經(jīng)突觸聯(lián)接的結(jié)構(gòu)進(jìn)行信息處理的數(shù)學(xué)模型。在這種模型中，大量的節(jié)點(diǎn)（或稱”神經(jīng)元”，或”單元”）之間相互聯(lián)接構(gòu)成網(wǎng)絡(luò)，即”神經(jīng)網(wǎng)絡(luò)”，以達(dá)到處理信息的目的。神經(jīng)網(wǎng)絡(luò)通常需要進(jìn)行訓(xùn)練，訓(xùn)練的過程就是網(wǎng)絡(luò)進(jìn)行學(xué)習(xí)的過程。訓(xùn)練改變了網(wǎng)絡(luò)節(jié)點(diǎn)的連接權(quán)的值使其具有分類的功能，經(jīng)過訓(xùn)練的網(wǎng)絡(luò)就可用于對(duì)象的識(shí)別。目前，神經(jīng)網(wǎng)絡(luò)已有上百種不同的模型，常見的有BP網(wǎng)絡(luò)、徑向基RBF網(wǎng)絡(luò)、Hopfield網(wǎng)絡(luò)、隨機(jī)神經(jīng)網(wǎng)絡(luò)（Boltzmann機(jī)）、競爭神經(jīng)網(wǎng)絡(luò)（Hamming網(wǎng)絡(luò)，自組織映射網(wǎng)絡(luò)）等。但是當(dāng)前的神經(jīng)網(wǎng)絡(luò)仍普遍存在收斂速度慢、計(jì)算量大、訓(xùn)練時(shí)間長和不可解釋等缺點(diǎn)。（4）k-近鄰

k-近鄰(kNN，k-Nearest Neighbors)算法是一種基于實(shí)例的分類方法。該方法就是找出與未知樣本x距離最近的k個(gè)訓(xùn)練樣本，看這k個(gè)樣本中多數(shù)屬于哪一類，就把x歸為那一類。k-近鄰方法是一種懶惰學(xué)習(xí)方法，它存放樣本，直到需要分類時(shí)才進(jìn)行分類，如果樣本集比較復(fù)雜，可能會(huì)導(dǎo)致很大的計(jì)算開銷，因此無法應(yīng)用到實(shí)時(shí)性很強(qiáng)的場合。（5）支持向量機(jī)

支持向量機(jī)（SVM，Support Vector Machine）是Vapnik根據(jù)統(tǒng)計(jì)學(xué)習(xí)理論提出的一種新的學(xué)習(xí)方法[43]，它的最大特點(diǎn)是根據(jù)結(jié)構(gòu)風(fēng)險(xiǎn)最小化準(zhǔn)則，以最大化分類間隔構(gòu)造最優(yōu)分類超平面來提高學(xué)習(xí)機(jī)的泛化能力，較好地解決了非線性、高維數(shù)、局部極小點(diǎn)等問題。對(duì)于分類問題，支持向量機(jī)算法根據(jù)區(qū)域中的樣本計(jì)算該區(qū)域的決策曲面，由此確定該區(qū)域中未知樣本的類別。

（6）基于關(guān)聯(lián)規(guī)則的分類

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中一個(gè)重要的研究領(lǐng)域。近年來，對(duì)于如何將關(guān)聯(lián)規(guī)則挖掘用于分類問題，學(xué)者們進(jìn)行了廣泛的研究。關(guān)聯(lián)分類方法挖掘形如condset→C的規(guī)則，其中condset是項(xiàng)(或?qū)傩?值對(duì))的集合，而C是類標(biāo)號(hào)，這種形式的規(guī)則稱為類關(guān)聯(lián)規(guī)則（class association rules，CARS）。關(guān)聯(lián)分類方法一般由兩步組成：第一步用關(guān)聯(lián)規(guī)則挖掘算法從訓(xùn)練數(shù)據(jù)集中挖掘出所有滿足指定支持度和置信度的類關(guān)聯(lián)規(guī)則；第二步使用啟發(fā)式方法從挖掘出的類關(guān)聯(lián)規(guī)則中挑選出一組高質(zhì)量的規(guī)則用于分類。屬于關(guān)聯(lián)分類的算法主要包括CBA[44]，ADT[45]，CMAR[46] 等。（7）集成學(xué)習(xí)（Ensemble Learning）

實(shí)際應(yīng)用的復(fù)雜性和數(shù)據(jù)的多樣性往往使得單一的分類方法不夠有效。因此，學(xué)者們對(duì)多種分類方法的融合即集成學(xué)習(xí)進(jìn)行了廣泛的研究。集成學(xué)習(xí)已成為國際機(jī)器學(xué)習(xí)界的研究熱點(diǎn)，并被稱為當(dāng)前機(jī)器學(xué)習(xí)四個(gè)主要研究方向之一。集成學(xué)習(xí)是一種機(jī)器學(xué)習(xí)范式，它試圖通過連續(xù)調(diào)用單個(gè)的學(xué)習(xí)算法，獲得不同的基學(xué)習(xí)器，然后根據(jù)規(guī)則組合這些學(xué)習(xí)器來解決同一個(gè)問題，可以顯著的提高學(xué)習(xí)系統(tǒng)的泛化能力。組合多個(gè)基學(xué)習(xí)器主要采用（加權(quán)）投票的方法，常見的算法有裝袋[47]（Bagging），提升/推進(jìn)[48, 49]（Boosting）等。

有關(guān)分類器的集成學(xué)習(xí)見圖2-5。集成學(xué)習(xí)由于采用了投票平均的方法組合多個(gè)分類器，所以有可能減少單個(gè)分類器的誤差，獲得對(duì)問題空間模型更加準(zhǔn)確的表示，從而提高分類器的分類準(zhǔn)確度。

圖2-5：分類器的集成學(xué)習(xí)

以上簡單介紹了各種主要的分類方法，應(yīng)該說其都有各自不同的特點(diǎn)及優(yōu)缺點(diǎn)。對(duì)于數(shù)據(jù)庫負(fù)載的自動(dòng)識(shí)別，應(yīng)該選擇哪種方法呢？用來比較和評(píng)估分類方法的標(biāo)準(zhǔn)[50] 主要有：（1）預(yù)測的準(zhǔn)確率。模型正確地預(yù)測新樣本的類標(biāo)號(hào)的能力；（2）計(jì)算速度。包括構(gòu)造模型以及使用模型進(jìn)行分類的時(shí)間；（3）強(qiáng)壯性。模型對(duì)噪聲數(shù)據(jù)或空缺值數(shù)據(jù)正確預(yù)測的能力；（4）可伸縮性。對(duì)于數(shù)據(jù)量很大的數(shù)據(jù)集，有效構(gòu)造模型的能力；（5）模型描述的簡潔性和可解釋性。模型描述愈簡潔、愈容易理解，則愈受歡迎。

最初的數(shù)據(jù)挖掘分類應(yīng)用大多都是在這些方法及基于內(nèi)存基礎(chǔ)上所構(gòu)造的算法。目前數(shù)據(jù)挖掘方法都要求具有基于外存以處理大規(guī)模數(shù)據(jù)集合能力且具有可擴(kuò)展能力。下面對(duì)幾種主要的分類方法做個(gè)簡要介紹：

（1）決策樹

決策樹歸納是經(jīng)典的分類算法。它采用自頂向下遞歸的各個(gè)擊破方式構(gòu)造決策樹。樹的每一個(gè)結(jié)點(diǎn)上使用信息增益度量選擇測試屬性。可以從生成的決策樹中提取規(guī)則。

(2)KNN法(K-Nearest Neighbor)

KNN法即K最近鄰法，最初由Cover和Hart于1968年提出的，是一個(gè)理論上比較成熟的方法。該方法的思路非常簡單直觀：如果一個(gè)樣本在特征空間中的k個(gè)最相似(即特征空間中最鄰近)的樣本中的大多數(shù)屬于某一個(gè)類別，則該樣本也屬于這個(gè)類別。該方法在定類決策上只依據(jù)最鄰近的一個(gè)或者幾個(gè)樣本的類別來決定待分樣本所屬的類別。

KNN方法雖然從原理上也依賴于極限定理，但在類別決策時(shí)，只與極少量的相鄰樣本有關(guān)。因此，采用這種方法可以較好地避免樣本的不平衡問題。另外，由于KNN方法主要靠周圍有限的鄰近的樣本，而不是靠判別類域的方法來確定所屬類別的，因此對(duì)于類域的交叉或重疊較多的待分樣本集來說，KNN方法較其他方法更為適合。

該方法的不足之處是計(jì)算量較大，因?yàn)閷?duì)每一個(gè)待分類的文本都要計(jì)算它到全體已知樣本的距離，才能求得它的K個(gè)最近鄰點(diǎn)。目前常用的解決方法是事先對(duì)已知樣本點(diǎn)進(jìn)行剪輯，事先去除對(duì)分類作用不大的樣本。另外還有一種Reverse KNN法，能降低KNN算法的計(jì)算復(fù)雜度，提高分類的效率。

該算法比較適用于樣本容量比較大的類域的自動(dòng)分類，而那些樣本容量較小的類域采用這種算法比較容易產(chǎn)生誤分。

(3)SVM法

SVM法即支持向量機(jī)(Support Vector Machine)法，由Vapnik等人于1995年提出，具有相對(duì)優(yōu)良的性能指標(biāo)。該方法是建立在統(tǒng)計(jì)學(xué)習(xí)理論基礎(chǔ)上的機(jī)器學(xué)習(xí)方法。通過學(xué)習(xí)算法，SVM可以自動(dòng)尋找出那些對(duì)分類有較好區(qū)分能力的支持向量，由此構(gòu)造出的分類器可以最大化類與類的間隔，因而有較好的適應(yīng)能力和較高的分準(zhǔn)率。該方法只需要由各類域的邊界樣本的類別來決定最后的分類結(jié)果。

支持向量機(jī)算法的目的在于尋找一個(gè)超平面H(d),該超平面可以將訓(xùn)練集中的數(shù)據(jù)分開，且與類域邊界的沿垂直于該超平面方向的距離最大，故SVM法亦被稱為最大邊緣(maximum margin)算法。待分樣本集中的大部分樣本不是支持向量，移去或者減少這些樣本對(duì)分類結(jié)果沒有影響，SVM法對(duì)小樣本情況下的自動(dòng)分類有著較好的分類結(jié)果。

(4)VSM法

VSM法即向量空間模型(Vector Space Model)法，由Salton等人于60年代末提出。這是最早也是最出名的信息檢索方面的數(shù)學(xué)模型。其基本思想是將文檔表示為加權(quán)的特征向量：D=D(T1，W1；T2，W2；…；Tn，Wn)，然后通過計(jì)算文本相似度的方法來確定待分樣本的類別。當(dāng)文本被表示為空間向量模型的時(shí)候，文本的相似度就可以借助特征向量之間的內(nèi)積來表示。

在實(shí)際應(yīng)用中，VSM法一般事先依據(jù)語料庫中的訓(xùn)練樣本和分類體系建立類別向量空間。當(dāng)需要對(duì)一篇待分樣本進(jìn)行分類的時(shí)候，只需要計(jì)算待分樣本和每一個(gè)類別向量的相似度即內(nèi)積，然后選取相似度最大的類別作為該待分樣本所對(duì)應(yīng)的類別。

由于VSM法中需要事先計(jì)算類別的空間向量，而該空間向量的建立又很大程度的依賴于該類別向量中所包含的特征項(xiàng)。根據(jù)研究發(fā)現(xiàn)，類別中所包含的非零特征項(xiàng)越多，其包含的每個(gè)特征項(xiàng)對(duì)于類別的表達(dá)能力越弱。因此，VSM法相對(duì)其他分類方法而言，更適合于專業(yè)文獻(xiàn)的分類。

(5)Bayes法

Bayes法是一種在已知先驗(yàn)概率與類條件概率的情況下的模式分類方法，待分樣本的分類結(jié)果取決于各類域中樣本的全體。

設(shè)訓(xùn)練樣本集分為M類，記為C=｛c1，…，ci，…cM}，每類的先驗(yàn)概率為P(ci)，i=1，2，…，M。當(dāng)樣本集非常大時(shí)，可以認(rèn)為P(ci)=ci類樣本數(shù)/總樣本數(shù)。對(duì)于一個(gè)待分樣本X，其歸于cj類的類條件概率是P(X/ci)，則根據(jù)Bayes定理，可得到cj類的后驗(yàn)概率P(ci/X)：

P(ci/x)=P(x/ci)?P(ci)/P(x)(1)若P(ci/X)=MaxjP(cj/X)，i=1，2，…，M，j=1，2，…，M，則有x∈ci(2)式(2)是最大后驗(yàn)概率判決準(zhǔn)則，將式(1)代入式(2)，則有：

若P(x/ci)P(ci)=Maxj［P(x/cj)P(cj)］，i=1，2，…，M，j=1，2，…，M，則x∈ci 這就是常用到的Bayes分類判決準(zhǔn)則。經(jīng)過長期的研究，Bayes分類方法在理論上論證得比較充分，在應(yīng)用上也是非常廣泛的。

Bayes方法的薄弱環(huán)節(jié)在于實(shí)際情況下，類別總體的概率分布和各類樣本的概率分布函數(shù)(或密度函數(shù))常常是不知道的。為了獲得它們，就要求樣本足夠大。另外，Bayes法要求表達(dá)文本的主題詞相互獨(dú)立，這樣的條件在實(shí)際文本中一般很難滿足，因此該方法往往在效果上難以達(dá)到理論上的最大值。

（6）神經(jīng)網(wǎng)絡(luò)

神經(jīng)網(wǎng)絡(luò)分類算法的重點(diǎn)是構(gòu)造閾值邏輯單元，一個(gè)值邏輯單元是一個(gè)對(duì)象，它可以輸入一組加權(quán)系數(shù)的量，對(duì)它們進(jìn)行求和，如果這個(gè)和達(dá)到或者超過了某個(gè)閾值，輸出一個(gè)量。如有輸入值X1, X2,..., Xn和它們的權(quán)系數(shù)：W1, W2,...,Wn，求和計(jì)算出的 Xi*Wi，產(chǎn)生了激發(fā)層 a =(X1 * W1)+(X2 * W2)+...+(Xi * Wi)+...+(Xn * Wn)，其中Xi 是各條記錄出現(xiàn)頻率或其他參數(shù)，Wi是實(shí)時(shí)特征評(píng)估模型中得到的權(quán)系數(shù)。神經(jīng)網(wǎng)絡(luò)是基于經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化原則的學(xué)習(xí)算法，有一些固有的缺陷，比如層數(shù)和神經(jīng)元個(gè)數(shù)難以確定，容易陷入局部極小，還有過學(xué)習(xí)現(xiàn)象，這些本身的缺陷在SVM算法中可以得到很好的解決。

第三篇：2018高考分類-算法

（2018北京3）.執(zhí)行如圖所示的程序框圖，輸出的s值為 A.B.C.D.，設(shè)計(jì)了下面的程序框圖，則在空白框中應(yīng)填入

D.（2018全國2）7.為計(jì)算A.B.C.（2018北京3）

（2018全國2）

（2018天津3）.閱讀右邊的程序框圖，運(yùn)行相應(yīng)的程序，若輸入N的值為20，則輸出T的值為

A.1

B.2

C.3

D.4

（2018江蘇）4.一個(gè)算法的偽代碼如圖所示，執(zhí)行此算法，最后輸出的S的值為________．

（2018江蘇）

（2018天津3）

第四篇：alsa音頻總結(jié)

Linux音頻驅(qū)動(dòng)總結(jié)

參考文章：http://blog.csdn.net/droidphone/

http://blog.chinaunix.net/uid/22917448.html

分析只列出部分重要代碼，具體請(qǐng)參考linux3.0內(nèi)核代碼。

Alsa架構(gòu)整體來說十分復(fù)雜，但對(duì)于驅(qū)動(dòng)移植來說我們僅僅只需要關(guān)心ASOC就足夠了。在學(xué)習(xí)asoc之前我們先了解一些專業(yè)術(shù)語：

ASoC currently supports the three main Digital Audio Interfaces(DAI)found on SoC controllers and portable audio CODECs today, namely AC97, I2S and PCM.ASoC現(xiàn)在支持如今的SoC控制器和便攜音頻解碼器上的三個(gè)主要數(shù)字音頻接口，即AC97，I2S，PCM（與pcm音頻格式注意區(qū)分，前者是一種音頻接口，后者是一種輸入聲卡的音頻格式）。

AC97 AC97 ====

AC97 is a five wire interface commonly found on many PC sound cards.It is now also popular in many portable devices.This DAI has a reset line and time multiplexes its data on its SDATA_OUT(playback)and SDATA_IN(capture)lines.The bit clock(BCLK)is always driven by the CODEC(usually 12.288MHz)and the frame(FRAME)(usually 48kHz)is always driven by the controller.Each AC97 frame is 21uS long and is divided into 13 time slots.AC97是一種個(gè)人電腦聲卡上常見的五線接口?，F(xiàn)在在很多便攜設(shè)備中也很流行。這個(gè)數(shù)字音頻接口有一個(gè)復(fù)位線，分時(shí)在SDATA＿OUT（回放）和SDATA＿IN（捕獲）線上傳送數(shù)據(jù)。位時(shí)鐘常由解碼器驅(qū)動(dòng)（通常是12.288MHz).幀時(shí)鐘（通常48kHz)總是由控制器驅(qū)動(dòng)。每個(gè)AC97幀21uS,并分為13個(gè)時(shí)間槽。

I2S I2S ===

I2S is a common 4 wire DAI used in HiFi, STB and portable devices.The Tx and Rx lines are used for audio transmission, whilst the bit clock(BCLK)and left/right clock(LRC)synchronise the link.I2S is flexible in that either the controller or CODEC can drive(master)the BCLK and LRC clock lines.Bit clock usually varies depending on the sample rate and the master system clock(SYSCLK).LRCLK is the same as the sample rate.A few devices support separate ADC and DAC LRCLKs, this allows for simultaneous capture and playback at different sample rates.I2S是一個(gè)4線數(shù)字音頻接口，常用于HiFi，STB便攜設(shè)備。Tx 和Rx信號(hào)線用于音頻傳輸。而位時(shí)鐘和左右時(shí)鐘（LRC）用于同步鏈接。I2S具有靈活性，因?yàn)榭刂破骱徒獯a器都可以控制位時(shí)鐘和左右時(shí)鐘。位時(shí)鐘因采樣率和主系統(tǒng)時(shí)鐘而有不同。LRCLK與采樣率相同。少數(shù)設(shè)備支持獨(dú)立的ADC和DAC的LRCLK。這使在不同采樣率情況下同步捕獲和回放成為可能。

I2S has several different operating modes:-I2S有幾個(gè)不同的操作模式：

o I2SMSB is transmitted on transition of LRC.左對(duì)齊模式：MSB在LRC傳送時(shí)傳送。

o Right JustifiedMSB is transmitted on falling edge of first BCLK after FRAME/SYNC.模式A－MSB在FRAME/SYNC后第一個(gè)BCLK的下降沿傳送。

o Mode Busing I2C, 3 Wire(SPI)or both APIs 3)Mixers and audio controls 4)Codec audio operations 1）解碼器數(shù)字音頻接口和PCM配置。

2）解碼器控制IO－使用I2C，3總線（SPI）或兩個(gè)都有。3）混音器和音頻控制。4）解碼器音頻操作。

Optionally, codec drivers can also provide:-解碼器驅(qū)動(dòng)可以選擇性提供：

5)DAPM description.6)DAPM event handler.7)DAC Digital mute control.5）動(dòng)態(tài)音頻電源管理描述。6）動(dòng)態(tài)音頻電源管理事件控制。7）數(shù)模轉(zhuǎn)換數(shù)字消音控制。SoC DAI Drivers 板級(jí)DAI驅(qū)動(dòng) ===============

Each SoC DAI driver must provide the following features:-每個(gè)SoC DAI驅(qū)動(dòng)都必須提供如下性能：

1)Digital audio interface(DAI)description 1)數(shù)字音頻接口描述

2)Digital audio interface configuration 2)數(shù)字音頻接口配置 3)PCM's description 3）PCM描述

4)SYSCLK configuration 4）系統(tǒng)時(shí)鐘配置

5)Suspend and resume(optional)5）掛起和恢復(fù)（可選的）

以上由君子翻譯，本人實(shí)在沒辦法比他描述的更好了，所以把重要的部分提取出來直接copy。在這里對(duì)君子表示由衷感謝，賦上君子注。君子注:

您現(xiàn)在所閱讀的，是君子閱讀Linux音頻SoC驅(qū)動(dòng)時(shí)，寫下的文檔譯文。

君子寫些譯文，一方面是作為自己的筆記，幫助記憶，另一方面也希望能對(duì)他人有所幫助。如果您能于君子的譯文中有所收獲，則吾心甚慰

現(xiàn)在我們開始分析ASOC：

ASoC被分為Machine、Platform和Codec三大部分。其中的Machine驅(qū)動(dòng)負(fù)責(zé)Platform和Codec之間的耦合和設(shè)備或板子特定的代碼。

看起來挺復(fù)雜，其實(shí)需要我們做的事情并不多，大部分內(nèi)核已經(jīng)完成。下面我們分析哪些是我們需要自己做的：

codec驅(qū)動(dòng)：負(fù)責(zé)音頻解碼。這部分代碼完全無平臺(tái)無關(guān)，設(shè)備原廠提供，我們只需要把它加進(jìn)內(nèi)核編譯就好了。platform驅(qū)動(dòng)：與處理器芯片相關(guān)，這部分代碼在該芯片商用之前方案產(chǎn)商提供的demo板已完全確定了，也就是說我們只需要使用就可以了。

machine驅(qū)動(dòng)：好了，到了最關(guān)鍵的地方了，machine驅(qū)動(dòng)是耦合platform和codec驅(qū)動(dòng)，同時(shí)與上層交互的代碼。由于上層是標(biāo)準(zhǔn)的alsa架構(gòu)，所以下層接口肯定要做了統(tǒng)一，所以我很負(fù)責(zé)的告訴你，這部分由machine本身的platform驅(qū)動(dòng)和platform設(shè)備組成(請(qǐng)跟asoc的platform驅(qū)動(dòng)區(qū)別)，platform驅(qū)動(dòng)內(nèi)核幫我們完成了，所以你無須過多的關(guān)心你的驅(qū)動(dòng)怎么跟上層alsa怎么衍接的問題，我們只需要注冊(cè)一個(gè)machine的platform設(shè)備以及完成platform和codec耦合就ok

asoc的關(guān)系圖如下：（以下適應(yīng)于linux3.0。linux2.6會(huì)有所不同）

上圖把a(bǔ)soc架構(gòu)顯示的淋漓盡致，如果你分析了asoc你就會(huì)發(fā)現(xiàn)上圖描述的結(jié)構(gòu)以及函數(shù)真的一個(gè)都跑不了。

Machie：

Machine platform device:(~/sound/soc/samsung/smdk_wm8994.c)

1.smdk_snd_device = platform_device_alloc(“soc-audio”,-1);2.if(!smdk_snd_device)3.return-ENOMEM;4.5.platform_set_drvdata(smdk_snd_device, &smdk);6.7.ret = platform_device_add(smdk_snd_device);

1.static struct snd_soc_dai_link smdk_dai[] = { 2.{ /* Primary DAI i/f */

3..name = “WM8994 AIF1”, 4..stream_name = “Pri_Dai”, 5..cpu_dai_name = “samsung-i2s.0”, 6..codec_dai_name = “wm8994-aif1”, 7..platform_name = “samsung-audio”, 8..codec_name = “wm8994-codec”, 9..init = smdk_wm8994_init_paiftx, 10..ops = &smdk_ops, 11.}, { /* Sec_Fifo Playback i/f */

12..name = “Sec_FIFO TX”, 13..stream_name = “Sec_Dai”, 14..cpu_dai_name = “samsung-i2s.4”, 15..codec_dai_name = “wm8994-aif1”, 16..platform_name = “samsung-audio”, 17..codec_name = “wm8994-codec”, 18..ops = &smdk_ops, 19.}, 20.};21.22.static struct snd_soc_card smdk = { 23..name = “SMDK-I2S”, 24..owner = THIS_MODULE, 25..dai_link = smdk_dai，26..num_links = ARRAY_SIZE(smdk_dai), 27.};

通過snd_soc_card結(jié)構(gòu)，又引出了Machine驅(qū)動(dòng)的另外兩個(gè)個(gè)數(shù)據(jù)結(jié)構(gòu)：

? ? snd_soc_dai_link（實(shí)例：smdk_dai[]）snd_soc_ops（實(shí)例：smdk_ops）

snd_soc_dai_link看名字就知道，很明顯它是起耦合鏈接作用的。它指定了Platform、Codec、codec_dai、cpu_dai的名字，稍后Machine驅(qū)動(dòng)將會(huì)利用這些名字去匹配已經(jīng)在系統(tǒng)中注冊(cè)的platform，codec，dai。

snd_soc_ops連接Platform和Codec的dai_link對(duì)應(yīng)的ops操作函數(shù)，本例就是smdk_ops，它只實(shí)現(xiàn)了hw_params函數(shù)：smdk_hw_params。

到此為止，最主要的部分machine的平臺(tái)設(shè)備注冊(cè)我們完成了。

下面我們關(guān)注machine平臺(tái)驅(qū)動(dòng)部分(這部分內(nèi)核不需要我們實(shí)現(xiàn)，但我們需要知道它是怎么工作的）

ASoC的platform_driver在以下文件中定義：sound/soc/soc-core.c。還是先從模塊的入口看起：

[cpp] view plaincopy 1.static int __init snd_soc_init(void)2.{ 3.......4.return platform_driver_register(&soc_driver);5.}

soc_driver的定義如下：

[cpp] view plaincopy

1./* ASoC platform driver */

2.static struct platform_driver soc_driver = { 3..driver = {

4..name = “soc-audio”, //確保你注冊(cè)machine平臺(tái)設(shè)備和它保持一致 5..owner = THIS_MODULE, 6..pm = &soc_pm_ops, 7.}，8..probe = soc_probe, 9..remove = soc_remove, 10.};

初始化入口soc_probe()

soc_probe函數(shù)本身很簡單，它先從platform_device參數(shù)中取出snd_soc_card，然后調(diào)用snd_soc_register_card，通過snd_soc_register_card，為snd_soc_pcm_runtime數(shù)組申請(qǐng)內(nèi)存，每一個(gè)dai_link對(duì)應(yīng)snd_soc_pcm_runtime數(shù)組的一個(gè)單元，然后把snd_soc_card中的dai_link配置復(fù)制到相應(yīng)的snd_soc_pcm_runtime中，最后，大部分的工作都在snd_soc_instantiate_card中實(shí)現(xiàn)，下面就看看snd_soc_instantiate_card做了些什么： 該函數(shù)首先利用card->instantiated來判斷該卡是否已經(jīng)實(shí)例化，如果已經(jīng)實(shí)例化則直接返回，否則遍歷每一對(duì)dai_link，進(jìn)行codec、platform、dai的綁定工作，下只是代碼的部分選節(jié)，詳細(xì)的代碼請(qǐng)直接參考完整的代碼樹。static int soc_probe(struct platform_device *pdev){

struct snd_soc_card *card = platform_get_drvdata(pdev);//別忘記了machine的platform_set_drvdata //取出snd_soc_card

.............ret = snd_soc_register_card(card);//注冊(cè)............}

下面我們看snd_soc_register_card()函數(shù):

int snd_soc_register_card(struct snd_soc_card *card){

。。。。

card->rtd = kzalloc(sizeof(struct snd_soc_pcm_runtime)*

(card->num_links + card->num_aux_devs)，GFP_KERNEL);//為snd_soc_pcm_runtime數(shù)組申請(qǐng)內(nèi)存，每一個(gè)dai_link對(duì)應(yīng)一個(gè)snd_soc_pcm_runtime數(shù)組單元。。。。

for(i = 0;i < card->num_links;i++)

card->rtd[i].dai_link = &card->dai_link[i];//把snd_soc_card中的dai_link復(fù)制到相應(yīng)的snd_soc_pcm_runtime。。。。

snd_soc_instantiate_cards();//將調(diào)用snd_soc_instantiate_card()//最為重要 }

下面我們分析snd_soc_instantiate_card()函數(shù)：

static void snd_soc_instantiate_card(struct snd_soc_card *card){

。。。。

if(card->instantiated){ //判斷該卡是否已經(jīng)實(shí)例化，如果是就返回

mutex_unlock(&card->mutex);

return;

}

/* bind DAIs */

for(i = 0;i < card->num_links;i++)//否則遍例每一對(duì)dai_link，進(jìn)行codec,flatrom,dai的綁定工作

soc_bind_dai_link(card, i);/* ******************************************************************************************************************************************************************

ASoC定義了三個(gè)全局的鏈表頭變量：codec_list、dai_list、platform_list，系統(tǒng)中所有的Codec、DAI、Platform都在注冊(cè)時(shí)連接到這三個(gè)全局鏈表上。soc_bind_dai_link函數(shù)逐個(gè)掃描這三個(gè)鏈表，根據(jù)card->dai_link[]中的名稱進(jìn)行匹配，匹配后把相應(yīng)的codec，dai和platform實(shí)例賦值到card->rtd[]中（snd_soc_pcm_runtime）。經(jīng)過這個(gè)過程后，snd_soc_pcm_runtime：（card->rtd）中保存了本Machine中使用的Codec，DAI和Platform驅(qū)動(dòng)的信息。

*****************************************************************************************************************************************************************/

/* bind completed ? */

if(card->num_rtd!= card->num_links){

mutex_unlock(&card->mutex);

return;

}

。。。。。

/* card bind complete so register a sound card */

ret = snd_card_create(SNDRV_DEFAULT_IDX1, SNDRV_DEFAULT_STR1,card->owner, 0, &card->snd_card)。。。。。

card->snd_card->dev = card->dev;

card->dapm.bias_level = SND_SOC_BIAS_OFF;

card->dapm.dev = card->dev;

card->dapm.card = card;

list_add(&card->dapm.list, &card->dapm_list);//初始化codec緩存，創(chuàng)建聲卡實(shí)例

。。。。。。。//下面是最重要的probe匹配工作

if(card->probe){

ret = card->probe(card);

if(ret < 0)

goto card_probe_error;

}

。。。。。

ret = soc_probe_dai_link(card, i, order);//主要的耦合鏈接工作在此函數(shù)完成。。。。。

ret = soc_probe_aux_dev(card, i)。。。。。

if(card->late_probe){//最后的聲卡初始化工作，ret = card->late_probe(card);

}

。。。。。

ret = snd_card_register(card->snd_card);//然后調(diào)用標(biāo)準(zhǔn)的alsa驅(qū)動(dòng)的聲卡函數(shù)進(jìn)行聲卡注冊(cè)

。。。。。

}

到這里聲卡已經(jīng)注冊(cè)好了，聲卡可以正常工作了，我們?cè)俜治鲎詈笠粋€(gè)函數(shù)，也就是它們是怎么匹配的 soc_probe_dai_link():

static int soc_probe_dai_link(struct snd_soc_card *card, int num, int order){

。。。。。

/* probe the cpu_dai */

if(!cpu_dai->probed &&

cpu_dai->driver->probe_order == order){

if(!try_module_get(cpu_dai->dev->driver->owner))

return-ENODEV;

if(cpu_dai->driver->probe){

ret = cpu_dai->driver->probe(cpu_dai);

if(ret < 0){

printk(KERN_ERR “asoc: failed to probe CPU DAI %sn”, cpu_dai->name);

module_put(cpu_dai->dev->driver->owner);

return ret;

}

}

cpu_dai->probed = 1;

/* mark cpu_dai as probed and add to card dai list */

list_add(&cpu_dai->card_list, &card->dai_dev_list);

}

/* probe the CODEC */

if(!codec->probed &&

codec->driver->probe_order == order){

ret = soc_probe_codec(card, codec);

if(ret < 0)

return ret;

}

/* probe the platform */

if(!platform->probed &&

platform->driver->probe_order == order){

ret = soc_probe_platform(card, platform);

if(ret < 0)

return ret;

}

/* probe the CODEC DAI */

if(!codec_dai->probed && codec_dai->driver->probe_order == order){

if(codec_dai->driver->probe){

ret = codec_dai->driver->probe(codec_dai);

if(ret < 0){

printk(KERN_ERR “asoc: failed to probe CODEC DAI %sn”, codec_dai->name);

return ret;

}

}

/* mark codec_dai as probed and add to card dai list */

codec_dai->probed = 1;

list_add(&codec_dai->card_list, &card->dai_dev_list);

}

/* complete DAI probe during last probe */

if(order!= SND_SOC_COMP_ORDER_LAST)return 0;

。。。。。

/* create the pcm */

ret = soc_new_pcm(rtd, num);//如果上面都匹配成功將創(chuàng)建標(biāo)準(zhǔn)的alsa的pcm邏輯設(shè)備

。。。。。

}

好了，到此為止我們最主要的部分machine部分分析完成了。接著是codec驅(qū)動(dòng)部分：

Codec簡介

在移動(dòng)設(shè)備中，Codec的作用可以歸結(jié)為4種，分別是：

? ? 對(duì)PCM等信號(hào)進(jìn)行D/A轉(zhuǎn)換，把數(shù)字的音頻信號(hào)轉(zhuǎn)換為模擬信號(hào)

對(duì)Mic、Linein或者其他輸入源的模擬信號(hào)進(jìn)行A/D轉(zhuǎn)換，把模擬的聲音信號(hào)轉(zhuǎn)變CPU能夠處理的數(shù)字信號(hào)

? 對(duì)音頻通路進(jìn)行控制，比如播放音樂，收聽調(diào)頻收音機(jī)，又或者接聽電話時(shí)，音頻信號(hào)在codec內(nèi)的流通路線是不一樣的

? 對(duì)音頻信號(hào)做出相應(yīng)的處理，例如音量控制，功率放大，EQ控制等等

ASoC對(duì)Codec的這些功能都定義好了一些列相應(yīng)的接口，以方便地對(duì)Codec進(jìn)行控制。ASoC對(duì)Codec驅(qū)動(dòng)的一個(gè)基本要求是：驅(qū)動(dòng)程序的代碼必須要做到平臺(tái)無關(guān)性，以方便同一個(gè)Codec的代碼不經(jīng)修改即可用在不同的平臺(tái)上。以下的討論基于wolfson的Codec芯片WM8994，kernel的版本3.3.x。

描述Codec的最主要的幾個(gè)數(shù)據(jù)結(jié)構(gòu)分別是：snd_soc_codec，snd_soc_codec_driver，snd_soc_dai，snd_soc_dai_driver，其中的snd_soc_dai和snd_soc_dai_driver在ASoC的Platform驅(qū)動(dòng)中也會(huì)使用到，Platform和Codec的DAI通過snd_soc_dai_link結(jié)構(gòu)，在Machine驅(qū)動(dòng)中進(jìn)行綁定連接。

Codec的注冊(cè)

因?yàn)镃odec驅(qū)動(dòng)的代碼要做到平臺(tái)無關(guān)性，要使得Machine驅(qū)動(dòng)能夠使用該Codec，Codec驅(qū)動(dòng)的首要任務(wù)就是確定snd_soc_codec和snd_soc_dai的實(shí)例，并把它們注冊(cè)到系統(tǒng)中，注冊(cè)后的codec和dai才能為Machine驅(qū)動(dòng)所用。以WM8994為例，對(duì)應(yīng)的代碼位置：/sound/soc/codecs/wm8994.c，模塊的入口函數(shù)注冊(cè)了一個(gè)platform driver：

[html] view plaincopy

1.static struct platform_driver wm8994_codec_driver = { 2..driver = { 3..name = “wm8994-codec”, //注意machine device里面和這里保持一致 4..owner = THIS_MODULE, 5.}, 6..probe = wm8994_probe, 7..remove = __devexit_p(wm8994_remove), 8.};9.10.module_platform_driver(wm8994_codec_driver);有platform driver，必定會(huì)有相應(yīng)的platform device，platform device其實(shí)在我們之前講過的machine device注冊(cè)時(shí)已經(jīng)引入了。

[html] view plaincopy

1.static int __devinit wm8994_probe(struct platform_device *pdev)2.{

3.return snd_soc_register_codec(&pdev->dev, &soc_codec_dev_wm8994, 4.wm8994_dai, ARRAY_SIZE(wm8994_dai));5.}

其中，soc_codec_dev_wm8994和wm8994_dai的定義如下（代碼中定義了3個(gè)dai，這里只列出第一個(gè)）：

[html] view plaincopy

1.static struct snd_soc_codec_driver soc_codec_dev_wm8994 = { 2..probe = wm8994_codec_probe, 3..remove = wm8994_codec_remove, 4..suspend = wm8994_suspend, 5..resume = wm8994_resume，6..set_bias_level = wm8994_set_bias_level, 7..reg_cache_size = WM8994_MAX_REGISTER, 8..volatile_register = wm8994_soc_volatile, 9.};

[html] view plaincopy

1.static struct snd_soc_dai_driver wm8994_dai[] = { 2.{

3..name = “wm8994-aif1”, 4..id = 1, 5..playback = {

6..stream_name = “AIF1 Playback”, 7..channels_min = 1, 8..channels_max = 2, 9..rates = WM8994_RATES, 10..formats = WM8994_FORMATS, 11.}，12..capture = {

13..stream_name = “AIF1 Capture”, 14..channels_min = 1, 15..channels_max = 2, 16..rates = WM8994_RATES, 17..formats = WM8994_FORMATS, 18.}，19..ops = &wm8994_aif1_dai_ops, 20.}, 21.......22.}

可見，Codec驅(qū)動(dòng)的第一個(gè)步驟就是定義snd_soc_codec_driver和snd_soc_dai_driver的實(shí)例，然后調(diào)用snd_soc_register_codec函數(shù)對(duì)Codec進(jìn)行注冊(cè)。

snd_soc_register_codec（）函數(shù)是machine driver提供的，只要注冊(cè)成功后codec提供的操作函數(shù)就能正常提供給machine driver使用了。int snd_soc_register_codec(struct device *dev，const struct snd_soc_codec_driver *codec_drv, struct snd_soc_dai_driver *dai_drv, int num_dai){ codec = kzalloc(sizeof(struct snd_soc_codec), GFP_KERNEL)。。。。。。

/* create CODEC component name */ codec->name = fmt_single_name(dev, &codec->id);/*Machine驅(qū)動(dòng)定義的snd_soc_dai_link中會(huì)指定每個(gè)link的codec和dai的名字，進(jìn)行匹配綁定時(shí)就是通過和這里的名字比較，從而找到該Codec的 */

// 然后初始化它的各個(gè)字段，多數(shù)字段的值來自上面定義的snd_soc_codec_driver的實(shí)例soc_codec_dev_wm8994： codec->write = codec_drv->write;codec->read = codec_drv->read;codec->volatile_register = codec_drv->volatile_register;codec->readable_register = codec_drv->readable_register;codec->writable_register = codec_drv->writable_register;codec->dapm.bias_level = SND_SOC_BIAS_OFF;codec->dapm.dev = dev;codec->dapm.codec = codec;codec->dapm.seq_notifier = codec_drv->seq_notifier;codec->dev = dev;codec->driver = codec_drv;codec->num_dai = num_dai;mutex_init(&codec->mutex);

/* allocate CODEC register cache */ if(codec_drv->reg_cache_size && codec_drv->reg_word_size){ reg_size = codec_drv->reg_cache_size * codec_drv->reg_word_size;codec->reg_size = reg_size;/* it is necessary to make a copy of the default register cache

* because in the case of using a compression type that requires

* the default register cache to be marked as __devinitconst the

* kernel might have freed the array by the time we initialize

* the cache.*/ if(codec_drv->reg_cache_default){ codec->reg_def_copy = kmemdup(codec_drv->reg_cache_default，reg_size, GFP_KERNEL);if(!codec->reg_def_copy){ ret =-ENOMEM;goto fail;} } }

。。。。。。/* register any DAIs */ if(num_dai){ ret = snd_soc_register_dais(dev, dai_drv, num_dai);//通過snd_soc_register_dais函數(shù)對(duì)本Codec的dai進(jìn)行注冊(cè) if(ret < 0)goto fail;}

mutex_lock(&client_mutex);list_add(&codec->list, &codec_list);/*最后，它把codec實(shí)例鏈接到全局鏈表codec_list中，并且調(diào)用snd_soc_instantiate_cards是函數(shù)觸發(fā)Machine驅(qū)動(dòng)進(jìn)行一次匹配綁定操作 */

snd_soc_instantiate_cards();mutex_unlock(&client_mutex)。。。。。}

好了，在這里我們的codec驅(qū)動(dòng)也分析完了，其實(shí)這部分都是與平臺(tái)無關(guān)代碼，一般也不需要改動(dòng)，這部分我們從設(shè)備原廠拿到代碼后丟上去就可以了，只是我們?cè)趯憁achine device的時(shí)候要注意和這里的名字匹配。接下來是asoc的platform驅(qū)動(dòng)：

Platform驅(qū)動(dòng)的主要作用是完成音頻數(shù)據(jù)的管理，最終通過CPU的數(shù)字音頻接口（DAI）把音頻數(shù)據(jù)傳送給Codec進(jìn)行處理，最終由Codec輸出驅(qū)動(dòng)耳機(jī)或者是喇叭的音信信號(hào)。在具體實(shí)現(xiàn)上，ASoC有把Platform驅(qū)動(dòng)分為兩個(gè)部分：snd_soc_platform_driver和snd_soc_dai_driver。其中，platform_driver負(fù)責(zé)管理音頻數(shù)據(jù)，把音頻數(shù)據(jù)通過dma或其他操作傳送至cpu dai中，dai_driver則主要完成cpu一側(cè)的dai的參數(shù)配置，同時(shí)也會(huì)通過一定的途徑把必要的dma等參數(shù)與snd_soc_platform_driver進(jìn)行交互。

snd_soc_platform_driver的注冊(cè)

通常，ASoC把snd_soc_platform_driver注冊(cè)為一個(gè)系統(tǒng)的platform_driver，不要被這兩個(gè)想像的術(shù)語所迷惑，前者只是針對(duì)ASoC子系統(tǒng)的，后者是來自Linux的設(shè)備驅(qū)動(dòng)模型。我們要做的就是：

? ? 定義一個(gè)snd_soc_platform_driver結(jié)構(gòu)的實(shí)例；

在platform_driver的probe回調(diào)中利用ASoC的API：snd_soc_register_platform()注冊(cè)上面定義的實(shí)例；

? 實(shí)現(xiàn)snd_soc_platform_driver中的各個(gè)回調(diào)函數(shù)；

以kernel3.3中的/sound/soc/samsung/dma.c為例：

[cpp] view plaincopy

1.static struct snd_soc_platform_driver samsung_asoc_platform = { 2..ops = &dma_ops, 3..pcm_new = dma_new, 4..pcm_free = dma_free_dma_buffers, 5.};6.7.static int __devinit samsung_asoc_platform_probe(struct platform_device *pdev)8.{ 9.return snd_soc_register_platform(&pdev->dev, &samsung_asoc_platform);10.} 11.12.static int __devexit samsung_asoc_platform_remove(struct platform_device *pdev)13.{ 14.snd_soc_unregister_platform(&pdev->dev);15.return 0;16.} 17.18.static struct platform_driver asoc_dma_driver = { 19..driver = { 20..name = “samsung-audio”, 21..owner = THIS_MODULE, 22.}, 23.24..probe = samsung_asoc_platform_probe, 25..remove = __devexit_p(samsung_asoc_platform_remove), 26.};27.28.module_platform_driver(asoc_dma_driver);snd_soc_register_platform()該函數(shù)用于注冊(cè)一個(gè)snd_soc_platform，只有注冊(cè)以后，它才可以被Machine驅(qū)動(dòng)使用。它的代碼已經(jīng)清晰地表達(dá)了它的實(shí)現(xiàn)過程：

? ? ? ? ? 為snd_soc_platform實(shí)例申請(qǐng)內(nèi)存；

從platform_device中獲得它的名字，用于Machine驅(qū)動(dòng)的匹配工作； 初始化snd_soc_platform的字段；

把snd_soc_platform實(shí)例連接到全局鏈表platform_list中；

調(diào)用snd_soc_instantiate_cards，觸發(fā)聲卡的machine、platform、codec、dai等的匹配工作；

cpu的snd_soc_dai driver驅(qū)動(dòng)的注冊(cè)

dai驅(qū)動(dòng)通常對(duì)應(yīng)cpu的一個(gè)或幾個(gè)I2S/PCM接口，與snd_soc_platform一樣，dai驅(qū)動(dòng)也是實(shí)現(xiàn)為一個(gè)platform driver，實(shí)現(xiàn)一個(gè)dai驅(qū)動(dòng)大致可以分為以下幾個(gè)步驟：

? ? 定義一個(gè)snd_soc_dai_driver結(jié)構(gòu)的實(shí)例；

在對(duì)應(yīng)的platform_driver中的probe回調(diào)中通過API：snd_soc_register_dai或者snd_soc_register_dais，注冊(cè)snd_soc_dai實(shí)例；

? ? 實(shí)現(xiàn)snd_soc_dai_driver結(jié)構(gòu)中的probe、suspend等回調(diào)；

實(shí)現(xiàn)snd_soc_dai_driver結(jié)構(gòu)中的snd_soc_dai_ops字段中的回調(diào)函數(shù)；

snd_soc_register_dai 這個(gè)函數(shù)在上一篇介紹codec驅(qū)動(dòng)的博文中已有介紹

具體不再分析，這個(gè)驅(qū)動(dòng)也不需要用戶做任務(wù)修改，所以只要知道它的作用就已經(jīng)夠了。就像電話機(jī)一樣，我們只要知道電話怎么打就夠了，至于它怎么連接我們并不太需要關(guān)心。

第五篇：算法總結(jié)

算法分析與設(shè)計(jì)總結(jié)報(bào)告

71110415 錢玉明

在計(jì)算機(jī)軟件專業(yè)中，算法分析與設(shè)計(jì)是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(shù)據(jù)結(jié)構(gòu)這個(gè)公式。算法的學(xué)習(xí)對(duì)于培養(yǎng)一個(gè)人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問題，解決問題的能力。作為IT行業(yè)學(xué)生，學(xué)習(xí)算法無疑會(huì)增強(qiáng)自己的競爭力，修煉自己的“內(nèi)功”。

下面我將談?wù)勎覍?duì)這門課程的心得與體會(huì)。

一、數(shù)學(xué)是算法的基礎(chǔ)

經(jīng)過這門課的學(xué)習(xí)，我深刻的領(lǐng)悟到數(shù)學(xué)是一切算法分析與設(shè)計(jì)的基礎(chǔ)。這門課的很多時(shí)間多花在了數(shù)學(xué)公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數(shù)學(xué)息息相關(guān)。其中有幾個(gè)定理令我印象深刻。

①主定理

本門課中它主要應(yīng)用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一個(gè)大問題分解為a個(gè)子問題，其中子問題的規(guī)模為b。而f(n)可看作這些子問題的組合時(shí)的消耗。這些可以利用主定理的相關(guān)結(jié)論進(jìn)行分析處理。當(dāng)f(n)量級(jí)高于nlogba時(shí)，我們可以設(shè)法降低子問題組合時(shí)的消耗來提高性能。反之我們可以降低nlogba的消耗，即可以擴(kuò)大問題的規(guī)模或者減小子問題的個(gè)數(shù)。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進(jìn)行有效的改進(jìn)。

②隨機(jī)算法中的許多定理的運(yùn)用

在這門課中，我學(xué)到了以前從未遇見過的隨機(jī)算法，它給予我很大的啟示。隨機(jī)算法不隨機(jī)，它可通過多次的嘗試來降低它的錯(cuò)誤率以至于可以忽略不計(jì)。這些都不是空穴來風(fēng)，它是建立在嚴(yán)格的定理的證明上。如素?cái)?shù)判定定理是個(gè)很明顯的例子。它運(yùn)用了包括費(fèi)馬小定理在內(nèi)的各種定理。將這些定理進(jìn)行有效的組合利用，才得出行之有效的素?cái)?shù)判定的定理。尤其是對(duì)尋找證據(jù)數(shù)算法的改進(jìn)的依據(jù)，也是建立在3個(gè)定理上。還有檢查字符串是否匹配也是運(yùn)用了許多定理：指紋的運(yùn)用，理論出錯(cuò)率的計(jì)算，算法性能的評(píng)價(jià)也都是建立在數(shù)學(xué)定理的運(yùn)用上。

這些算法都給予了我很大啟發(fā)，要想學(xué)好算法，學(xué)好數(shù)學(xué)是必不可少的。沒有深厚的數(shù)學(xué)功力作為地基，即使再漂亮的算法框架，代碼實(shí)現(xiàn)也只能是根底淺的墻上蘆葦。

二、算法的核心是思想

我們學(xué)習(xí)這門課不是僅僅掌握那幾個(gè)經(jīng)典算法例子，更重要的是為了學(xué)習(xí)蘊(yùn)含在其中的思想方法。為什么呢？舉個(gè)例子。有同學(xué)曾問我這樣一個(gè)問題：1000只瓶子裝滿水，但有一瓶有毒，且毒發(fā)期為1個(gè)星期?，F(xiàn)在用10只老鼠在一個(gè)星期內(nèi)判斷那只瓶子有毒，每只老鼠可以喝多個(gè)瓶子的水，每個(gè)瓶子可以只喝一點(diǎn)。問如何解決？其實(shí)一開始我也一頭霧水，但是他提醒我跟計(jì)算機(jī)領(lǐng)域相關(guān)，我就立馬有了思路，運(yùn)用二進(jìn)制。因?yàn)橛?jì)算機(jī)的最基本思想就是二進(jìn)制。所以說，我們不僅要學(xué)習(xí)算法，更得學(xué)習(xí)思想方法。

①算法最基本的設(shè)計(jì)方法包括分治法，動(dòng)態(tài)規(guī)劃法，貪心法，周游法，回溯法，分支定界法。我們可利用分治法做快速排序，降低找n個(gè)元素中最大元和最小元的量級(jí)，降低n位二進(jìn)制x和y相乘的量級(jí)，做Strassen矩陣乘法等等。它的思想就是規(guī)模很大的問題分解為規(guī)模較小的獨(dú)立的子問題，關(guān)鍵是子問題要與原問題同類，可以采取平衡法來提高性能。

動(dòng)態(tài)規(guī)劃法是把大問題分解為子問題，但是子問題是重復(fù)的，后面的問題可以利用前面解決過的問題的結(jié)果。如構(gòu)造最優(yōu)二叉查找樹，解決矩陣連乘時(shí)最小計(jì)算次數(shù)問題，尋找最長公共子序列等等。

貪心法就是局部最優(yōu)法，先使局部最優(yōu)，再依次構(gòu)造出更大的局部直至整體。如Kruscal最小生成樹算法，求哈夫曼編碼問題。

周游法就是簡單理解就是采取一定的策略遍歷圖中所有的點(diǎn)，典型的應(yīng)用就是圖中的深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。

回溯法就是就是在滿足一定的條件后就往前走，當(dāng)走到某步時(shí)，發(fā)現(xiàn)不滿足條件就退回一步重新選擇新的路線。典型的應(yīng)用就是8皇后問題，平面點(diǎn)集的凸包問題和0-1背包問題。

分支定界法：它是解決整數(shù)規(guī)劃問題一種最常用的方法。典型應(yīng)用就是解決整數(shù)規(guī)劃問題。

②評(píng)價(jià)算法性能的方法如平攤分析中的聚集法，會(huì)計(jì)法和勢能法。聚集法就是把指令分為幾類，計(jì)算每一類的消耗，再全部疊加起來。會(huì)計(jì)法就是計(jì)算某個(gè)指令時(shí)提前將另一個(gè)指令的消耗也算進(jìn)去，以后計(jì)算另一個(gè)指令時(shí)就不必再算了。勢能法計(jì)算每一步的勢的變化以及執(zhí)行這步指令的消耗，再將每一步消耗全部累計(jì)。

這幾種方法都是平攤分析法，平攤分析的實(shí)質(zhì)就是總體考慮指令的消耗時(shí)間，盡管某些指令的消耗時(shí)間很大也可以忽略不計(jì)。上述三種方法難易程度差不多，每種方法都有屬于它的難點(diǎn)。如聚集法中如何將指令有效分類，會(huì)計(jì)法中用什么指令提前計(jì)算什么指令的消耗，勢能法中如何選取勢能。因此掌握這些方法原理還不夠，還要學(xué)會(huì)去應(yīng)用，在具體的問題中去判斷分析。

三、算法與應(yīng)用緊密相關(guān)

我認(rèn)為學(xué)習(xí)算法不能局限于書本上的理論運(yùn)算，局限于如何提高性能以降低復(fù)雜度，我們要將它與實(shí)際生活聯(lián)系起來。其實(shí)算法問題的產(chǎn)生就來自于生活，設(shè)計(jì)出高效的算法就是為了更好的應(yīng)用。如尋找最長公共子序列算法可以應(yīng)用在生物信息學(xué)中通過檢測相似DNA片段的相似成分來檢測生物特性的相似性，也可以用來判斷兩個(gè)字符串的相近性，這可應(yīng)用在數(shù)據(jù)挖掘中?？焖俑盗⑷~變換（FFT）可應(yīng)用在計(jì)算多項(xiàng)式相乘上來降低復(fù)雜度，脫線min算法就是利用了Union-Find這種結(jié)構(gòu)。還有圖中相關(guān)算法，它對(duì)于解決網(wǎng)絡(luò)流量分配問題起了很大的幫助，等等。

這些應(yīng)用給了我很大的啟發(fā)：因?yàn)閱渭冎v一個(gè)Union-Find算法，即使了解了它的實(shí)現(xiàn)原理，遇到具體的實(shí)際問題也不知去如何應(yīng)用。這就要求我們要將自己學(xué)到的算法要和實(shí)際問題結(jié)合起來，不能停留在思想方法階段，要學(xué)以致用，做到具體問題具體分析。

四、對(duì)計(jì)算模型和NP問題的理解

由于對(duì)這部分內(nèi)容不是很理解，所以就粗淺的談一下我的看法。

首先談到計(jì)算模型，就不得不提到圖靈計(jì)算，他將基本的計(jì)算抽象化，造出一個(gè)圖靈機(jī)，得出了計(jì)算的本質(zhì)。并提出圖靈機(jī)可以計(jì)算的問題都是可以計(jì)算的，否則就是不可計(jì)算的。由此引申出一個(gè)著名論題：任何合理的計(jì)算模型都是相互等價(jià)的。它說明了可計(jì)算性本身不依賴于任何具體的模型而客觀存在。

NP問題比較復(fù)雜，我認(rèn)為它是制約算法發(fā)展的瓶頸，但這也是算法分析的魅力所在。NP問題一般可分為3類，NP-C問題，NP-hard問題以及頑型問題。NP-C它有個(gè)特殊的性質(zhì)，如果存在一個(gè)NP-C問題找到一個(gè)多項(xiàng)式時(shí)間的解法，則所有的NP-C問題都能找到多項(xiàng)式時(shí)間解法。如哈密頓回路問題。NP-hard主要是解決最優(yōu)化問題。它不一定是NP問題。這些問題在規(guī)模較小時(shí)可以找出精確解，但是規(guī)模大時(shí)，就因時(shí)間太復(fù)雜而找不到最優(yōu)解。此時(shí)一般會(huì)采用近似算法的解法。頑型問題就是已經(jīng)證明不可能有多項(xiàng)式時(shí)間的算法，如漢諾塔問題。

最后談?wù)剬?duì)這門課程的建議

①對(duì)于這門算法課，我認(rèn)為應(yīng)該加強(qiáng)對(duì)算法思想方法的學(xué)習(xí)。所以我建議老師可不可以先拋出問題而不給出答案，講完一章，再發(fā)課件。讓我們先思考一會(huì)兒，或者給出個(gè)獎(jiǎng)勵(lì)機(jī)制，誰能解決這個(gè)問題，平時(shí)成績加分。這在一定程度上會(huì)將強(qiáng)我們思考分析問題的能力。因?yàn)槲腋杏X到，一個(gè)問題出來，未經(jīng)過思考就已經(jīng)知曉它的答案，就沒什么意思，得不到提高，而且也不能加深對(duì)問題的思考和理解。下次遇到類似的問題也就沒有什么印象。而且上課讓我們思考，點(diǎn)名回答問題可以一定程度上有效的防止不認(rèn)真聽課的現(xiàn)象。

②作業(yè)安排的不是很恰當(dāng)。本門課主要安排了三次作業(yè)，個(gè)人感覺只有第一次作業(yè)比較有意思。后面兩次作業(yè)只是實(shí)現(xiàn)一下偽代碼，沒有太多的技術(shù)含量。而且對(duì)于培養(yǎng)我們的解決問題的能力也沒有太多的幫助，因?yàn)檫@間接成為了程序設(shè)計(jì)題，不是算法設(shè)計(jì)題。

③本門課的時(shí)間安排的不太恰當(dāng)，因?yàn)楸緦W(xué)期的課程太多，壓力太大。沒有太多的時(shí)間去學(xué)習(xí)這門課程。因?yàn)槲蚁嘈糯蠹叶紝?duì)它感興趣，比較重視，想花功夫，但苦于沒時(shí)間。所以可不可以將課程提前一個(gè)學(xué)期，那時(shí)候離散數(shù)學(xué)也已經(jīng)學(xué)過，且課程的壓力也不是很大。錯(cuò)開時(shí)間的話，我覺得應(yīng)該能夠更好提高大家算法分析設(shè)計(jì)的能力。