小编Coq*_*vas的帖子

我正在编写一个预测搜索,为了服务器性能要求(所有都是缓存的),必须在客户端浏览器上运行.这些项目是电视节目和电影,并由标题,演员和导演名称匹配.执行搜索后,它会返回一个匹配项列表,每个结果有两个值:

1. 匹配单词的数量(n):用户可以输入4个单词,但只有2个单词与一个项目匹配.越多越好.

2. 在莱文斯坦编辑距离增加(LD).用户可以输入3个单词,但其中有2个单词与索引的单词有拼写错误或其他小差异.我使用编辑距离来查找最近的索引字.所有Levenshtein距离的添加都作为接近指示符返回.越少越好.

要求

1. 客户端.没有Sphinx,Lucene或任何其他服务器端解决方案.

2. 速度超过准确性.该算法在每次击键时运行,我们不想让用户厌烦.保持大O不是那么大.

3. 非递归.每个项目相关性的计算不应该依赖于其他项目计算.我不想击败谷歌,只提供小套装的最佳效果.

4. 有界形式0到1,0到100或类似的东西.不是必需品,但能够显示"相关百分比"是一个加分.

5. 关于实施的想法.我正在寻找一种比特定实现更好的算法/公式.

我的aproach

基于指数衰减(如放射性半衰期分解),我编制了这个公式.

哪里:

• T 是用户提供的单词数.
• n 是匹配单词的数量.
• ld 是这个匹配单词的Levenshtein距离加法.

在伪代码中.

function lambda(n, ld) {
    lambda = (n/T) * e^(-ld * 1/n);
    return lambda;
}

一点解释:

• -ld * 1/n是相关性度量核心.如果ld是低并且n很大,它接近于零(-0侧)并且表明该结果更相关.

• n/T是准确率.匹配单词与所有单词.通过考虑总用户输入来优化先前的相关性.

对于负数幂,指数函数将结果限制在0和1之间.

最后,问题

我想要的不是基于具有额外编辑距离计算的响应来细化搜索算法,而是通过将相关值设置为每个来改进返回元素的相关性排序.如果可以使用除了n并且ld需要且易于计算的任何参数.在我的解决方案中,我添加T了用户提供的单词数.