1、在大數(shù)據(jù)的時代背景下，拼寫檢查、數(shù)據(jù)清洗、協(xié)同過濾等應(yīng)用成為研究熱點，而相似性連接作為這些眾多數(shù)據(jù)分析的基本操作有著廣泛的應(yīng)用價值，同時Google提出的MapReduce編程模型是處理海量數(shù)據(jù)最流行的并行計算模型之一，但因其不能較好的支持相似性連接算法，使得在MapReduce上進(jìn)行相似性連接成為大數(shù)據(jù)的一個重要可擴(kuò)展的研究領(lǐng)域。相似性連接中，以n-gram算法為基礎(chǔ)的傳統(tǒng)算法應(yīng)用領(lǐng)域非常廣泛，增加了錯誤拼寫對相似性度量的影響，但由于

2、該算法生成的標(biāo)記存在大量冗余，無形中增加了內(nèi)存空間的消耗以及運(yùn)行時間。隨后針對n-gram算法提出了改進(jìn)的ED-Join算法，在前綴篩選階段減少了前綴標(biāo)記的數(shù)量，但卻給每個標(biāo)記分配了位置因素，雖然運(yùn)行時間顯著減少，空間消耗減少卻不多。并且以n-gram算法為基礎(chǔ)的ED-Join算法并沒有在并行架構(gòu)下實現(xiàn)，無法適應(yīng)海量數(shù)據(jù)處理的要求，因此在海量的數(shù)據(jù)中改進(jìn)n-gram算法，減少冗余，減少空間消耗以及運(yùn)行時間成為亟待解決的問題。
　　

3、針對以上問題，本文改進(jìn)了傳統(tǒng)的n-gram算法以及ED-Join算法，提出一種支持MapReduce的新型算法-n-gram-imp算法。首先，該算法在劃分字符串時，用無冗余滑動窗口代替冗余滑動窗口，僅需選取少量的前綴標(biāo)記參加過濾即可，使空間利用效率以及運(yùn)行時間都得到了提升。其次，n-gram-imp算法生成的標(biāo)記無冗余，需要對篩選出的標(biāo)記進(jìn)行針對性的過濾操作，所以提出了Pre-imp前綴過濾算法。最后，在MapReduce計算模型上實