论文名称：
Spell: Streaming Parsing of System Event Logs
1、简介
1、Spell指的是：一个基于LCS（最长公共子序列）的结构化流式事件日志解析器。
2、spell算法以在线流的方式，将非结构化的日志消息解析成结构化的日志类型和参数。
3、处理每个日志条目e的时间复杂度接近于线性（和e的大小线性相关），比drain小多了。
2、Spell
1、LCS问题
LCS就是最长公共子序列。
这个例子简单明了，所谓的最长公共子序列，就是求交集。
2、基本符号与数据结构
在一个日志条目中，我们将一个单词（word）称作一个标记（token）。根据日志的格式，可以使用系统定义的（或者用户自定义的）分隔符将日志条目e解析为一组token。一般来说像是空格或者等号这样的分隔符足以涵盖大多数的情况。
在对一个日志条目进行标记化处理之后，每一个日志条目都被转换成一个“标记”的序列，我们要用这些“标记”的序列来计算最长公共子集。
每个日志条目都被分配一个惟一的行id，初始化为0，并在新日志条目到来时自动递增。
我们创建一个LCSObject的数据结构保存序列和相关的元数据信息。
我们使用LCSseq表示一个序列，它是多个日志消息的LCS（最长公共子序列），（在我们的设置中）它是这些日志条目的消息类型（日志模板）的候选。
也就是说，每个LCSObject包含一个LCSseq和一组行索引(称为lineIds)，这些行索引存储指向这个LCSseq的相应日志条目的行id。
最后，我们将当前解析的所有LCSObjects存储到一个名为LCSMap的列表中。当一个新的日志条目ei到达时，我们首先将它与LCSMap中现有LCSObject中的所有LCSseq进行比较，然后根据结果，将行id i插入现有LCSObject的直线，或者计算一个新的LCSObject并将其插入到LCSMap中。
3、基本工作流
我们的算法以流方式运行，如图1所示。
最初，LCSMap列表是空的。
当到达一个新的日志项 ei 时，首先使用一组分隔符将其解析为一个标记（token）序列 si 。在此之后，我们将 si 与当前LCSMap中所有LCSObject中的LCSseq进行比较，以查看 si 是否“匹配”现有LCSseq中的一个(如果匹配到了，行id i被添加到对应的LCSObject的行id中)，或者（如果没有匹配到）我们需要为LCSMap创建一个新的LCSObject。
获取新的LCS
给出一个新的日志序列s，它是由一个新的日志条目e标记化（tokenization）产生的，我们在LCSMap中搜索。
对于第 i 个LCSObject，假设，它的LCSseq是 qi ，我们计算 li 的值， li 是LCS（qi ， s）的长度。（简单说就是计算新来的日志序列和现有的模板的的最长公共子集的长度）
当我们在LCSMap中搜索的时候，我们保持最长的 li 值和相对应的LCSObject的索引。
在最后，如果
比一个阈值τ（tao）大。
|s|表示序列s的长度，也就是说一个日志条目e中token的个数。
我们认为 LCSseq qj 以及新的日志序列s有着相同的信息类型（全文中的信息类型都指的是日志提取的模板）
直观上来说，qj 和 s 的LCS（最长公共子列）是LCSMap中所有LCSObject中LCS的最大值。LCS（qi ， s）的长度至少是s长度的一半。
因此，除非，e中的参数值的总长度比它自身长度的一半还要长（这在现实中不太可能），LCS（qi ， s）的长度是一个很好的指标（来判断），在第j个LCSObject（它们共享LCSseq qj）中的日志条目是否和 e 共享相同的日志类型（将会是LCS（qi ， s））。
如果有多个 LCSObjects 拥有相同的最大的 l 值，我们选择 |qj| 值最小的那一个，因此，它有一个更高的相似性值设置with s。
然后我们使用回溯（backtracking）来生成一个新的LCS序列来表示第 j 个LCSObject中的所有日志条目和 e 的信息类型。
注意，当我们使用回溯来得到这个新的LCSseq qi 和 s 的时候，我们在两个序列不一致的地方标记为“*”，作为参数的占位符。连续的相邻的“*”，会被合并成一个。
完成上述操作之后，我们将第 j 个 LCSObject 的 LCSseq 从 qj 更新为 LCS(qj,s)，并将 e 的行 id （lineIds）添加到第 j 个 LCSObject 的行 id中。
如果现有的 qi 没有一个与 s 共享长度至少为|s|/2的LCS，我们在LCSMap 中为 e 创建一个新的 LCSObject，并将其 LCSseq 设置为s 本身。
这就完成了Spell算法的基本过程，并且使用这种方法可以成功地解析大多数标准日志。
