劉峻松 唐明靖 薛 崗* 楊成榮
1(云南大學軟件學院 云南 昆明 650000)2(云南師范大學生命科學學院 云南 昆明 650000)3(六盤水師范學院 貴州 六盤水 553004)
Stack Overflow是一個熱門的計算機編程領域的問答社區(qū),它為世界范圍內(nèi)的計算機編程愛好者提供了一個解決問題的平臺。因此論壇中的問答文本具有很高的價值,每年都有很多人以Stack Overflow中的問題答案文本為研究對象,在海量的文本數(shù)據(jù)中挖掘不同的信息,為不同領域的研究提供數(shù)據(jù)基礎。
由于Stack Overflow是一個開放式的問答社區(qū)平臺,其中所有的文本數(shù)據(jù)均為來自世界各地用戶的輸入,因此其文本數(shù)據(jù)中存在大量的拼寫錯誤。在對文本進行分析時,拼寫錯誤對基于統(tǒng)計學理論的很多分析方法來說是相對致命的。以分析熱門問題和熱搜問題為例,在通過關鍵詞進行分析和檢索的過程中,如果某段文本的語義中心詞存在拼寫錯誤,根據(jù)計算機的模式匹配原則,該文段將會被錯誤地認知或歸類,當錯誤詞匯出現(xiàn)的頻率較高時,對于統(tǒng)計結果乃至最終的分析結果都會產(chǎn)生較大的影響。絕大多數(shù)人類輸入的文字都會出現(xiàn)文本拼寫錯誤,而諸如Stack Overflow這種開放平臺下的自然語言文本來說,其中拼寫錯誤文本的數(shù)量更是不可忽視。
本文提出了一種基于詞向量的文本拼寫錯誤自動檢測算法,通過結合文段語義及部分計算機輸入習慣所造成的常見錯誤情況,對Stack Overflow中計算機編程領域的文本數(shù)據(jù)進行自動的單詞拼寫檢測和糾正。實驗結果表明,與現(xiàn)有的以編輯距離為基礎的候選詞檢測和糾錯方式相比,使用本文算法對文本進行自動校正后,所獲得的結果文本與標準文本對比,語義相似度更高,針對部分計算機編程領域的專業(yè)詞匯及縮寫等情況的檢測和糾正效果更好,且在面對海量文本數(shù)據(jù)時能夠做到快速自動檢測和糾正,從而驗證了基于Word2Vec的計算機編程領域詞語拼寫錯誤檢測算法在針對計算機編程領域自然語言文本的單詞拼寫自動糾錯問題中具有較好的效果。
單詞拼寫錯誤的檢測和糾正在自然語言處理領域是一個很早就已經(jīng)出現(xiàn)的問題,Kukich[1]使用UNIX實現(xiàn)了英文文本的拼寫檢查方法,同時提出了單詞拼寫錯誤應包括非詞錯誤(Non-word error)和真詞錯誤(Real-word error),這些理論為后續(xù)的單詞拼寫檢測和糾錯提供了基礎。Levenshtein[2]提出了編輯距離的概念,如今編輯距離被廣泛應用于單詞拼寫檢測和糾錯中,Soleh等[3]提出了使用詞法分析和查找字典的方式檢測錯誤詞匯,通過錯誤詞匯編輯距離構建候選詞集合,最后使用隱馬爾可夫模型對詞匯文本進行分析進而對候選詞集合的所有詞匯進行排序,選取序列中排列首位的詞匯作為錯誤詞匯的改正詞匯進行替換。謝文慧等[4]提出在編輯距離的計算中引入鍵盤物理布局這一因素,將鍵盤鍵位間的最短距離直接引入到編輯距離算法中,但該文使用絕對的物理距離作為參數(shù),實際上用戶的鍵盤輸入誤差僅存在于周圍的鍵位當中,更遠的鍵位距離值會對最終的判別產(chǎn)生負向的影響。且上述所有方法均是以字典和編輯距離為核心判斷標準,因此對于部分專業(yè)領域較強的特殊詞匯及字典中沒有記錄的網(wǎng)絡新興詞匯的檢測能力不強,甚至可能會出現(xiàn)誤判的情況,而且對于網(wǎng)絡開放社區(qū)的文本來說存在大量諸如用戶名、郵箱地址等特定且無實際意義的詞匯,該類詞匯可能由某個具有實意的單詞演變而來且二者編輯距離極有可能很小,對該類詞匯的誤判會對文段的語義產(chǎn)生較大影響。
Bergsma等[5]將N-gram模型引入到拼寫糾錯問題當中,基于統(tǒng)計語言模型,分別利用了有監(jiān)督和無監(jiān)督的方法,結合上下文語義對單詞進行拼寫糾錯。Kim等[6]結合了單詞的相似性和N-gram模型,使用N-gram模型計算的語義相似性對單詞的拼寫相似度進行修正,提高了拼寫糾錯的準確性,但是N-gram模型具有參數(shù)空間大且數(shù)據(jù)稀疏嚴重的弊端,因此在處理大量文本時效率較低。
目前從文本拼寫糾錯領域的研究情況看,大部分方法是基于文本拼寫特征或基于統(tǒng)計的詞匯替換方法進行詞語拼寫矯正,上述方法存在準確度低、速度較慢等問題,而本文算法以Word2Vec運算的詞向量構建文本的向量空間,通過余弦相似度構建與檢測詞匯語義相似詞匯的集合,結合余弦相似度、詞頻、基于鍵盤鍵位改進的文本編輯距離的復合評分標準來對錯誤詞匯進行檢測和糾正。相較于上述已有的方法,本文提出的方法復合了多種對詞匯正誤判斷及候選集合選取有影響的因素。通過實驗表明,本文方法能夠在保證語義的前提下自動對大量文本進行檢測和糾錯,并且對部分專業(yè)性較強的生僻詞匯、新詞匯、縮寫詞匯有較好的檢測和糾正效果。
為了表達詞與詞之間的關系,Hinton[7]提出了詞語的分布式表達形式,每個詞對應的分布式表達是一個低維度的實值向量,其中每一個維度均可以表示一個詞的潛在特征。通過對大量文本語料的分析和訓練,將已知文本中的每一個詞匯映射為低維向量空間中的一個向量,這個向量空間稱為詞向量空間,其中的每一個向量稱之為詞向量。在這個空間中引入“距離”的概念,這個“距離”一般使用向量間的余弦值,多維向量的余弦值由歐幾里得向量點積公式推導得出,以此值作為兩個詞語的余弦相似度[8]。假設空間內(nèi)現(xiàn)有兩個n維向量a=(A1,A2,…,An)、b=(B1,B2,…,Bn),向量夾角為θ,余弦相似度計算式表示為:
(1)
由于詞向量本身包含了詞語潛在的上下文特征,因此通過對向量間余弦值的計算可以判斷其對應詞匯之間在語義或者上下文使用上的相似度。
Word2Vec是在2013年由Google的Mikolov等[9-10]提出并實現(xiàn)的一種工具,用于快速地對文本進行訓練并獲得低維詞向量,其核心是一個淺層的神經(jīng)網(wǎng)絡。Word2Vec中包含了兩種訓練模型[10],分別為CBOW和Skip-gram,兩種模型如圖1所示。
(a) CBOW模型 (b) Skip-gram模型圖1 Word2Vec中的兩種訓練模型
可以看出,兩種模型均是包含輸入層、輸出層及映射層的淺層神經(jīng)網(wǎng)絡模型,核心理論是貝葉斯條件概率,研究w和Context(w)之間的條件概率關系,即P(w|Context(w))或P(Context(w)|w),此處Context(w)定義為詞語w的上下文,數(shù)學表達如下:
Context(wi)=wi-t,…,wi-1,wi,wi+1,…,wi+t
(2)
式中:wi表示當前詞匯;t表示納入上下文計算的詞匯數(shù)量,即從當前詞匯開始計算前后需要納入計算的連續(xù)詞匯的數(shù)量。CBOW模型是通過輸入上下文對其中詞匯進行預測,而Skip-gram與之相反,通過詞匯對上下文進行預測。Word2Vec為了提高訓練的效率,還提供了兩種優(yōu)化算法,分別是Hierachy Softmax和Negative Sampling,通過使用Word2Vec訓練可以輸出一組質量相對較高的低維詞向量,并且語義相近的詞匯將被映射到空間距離相近的位置上。
編輯距離(Levenshtein Distance)是Levenshtein[2]提出的方法,用于表示一個字符串轉變?yōu)榱硪粋€字符串所需的最小操作步數(shù)。一步操作包括刪除一個字符、增加一個字符和修改一個字符三種情況,假設現(xiàn)有字符串A和字符串B,使用Ai表示A字符串前i個字符構成的子串,同理使用Bj表示B字符串前j個字符構成的子串,用LD(i,j)表示字符串A和B之間的編輯距離,則根據(jù)編輯距離算法可得計算式:
(3)
本文以文本詞向量為詞義相似度的評判基礎,通過改進的編輯距離模型對詞義相似度的模型進行修正,綜合考慮文本的語義和編輯距離的影響提出一種文本相似度計算方法,以此為基礎提出了一種文本單詞拼寫檢測糾錯的算法。本節(jié)通過對編輯距離模型、綜合文本相似度模型及單詞拼寫錯誤檢測方法三個方面進行概述。
Levenshtein[2]提出的編輯距離可以一定程度的描述兩個單詞之間的拼寫相似程度,但是Stack Overflow是一個開放的網(wǎng)絡社區(qū),其中絕大多數(shù)詞匯都是通過計算機鍵盤進行輸入的,因此有一部分詞匯錯誤是鍵盤鍵位相近導致的誤操作所造成的。本文將在原始編輯距離公式上進行改進,將因鍵盤鍵位相近導致誤操作的情況納入編輯距離計算中。
本文使用無向圖的方式表示鍵盤鍵位,根據(jù)國際標準QWERTY鍵盤的物理鍵位位置,構建如圖2所示的無向圖。文獻[4]使用無向圖中的最短路徑作為距離引入到編輯距離當中,但實際上針對國際標準鍵盤布局,有一種較為常用的輸入指法,在該指法下,用戶在輸入的過程中,不同的輸入錯誤情況出現(xiàn)的概率會根據(jù)指法中鍵位的分布而存在偏差,鍵盤指法的分布如圖2所示。
圖2 鍵盤布局和鍵盤指法分布圖
文獻[11]中針對鍵盤指法提出了三種輸入錯誤的類型:(1) 錯誤字母與正確字母位于同一個手指負責的區(qū)域(此類錯誤情況定義為W1);(2) 錯誤字母與正確字母位于同一只手的相鄰手指負責的區(qū)域(此類錯誤情況定義為W2);(3) 錯誤字母與正確字母位于不同手的相鄰手指負責的區(qū)域(此類錯誤情況定義為W3)。
以單詞“word2vec”為例,與字母“w”相鄰部分的鍵位如圖3所示,用戶在執(zhí)行鍵入“W”的操作時,若錯誤輸入為“2”“S”則屬于W1情況,若錯誤輸入為“3”“Q”“E”“A”則屬于W2情況。
圖3 字母“W”相鄰布局圖
文獻[11]通過大量的統(tǒng)計實驗表明,上述三種錯誤情況出現(xiàn)的概率滿足如下關系:
(4)
式中:W1、W2、W3分別代表上文提及的發(fā)生三種輸入錯誤類型的事件;P(W)表示不同輸入錯誤類型所代表的事件的發(fā)生概率。因此,將上述無向圖改為加權無向圖,將邊賦予不同的權值。同樣以“word2vec”為例,如果使用圖的最短距離直接作為鍵盤鍵位對編輯距離的影響因子,則“mord2vec”和“tord2vec”的影響程度是不一樣的,但是實際上,一旦超過“相鄰”鍵位這個范疇,這種詞語中字符的區(qū)別則更傾向于不同單詞或其他錯誤情況,因此本文在上述基礎上引入一個閾值,當其最短距離超過閾值時,則認為該字符差異不是由鍵盤物理鍵位的誤操作引起的。
根據(jù)上述思路,首先根據(jù)三種錯誤情況出現(xiàn)的概率對鍵盤鍵位圖中各邊的權值進行設定,根據(jù)上述規(guī)則,設W1=1、W2=2、W3=3。盡管某些情況下,同一手指負責的區(qū)域出錯的可能性較大。由于兩個字母按鍵相隔距離較遠時,其混淆輸入的可能性將大幅度下降,因此在加權圖的距離計算時將距離乘跳數(shù)作為其距離的最終值,同時引入閾值T=4,將誤操作范圍界定于圖3所示的范圍內(nèi)。則任意兩個鍵盤可輸入字符串A和B之間的距離Dk的計算公式如下:
(5)
(6)
則推導可得任意兩個字符串A和B,改進后編輯距離的影響因子I(A,B)的計算式如下:
(7)
綜上,對原始編輯距離公式修正為:
LDk(A[i],B[j])=
(8)
基于詞向量關注每個詞匯上下文情況,而不關注詞匯拼寫本身的特性,且絕大部分拼寫錯誤詞匯,輸入者所想表達的語義與其對應的正確詞匯是一致的,因此錯誤詞匯的上下文特征與正確詞匯的上下文特征相似度較高,也就是在向量空間中二者詞向量間的夾角余弦值較小,因此將詞向量間的余弦相似度值與上述改進的編輯距離同時納入到綜合相似度評分的計算中。
對任意兩個詞A和B的綜合相似度評分S(A,B)進行計算,S(A,B)與A、B對應詞向量的余弦相似度成正比,與LDk成反比,由此可得S(A,B)計算公式為:
特深井實施應依據(jù)地層深度方向宏觀分布規(guī)律將特深井分為上部、中部和下部三段分別考慮。本文依據(jù)科學特深井地層深度方向的不同特點,以孔內(nèi)安全問題為技術主線,提出具有針對性的鉆孔安全技術措施,從而提出特深井施工技術體系初步方案及其重大關鍵技術構想。
(9)
式中:a、b表示詞語A、B所對應的詞向量;cos(a·b)表示A、B詞語對應詞向量的余弦相似度;LDk(A,B)表示改進的詞語A、B的編輯距離;max()表示選取最大值函數(shù);len()表示字符串長度。若兩個詞語的編輯距離等于最長詞語的字符數(shù),則意味著在本文模型中,這兩個詞匯沒有任何相似之處,因此將其相似度綜合評分直接定為0。
本文提出的算法會對文本中每一個詞語進行分析。對于每一個被檢測詞語,首先通過Word2Vec計算的模型獲得與當前詞語向量余弦語義相似度最高的十個詞語組成候選詞集合,分別對當前詞語和候選詞集合中的所有詞語計算綜合相似度評分,獲取評分最高的詞語,對比兩個詞語的詞頻。若當前被檢測詞語的詞頻低于候選集中評分最高的詞語,則使用該詞語替換當前詞語,達到詞語糾錯的目的。因此要對文本語料進行處理和訓練,獲得詞向量模型。首先對文本進行預處理,原始Stack Overflow的文本數(shù)據(jù)如下:
PyXML works well.
You didn t say what platform you re using, however if you re on Ubuntu you can get it with sudo apt-get install python-xml
. I m sure other Linux distros have it as well.
If you re on a Mac, xpath is already installed but not immediately accessible. You can set PY_USE_XMLPLUS
in your environment or do it the Python way before you import xml.xpath:
if sys.platform.startswith(′darwin′):
os.environ[′PY_USE_XMLPLUS′]=′1′
In the worst case you may have to build it yourself. This package is no longer maintained but still builds fine and works with modern 2.x Pythons.Basic docs are here.
Stack Overflow的原始文本是按照HTML的格式組織的,其中包含大量的HTML標簽和無意義的格式信息,因此對上述原始數(shù)據(jù)的處理步驟如下:
(1) 解析HTML結構文本獲得自然語言文本。在解析HTML文本的過程中,包含兩類標簽,一類是諸如