一個(gè)借助查詢歷史改善結(jié)果排序的文件檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)碩士畢業(yè)論文

《一個(gè)借助查詢歷史改善結(jié)果排序的文件檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)碩士畢業(yè)論文》由會(huì)員分享，可在線閱讀，更多相關(guān)《一個(gè)借助查詢歷史改善結(jié)果排序的文件檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)碩士畢業(yè)論文（60頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、北京大學(xué)碩士研究生學(xué)位論文題目：一個(gè)借助查詢歷史改善結(jié)果排序的文件檢索系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)姓 名： 學(xué) 號(hào)： 院 系：信息科學(xué)技術(shù)學(xué)院專 業(yè)：計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)研究方向：計(jì)算機(jī)網(wǎng)絡(luò)與分布式系統(tǒng)導(dǎo) 師： 1版權(quán)聲明版權(quán)聲明任何收存和保管本論文各種版本的單位和個(gè)人，未經(jīng)本論文作者同意，不得將本論文轉(zhuǎn)借他人，亦不得隨意復(fù)制、抄錄、拍照或以任何方式傳播。否則，引起有礙作者著作權(quán)之問(wèn)題，將可能承擔(dān)法律責(zé)任。 2摘摘 要要隨著網(wǎng)絡(luò)的發(fā)展，網(wǎng)絡(luò)上提供文件共享服務(wù)的服務(wù)器越來(lái)越多，共享的文件數(shù)量也隨之增加。如何更好的檢索、利用這些共享文件成為一個(gè)重要的問(wèn)題。針對(duì)用戶對(duì)文件檢索的需求，本文在文件檢索技術(shù)領(lǐng)域有如下貢獻(xiàn)。

2、1. 本文首先提出了一個(gè)文件檢索的模型，明確了在文件檢索模型中檢索對(duì)象、查詢串、查詢與檢索對(duì)象的匹配方式三部分的含義。檢索對(duì)象，即文件條目表示為六元組name, ext, size, date, site, path的形式，查詢串表示為以空格分隔的字符串的集合，查詢與檢索對(duì)象的匹配則表示為查詢串與文件條目的匹配串之間的匹配。2. 提出了對(duì)文件檢索系統(tǒng)進(jìn)行評(píng)測(cè)的指標(biāo)。將查詢結(jié)果視作集合時(shí)以查全率、查準(zhǔn)率為評(píng)測(cè)指標(biāo)。將查詢結(jié)果視作有序序列時(shí)，分析了查詢結(jié)果的相關(guān)性、連接下載速度以及結(jié)果的可用性等因素對(duì)排序的影響，并提出了對(duì)排序進(jìn)行評(píng)測(cè)的指標(biāo)排序指數(shù)。作者還提出對(duì)于兩個(gè)排序策略進(jìn)行比較時(shí)，應(yīng)當(dāng)在結(jié)果

3、的每個(gè)頁(yè)面內(nèi)部應(yīng)用排序策略，而不是在全體結(jié)果集合上應(yīng)用排序策略，并比較平均用戶選取條目的頁(yè)內(nèi)排名。3. 通過(guò)統(tǒng)計(jì)、分析用戶對(duì)文件搜索引擎的檢索和對(duì)檢索結(jié)果中下載地址條目的選取，作者發(fā)現(xiàn)了用戶行為習(xí)慣中的兩個(gè)重要規(guī)律：一、少數(shù)查詢串占據(jù)了全部查詢請(qǐng)求的大多數(shù)，具體而言，前 20%的熱門查詢串占據(jù)了全部查詢請(qǐng)求的80%；二、對(duì)全體用戶而言，假設(shè)有 n 次不同的查詢請(qǐng)求使用了同一個(gè)查詢串，并且它們代表 k 類不同的查詢意圖。那么通常 k3，因而在 n 較大的情況下，則 n/k 的值較大，即大量的來(lái)自不同用戶的請(qǐng)求代表了相同的查詢意圖。4. 基于上文所述，作者設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)真實(shí)的系統(tǒng)。該系統(tǒng)借助查詢

4、歷史改善結(jié)果的排序。與一般基于用戶歷史信息的檢索系統(tǒng)不同的是，本系統(tǒng)借助的歷史信息不局限于當(dāng)前用戶的歷史信息，還包含提交了相同查詢串的其他用戶的查詢信息?；蛘哒f(shuō)，即使當(dāng)前用戶是第一次使用本系統(tǒng)，本系統(tǒng)也能利用其他用戶的歷史記錄來(lái)改進(jìn)結(jié)果的排序和篩選。作者最后還驗(yàn)證了其實(shí)際的效果。應(yīng)用本方法后，平均用戶選取條目的頁(yè)內(nèi)排名從原來(lái)的13.70 名前進(jìn)到了 8.93 名。試驗(yàn)結(jié)果表明文中所做的分析是正確的。關(guān)鍵詞：文件檢索系統(tǒng)，查詢歷史，檢索模型 3The Design and Implementation of a File Index System which Improve the Order

5、by Query History AbstractWith the rapid expansion of the Internet, there are more sharing file servers. And the number of sharing files is increasing rapidly too. So its more important to retrieve these files easily.For the requirement of file retrieving of the users, we did the following jobs:1. We

6、 proposed a file index model. The model is composed of the expression of an index object, the expression of a query, and how the query word matches the index object. The index object can be expressed as name, ext, size, date, site, path, the query string is expressed as strings separated by space, a

7、nd the matching between query and index object is realized by matching the query string and the matching strings of the file item.2. We also proposed the evaluation indicator for the file index evaluation. The precision and recall are useful when we evaluate the query result. But the result is not a

8、 set, but an ordered list. So we indicated the factors in order: the relativity of the item, the connecting and download speed and the availability of the site. We proposed how to evaluate the order: average rank of chosen items. If we just want to compare two ranking strategy, we should not reorder

9、 all items in the result set but only reorder the items within each page and compare the average rank of chosen items within page.3. By analyzing the records of users queries and the file items that users chosen from a real file search engine, we discovered two lows. 1). Most query strings are repea

10、ting hot query strings. 80% query words are the top 20% hot query strings. 2) If there are n times of queries using the same query strings, and the total number of different intensions is k. Then k should be a very small number (usually, k5對(duì)應(yīng)的查詢串的個(gè)數(shù)3315781010從上表可見(jiàn)，查詢意圖只有 13 個(gè)的查詢串占全部記錄數(shù)據(jù)的絕大部分，超過(guò) 5 種不

11、同意圖的查詢串在統(tǒng)計(jì)的日志中根本就沒(méi)有出現(xiàn)。我們?cè)賮?lái)看一下 n 和 k 的比例的分布，統(tǒng)計(jì)結(jié)果如下圖。圖中橫坐標(biāo)表示查詢串被查詢的次數(shù) n，綜坐標(biāo)為 n/k 的比值。要說(shuō)明一點(diǎn)就是為了使圖像中的點(diǎn)線顯示清晰，我們忽略了很少量的查詢次數(shù)非常高的詞（這些點(diǎn)對(duì)應(yīng)的橫坐標(biāo)值非常大），但事后的手工驗(yàn)證仍然證明了它們符合本文的規(guī)律。 26110100100001002003004005006007008009001000圖 4-3 查詢串與查詢意圖種類比值分析其中橫坐標(biāo)為查詢串查詢次數(shù) n，綜坐標(biāo)為 n/k 比值（為指數(shù)標(biāo)度）從圖中可以看到，當(dāng) n100 時(shí)，n/k 的值都在 30 以上。由上面的分析我們

