在詞典中查找最匹配的單詞

Question

我正在創建一個讀取掃描的手寫文檔並將其轉換爲文本的程序。被識別的單詞必須來自我創建的約300字的字典。例如，如果手寫文字被識別爲「heilo」，但我的字典只包含「hello」和「world」，它應該將其轉換爲「hello」。但是，如果它認爲它是「星球」，它就不應該與任何東西相匹配。我認爲一種可能的方法是創建一個關於識別單詞與字典中每個單詞的匹配程度的得分。如果它沒有得到最低分數，則找不到匹配。

我正在用C＃編寫應用程序。是否有任何圖書館/例子可以做這樣的事情，還是我必須從頭開始編寫所有的代碼？

感謝

Answer 1

標準庫中沒有任何內容可以計算單詞之間的距離，但在Internet上可以找到大量示例：查找"edit distance"或"Levenshtein distance"。這個想法是根據第一個字符串的變化數量來衡量相似性，以使其成爲第二個字符串。 「heil」和「hello」之間的距離爲2，因爲您需要用「l」（第一個編輯）替換「i」，然後附加「o」（第二個編輯）。

在尋找實現或實現自己的實現時，避免使用二維數組實現簡單的實現，因爲它不符合內存效率。使用修改O(min(m,n))內存要求而不是「天真」O(m*n)。

Answer 2

我手頭沒有lib添加到你所需要的，但在網上搜索知道你要計算的Levenshtein Distance可以幫助你在你的搜索。

Answer 3

也許你應該從拼寫檢查開始 - 有一個number of libraries available這樣做。

Answer 4

有一些C＃代碼片段在網上，這將讓球滾動：

萊文斯坦： http://www.dotnetperls.com/levenshtein

博耶 - 穆爾： http://www-igm.univ-mlv.fr/~lecroq/string/node15.html#SECTION00150

此基礎上，你可以輕鬆實現您自己的Word Matcher模塊。