algorithm - 如何从中间搜索尝试

Question

我一直遇到这种情况，我有一个 trie 分支，我想在它的中间向下匹配。因此，例如，我可能有这种 trie 分支之类的东西。

foo {
  bar {
    baz {
      hello {
        world {
          123 {
            456 {
              abc {
                xyz
              }
            }
          }
        }
      }
    }
  }
}

这是一个大大缩短的版本。实际上，它可能是具有 100 多个级别的二进制 trie，例如 10101011011010100110000101......，如下所示:

1 {
  0 {
    1 {
      0 {
        1 {
          ...
        }
      }
    }
  }
}

但在使用字符串键的简化示例中，完整路径如下所示:

foo/bar/baz/hello/world/123/456/abc/xyz

尝试基本上从 trie 的顶部开始并部分或一直向下移动是很常见的。因此，您可能会在此处找到匹配项，位于部分路径。

foo/bar/baz/hello/world/123/

或者您可能会在这里找到一个:

foo/bar/baz/

这很容易尝试，您只需从顶部开始，然后逐步下降。它们的共同点是它们从分支的顶部开始。

但我想知道的是不同的。我想知道如何从某个地方的 trie 中间开始。因此，例如，我想这样匹配:

/world/123/456/

基本上就像一个正则表达式 */world/123/456/*，它在中间匹配。

问题是，如果 trie 是密集的，那么理论上可能有数千甚至一百万个节点分散在整个 trie 中。因此，在 /world/123/456/ 中向下匹配 5 层可能意味着在我们找到匹配项之前扫描 1000 个上层 trie 节点。

我想知道您在这种情况下会做什么，可能的解决方案是什么。我目前所能想到的就是以某种方式使分支中间成为它自己的顶级特里树，将特里树的嵌套部分复制到内存中的另一个地方。但这在空间和内存方面似乎效率低下且浪费空间，这就是为什么我想知道您如何解决这个问题。

Answer 1

trie 中的每个节点在技术上仍然是一个 trie。您可以将其视为该子树的根。

您可以通过保留一个哈希表来利用这一点，该哈希表将每个节点的值映射到 trie 中的相应节点。如果节点可以有重复值，则将每个值映射到节点列表。

如果您需要在 trie 的中间搜索一个值，您可以使用哈希表立即跳转到 trie 中以您的起始值开头的节点。然后对于这些节点中的每一个，您都可以搜索您的值，就好像该节点是某处顶级 trie 的根一样。