改进的Trie树和AC算法在Android平台上个性化推荐引擎的设计与实现

发布时间：2020-03-08 10:09

【摘要】：随着科技的高速发展，电脑已从最初的庞然大物发展到现在的掌上电脑（PocketPC），体积的缩小并没有降低它的能力，反而功能更多速度更快。随着用户对掌上电脑处理个人信息方面功能的依赖不断提升，用户不得不随时携带手机和PPC两个设备。于是，聪明的厂商就将掌上电脑的操作系统移植到手机中，智能手机由此诞生了。它就像个人电脑一样，具有独立的操作系统，可以让用户自行安装软件、游戏等第三方应用，通过这些应用来不断地扩充手机的功能，并可以通过移动通讯网络来接入无线网络。一旦接入网络，用户就可以通过搜索引擎查找到任何想要的信息。在搜索领域，胜负已经非常明显。在国外，Google遥遥领先，在国内，百度一枝独秀。然而在推荐领域，至少到目前为止，还没有哪个推荐引擎是当之无愧的市场领导者。目前市场上的智能手机操作系统主要是Android和IOS系统，而据最新数据显示，截止到2012年11月，在全球，Android系统的市场份额已占据全球智能手机操作系统市场的76%，在中国的市场占有率已高达90%。本课题的研究正是基于以上大环境下，希望研发出一种基于Android平台的个性化推荐引擎。该推荐引擎主要采用了改进的Trie树和AC算法来实现。 Trie树，又称字典树，单词查找树或键树，是一种用于快速查找的多叉树结构。Trie树包含三个基本特性：第一，根节点不包含字符，除根节点以外的节点都只含有一个字符；第二，从根节点到指定节点，路径上所有经过的字符拼接起来，即为该节点所代表的字符串；第三，每个节点的所有子节点包含的字符串都必须是不同的。Trie树的核心思想是以空间换时间，利用字符串的公共前缀来降低查询时间以提高效率。它的典型应用就是统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎用于文本词频统计。 AC算法即Aho Corasick字符串匹配算法，是由Alfred V. Aho和MargaretJ. Corasick发明的。所谓字符串匹配也就是从一段文字或文本中找出和输入的字符串相匹配的文字。而AC算法是一个经典的进行多模式匹配的算法，它可以定位出一段文本在一个有限的模式串集合（字典）中的所有元素，而且同时匹配所有的模式。AC算法的关键是在Trie树的基础上构建失败节点。即每个节点都有一个失败节点，当查找到当前节点不匹配时，则直接跳转到当前节点的失败节点继续查找。本课题所研究实现的个性化推荐引擎是基于Android手机的，，它首先获取用户手机上的短信息内容（只限于英文文本），然后对其进行分析得出结果，根据结果向用户推送信息。而该推荐引擎与其他推荐引擎最大的区别在于：它分析的是手机上现存的数据信息，而不是基于浏览器的。本课题所实现的推荐引擎更加高效的利用了用户信息，将推荐功能从网站延伸到手机，使得用户在平时的日常交流中就可以随时得到所需的信息。将其与Android手机平台的结合，为其以后的应用前景提供了广阔的发展空间。
【图文】：

操作图,主题,定义规则,生存周期

满足用户需要的信息直接关系着整个应用的生存周期。因此如何能够高效的从成千上万的规则中进行高效的匹配计算是这次开发面临的最重要的问题。根据rule的定义规则，图3-8显示了一个与主题Sports相关联的一系列操作。

广告图片,推送

成都理工大学硕士学位论文4.4 广告推送模块设计与实现广告推送模块主要用于实现广告推送的控制逻辑。该模块根据推荐引擎分析得出的主题 topic 向用户推送个性化广告服务。4.4.1 广告资源存储在本应用中，根据 rule 规则定义的 12 个主题 topic，分别设置了相应的广告信息，其中包括相关主题的推送询问、图片以及相应的链接地址。他们都以规定的格式分别存储在相应的文件中，这些文件都存放在 assets 目录文件下，随应用一起打包到 APK 安装包中。例如主题 topic Fashion 的推送询问格式及内容为：“Fashion:Do you want the latest fashion offers?”。推送显示的图片如图 4-4 所示。
【学位授予单位】：成都理工大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP391.1

【参考文献】