字符串匹配算法

說我有3個字符串。然後再多一個字符串。
有沒有一種算法可以讓我找到前3個字符串中的哪一個匹配最多的第4個字符串？
沒有任何字符串會精確匹配，我只是試圖找到最接近的匹配。
如果算法已經存在於STL中，那會很好。字符串匹配算法

在此先感謝。

2012-01-13 Josh

**匹配**是一個非常主觀的術語。 – 2012-01-13 16:26:09

您可以查看[維基百科文章中的「字符串相似性度量」類別]（http://en.wikipedia.org/wiki/Category:String_similarity_measures），並查看其中哪些與您的想法最接近。 – ruakh 2012-01-13 16:28:45

define：最接近的。 – 2012-01-13 16:35:52

您沒有指定「你最匹配」的意思，所以我假設你沒有確切的要求。在這種情況下，Levenshtein distance在一個合理的度量。簡單地計算三個弦和四個弦之間的Levenshtein距離，然後選擇一個距離最遠的弦。

來源

2012-01-13 16:27:38 NPE

您可以實現Levenshtein Distance算法，它提供了一個非常好的衡量兩個字符串之間匹配程度有多接近的方法。它會測量爲了將一個字符串轉換爲另一個字符串而需要進行的擊鍵次數。你可以找到一個C++實現here。

Compute Levenshtein字符串＃4與您擁有的三個字符串之間的距離。選擇距離最短的字符串。

來源

2012-01-13 16:27:48 dasblinkenlight

令人遺憾的是，該實現中的C++程序的levenshtein距離不爲0.但是，我認爲將typedef固定爲向量>使其正確。 – xaxxon 2016-06-09 07:01:13

STL中沒有什麼東西準備好，但是你需要的是某種字符串度量。

使用Levenshtein distance如果字符串在某些拼寫錯誤之前是相似的，例如， Hello vs Helol。
使用Jaccard distance/Dice's coefficient關於這組n-grams如果字符串可能更劇烈地改變，如hello world與world hello。

來源

2012-01-13 16:31:04 ybungalobill

您有近似的字符串匹配問題。根據您要執行的匹配類型，您將使用不同的算法。有很多.. SOUNDEX,Jaro-Winkler,Levenstein Distance，metaphore ...等。關於STL，我不知道實現這些算法的任何函數，但你可以看看here爲一些soource使用C++。另外，請注意，如果您從數據庫中獲取字符串，那麼您的數據庫引擎很可能會實現一些算法（很可能是SOUNDEX）。

來源

2012-01-13 16:31:09

字符串匹配算法

回答

相關問題