識別字符串中的相似性

我正在研究一個允許導入的文件被本地化爲其他語言的系統。識別字符串中的相似性

這主要是一個私人項目獲得MVC3，的EntityFramework，LINQ，諸如此類的竅門。因此，我喜歡做一些瘋狂的事情來增加最終結果，其中之一就是對類似字符串的認識。

想象一下，你有一個字符串下面的列表 - 從遊戲我已經在過去曾與借來的：

正如你可以看到，當用戶已經翻譯了第4串，以下4個份額有很多相似之處，在這種情況下：

考慮的第一個4串確實已經翻譯，當用戶從列表中選擇5號線，是什麼樣的算法或技術可以用來向用戶顯示「類似字符串」的子標題下的第一個字符串（以及其他可能的字符）？

編輯 - 在Levenshtein距離有點評論：我目前針對數據庫中的10K字符串。 Levenshtein Distance將每個字符串的字符串進行比較，因此在這種情況下爲10k x（10k -1）個可能的組合。我如何以可行的方式來解決這個問題？有沒有更好的解決方案，這個特定的算法？

有趣的問題。我不知道該從哪裏開始回答這個問題，但是生病了，看着。 – Gallen

編輯距離。其品種很多。而且相當直接。如果矩陣變大，可能在計算上很昂貴。 – DarthVader

你可以連接所有的字符串，然後通過空格分隔（使用正則表達式），然後用'.Distint（）'將其轉換並用替換執行翻譯。與此相關的問題是，並非所有的語言都會逐字翻譯。 – Jay

你可以看着Levenshtein Distance。低於某個閾值的那些將被認爲是相似的。兩個相同的字符串的距離爲零。

有一個C＃實現，除其他語言，在Rosetta Code。

2012-10-22 20:20:26 keyboardP

+1，只是推薦Levenshtein，你打我吧 – CaffGeek

我我確實碰到過這個算法，但坦率地忘記了這個名字，謝謝。我很想知道更多的答案，所以我會留下這個開放的一點;） –

這很好，我也有興趣看看別人是否有另一種解決方案:) – keyboardP

這將取決於數據的大小以及豐富的詞彙量。這裏的第一個想法：在地圖上標註的單詞爲字符串然後詞的對另一個地圖爲字符串也許如果數據不是字符串三胞胎爲字符串的巨大的地圖。刪除指向單個字符串的映射（這將顯着減少三元映射的數量）。將結果字典保存在磁盤或數據庫中，如果構建它需要時間。

現在給出一個字符串，你應該能夠快速地將它分成單詞，單詞對和三元組，並查找與之相關的所有字符串。你將需要發揮重量來匹配三字符匹配與四字匹配。即是「我是一個老人」，更接近「一位老人吃了胡蘿蔔」或「男人用箭射死了老狗」（聽起來像三胞胎比賽更重要）。

更新：如果在Microsoft SQL Server數據庫中可以使用全文搜索功能。我從來沒有嘗試過。你也應該看看Lucene。

2012-10-22 20:25:40

回答