在HashMap值上搜索子字符串

本文关键字：字符串 搜索 HashMap | 更新日期: 2023-09-27 17:51:21

给定一个HashMap，我想检索其值包含给定子字符串s的所有条目e(不区分大小写)。我正在寻找对后缀树(trie)的行子字符串索引的想法，这只适用于前缀/后缀匹配。

在HashMap值上搜索子字符串

基于广义后缀树的解决方案

后缀树不仅适用于后缀匹配。你可以这样做:

  • 用哈希表中的每个条目构建一个通用后缀树。注意，为了忽略大小写，您必须将所有字符串转换为任意大小写。在构建过程中，用一组共享叶子的字符串标记每个叶子(例如字符串hazelnut和coconut将共享代表nut, ut和t的叶子)
  • 从根目录开始:
    • 用子字符串s沿着树走(转换为第一步中选择的情况):您最终处于隐式状态(即在边缘的中间)或显式状态(您最终处于节点N)。
    • 如果你处于隐式状态，就取你所在边的目标节点，我们称该节点为N
  • 计算从N可以到达的所有叶子的字符串集的并集:你得到一个字符串集S
  • S是哈希表中包含子字符串S
    • 的所有字符串的集合。

复杂性分析

设K为表中字符串的个数。设Li为字符串Si的各自长度，设L =∑Li。树的构造将是O(L)。

下到节点N为 0(长度(s))。

现在棘手的部分开始了。列出一个节点可到达的所有叶子不会是线性的，但也不会太麻烦。

让Lmax = max(Li)，那么你可以通过遍历最多Lmax节点到达每个叶子，更准确地说，如果你从前面定义的N节点开始，你将到达中N的每个子叶子最多L(s) = Lmax - length(s)步骤。

从N开始的子树也具有广义后缀树的结构。它表示最多K个长度最多L(s)的字符串。这些字符串最多有L(s)个叶。所以对它们的迭代最多是O(K.L(s)2)

计算每个这样的叶子中字符串集合的并集，则不超过O([K.L(s)]2)。(实际上它更接近于O(K.L(s)2)，因为如果每个叶子在它的集合中有所有的原始K字符串，那么在扎根于N的子树中只有L(s)叶子)

。这将导致最坏情况下的总复杂度为:

O (L +长度(s) +(提供(s)] <一口> 2>

但是实际的使用复杂度会更接近:

O (L +长度(s) + k [L (s)] <一口> 2>

标准方法(遍历每个字符串并在每个字符串中搜索s)是:

O (∑(L <子> +长度(s))) = O (L + K.length (s))

但等待…我们总是查找子字符串s!因此，对于KMP算法的预处理只需要进行一次。这减少了这种方法的复杂性:

0 (L + length(s))

但是，为了从这种优化中获益，您必须自己编写它，而不是使用标准实现…

结论

假设您只需要在映射上测试一个字符串s，朴素的解决方案易于实现，易于理解，其总体复杂性不仅优于基于后缀树的方法，而且是最优的。所以你可以自信地坚持下去。

然而，如果你必须测试大量的Ks字符串sj，那么后缀树方法可以更好，因为它的总体复杂度最多为:

O (L + K <子>。(max(长度(s <子>))+ (K.max (L (s <子>)]<一口> 2>

而KMP方法将导致总复杂度为:

O (K <子>。L +∑(length(sj))) = O(Ks)。[L + max(length(sj))])

还请注意，由于后缀树是树形结构，如果没有巧妙地设计，内存访问和分配将发挥作用，并可能严重损害运行时间。

如果你愿意，我可以举一个例子(在c++中，但它仍然可以说明问题)。

相关文章：