很多首诗，每首诗中包含很多字。我当然要用倒排索引了，对每个字建立索引，形式如下：
字1 诗11 诗12 诗13
字2 诗21 诗22
......
用户查询的是一个诗句，我把这个诗句中的每个字都摘出来去倒排索引里找，把每个字对应的集合做AND操作，得到一个诗的集合。
现在问题来了，如何对这个诗的集合排序？
这个问题其实就是相关度排序。最小编辑次数、最长公共子序列虽然也是一种排名方法，但容错性较低。比如我把“床前明月光”写成了“明月床前光”，最好也能够容忍我这种错误。
这肯定跟字在诗中的位置有关系，这些字离得越近越好。于是想到了使用方差。
在倒排索引中，加入“字位”信息。对于一首诗，字位信息如下：
字1 位置11 位置12 位置13
字2 位置21 位置22 位置23
字3 位置31 位置32 位置33
......
形式化一下这个问题：
给定N个集合，从每个中选取1个元素组成新的集合，使得新集合中元素方差最小，这个最小方差即为这N个集合的“得分”。
这个问题应该怎么做呢？
根据学过的算法可以很容易地构造出几个不一定正确的算法：
-
动态规划，定义二维数组f，f[i][j]表示前i个集合的最小方差并且最后一个数字是第i个集合中的第j个元素。当走出一条路径之后，对这条路径求均值，最佳路径必然是路径上的每一个结点都尽量靠近平均值，反复迭代更新，直到无法更新为止。
上面这种动态规划思想有点马尔科夫过程维特比算法的意思。 -
贪心，一开始把全部点放进一个盒子，求平均值，把离平均值最远的那个点删掉，如果某集合中只剩下一个点则这个点不可删。如此贪心，每次删除离均值最远的点，知道无法删除，即为所求。
-
如果集合个数小于16，并且集合中每个数字都比较小（比如小于1000），那么可以用动态规划，f[i][j]中的i表示二进制的集合状态（也就是有没有访问过），j表示当前的平均数，f[i][j]表示当前的方差。
上面这种想法对不对呢？