C＃比较匹配单词的两个字符串

我有两个字符串包含由空格分隔的字母和数字。 ex “elza7ma wa2fa fel matab”and“2ana ba7eb el za7ma 2awy 2awy”C＃比较匹配单词的两个字符串

比较这两个字符串以找出它们是否有共同词汇的最快方法是什么？

我试图用string.split拆分其中的一个，并在整个单词数组上使用string.compare。但是由于我会比较很多字符串，所以速度很慢。

2010-09-24 Marwan

看来indexOf会比正则表达式工作得更快，但不知道它是否更快，然后string.compare :)。你可以尝试 – Danil 2010-09-24 07:45:28

你真的想*最快*吗？你可以在那个问题上工作几年*。我怀疑你想*速度够快，在这种情况下，你没有提供足够的信息来解决问题。 *什么是您的硬件，什么是您的时间预算，什么是典型的大小问题？* – 2010-09-24 15:29:29

另外，什么是“很多字符串”？下面的评论表明“很多”是数百。我会认为数百个是*数量极少的字符串*。这是否准确？我认为“很多”是数百万或数十亿字符串 - 如Bing所示，索引的字符串很多。如果不清楚问题的大小，很难给出一个很好的答案。 – 2010-09-24 16:05:46

LINQ的解决方案

"elza7ma wa2fa fel matab".Split() 
         .Intersect("2ana ba7eb el za7ma 2awy 2awy".Split()) 
         .Any(); 

// as a string extension method 
public static class StringExtensions 
{ 
    public static bool OneWordMatches(this string theString, string otherString) 
    { 
     return theString.Split().Intersect(otherString.Split()).Any(); 
    } 
} 

// returns true 
"elza7ma wa2fa fel matab 2ana".OneWordMatches("2ana ba7eb el za7ma 2awy 2awy");

来源

2010-09-24 07:43:21

'Split'没有超载需要一个'char'。也许最好也指定'RemoveEmptyEntries' – JaredPar 2010-09-24 07:45:56

你可以使用'Split（）'而不用任何参数。在这种情况下，它将使用空格，制表符和新行作为分隔符。 – Oliver 2010-09-24 07:50:51

这是真的更快，还是Intersect（）也循环通过这两个数组？ – Sjoerd 2010-09-24 07:52:01

我认为最简单的方法是将字符串分解成字和使用像HashSet<string>一组结构，重复检查。例如，

public bool HasMatchingWord(string left, string right) { 
    var hashSet = new HashSet<string>(
    left.Split(" ", StringSplitOptions.RemoveEmptyEntries)); 
    return right 
    .Split(" ", StringSplitOptions.RemoveEmptyEntries) 
    .Any(x => hashSet.Contains(x)); 
}

来源

2010-09-24 07:44:49 JaredPar

可能还想添加一个相等检查来处理冲突（如果有的话）。 – 2010-09-24 08:18:19

是否有人确定如果这是最好的方法性能明智？ – Marwan 2010-09-24 08:49:40

您可以通过单词拆分这两个字符串并构建两个哈希表/字典。然后通过两者并在第三个字典中添加递增int的键（Dictionary<string, int>）。如果第三个字典中的任何一个键的计数不止一个，那么这个词就是两个原始字符串。

我会认为解决这个问题的任何算法都会很慢 - 特别是对于大量的输入字符串/许多单词。

来源

2010-09-24 07:45:07 mbanzon

将所有单词添加到相同的HashSet并检查Add（）的返回值更简单。 – Sjoerd 2010-09-24 07:53:40

我重读了原来的问题 - 是的，它会简单得多。他只是问是否有任何字符都是用两个字符串表示的 - 而不是其中的哪一个，而不是多少次出现。 – mbanzon 2010-09-24 08:08:40

我可能会采取最初的性能命中并拆分字符串，然后按字母顺序和字长进行排序。如果您只需查明一个单词是否匹配，只要找到一个单词就会中断。一旦你有字母和长度的字母顺序拆分字符串数组，这限制了你必须做的比较次数。

来源

2010-09-24 07:45:37 Matt

最简单的方法是将所有单词与任何其他单词进行比较。这是一个简单的解决方案，但速度很慢。
另一种方法是对两个列表进行排序，然后比较前两个条目。像mergesort一样，但其目标是找到相同的单词。
另一种方法是将单词列表编译为树，并将单词与该树匹配。正则表达式可以做到这一点，或者你可以自己做。在你的例子中，第一个字母应该是2，b，e或z。这样，每个单词只被检查一次，并检查最少的字符数。

来源

2010-09-24 07:46:41 Sjoerd

C＃比较匹配单词的两个字符串

回答

相关问题