发明创造名称：一种实现倒排链快速归并的方法和装置
外观设计名称：
决定号：186434
决定日：2019-07-29
委内编号：1F246964
优先权日：
申请（专利）号：201510611489.0
申请日：2015-09-22
复审请求人：广州神马移动信息科技有限公司
无效请求人：
授权公告日：
审定公告日：
专利权人：
主审员：唐娜
合议组组长：巩瑜
参审员：赵晓敏
国际分类号：G06F17/30
外观设计分类号：
法律依据：专利法第22条第3款
决定要点
：如果一项权利要求请求保护的技术方案与作为最接近现有技术的对比文件相比存在区别技术特征，但该区别技术特征属于本领域的常用技术手段，则该项权利要求不具有突出的实质性特点，不具备创造性。
全文：
本复审请求涉及申请号为201510611489.0，名称为“一种实现倒排链快速归并的方法和装置”的发明专利申请（下称本申请）。本申请的申请人为广州神马移动信息科技有限公司，申请日为2015年09月22日，公开日为2016年01月06日。
经实质审查，国家知识产权局实质审查部门于2017年12月01日发出驳回决定，驳回了本申请，其理由是：权利要求1和10的修改不符合专利法第三十三条的规定。具体理由为：技术特征“在归并过程中，不再对已经归并的分词部分所对应的不同粒度的分词进行处理”既未明确地记载在原说明书和权利要求书中，也不能由原说明书和权利要求书所记载的内容直接地、毫无疑义地确定，因此超出了原说明书和权利要求书记载的范围，不符合专利法第33条的规定。
驳回决定所依据的文本为：申请日2015年09月22日提交的说明书摘要、说明书第1-13页、摘要附图、说明书附图第1-2页；2017年08月29日提交的权利要求第1-15项。
驳回决定中引用一篇对比文件，为：
对比文件1：倒排文件的组织与最佳归并分析，赵长林，西南民族学院学报自然科学版，第21卷第4期，公开日为1995年11月30日。
驳回决定所针对的权利要求书如下：
“1. 一种实现倒排链快速归并的方法，其包括：
预先建立倒排索引并记录该倒排索引中的各条倒排链的长度，其中，在建立倒排索引的过程中还包括使用多粒度分词的方法建立多条倒排链；
通过所述倒排索引查询到与至少一个关键词对应的多条倒排链，其中，在查询的过程中使用多粒度分词的方法对所述至少一个关键词进行分词；
按照长度从小到大的顺序对查询到的多条倒排链进行排序；
从长度最小的倒排链开始对所述排序后的多条倒排链进行顺序归并，在归并过程中，不再对已经归并的分词部分所对应的不同粒度的分词进行处理。
2. 根据权利要求1所述的方法，其特征在于，在建立倒排索引的过程中还包括建立分别包含检索单元和语义单元的多条倒排链。
3. 根据权利要求2所述的方法，其特征在于，所述检索单元为通过小粒度分词方法获得的关键词。
4. 根据权利要求2所述的方法，其特征在于，所述语义单元为通过大粒度分词方法获得的关键词。
5. 根据权利要求1或2所述的方法，其特征在于，在建立倒排索引的过程中，还包括将倒排链所记录的文档按照多维特征进行排序，确保优质文档排在倒排链靠近链头的位置。
6. 根据权利要求5所述的方法，其特征在于，所述文档的多维特征包括文档的点击量、文档质量和文档的作者。
7. 根据权利要求1所述的方法，其特征在于，还包括：所述关键词是通过采用多粒度分词方法对给定文本进行分词产生的。
8. 根据权利要求1所述的方法，其特征在于，还包括：采用插入排序法、冒泡排序法或者选择排序法来按照长度从小到大的顺序对所述多条倒排链进行排序。
9. 根据权利要求5所述的方法，其特征在于，还包括：在对所述排序后的多条倒排链进行顺序归并时采用截断方法来进行，具体过程是：召回预设数量的排在倒排链靠近链头位置的文档后提前结束归并。
10. 一种实现倒排链快速归并的装置，其包括：
倒排索引建立单元，用于预先建立倒排索引并记录该倒排索引中的各条倒排链的长度，其中，在建立倒排索引的过程中还包括使用多粒度分词的方法建立多条倒排链；
查询单元，用于通过所述倒排索引查询到与至少一个关键词对应的多条倒排链，其中，在查询的过程中使用多粒度分词的方法对所述至少一个关键词进行分词；
排序单元，用于按照长度从小到大的顺序对查询到的多条倒排链进行排序；
归并单元，用于从长度最小的倒排链开始对所述排序后的多条倒排链进行顺序归并，在归并过程中，不再对已经归并的分词部分所对应的不同粒度的分词进行处理。
11. 根据权利要求10所述的装置，其特征在于，所述倒排索引建立单元还用于建立分别包含检索单元和语义单元的多条倒排链。
12. 根据权利要求11所述的方法，其特征在于，所述检索单元为通过小粒度分词方法获得的关键词。
13. 根据权利要求11所述的方法，其特征在于，所述语义单元为通过大粒度分词方法获得的关键词。
14. 根据权利要求10所述的装置，其特征在于，还包括：优先排序单元，用于将倒排链所记录的文档按照多维特征进行排序，确保优质文档排在倒排链靠近链头的位置。
15. 根据权利要求14所述的方法，其特征在于，所述文档的多维特征包括文档的点击量、文档质量和文档的作者。”
申请人（下称复审请求人）对上述驳回决定不服，于2018年03月16日向国家知识产权局提出了复审请求，未修改申请文件。复审请求人认为：（1）关于修改超范围：根据说明书第11页第1段的记载可以毫无疑义地得到特征“在归并过程中，不再对已经归并的分词部分所对应的不同粒度的分词进行处理”。因此，将该技术特征补充至权利要求1未超出原说明书和权利要求的范围，符合专利法第33条的规定；（2）关于创造性：在多粒度分词的情况下，为了完成整个搜索关键词的归并，获取不同分词粒度拆分出的分词部分分别对应的倒排链的长度，从长度最小的倒排链开始，对拆分出的词分别对应的倒排链进行归并，并且在归并过程中，不再对已经归并的分词部分所对应的不同粒度的分词进行处理，有效提升了归并效率。对比文件1中没有提到过任何有关采用不同粒度进行分词，并对同一个词建立多个倒排链的内容，在对比文件1中一个关键词只对应一个倒排链，并且后续的归并也只由倒排链的长度决定，进一步地，在对比文件1的归并过程中，不管这个分词是否已经归并过，都会对其进行归并，进而存在重复归并，归并效率低的技术问题。
经形式审查合格，国家知识产权局于2018年04月09日依法受理了该复审请求，并将其转送至实质审查部门进行前置审查。
实质审查部门在前置审查意见书中认为：本领域技术人员根据原申请文件的记载，不能直接地、毫无疑义地确定，在归并过程中，选择倒排链的条件还包括“在归并过程中，不再对已经归并的分词部分所对应的不同粒度的分词进行处理”。因此，该修改存在超范围缺陷。本申请原申请文件公开的方案是采用不同粒度的分词方法建立多条倒排链，在分别对不同粒度的分词方案得到的倒排链进行归并时按照长度从小到大的顺序进行。而对比文件1已经公开了对不同长度的倒排表的不同归并顺序会有不同的归并效率的内容，以及较长的倒排表较晚一些参加归并对提高检索效率比较有利的内容，对于本领域技术人员来说，按照长度从小到大的顺序进行倒排链归并是本领域技术人员在对比文件1公开的内容的基础上容易想到的，且分词处理以及多粒度分词均是搜索引擎领域所常用的处理手段。因而坚持驳回决定。
随后，国家知识产权局成立合议组对本案进行审理。
合议组于2019年03月22日向复审请求人发出复审通知书，指出：权利要求1-15不具备专利法第22条第3款规定的创造性。针对复审请求人的意见陈述，合议组认为：虽然对比文件1并未指明采用多粒度方式进行分词，从而对比文件1中的一个关键词只对应一个倒排链。基于不同粒度的分词方式有各自的特点，在搜索领域采用多粒度分词方式属于为了同时兼顾搜索的快速性与准确性的常规手段。在对比文件1已经公开了较长的倒排表较晚一些参加归并对提高检索效率比较有利的基础上，为了兼顾搜索的效率和准确率，本领域技术人员容易想到搜索时采用多粒度的分词方式进行语义分析。从而由于采用多粒度的分词方式，同一关键词可能对应多种倒排链。在多粒度分词及获取其对应倒排链的基础上，在按照长度顺序进行归并的过程中，本领域技术人员容易想到，先归并的分词对应的倒排链的长度相较于后归并的分词对应的倒排链的长度要小。若后归并的分词为先归并的分词通过更小粒度的分词得到的，则其与先归并的分词的倒排链合并时通常仍会得到先归并的分词对应的倒排链。因此，为了提高归并效率，本领域技术人员容易想到不再对已经归并的分词部分所对应的不同粒度的分词进行处理。
复审请求人于2019年05月06日提交了意见陈述书，未修改申请文件。复审请求人认为：本申请权利要求1中，按照多种粒度对同样的至少一个关键词进行分词，获得分词结果，然后将分词结果掺杂后，对掺杂后的分词结果按照倒排链从小到大的顺序进行排序，然后从长度最小的倒排链开始对所述排序后的多条倒排链进行顺序归并，且在归并过程中，不再对已经归并的分词部分所对应的不同粒度的分词进行处理。在归并倒排链时，本领域技术人员容易想到分别对这两种方案所对应的倒排链进行归并，也就是说将“中华”、“人民”、“共和国”、“建立”、“时间”，这5个词对应的倒排链进行归并；以及将“中华人民共和国”、“建立”、“时间”这3个词对应的倒排链进行归并，得到的两个并集进行求或操作作为搜索结果。因此，本申请具备创造性。
在上述程序的基础上，合议组认为本案事实已经清楚，可以依法作出审查决定。
二、决定理由
1、审查文本的认定
复审请求人在复审阶段未修改申请文件。本复审请求审查决定所针对的审查文本与驳回决定所针对的文本相同，即：申请日2015年09月22日提交的说明书摘要、说明书第1-13页、摘要附图、说明书附图第1-2页；2017年8月29日提交的权利要求第1-15项。
2、关于专利法第22条第3款
专利法第22条第3款规定：创造性，是指与现有技术相比，该发明具有突出的实质性特点和显著的进步，该实用新型具有实质性特点和进步。
如果一项权利要求请求保护的技术方案与作为最接近现有技术的对比文件相比存在区别技术特征，但该区别技术特征属于本领域的常用技术手段，则该项权利要求不具有突出的实质性特点，不具备创造性。
本复审请求审查决定所引用的对比文件与复审通知书和驳回决定中引用的对比文件相同，即：
对比文件1：倒排文件的组织与最佳归并分析，赵长林，西南民族学院学报自然科学版，第21卷第4期，公开日为1995年11月30日。
2.1、权利要求1要求保护一种实现倒排链快速归并的方法。对比文件1公开了一种倒排文件的组织方法并进行了最佳归并顺序的分析，并具体公开了以下技术特征（参见第1-3节）：我们把每个索引项看作一个记录，它由属性值和一组指针组成。属性值是唯一的，不同的索引项具有不同的属性值，可以把它看作码，用组织文件的一般方法来组织这项索引，用索引顺序组织或Hash表均可凑效。对倒排文件的索引结构，采用索引顺序为宜（相当于预先建立倒排索引）。倒排表X1，X2，X3，X4的长度分别为1，2，5，10（相当于记录该倒排索引中的各条倒排链的长度）。在倒排文件上关于满足某一布尔表达式的检索运算可如下进行，对于在布尔表达式中出现的属性名及其要满足的值，从相应的倒排索引中找出相应的倒排表（相当于通过倒排索引查询到与关键词对应的倒排链），把这些倒排表按布尔表达式中的逻辑运算符加以归并，得到结果倒排表（相当于对多条倒排链进行归并）；由结果倒排表中所含的指针，找到相应的记录；归并倒排表的顺序不同可能效率不同，上面为参数归并的各倒排表的长度不同，一般效率不同；较长的倒排表较晚一些参加归并对提高检索效率比较有利；不同的布尔表达式有不同的归并顺序，不同的归并顺序，或能产生不同的检索效率；不同的布尔表达式，可以表达成不同的归并树，要确定一个具有最小归并时间的布尔表达式，就相当于找一棵最佳树。
权利要求1请求保护的技术方案与对比文件1的区别技术特征在于：1）按照长度从小到大的顺序对多条倒排链进行排序；从长度最小的倒排链开始对排序后的多条倒排链进行顺序归并；2）在建立倒排索引的过程中使用多粒度分词的方法建立多条倒排链；在查询过程中使用多粒度分词的方法对至少一个关键词进行分词；在归并过程中，不再对已经归并的分词部分所对应的不同粒度的分词进行处理；权利要求1是查询到与至少一个关键词对应的多条倒排链，对比文件1是查询到与布尔表达式中的属性项对应的倒排链。基于上述区别技术特征，权利要求1实际所要解决的技术问题是：如何提高归并效率以及提高搜索效率。
针对区别技术特征1），对比文件1已经公开了对不同长度的倒排表的不同归并顺序会有不同的归并效率以及较长的倒排表较晚一些参加归并对提高检索效率比较有利。在此基础上，本领域技术人员容易想到按照长度从小到大的顺序对多条倒排链进行归并以提高归并效率。因此，区别技术特征1）属于本领域的常用技术手段。
针对区别技术特征2），根据本领域技术人员的技术常识可知，准确率和召回率是常见的评价搜索引擎的指标，词粒度越小，搜索的召回率越高，但计算速度相应减慢，分词粒度越大，搜索的准确率越高，但计算速度相应较快。由此可见，不同粒度的分词方式有各自的特点，在此基础上，本领域技术人员容易想到同时应用不同粒度的分词方式有助于兼顾搜索效率和准确率。并且，不同粒度的分词方式通常对应不同的倒排链。从而，在多粒度分词及获取其对应倒排链的基础上，应用上述区别技术特征1）按照长度顺序进行归并的过程中，本领域技术人员容易想到，先归并的分词对应的倒排链的长度相较于后归并的分词对应的倒排链的长度要小。若后归并的分词为先归并的分词通过更小粒度的分词得到的，则其与先归并的分词的倒排链合并时通常仍会得到先归并的分词对应的倒排链。因此，为了提高归并效率，本领域技术人员容易想到不再对已经归并的分词部分所对应的不同粒度的分词进行处理。因此，区别技术特征2）属于本领域的常用技术手段。
因此，在对比文件1的基础上结合本领域的常用技术手段得到该权利要求所请求保护的技术方案，对本领域的技术人员来说是显而易见的，因此该权利要求所请求保护的技术方案不具有突出的实质性特点，因而不具备专利法第22条第3款规定的创造性。
2.2、权利要求2对权利要求1作了进一步限定。其附加技术特征属于本领域通过多粒度分词建立多条倒排链的常用技术手段。因而当其引用的权利要求不具备创造性时，该权利要求也不具备专利法第22条第3款规定的创造性。
2.3、权利要求3、4对权利要求2作了进一步限定。在本领域中，由于不同粒度对应的关键词切分方式不同，因此，权利要求3、4 的附加技术特征属于本领域设置检索单元和语义单元以实现通过多粒度分词建立多条倒排链的常用技术手段。因而当其引用的权利要求不具备创造性时，该权利要求也不具备专利法第22条第3款规定的创造性。
2.4、权利要求5对权利要求1或2作了进一步限定。根据本领域技术人员的技术常识可知，在建立倒排索引的过程中，将倒排链所记录的文档按照多维特征进行排序，确保优质文档排在倒排链靠近链头的位置属于本领域提高检索效率的常用技术手段。因而当其引用的权利要求不具备创造性时，该权利要求也不具备专利法第22条第3款规定的创造性。
2.5、权利要求6对权利要求5作了进一步限定。在本领域中，文档的点击量、文档质量和文档的作者都是常见的文档多维特征。因而当其引用的权利要求不具备创造性时，该权利要求也不具备专利法第22条第3款规定的创造性。
2.6、权利要求7对权利要求1作了进一步限定。在本领域中，通过采用多粒度分词方法对给定文本进行分词产生关键词属于本领域确定搜索过程中的关键词的常用技术手段。因而当其引用的权利要求不具备创造性时，该权利要求也不具备专利法第22条第3款规定的创造性。
2.7、权利要求8对权利要求1作了进一步限定。在本领域中，插入排序法、冒泡排序法、选择排序法均是常见的排序方法。因此，根据各条倒排链的长度，按照长度从小到大的顺序，利用公知的排序方法对多条倒链进行排序属于本领域的常用技术手段。因而当其引用的权利要求不具备创造性时，该权利要求也不具备专利法第22条第3款规定的创造性。
2.8、权利要求9对权利要求5作了进一步限定。根据本领域技术人员的技术常识可知，由于优质文档通常排在倒排链靠近链头的地方，为了提高查询时的搜索效率和准确率，本领域技术人员容易想到召回排在靠近链头的一定数量的文档以提前结束归并。因此，权利要求9的附加技术特征属于本领域的常用技术手段。因而当其引用的权利要求不具备创造性时，该权利要求也不具备专利法第22条第3款规定的创造性。
2.9、权利要求10-15请求保护一种实现倒排链快速归并的装置，其与权利要求1-6所请求保护的实现倒排链快速归并方法相对应，基于相同的理由，权利要求10-15也不具有突出的实质性特点，不具备专利法第22条第3款规定的创造性。
3、对复审请求人相关意见的评述
针对复审请求人在2019年05月06日提交的意见陈述书中的相关意见，合议组认为：
首先，对比文件1已经公开了对不同长度的倒排表的不同归并顺序会有不同的归并效率以及较长的倒排表较晚一些参加归并对提高检索效率比较有利。在此基础上，本领域技术人员容易想到按照长度从小到大的顺序对多条倒排链进行归并以提高归并效率。进一步，根据本领域技术人员的技术常识可知，在搜索领域采用多粒度分词方式属于为了同时兼顾搜索的快速性与准确性的常规手段。而不同的分词粒度，对应的倒排链的长度通常不同。因此，在对比文件1已经公开了较长的倒排表较晚一些参加归并对提高检索效率比较有利的基础上，为了兼顾搜索的效率和准确率，本领域技术人员容易想到搜索时采用多粒度的分词方式进行语义分析。由此可见，归并结果由分词粒度和倒排链的长度决定，这是本领域技术人员容易想到的。
其次，在多粒度分词及获取其对应倒排链的基础上，按照长度顺序进行归并的过程中，本领域技术人员容易想到，先归并的分词对应的倒排链的长度相较于后归并的分词对应的倒排链的长度要小。若后归并的分词为先归并的分词通过更小粒度的分词得到的，则其与先归并的分词的倒排链合并时通常仍会得到先归并的分词对应的倒排链。具体到用户检索“中华人民共和国建立时间”这个词：由于“中华”、“人民”、“共和国”以及“中华人民共和国”是同一分词按照不同粒度分词处理获得的两种结果，并且如果“中华人民共和国”对应的倒排链较短，即使对“中华”、“人民”、“共和国”所对应的倒排链进行归并，其归并结果仍将是“中华人民共和国”对应的倒排链。因而在该种情形下，本领域技术人员没有必要再对“中华”、“人民”、“共和国”所对应的倒排链进行归并。即，为了提高归并效率，本领域技术人员容易想到不再对已经归并的分词部分所对应的不同粒度的分词进行处理。
综上所述，复审请求人的意见陈述不具有说服力，合议组不予支持。
三、决定
维持国家知识产权局于2017年12月01日对本申请作出的驳回决定。
如对本复审请求审查决定不服，根据专利法第41条第2款的规定，复审请求人可以自收到本复审请求审查决定之日起三个月内向北京知识产权法院起诉。
郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
