美团是怎么实现搜索关键词自动匹配功能的？

问题背景搜索关键字智能提示是搜索应用程序的标准配置。其主要功能是避免用户输入错误的搜索词，并将用户引导到相应的关键词，以改善用户的搜索体验。美团CRM系统有数百万企业。为了让用户快速找到目标业务，我们在solrcloud的基础上实现了业务搜索模块。用户主要输入商户名和商户地址进行搜索。为了提高用户的搜索体验和输入效率，本文实现了基于solr前缀匹配查询关键字的智能提示(Suggestion)实现。1.支持前缀匹配原则在搜索框中输入“海底”，以海底为前缀，在搜索框下显示“海底捞”、“海底捞火锅”、“海底世界”等搜索词；输入“万达”会提示“万达影城”、“万达广场”、“万达百货公司”和其他搜索词。2.由于汉字和拼音输入的特点，如果搜索自动提示可以支持拼音，它将给用户带来更大的方便，以避免切换输入方法。例如，输入“haidi与输入“海底”提示相同，输入“提示”关键词wanda与输入“万达”提示的关键字相同。3.支持多音字输入提示，如输入“chongqing”或者“zhongqing“重庆火锅”都能提示“重庆火锅”、“重庆烤鱼”、“重庆小天鹅”。4.支持拼音缩写输入。为了提高输入效率，有必要提供拼音缩写输入。例如，输入“hd应该能够提示“”haidi输入“类似关键词”wd“也可以提示“万达”关键词。根据用户的历史搜索行为，根据关键词的热度进行排序。为了提供sugest关键词的准确性，根据用户查询关键词的频率对最终查询结果进行排序，如输入[重庆，chongqing,cq,zhongqing,zq]—>[“重庆火锅”(f1)、“重庆烤鱼”(f2)、“重庆小天鹅”(f3)、>f2>F3。解决方案1。当用户输入前缀时，遇到许多提示候选人时，如何选择，哪些显示在前面，哪些显示在后面？这是一个搜索热的问题。用户使用搜索引擎搜索业务，会输入大量的关键字，每个输入是关键字投票，所以关键字输入越多，相应的查询更受欢迎，所以需要记录查询关键字，统计每个关键字的频率，方便提示结果按频率排序。搜索引擎将通过日志文件记录用户每次搜索使用的所有搜索串，每个查询串的长度为1-255字节。2.汉字拼音用户输入的关键字可能是汉字、数字、英语、拼音、特殊字符等。由于需要实现拼音提示，我们需要将汉字转换为拼音，并考虑在java中使用piny4j组件进行转换。3.考虑到支持拼音缩写的过程。chongqing”,"zhongqing"--->"cq",”zq4.多音字的全排列应支持多音字提示。查询串转换为拼音后，需要实现全排列组合。字符串多音字的全排列算法如下:Javacode将内容复制到剪贴板public static List getPermutationSentence(List> termArrays,int start) {    if (CollectionUtils.isEmpty(termArrays))        return Collections.emptyList();    int size = termArrays.size();    if (start < 0  || start >= size) {        return Collections.emptyList();    }    if (start == size-1) {        return termArrays.get(start);    }    List  List1);    if (CollectionUtils.isEmpty(strings)) {        return permutationSentences;    }    if (CollectionUtils.isEmpty(permutationSentences)) {        return strings;    }    Listnew ArrayList  for (String pre : strings) {        for (String suffix : permutationSentences) {            result.add(pre suffix);        }    }    return result;  }  索引和前缀查询方案 Trie树，TopK算法，即字典树，又称单词搜索树或键树，是一种树形结构，是哈希树的变种。典型的应用程序是用来统计和排序大量的字符串（但不限于字符串），因此搜索引擎系统经常用于文本字频统计。典型的应用程序用于统计和排序大量的字符串（但不限于字符串），因此搜索引擎系统经常用于文本字频统计。其优点是最大限度地减少不必要的字符串比较，查询效率高于哈希表。Trie是一棵存储多个字符串的树。相邻节点之间的边缘代表一个字符，使树的每个分支代表一个子串，而树的叶节点代表一个完整的字符串。与普通树不同的是，相同的字符串前缀共享相同的分支。例如，给出一组单词inn，int,at,age,adv,ant,我们可以得到以下Triee：从上图可以看出，当用户输入前缀i时，搜索框可能会显示以i为前缀的“in”，“inn”，”int"等待关键词，当用户输入前缀a时，搜索框中可能会提示以a为前缀的“ate等待关键词。这样，实现搜索引擎智能提示sugestion的第一步就清楚了，就是用trie树存储大量的字符串，当前缀固定时，存储相对较热的后缀。Topk算法用于解决统计热词的问题。解决TopK问题主要有两种策略：hashMap统计 hashmap统计：先预处理这批海量数据。具体方法是：将Key维护为Query字符串，Value维护为Query出现次数的HashTable，即hash_map(Query，Value)，每次读一个Query，如果字串不在Table中，则添加字串，并将Value值设置为1；如果字串在Table中，则可以添加字串的计数，最终在O(N)Hash表完成了时间复杂性的统计。堆排序：借助堆的数据结构，找出TopK，时间复杂度为N‘logK。堆排序：借助堆的数据结构，找出TopK，时间复杂度为N‘logK。也就是说，借助堆结构，我们可以在log量级的时间内找到和调整/移动。因此，维护一个K(题目为10)大小的小根堆，然后通过300万的Query，分别与根元素进行比较。因此，我们最终的时间复杂度是：O（N） N'*O（logK），（N为1000万，N’为300万）。该方案的问题是：在构建索引和查询时，汉字应转换为拼音。查询完成后，拼音应转换为汉字显示，并考虑数字和特殊字符。两棵Trie树需要保持拼音和缩写。作为一个应用广泛的搜索引擎系统，Sugest智能提示Solr内置了智能提示功能，称为Sugest模块。该模块可以根据提示词文本选择智能提示，并支持通过建立索引词库来提示索引的某个字段。(详见solrwiki页面htp://wiki.apache.org/solr/Suggester)该方案的问题是，返回的结果是根据索引中字段的词频进行排序，而不是用户搜索关键字的频率，因此一些流行关键字不能排在前面。拼音提示，多音字，缩写或添加索引字段。方案3Solrcloud建立单独的collection，使用solr前缀查询实现上述问题。上述两个方案在实施过程中都存在一些问题 在处理汉字suggest时，Topk算法并不十分优雅，需要维护两棵Trie树，实施起来很复杂；Solr自带的sugest智能提示组件的问题是使用freq排序算法。返回结果完全基于索引中字符的出现次数，不考虑用户搜索单词的频率。因此，一些流行词不能排在更高的位置。因此，我们继续寻找更优雅的解决方案。因此，我们继续寻找一个更优雅的解决方案来解决这个问题。到目前为止，我们考虑为关键字建立索引collection，并使用solr前缀查询。copyField在solr中可以很好地解决我们同时索引多个字段(汉字，pinyin,abbre)当field的multivalued属性设置为true时，可以解决同一关键字的多音字组合问题。配置如下：schema.xml:XML/HTMLCode复制内容到剪贴板<field name="kw" type="string" indexed="true" stored="true" /><field name="pinyin" type="string" indexed="true" stored="false" multiValued="true"/><field name="abbre" type="string" indexed="true" stored="false" multiValued="true"/><field name="kwfreq" type="int" indexed="true" stored="true" /><field