1

我有一组树，其节点被标记（但不是唯一的）。具体来说，这些树来自一组已解析的句子（参见http://en.wikipedia.org/wiki/Treebank）。我希望从集合中提取最常见的子树——性能（还）不是问题。我会感谢算法（最好是 Java）或指向为树库执行此操作的工具的指针。请注意，子节点的顺序很重要。

编辑@mjv。我们在一个有限的领域（化学）中工作，它有一种程式化的语言，所以树木的种类并不多——可能类似于儿童读者。“猫坐在垫子上”的简单树。

<sentence>
  <nounPhrase>
    <article/>
    <noun/>
  </nounPhrase>
  <verbPhrase>
    <verb/>
    <prepositionPhrase>
      <preposition/>
      <nounPhrase>
        <article/>
        <noun/>
      </nounPhrase>
    </prepositionPhrase>
  </verbPhrase>
</sentence>

这里句子包含两个相同的词性子树（实际标记“cat”。“mat”在匹配中并不重要）。所以算法需要检测到这一点。请注意，并非所有名词短语都是相同的——“the big black cat”可能是：

      <nounPhrase>
        <article/>
        <adjective/>
        <adjective/>
        <noun/>
      </nounPhrase>

句子的长度会更长——在 15 到 30 个节点之间。我希望从 1000 棵树中获得有用的结果。如果这不会超过一天左右，那是可以接受的。

显然树越短越频繁，所以名词短语会很常见。

编辑如果这要通过展平树来解决，那么我认为它与最长公共子串有关，而不是最长公共序列。但请注意，我不一定只想要最长的 - 我想要一个足够长的列表以“有趣”（标准尚未确定）。

4

4 回答 4

4

找到集合中最频繁的子树，创建子树的紧凑形式，然后迭代每个子树并使用哈希集来计算它们的出现次数。30 个节点对于一个完美的哈希来说太大了——每个节点只有一位，你需要这么多来表明它是兄弟姐妹还是孩子。

那个问题不是 LCS——最常见的序列与最长的公共子序列无关。最频繁的子树是出现次数最多的子树。

对于长度为 L 的 N 个树，最坏的情况应该是 O(NL^2)（假设测试包含 L 个节点的子树的相等性是 O(L)）。

于 2009-11-06T12:50:40.643 回答
3

我认为，尽管您说性能还不是问题，但这是一个 NP-hard 问题，因此可能永远无法使其快速。如果我理解正确，您可以将其视为最长公共子序列问题的变体；如果你将你的树展平成一个直线序列，比如

(nounphrase)(DOWN)(article:the)(adjective:big)(adjective:black)(noun:cat)(UP)

那么你的问题就变成了LCS。

Wikibooks在这里有一个 LCS 的 java 实现

于 2009-11-06T12:21:30.080 回答
3

这是计算机科学中众所周知的问题，对此有有效的解决方案。

以下是一些相关的参考资料：

Kenji Abe，Shinji Kawasoe，Tatsuya Asai，Hiroki Arimura，Setsuo Arikawa，半结构化数据的优化子结构发现，Proc。第六届欧洲数据库知识发现原则和实践会议 (PKDD-2002)，LNAI 2431，Springer-Verlag，1-14，2002 年 8 月。

Mohammed J. Zaki，有效地挖掘森林中的频繁树木，第 8 届 ACM SIGKDD 知识发现和数据挖掘国际会议，2002 年 7 月。

或者，如果您只想快速编写代码，请访问此处： FREQT （将 xml 转换为 S 表达式不会给您带来太多问题，留给读者作为练习）

于 2010-05-18T03:57:33.470 回答
1

在这种情况下，我发现名为 gspan 的工具非常有用。它可在http://www.cs.ucsb.edu/~xyan/software/gSpan.htm免费下载。其带有 matlab 接口的 c++ 版本位于http://www.nowozin.net/sebastian/gboost/

于 2014-04-16T10:26:18.670 回答