杜诗晴，王 鹏，汪 卫

（1.复旦大学软件学院，上海 201203；2.复旦大学计算机科学技术学院，上海 201203）

0 概述

日志数据记录了互联网系统运行时的状态以及任务的开始与结束等重要事件，其易于获取且含有丰富的信息，已经成为系统运维领域的重要数据源。系统运行产生的日志数据可被视作时序事件序列，利用序列模式挖掘技术可从时序事件序列中发现有意义的序列模式。挖掘得到的模式结果能够有效帮助工程师理解系统行为，还可进一步用于异常检测、故障诊断与原因分析等任务。

序列模式挖掘是数据挖掘领域中的重要研究课题之一，由AGRAWAL和SRIKANT［1］于1995年提出。传统的序列模式挖掘算法致力于发现序列中频繁出现的序列模式，但是该类算法生成的模式结果集数目众多且信息冗余，不利于人工查看分析，因此从序列中挖掘出高质量低冗余的序列模式具有实际意义。为了减少模式结果的数目并降低模式结果冗余度，常用的方法是筛选出原始结果集中的部分模式作为最终结果返回，使得最终结果中的模式在充分代表原序列中典型行为模式的同时有效降低结果集数目。文本压缩中广泛使用的最小描述长度（Minimum Description Length，MDL）准则［2］是一种有效的筛选准则，该准则使得模式结果集中的复杂度和其代表序列的能力之间达到良好平衡。

目前，文献［3-5］将MDL准则应用于序列模式挖掘，该类算法的基本思路是通过设计编码方案，采用一组模式集合作为字典对原始序列进行编码。……