javascript - 获取两个 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) 应该导致:(就我的目的而言，没有“更改”的更改，例如，如果文件名发生更改，则它是一个新文件，而旧文件则为旧文件)其中一个被视为已删除而不是移动，并且如果其文件发生更改，则不包括目录)。

[
    {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”的数据结构(应该选择一个更具描述性的名称，但想不出一个)。这张 map 将是 dictionary .

我们的 map 由键值对组成。

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

因此，您提供的两个示例 XML 结构的映射将如下所示:

旧 map :

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

新 map :

{
   "/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 步:获取两张 map 之间的差异

现在我们将从 map 中得出更改。

基本上，我们要做的就是遍历旧 map 的路径，获取每个路径中的子集(从两个 map )，然后比较两组子集以获得我们需要的更改。

该步骤的功能如下:

// 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' } ]