在(解析)树集合中查找最频繁的子树

我有一组树,它们的节点被标记(但不是唯一的)。具体来说,这些树来自一组已解析的句子(请参见 http://en.wikipedia.org/wiki/Treebank )我希望从集合中提取最常见的子树-性能还不是问题。我很感激算法(理想的Java)或指向树库的工具的指针。注意,子节点的顺序很重要。

编辑 @兆焦耳。我们在一个有限的领域(化学)工作,这个领域有一种风格化的语言,所以树的多样性不是很大——可能与儿童读者相似。“猫坐在垫子上”的简单树。

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

这里的句子包含两个相同的词类子树部分(实际的标记“cat”)。Mat“在匹配中并不重要)。所以算法需要检测到这一点。请注意,并非所有的名词短语都相同-“大黑猫”可以是:

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

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

显然,树越短越频繁,所以名词短语将非常常见。

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