第 1 章  緒論

1.1 課題背景及意義
在這樣一個(gè)科技不斷進(jìn)步的時(shí)代里，信息量無時(shí)無刻不在增加，數(shù)據(jù)量急劇膨脹。面對(duì)這樣一種情況，數(shù)據(jù)處理工作變得越來越困難，如何快速地從互聯(lián)網(wǎng)的信息庫(kù)中尋找我們需要的信息正成為一個(gè)亟需解決的問題。 當(dāng)今社會(huì)信息交互日益頻繁，隨著社會(huì)的發(fā)展、科技的進(jìn)步，不難發(fā)現(xiàn)：傳統(tǒng)的基于關(guān)鍵字的查詢已經(jīng)無法滿足信息交流的需求。可以看這樣一個(gè)例子，某用戶想要找到關(guān)于“windows  XP 操作系統(tǒng)”相關(guān)信息，但因?yàn)橛脩粲洃洸磺寤蜉斎腭R虎錯(cuò)誤，在向數(shù)據(jù)庫(kù)中輸入信息時(shí)卻輸入成“windo XP 操作系統(tǒng)”。那么數(shù)據(jù)庫(kù)最終可能無法返回給用戶所需要的信息。如果使用字符串相似連接技術(shù)，當(dāng)用戶記憶不清或輸入馬虎錯(cuò)誤，在向數(shù)據(jù)庫(kù)中輸入信息時(shí)卻輸入成“windo XP操作系統(tǒng)”。那么最終也是可以返回給用戶所需要“windows XP 操作系統(tǒng)”相關(guān)信息。因此，如何以最快的速度從海量的數(shù)據(jù)庫(kù)中找到用戶所需及其相似的結(jié)果，是本文努力研究方向。 早期關(guān)于字符串相似連接問題的研究主要用于解決信息檢索、生物信息學(xué)、數(shù)據(jù)集成等方面的相似連接問題。直到目前，以上幾個(gè)問題依舊是字符串相似連接能夠不斷向前發(fā)展的驅(qū)動(dòng)力。 隨著計(jì)算機(jī)的普及，互聯(lián)網(wǎng)技術(shù)的的廣泛應(yīng)用，信息已經(jīng)實(shí)現(xiàn)了全球共享。文本成為信息存儲(chǔ)和傳播的主要形式。在面對(duì)大量的文本信息時(shí)，人們通常不知所措。通過信息檢索，能從海量的文本中快速地、準(zhǔn)確地找到所需要的信息。但想要在浩瀚如海的信息中甚至包含錯(cuò)誤信息的數(shù)據(jù)庫(kù)中找出與給定文本相似的信息，這就需要依靠字符串的相似連接的方法。 在當(dāng)今社會(huì)，學(xué)術(shù)論文抄襲問題十分嚴(yán)重。如何有效地展開防止抄襲學(xué)術(shù)成果越來越受到社會(huì)的重視，在這種情況下出現(xiàn)了許多學(xué)術(shù)不端檢測(cè)系統(tǒng)。在這些檢測(cè)系統(tǒng)中，字符串的相似連接是根本[1]。 
........

