字符串相似算法

Question

我有兩個字符串（他們將在最後一個簡單的數據庫描述），讓我們說他們是

1. 字符串答：「蘋果桔子椰子石灰吉米自助餐」
2. 字符串B：「汽車 自行車滑板」

我在找的是這個。我想要一個具有輸入「cocnut」的函數，並且輸出爲「字符串A」

我們可以在大小寫上有差異，並且拼寫不會總是出現在點上。如果您願意，我們的目標是「快速和骯髒」搜索。

是否有任何.net（或第三方），或推薦'喜歡算法'的字符串，所以我可以檢查輸入有一個'非常接近的片段'並返回它？我的數據庫將有50個條目，上衣。

Answer 1

你要搜索的是兩個字符串之間的edit distance。有很多實現 - here’s one from Stack Overflow itself。

既然你要搜索只一個字符串的一部分你想要的是一個局部最優比賽，而不是作爲計算通過這種方法一個全球性的比賽。

這就是所謂的local alignment problem並再次它是由一個幾乎相同的算法容易解決 - 唯一改變的事情就是初始化（我們不懲罰無堅不摧之前搜索字符串）和的選擇最佳值（我們不會懲罰之後搜索字符串）。