12、能夠知道，盡管查詢串不同，但一般說(shuō)來(lái)，它們所代表的查詢意圖的數(shù)量并不是太多的，通常在1-3 種，并且在 n 較大的情況下（如n100），通常 n/k 的比值較大（本例中大于 30）。因此我們得到了第二個(gè)重要的規(guī)律：規(guī)規(guī)律律二二：假假設(shè)設(shè)有有 n 次次不不同同的的請(qǐng)請(qǐng)求求查查詢?cè)兞肆送灰粋€(gè)個(gè)查查詢?cè)兇?，并并且且它它們們代代表表k 種種不不同同的的查查詢?cè)円庖鈭D圖。在在 n 較較大大的的情情況況下下（ n100），n/k 的的值值較較大大（ n/k30）。4.3用戶行為特點(diǎn)的啟發(fā)利用上面的用戶行為特點(diǎn)中的兩個(gè)規(guī)律，以及前面關(guān)于相關(guān)反饋方法的思路，可以考慮采用如下思路來(lái)實(shí)現(xiàn)一個(gè)借助查詢歷史信息

13、改善結(jié)果排序的文件檢索系統(tǒng)。從上面的特征我們知道，大多數(shù)的查詢請(qǐng)求不僅其查詢串本身是重復(fù)的，而且其所代表的查詢意圖也是重復(fù)的。這樣我們就可以由“較早的相同的查詢串的結(jié)果選取記錄”作為用戶的反饋信號(hào)。這樣一來(lái)，后來(lái)提交同樣查詢串的用戶不需要 27任何主動(dòng)干預(yù)，就可以得到經(jīng)過(guò)反饋信號(hào)處理過(guò)的重新排序的查詢結(jié)果了。當(dāng)然，由于用戶意圖并不唯一，我們并不能確定究竟本次查詢的用戶是哪種查詢意圖，但因?yàn)?k 值通常都相當(dāng)?。ㄐ∮诘扔?3），因此對(duì)用戶而言，很容易從這為數(shù)極少的查詢意圖中找到滿足自己意圖的結(jié)果。具體而言，我們可以考慮如下的思路。首先記錄下每次用戶對(duì)查詢結(jié)果的選取。我們認(rèn)為，用戶在查詢結(jié)果中點(diǎn)擊

14、的下載地址，就是用戶認(rèn)為比較理想的下載地址。通過(guò)一段時(shí)間的記錄，我們就得到了對(duì)于大量查詢串的較理想的匹配結(jié)果。對(duì)于一個(gè)查詢串q，我們有一個(gè)用戶認(rèn)為較好的文件條目的集合 S，我們將其表示為一個(gè)二元組 (q,S)。這樣，我們就得到了大量的這樣的二元組。依據(jù)規(guī)律 2，我們知道每個(gè)查詢串可能代表幾個(gè)不同的查詢意圖，那么不同的查詢意圖對(duì)應(yīng)的理想下載地址肯定不同（否則就是相同的查詢意圖了），我們可以采用聚類的方法對(duì)每個(gè) S 中的文件條目進(jìn)行聚類。聚類后，對(duì)于每個(gè)q，我們會(huì)得到 k 種不同的類別，這 k 個(gè)類別就也就反映了不同的查詢意圖，而每個(gè)類別中的文件條目，就可以看作這個(gè)類別的訓(xùn)練集。每個(gè)類別中的條目個(gè)

15、數(shù)，也直接反映了這個(gè)類別的權(quán)重。當(dāng)再次有用戶查詢同樣的查詢串 q 時(shí)，我們首先采用原始的檢索方法，得到一個(gè)結(jié)果集合，然后用聚類得到的 k 個(gè)類別和訓(xùn)練集對(duì)其進(jìn)行分類處理。一些條目被分到這 k 個(gè)類別中，另外一些可能不屬于任何類別。不屬于任何類別的條目往往也是用戶不太需要的條目，可以考慮拋棄或排在結(jié)果的最后輸出。 28第5章 系統(tǒng)體系結(jié)構(gòu)與主要算法5.1系統(tǒng)體系結(jié)構(gòu)基于以上分析，我們?cè)O(shè)計(jì)了如下的檢索系統(tǒng)來(lái)改善文件檢索系統(tǒng)的排序。Query String (q)Normal Index System (I)Index Result (S0)Feedback data DataBaseSite Li

16、st DataBasequeryClusteringThe training set for query item qItems not belong to any groupResult after Categorization (S)Categorization, OrderingFileitems that user clicked圖 5-1 系統(tǒng)結(jié)構(gòu)圖下面我們來(lái)詳細(xì)介紹這個(gè)模型。我們首先查看模型中的各個(gè)組成部分。Query String (q)：用戶輸入的查詢串；Normal Index System(I)：常規(guī)的文件檢索系統(tǒng)；Index Result(S0)：初始查詢結(jié)果集；Feed

17、back Data DB(F)：該數(shù)據(jù)庫(kù)中記錄了已有的每個(gè)查詢請(qǐng)求和它對(duì)應(yīng)的不同的 k 種查詢意圖，以及每種意圖的作為訓(xùn)練集的文件條目。Fileitem DB(D)：該數(shù)據(jù)庫(kù)中保存了每次用戶進(jìn)行檢索后對(duì)查詢結(jié)果的選取情況。具體而言，當(dāng)用戶進(jìn)行查詢后，檢索系統(tǒng)返回結(jié)果，當(dāng)用戶在結(jié)果頁(yè)面中對(duì)文件條目進(jìn)行點(diǎn)擊并下載時(shí)，本模型會(huì)記錄用戶的點(diǎn)擊選取行為。庫(kù)中的每條記錄含有當(dāng)前的查詢串和用戶點(diǎn)擊的這條記錄的具體文件信息：文件名稱、擴(kuò)展名稱、最后修改日期、文件大小、文件所在站點(diǎn)和文件所在的路徑。 29本檢索系統(tǒng)的工作流程如下：數(shù)據(jù)庫(kù) F 中需要足夠的數(shù)據(jù)記錄系統(tǒng)才能夠進(jìn)行工作。因此在系統(tǒng)運(yùn)行之初，系統(tǒng)便開始

