我應該使用什麼數據結構來查找類似的字符串？

我應該使用什麼數據結構來查找類似的字符串？例如，當您向Google查詢字符串「hapyp brithdya」時，Google會詢問您是否指「生日快樂」，這個字符串與以前拼錯的字符串「hapyp brithdya」非常相似。我應該使用什麼數據結構來查找類似的字符串？

什麼數據結構在空間和時間上都能最有效地完成這種操作？

請幫忙。您的時間非常感謝。

來源

2011-07-04 Daniel Johnson

在您的例子（說）「尿布生日」，只顯示不同的話由他們的字母排列組成。你是否也想找到「相似」的單詞，但實際上有不同的字母（例如「happy」和「hbppy」）？ – huitseeker

是的，的確如此。我也想得到像「開心」或「hbppy」 –

既然你問了一個數據結構，我會推薦Levenshtein automata。

這些可以擴展爲一個概率變量，返回字符串最有可能（根據語料庫統計）校正。請參閱Google的Peter Norvig撰寫的文章"How to Write a Spelling Corrector"，其基本思路是：結合Levenshtein自動機需要一些有限狀態傳感器的知識。有關更多詳情，請參閱Hassan, Noeman and Hassan。

來源

2011-07-04 16:43:29

Google使用的學習機制是搜索歷史記錄。例如，我搜索了「hapyp brithdya」，然後意識到拼寫不正確，因此沒有選擇任何鏈接。我的下一個搜索將是「生日快樂」正確的拼寫。從這一系列的搜索谷歌可以發現，「hapyp brithdya」實際上意味着「生日快樂」。

另一種基於相同線條的計分機制可幫助谷歌提供更多可接受的拼寫更正，即搜索「hapyp brithdya」，導致用戶點擊包含「生日快樂」的鏈接（由Google搜索建議）」。這增加了「生日快樂」的接近「hapyp brithdya」相比，這是存在的鏈接，用戶沒有訪問

來源

2011-07-04 17:41:29 Akhil

我應該使用什麼數據結構來查找類似的字符串？

回答

相關問題