获得两棵 XML 树之间差异的算法（JS 或伪代码）

Question

所以我想找出一种方法来区分两棵 XML 树（下面的示例）但无法想出任何办法。我需要结果是一个差异数组，数组中的每个元素都包含已更改的节点、更改方式（添加、删除）以及节点的路径。

编辑：忘了说，XML 的顺序无关紧要。我尝试使用 npm/dom-compare，但它并没有完全给出所需的结果（使用下面的示例），因为它不希望看到新标签（目录照片），但没有提供它发现的过去的相关信息意外标签。

1.

<dir name="rootDir">
    <dir name="childDir">
        <file name="hello.jpg"/>
    </dir>
    <file name="linux.txt"/>
    <file name="img.png"/>
</dir>

2.

<dir name="rootDir">
    <dir name="childDir">
        <file name="hello.jpg"/>
        <file name="interesting.brain"/>
    </dir>
    <dir name="photos">
        <file name="me.dng"/>
    </dir>
    <file name="img.png"/>
</dir>

我的 XML 来源将只包含和标签。

例如，在上面的两个 XML 文档中，compare(1, 2) 应该导致：（就我而言，没有变化 'changed'，例如，如果文件名发生变化，则这是一个新文件，旧文件被视为已删除而不是移动，如果文件更改，则不包括目录。

[
    {node: '<file name="interesting.brain"/>', path: '/rootDir/childDir' change: 'added'},
    {node: '<dir name="photos">', path: '/rootDir', change: 'added'}
    {node: '<file name="linux.txt"/>', path: '/rootDir', change: 'deleted'}
]

我的第一个想法是首先使用fast-xml-parser将XML字符串解析成JS对象，得到如下对象：

1.

{ dir: [
    {
        name: 'rootDir',
        dir: [
            {
                name: 'childDir',
                file: [
                    { name: 'hello.jpg' }
                ]
            }
        ],
        file: [
            { name: 'linux.txt' },
            { name: 'img.png' }
        ]
    }
] }

2.

{ dir: [
    {
        name: 'rootDir',
        dir: [
            {
                name: 'childDir',
                file: [
                    { name: 'hello.jpg' },
                    { name: 'interesting.brain' }
                ]
            },
            {
                name: 'photos',
                file: [
                    { name: 'me.dng' }
                ]
            }
        ],
        file: [
            { name: 'img.png' }
        ]
    }
] }

然而，这会导致额外的复杂性，因为生成的格式使用数组和对象，这至少会增加弄清楚如何区分两者的脑力工作量。它也可能慢一点，因为显然你必须首先解析 XML 字符串，更不用说添加第 3 方库了。

正在寻找可用于解决此问题的任何建议或伪代码算法。应该注意我正在使用 Typescript 并以 ES6 / Node.js.

为目标

干杯。

Answer 1

我已经根据您对问题的描述创建了一个简单的解决方案。它可能不是真正的最佳选择，但它可以完成工作（希望如此）。看看这是不是你需要的。

我们将使用 xml-parse 包来处理 XML。

TL;DR: 获取完整代码 here.

那么，为了解决这个问题，我们将分两步走。

第 1 步：创建 XML 文件的地图

让我们定义一个名为 "map" 的数据结构（应该选择一个更具描述性的名称，但想不出一个）。此地图将是 dictionary.

我们的地图由键值对组成。

关键是路径。我们的地图将包含 XML 结构中的所有现有路径。
值是另一个字典：
- 键是元素的名称。
- 该值为元素的标签。

因此，您提供的两个示例 XML 结构的地图将如下所示：

旧地图：

{
   "/rootDir":{
      "childDir":"dir",
      "linux.txt":"file",
      "img.png":"file"
   },
   "/rootDir/childDir":{
      "hello.jpg":"file"
   }
}

新地图：

{
   "/rootDir":{
      "childDir":"dir",
      "photos":"dir",
      "img.png":"file"
   },
   "/rootDir/childDir":{
      "hello.jpg":"file",
      "interesting.brain":"file"
   },
   "/rootDir/photos":{
      "me.dng":"file"
   }
}

从 XML 结构构建映射的递归函数如下所示：

// recursive function to build map
function buildMap(element, path, map) {
  map[path] = {}
  // const childElements = element.childNodes.filter(childNode => childNode.type === 'element');
  for (const childNode of element.childNodes) {
    // skip text (because the xml-parse package also returns the unnecessary texts in an XML structure, e.g. line breaks)
    if (childNode.type === 'text') continue;

    // process child element
    // add child element's name to indicate that this path has a child with this name
    // use child element's type (dir/file) as the value
    map[path][childNode.attributes.name] = childNode.tagName;

    // if child element is dir, process it recursively
    if (childNode.tagName === 'dir') buildMap(childNode, `${path}/${childNode.attributes.name}`, map);
  }
}