1.2 國(guó)內(nèi)外研究現(xiàn)狀
國(guó)內(nèi)在字符串相似性連接的研究主要包括英文字符串的相似度連接，中英文結(jié)合的相似字符串的連接以及中文字符串相似性連接，而國(guó)外的研究主要集中在英文字符串的相似度連接。中文字符串相似性連接主要被應(yīng)用在中文信息檢索、過濾、OCR 辨認(rèn)、以及中文文本比較等領(lǐng)域�，F(xiàn)有的字符串相似相似性連接方法根據(jù)處理特征的不同，大致可以分成兩類：基于語法的相似性連接、基于語義相似性連接[4-9]。 基于語法的相似性連接實(shí)際上也就是基于字符串的相似性連接，這類研究在國(guó)內(nèi)外也較多�；谔卣鞯南嗨菩赃B接首先需要提取字符串特征，然后根據(jù)相似度的度量方法，計(jì)算出兩個(gè)字符串間的相似度并給出評(píng)價(jià)標(biāo)準(zhǔn)。目前，字符串的特征提取方法主要有基于字符的 q-gram 等和基于 token 的方法。衡量字符串相似度的方法主要有 Jaccard 相似度，Cosine 相似度，編輯距離（Edit Distance），混淆字符集，混淆字符矩陣或是 n 元相似度算法，在以上相似度的計(jì)算方法的基礎(chǔ)上，提出了許多用于完成兩個(gè)字符串相似度連接的算法，如 Part-Enum，All-Pairs-Ed，Ed-Join 以及基于 Trie 樹的算法等。這些算法根據(jù)其處理策略可以分為兩類：(1)先過濾后提煉的方法，如 Part-Enum，All-Pairs-Ed 以及 Ed-Join 算法；(2)基于 Trie 樹的處理方法，如 Trie-Traverse，Trie-Dynamic，Trie-PathStack等[10-18]。 兩個(gè)不同的句子不同詞可能表述著相同的意思（比如同義詞），這是基于語法的相似性連接無法解決的問題�；谡Z義的相似性連接在基于語法的相似性連接的基礎(chǔ)上增加了語義相似性連接部分。它是基于語法的相似性的一種延續(xù)和擴(kuò)展，在信息的表示和檢索中的極為重要�；谡Z義的相似性連接首先需要明確語義相似度的概念，找到衡量語義相似度的方法以及計(jì)算過程中需要考慮的因素。
.......

第 2 章  字符串相似性連接技術(shù)研究 

本章主要研究字符串相似性連接技術(shù)，首先詳細(xì)分析字符串相似性連接的過程，介紹了相關(guān)定義及概念；然后給出了字符串相似性連接中常用的相似度的度量方法以及相似性連接技術(shù)；最后分析了近年來研究最多的方法技術(shù)及現(xiàn)狀，找出不足和解決大規(guī)模字符串連接的關(guān)鍵。 

2.1 相關(guān)定義及概念
在使用中，由于 Hamming  Distance 針對(duì)兩個(gè)等長(zhǎng)的字符串，而在實(shí)際計(jì)算字符串相似度的過程中，給定的兩個(gè)字符串通常是不等長(zhǎng)的，所以在應(yīng)用Hamming  distance 時(shí)一般需要對(duì)給定的字符串做一些預(yù)處理。例如，先應(yīng)用n-gram 將給定的字符串轉(zhuǎn)換成一些長(zhǎng)度為 n 的子串集合，然后再結(jié)合一些基于集合的相似度算法進(jìn)而計(jì)算出兩個(gè)字符串間的相似度。但是在實(shí)際的應(yīng)用中，找到一種將兩個(gè)字符串轉(zhuǎn)化成等長(zhǎng)且保留原語義的有效的方法十分困難。 
.......

2.2 字符串相似度的度量方法

字符串的相似度是用于判斷兩個(gè)字符串是否相似的基礎(chǔ)，所以在字符串的相似性連接過程中，計(jì)算字符串間的相似度是至關(guān)重要的步驟。目前已經(jīng)存在眾多計(jì)算的字符串相似度的方法，大致可分為兩類：基于特征的字符串相似度的度量方法和基于集合的字符串相似度的度量方法[25]。 編輯距離是指兩個(gè)字串之間，從一個(gè)轉(zhuǎn)變?yōu)榱硪粋�(gè)所需經(jīng)過的最少編輯次數(shù)。許可的編輯操作包括將將一個(gè)字符替換成另一個(gè)字符，在字符串中插入一個(gè)字符，從字符串中刪除一個(gè)字符。此算法首先由俄國(guó)科學(xué)家 Levenshtein 提出的，故又叫 Levenshtein Distance。編輯距離算法的匹配過程是有序的，對(duì)順序的匹配十分有效。常用被應(yīng)用于拼寫檢查、語音識(shí)別以及 DNA 比對(duì)和自動(dòng)評(píng)分系統(tǒng)中。本文后續(xù)部分如無特殊說明默認(rèn)為使用編輯距離衡量?jī)蓚�(gè)字符串間的相似度[26]。 

