[發(fā)明專利]一種輸入過程中的中文術(shù)語自動糾錯方法

無效

• 申請?zhí)枺?/td>: 200910023816.5
• 申請日: 2009-09-08
• 公開（公告）號: CN101639830A
• 公開（公告）日: 2010-02-03
• 發(fā)明（設(shè)計）人: 劉均;鄭慶華;沙莎;鄭成;周正
• 申請（專利權(quán)）人: 西安交通大學(xué)
• 主分類號: G06F17/28
• 分類號: G06F17/28;G06F17/30;G06F3/023
• 代理公司: 西安通大專利代理有限責(zé)任公司
• 代理人: 陸萬壽

1.一種輸入過程中的中文術(shù)語自動糾錯方法，其特征在于，按照如下步驟：

(1)以用戶的輸入中的每一個元素為一個Term，所述Term是漢字串、字母 串或者字母漢字混合串；

(2)采用Bloom濾波器的結(jié)構(gòu)快速判斷該Term是否是一個合法的術(shù)語；如 果Term是一個合法的術(shù)語，則將該Term進(jìn)行術(shù)語補(bǔ)全，否則對Term進(jìn)行術(shù)語 糾錯；所述術(shù)語補(bǔ)全是指對正確的短術(shù)語進(jìn)行補(bǔ)全提示；所述術(shù)語糾錯是指對錯 誤的輸入進(jìn)行糾正得到接近用戶本意的合法術(shù)語提示項(xiàng)；

所述術(shù)語補(bǔ)全和術(shù)語糾錯都采用了術(shù)語分簇以及Trie樹構(gòu)建和檢索機(jī)制；

所述采用Bloom濾波器的結(jié)構(gòu)快速判斷該Term是否是一個合法的術(shù)語是指 按照下列過程：

(a)按照公式(1)確定Bloom濾波器向量長度，

(12)k≈0.6185m/n---(1)]]>

其中，k為Hash函數(shù)的個數(shù)，m為Bloom濾波器的長度，n為構(gòu)建Bloom 濾波器的集合中元素的總個數(shù)，限制最大錯誤率為0.5％，公式(1)中m/n為16， 設(shè)n＝979，所以m約為979×16＝15664，這里選取m為最接近于15664的質(zhì)數(shù)15667；

(b)確定Hash函數(shù)個數(shù)為3；

(c)選擇Hash函數(shù)構(gòu)造Bloom濾波器的hash函數(shù)表：選出取模算法、PJW 算法和DJB算法3個獨(dú)立無關(guān)的Hash函數(shù)構(gòu)成構(gòu)造Bloom濾波器的hash函數(shù)表；

(d)構(gòu)造Bloom濾波器，其具體包括如下步驟：

Step1：一次將合法術(shù)語庫中的術(shù)語全部讀出，形成術(shù)語隊列，構(gòu)成構(gòu) 建Bloom濾波器的元素集合；

Step2：判斷是否已經(jīng)讀到術(shù)語隊列的尾部，如果是已經(jīng)讀到術(shù)語隊列 的尾部，結(jié)束構(gòu)造Bloom濾波器；如果不是已經(jīng)讀到術(shù)語隊列的尾部，進(jìn)入 Step3；

Step3：當(dāng)前指針?biāo)赶虻男g(shù)語依次經(jīng)過取模Hash、PJW?Hash、DJB?Hash 的計算，得到三個在0-15666的整數(shù)，分別令這三個數(shù)字所對應(yīng)的Bloom濾 波器中的位置處值為1；回到step2；

(e)基于Bloom濾波器判斷用戶輸入是否合法的工作機(jī)制為：

Step1：令用戶輸入依次經(jīng)過取模Hash、PJW?Hash、DJB?Hash的計算， 得到三個0-15666的整數(shù)；

Step2：檢查Bloom濾波器中對應(yīng)于上述三個整數(shù)的位置，如果對應(yīng) 位置處所有的值均為“1”，則該用戶輸入合法；否則判斷為不合法；

