摘要：本文同時發在我的博客上，歡迎在百度或者搜索的時候，有時會小手一抖，打錯了個別字母，比如我們想搜索，錯打成了，但神奇的是，即使我們敲下回車，搜索引擎也會自動搜索而不是，這是怎么實現的呢本文就將從頭實現一個版的拼寫檢查器基礎理論首先，我們要確定

本文同時發在我的github博客上，歡迎star

在百度或者Google搜索的時候，有時會小手一抖，打錯了個別字母，比如我們想搜索apple，錯打成了appel，但神奇的是，即使我們敲下回車，搜索引擎也會自動搜索apple而不是appel，這是怎么實現的呢？本文就將從頭實現一個JavaScript版的拼寫檢查器

首先，我們要確定如何量化敲錯單詞的概率，我們將原本想打出的單詞設為origin(O)，錯打的單詞設為error(E)

由貝葉斯定理我們可知：P(O|E)=P(O)*P(E|O)/P(E)

P(O|E)是我們需要的結果，也就是在打出錯誤單詞E的情況下，原本想打的單詞是O的概率

P(O)我們可以看作是O出現的概率，是先驗概率，這個我們可以從大量的語料環境中獲取

P(E|O)是原本想打單詞O卻打成了E的概率，這個可以用最短編輯距離模擬概率，比如原本想打的單詞是apple，打成applee(最短編輯距離為1)的概率比appleee(最短編輯距離為2)自然要大

P(E)由于我們已知E，這個概念是固定的，而我們需要對比的是P(O1|E)、P(O2|E)...P(On|E)的概率，不需要精確的計算值，我們可以不用管它

這部分的實現我參考了natural的代碼，傳送門

首先是構造函數：

function SpellCheck(priorList) {
    //to do trie
    this.priorList = priorList;
    this.priorHash = {};
    priorList.forEach(item => {
        !this.priorHash[item] && (this.priorHash[item] = 0);
        this.priorHash[item]++;
    });
}

priorList是語料庫，在構造函數中我們對priorList中的單詞進行了出現次數的統計，這也就可以被我們看作是先驗概率P(O)

接下來是check函數，用來檢測這個單詞是否在語料庫中出現

SpellCheck.prototype.check = function(word) {
    return this.priorList.indexOf(word) !== -1;
};

然后我們需要獲取單詞指定編輯距離內的所有可能性：

SpellCheck.prototype.getWordsByMaxDistance = function(wordList, maxDistance) {
    if (maxDistance === 0) {
        return wordList;
    }
    const listLength = wordList.length;
    wordList[listLength] = [];
    wordList[listLength - 1].forEach(item => {
        wordList[listLength].push(...this.getWordsByOneDistance(item));
    });
    return this.getWordsByMaxDistance(wordList, maxDistance - 1);
};
SpellCheck.prototype.getWordsByOneDistance = function(word) {
    const alphabet = "abcdefghijklmnopqrstuvwxyz";
    let result = [];
    for (let i = 0; i < word.length + 1; i++) {
        for (let j = 0; j < alphabet.length; j++) {
            //插入
            result.push(
                word.slice(0, i) + alphabet[j] + word.slice(i, word.length)
            );
            //替換
            if (i > 0) {
                result.push(
                    word.slice(0, i - 1) +
                        alphabet[j] +
                        word.slice(i, word.length)
                );
            }
        }
        if (i > 0) {
            //刪除
            result.push(word.slice(0, i - 1) + word.slice(i, word.length));
            //前后替換
            if (i < word.length) {
                result.push(
                    word.slice(0, i - 1) +
                        word[i] +
                        word[i - 1] +
                        word.slice(i + 1, word.length)
                );
            }
        }
    }
    return result.filter((item, index) => {
        return index === result.indexOf(item);
    });
};

wordList是一個數組，它的第一項是只有原始單詞的數組，第二項是存放距離原始單詞編輯距離為1的單詞數組，以此類推，直到到達了指定的最大編輯距離maxDistance

以下四種情況被視為編輯距離為1:

插入一項，比如ab->abc

替換一項，比如ab->ac

刪除一項，比如ab->a

前后替換，比如ab->ba

