發(fā)布時間：2016-06-13 05:40

第 1 章  緒論

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

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

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

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

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

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

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

........

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

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

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

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

總結(jié)

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

本文編號：56661