如何计算树编辑距离? [英] How do I calculate tree edit distance?

问题描述

我需要计算树木之间的编辑距离.这篇论文描述了一种算法，但我无法从中得出正面或反面.你能用更平易近人的方式描述一个适用的算法吗?伪代码或代码都会有帮助.

解决方案

这里有一些 Java 源代码(底部的 gzipped tarball)用于树编辑距离算法，可能对您有用.

该页面包括参考资料和一些幻灯片，这些幻灯片通过张和莎莎"算法分步说明和其他有用的链接，可让您快速上手.

链接中的代码有错误.Steve Johnson 和 tim.tadh 提供了工作 Python 代码.有关详细信息，请参阅史蒂夫·约翰逊的评论.>

I need to calculate the edit distance between trees. This paper describes an algorithm, but I can't make heads or tails out of it. Could you describe an applicable algorithm in a more approachable way? Pseudocode or code would both be helpful.

解决方案

Here's some Java source code (gzipped tarball at the bottom) for a tree edit distance algorithm that might be useful to you.

The page includes references and some slides that go through the "Zhang and Shasha" algorithm step-by-step and other useful links to get you up to speed.

The code in the link has bugs. Steve Johnson and tim.tadh have provided working Python code. See Steve Johnson's comment for more details.

这篇关于如何计算树编辑距离?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！