发明创造名称：地理信息数据压缩处理算法
外观设计名称：
决定号：191811
决定日：2019-10-08
委内编号：1F267088
优先权日：
申请（专利）号：201510143642.1
申请日：2015-03-30
复审请求人：四川空间信息产业发展有限公司
无效请求人：
授权公告日：
审定公告日：
专利权人：
主审员：谢寅黎
合议组组长：孙泽竑
参审员：杨广辉
国际分类号：G06F17/30
外观设计分类号：
法律依据：专利法第22条第3款
决定要点
：如果权利要求所要保护的技术方案相对于最接近的现有技术具有区别特征，而该区别特征为本领域的常用技术手段，且本领域技术人员在面对所要解决的技术问题时有动机将上述本领域的常用技术手段应用到最接近的现有技术中以解决所要解决的技术问题，并获得该权利要求所要求保护的技术方案，则该权利要求不具备创造性。
全文：
本复审请求审查决定涉及申请号为201510143642.1、名称为“地理信息数据压缩处理算法”的发明专利申请（下文称本申请）。本申请的申请人为四川空间信息产业发展有限公司，申请日为2015年03月30日，公开日为2015年06月10日。
经实质审查，国家知识产权局原审查部门于2018年09月03日发出驳回决定，以权利要求1-4不具备专利法第22条第3款规定的创造性为由驳回了本申请。具体驳回理由为：权利要求1与对比文件1（“入侵检测系统中多模式匹配算法的研究”，董世博，《中国优秀硕士学位论文全文数据库》， 公开日为：2012年09月30日）的区别特征为：（1）将匹配算法应用于地理信息数据压缩处理中，包括定义历史窗口和待编码窗口，所述历史窗口中包括目标字符串T，所述待编码窗口中包括模式字符串P；（2）当在一次比较过程中，模式字符串P的第j＋1个位置与目标字符串T的相应位置失配时，且j＞0，则下一次比较时模式字符串P的比较起始位置是p（j 2），由该起始位置继续与目标字符串T中上一次比较中失配的字符进行比较；（3）以j＝0为初始位置。上述区别特征均为本领域的常用技术手段，因此权利要求1相对于对比文件1和本领域的常用技术手段的结合不具备创造性。权利要求2-4的附加技术特征也是本领域的常用技术手段，因此也不具备创造性。
驳回决定所依据的文本为：2018年04月09日提交的权利要求第1-4项，2015年04月17日提交的说明书第1-29段，申请日2015年03月30日提交的说明书摘要。
驳回决定所针对的权利要求书如下：
“1. 地理信息数据压缩处理算法，包括定义历史窗口和待编码窗口，所述历史窗口中包括目标字符串T，所述待编码窗口中包括模式字符串P，所述压缩处理算法中包括对目标字符串和模式字符串逐位比较的比较过程，其特征在于，所述压缩处理算法还包括定义失效函数fail (j)＝k，其中k是使得模式字符串P中的连续位字符p（0）、p（1）、… p（k）分别等于 p（j-k）、 p（j-k 1）、… p（j）的最大整数，且k＜j；当在一次比较过程中，如果模式字符串P的第j＋1个位置与目标字符串T的相应位置失配时，且j＞0，则下一次比较时模式字符串P的比较起始位置是p（j 2），由该起始位置继续与目标字符串T中上一次比较中失配的字符进行比较；当在一次比较过程中，如果模式字符串P的第j＋1个位置与目标字符串T的相应位置失配时，且j＝0，则下一次比较时模式字符串P的比较起始位置是p（0），由该起始位置继续与目标字符串T中上一次比较中失配的字符前进一位进行比较。
2. 如权利要求1所述的地理信息数据压缩处理算法，其特征在于，所述待编码窗口的窗口长度采用变长编码定义。
3. 如权利要求1所述的地理信息数据压缩处理算法，其特征在于，在模式字符串的被比较字符串起始位置移动时，定义一个指向起始位置的指针，通过指针移动实现模式字符串的起始位置移动。
4. 如权利要求1所述的地理信息数据压缩处理算法，其特征在于，所述压缩处理算法利用C语言编程实现。”
申请人（下文称复审请求人）对上述驳回决定不服，于2018年11月19日向国家知识产权局提出了复审请求，并提交了权利要求书的全文修改替换页，包括权利要求第1-3项。将原权利要求3作为新的权利要求1，并对权利要求的序号和引用关系进行了适应性修改。复审请求人认为：（1）权利要求1是一个不回溯的匹配过程，对比文件1的KMP算法是一个回溯的匹配算法，二者不同；（2）对比文件1没有公开定义一个指向起始位置的指针；（3）权利要求1解决了如何节省硬件空间以及节省时间开销的技术问题，而对比文件1并未解决这一问题。
复审请求时提交的经修改的权利要求书如下：
“1. 地理信息数据压缩处理算法，包括定义历史窗口和待编码窗口，所述历史窗口中包括目标字符串T，所述待编码窗口中包括模式字符串P，所述压缩处理算法中包括对目标字符串和模式字符串逐位比较的比较过程，其特征在于，所述压缩处理算法还包括定义失效函数fail(j)＝k，其中k是使得模式字符串P中的连续位字符p(0)、p(1)、...p(k)分别等于p(j-k)、p(j-k 1)、...p(j)的最大整数，且k＜j；
当在一次比较过程中，模式字符串P的第j 1个位置与目标字符串T的相应位置失配时，且j＞0，则下一次比较时模式字符串P的比较起始位置是p(j 2)，由该起始位置继续与目标字符串T中上一次比较中失配的字符进行比较；当在一次比较过程中，模式字符串P的第j 1个位置与目标字符串T的相应位置失配时，且j＝0，则下一次比较时模式字符串P的比较起始位置是p(0)，由该起始位置继续与目标字符串T中上一次比较中失配的字符前进一位进行比较；
在模式字符串的被比较字符串起始位置移动时，定义一个指向起始位置的指针，通过指针移动实现模式字符串的起始位置移动。
2. 如权利要求1所述的地理信息数据压缩处理算法，其特征在于，所述待编码窗口的窗口长度采用变长编码定义。
3. 如权利要求1所述的地理信息数据压缩处理算法，其特征在于，所述压缩处理算法利用C语言编程实现。”
经形式审查合格，国家知识产权局于2018年12月27日依法受理了该复审请求，并将其转送至原审查部门进行前置审查。
原审查部门在前置审查意见书中认为：（1）对比文件1公开的KMP算法与本申请一样，目标串T不回溯，当失配后，从当前位置继续比较。KMP变迁表展示的是变量j的变迁，代表的是模式串P的变迁过程，而在实际匹配过程中，目标串T并未回溯。（2）在计算机科学中，指针是编程语言中的常见对象，指针的值直接指向存储器中的地址，通过地址寻找存储的值，属于本领域的公知常识。因此利用指针指向并读取字符串的值，是本领域技术人员常用的技术手段。（3）对比文件1公开了本申请不回溯匹配的算法过程，在提高匹配速度的同时，同样具有节省硬件空间、节省时间的效果。利用指针指向字符串获取字符地址读取存储的值是本领域技术人员常用的技术手段，属于公知常识。因而坚持原驳回决定。
随后，国家知识产权局成立合议组对本案进行审理。
合议组于2019年06月24日向复审请求人发出复审通知书，指出权利要求1中将“则下一次比较时模式字符串P的比较起始位置是p(j 1)”修改为“则下一次比较时模式字符串P的比较起始位置是p(j 2)”不符合专利法第33条的规定，并进一步指出即使克服上述超范围的问题，修改后的权利要求1-3将不具备专利法第22条第3款规定的创造性，理由概述如下：权利要求1与对比文件1的区别特征在于：（1）该算法应用于地理信息数据压缩处理，包括定义历史窗口和待编码窗口，所述历史窗口中包括目标字符串T，所述待编码窗口中包括模式字符串P，所述压缩处理算法中包括对目标字符串和模式字符串逐位比较的比较过程；（2）在模式字符串的被比较字符串起始位置移动时，定义一个指向起始位置的指针，通过指针移动实现模式字符串的起始位置移动。而上述区别特征为本领域的常用技术手段，因此权利要求1相对于对比文件1和本领域的常用技术手段的结合不具备创造性。权利要求2、3的附加技术特征为本领域的常用技术手段，因此权利要求2、3也不具备创造性。
复审请求人于2019年08月09 日提交了意见陈述书，并提交了权利要求书的全文修改替换页，包括权利要求第1-3项。其中，将权利要求1中的“p（j 2）”修改为“p（k）”。复审请求人认为：（1）对比文件1没有公开权利要求1中的“当在一次比较过程中，模式字符串P的第j 1个位置与目标字符串T的相应位置失配时，且j＞0，则下一次比较时模式字符串P的比较起始位置是p(k)，由该起始位置继续与目标字符串T中上一次比较中失配的字符进行比较；当在一次比较过程中，模式字符串P的第j 1个位置与目标字符串T的相应位置失配时，且j＝0，则下一次比较时模式字符串P的比较起始位置是p(0)，由该起始位置继续与目标字符串T中上一次比较中失配的字符前进一位进行比较”，对比文件1的KMP匹配算法在匹配过程中，如果匹配失败，需要回溯从头开始匹配，而本申请在整个匹配过程，对目标字符串T仅需要从头到尾扫描一遍，目标T中的扫描指针不需要回溯，对比文件1与本申请的工作原理不同，所达到的效果也不同，因此对比文件1不能解决现有压缩算法存在的缺陷，本领域技术人员很难想到将对比文件1中KMP算法应用到LZ77得到本申请的技术方案。（2）对比文件1没有公开“在模式字符串的被比较字符串起始位置移动时，定义一个指向起始位置的指针，通过指针移动实现模式字符串的起始位置移动”，对比文件1没有给出关于通过指针指向字符串位置的任何启示，即使得到了关于指针指向字符串位置的启示，本领域技术人员只会想到，每次输出匹配词语之后，把整个窗口的内容向前移若干位，而不是本申请中的通过指针指向字符串位置。
复审请求人提交的新的权利要求书为：
“1. 地理信息数据压缩处理算法，包括定义历史窗口和待编码窗口，所述历史窗口中包括目标字符串T，所述待编码窗口中包括模式字符串P，所述压缩处理算法中包括对目标字符串和模式字符串逐位比较的比较过程，其特征在于，所述压缩处理算法还包括定义失效函数fail(j)＝k，其中k是使得模式字符串P中的连续位字符p(0)、p(1)、...p(k)分别等于p(j-k)、p(j-k 1)、...p(j)的最大整数，且k＜j；
当在一次比较过程中，模式字符串P的第j 1个位置与目标字符串T的相应位置失配时，且j＞0，则下一次比较时模式字符串P的比较起始位置是p(k)，由该起始位置继续与目标字符串T中上一次比较中失配的字符进行比较；当在一次比较过程中，模式字符串P的第j 1个位置与目标字符串T的相应位置失配时，且j＝0，则下一次比较时模式字符串P的比较起始位置是p(O)，由该起始位置继续与目标字符串T中上一次比较中失配的字符前进一位进行比较；
在模式字符串的被比较字符串起始位置移动时，定义一个指向起始位置的指针，通过指针移动实现模式字符串的起始位置移动。
2. 如权利要求1所述的地理信息数据压缩处理算法，其特征在于，所述待编码窗口的窗口长度采用变长编码定义。
3. 如权利要求1所述的地理信息数据压缩处理算法，其特征在于，所述压缩处理算法利用C语言编程实现。”
在上述程序的基础上，合议组认为本案事实已经清楚，可以作出审查决定。
二、决定的理由
（一）审查文本的认定
复审请求人于2019年08月09日提交了修改后的权利要求第1-3项。经审查，上述修改符合专利法实施细则第61条第1款及专利法第33条的规定。本复审决定针对的审查文本为：2019年08月09日提交的权利要求第1-3项，2015年04月17日提交的说明书第1-29段，申请日2015年03月30日提交的说明书摘要。
（二）具体理由的阐述
专利法第22条第3款规定，创造性，是指与现有技术相比，该发明具有突出的实质性特点和显著的进步，该实用新型具有实质性特点和进步。
如果权利要求所要保护的技术方案相对于最接近的现有技术具有区别特征，而该区别特征为本领域的常用技术手段，且本领域技术人员在面对所要解决的技术问题时有动机将上述本领域的常用技术手段应用到最接近的现有技术中以解决所要解决的技术问题，并获得该权利要求所要求保护的技术方案，则该权利要求不具备创造性。
本复审决定所引用的对比文件与驳回决定和复审通知书中所引用的对比文件相同，为：
对比文件1：“入侵检测系统中多模式匹配算法的研究”，董世博，《中国优秀硕士学位论文全文数据库》， 公开日为：2012年09月30日。
1、权利要求1不具备专利法第22条第3款规定的创造性。
权利要求1要求保护一种地理信息数据压缩处理算法。对比文件1公开了一种字符串匹配的KMP算法，并具体公开了以下技术特征（参见第16-18页）：定义失效函数f（j），Next特征数组为失效函数f（j）中j取所有数值的集合，模式串p0…pi-1中最大相同的前缀和后缀的长度k，next[i]＝k，因此对比文件1公开了定义失效函数fail(j)＝k，其中k是使得模式字符串P中的连续位字符p(0)、p(1)、...p(k)分别等于p(j-k)、p(j-k 1)、...p(j)的最大整数，且k＜j；
当在一次比较过程中，若T[i]不匹配P[j]，且1﹤j﹤＝m（即模式字符串P的第j 1个位置与目标字符串T的相应位置失配时，且j＞0），则模式串右移j-next（j）位，检查T[i]和P[next(j)]是否匹配（即下一次比较时模式字符串P的比较起始位置是p(j 1)，而由于指针回退，p(j 1)实质上为p(k)，由该起始位置继续与目标字符串T中上一次比较中失配的字符进行比较）；
当在一次比较过程中，若T[i]不匹配P[j]，且j＝1（即模式字符串P的第j 1个位置与目标字符串T的相应位置失配时，且j＝0），则模式串右移一位，检查T[i 1]与模式字符串P的首字符（即下一次比较时模式字符串P的比较起始位置是p(0)，由该起始位置继续与目标字符串T中上一次比较中失配的字符前进一位进行比较）。
权利要求1与对比文件1的区别特征在于：（1）该算法应用于地理信息数据压缩处理，包括定义历史窗口和待编码窗口，所述历史窗口中包括目标字符串T，所述待编码窗口中包括模式字符串P，所述压缩处理算法中包括对目标字符串和模式字符串逐位比较的比较过程；（2）在模式字符串的被比较字符串起始位置移动时，定义一个指向起始位置的指针，通过指针移动实现模式字符串的起始位置移动。
基于上述区别特征，权利要求1的技术方案实际要解决的技术问题是：如何对地理信息数据进行压缩以及如何移动模式字符串。
关于上述区别特征（1），对于本领域的技术人员来说，LZ77是本领域技术人员常用的数据压缩算法，其具有search buffer窗口（即历史窗口）和look ahead buffer窗口（即待编码窗口），search buffer窗口中为已编解码字符串（即目标字符串T），look ahead buffer窗口中为待编解码字符串（即模式字符串P），在压缩处理算法中对已编解码字符串和待编解码字符串逐位比较，查找二者之间重复的部分，以获得压缩索引。而LZ77算法可用于地理信息数据压缩处理，也是本领域的常规应用。因此，本领域技术人员将对比文件1中公开的KMP算法应用于LZ77算法中，以快速获得已编码字符串和待编码字符串重复的部分，提高压缩效率，是容易想到的，并不存在技术障碍。
关于上述区别特征（2），对比文件1公开了在模式串P右移j-next（j）位时，检查T[i]和P[next(j)]是否匹配，其中j为模式串P的位置变量，指示模式串P的比较起始位置。对于本领域的技术人员来说，定义一个指向起始位置的指针，通过指针移动实现模式字符串的起始位置移动，是本领域的常用技术手段。
因此，权利要求1相对于对比文件1和本领域的常用技术手段的结合不具有突出的实质性特点和显著的进步，不具备专利法第22条第3款规定的创造性。
2、权利要求2、3不具备专利法第22条第3款规定的创造性。
权利要求2对权利要求1作了进一步限定。而变长编码是本领域常用的编码形式，使用变长编码来定义待编码窗口的窗口长度是本领域技术人员的常用技术手段。因此，当权利要求1不具备创造性时，其从属权利要求2也不具备专利法第22条第3款规定的创造性。
权利要求3对权利要求1作了进一步限定。而压缩处理算法利用C语言编程来实现，是本领域技术人员的常用技术手段。因此，当权利要求1不具备创造性时，其从属权利要求3也不具备专利法第22条第3款规定的创造性。
（三）对复审请求人相关意见的评述
对于复审请求人陈述的上述意见，合议组认为：
（1）复审请求人认为对比文件1中公开的KMP算法与权利要求1中的压缩处理算法不同。而实际上二者的算法是完全相同的：权利要求1和对比文件1的技术方案均是采用目标字符串T（对比文件1中的主串T）不回溯，当失配后，进行下一次比较时，目标串T从当前位置（当j＝0时，则前进一位）继续进行比较，而模式字符串P（对比文件1中的模式串P）的比较起始位置通过修改j回溯到k（当j＝0时，为字符串P的首位）继续进行比较。
复审请求人坚持认为“对比文件1的KMP匹配算法在匹配过程中，如果匹配失败，需要回溯从头开始匹配”，而对比文件1中明确记载了（参见第16页）：“若T[i]不匹配P[j]，则分成两种情况：若j＝1，则模式串右移一位，检查T[i 1]和P[1]是否匹配；若1＜j＜＝m，则模式串右移j- next（j）位，检查T[i]和P[next（j）]是否匹配”，可见当T[i]和P[j]失配时，在下一次比较时，对于模式串T来说：起始比较位置是T[i]或T[i 1]，模式串T没有回溯，这与复审请求人所陈述的“本申请在整个匹配过程，对目标字符串T仅需要从头到尾扫描一遍，目标T中的扫描指针不需要回溯”是一致的。对比文件1中的上述内容已经公开了权利要求1中记载的“当在一次比较过程中，模式字符串P的第j 1个位置与目标字符串T的相应位置失配时，且j＞0，则下一次比较时模式字符串P的比较起始位置是p(k)，由该起始位置继续与目标字符串T中上一次比较中失配的字符进行比较；当在一次比较过程中，模式字符串P的第j 1个位置与目标字符串T的相应位置失配时，且j＝0，则下一次比较时模式字符串P的比较起始位置是p(0)，由该起始位置继续与目标字符串T中上一次比较中失配的字符前进一位进行比较”。
因此，对比文件1中公开的KMP算法与本申请中所使用的模式字符串的匹配算法相同，本领域技术人员将对比文件1中公开的KMP算法应用于LZ77算法中，以快速获得已编码字符串和待编码字符串重复的部分，提高压缩效率，是容易想到的，并不存在技术障碍。
（2）对比文件1已经公开了j为模式串P的位置变量，通过j值的变化来改变模式串P的比较起始位置。对比文件1没有公开用指针来实现j的位置的改变，而在本领域中，指针是编程语言中的常见对象，用来指向地址所对应的变量或数组，是本领域的常用技术手段。因此利用指针指向并读取字符串的值，是本领域技术人员常用的技术手段。
因此，合议组对于复审请求人的意见不予支持。
综上所述，合议组依法作出如下复审请求审查决定。
三、决定
维持国家知识产权局于2018年09月03日对本申请作出的驳回决定。
如对本复审请求审查决定不服，根据专利法第41条第2款的规定，复审请求人可以自收到本决定之日起三个月内向北京知识产权法院起诉。
郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
