[发明专利]基于用户行为分析的路径倒排表建立、匹配方法及系统

说明书

技术领域

本申请涉及网络技术，特别是涉及基于用户行为分析的路径倒排表建立、匹配方法及系统。

背景技术

在获得网站访问量基本数据的情况下，对有关数据进行统计、分析，从中发现用户访问网站的规律就是用户行为分析。

用户行为分析可以根据用户的浏览轨迹来分析用户的行为，在这种方法中将每个页面看作一个页面节点。用户浏览网站时会查看网站中的网页，通过网页页面中的链接地址可以从一个页面跳转到另一个页面，因此页面间的跳转就可以看作是页面节点间的跳转，那么用户通过链接地址对页面的访问、浏览轨迹，就是多个页面节点间的跳转的运行轨迹。通过对页面节点路径的分析可以了解到用户的访问轨迹，进而了解到用户最常访问的页面以及有可能会访问的页面，以分析用户的行为。

上述通过网页页面中的链接地址，可以由一个页面可以跳转到另一个页面，也就是由一个页面节点连接到另一个页面节点，那么在一个网站中通过链接地址实现页面之间的跳转，就可以构成由页面节点连接而成的页面节点路径图。现有技术在路径匹配时，是将每一个轨迹和所述页面节点路径图进行顺序匹配。例如，假设用户轨迹为：(k)A+B+E，页面节点路径图中定义的路径为：(n)P1：A+B+E+F+H；P2：A+B+E+G+M，那么顺序匹配的结果为：P1，F；P2，G，其中，字母A、B、E、F、G、H和M分别表示一个页面节点，P1和P2为路径标识。根据用户的轨迹来匹配路径，可以得到用户可能的访问路径，用户接下来可能访问页面节点F或页面节点G。

由上述可知，此种算法只要顺着路径的页面节点一个一个的进行匹配即可，但是在一些大型的网站中，拥有非常多的页面，一个页面可以通过链接地址跳转到很多其他的页面上，其他的页面又可以跳转到另一些页面上，这样就形成一幅非常庞大的页面节点路径图。由此组成的路径的规模通常是千级别的，若算法的时间复杂度为O(n)的话(n一般为1000)，那么在亿级别的用户轨迹(k)下，匹配的效率就非常低。

发明内容

本申请提供了基于用户行为分析的路径倒排表建立、匹配方法及系统，以解决原有路径匹配方法效率较低的问题。

为了解决上述问题，本申请公开了基于用户行为分析的路径倒排表建立方法，包括：

将页面节点路径图中的路径拆分为由两个页面节点构成的原子路径，所述原子路径包括两个相邻页面节点组合的强路径和两个相隔页面节点组合的弱路径；

根据所述原子路径对所述页面节点路径图中的路径进行切分，得到所述原子路径在该路径中跳转的页面节点，其中，所述路径由路径标识唯一确定；

建立包含原子路径、路径标识和跳转的页面节点的路径倒排表。

优选的，根据所述原子路径对所述页面节点路径图中的路径进行切分，得到所述原子路径在该路径中跳转的页面节点，包括：

设原子路径中的第一个页面节点为首节点，第二个页面节点为次节点；

将原子路径中的首节点和次节点，按照前后顺序分别与路径中的页面节点进行匹配；

对于匹配的情况，将与次节点匹配的页面节点在路径中跳转的页面节点，作为原子路径在该路径中跳转的页面节点。

同时，本申请还公开了基于用户行为分析的路径匹配方法，包括：

读取路径倒排表和用户轨迹，其中，所述用户轨迹由页面节点构成；

根据页面节点两两组合对用户轨迹进行拆分，得到对应用户轨迹的原子轨迹；

将所述用户轨迹的原子轨迹与路径倒排表中的原子路径进行匹配，得到用户轨迹的原子轨迹对应路径标识和跳转的页面节点；

将用户轨迹的第一个页面节点与所述用户轨迹的原子轨迹逐个进行匹配，并添加匹配的原子轨迹对应路径标识和跳转的页面节点，得到最终输出的组合路径。

优选的，所述将用户轨迹的原子轨迹与路径倒排表中的原子路径进行匹配，得到用户轨迹的原子轨迹对应路径标识和跳转的页面节点，包括：

将所述用户轨迹的原子轨迹与路径倒排表中的原子路径进行匹配；

若匹配，则将路径倒排表中的原子路径对应的路径标识和跳转的页面节点添加到所述用户轨迹的原子轨迹中，得到用户轨迹的原子轨迹对应路径标识和跳转的页面节点；

优选的，所述将用户轨迹的第一个页面节点与所述用户轨迹的原子轨迹逐个进行匹配，并添加匹配的原子轨迹对应路径标识和跳转的页面节点，得到最终输出的组合路径，包括：

将用户轨迹的第一个页面节点与所述用户轨迹的原子轨迹逐个进行匹配；

若匹配，则添加所述用户轨迹的原子轨迹对应路径标识和跳转的页面节点，到所述用户轨迹的第一个页面节点中；