照明快速自动完成搜索建议的完整指南电视电影小迷妹 TVco.cn

因此，在狂欢了很长一段时间的第一个奇妙的《麦瑟尔太太》季之后，我想知道还有什么吗？

-宾格守望者
每个MLB团队在2018年奥斯卡提名电影中的完美比赛
当然，MoviePass是值得的！
捍卫星球大战：最后的绝地武士
克雷格·布鲁尔（Craig Brewer）将指导埃迪·墨菲（Eddie Murphy）出演《来美国2》
＃365DaysOfWriting-第273天

阅读了技术博客的完全不相关的开篇行之后，接下来的内容可能不会让您失望，所以继续。

我之所以选择像深度学习，人工智能和大数据这样的简单的自动完成搜索建议，是因为
1.网站/应用程序顶部的搜索框是所有产品的最基本功能。
2.每个人都使用它。它是您产品的门户。
3.缺乏实现和优化的文档。
4.我对ML的了解还不值得撰写博客。

我将本指南分为多个部分，以使其对多种用例有用，从15分钟内的快速解决方案到高级闪电般的微服务。我将从一个简单的实现开始，并提高可用性，速度和规模。

首先，自动完成服务有两个挑战
1.速度-非常低的响应时间〜100ms。
2.排名 -由于房地产有限，只能显示6–10条建议。最佳排名是一个挑战。

窥见实施

服务分为两个部分

客户端-负责发送击键，在客户端缓存和呈现结果。所有这些都很好地捆绑到了JQuery UI自动完成包中。完整的代码段可以在给定的链接中找到。
服务器端-负责针对查询返回排名结果。如果您的数据大小超过几个MB，则将在此处进行操作。在本文的其余部分，我将深入研究此API实现。假设这个API是

GET / service / uggestions？q = {term}

API的实现

让我们从最快的解决方案开始，在几分钟之内启动并运行。使用任何SQL数据库存储数据。您只需一个简单的LIKE查询即可。

从电影中选择名称，例如“％term％”的名称限制为10；

而已！您的实施率高达90％的网站，但如果您打算为人类编写软件，则应继续阅读。

上述实现的问题是结果的排名。让我们看一下JQuery UI演示的结果

我正在寻找鹰派。键入“ ha”时，它会显示与“ ha”匹配的所有内容，更糟糕的是，由于占位符的限制，任何带有hawk的内容都不会出现。
实际上，如果有人开始在搜索框中键入内容，则该查询应匹配所有可能建议中的单词边界，而不是子字符串。例如，查询“ go”在一组编程语言中搜索，我可能正在寻找Go或Go lo或Pro Go，而不是Lo go和Hu go 。

这带来了我们的下一个改进，加强了80-20规则。只需稍微修改第一个SQL查询，通过匹配单词边界（而不是子字符串），建议将大大改善。

从电影中选择名称，例如“ term％”之类的名称或“％term％”之类的名称限制为10； — —以％term％表示空格

恭喜你！！只需添加“％term％”或类似“％term％”的名称，您的搜索建议就比互联网上的大多数产品都要好。如果您的数据集约为100k，则此解决方案将在合理的时间内工作。

API的实现-闪电般的野兽模式

根据您的业务需求，上面的解决方案可能就足够了，但是以速度和用户体验为核心功能的产品有很多优化的余地。在深入探讨之前，让我添加一些背景信息，因为有多种方法可以优化速度和进一步排名。它将证明我们的决定是合理的（在促销中明智地滑入）。 MyMovieRack主要是一个影视节目平台，具有使娱乐个性化的核心价值。因此，优化搜索体验是该产品的心跳。直到几个月前，SQL查询上的缓存层对我们来说都运作良好。迫使我们转向更快的实现（约50毫秒）的原因是

影视节目数量的增长以及我们最近的热门节目-网络连续剧。
更多忠实的用户会定期访问该网站。将直接用户与SERP流量进行比较时，行为会发生巨大变化。当SERP流量从Google登陆到相关页面时，忠实用户倾向于更频繁地使用搜索框进行评分，评论等。
最后但并非最不重要的事情-和交易破坏者-用于创建电影和节目列表的功能。要创建列表，必须通过搜索并从建议中选择来添加电影。对于100部电影的列表，用户必须执行100次。对于客户偏心的产品，每个建议调用的〜1.2秒延迟（以印度的多个客户为基准）是不可接受的。因此，需要更快的API。

我们从两种主要的方法开始解决这个问题。两种方法的基本思想都是创建该术语的所有可能的前缀，并在用户每次击键之后的固定时间内进行快速查找。这些前缀中的每一个都将指向实际名称->矩阵。例如，下面列出了Matrix的所有前缀。

Ť
钍
的
的
M
妈
垫子
马特
马特里
矩阵
中号
嘛
垫
马特
马特里
矩阵

可以使用以下方法来实现此想法：