18、自動(dòng)記錄用戶的點(diǎn)擊，并將記錄填充進(jìn)數(shù)據(jù)庫(kù)D。數(shù)據(jù)庫(kù) D 每隔一段時(shí)間，對(duì)每個(gè)查詢串 q 進(jìn)行一次聚類操作，這樣便得到了每個(gè)查詢串所代表的k種查詢意圖?，F(xiàn)在我們假設(shè) F 中已經(jīng)包含有了足夠的記錄信息。當(dāng)用戶輸入查詢串q 后，一方面，模型中最上面的流程開始工作，常規(guī)的檢索系統(tǒng)進(jìn)行檢索，得到一個(gè)原始的查詢結(jié)果 S0。另一方面，如模型圖示中的中層的流程， q 被送入數(shù)據(jù)庫(kù) F。數(shù)據(jù)庫(kù) F 返回對(duì)應(yīng)的 k 種意圖和其點(diǎn)擊記錄集合。這些記錄將作為下一步分類工作的訓(xùn)練集。有了 S0和這 k 種類別，下面將利用這 k 種類別的訓(xùn)練集對(duì) S0進(jìn)行分類。分類后我們將 S0分成了 k+1 類，其中新增加的這個(gè)類別是

19、那些不屬于任何類別的文件條目 item 集合。對(duì)于不屬于任何類別的條目，我們認(rèn)為它是用戶不太關(guān)心的結(jié)果，可以把它拋棄或放入輸出結(jié)果的最后。這里有一點(diǎn)要注意，就是 k 種類別的地位是不同的，類別本身也是有權(quán)重的，權(quán)重可以由聚類時(shí)每個(gè)類別中的條目數(shù)量來(lái)決定。這樣在最后輸出時(shí)可以按照權(quán)重本身對(duì)類別進(jìn)行排序。由于 k 的取值通常都比較?。ㄐ∮诘扔?3），用戶最終看到的結(jié)果往往是接近用戶的真實(shí)查詢意圖的。然后就可以按照一般的條目列表方式或者聚類的樹型結(jié)構(gòu)將結(jié)果輸出給最終用戶。5.2主要算法5.2.1 用戶點(diǎn)擊日志的表示用戶點(diǎn)擊日志就是用戶所點(diǎn)擊的文件條目item。由前面的對(duì)文件檢索的建模，我們知道可以表

20、示為：item = name, ext, size, date, site, path我們將其改寫為如下格式：pathsitedatesizeextnamexxxxxx有時(shí)候?yàn)榱撕?jiǎn)便，我們也會(huì)表述為如下形式： 30654321xxxxxx對(duì)于查詢串 q，價(jià)格共有 n 個(gè)記錄，因此我們得到如下的矩陣：1,11,21,31,41,51,6,1,2,3,4,5,6,1,2,3,4,5,6.iiiiiinnnnnnxxxxxxxxxxxxxxxxxx5.2.2 計(jì)算文件條目之間的距離不論是進(jìn)行聚類處理還是進(jìn)行分類處理，都需要進(jìn)行大量的對(duì)兩個(gè)文件條目(item)之間的距離 d 的計(jì)算。或者說(shuō)，需要通過(guò)上

21、文中的二模矩陣，得到下面的表示條目之間距離的單模矩陣：0(2,1)0(3,1)(3,2)0(4,1)(4,2)(4,3)0(5,1)(5,2)(5,3)(5,4)0(6,1)(6,2)(6,3)(6,4)(6,5)0(7,1)(7,2)(7,3)(7,4)(7,5)(7,6)0.0( ,1)( ,2)( ,3)( ,4)( ,5)( ,6).( ,dddddddddddddddddddddd nd nd nd nd nd nd n n1)0圖中我們用 d(i,j)表示項(xiàng) xi和 xj之間的距離，有 d(i,j)0。當(dāng) d(i,j)=0 時(shí)表示二者完全相同；當(dāng) d(i,j)0 時(shí)表示二者不同，并

22、且 d 的值越大表示文件條目 xi和 xj之間的差異越大。對(duì)于條目 i 和 j 之間距離的 d(i,j)的計(jì)算，我們采用如下加權(quán)公式： 31(,)11( ,)ifjfpxxffpfdfd x xijf由前文文件檢索模型可知，此處 p=6。我們分別計(jì)算文件條目 i 和 j 的 6 項(xiàng)對(duì)應(yīng)屬性的距離，再進(jìn)行加權(quán)求和最后再進(jìn)行標(biāo)準(zhǔn)化處理。由于文件條目的 6 項(xiàng)屬性的數(shù)據(jù)類型和含義不完全相同，因此具體的計(jì)算方法區(qū)別較大，在計(jì)算時(shí)需要分別考慮。下圖為各個(gè)屬性的數(shù)據(jù)類型和計(jì)算方法。表格 5-1 文件條目各個(gè)屬性數(shù)據(jù)類型屬屬性性數(shù)數(shù)據(jù)據(jù)類類型型距距離離計(jì)計(jì)算算方方法法nameStringMinimal ed

23、it distanceextStringNominal VariablessizeIntegerInterval-scaled variablesdateIntegerInterval-scaled variablessiteStringN/ApathStringSubsection string具體方法為：5.2.2.1name 屬性距離的計(jì)算方法name 表示文件的不包含擴(kuò)展名的主名的名稱，數(shù)據(jù)類型為字符串型。對(duì)于這種字符串類型數(shù)據(jù)的處理，一般情況下可以按照文檔的相似度的方式進(jìn)行。但由于文件名通常都比較短小，命名多數(shù)情況下也不規(guī)范。這里并不建議按照文檔的形式來(lái)處理。我們這里采用的處理方法是

24、按照最小編輯距離的方法來(lái)處理。編輯距離是指兩個(gè)字符串通過(guò)插入字符、刪除字符、改寫字符而變?yōu)橄嗤址枰牟僮鞔螖?shù)。比如：d(“abc”,”abd”) = 1d(“abc”,”ab”) = 1d(“abc”, “abcdf”) = 2d(“serverU”,” ser-u”) = 4利用動(dòng)態(tài)規(guī)劃的方法計(jì)算編輯距離，時(shí)間復(fù)雜性可以達(dá)到O(n2)，空間復(fù)雜性 32為 O（n2）。計(jì)算方法為一個(gè)遞歸算法：d(, ) = 0d(s, ) = d(, s) = |s| （|s|表示 s 的長(zhǎng)度）d(s1+ch1, s2+ch2) = min( d(s1, s2) + （if ch1=ch2 then

25、0 else 1）, d(s1+ch1, s2) + 1, d(s1, s2+ch2) + 1 )5.2.2.2ext 屬性距離的計(jì)算方法ext 指文件的擴(kuò)展名，雖然數(shù)據(jù)類型為字符串，但因此常見(jiàn)的文件類型是有限的，因此可以看成是枚舉類型，在聚類算法中則稱為標(biāo)稱變量。在進(jìn)行距離計(jì)算時(shí)可以按照聚類算法中對(duì)于此類數(shù)據(jù)類型的標(biāo)準(zhǔn)處理方法進(jìn)行處理，即其距離只是一個(gè)二值函數(shù)：取值相同則距離為 0；否則距離為 1。但考慮到文件擴(kuò)展名是有實(shí)際含義的，而且很多時(shí)候這些不同的擴(kuò)展名之間還有著豐富的聯(lián)系，因此我們能夠?qū)⑵涮幚淼母泳_。一般的，我們可以按照文件的擴(kuò)展名對(duì)文件類型進(jìn)行分類。比如可以將文件分成：程序、圖

