在錄入文本里，有2種字符：“有效字符”和“多打字符”。“有效字符”是指它在標準文本里可以找到唯一的“對應字符”。“對應字符”當然與它相同，但是，相同的字符不一定就是“對應字符”。例如：
? ? 標準文本：我們班里的學生大多數是女生。
? ? 錄入文本：我們班里喜歡數學的學生大多數是女生。
錄入文本的第一個“數”字，在標準文本里是找不到“對應字符”的。
? ? 我的算法思路是這樣的：對于錄入文本里的每一個字符（包括看不見但是占位置的全、半角空格；包括看不見又不占位但長度又不為零的回車），在標準文本里尋找“對應字符”。（如何確認“對應字符”是個難點，我在后面會提出解決方法，那其實是本文的重點。尋找“對應字符”首先是尋找“相同字符”，只有“相同字符”才有資格做“對應字符”）
? ? 根據尋找的結果（有或沒有），自然就解決了“漏”和“多”的問題，既可以得到字符（串）的內容，又可以統計數字。至于“錯字”，其實就是“漏”與“多”在對應位置所出現的綜合事件，比如把“你說”錯打成了“他說”，漏了“你”；多了“他”。在下面的描述中我會細說的。
? ? 下面用文字和圖片來描述一次“尋找”的過程。

圖1中n1、n2分別是尋找的第一個字符的位置，內容是zn1、zn2 。我稱為“起始字符”。如果相同，那比較簡單。（不是本文的重點，后面會提出一個小細節）。在圖1中兩個字不相同。那么把標準文本里的下一個字符與zn2進行比較（標準文本的起始字符仍然記住是zn1）。如果最終找到（z1）。（并確定是“對應字符”，下同）。那么從n1（包括zn1）到z1(不包括z1)的字符（串）就是“漏字符（串）”，標準文本下一輪尋找（比對）從z1之后的那個字符開始；錄入文本下一輪尋找從zn2之后的那個字符開始。（即zn2是“有效字符”）。
如果zn2始終沒找到“對應字符”（圖2）

，那么zn2就是“多”字符，標準文本下一輪尋找仍然從n1開始；錄入文本下一輪尋找從zn2之后的那個字符開始。（錄入文本始終是一個一個的往后“走”，不管這個字是“有效”還是“多打”）。?? ? 這里說一下“錯字”的問題。在每次發生“多”結果時，要有一個變量記錄連續“多”的累計字符數（不是最終評分的累計數），一旦發生了“漏”結果，就要馬上算出“錯”字符內容和個數（當然也可以算出準確字符的內容，調整“漏”和“多”的內容和數量，包括重新涂顏色）然后把“多”的累計字符數清零。這里的細節就不多說了。
下面借助幾張截圖來說說怎樣判斷“對應字符”。這是本文的重點。

圖3：錄入文本里的加紅圈的字被誤判為“有效字符”；圖4里標準文本里的加紅圈的字被誤判為“對應字符”，造成的后果雖然不影響總分，但是看上去別扭且不大合理，本來連續的漏或錯被分成了2段，中間夾了一個對應字符和有效字符。
而圖5

更是誤判了，錄入文本里原本有效的“BCD”成了“多”字符，而標準文本里的“BCD”又成了“漏字符”。真實情況是“多打”了1個“E”。造成這個結果，是因為標準文本里的那個“E”被誤判成錄入文本第一個“E”字符的“對應字符”了。那是我用“人腦”發現的。怎樣讓程序來判斷呢？?我以本文開頭的2行文字為例：圖6

先定義2個12個字符的字符串：在標準文本里的 ?串1=“數是女生。 ? ?”和錄入文本的 ?串2=“數學的學生大多數是女生。”（它們的首字符就是被判斷是否“對應字符”的字符“數”）
用一個十多行左右代碼的函數判斷“有幾個不顛倒、可以有間隔的共同字符”。上面的共同字符數是5。
下一步，我先把上述標準文本里的“BCD”+“E”表述成“疑漏字符串”，圖6中標準文本里“的學生大多數”。把錄入文本在n2后面的區域表述為“未比對區域”。
接著，用For 循環分別把“疑漏字符串”中的每個字符在“未比對區域”尋找相同的字符，若找到，就用該字符為首字符用標準文本和錄入文本組成2個也是12個字符的字符串3和字符串4（圖6右下方的上下2個）。

然后用同樣的函數求出它們的共同字符數。一旦發生“第2個共同字符數大于第1個共同字符數”（圖6這里是10）時，那個疑似“對應字符”（數）即被否定。退出For 循環，確認標準文本上的這個“數”字符不是“對應字符”而繼續在標準文本里找，也就是說，這一輪尋找還沒有結束。這樣就避免了誤判。等到這一輪尋找結束，確定是“多”還是“漏”，本輪尋找才算結束，然后更新“起始字符”，進入下一輪尋找“對應字符”.....。

將這樣的“尋找”在錄入文本里從頭到尾走一遍，就完成了“文本比對”。

如果你對上面的描述已經理解的話，你試試在圖1中找出2對（4個）字符串，看會不會發生“第2個共同...大于...數”，從而否定“E”(z1）是“對應字符”。

前面圖3圖4里的問題，也是用“繼續找相同字”--“比較2個共同字符數”的方法（不再贅述），不過尋找的區域不同，也不用For 循環，因為只有1個要找的字符。前面為什么要for每個字要找，是因為那個“未比對區域”有可能恰好漏打了某個字，以致找不到。

總結

以上是生活随笔為你收集整理的文本比对的一种算法探索、比对算法中的难点及解决方法---学习笔记记录的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。