在Java中實現的最佳字符串匹配算法？

我想在Java中實現一個算法來查找最近似的字符串。在Java中實現的最佳字符串匹配算法？

我有station_names在的MySQL數據庫等 - 23 ST，233 ST，21 ST，14聖時代廣場，24 ST

，並且如果用戶輸入等23日站搜索字符串然後我應該返回23 ST和233 ST或者如果用戶輸入像時代廣場那麼結果應該是14時代廣場。

我在互聯網上發現了很多算法，但我很困惑要使用哪一種算法。

您能否給我推薦我可以用Java實現的最佳算法？

在此先感謝

2012-12-26 Deepu

*「你能給我推薦最好的算法嗎？」*我通常會選擇帶圓點的那種，因爲它更漂亮。當然，你對「更好」的定義可能不包括視覺效果，那麼爲什麼不告訴我們你的意思是更好？ –

感謝Andrew對你的回覆，最好的算法意味着會產生用戶想要搜索的最類似的字符串，例如，對於23 ST用戶可以給搜索字符串，如23rd Station/23 Station/23rd St ect – Deepu

http://en.wikipedia.org/wiki/String_searching_algorithm討論一些流行的算法，但你需要在Java中實現它們 – AurA

有很多方法可以做到這一點。例如，您可能會說21 ST比233 ST更接近23rd station。你必須弄清楚你想要什麼，找到最適合的方法。

很可能您可能需要多種方法然後對結果進行評分。這是我會做的。

您可以通過提供大型樣本數據測試套件並找出哪種方法（或組合）能夠提供最高的成功率來測試不同的方法。

2012-12-26 12:40:39

感謝Peter的回答，我想返回用戶想要搜索的最類似的字符串，例如** 23 ST **（實際電臺名稱）用戶可以輸入搜索字符串 - ** 23rd Station/23 Station/23rd St ** – Deepu

您可以定義「最相似」嗎？雖然這是大多數人的想法，但對於計算機，您需要正式定義它。 –

要回答你的問題，通常沒有最好的算法，只有在你的特定情況下效果最好的算法。

您將需要定義一個或多個度量標準來測量輸入和DB中的字符串之間的差異，然後按照得分對結果進行排序（請參閱String metric）。

問題是最相似的字符串並不總是最接近的地址。這就是爲什麼我說你必須定義你自己的指標。

2012-12-26 12:54:04

謝謝桑迪，我會試試這個。 – Deepu

回答