26、片、音樂(lè)、影視、源碼等類別。在每個(gè)類別內(nèi)部，可能又有更深的層次，比如源碼可能又分為 C/C+源碼，JAVA 源碼等，而 C/C+源碼又可以進(jìn)一步分為頭文件和實(shí)現(xiàn)文件等 這樣就形成了一棵樹。不過(guò)要注意的是，這棵樹不是平衡的，某些葉節(jié)點(diǎn)可能比較深，另外一些可能比較淺。為了形成這棵樹，我們還需要說(shuō)明如下。首先，我們假設(shè)每種擴(kuò)展名只對(duì)應(yīng)于樹中的一個(gè)節(jié)點(diǎn)；其次，我們?cè)O(shè)置一個(gè)根節(jié)點(diǎn)，根節(jié)點(diǎn)本身不包含如何任何文件類型；再有，對(duì)于沒(méi)有擴(kuò)展名的文件，我們?yōu)槠滟x予一個(gè)特殊的值，并且直接位于根節(jié)點(diǎn)之下；對(duì)于不能識(shí)別的擴(kuò)展名我們也做同樣處理。這樣，最后形成了一棵類似下圖的樹： 33rootprogramvideomu

27、sicpicturesourceotherReal format.avi.rm.rmvbC/C+ language.java.himplementation.c.cpp圖 5-2 文件擴(kuò)展名屬性距離計(jì)算這樣，計(jì)算任意兩個(gè)文件條目類型屬性的距離演變成了計(jì)算樹中任意兩個(gè)葉節(jié)點(diǎn)之間的關(guān)系。對(duì)于樹中任意兩個(gè)葉節(jié)點(diǎn)的距離，則表示為其相似程度的倒數(shù)。而相似程度的計(jì)算，可以按照如下算法。樹中每個(gè)節(jié)點(diǎn)均存在一條從根節(jié)點(diǎn)到達(dá)它所在位置的唯一路徑 P。兩個(gè)節(jié)點(diǎn)的相似程度可以表示為它們各自路徑P 中公共節(jié)點(diǎn)的個(gè)數(shù)的函數(shù)。在實(shí)現(xiàn)上，我們選取如下的函數(shù)：假設(shè)需要計(jì)算兩個(gè) ext 值分別為 e1 和 e2 的點(diǎn) xi、x

28、j在此屬性上的距離。設(shè)e1 對(duì)應(yīng)的路徑為 p1，e2 對(duì)應(yīng)的路徑為 p2。p1 和 p2 的公共節(jié)點(diǎn)個(gè)數(shù)為 k（根節(jié)點(diǎn)除外），則我們?nèi)。?,2,211(,)2ijkdxx 345.2.2.3size 屬性距離的計(jì)算方法size 屬性表示文件條目的文件大小，以字節(jié)為單位，數(shù)據(jù)類型為整數(shù)。由于文件大小的取值范圍跨度很大，一般能夠從幾十字節(jié)到幾十億字節(jié)，因此不適合按照一般區(qū)間標(biāo)度變量的方法來(lái)計(jì)算，可以按照比例標(biāo)度型變量來(lái)處理。首先對(duì)size的值取對(duì)數(shù)：,3,3log()iiyx不過(guò)在實(shí)際應(yīng)用中要注意的是，因?yàn)閟ize 的取值范圍是非負(fù)整數(shù)，可能取0，因此不能直接取 log，可以考慮首先將 x1 再取

29、 log。,3,3log(1)iiyx然后將 yi3轉(zhuǎn)化為對(duì)應(yīng)的 z-score 值 Zi3,33,33iiymz s其中.)31,32,3,31nm (yyyn31,332,33331(| | . |)nsymymymn 進(jìn)行標(biāo)準(zhǔn)化處理之后，再求二者之差： 3,3,3,3,3(,)ijijdxxzz5.2.2.4date 屬性距離的計(jì)算方法date 屬性表示文件的最后修改日期，前面已經(jīng)說(shuō)過(guò)，我們將原來(lái)的字符串格式統(tǒng)一轉(zhuǎn)化為整數(shù)，比如按照距離公元元年元旦的日期數(shù)。對(duì)于整數(shù)，屬于區(qū)間標(biāo)度變量。為了更好的計(jì)算各個(gè)項(xiàng)目該屬性之間的距離，我們并不直接計(jì)算各個(gè)條目的差，而是先對(duì)其進(jìn)行標(biāo)準(zhǔn)化處理。將Xi4

30、轉(zhuǎn)化為對(duì)應(yīng)的 z-score 值 Zi4,44,44iixmz s 35其中.)41,42,4,41nm (xxxn41,442,44,441(| | . |)nsxmxmxmn 進(jìn)行標(biāo)準(zhǔn)化處理之后，再求二者之差：444,4,4(,)ijijdxxzz5.2.2.5site 屬性距離的計(jì)算方法由于在實(shí)際文件共享系統(tǒng)中， site 值最常見(jiàn)的情況就是 IP 地址，而兩個(gè) IP 地址之間的距離的比較是沒(méi)有實(shí)際意義的，因此我們忽略兩個(gè)site 屬性的之間的距離，或者可以表示為：5,5,5(,)0ijdxx5.2.2.6path 屬性距離的計(jì)算方法path 表示文件從根目錄開始到其節(jié)點(diǎn)所經(jīng)過(guò)的路徑。其

31、重要特點(diǎn)就是路徑是分段的，是由多個(gè)字符串連接而成的。比如路徑： /Resource/Software/Tools/network/可以看成是由分段的子字符串 Resource，Software，Tools 和 network 構(gòu)成的。在對(duì) path 進(jìn)行比較的時(shí)候，我們將每個(gè)路徑拆分成多個(gè)子字符串，然后比較其中公共子字符串的個(gè)數(shù)占全部子字符串的比例。6,6,6(,)comijijsdxxss公式中 si和 sj分別表示 xi和 xj的 path 屬性的分段的個(gè)數(shù)， Scom為公共子字符串的個(gè)數(shù)。5.2.3 對(duì)用戶點(diǎn)擊記錄進(jìn)行聚類在本體系中需要對(duì)用戶的點(diǎn)擊日志進(jìn)行聚類，以便能夠得到這k 個(gè)不同的

32、用戶查詢意圖。聚類常用的方法有 Partitioning 方法，Hierarchical 方法和 Density-based 方法。根據(jù)我們的具體情況，這里選用自底向上的Hierarchical 方法。 36對(duì)本方法的圖示說(shuō)明如下： abcdea,bstep 0 step 1 step 2 step 3 step 4d,ec,d,ea,b,c,d,eagglomerative(AGNES)圖 5-3 聚類示意圖假設(shè)共有 5 個(gè)對(duì)象 a,b,c,d,e，我們將其根據(jù)彼此的相關(guān)程度進(jìn)行聚類。首先，將每個(gè)待聚類的元素獨(dú)立劃分為一 個(gè)自己的類別，如果有 n 個(gè)元素，則開始時(shí)共有 n 類。然后將距離最近

33、的兩個(gè)元素歸為一類，此時(shí)有n-1 類；此后再將距離次近的歸為一類，類別共 n-2 類；如此不斷重復(fù) 如果沒(méi)有結(jié)束標(biāo)志，則最終將會(huì)把所有類別都?xì)w為一類。所以必須要設(shè)置結(jié)束標(biāo)志。這其中有幾點(diǎn)要說(shuō)明：5.2.3.1結(jié)束標(biāo)志的設(shè)定結(jié)束標(biāo)志可以從幾個(gè)方面來(lái)綜合考慮。首先是距離因素，設(shè)定當(dāng)距離最近的兩個(gè)類的距離大于某個(gè)類別間的距離閥值D 時(shí)不再進(jìn)行合并操作，設(shè)置距離標(biāo)志D可以防止最后生成的類別過(guò)少。另外由規(guī)律2 可知相同的查詢串通常只表示很少的查詢意圖，因此可以設(shè)定一個(gè)最大類別數(shù)G，這個(gè)表示可以防止最后生成的類別數(shù)過(guò)多。通過(guò)這兩個(gè)結(jié)束標(biāo)志的綜合運(yùn)用，可以使最終的類別數(shù)量控制在較理想的范圍中。5.2.3.2

