我有一個縮寫列表，例如「ccd」，「bbq」，「phd」等。匹配像「ccd」，「bbq」，「phd」等縮寫字母與一組字符串中最相似的字符串
例如，讓我們「燒烤」，我們試圖映射此abbrevation到字符串列表，
燒烤國家 - 實際的答案應該是這個
燒烤煙霧和燒烤
啤酒和燒烤蓋茨
我們如何決定縮寫屬於哪個字符串。我曾嘗試通過KMP和Longest Common Subsequence算法使用字符串匹配，並增加了對以前匹配的字符串添加更多值的調整。
有沒有什麼數據結構可以幫助解決這類問題，或者有哪些算法可以處理這種情況？
謝謝！
啊，共謀問題。我的專長。
查看它的一種方法是將字典作爲拼寫糾正問題。你想要的是有兩個組件，一個由j_random_hacker指出的編輯距離度量和一個列出所有可接受的縮寫的字典。您可能希望在詞典中包含一個計數，以便更常用的長格式計數更多。
編輯距離模型將通過針對評估指標進行調整來確定。有法術在http://alias-i.com/lingpipe/demos/tutorial/querySpellChecker/read-me.html
檢查你將不會被使用的語言模型來評估編輯，但它會爲您建立的性能指標，編輯距離等一個很好的教程...
布雷克
澄清後續問題：
您的指標將由系統的性能驅動。你看看系統的功能是什麼，錯了什麼，然後你修改編輯距離來更好地建模你想要的。
因此，詞典的分數可以是詞組是否在詞典中。我將從第一個字符匹配開始，在短語中每個單詞得分爲-1，在'and'這個短語中爲-1個跳過的功能單詞，跳過首字母縮寫中的一個字母爲-5。因此，通過查看字典的「bbq」可以與得分爲-8（-1 + -1 + -1 + -5）的「Beer and Bakes Gates」相匹配
「燒烤國家」將需要編輯那比分更好。所以同一個單詞中的字母得分爲-5，跳過的單詞是-6.5（-.5 + - 。5 + - 。5 + -5），這是一個更好的分數。如果您需要任何通用性，這些編輯成本必須在您擁有的幾千個示例的訓練集中進行平衡。
您好布雷克，請讓我知道我可以用來評估編輯的所有指標。我所能理解的是，通過檢查縮寫的字符是否與字符串中的順序相同，我可以減少要比較的字符串的數量（即可接受的完整縮寫形式的字典）。 –
對不起，這麼晚回覆。編輯在答案中作出。 –
謝謝布雷克，會考慮這些方面，看看系統是如何運作的。 –
在您做任何事情之前，您需要一種評分縮寫與字符串匹配程度的方法;那麼問題就成爲決定哪個字符串得分最高的問題（在最壞的情況下，您只需計算每個字符的得分，並選出最高的字符）。評分比賽有多種方式，但我想不出任何明顯比「BBQ Smoke and Grill」更高的「燒烤國度」 - 無論如何，*您必須決定使用哪種評分功能。 –