4

我正在挑选我的一个旧项目，其中有效性和效率是关键。我解析了 100 GB 的 XML 数据。对于每个 XML 树（数以百万计），都使用一些 XML 属性，从中扣除模式。不过，对于这个问题，我将大大简化事情 - 但重要的是要记住有大量数据，快速处理以及以 XML 格式整齐地存储结果很重要。此外，还需要遍历生成的 XML 树。事实上，它将作为BaseX中使用的自定义索引机制，但我稍后会谈到这一点。

从每棵树（及其子树，但现在不重要）创建一个基于根节点的直接子节点的模式。作为一个基本示例，采用以下 XML 树：

<node letter="X">
  <node letter="A"/>
  <node letter="B"/>
  <node letter="C"/>
  <node letter="D"/>
</node>

该模式是通过获取所有孩子的字母属性并将它们排序并连接它们来创建的。在这种情况下，模式将是ABCD。

对于每棵树，还生成所有可能的子树（顺序不重要，最小组合 2），即所有可能的子树组合，并生成它们的模式。我不包括组合树的 XML，但除了 之外，可能的模式ABCD将是：

AB
ABC
ABD
AC
ACD
AD
BC
BCD
BD
CD

在层次结构中，它们看起来像这样（注意终端节点中的重复）。

模式树视图

此外，我们开始的完整模式应该在生成的 XML 中以某种方式指示，以表明它是树中的“主要”模式。最终，我想恢复从给定模式派生的所有模式（参见稍后）并将这些模式过滤为仅作为“主要”模式的模式。

从查询的角度来看，您可以argue that I am doing a bottom-up look-up. If I am looking for a generalized pattern, e.g. AB, the more specific patterns should also be found becauseABCD is part of。因此，如果我要使用上面的数据寻找模式AB，我会想找到

ABCD
ABC
ABD

很明显，这里有两个步骤。首先，概括一个级别：AB -> ABC,ABD然后ABC->ABCD（ABD->ABDC当然，每个结果应该只找到一次）。中间步骤对我来说ABC也ABD很重要，而不仅仅是最终ABCD结果。

我面临的问题是如何有效地存储一棵树，例如图像中呈现的树，以便它 1. 以我讨论的方式易于查询；2.尽可能稀疏而不丢失任何节点；3.高效搭建。后一点对于这个问题不太重要，因为我将自己实现构建脚本——这将在 Python 3.6 中完成。

到目前为止，我的想法是拥有一个相当扁平的结构，通过“coindexing”直接父节点来工作。它看起来像这样：

<tree>
  <node pattern="AB" index="1">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="8"/> <!-- ABD -->
  </node>
  <node pattern="AC" index="2">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="9"/> <!-- ACD-->
  </node>
  <node pattern="AD" index="3">
    <parentnode coindex="8"/> <!-- ABD -->
    <parentnode coindex="9"/> <!-- ACD -->
  </node>
  <node pattern="BC" index="4">
    <parentnode coindex="7"/> <!-- ABC -->
    <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="BD" index="5">    
      <parentnode coindex="8"/> <!-- ABD -->
      <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="CD" index="6">    
      <parentnode coindex="9"/> <!-- ACD -->
      <parentnode coindex="10"/> <!-- BCD -->
  </node>
  <node pattern="ABC" index="7">    
    <parentnode coindex="11"/> <!-- ABCD -->
  </node>
  <node pattern="ABD" index="8">    
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="ACD" index="9">   
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="BCD" index="10">    
    <parentnode coindex="11"/> <!-- ABCD -->    
  </node>
  <node pattern="ABCD" index="11" isMain="true"/>
</tree>

通过这样做，我想可以得到所有链接在一起的模式。例如，如果我现在要查找 AB，我希望到达该节点 children ( parentnode) 并获取这些索引并使用这些索引来查找直接父节点。然后应该重复该过程，直到没有元素留下协索引（例如ABCD在这种情况下）。

想象一下，有成千上万个这样的 XML 元素，主要的元素用isMain. 请注意，这isMain不一定是没有父节点子节点的模式！结果是所有原始 XML 树的累积。这意味着在某些情况下，一种模式可能是主要模式，而在其他情况下，它可能是组合的一部分。在这种情况下，node 用表示，isMain因为在原始 XML 中有“某些树以这种模式作为其主要模式”。

到目前为止，这只是我的想法，但我不确定是否有更好的方法，或者更重要的是，是否可以在 BaseX 中轻松查询。基本上，对于给定的输入AB，我想pattern通过使用索引来检索所有相关的 s（ABC、ABD、ABCD），然后通过仅检索 where 来过滤这些结果isMain="true"。我期待看到更好的想法，以及在 BaseX 中查询它们的方法。如果我的想法不错，那么我希望看到一种在单个 xquery 表达式中捕获查询的好方法。

4

1 回答 1

2

通过将分层数据放入平面结构而不是仍然使用 BaseX（一种高效的 XML 处理器），我不太了解您想要实现的目标。

我认为将数据放入它已经表示的逻辑结构并使用索引来有效地查询数据更自然（也更快）。

因此，您只需按原样使用层次结构，例如：

<tree>
    <node pattern="ABCD">
      <node pattern="ABC">
        <node pattern="AB"/>
        <node pattern="AC"/>
        <node pattern="BC"/>
      </node>
      <node pattern="ABD">
        <node pattern="AB"/>
        <node pattern="AD"/>
        <node pattern="BD"/>
      </node>
    </node>
</tree>

所以，我猜你是因为性能原因选择了这种格式。但是当你建立你的数据库时，你应该创建一个属性索引，即你所有的属性值都会被索引。通常，对于更常见的查询，它应该被重写，但您可以直接使用属性索引。例如，我有一个 50GB 以上的数据库，其中包含英文维基百科的转储。例如，我选择搜索一个页面List of Dragon Ball characters：

db:attribute("wikipedia", "List of Dragon Ball characters")/parent::*

这在我的机器上执行大约需要 20 毫秒。

所以类似地，你可以简单地搜索模式并爬上你的树：

db:attribute("<YOUR_DB>", "AB")/ancestor::node/@pattern => distinct-values()

鉴于您首先使用索引，然后简单地上升父母，这应该尽可能快。

于 2018-06-29T09:15:45.180 回答