34、具有多個(gè)元素的類別之間距離的計(jì)算當(dāng)類別包含多個(gè)元素時(shí)，計(jì)算它們之間的距離有三種不同的方法：計(jì)算距離最近的兩點(diǎn)之間的距離、最遠(yuǎn)的兩點(diǎn)之間的距離、或者用中心點(diǎn)來(lái)計(jì)算距離。我們這里選用中心點(diǎn)來(lái)計(jì)算二者的距離。這個(gè)中心點(diǎn)可能是類別中真實(shí)存在的一個(gè)元素， 37但也可能是一個(gè)并不真正包含的虛擬的元素。5.2.3.3孤立點(diǎn)的處理事實(shí)上，一些查詢串可能會(huì)對(duì)應(yīng)一兩個(gè)或很少的孤立查詢記錄，這些查詢記錄和其余大量的查詢記錄的相似度很低。通過(guò)人工查看的方法，我們發(fā)現(xiàn)很多這些孤立查詢記錄其實(shí)都是看上去不太正常的記錄，比如對(duì)于一些大小為0 的文件進(jìn)行下載，或者下載一些快捷方式文件等。我們認(rèn)為這些孤立點(diǎn)是因?yàn)橛脩舨恍⌒幕虿?/p>

35、了解所致。而這些文件條目實(shí)際上并不應(yīng)該被下載，而應(yīng)該被拋棄。因此我們需要對(duì)這些孤立點(diǎn)進(jìn)行丟棄。5.2.3.4訓(xùn)練集的生成由于在進(jìn)行完聚類后我們會(huì)對(duì)查詢?cè)龠M(jìn)行分類，因此我們考慮利用聚類中的文件條目作為分類時(shí)的訓(xùn)練集。在聚類完成后我們將保留每個(gè)查詢串的每個(gè)類別足夠的文件條目。5.2.4 對(duì)查詢結(jié)果集合進(jìn)行分類常用的分類算法有 k nearest neighbor(kNN), Nave Bayes, 還有 support vector machines 等。我們采用 kNN 算法。其具體步驟為：首先需要有一個(gè)訓(xùn)練集。對(duì)于每個(gè)可能的類別，各自有一些屬于該類別的對(duì)象。給定一個(gè)待分類的對(duì)象，系統(tǒng)在訓(xùn)練集中

36、查找與其最相似的k 個(gè)對(duì)象(稱為鄰居)，并根據(jù)這些鄰居所屬的類別情況來(lái)給該對(duì)象的候選類別評(píng)分，最后按照分值來(lái)確定待分類對(duì)象的類別。 38第6章 系統(tǒng)實(shí)現(xiàn)與評(píng)測(cè)6.1系統(tǒng)設(shè)計(jì)體系結(jié)構(gòu)圖實(shí)際系統(tǒng)的體系結(jié)構(gòu)圖如下?？紤]到一些實(shí)現(xiàn)問(wèn)題，和上一章的系統(tǒng)模型略有區(qū)別。 Index Part Clustering Part Collection Part ClickLog DataBase Training Set DataBase ClickLog Server Clustering Query q Normal Index System Items Categorization Filter Categ

37、ories Click log Items Training set Click log 圖 6-1 體系結(jié)構(gòu)圖下面我們來(lái)詳細(xì)介紹此系統(tǒng)設(shè)計(jì)。6.1.1 用戶行為收集部分Collection Part 部分為用戶點(diǎn)擊記錄收集部分，是實(shí)時(shí)運(yùn)行的。在用戶進(jìn)行查詢后，文件檢索系統(tǒng)返回包含查詢串的結(jié)果。用戶從中選取自己認(rèn)為正確的文件條目。用戶的選取操作就是一次鼠標(biāo)的點(diǎn)擊操作。這個(gè)點(diǎn)擊動(dòng)作自動(dòng)觸發(fā)到我們的后臺(tái) CGI 程序，程序先將用戶的下載請(qǐng)求轉(zhuǎn)向到真正的下載地址，后臺(tái)再發(fā)送一個(gè)記錄點(diǎn)擊操作的服務(wù)請(qǐng)求。該服務(wù)請(qǐng)求由ClickLog Server 接收，并記錄到 ClickLog Database 中。

38、我們稱用戶的每次點(diǎn)擊對(duì)應(yīng)的文件條目為 39ClickLog。經(jīng)過(guò)這樣反復(fù)多次后， ClickLog Database 中記錄了大量的 ClickLog，每個(gè) ClickLog 包含一個(gè)查詢串和對(duì)應(yīng)的文件條目item。6.1.2 聚類部分此部分為聚類操作部分，每隔一段時(shí)間運(yùn)行一次。在實(shí)際系統(tǒng)中可以根據(jù)用戶數(shù)量來(lái)設(shè)定為每小時(shí)或每天一次。這部分首先從 ClickLog Database 中讀取全部的 ClickLog 條目，然后對(duì)每個(gè)查詢串依次進(jìn)行處理。取出每個(gè)查詢串對(duì)應(yīng)的ClickLog 記錄，進(jìn)行聚類，聚類后得到 k 個(gè)類別。如前文所述，其中可能存在一些孤立點(diǎn)，然后按照標(biāo)準(zhǔn)對(duì)這些孤立點(diǎn)進(jìn)行考察，