獲取了所有在指定編輯距離的單詞候選集，再比較它們的先驗概率：

SpellCheck.prototype.getCorrections = function(word, maxDistance = 1) {
    const candidate = this.getWordsByMaxDistance([[word]], maxDistance);
    let result = [];
    candidate
        .map(candidateList => {
            return candidateList
                .filter(item => this.check(item))
                .map(item => {
                    return [item, this.priorHash[item]];
                })
                .sort((item1, item2) => item2[1] - item1[1])
                .map(item => item[0]);
        })
        .forEach(item => {
            result.push(...item);
        });
    return result.filter((item, index) => {
        return index === result.indexOf(item);
    });
};

最后得到的就是修正后的單詞

我們來測試一下：

const spellCheck = new SpellCheck([
    "apple",
    "apples",
    "pear",
    "grape",
    "banana"
]);
spellCheck.getCorrectionsByCalcDistance("appel", 1); //[ "apple" ]
spellCheck.getCorrectionsByCalcDistance("appel", 2); //[ "apple", "apples" ]

可以看到，在第一次測試的時候，我們指定了最大編輯距離為1，輸入了錯誤的單詞appel，最后返回修正項apple；而在第二次測試時，將最大編輯距離設為2，則返回了兩個修正項

上面的實現方法是先獲取了單詞所有指定編輯距離內的候選項，而在語料庫單詞較少的情況下，這種方法比較耗費時間，我們可以改成先獲取語料庫中符合指定最短編輯距離的單詞

計算最短編輯距離是一種比較經典的動態規劃(leetcode:72)，dp即可。這里的計算最短編輯距離與leetcode的情況略有不同，需要多考慮一層臨近字母左右替換的情況

leetcode情況下的狀態轉換方程：

dp[i][j]=0 i===0,j===0

dp[i][j]=j i===0,j>0

dp[i][j]=i j===0,i>0

min(dp[i-1][j-1]+cost,dp[i-1][j]+1,dp[i][j-1]+1) i,j>0

其中當word1[i-1]===word2[j-1]時，cost為0，否則為1

考慮臨近字母左右替換的情況，則需要在i>1,j>1且word1[i - 2] === word2[j - 1]&&word1[i - 1] === word2[j - 2]為true的條件下，再作min(dp[i-1][j-1]+cost,dp[i-1][j]+1,dp[i][j-1]+1,dp[i-2][j-2]+1)

拿到語料庫中符合指定最短編輯距離的單詞在對先驗概率作比較，代碼如下：

SpellCheck.prototype.getCorrectionsByCalcDistance = function(
    word,
    maxDistance = 1
) {
    const candidate = [];
    for (let key in this.priorHash) {
        this.calcDistance(key, word) <= maxDistance && candidate.push(key);
    }
    return candidate
        .map(item => {
            return [item, this.priorHash[item]];
        })
        .sort((item1, item2) => item2[1] - item1[1])
        .map(item => item[0]);
};
SpellCheck.prototype.calcDistance = function(word1, word2) {
    const length1 = word1.length;
    const length2 = word2.length;
    let dp = [];
    for (let i = 0; i <= length1; i++) {
        dp[i] = [];
        for (let j = 0; j <= length2; j++) {
            if (i === 0) {
                dp[i][j] = j;
                continue;
            }
            if (j === 0) {
                dp[i][j] = i;
                continue;
            }
            const replaceCost =
                dp[i - 1][j - 1] + (word1[i - 1] === word2[j - 1] ? 0 : 1);
            let transposeCost = Infinity;
            if (
                i > 1 &&
                j > 1 &&
                word1[i - 2] === word2[j - 1] &&
                word1[i - 1] === word2[j - 2]
            ) {
                transposeCost = dp[i - 2][i - 2] + 1;
            }
            dp[i][j] = Math.min(
                replaceCost,
                transposeCost,
                dp[i - 1][j] + 1,
                dp[i][j - 1] + 1
            );
        }
    }
    return dp[length1][length2];
};

這份代碼還有很多可以優化的地方，比如check函數使用的是indexOf判斷單詞是否在語料庫中出現，我們可以改用單詞查找樹(Trie)或者hash的方式加速查詢