所述術(shù)語分簇的機(jī)制是根據(jù)拼音串與音調(diào)串兩個屬性對術(shù)語庫中的術(shù)語 進(jìn)行分簇，并將各術(shù)語簇到Trie結(jié)構(gòu)中，以便檢索術(shù)語的補(bǔ)全結(jié)果；所述分簇 是將具有相同屬性的元素歸在同一集合中；所述分簇包含第一層分簇和第二層分 簇；所述第一層分簇為將合法術(shù)語所對應(yīng)的全拼拼音作為第一屬性，每一種第一 屬性分別代表一個大分簇，并稱為該分簇的標(biāo)簽，標(biāo)簽所對應(yīng)的拼音串是該分簇 中所有術(shù)語全拼拼音串的子串或全部；所述第二層分簇為在每一個大分簇中，利 用第二個屬性音調(diào)串進(jìn)行第二層分簇，對于一個特定的大分簇，屬性音調(diào)串指的 是術(shù)語中對應(yīng)于該大分簇標(biāo)簽所在子串的音調(diào)或者音調(diào)串，將具有相同音調(diào)串屬 性的術(shù)語歸為同一小分簇；

所述Trie樹的構(gòu)建機(jī)制為：

Step1：令當(dāng)前節(jié)點(diǎn)為Trie樹的根節(jié)點(diǎn)；當(dāng)前轉(zhuǎn)移條件為插入詞的第一個 字母；

Step2：以當(dāng)前節(jié)點(diǎn)為基準(zhǔn)，查看節(jié)點(diǎn)數(shù)組中代表當(dāng)前轉(zhuǎn)移條件的單元， 如果該單元指向了一個子節(jié)點(diǎn)，則令當(dāng)前節(jié)點(diǎn)為該子節(jié)點(diǎn)，轉(zhuǎn)入Step3；否則生 成一個新的節(jié)點(diǎn)，令當(dāng)前節(jié)點(diǎn)數(shù)組中代表當(dāng)前轉(zhuǎn)移條件的單元指向這個新生成的 節(jié)點(diǎn)，同時令當(dāng)前節(jié)點(diǎn)為這個新節(jié)點(diǎn)，進(jìn)入Step3；

Step3：如果當(dāng)前轉(zhuǎn)移條件為檢索詞的最后一個字母，則進(jìn)入step4；若不 是，則令當(dāng)前轉(zhuǎn)移條件為插入詞的下一個字母，回到Step2；

Step4：如果當(dāng)前分簇是待插入分簇的最后一個分簇，則構(gòu)建過程結(jié)束Trie 樹的構(gòu)建機(jī)制；如果不是，取出下一個分簇，回到Step1；

所述Trie樹的檢索機(jī)制：

Step1：令當(dāng)前節(jié)點(diǎn)為Trie樹的根節(jié)點(diǎn)；當(dāng)前轉(zhuǎn)移條件為待匹配的拼音串 的第一個字母，當(dāng)前音調(diào)串為待匹配術(shù)語的音調(diào)串；

Step2：以當(dāng)前節(jié)點(diǎn)為基準(zhǔn)，查看節(jié)點(diǎn)數(shù)組中代表當(dāng)前轉(zhuǎn)移條件的單元， 如果該單元指向了一個子節(jié)點(diǎn)，則令當(dāng)前節(jié)點(diǎn)為該子節(jié)點(diǎn)，轉(zhuǎn)入Step3；否則轉(zhuǎn) 入Step5；

Step3：如果當(dāng)前轉(zhuǎn)移條件為檢索詞的最后一個字母，則查看當(dāng)前節(jié)點(diǎn)的 術(shù)語列表，若術(shù)語列表不為空，轉(zhuǎn)入step3.1；若術(shù)語列表為空，完全匹配不成 功，轉(zhuǎn)入Step5；

Step3.1：沿著當(dāng)前節(jié)點(diǎn)的術(shù)語分簇列表，用當(dāng)前音調(diào)串和各個分簇標(biāo)志 作比較，如果某一個分簇的標(biāo)志和當(dāng)前音調(diào)串一樣，則說明完全匹配成功，返回 小分簇的術(shù)語列表作為候選術(shù)語集合；否則，說明完全匹配不成功，轉(zhuǎn)入Step3.2；

Step3.2：返回當(dāng)前節(jié)點(diǎn)中的所有小分簇中的術(shù)語，整體作為候選術(shù)語集 合，結(jié)束Trie樹的檢索機(jī)制；

Step4：如果當(dāng)前轉(zhuǎn)移條件不是檢索詞的最后一個字母，則令當(dāng)前轉(zhuǎn)移條 件為檢索詞中的下一個字母，轉(zhuǎn)到Step2；

Step5：返回以當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)或祖先節(jié)點(diǎn)的所有終結(jié)點(diǎn)中術(shù)語，結(jié)束 Trie樹的檢索機(jī)制。