........

第  3  章 基于內(nèi)存的并行化連接方法........ 16 
3.1 相關(guān)符號(hào)定義 .... 16 
3.2 Para-Join 算法框架 .......... 17 
3.3 Para-Join 的數(shù)據(jù)劃分及相似度計(jì)算 .......... 18 
3.3.1  數(shù)據(jù)劃分.......... 18 
3.3.2  相似度計(jì)算...... 20 
3.4 Para-Join 的連接過程 ...... 21 
3.4.1 Para-Join 算法的實(shí)現(xiàn) .... 21 
3.4.2 Para-RR 與 Para-RS 的實(shí)現(xiàn) ........ 23 
3.5 實(shí)驗(yàn)結(jié)果與分析 ....... 25
3.6 本章小結(jié) ..... 28 
第  4  章 基于 Spark 框架的 Spss-Join 算法 ...... 30 
4.1 常見的并行化處理框架 ......... 30 
4.2 MapReduce 在字符串相似度連接中的應(yīng)用 ..... 33
4.3 基于 Spark 框架的 Spss-Join 算法實(shí)現(xiàn) ...... 38
4.4 實(shí)驗(yàn)結(jié)果與分析 ....... 41
4.5 本章小結(jié) ..... 43 
第  5  章 系統(tǒng)原型..... 44 
5.1 系統(tǒng)框架 ..... 44
5.2 運(yùn)行結(jié)果 ..... 47 
5.3 本章小結(jié) ..... 48 

第 5 章  系統(tǒng)原型

本章結(jié)合基于內(nèi)存的 Para-Join 算法和基于 Spark 框架的 Spss-Join 算法，設(shè)計(jì)并給出了一個(gè)用于處理字符串相似度連接的系統(tǒng)原型。該系統(tǒng)主要分成五個(gè)模塊：輸入模塊、token 集劃分模塊、數(shù)據(jù)過濾模塊、數(shù)據(jù)驗(yàn)證模塊、輸出模塊。本章首先將詳細(xì)介紹這五個(gè)模塊，并給出相應(yīng)模塊中的 API 接口，最后通過一個(gè)真實(shí)案例的應(yīng)用來分析該系統(tǒng)。 

5.1 系統(tǒng)框架 
本節(jié)分別將從硬件架構(gòu)和功能框架兩方面來分析字符串相似度連接的系統(tǒng)的組成。如圖 5-1 所示，系統(tǒng)的物理部署可以劃分為 C/S 和 B/S 相結(jié)合的模式。對(duì)于主要的功能模塊以 C/S 模式部署在服務(wù)器上，token 集劃分模塊、數(shù)據(jù)過濾模塊和數(shù)據(jù)驗(yàn)證模塊，從而能夠快速的進(jìn)行相似性連接工作，將輸入數(shù)據(jù)集以及相似性連接的結(jié)果存儲(chǔ)于 HDFS 中；需要與用戶交互的輸入輸出模塊則同時(shí) B/S 和B/S 模式來構(gòu)建，用戶既可以通過 PC 客戶端又可以通過瀏覽器來訪問系統(tǒng)。 這兩個(gè)模塊主要用于與用戶交互，用戶可以同過輸入模塊上傳需要進(jìn)行處理的字符串集合，設(shè)置相關(guān)參數(shù)，例如相似度閾值。PC 客戶端的用戶界面如圖 5-3所示。輸入模塊首先會(huì)對(duì)用戶上傳的數(shù)據(jù)集進(jìn)行簡(jiǎn)單的預(yù)處理，例如將結(jié)構(gòu)化的數(shù)據(jù)去結(jié)構(gòu)化轉(zhuǎn)換成簡(jiǎn)單的字符串，以方便之后的模塊使用，接著將處理后的數(shù)據(jù)存入 HDFS 中。輸出模塊主要用于完成結(jié)果的查詢，用戶發(fā)出查詢請(qǐng)求后，該模塊將存儲(chǔ)在 HDFS 中的相似性連接結(jié)果取出并返回給用戶，該模塊會(huì)將相似對(duì)數(shù)以及連接用時(shí)等結(jié)果直接返回給用戶，對(duì)于相似對(duì)記錄會(huì)以文本的形式返回給用戶，需要用戶下載后才能查看。表 5-1 給出了相應(yīng)的 API 接口。 
.......

