PQGrams

作者：Cathal Garvey，版权所有 2017，许可协议：LGPLv3或更高；请参阅license.txt

关于

PQ-Grams是一种用于有效评估树结构/内容相似性的方法，适用于可以抽象为嵌套（标签，子项）对的树结构。基于这个前提，一个PQ-Gram是之前的P祖先标签（包括当前节点），以及下一个Q子标签。PQ-Gram配置文件是树中所有PQ-Grams的集合，包括填充在每对子项左右以及祖先顶部的“填充”节点。

这些PQ-Grams可以类似于NLP中的n-Grams或shingles，通过集合并和集合差度量来评估树之间的相似性。原始用途执行类似集合差的操作来计算近似树编辑距离。

PQ-Grams尚未得到广泛实现，这是件遗憾的事。在审查和修改PyGram一段时间后，我决定我想在Rust中实现这个算法以提高速度和可移植性。具有讽刺意味的是，PyGram迁移到Python3使我能够添加一些尚未在Rust中实现的高效功能，例如LRU缓存，但我希望将来能够完成这项工作。

下一步

我想构建Rust/Python绑定，以接受LXML树，以评估使用PQGrams对HTML片段进行结构比较的可能性。有风险的是，PQGram配置文件生成过程在大型文档上可能会变得昂贵，因此我可能需要重新审查实现并考虑添加迭代接口；我们将看看这是否会成为重大问题。

使用方法

提供了一个泛型Tree，可以用于构建模式快速构建树。请查看lib.rs中的测试以获取使用示例。

不过，预期用途是实现针对您树类型的LabelledTree特质，为每个节点选择一个合理且可比较的标签，并将该实现传递给此代码。例如，HTML树可能通过提取HTML标签并将它们转换为u8（因为HTML标签集较小，而u8比字符串更节省空间）来实现LabelledTree，或者一个JSON遍历树可能提取对象键作为标签，并为非容器值提供基于值的确定性标签。