一种信息匹配方法及装置.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN105843882A(43)申请公布日2016.08.10(21)申请号201610161559.1(22)申请日2016.03.21(71)申请人乐视网信息技术（北京）股份有限公司地址100089北京市海淀区学院南路68号19号楼六层6184号房间(72)发明人王乙丁(74)专利代理机构北京弘权知识产权代理事务所(普通合伙)11363代理人逯长明许伟群(51)Int.Cl.G06F17/30(2006.01)权利要求书2页说明书7页附图5页(54)发明名称一种信息匹配方法及装置(57)摘要本发明实施例提供了一种信息匹配方法及装置，其中方法包括：获取输入的待检索信息；在预设数据库中按照预设规则查找与所述待检索信息相匹配的数据；输出所查找到的与所述待检索信息相匹配的数据；其中，所述预设数据库中的数据按照Trie树方式存储，并且，所述Trie树中除了普通节点外还包括模糊节点，所述模糊节点用于在需要进行模糊查找时越过同一级中的各兄弟普通节点而直接达到所述同一级中的各兄弟普通节点的子节点。本发明对Trie树的结构进行了改进，在Trie树的普通节点的基础上添加了模糊节点，使之变为更适合模糊匹配的数据结构，使用时可大大减少查找和比较的次数，进而提高了模糊查找的速度。CN105843882ACN105843882A权利要求书1/2页1.一种信息匹配方法，其特征在于，所述方法包括：获取输入的待检索信息；在预设数据库中按照预设规则查找与所述待检索信息相匹配的数据；输出所查找到的与所述待检索信息相匹配的数据；其中，所述预设数据库中的数据按照Trie树方式存储，并且，所述Trie树中除了普通节点外还包括模糊节点，所述模糊节点用于在需要进行模糊查找时越过同一级中的各兄弟普通节点而直接达到所述同一级中的各兄弟普通节点的子节点；所述预设规则包括：按照深度优先算法在所述预设数据库查找与所述待检索信息相匹配的数据，当需要选取下一个节点时，如果此时为模糊查找，则只选取下一个节点中的模糊节点。2.根据权利要求1所述的方法，其特征在于：所述模糊节点分为一级模糊节点和二级模糊节点，所述Trie树的每个普通节点下带有一个一级模糊节点，每个一级模糊节点下带有一个二级模糊节点，所述一级模糊节点的父节点的子子节点中的所有普通节点均链接到当前一级模糊节点下，所述二级模糊节点的祖父节点的子子子节点中所有普通节点均链接到当前二级模糊节点下，作为叶子节点的一级模糊节点储存有同父的所有兄弟普通节点中所储存的数据，作为叶子节点的二级模糊节点储存有同祖父的所有兄弟普通节点中所储存的数据。3.根据权利要求2所述的方法，其特征在于，在获取输入的待检索信息之前，所述方法还包括：获取用于生成所述预设数据库的数据；将所述用于生成所述预设数据库的数据按照Trie树方式存储；在每个Trie树的普通节点下添加一个一级模糊节点，在每个一级模糊节点下添加一个二级模糊节点，将一级模糊节点的父节点的子子节点中的所有普通节点均链接到当前一级模糊节点下，将二级模糊节点的祖父节点的子子子节点中的所有普通节点均链接到当前二级模糊节点下，并令作为叶子节点的一级模糊节点储存有同父的所有兄弟普通节点所储存的数据，作为叶子节点的二级模糊节点储存有同祖父的所有兄弟普通节点所储存的数据，以生成所述预设数据库。4.根据权利要求1所述的方法，其特征在于，通过如下方式判断是否为模糊查找：如果所述待检索信息中包括模糊通配符，则当所述查找进行到所述模糊通配符的位置处时，判断为此时进行模糊查找。5.根据权利要求1所述的方法，其特征在于，所述输出所查找到的与所述待检索信息相匹配的数据，包括：输出所查找到的叶子节点中所存储的数据。6.一种信息匹配装置，其特征在于，所述装置包括：获取单元，用于获取输入的待检索信息；匹配单元，用于在预设数据库中按照预设规则查找与所述待检索信息相匹配的数据；输出单元，用于输出所查找到的与所述待检索信息相匹配的数据；其中，所述预设数据库中的数据按照Trie树方式存储，并且，所述Trie树中除了普通节点外还包括模糊节点，所述模糊节点用于在需要进行模糊查找时越过同一级中的各兄弟普2CN105843882A权利要求书2/2页通节点而直接达到所述同一级中的各兄弟普通节点的子节点；所述预设规则包括：按照深度优先算法在所述预设数据库查找与所述待检索信息相匹配的数据，当需要选取下一个节点时，如果此时为模糊查找，则只选取下一个节点中的模糊节点。7.根据权利要求6所述的装置，其特征在于：所述模糊节点分为一级模糊节点和二级模糊节点，所述Trie树的每个普通节点下带有一个一级模糊节点，每个一级模糊节点下带有一个二级模糊节点，所述一级模糊节点的父节点的子子节点中的所有