Hobbs(1978)描述了一种代词判定的算法，树查询算法（Tree Search Algorithm） ，以当前句子以前的几个句子（包含当前句子）的句法表示为输入，并在这些句法树中执行先行名词短语的查询。这里并没有明确地用到Lappin和Leass算法中的话语模型或优先关系的表示。但是，通过执行句法树查询的先后顺序可以近似地表现出某些优先关系。

查询剖析树的算法也必须指定语法，因为与句法树结构有关的假设将影响结果。在图1中给出了该算法所用的英语语法的片断。该算法的步骤如下：

1. 从紧邻的支配该代词的名词短语（NP）结点开始。

2. 沿剖析树向上到达所遇到的第一个NP或句子（S）结点。称该结点为X，并称到达该结点的路径为p。

3. 以从左到右、宽度优先的方式遍历路径p左侧低于结点X的所有分支。对于遇到的任何NP结点，如果在它与X之间存在NP或S结点，则提议作为先行词。

4. 如果结点X是句子中最高的S结点，则按照新近顺序（首先是最新近的），遍历文中前述句子的表层剖析树；每个剖析树用从左到右、宽度优先的方式遍历，当遇到一个NP结点时，它就被提议为先行词。如果X不是句子中最高的S结点，继续步骤5。

5. 从结点X沿剖析树向上到达最先遇到的NP或S结点，称它为新的X结点，并称到达该结点的路径为p。

6. 如果X是NP结点，并且如果到X的路径p没有穿过紧邻的支配X的名词性结点，则提议X为先行词。

7. 以从左到右、宽度优先的方式遍历路径p左侧低于结点X的所有分支。提议所遇到的任何NP结点为先行词。

8. 如果X是S结点，以从左到右、宽度优先的方式遍历路径p右侧低于结点X的所有分支，但是不要遍历低于任何遇到的NP或S结点的分支。提议所遇到的任何NP结点为先行词。

9. 回到步骤4。

图1树查询算法的语法片断

如前所述，该算法以完整并正确的句法结构为输入。Hobbs从3个不同的文本中各选出一百个例句手工评测了他的方法（分为剖析构建和算法实现两部分），报道的精度为88.3%（如果假定某些选择限制约束，则精度上升为91.7%）。Lappin和Leass在他们的系统中也实现了该算法，对他们的测试语料所报道的精度为82%。尽管这低于他们自己的算法精度（86%），但应该记住Lappin和Leass所用的测试语料的体裁与他们的训练集一致，但与Hobbs在研制算法时所用的体裁不同。

责任编辑：admin