当我们事先不知道有多少个哈希集时，在c#中获取两个以上哈希集的交集的最好方法

Question

我正在制作一个布尔检索系统，用于一些大的no。文档，其中我制作了一个哈希集字典，字典中的条目是术语，哈希集包含在其中找到术语的文档in。现在，当我想要搜索单个单词时，我只需输入该单词，然后使用查询中输入的单词对字典进行索引，并打印出相应的哈希集。但我也想搜索句子，在这种情况下，我将把查询拆分成单独的单词，并根据这些单词对字典进行索引，现在根据查询中的单词数量，将返回许多哈希集，现在我想将这些哈希集相交，这样我就可以返回在查询中找到单词的文档ids。我的问题是，获取这些哈希集的交集的最佳方法是什么？

现在我把哈希集放到一个列表中，然后取这两个数的交集。一次两个哈希集，然后取前两个结果的交集，然后是第三个结果，依此类推。

这是代码

Dictionary<string, HashSet<string>> dt = new Dictionary<string, HashSet<string>>();//assume it is filled with data...

while (true)
            {
                Console.WriteLine("\n\n\nEnter the query you want to search");
                string inp = Console.ReadLine();
                string[] words = inp.Split(new Char[] { ' ', ',', '.', ':', '?', '!', '\t' });

                List<HashSet<string>> outparr = new List<HashSet<string>>();
                foreach(string w in words)
                {
                    HashSet<string> outp = new HashSet<string>();
                    if (dt.TryGetValue(w, out outp))
                    {
                        outparr.Add(outp);
                        Console.WriteLine("Found {0} documents.", outp.Count);
                        foreach (string s in outp)
                        {
                            Console.WriteLine(s);
                        }
                    }
                }

                HashSet<string> temp = outparr.First();
                foreach(HashSet<string> hs in outparr)
                {
                    temp = new HashSet<string>(temp.Intersect(hs));
                }

                Console.WriteLine("Output After Intersection:");
                Console.WriteLine("Found {0} documents: ", temp.Count);
                foreach(string s in temp)
                {
                    Console.WriteLine(s);
                }

            }

Answer 1

您使用的原则是合理的，但您可以对其进行一些调整。

通过按大小对哈希集进行排序，您可以从最小的哈希集开始，这样就可以最小化比较的次数。

您可以在循环中执行相同的操作，而不是使用IEnumerable<>.Intersect方法，但前提是您已经有了一个哈希集。检查值是否存在于散列集中非常快，因此您只需遍历最小集中的项，并在下一个集中查找匹配值，然后将它们放入新的集中。

在循环中，您可以在开始时跳过第一项。你不需要把它和它本身相交。

outparr = outparr.OrderBy(o => o.Count).ToList();

HashSet<string> combined = outparr[0];
foreach(HashSet<string> hs in outparr.Skip(1)) {
  HashSet<string> temp = new HashSet<string>();
  foreach (string s in combined) {
    if (hs.Contains(s)) {
      temp.Add(s);
    }
  }
  combined = temp;
}

Answer 2

IntersectWith是一个很好的方法。如下所示：

            HashSet<string> res = null;
            HashSet<string> outdictinary = null;
            foreach(string w in words)
            {
                if (dt.TryGetValue(w, out outdictinary))
                {
                    if( res==null)
                        res =new HashSet( outdictinary,outdictinary.Comparer);
                    else
                    {   
                        if (res.Count==0)
                             break;
                        res.IntersectWith(outdictinary);
                    }
                }
            }
            if (res==null) res = new HashSet();
            Console.WriteLine("Output After Intersection:");
            Console.WriteLine("Found {0} documents: ", res.Count);
            foreach(string s in res)
            {
                Console.WriteLine(s);
            }

Answer 3

为了回答您的问题，您可能会在某一时刻找到一组包含单词a、b和c的文档，而另一组仅包含查询中的其他单词，因此交集在几次迭代后可能会变为空。您可以从foreach中检查这一点和break。

现在，我觉得这样做是没有意义的，因为通常一个搜索结果应该包含多个按相关性排序的文件。这也会容易得多，因为你已经有了一个包含一个单词的文件列表。从为每个单词获得的散列中，您必须计算文件ids的出现次数，并返回按出现次数降序排列的有限数量的ids。