>匹配单词的数量(n)：用户可以键入4个单词,但只有2个单词与一个项目匹配.越多越好.
> Levenshtein Edit Distance加法(ld).用户可以键入3个单词,但其中2个单词与索引的单词有拼写错误或其他小差异.我使用编辑距离来查找最近的索引字.所有Levenshtein距离的加法作为接近指标返回.越少越好.
要求
>客户端.没有Sphinx,Lucene或任何其他服务器端解决方案.
>速度超过准确性.该算法在每次击键时运行,我们不想让用户厌烦.保持大O不是那么大.
>非递归.每个项目相关性的计算不应该依赖于其他项目计算.我不想击败谷歌,只提供小套装的最佳效果.
>有界形式0到1,0到100或类似的东西.不是必需品,但能够显示“相关百分比”是一个加分.
>关于实施的想法.我正在寻找一种比特定实现更好的算法/公式.
我的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之间.
最后,问题
我想要的不是基于this response通过额外的编辑距离计算来细化搜索算法,而是通过将相关值设置为每个来改进返回元素的相关性排序.如果需要除n和ld之外的任何参数并且易于计算,则可以使用.在我的解决方案中,我添加了T,即用户提供的单词数.
解决方法
分析
让我们改写你的公式：
首先,请注意,n / T未规范化：可能会有更多结果(n),然后是搜索项(T).考虑这样的例子：用户输入查询“John Malkovich”,数据库中有电影Being John Malkovich.用户输入了2个单词,即T = 2,但是电影在电影片名和演员表中都有这些术语,因此n = 2 * 2 = 4.鉴于此,最终相关性将更加严格,然后是1.缺乏规范化不是问题本身,但实际上可能会导致将来出现一些错误.
现在让我们看看公式的第二部分 – 1 / e ^(ld / n).我们将ld / n表示为x.在这种情况下,公式的第二部分将如下所示：
因此,对于x的高值,它将大大削弱最终相关性.虽然我不明白为什么它必须是指数级的,但它仍然有意义.但是x不是自变量,它本身就是2个变量的函数：x = x(ld,n).此外,ld也是一个函数：ld = ld(MAX_LD,T),因此x取决于3个不同的独立变量/参数：x = x(MAX_LD,T,n).在这种情况下,很难预测所有可能情况的x行为(以及最终相关性).
建议
1.简化x().如果您希望公式的第二部分仅跟踪Levenshtein距离,则仅依赖于此距离,而不是所有3个独立变量.例如,您的公式可能如下所示：
甚至：
其中距离是Levenshtein的实际编辑距离,而不是T和MAX_LD的函数.
2.使用词干.我知道,我知道,你说,你不能使用服务器端编程.但是你确定它无法在客户端执行吗？茎干似乎比它容易得多.大多数词干只是截断后缀和结尾,如“-s”,“-ing”,“-ment”等.这不是理想的,但我相信它会给出更好的结果,然后是Levenshtein距离.这里唯一强有力的限制是：必须使用词干 – 索引和搜索.
有关更精确的词干算法,请参阅Lucene sources中的PorterStemmer类.
3.使用反向记录频率.回想一下查询“John Malkovich”的例子.可能有很多电影用“约翰”这个词,但只有几部用“马尔科维奇”.很自然地假设,第二项必须在搜索结果中具有更大的权重,然后是第一项. tf-idf在其idf(逆文档频率)部分中涉及此事实.您可以通过计算逆记录频率来做同样的事情：
irf = number-of-all-found-records / number-of-records-with-current-term
并添加到您的相关性公式第三部分：
当然,请记住：在对真实数据进行测试之前,没有公式是好的.
