當前位置:成語大全網 - 新華字典 - 自然語言處理(NLP)知識整理及概述(二)

自然語言處理(NLP)知識整理及概述(二)

假設 a = {a-z, A-Z, ...} 是英語所有可能構成單詞的字母集合, a* 為由這個字母表所構成的任意有限長度的字符串集合。 其中所有有效的單詞構成的集合D是a*的壹個子集。而noise channel 是指從目的詞(即字典)與實際接收到的字符串x所構成的矩陣。

對於所捕獲到的,存在拼寫錯誤的字符串x, 目標是在字典中找到壹個詞w,使這壹情況出現的概率最大。 即:

由於用戶實際想拼寫的單詞是不確定的,因此需要生成壹個修正候選列表(candidate corrections),這個列表基於兩個規則:

因此, noisy channel 實際上可以理解為,用戶所輸入的壹個錯誤的字符串,經過怎樣的變換過程可以得到若幹個正確的單詞。變換的過程越多,相當於channel越長, 而找候選列表的過程也就是找channel最短的過程。

最我輯距離(minimum edit distance)是指從壹個string到另壹個string所需的最我輯步驟,包括:插入、刪除、替換。而采用這三種編輯手段計算所得的距離又稱為 Levenshtein distance 。這壹距離將所有操作的cost都記為1.

但嚴格來說,替換這壹操作等於先刪除再插入。因此這壹操作的cost可當成是2(更接近實際操作的cost)。 此外,對於 Damerau–Levenshtein distance ,這壹距離還新增了transposition of two adjacent characters 這壹操作。

統計概率的計算方法如下:

首先對錯誤統計的方式:

顯然,用戶想輸入across的概率最大,這樣候選詞列表就有了排序和過濾的依據(大概率的排在前面,概率過低的可以不顯示)。另壹方面,P(word) 也可以使用bigram,這樣就與上下文取得了聯系,能更好的預測用戶想要輸入的單詞。

有25%-40%的錯誤屬於 real-word error

這壹部分是language model與noisy channel model的結合。假設用戶輸入的所有單詞都沒有non-word error

舉個例子,用戶輸入 "two of thew":

僅考慮 two off thew, two of the, too of thew 的概率,取最大值。

Peter Norvig’s list of errors

Wikipedia’s list of common misspelllings

GNU Aspell

Hunspell

How to Write a Spelling Corrector