39、需要的話要拋棄掉其對(duì)應(yīng)的孤立類別。聚類操作完成后，將聚類的結(jié)果存入Training Set Database 中。至此，我們就得到了實(shí)現(xiàn)免用戶干預(yù)的、基于反饋信息的檢索系統(tǒng)所需要的反饋數(shù)據(jù)。6.1.3 索引部分完成了上面兩個(gè)部分的工作，就可以進(jìn)行真正的反饋了。對(duì)于用戶的查詢串q，首先使用常規(guī)檢索系統(tǒng)進(jìn)行檢索，就可得到一個(gè)文件條目Item 的集合。然后在 Training Set Database 中取出對(duì)應(yīng)于查詢串 q 的 k 個(gè)類別的訓(xùn)練集。利用這些訓(xùn)練集條目為剛剛通過(guò)常規(guī)查詢得到的Item 集合進(jìn)行分類。此處我們限定每個(gè)文件條目至多屬于 1 個(gè)類別。分類后可能得到 k+1 個(gè)類別（某些 I

40、tem 可能不屬于任何類別），以及每個(gè)條目和其所屬類別的相似程度。利用分類的類別和相似度，系統(tǒng)可以重新根據(jù)此信息進(jìn)行輸出。對(duì)于那些不屬于任何類別的文件條目，通常也是用戶所不太關(guān)心的結(jié)果，可以選擇拋棄或排在結(jié)果頁(yè)面的最后。6.2其它實(shí)現(xiàn)中的問(wèn)題6.2.1 記錄用戶對(duì)查詢結(jié)果的選取對(duì)于用戶對(duì)查詢結(jié)果的選取的記錄，一般有兩種方法，采用client 端技術(shù)和server 端技術(shù)。為了方便用戶的使用，不改變用戶的任何使用習(xí)慣，我們采取server 端技術(shù)來(lái)記錄用戶的選擇，這樣用戶在使用時(shí)就不需要絲毫的改變，而我們也能夠得到足夠的記錄信息。 40具體說(shuō)來(lái)，傳統(tǒng)網(wǎng)頁(yè)上的鏈接一般如下：qqtail.sln我們

41、采用 javascript 技術(shù)將其進(jìn)行改造，改造后的形式如下：QQTail.sln注意其中有 2 處 javascript 腳本。第一處是 onClick 信息，當(dāng)用戶點(diǎn)擊了該鏈接時(shí)，自動(dòng)重新轉(zhuǎn)向到了我們的服務(wù)器上，服務(wù)器有一個(gè)接收該請(qǐng)求的CGI 程序clicklog，這個(gè)程序自動(dòng)轉(zhuǎn)向到實(shí)際的 FTP 下載地址，然后向 ClickLog Server 發(fā)送一個(gè)記錄請(qǐng)求， ClickLog Server 就記錄下整個(gè)查詢串和文件條目信息。腳本中的另一處是 onMouseOver，這個(gè)是為了處理當(dāng)用戶已經(jīng)點(diǎn)擊該鏈接后卻又突然想復(fù)制該鏈接而使用的。只所以在此處使用了 javascript 而不是直

42、接改變鏈接地址，是為了便于那些并不希望通過(guò)直接點(diǎn)擊，而是希望使用下載工具或想復(fù)制下載地址的用戶的方便。通過(guò)現(xiàn)在這種改造，用戶看到的頁(yè)面和鏈接地址都是和原始信息是完全一致的。6.2.2 文件類型屬性距離計(jì)算方法的實(shí)現(xiàn)前面談到對(duì)于常見(jiàn)的文件擴(kuò)展名，我們將其各自賦予一個(gè)屬性值，屬性值代表了在文件類別樹中從根結(jié)點(diǎn)到該文件類型所在節(jié)點(diǎn)的所有節(jié)點(diǎn)編號(hào)的集合。節(jié)點(diǎn)的編號(hào)示例如下圖所示，每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)的編號(hào)都是從1 開始的，并沒(méi)有全局性的編號(hào)。 41root1234561212121212圖 6-2 ext 屬性距離計(jì)算方法的實(shí)現(xiàn)比如對(duì)應(yīng)圖中左下角的灰色節(jié)點(diǎn)來(lái)說(shuō)，對(duì)應(yīng)的路徑為2.1.1；右下角的灰色節(jié)點(diǎn)對(duì)應(yīng)

43、的路徑則為 5.1.2.2。這樣，如果比較兩個(gè)節(jié)點(diǎn)的相似度，我們只需計(jì)數(shù)它們的路徑中相同的節(jié)點(diǎn)個(gè)數(shù)即可。比如路徑為 2.1.1 的節(jié)點(diǎn)和 2.2 的節(jié)點(diǎn)，它們的路徑中有一個(gè)相同的節(jié)點(diǎn)2，或者說(shuō)相似度為 1 層；路徑為 2.1.1 的節(jié)點(diǎn)和 2.1.2 的節(jié)點(diǎn)，它們的相似度為2 層；路徑為 5.3 的節(jié)點(diǎn)和路徑為 7 的節(jié)點(diǎn)相似度則為 0。具體文件類型分類列表見(jiàn)附錄 1。配置文件格式，擴(kuò)展名分類文件的配置文件的格式舉例如下：111mp3|wav|wma|112midi|mid|文件說(shuō)明： 42作用：通過(guò)讀取文件得到每個(gè)擴(kuò)展名對(duì)應(yīng)的路徑。文件格式：每 3 行為一個(gè)記錄。每個(gè)記錄中第一行是空行；第2

44、 行是路徑，格式為每層節(jié)點(diǎn)編號(hào)用制表符分割；第3 行是擴(kuò)展名列表，每個(gè)擴(kuò)展名都以豎線“|”結(jié)束。距離計(jì)算方法的實(shí)現(xiàn)：在系統(tǒng)實(shí)現(xiàn)時(shí)，定義了一個(gè) ExtVector 類，它代表了一個(gè)具體的節(jié)點(diǎn)路徑，ExtVector 繼承自 vector，這里的 vector 是標(biāo)準(zhǔn) STL 的 vector，并且實(shí)現(xiàn)了如下方法來(lái)計(jì)算兩個(gè)路徑之間的距離：double operator (const ExtVector& e1, const ExtVector& e2); 6.3系統(tǒng)的評(píng)測(cè)環(huán)境我們采用天網(wǎng)千帆文件搜索引擎為測(cè)試系統(tǒng)。天網(wǎng)千帆文件搜索引擎為北京大學(xué)網(wǎng)絡(luò)實(shí)驗(yàn)室開發(fā)的一個(gè) FTP 文件搜索引擎，有較大的用

