3

我想创建一个图书馆书名数据库，可以有效地搜索子字符串匹配。也就是说，如果我搜索“Programming”，那么将返回所有包含“programming”一词的书名。该数据库可以进行预处理，并将完全存储在内存中。

什么是有效的数据结构和搜索算法来解决这个问题？我想完全用 C++ 实现它，所以请不要使用 3rd 方库。

4

2 回答 2

7

后缀树是一种高效的子串搜索数据结构。

这个想法是：
创建你的后缀树数据结构，并从每个叶子连接到与这个后缀代表的书相关的条目。
在查询时 - 使用子字符串遍历树 - 并从您到达的终点（最长匹配） - 进行一些遍历（例如DFS）并检索与查询作为前缀的所有后缀相关的所有条目。

当然，如果您只想要单词而不是所有子字符串，则映射（基于树/哈希）可能就足够了，并且更容易实现和使用（map<string,list<book> >例如，类型应该是基于树的方法，它会映射从每个单词到包含标题中包含该单词的所有书籍的列表）。
您还可以使用trie来实现地图。

于 2012-12-09T15:52:01.077 回答
3

对于子字符串匹配，有一个简单的方案：将完整标题拆分为“块”并以下列方式创建数据库：

  • 每本书都有唯一标识（ID/指针）
  • 每个“块”指向一组书籍标识符

当用户查询系统时，以相同的方式将她的请求分成块以识别匹配的书籍。

通过这个简单的方案，您有 2 个功能定制点：如何派生块以及如何对书籍进行排名；和 1 点技术定制：如何“合并/加入”不同匹配块的集合，这取决于您想要对书籍进行排名的方式。

如何派生块？

一种简单（但有效）的方法是在单词边界上拆分：The C++ Programming Language变成{the, c++, programming, language}.

注意：通常，有些词会被忽略（列入黑名单）。例如，The可能出现在 80% 的标题中，因此大多数时候考虑它是没有用的。

注意：搜索可能不区分大小写。

如何对书籍进行排名？

一个简单的算法是返回所有匹配项。更好的方法是根据查询中与该 ID 匹配的块数对它们进行排名。一个更好的方法是对那些单词以与查询相同的顺序出现的标题（最长的子匹配）排名更高。当然，您也许应该考虑同义词。

排名可能是系统的核心，谷歌很受欢迎，因为它的排名算法运行良好，这意味着如果找到你想要的。

如何实现合并/加入？

除非您只想返回与原始查询中的所有块匹配的搜索结果（这很有用，但由于同义词而烦人），否则您应该保留有序集并为每个块构建它们的交集：

  • chunk1：{B1, B2, B7, B9, B15}
  • chunk2：{B1, B7, B8, B13, B15}
  • chunk3：{B1, B3, B4, B7, B9, B12, B13, B14, B15}

chunk1然后，与和的集合相交chunk2，导致{B1, B7, B15}与 相交chunk3（这不会改变任何东西）。

注意：从较小的集合开始可以让您保留较小的中间结果，从而加快结果。

注意：当一个小集合与一个更大的集合相交时，大集合的线性游走可能比二分搜索慢得多。

另一方面，如果您想对搜索结果进行排名，那么您可能需要保留地图 ID -> 分数作为中间结果。该映射可能是二叉搜索树或哈希映射（后者对于非常大的集合更快，但对于小型集合通常有一些开销）。

请注意，这个排名的东西通常很慢，但很容易并行化。这就是 Google 使用 MapReduce 所做的。

于 2012-12-09T16:48:53.187 回答