8

我正在编写一个预测搜索，对于服务器性能要求（所有内容都已缓存），必须在客户端浏览器上运行。这些项目是电视节目和电影，并与标题、演员和导演姓名相匹配。执行搜索后，它会返回一个匹配项列表，每个结果有两个值：

  1. 匹配词数（n）：用户可以输入 4 个词，但其中只有 2 个词匹配一个项目。越多越好。

  2. Levenshtein 编辑距离添加(ld)。用户可以键入 3 个单词，但其中 2 个单词与索引的单词有拼写错误或其他小的差异。我使用编辑距离来查找最近的索引词。所有 Levenshtein 距离的相加作为邻近指标返回。越少越好。

要求

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

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

  3. 非递归的。每个项目相关性的计算不应依赖于其他项目的计算。我不想打败谷歌，只提供一个小集合中最好的结果。

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

  5. 想法优于实现。我正在寻找比特定实现更好的算法/公式。

我的方法

基于指数衰减（如放射性半衰期分解），我提出了这个公式。

数学风格，感谢维基百科 LaTeX 支持

在哪里：

  • 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了用户提供的字数。

4

1 回答 1

8

一般来说，我相信你必须简化你的公式。事实上，像tf-idf这样的大多数基本相关性公式都非常简单，只使用产生式或部分参数，可能具有“加强”或“削弱”功能。例如，tf-idf只是词频乘以对数逆文档频率“弱化”。首先，我将快速分析您的公式，然后提出一些建议。

分析

让我们重写你的公式：

在此处输入图像描述

首先，请注意，这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 个自变量。例如，您的公式可能如下所示：

在此处输入图像描述

甚至：

在此处输入图像描述

其中distance是实际的 Levenshtein 编辑距离，而不是 and 的T函数MAX_LD。

2. 使用词干。我知道，我知道，你说过，你不能使用服务器端编程。但是你确定它不能在客户端执行吗？词干比看起来要容易得多。大多数词干只是截断后缀和结尾，如“-s”、“-ing”、“-ment”等。这并不理想，但我相信它会产生更好的结果，然后是 Levenshtein 距离。这里唯一的严格限制是：词干必须用于索引和搜索。

有关更精确的词干算法，请参阅Lucene 来源的 PorterStemmer 类。

3. 使用逆记录频率。回忆一下查询“John Malkovich”的例子。可能有很多电影都带有“约翰”一词，但只有几部电影带有“马尔科维奇”。很自然地假设，第二个词在搜索结果中的权重必须大于第一个。在其（逆文档频率）部分tf-idf中涉及到这一事实。idf您可以通过计算逆记录频率来做同样的事情：

irf = number-of-all-found-records / number-of-records-with-current-term

并添加到您的相关性公式第三部分：

在此处输入图像描述

当然，请记住：没有公式是好的，除非它在真实数据上进行测试。

于 2011-01-30T18:27:05.617 回答