45、戶訪問(wèn)量。在2005 年4 月，我們先后運(yùn)行了普通文件搜索引擎和我們?cè)O(shè)計(jì)的新型文件搜索引擎，并記錄了用戶的查詢記錄和用戶對(duì)查詢結(jié)果的選取信息。為了保證評(píng)測(cè)效果的準(zhǔn)確性，在使用了新系統(tǒng)后，我們沒(méi)有通知任何用戶，也沒(méi)有改變?nèi)魏斡脩艚缑妫箿y(cè)試盡量在用戶不知情的情況下進(jìn)行。對(duì)于分類后不能歸入任何類別的文件條目，為了保證總體查詢結(jié)果數(shù)量不變，我們也沒(méi)有進(jìn)行拋棄，而是放在排序的最后返回給用戶。這里采用的排序方法是在頁(yè)內(nèi)按照各個(gè)初始結(jié)果集合 S0中各個(gè)條目距離其類別的距離遠(yuǎn)近進(jìn)行排序，對(duì)不同的類別之間并不進(jìn)行排序。在結(jié)果的表現(xiàn)形式上與普通搜索引擎無(wú)異。比較試驗(yàn)共進(jìn)行了 8 天，其中 4 天為普通文件檢索系

46、統(tǒng)，另外 4 天則為我們的新系統(tǒng)。我們分別比較了用戶對(duì)前2 頁(yè)查詢結(jié)果頁(yè)面中點(diǎn)擊的文件條目在該頁(yè)面中的排序的情況，共取得了 8 組比較數(shù)據(jù)。6.4評(píng)測(cè)結(jié)果具體比較結(jié)果參見(jiàn)下圖。圖中橫坐標(biāo)表示8 組比較數(shù)據(jù)，縱坐標(biāo)為各組試驗(yàn)數(shù)據(jù)的在頁(yè)面中點(diǎn)擊的條目的排序的平均值。圖中上部的曲線（虛線）為普通文件檢索系統(tǒng)的結(jié)果，下面的曲線（實(shí)線）為新系統(tǒng)的試驗(yàn)結(jié)果。 43圖 6-3 系統(tǒng)試驗(yàn)效果比較從圖中可以明顯的看到：在新系統(tǒng)下，用戶所點(diǎn)擊的文件條目在頁(yè)面中的排序比普通系統(tǒng)有了較大幅度的提前。在我們的試驗(yàn)系統(tǒng)中，普通文件檢索系統(tǒng)用戶點(diǎn)擊的條目在頁(yè)面中的排名為13.70，而使用了新系統(tǒng)后，點(diǎn)擊條目的平均排名為8.

47、93。排名前進(jìn)了 13.70-8.93=4.77 名。檢索效果有了較大幅度的改進(jìn)。由此可驗(yàn)證本文所述新型文件檢索系統(tǒng)的正確性。 44第7章 總結(jié)與展望7.1總結(jié)作者在本文中首先對(duì)文件檢索系統(tǒng)進(jìn)行了一些基礎(chǔ)性的研究工作，提出了文件檢索系統(tǒng)的檢索模型，并提出了評(píng)測(cè)的指標(biāo)。然后在對(duì)用戶使用文件檢索系統(tǒng)的行為和習(xí)慣進(jìn)行記錄的基礎(chǔ)上，發(fā)現(xiàn)了用戶行為習(xí)慣中的兩個(gè)重要規(guī)律。利用這兩個(gè)規(guī)律，作者提出了一個(gè)免用戶干預(yù)的、基于用戶查詢記錄的新型文件檢索模型，該模型可以有效的提高文件檢索系統(tǒng)的精度。最后作者實(shí)現(xiàn)了一個(gè)真實(shí)的系統(tǒng)并利用該系統(tǒng)對(duì)本模型的有效性進(jìn)行了驗(yàn)證。7.2展望由于研發(fā)時(shí)間倉(cāng)促，系統(tǒng)的有些功能還沒(méi)有來(lái)

48、得急加入，有的地方還有待加強(qiáng)，特別如下文所述的幾處。7.2.1 目錄本文的全部算法都沒(méi)有考慮目錄的特殊性，而在實(shí)際的FTP 系統(tǒng)中是存在目錄共享的。在本文提到的試驗(yàn)系統(tǒng)中，對(duì)目錄是不加區(qū)分的看成文件來(lái)處理，這樣在處理效果上就不是很理想了。目錄和文件的區(qū)別主要表現(xiàn)在這幾個(gè)方面：首先，目錄不存在擴(kuò)展名屬性 ext，這樣造成了無(wú)法利用這個(gè)屬性來(lái)進(jìn)行判斷，而 ext 屬性在距離計(jì)算中又是非常重要的一個(gè)因素。其次，目錄的大小 filesize 往往比較大。因?yàn)槟夸浭怯脕?lái)容納文件的，因此目錄的大小必然比其內(nèi)部的任何文件都要大。這樣，就不能直接將目錄和文件的大小進(jìn)行相似度計(jì)算。7.2.2 壓縮文件類型壓縮文

49、件，比如我們通常見(jiàn)到的 zip 文件，rar 文件等。是一種特殊形式的文件。如文中我們所言，文件的擴(kuò)展名常常表示文件的類型，比如是圖片文件、音樂(lè) 45文件、視頻文件等。而壓縮文件本身是為了節(jié)省存儲(chǔ)空間而通過(guò)對(duì)其它文件進(jìn)行壓縮而生成的。此類文件的意義在于其所壓縮的文件，而本身的文件類型是沒(méi)有意義的。這樣就造成了文件類型屬性 ext 判斷的失效。在另一個(gè)屬性上，文件大小，對(duì)于壓縮文件也是意義不明顯的。因?yàn)閴嚎s方式的區(qū)別，造成壓縮比例的差異，同樣大小的原始文件，可能壓縮為不同大小的壓縮文件；壓縮后同樣大小的文件，其原始文件可能也是不同的。因此直接用文件大小這個(gè)屬性來(lái)比較壓縮文件也是不準(zhǔn)確的。如上這些

50、特性，造成了壓縮文件不適于按照一般的文件類型來(lái)進(jìn)行比較，應(yīng)該進(jìn)行專門的處理。 46參考資料Ruthven, et al., 2003 I. Ruthven and M. Lalmas, A survey on the use of relevance feedback for information access, Knowledge Engineering Review. Vol 18. Issue 2. pp 95-145. 2003.Chang, et al., 1996 Chen-Chuan K. Chang, Hctor Garca-Molina, and Andreas Paepc

51、ke. Boolean Query Mapping Across Heterogeneous Information Sources. IEEE Transactions on Knowledge and Data Engineering, 8(4): 515-521, Aug, 1996.Zhang and Dong, 2002 Dell Zhang, Yisheng Dong. A novel Web usage mining approach for search engines, computer networks, 2002, vol.39: 303-310.Allison, 199

52、9 Allison, L. Dynamic programming algorithm (DPA) for edit distance, In Algorithms and Data Structures Research & Reference Material. School of Computer Science and Software Engineering, Monash University, Australia 3168. 1999Beeferman, et al., 2000 D. Beeferman, A. Berger, Agglomerative clustering

53、of a search engine query log, in: Proceedings of ACM KDD, 2000, Boston, MA, USA.Salton, et al, 1983 G. Salton, M. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, New York, 1983.Lewis, 1995 D. D. Lewis. Evaluating and optimizing autonomous text classification systems. In Proceeding

