【文章內(nèi)容簡(jiǎn)介】 數(shù)，而構(gòu)成一個(gè)倒排基本單位。 例如，一本旅游類書籍的第 130 頁講述了“冰糖葫蘆”的來歷。在經(jīng)過倒排后，“冰糖葫蘆”被作為一個(gè)單獨(dú)的關(guān)鍵字切分出來，保存在索引中，同時(shí)還帶有其頁碼“ 130”，作為索引項(xiàng)的內(nèi)容。這樣，當(dāng)信息檢索系統(tǒng)檢索“冰糖葫蘆”這個(gè)關(guān)鍵字 時(shí)，系統(tǒng)就可以迅速給出其頁碼，然后再到原書中取出相關(guān)頁面文本內(nèi)容。這種查找方式要比從第 1頁開始，線性匹配所有文本，找出包含有“冰糖葫蘆”的頁面內(nèi)容要快得多，如圖 所示 原始文檔 索引 圖 倒排 上說，倒排是一種面向單詞的索引機(jī)制。通常，它由詞（關(guān)鍵字）和出現(xiàn)情況兩部分組成。對(duì)于索引中的每個(gè)詞（關(guān)鍵字），都跟隨一個(gè)列表（位置表），用來記錄單詞在所有文檔中出現(xiàn)的位置。 【 8】 倒排的特點(diǎn) 在倒排索引中，關(guān)鍵字的數(shù)量并非隨著文本內(nèi)容的增長也線性增長。這是因?yàn)闊o論多大數(shù)量的文本數(shù)據(jù)庫，總能夠規(guī)范出一個(gè)關(guān)鍵字表。這種關(guān)鍵字表受到實(shí)際語言因素的限制，它的增長率在文本數(shù)據(jù)庫達(dá)到一定規(guī)模后可以忽略不計(jì)。有人做過統(tǒng)計(jì)，冰糖葫蘆 130 頁 砂鍋丸子 第 42 頁 羊肉串 第 67 頁 冰糖葫蘆 第 30 頁 炸醬面 第 142 頁 大閘蟹 第 177 頁 9 對(duì)于 1GB 的文本信息來說， 詞匯表（關(guān)鍵字表）的大小在 5MB 左右。 【 9】 可以試想，將一本書上所有的文本均制作成關(guān)鍵字，并對(duì)其進(jìn)行倒排構(gòu)建一個(gè)信息搜索引擎系統(tǒng)。對(duì)其中的內(nèi)容進(jìn)行檢索，在整個(gè)過程中，最消耗時(shí)間的應(yīng)該就是倒排階段。因?yàn)樵诘古艜r(shí)，需要對(duì)文本進(jìn)行分析、切詞， 還要構(gòu)建索引結(jié)構(gòu)，記錄位置信息，同時(shí)維護(hù)相關(guān)內(nèi)容。雖然這一階段花費(fèi)大量時(shí)間，但是一旦完成。檢索時(shí)將會(huì)節(jié)省大量時(shí)間。事實(shí)上，一個(gè)信息檢索系統(tǒng)在建立索引時(shí)的速度要求是可以放寬的，因?yàn)楫吘惯@是在后臺(tái)異步完成，而其搜索速度影響用戶最終體驗(yàn)的直接因素。 分詞技術(shù) 為什么需要分詞 目前的搜索引擎，大多是基于一種稱為倒排索引的結(jié)構(gòu)。以什么做為 索引 的 Key 值，直接影響到整個(gè)搜索引擎的準(zhǔn)確度、召回率、速度。我們先看看不使用中文分詞的情況。如果不使用中文分詞，可以采用單個(gè)漢字索引方式。例如，雅虎 ， 先索引 ‘ 雅 ’ 字，然后再索引 ‘ 虎 ’ 字。同樣，對(duì)于一篇文章，先把所有的漢字都單獨(dú)索引一次，并記錄他們的位置。搜索過程中，也是先找 39。雅 39。字的所有文檔，再找 39?；?39。字的所有文檔，然后做交叉 39。與 39。運(yùn)算，即包含這兩個(gè)字，而且位置連續(xù)的文檔才會(huì)做為符合要求的結(jié)果。這種方式是最基本的索引方式，現(xiàn)在有些小 引擎中還在使用。但這里存在一個(gè)很有挑戰(zhàn)性的問題：總共的常用漢字 才 3000 多個(gè)，我們每次查詢過程中，進(jìn)行 39。與 39。操作的計(jì)算量會(huì)相當(dāng)大，對(duì)于大數(shù)據(jù)量搜索引擎來說 (超過 10億的文檔 )，每天上億次查詢，這樣的索引結(jié)構(gòu)，無疑是對(duì)硬件和算法的極 大挑戰(zhàn)。 考慮到速度問題，如果不使用分詞，還有另外一種選擇： n 元組合索引方式 ， 2元 /3元等。拿 2元來說，中國人 , 先索引 ‘ 中國 ’ , 再索引 ‘ 國人 ’ 。同樣，對(duì)于一篇文章，以 2 為單位，把所有相鄰的漢字都索引起來，并記錄他們的位置。搜索過程中，也是先找包含 39。中國 39。的所有文檔，再找 39。國人 39。的所有文檔，然后做交叉 39。與 39。運(yùn)算，即包含這兩個(gè)單元，而且位置連續(xù)的文檔才會(huì)做為符合要求的結(jié)果。這樣以兩個(gè)字做為索引單元，可以大大減少在搜索過程中的計(jì)算量。 以上兩種方式，都可以不需要分詞，也能實(shí)現(xiàn)搜索引擎的索引和搜索。但是這里 存在一個(gè)不可忽視的問題：準(zhǔn)確度。一個(gè)很常見的例子： 和服 , 如果按照上面兩種方式，都會(huì)查到包含 39。主板 和服 務(wù)器 39。的文檔； 北大 也會(huì)得到 39。東 北大 學(xué) 39。對(duì)于大數(shù)據(jù)量的搜索引擎來說，每個(gè)搜索次都會(huì)有成千上萬個(gè)結(jié)果，用戶已經(jīng)很挑選他真正想要的文章，如果這里還要增加許多錯(cuò)誤，估計(jì)用戶體驗(yàn)會(huì)極差。這時(shí)候，我們需要中文分詞。 10 詞，是中文語言中最小的語意單位。以詞為單位做為搜索引擎的索引的 Key 值，會(huì)大大提高搜索引擎結(jié)果的準(zhǔn)確性，同時(shí)保證了搜索過程中計(jì)算量小。其實(shí)還有一個(gè)優(yōu)點(diǎn)，以詞為單位的索引，起索引庫會(huì)比上兩 種方式的索引庫小很多。很明顯：如果以 中國人 做為一個(gè)詞，那么搜索的時(shí)候，不需要任何 39。與 39。運(yùn)算，索引的時(shí)候記錄也會(huì)減少。 中文分詞的算法 中文分詞技術(shù)的研究，已經(jīng)有幾十年的歷史了，在 20 世紀(jì) 80 年代，我國就有人開始研究如何用計(jì)算機(jī)來自動(dòng)分詞。如何讓機(jī)器去識(shí)別語言中最小的語意單位，不是一件很容易的事情。 如何進(jìn)行分詞？對(duì)于程序員來說，最容易想到的辦法是，用一個(gè)大詞典，把所有的詞都存入詞典中，掃描輸入的文本，查找所有可能的詞，然后看哪個(gè)詞可以做為輸出。例如： 輸入文本 : 我是學(xué)生 詞 : 我 /是 /學(xué)生 其實(shí)這樣做了以后，可以解決 60%的問題。總結(jié)起來，分詞的算法分為： 基于字符串匹配的分詞方法 基于理解的分詞方法 基于統(tǒng)計(jì)的分詞方法 關(guān)于這 3種算法的詳細(xì)介紹，可以查看 中文分詞技術(shù) ， 這里想介紹的是，如何處理新詞。 新詞，術(shù)語是 未登錄詞 ，就是那些沒有收入到詞典里面的詞。新詞主要包括：人名、地名、機(jī)構(gòu)名、熱點(diǎn)新名詞等。例 如： 2020 年之前，沒有人知道 非典 。 非典 剛出現(xiàn)的時(shí)候，這就是新詞。還有 超女 , 三個(gè)代表 ， 芙蓉姐姐 。識(shí)別新詞的能力是評(píng)估一個(gè)分詞系統(tǒng)的重要指標(biāo)。在國際上每年進(jìn)行的分詞大賽中，識(shí)別新詞的比賽也單獨(dú)提出。 2020 年 SIGHAN 的分詞大賽中，就增添了對(duì)于機(jī)構(gòu)名識(shí)別的比賽。 如何識(shí)別新詞成為最近幾年分詞技術(shù)研究的重點(diǎn)?？偨Y(jié)起來，無非分成兩種： 基于規(guī)則的方法。 基于統(tǒng)計(jì)、機(jī)器學(xué)習(xí)。 拿人名識(shí)別 為例。你不可能把所有的人名都放入詞典中，這決定了人名注定會(huì)是新詞。從人名構(gòu)造來說，很有規(guī)律：姓＋名。張王劉李陳、天下一半人。也就是說可能有 11 一半的人，是這五個(gè)姓。名也有一定規(guī)律：建華 /建國 /志強(qiáng) .....等有許多經(jīng)常用于名字中的漢字；對(duì)于地名識(shí)別也可以找出很多規(guī)則，省 /縣 /村 /鎮(zhèn) /灣 /河等，都是很常用的后綴，如果他們出現(xiàn)，之前出現(xiàn)地名的可能性比較大。如果把這些規(guī)律轉(zhuǎn)化成計(jì)算機(jī)能識(shí)別的算法，就是基于規(guī)則的算法。這種基于規(guī)則的算法簡(jiǎn)單有效，而且發(fā)現(xiàn)規(guī)則可很方便加入。 規(guī)則總會(huì)有例外，規(guī)則過多以后，如何去權(quán)衡這些 規(guī)則，會(huì)是十分頭疼的問題。人們?cè)囍嬖V計(jì)算機(jī)目標(biāo)，讓計(jì)算機(jī)自己去嘗試各種方法組合這些規(guī)則并得到最優(yōu)參數(shù)，這就 是 機(jī)器學(xué)習(xí)。隨著 Machine Learning(機(jī)器學(xué)習(xí) )技術(shù)的不斷進(jìn)步，其應(yīng)用范圍也越來越廣，中文分詞算法也從中受益。 ANN(人工神經(jīng)網(wǎng)絡(luò) ), 最大熵模型 , HMM(隱馬爾可夫模型 )等算法都在新詞識(shí)別中有應(yīng)用。通過機(jī)器學(xué)習(xí)識(shí)別新詞的原理并不復(fù)雜。一般都是先定義一些特征，然后利用訓(xùn)練語料進(jìn)行學(xué)習(xí)，建立模型。還是以人名識(shí)別為例，可以定義姓名前面的字、姓、名、姓名后面的字做為特征，通過利用標(biāo)注好姓名的語 料庫進(jìn)行學(xué)習(xí)訓(xùn)練。 機(jī)器學(xué)習(xí)識(shí)別新詞的好處在于自動(dòng)尋找一些識(shí)別新詞的特征，其準(zhǔn)確度和召回率都能達(dá)到比較高的水平。但機(jī)器學(xué)習(xí)算法需要有足夠多的訓(xùn)練語料，人工準(zhǔn)備準(zhǔn)確的大規(guī)模的訓(xùn)練語料也會(huì)十分困難。另外，機(jī)器學(xué)習(xí)算法一般速度會(huì)比較慢，優(yōu)化速度，使之用于海量數(shù)據(jù)處理，也是使用機(jī)器學(xué)習(xí)的一個(gè)關(guān)鍵點(diǎn)。 【 10】 中文分詞和搜索引擎 中文分詞除了在索引結(jié)構(gòu)上影響搜索引擎以外，還會(huì)如何影響搜索引擎？ 除了搜索引擎的索引過程需要用到分詞以外，所有的搜索之前也需要用到分詞。有些人誤認(rèn)為 短語搜索 （即兩端加上引 號(hào)的搜索方式，搜索引擎基本都支持這種方式，查看 搜索引擎幫助 ）是 直接拿字符串去匹配不用分詞，因?yàn)榻Y(jié)果看上去好像是字符串匹配的結(jié)果。其實(shí)不然，短語搜索同樣需要用分詞，只不過在結(jié)果中需要位置連續(xù)等嚴(yán)格限制。當(dāng)位置連續(xù)時(shí)，在顯示摘要的時(shí)候，會(huì)讓你感覺只是用字符串匹配。 除了在搜索前端后端都需要用到分詞以外，搜索引擎還有一個(gè)原則：前端后端分詞結(jié)果應(yīng)該一致。這意思是說，如果你在索引時(shí) 沒有識(shí)別出 文德 的人名，你在搜索時(shí)最好也別識(shí)別出來，這樣可以按照兩個(gè)單字的方式查找，或許有正確結(jié)果，否則會(huì)查不到結(jié)果。反之也一樣。由于索引過程中，分詞輸入的一篇文章，有大量的上下文信息，但在搜索時(shí)，用戶輸入的可能只有幾個(gè)字，很多上下文信息不在存在。如果過多使用統(tǒng)計(jì)或機(jī)器學(xué)習(xí)，很容易導(dǎo)致搜索引擎的前端后端分詞不一致的問題。這也是搜索引擎使用分詞和其他系統(tǒng)，如機(jī)器翻譯，使用分詞不一樣的地方。 12 如果你看過搜索引擎的 query log（即所有搜索詞的記錄），你會(huì)發(fā)現(xiàn)新詞很多，會(huì)占 30%，或者更多。對(duì)這些新詞的識(shí) 別會(huì)直接影響搜索結(jié)果的準(zhǔn)確性，或者說相關(guān)性。搜索結(jié)果的相關(guān)性決定于排序算法，排序算法一部分依賴于網(wǎng)頁的質(zhì)量和權(quán)威性，另一方面依賴于分詞結(jié)果的準(zhǔn)確性。分詞結(jié)果準(zhǔn)確，我們會(huì)方便的計(jì)算詞在文章中的重要程度。超女 做為一個(gè)詞在文章中的權(quán)重，和 超 、 女 兩個(gè)字在文章中的權(quán)重計(jì)算方法會(huì)很不一樣，這樣就會(huì)直接影響相關(guān)性的計(jì)算。 中文分詞對(duì)于搜索引擎的影響，還表現(xiàn)在對(duì)于用戶輸入詞意圖的識(shí)別。識(shí)別用戶的輸入詞是否是人名、網(wǎng)站名、軟件名還是其他通用詞匯，能夠判斷用戶的意圖，從而提供用戶想要的結(jié)果。 其實(shí)中文分詞是所有 中文處理的基礎(chǔ)，因此如果有一個(gè)好的分詞系統(tǒng)，會(huì)對(duì)改進(jìn)搜索引擎的相關(guān)性有很大的幫助。但最終展現(xiàn)給用戶的是網(wǎng)頁結(jié)果而不是分詞結(jié)果，提高網(wǎng)頁的相關(guān)性，有 100%準(zhǔn)確的分詞也是不夠。如何在準(zhǔn)確的中文分詞基礎(chǔ)上，做更多的分析和挖掘，理解用戶的意圖，滿足用戶的需要，是每個(gè)搜索引擎公司都在努力做的事情。 用 OpenCV 庫 求解 圖像顏色分布直方圖 什么是 OpenCV OpenCV 是 Intel174。開源計(jì)算機(jī)視覺庫。它由一系列 C 函數(shù)和少量 C++ 類構(gòu)成，實(shí)現(xiàn)了圖像處理和計(jì)算機(jī)視覺方面的很多通用算法 。 OpenCV 擁有包括 300 多個(gè) C 函數(shù)的跨平臺(tái)的中、高層 API。它不依賴于其它的外部庫 ——盡管也可以使用某些外部庫。OpenCV 對(duì)非商業(yè)應(yīng)用和商業(yè)應(yīng)用都是免費(fèi)（ FREE）的。 它還 為 Intel174。 Integrated Performance Primitives (IPP) 提供了透明接口。 這意味著如果有為特定處理器優(yōu)化的 IPP 庫， OpenCV 將在運(yùn)行時(shí)自動(dòng)加載這些庫 。【 11】 OpenCV作為開放的數(shù)字圖像處理和計(jì)算機(jī)視覺軟件平臺(tái)，有以下特點(diǎn)： ① 開放 C 源碼。 ② 基于 Intel 處理器指令 集開發(fā)的優(yōu)化代碼。 ③ 統(tǒng)一的結(jié)構(gòu)和功能定義。 ④ 強(qiáng)大的圖像和矩陣運(yùn)算能力。 ⑤ 方便靈活的用戶接口。 ⑥ 同時(shí)支持 MSWindows 和 Linux 平臺(tái)。 作為一個(gè)基本的計(jì)算機(jī)視覺、圖像處理和模式識(shí)別的開源項(xiàng)目， OpenCV 可以直接應(yīng)用于很多領(lǐng)域，作為二次開發(fā)的理想工具。 13 求解 圖像顏色分布直方圖 實(shí)例 以一幅彩色圖像為例， 求解其對(duì)應(yīng)的顏色分布直方圖，并附上求解過程的源代碼 ，對(duì)應(yīng)的程序流圖見圖 。 輸入圖像： 輸出直方圖分布圖像： include 14 include include iostream using namespace std。 int main( int argc, char** argv ) { IplImage * src= cvLoadImage(F:\\)。 IplImage* hsv = cvCreateImage( cvGetSize(src), 8, 3 )。 IplImage* h_plane = cvCreateImage( cvGetSize(src), 8, 1 )。 IplImage* s_plane = cvCreateImage( cvGetSize(src), 8, 1 )。 IplImage* v_plane = cvCreateImage( cvGetSize(src), 8, 1 )。 IplImage* planes[] = { h_plane, s_plane }。 /** H 分量劃分為 16 個(gè)等級(jí)， S 分量劃分為 8 個(gè)等級(jí) */ int h_bins = 16, s_bins = 8。 int hist_size[] = {h_bins, s_bins}。 /** H 分量的變化范圍 */ float h_ranges[] = { 0, 180 }。 /** S 分量的變化范圍 */ float s_ranges[] = { 0, 255 }。 float* ranges[] = { h_ranges, s_ranges }。 /** 輸入圖像轉(zhuǎn)換到 HSV 顏色空間 */ c