如何从中间搜索尝试

Question

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

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

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

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

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 节点。

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

Answer 1

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

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

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

如何从中间搜索尝试

How to search tries from the middle

algorithm

search

trie

data-structures