摘要：本文同時(shí)發(fā)在我的博客上，歡迎在百度或者搜索的時(shí)候，有時(shí)會(huì)小手一抖，打錯(cuò)了個(gè)別字母，比如我們想搜索，錯(cuò)打成了，但神奇的是，即使我們敲下回車(chē)，搜索引擎也會(huì)自動(dòng)搜索而不是，這是怎么實(shí)現(xiàn)的呢本文就將從頭實(shí)現(xiàn)一個(gè)版的拼寫(xiě)檢查器基礎(chǔ)理論首先，我們要確定

本文同時(shí)發(fā)在我的github博客上，歡迎star

在百度或者Google搜索的時(shí)候，有時(shí)會(huì)小手一抖，打錯(cuò)了個(gè)別字母，比如我們想搜索apple，錯(cuò)打成了appel，但神奇的是，即使我們敲下回車(chē)，搜索引擎也會(huì)自動(dòng)搜索apple而不是appel，這是怎么實(shí)現(xiàn)的呢？本文就將從頭實(shí)現(xiàn)一個(gè)JavaScript版的拼寫(xiě)檢查器

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

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

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

P(O)我們可以看作是O出現(xiàn)的概率，是先驗(yàn)概率，這個(gè)我們可以從大量的語(yǔ)料環(huán)境中獲取

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

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

這部分的實(shí)現(xiàn)我參考了natural的代碼，傳送門(mén)

首先是構(gòu)造函數(shù)：

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是語(yǔ)料庫(kù)，在構(gòu)造函數(shù)中我們對(duì)priorList中的單詞進(jìn)行了出現(xiàn)次數(shù)的統(tǒng)計(jì)，這也就可以被我們看作是先驗(yàn)概率P(O)

接下來(lái)是check函數(shù)，用來(lái)檢測(cè)這個(gè)單詞是否在語(yǔ)料庫(kù)中出現(xiàn)

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

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

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是一個(gè)數(shù)組，它的第一項(xiàng)是只有原始單詞的數(shù)組，第二項(xiàng)是存放距離原始單詞編輯距離為1的單詞數(shù)組，以此類(lèi)推，直到到達(dá)了指定的最大編輯距離maxDistance

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

插入一項(xiàng)，比如ab->abc

替換一項(xiàng)，比如ab->ac

刪除一項(xiàng)，比如ab->a

前后替換，比如ab->ba

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

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);
    });
};

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

我們來(lái)測(cè)試一下：

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

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

上面的實(shí)現(xiàn)方法是先獲取了單詞所有指定編輯距離內(nèi)的候選項(xiàng)，而在語(yǔ)料庫(kù)單詞較少的情況下，這種方法比較耗費(fèi)時(shí)間，我們可以改成先獲取語(yǔ)料庫(kù)中符合指定最短編輯距離的單詞

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

leetcode情況下的狀態(tài)轉(zhuǎn)換方程：

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

其中當(dāng)word1[i-1]===word2[j-1]時(shí)，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)

拿到語(yǔ)料庫(kù)中符合指定最短編輯距離的單詞在對(duì)先驗(yàn)概率作比較，代碼如下：

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];
};

這份代碼還有很多可以優(yōu)化的地方，比如check函數(shù)使用的是indexOf判斷單詞是否在語(yǔ)料庫(kù)中出現(xiàn)，我們可以改用單詞查找樹(shù)(Trie)或者h(yuǎn)ash的方式加速查詢