xml - 无法以XML表示的数据结构？

Question

不能(明智地)用XML表示的数据结构的例子是什么？这是一个面试问题，我对此一无所获。

Answer 1

tl; dr 我不认识，我尝试了很多数据结构。但是，某些表示形式的效率较低，因此即使完全明智，也不一定是最佳选择。

这是一个棘手的问题。 XML是一个非常不受限制的树，它已经覆盖了所有数据结构的一半。即使是最奇特，最复杂的树仍然是树-我仍然不太了解vBE trees的创建和操作，但是我知道它是一棵树，因此我可以将给定的vBE树变成XML。

为每个节点分配一个ID，或设计另一个轻量级方案来引用一个节点而不使其成为引用程序的子级，您可以构建任何类型的图而不会带来太多麻烦。图几乎是通用数据结构的全部和全部。例如，有向循环图如下所示:

<graph>
  <vertex id="1">
    <!-- vertex data -->
    <edge to="3"/>
  </vertex>
  <vertex id="2">
    <!-- vertex data -->
    <edge to="1"/>
    <edge to="3"/>
  </vertex>
  <vertex id="3">
    <!-- vertex data -->
    <edge to="1"/>
    <edge to="2"/>
  </vertex>
</graph>

很明显，这是如何映射到邻接表的。支持甚至更复杂的图形，例如超图(一个边可以包含任意数量的顶点)，您只需要一个单独的边列表，每个边都包含一个顶点引用列表(请参见下面的列表)。

更普通的数据结构甚至更容易映射到XML:

数组，列表，队列，堆栈和其他有序的平面集合:将每个项目作为一个节点，将它们放在一个<seq>父节点中，以便它们成为同级。

元组(k个值):为每个项目分配一个标识符，然后使它们成为属性。或者，创建一个带有k个子节点的<tuple>节点，由于保留了节点顺序(与属性顺序不同)，因此不需要标识符。

字典:将它们视为(键，值)元组的序列。

集合没有顺序，但是我知道的每个集合数据结构都会在内部对元素进行排序(通过比较，哈希和冲突，或者在幼稚的情况下仅通过插入顺序)。当您要求数据结构枚举其元素时，要么使用该顺序，要么使用元素产生的任何顺序(如果不同)。

缺少数据结构？将其编码为记录(将指针替换为图形所用的间接指针)，然后将记录映射到具有每个记录成员的子节点或属性的节点。对于某些事情，例如链表，这很难看，但是对于它们来说，如上所述，存在一个更简单的表示形式。

这些表示法都不能像实际处理的那样好，但是您可以很好地使用它们，并且在内存中构建真实的数据结构只是一个简单而又正确的库循环(例如，Python中的lxml)，部分原因是XPath)。

一类数据结构不能很容易地映射到树。 bool 矩阵，位掩码等通过将每个元素降至单个位而提高了效率，但是当您为每个元素(或每个 true元素或每个 false元素)使用几十个字节时， bool 矩阵，位掩码等将大大消耗遗迹)。但是，较少的以树为中心的编码可以解决该问题。例如，您可以为一维位掩码存储base64字符串，并为更高维度使用这些序列(包括 bool 矩阵)。连接这些位以形成一个数字，并在base64中对其进行编码-或者更确切地说，在网上进行编码，以避免进行大精度的算术运算。结果不是完全XML，但仍然足够简单以生成和解析。

因此，我无法为您提供无法用XML合理表示的数据结构。这太笼统了，特别是当我们利用将任意二进制数据嵌入到base64等中的能力时。如果您因为不是纯XML而拒绝它，那么请注意: 在纯XML中不能有效地表示位掩码和 bool 矩阵。但是请注意，纯XML编码仍然是明智的选择，它仅占用大量空间。通过仅存储一个稀有值并将另一个隐式化，即使假值之一的真值很少出现(例如非常密集或稀疏图的邻接矩阵)，也可以缓解这种情况。

但是，这并不意味着XML是编码这些数据结构的最佳选择，甚至不是一个好的选择。这是一种流行的数据交换格式，但是对于任何给定的数据结构，都有更简单，更有效的表示形式。因此，如果您不需要灵活性并负担得起一些额外的工作，请不要使用它。或使用其他通用数据格式之一。上面描述的所有编码在YAML中都可以完美地工作，而没有太多的冗长，并且在内置诸如映射和数组之类的东西时甚至可以更好地工作。树变得更加难看，因为您必须将它们编码为嵌套记录(阅读:列表/映射)。 ，但是无论如何，这就是您要用编程语言表示它们的方式。我也很确定JSON可以处理所有这些内容，但是由于我没有花费很多时间来生成和解析它(我使用XML和YAML做到了)，所以我不确定。