伪代码
初始化为句法树的最优得分或者负无穷，其中det()用来求解句法树的最优得分，但是没有必要真的求出最优句法树，只需要在每个结点处保留得分最高的边即可。尽管这样得出来的句法树基本不是最高的，但是能够缩小
范围即可。init-chart()首先初始化分析表，全部初始化为收缩符号。- 然后开始迭代过程，首先执行维特比inside算法，也就是CKY算法
Viterbi-inside()，得到最优句法树
。 - 如果最优句法树不含有任意收缩符号，那么迭代结束，直接返回该句法树。
- 否则的话，更新
为最优句法树的分数best()。 expand-chart()将所有收缩符号替换为下一层的收缩符号。Viterbi-outside()计算outside值。prune-chart()进行剪枝，过滤掉无用的边。
剪枝过程
算法的重要部分就是prune-chart()剪枝过程，这里要详细讲一下。
对于一条边 
，定义 
为含有边 e 的句法树的最大分数。那么如果
，这条边 e 就没有搜索的必要了，可以从分析表中去掉。
但是每次迭代都从原始表中计算 
值太麻烦了，可以在每次迭代的时候计算粗表中的值：
所以当 
时，从分析表中删除这条边。虽然搜索空间减少了，但是不影响算法的迭代轮数。
虽然在expand-chart()这一步要扩展收缩符号为下一层所有符号，但是实际运行起来时间比普通的CKY算法大大减少。
K-best扩展
基本框架和1-best是一样的，主要思路就是首先求出最优句法树，如果包含收缩符号，那么就下面步骤和1-best一样。否则的话求出后面k-1棵最优的句法树，如果都不包含收缩符号，直接返回k-best棵句法树。否则从中选出最好的一棵含有收缩符号的句法树，下面的步骤和1-best一样。
实验
数据集用的是PTB中长度小于35的句子。
上面这张表显示出，IVP算法的边的数量远远小于CKY算法，虽然迭代次数大大增加，但是总时间仍然远远小于CKY算法，而且边数减少了之后inside和outside算法的时间可以忽略不计了。最后一行是平均数据。
上图说明了，当k较小时，IVP算法时间快于普通的k-best算法，但是k大了之后就变慢了，原因如下图所示：
当k太大了之后，lb不能很好的得到最优得分的下界，所以无法有效地剪枝。而且k越小，算法收敛的也越快。
结论
提出了K-best IVP算法，基本框架还是inside-outside算法。
但是全文自始自终没有提及算法的准确率，感觉应该不是很高，不知道有没有又高又快的优化方法呢？