使用Trie：在Trie中插入所有前缀，并将叶节点链接到自动完成小部件所需的对象，例如{“ name”：“ The Matrix”，“ img”：“ img url”}。在实现方面，叶节点将链接到按相关性得分排序的ID优先级队列（记住最佳排名）。这些ID将指向实际数据。
我们选择不使用trie，因为我们的后端在PHP中（停止判断）。 因此，每个新请求都必须初始化自己的trie，这没有任何意义。懒得为它设置JAVA（或任何其他）服务器。当使用Redis实施起来要容易得多时，就懒于编写其他原因。
使用内存缓存 ：我是Redis的粉丝。粉丝。从现在开始，我将把Redis替换为内存缓存。除了作为内存键值存储外，Redis还支持一些基本数据结构，这使其成为解决问题的最佳工具。
实现基本上涉及将所有电影名称和电影ID的每个前缀的集合排序为集合的成员。最初，它感觉不直观/键空间爆炸/冗余。如果这种方法无效，我们会进行互联网检查。 Redis的创建者Antirez的这个博客谈到了类似的服务。同样，此博客涵盖了两种不同的方法。我们解决方案的一部分与这些方法重叠。我鼓励您浏览这些博客以进行详细的实现。
这是我们的粗略实现-创建与所有名称的所有前缀对应的排序集，并在这些集中添加ID。将与这些ID对应的数据存储在哈希中以进行最终查找。伪代码将如下所示

foreach（电影名称为m）{
foreach（m.getPrefix（）as p）{
zset autocomplete :: p分数m.id
}
设置数据：: m.id {“ n”：“ m.name”，“ i”：“ m.img”}
}

我们在EC2上产生了最便宜的Redis实例（弹性缓存），该实例提供500 MB的存储空间。由于MyMovieRack对所有用户免费，因此节俭是一种虔诚的做法，目的是节省服务器成本。此框上的天真的实现占用了超过400 MB的空间。以下是为减少75％的内存空间而进行的一系列优化。

寻求从400MB到100 MB的空间优化

我们对约90,000个电影名称进行了有限的测试。在天真的实现了上述伪代码之后：

前缀总键：2,312,783
已用总空间：400MB

现在，这是一个挫折，因为电影的总数远不止于此。更不用说可扩展性计划了。如果我们计划采用整体发现方法在同一搜索中支持名人姓名建议（顺便说一下，我们现在支持名人搜索：）。

是时候戴上优化帽并深入研究数据了。

优化1-不存储长度为1的前缀

因此，基于一个输入字符的建议没有多大意义。即使您想要支持它，也可以硬编码与这26个存储桶相对应的热门建议，而不必存储所有名称，因为每个可能的名称都将落入其中一个存储桶中，浪费很多空间。优化后的结果：

总前缀：2,225,827（减少3％）
总空间：350MB（减少12％）

优化2-不要存储以停用词开头的前缀（如果该停用词不是电影名称的第一个单词）

该观察结果基于我们所进行搜索的历史数据。人们通常不会以诸如（a，an，the，of等）的停用词开始搜索，除非它是名称的第一个单词。例如，可能的搜索尝试因为对幸福的追求可以是“追求”，“追求”，“幸福”，而不是“幸福”

同样，对于指环王来说 ，可能的尝试可能是“领主”，“霸主”，“指环”，但没有人从“指环”开始搜索。下面的列表将给出有关生成的冗余前缀的想法。

  “指环王”的所有前缀（64） 
  Ť 
 钍 
 的 
 的 
  L 
 罗 
 洛尔 
 主 
 主 
 主阿 
 的主 
 的主 
  t之王 
 上帝之王 
 的主 
 的主 
  R之王 
  Ri之王 
  in之王 
 戒指的主人 
 指环王 
 大号 
 罗 
 洛 
 主 
 主 
 主阿 
 的主 
 的主 
  t之王 
 上帝之王 
 的主 
 的主 
  R之王 
  Ri之王 
  R王 
 指环王 
 指环王 
  Ø 
  的 
  的 
  的t 
  的 
  的 
  的 
  R的 
  Ri的 
  R之 
  指环王 
  指环王 
  Ť 
  日 
  的 
  的 
  R 
  里 
  R 
  戒指 
  戒指 
  [R 
 日 
  in 
 环 
 戒指

由于此优化，粗体标记的内容将被删除（63个中的19个）。由于首次优化，单个字母前缀将被删除。

此优化的最佳部分–由于忽略了停用词，因此使结果更可靠。优化后的结果：

总前缀：1,831,758（比上次优化少17％）
总空间：280MB（比上一次优化少20％）

优化3-您无法拒绝的提议-将前缀最大长度限制为8个字符（或根据业务逻辑通常为n个字符）

我们用这个赢了大奖。在研究前缀（排序集）的分布时，发现〜95％的前缀的基数为1。这意味着可以在前n个字符后唯一标识一个名称，而存储其余字符不会改善解决方案。另外，通过限制前缀的最大长度，可以增加平均基数。

最好不要有每个带10个元素的10个前缀，而不是每个带一个元素的100个前缀（排序集）。

例如，在将“指环王”的最大前缀长度限制为8后，密钥空间将大大减少，并且平均基数将大于1，因为许多电影名称将共享同一前缀。所有优化后的最后一组前缀：

 经过所有优化后，“指环王”的所有前缀（18） 
 钍 
 的 
 的 
  L 
 罗 
 洛尔 
 主 
 罗 
 洛 
 主 
 主 
 主阿 
 的主 
 的主 
 日 
  in 
 环 
 戒指

总前缀：357,465（比以前减少80％）
总空间：102 MB（比以前少63％）

是的-总共优化了75％的空间。

进一步发展

这只是我们已实施的概述。可以根据业务逻辑轻松地对结果进行评分。前面提到的博客使用另一种方法，该方法将前缀限制为单个单词，并依靠Redis集并集获得最终结果。随意探索该方法并发表您的发现。另外，这是我的第一个博客，花了很多时间才能完成。我可能已经跳过了一些实现细节或解释。如果有不清楚的地方，请不要犹豫在评论中发表。

您可以在“ 电影发现”页面上 看到自动完成功能 。