字符串匹配算法

说我有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

字符串匹配算法

回答

相关问题