總結(jié)

在計(jì)算機(jī)應(yīng)用方面，字符串相似性連接是被廣泛研究的課題之一。它在眾多領(lǐng)域方面都有著重要應(yīng)用，如數(shù)據(jù)清洗和集成、附近重復(fù)文本檢測(cè)、協(xié)同過濾、生物信息序列比較等。目前，已有大量的字符串相似性算法被提出。本文在這些算法的基礎(chǔ)上，重點(diǎn)研究了并行化的字符串連接技術(shù)。下面給出本文的主要工作： 
(1) 提出了一種新的字符串相似度計(jì)算方法，它在過濾階段結(jié)合了頻率向量過濾和多匹配感知子串選擇（Multi-match-aware Substring Selection）技術(shù)，提高了過濾的強(qiáng)度。在過濾階段能夠淘汰掉更多的不相似對(duì)，從而減少的計(jì)算量提高了算法效率。 
(2) 提出了一種新的基于內(nèi)存的并行化字符串相似性連接算法——Para-Join，同時(shí)本文還提出了 Para-RR 和 Para-RS 算法，用于解決單個(gè)子集的自連接問題和不同子集間的連接問題。實(shí)驗(yàn)結(jié)果表明 Para-Join 算法在處理大量字符串相似性連接時(shí)比以往的算法更加高效，他擁有高可擴(kuò)展性。由于算法完全在內(nèi)存中運(yùn)行，內(nèi)存容量會(huì)限制對(duì)數(shù)據(jù)集的大小，同時(shí)對(duì)算法的效率產(chǎn)生較大的影響。另一方面，線程數(shù)量受到具體的應(yīng)用環(huán)境的影響，用戶無法在算法運(yùn)行前給出一個(gè)最優(yōu)的線程數(shù)。 
(3) 為了彌補(bǔ) Para-Join 的不足，本文研究了當(dāng)前流行的并行化處理框架Hadoop 和 Spark。重點(diǎn)研究了如何使用 MapReduce 編程模型解決大規(guī)模字符串相似度連接的問題。通過分析發(fā)現(xiàn)它擁有諸多優(yōu)點(diǎn)，例如算法不再需要明確指出線程數(shù)量，數(shù)據(jù)集的大小不再受內(nèi)存容量的限制。但讓也同時(shí)帶來了新的問題，由于 MapReduce 編程模型本身不支持迭代，使得在一次算法運(yùn)行中不得不多次開啟 map-reduce 任務(wù)，，另外由于其對(duì)編輯距離的支持較差，使得已有的大量高效的過濾驗(yàn)證策略不能被使用，降低了算法的效率。針對(duì)以上問題本文在Para-Join 的基礎(chǔ)上，提出了基于 Spark 框架的 Spss-Join 算法，它有效的解決了上述所有問題。 
(4) 本文最后在 Spark 框架的基礎(chǔ)上，設(shè)計(jì)并討論了一個(gè)用于處理大規(guī)模字符串相似性連接的并行化系統(tǒng)原型。
.........
參考文獻(xiàn)(略) 

本文編號(hào)：56661