javascript - 具有多个参数的客户端预测性搜索相关性计算

我正在写一个预测性搜索，出于服务器性能的要求(所有内容都已缓存)，必须在客户端浏览器上运行该搜索。这些项目是电视节目和电影，并与标题， Actor 和导演姓名匹配。执行搜索后，它将返回一个匹配项的列表，其中每个结果都有两个值:

匹配的单词数(n):用户可以键入4个单词，但其中只有2个单词与某个项目匹配。越多越好。

Levenshtein Edit Distance加法(ld)。用户可以键入3个单词，但其中2个单词与输入的单词有错别字或其他小区别。我使用编辑距离来查找最接近的索引词。所有Levenshtein距离的加法值都作为接近指示器返回。越少越好。

要求

客户端。没有Sphinx，Lucene或任何其他服务器端解决方案。

速度超过准确性。该算法在每次击键时运行，我们不想让用户感到厌烦。不要让大O太大。

非递归。每个项目相关性的计算不应依赖于其他主题的计算。我不想击败Google，只提供一小部分最好的结果。

有界形式0到1、0到100或类似的形式。不是必需的，但能够显示“相关百分比”是一个加号。

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

我的方法

基于指数衰减(如放射性半衰期分解)，我建立了这个公式。

哪里:

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，即用户提供的单词数。

最佳答案

通常，我相信您必须简化您的公式。实际上，大多数基本的相关性公式(例如tf-idf)都非常简单，并且仅使用具有“加强”或“减弱”功能的参数的产生式或分数式。例如，tf-idf只是项频率和“弱”乘以对数逆文档频率的乘积。首先，我将对您的公式进行快速分析，然后提出一些建议。

分析

让我们重写您的公式:

首先，请注意，n/T是而不是规范化的:可能有更多结果(n)比搜索项(T)。考虑这样的示例:用户输入查询“John Malkovich”，并且数据库中存在电影Being John Malkovich。用户输入了2个字，即T = 2，但电影在电影标题和 Actor 表中都有这些术语，因此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个独立变量。例如，您的公式可能如下所示:

甚至:

其中distance是实际的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

并将第三部分添加到您的相关性公式中:

而且，当然，请记住:在实际数据上进行测试之前，没有公式是好的。