第 2 步：获取两个地图之间的差异

现在我们将从地图中导出更改。

基本上，我们要做的是遍历旧地图的路径，获取每条路径中的子集（从两个地图）并比较这两组子集以获得我们需要的更改。

这一步的作用如下：

// function to get the differences between two maps
function diffMaps(oldMap, newMap) {
  const changes = [];
  // traverse each path of the old map
  for (const key of Object.keys(oldMap)) {
    // get children in this path for both old map and new map
    const oldChildren = oldMap[key];
    const newChildren = newMap[key];
    changes.push(...diffChildren(key, oldChildren, newChildren));
  }
  return changes;
}

// function to get the differences between the children of two maps
function diffChildren(path, oldChildren, newChildren) {
  const changes = [];
  // traverse each child of the old children
  for (const key of Object.keys(oldChildren)) {
    // if new children also have that child ==> no change ==> remove that child from new children and continue
    if (newChildren[key]) {
      // the reason for deleting is that after we have deleted all the keys that are present in old children, the remaining keys in new children will be the newly added ones.
      delete newChildren[key];
      continue;
    }

    // new children don't have that child ==> deleted ==> add to changes
    const type = oldChildren[key];
    changes.push({
      node: type === 'dir' ? `<dir name="${key}">` : `<file name="${key}"/>`,
      path: path,
      change: 'deleted'
    });
  }

  // traverse each child of the new children and add them to changes
  for (const key of Object.keys(newChildren)) {
    const type = newChildren[key];
    changes.push({
      node: type === 'dir' ? `<dir name="${key}">` : `<file name="${key}"/>`,
      path: path,
      change: 'added'
    });
  }

  return changes;
}

最后：测试

现在我们有了必要的功能，只需插入我们的数据和运行 :)

const oldXmlString = String.raw`
<dir name="rootDir">
    <dir name="childDir">
        <file name="hello.jpg"/>
    </dir>
    <file name="linux.txt"/>
    <file name="img.png"/>
</dir>
`.trim();

const newXmlString = String.raw`
<dir name="rootDir">
    <dir name="childDir">
        <file name="hello.jpg"/>
        <file name="interesting.brain"/>
    </dir>
    <dir name="photos">
        <file name="me.dng"/>
    </dir>
    <file name="img.png"/>
</dir>
`.trim();

const oldXml = xml.parse(oldXmlString);
const newXml = xml.parse(newXmlString);

const oldRoot = oldXml[0];
const newRoot = newXml[0];

// maps with path as key and child nodes' names as value
const oldMap = {};
const newMap = {};

buildMap(oldRoot, `/${oldRoot.attributes.name}`, oldMap);
buildMap(newRoot, `/${newRoot.attributes.name}`, newMap);

const diffs = diffMaps(oldMap, newMap);
console.log(diffs);

输出：

[ { node: '<file name="linux.txt"/>',
    path: '/rootDir',
    change: 'deleted' },
  { node: '<dir name="photos">',
    path: '/rootDir',
    change: 'added' },
  { node: '<file name="interesting.brain"/>',
    path: '/rootDir/childDir',
    change: 'added' } ]

Answer 2

有一家名为 DeltaXML 的公司，其整个商业模式都是围绕解决这个问题而建立的。我只是提到这一点，所以你意识到你正在解决一个不平凡的问题。

比如你说：忘了说了，XML的先后顺序不用管。

这说明了这样一个事实，即人们希望通过比较来反映他们特定 XML 词汇表的语义，而不仅仅是 XML 语法本身。显然有很多 XML 个词汇表，其中改变元素的顺序是一个重大变化。

即使是纯文本或字符串，也有大量关于差分的学术文献。例如，阅读 David Birnbaum 在 XML 布拉格 2020 (https://archive.xmlprague.cz/2020/files/xmlprague-2020-proceedings.pdf#page=57) 上发表的关于在 XSLT 3.0 中实现 Needleman-Wunsch 算法的论文。

当然，您或许可以发明一种算法来满足您的特定需求，而无需对该领域进行彻底研究。但至少，要得到这个问题的正确答案，您需要更准确地定义您的需求。一个简单的例子不构成规范。

这个问题的一个特点是最优算法（识别最小数量差异的算法）可能非常耗时（可能为 O(n^3)），因此您可能需要在两者之间做出妥协答案的质量和交付它所花费的时间。

获得两棵 XML 树之间差异的算法（JS 或伪代码）

Algorithm (JS or Pseudocode) to get difference between two XML trees

javascript

xml

algorithm

pseudocode

typescript