在 Ruby 中构建独特树的最快/最短方法？

Question

假设树有一组定义的节点，从树中构建唯一的元素树的最快/最短/单行（不可能：p）方法是什么，其中许多元素在某些节点中重复/丢失（我们将使用这个算法来解决这个问题，这样我们就不必手动完成）。

它可以是 XML/JSON（哈希），或者其他。所以像这样：

root {
    nodes {
        nodeA {}
        nodeB {
            subNodeA {}
        }
    }
    nodes {
        nodeA {
            subNodeA {}
        }
        nodeB {
            subNodeX {}
        }
    }
}

...转换成这样：

root {
    nodes {
        nodeA {
            subNodeA {}
        }
        nodeB {
            subNodeA {}
            subNodeX {}
        }
    }
}

与 xml 相同：

<root>
    <nodes>
        <nodeA/>
        <nodeB>
            <subNodeA/>
        </nodeB>
    </nodes>
    <nodes>
        <nodeA>
            <subNodeA/>
        </nodeA>
        <nodeB>
            <subNodeX/>
        </nodeB>
    </nodes>
</root>

<root>
    <nodes>
        <nodeA>
            <subNodeA/>
        </nodeA>
        <nodeB>
            <subNodeA/>
            <subNodeX/>
        </nodeB>
    </nodes>
</root>

xml/json 文件可能相当大（1MB+），因此必须以深度优先的方式迭代每个元素，或者看起来需要一段时间。它也可以像上面的例子一样小。

Answer 1

这将为您提供一组独特的路径：

require 'nokogiri'
require 'set'

xml = Nokogirl::XML.parse(your_data)
paths = Set.new
xml.traverse {|node| next if node.text?; paths << node.path.gsub(/\[\d+\]/,"").sub(/\/$/,"")}

这可以让您开始吗？

[回复评论中的问题]

添加属性路径也很容易，但我们至少要多行一些：

xml.traverse do |node|
  next if node.text?
  paths << (npath = node.path.gsub(/\[\d+\]/,"").sub(/\/$/,""))
  paths += node.attributes.map {|k,v| "#{npath}@#{k}"}
end