因此，我试图找出一种方法来获得两个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）的结果为：（出于我的目的，没有“更改”更改，例如，如果文件名更改，则它是一个新文件，而旧文件被视为好像已被删除并没有移动，并且如果目录更改，dir也将不包括在内。
[
{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。
欢呼声。
我根据您对问题的描述创建了一个简单的解决方案。它可能并不是真正的最佳选择，但可以完成工作（希望如此）。看看这是否是您需要的。
我们将使用xml-parse包来处理XML。
TL; DR：获取完整代码here。
因此，要解决此问题，我们将经历两个步骤。
STEP 1：创建XML文件的映射
让我们定义一个称为“ map”的数据结构（应该选择一个更具描述性的名称，但是想不到一个）。该地图将为dictionary。
我们的地图由键值对组成。
因此，您提供的两个示例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);
}
}
STEP 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' } ]
有一家名为DeltaXML的公司，其整个业务模型都是围绕解决此问题而建立的。我只提到这一点，以便您意识到自己正在解决一个不重要的问题。
例如，您说：忘记了，XML的顺序不必紧。
这说明了一个事实，人们希望进行比较以反映其特定XML词汇表的语义，而不仅仅是XML语法本身。显然，有许多XML词汇表，其中更改元素的顺序是一项重大更改。
即使使用纯文本或字符串，也有很多关于差异的学术文献。例如，请阅读David Birnbaum在XML Prague 2020（https://archive.xmlprague.cz/2020/files/xmlprague-2020-proceedings.pdf#page=57）上发表的有关XSLT 3.0中Needleman-Wunsch算法实现的论文。
当然，您可能无需完全深入研究该领域，就能发明出满足您特定需求的算法。但是至少要想得到一个好的答案，您需要更精确地定义您的要求。一个简单的例子并不构成规范。
此问题的一个特殊特征是，最佳算法（标识最小差异数的算法）可能非常耗时（也许为O（n ^ 3）），因此您可能需要在质量之间做出妥协答案和交付时间。