54、s of SIGIR-95, 18th ACM International Conference on Research and Development in Information Retrieval, pages 246254, Seattle, US, 1995.Ripeanu, 2001 M. Ripeanu, peer-to-peer Architecture Case Study: Gnutella, Network, University of Chicago Technical Report TR-2001-26.RFC 959 RFC 959, File Transfer P

55、rotocol (FTP)陳華等，2003 陳華，李曉明，高級(jí)文件搜索引擎核心功能的實(shí)現(xiàn)技術(shù)，全國(guó)搜索引 47擎與 Web 挖掘進(jìn)展會(huì)議，2003.3 15-27天網(wǎng) 天網(wǎng)千帆文件搜索引擎 http:/天網(wǎng) maze 天網(wǎng) maze 文件共享系統(tǒng) http:/王建勇等, 2001 王建勇、單松巍、雷鳴、謝正茂、李曉明，海量 web 搜索引擎系統(tǒng)中用戶行為的分布特征及其啟示， 中國(guó)科學(xué)E 輯，2001 年 8 月，第 31 卷，第四期，372-384 頁(yè)陳華等,2004 陳華，王繼民，韓近強(qiáng)，謝欣，互聯(lián)網(wǎng)上 FTP 文件的分布特征及啟示，計(jì)算機(jī)工程與應(yīng)用 ， 2004 年第 40 卷，129-1

56、33 48附錄：文件類型列表 音頻文件： 1常用：1.1 聲音記錄 1.1.1mp3|wav| wma| 音階 1.1.2midi| mid|cda| mp1|m3u|mjf|voc|xm|s3m|stm|mod|dsm|far|ult|mtm|mp2|mpa|669|aac|mp4|vqf|pls|xpl|lrc|rmi|snd|aif|wax|rms|aiff|aifc|mpga| 視頻文件 2電影常用格式 2.1 real 格式 2.1.1rmvb| rm| 高清晰 2.1.2avi|短篇格式 2.2 mpg| mpeg| asf| wmv| mpe| dat| asx|mkv|字幕 2

57、.3 vob|ram|rmm|rmj|wvx|m1v|wmp|ivf|smi|mpv|ssm|mpv2|mp2v|smil|rv|rp|rf|rt| 49wm|ra|kbk|la1|lar|lavs|lmsff| 圖形文件 3web 常用格式 3.1 jpg|bmp|gif| png| jpe|矢量 3.2 wmf|pcx|tif|psd|tga|pic|pcd|dib|rle|iff|lbm|jif|dcx|ico|tiff|ilbm| 代碼文件 4C/C+ 4.1 c|h| cpp|hpp|JAVA 4.2 java|class|PASIC 4.3 pas|BASIC 4.4 bas|匯編

58、 4.5 asm|perl 4.6 perl|js|inc|cxx|tli|tlh|hxx|inl|def|odl|idl|py| 壓縮文件 5常用格式 5.1 rar|zip|linux 壓縮格式 5.2 gz|tar|tgz|b64| gz| z|arj|cab| arc| bhx|hqx|lzh|mim|taz|uue|xxe|tz|uu| 網(wǎng)頁(yè)文件 6靜態(tài) 6.1 htm|html|shtml|動(dòng)態(tài) 6.2 50 php|asp| php3|jsp|web 程序 6.3 htw|htx|css|url| 程序相關(guān)文件 7可執(zhí)行文件 7.1 windows 程序 7.1.1exe|msi

59、| Dos 文件 7.1.2com|bat| unix 程序 7.1.3out|系統(tǒng)文件 7.2 ocx|dll|drv| 文本文件 8txt|asa|wri|log|scp| 系統(tǒng)配置文件 9配置文件 9.1 ini|inf|conf|注冊(cè)表文件 9.2 reg| office 文檔 10Word 文擋 10.1 doc|rtf|wbk|Excel 文檔 10.2 xls|xlb|xlc|PowerPoint 文檔 10.3 ppt| 幫助文檔 11hlp| Flash 文檔 12swf|fla| Acrobat 文檔 13pdf|pdx|apf|fdf|rmf|xfdf| Caj 文檔 1

60、4caj|kdh|其它不可識(shí)別格式 51致謝首先要向我的導(dǎo)師 表示衷心的感謝，感謝他在我三年的碩士生階段和本論文的完成工作中對(duì)我的精心指導(dǎo)和諄諄教誨，他踏實(shí)的治學(xué)態(tài)度和嚴(yán)謹(jǐn)?shù)墓ぷ髯黠L(fēng)使我受益匪淺，他淵博的知識(shí)和對(duì)事業(yè)無(wú)止境的追求使我感受至深，他對(duì)我的嚴(yán)格要求將對(duì)我以后的工作學(xué)習(xí)產(chǎn)生巨大的影響，使我終生受益，我以作為他的學(xué)生而自豪。感謝我的父母，他們?cè)谖业某砷L(zhǎng)過(guò)程中傾注了極大的心血，他們對(duì)我的言傳身教和嚴(yán)格要求，將是我這一生中最寶貴的財(cái)富。要感謝我的同學(xué)，他們對(duì)我的論文寫作起了非常大的幫助作用，曾經(jīng)多次幫助過(guò)我。 還要感謝我的女友，在我的生活和工作中，給予了我莫大的支持和鼓勵(lì)。最后，深深感謝每一

61、位關(guān)心我的朋友和老師，感謝你們?cè)谖页砷L(zhǎng)道路上對(duì)我的幫助。 52北京大學(xué)學(xué)位論文原創(chuàng)性聲明和使用授權(quán)說(shuō)明北京大學(xué)學(xué)位論文原創(chuàng)性聲明和使用授權(quán)說(shuō)明原創(chuàng)性聲明原創(chuàng)性聲明本人鄭重聲明： 所呈交的學(xué)位論文，是本人在導(dǎo)師的指導(dǎo)下，獨(dú)立進(jìn)行研究工作所取得的成果。除文中已經(jīng)注明引用的內(nèi)容外，本論文不含任何其他個(gè)人或集體已經(jīng)發(fā)表或撰寫過(guò)的作品或成果。對(duì)本文的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中以明確方式標(biāo)明。本聲明的法律結(jié)果由本人承擔(dān)。論文作者簽名： 日期： 年 月 日學(xué)位論文使用授權(quán)說(shuō)明學(xué)位論文使用授權(quán)說(shuō)明本人完全了解北京大學(xué)關(guān)于收集、保存、使用學(xué)位論文的規(guī)定，即：按照學(xué)校要求提交學(xué)位論文的印刷本和電子版本；學(xué)校有權(quán)保存學(xué)位論文的印刷本和電子版，并提供目錄檢索與閱覽服務(wù)；學(xué)?？梢圆捎糜坝　⒖s印、數(shù)字化或其它復(fù)制手段保存論文；在不以贏利為目的的前提下，學(xué)?？梢怨颊撐牡牟糠只蛉?jī)?nèi)容。（保密論文在解密后遵守此規(guī)定）論文作者簽名： 導(dǎo)師簽名： 日期： 年 月 日