本篇博客是针对TraceSim: A Method for Calculating Stack Trace Similarity的阅读。
在本文中提出了一个新的计算堆栈跟踪相似性的算法，该算法结合了TF-IDF和Levenshtein distance两者，且用了机器学习来构建堆栈跟踪间的相似性度量。
文章中需要注意的关键字：
- Duplicate Crash/Bug Report： 重复的崩溃/错误报告
- Stack Trace：堆栈跟踪
- WER：微软用于管理崩溃报告的系统。
- Information Retrieval Approach： 信息检索方法
- String Matching algorithms：字符串匹配算法
TF-IDF:TF(term frequency)，IDF(inverse document frequency)。
Levenshtein distance:一个字符串匹配方法，在这里被改进用来计算堆栈间距离的度量。
概述
文章和ReBucket想要解决的是类似的问题，也就是对于像WER这样的管理崩溃报告的系统来说：
- 对于给定的报告，在数据库中找到相似的报告并且根据他们属于同一错误的可能性进行排名
- 将一组给定的报告分发到buckets中（分桶）
对于以上两个问题，定义一个好的相似性度量是很重要的，因为输出的质量很大程度上取决于此。而且仔细的改进相似性算法也是很重要，因为大量的报告需要被正确处理，甚至一个相对较小的改进就可以在分桶质量上有很大的提升作用。大多数的重复数据删除研究可以分为两类：基于IT-IDF或是堆栈追踪结构。前者是用到了信息检索方法，后者采用的是字符串匹配方法。本文结合了这两个方法并加了机器学习，设计了TraceSim算法。
算法流程
算法将两个堆栈跟踪（stack traces）作为输入，首先，算法会单独处理stack overflow exceptions(SOEs),因为这些堆栈跟踪包含了大量重复的帧，且他们的相似性可以用TF-IDF有效的计算相似性。
如果输入的堆栈报错不是SOEs将按顺序执行如下三个步骤：
- 计算堆栈跟踪中每一帧的权重
- 计算两个堆栈跟踪中的edit distance，在本方法中，它被定义为带有帧权重的Levenshtein distance
- 将计算所得的Levenshtein distance归一化，作为最终结果
这是算法实现的链接:
单独处理SOEs
作为堆栈溢出异常的堆栈跟踪有很多引用递归调用的重复帧。如果这个递归部分的两个堆栈跟踪相似，那么很可能他们错误情况也是相似的，递归部分相比非递归要多很多，所以复杂的测试对这类堆栈追踪是没必要的，根据帧频率计算他们的近似度就足够了。
文章使用了如下的IT-IDF算法来处理这种情况:
The Algorithm
帧（Frame）权值计算
和ReBucket中类似，在比较两个堆栈追踪时，距离堆栈顶部的帧要更为重要，因为他们一般更可能包含bug的来源。算法将这种影响表示为帧权重：权重越高越重要。
我们确定了两个对权重有影响的因素：
- 堆栈跟踪中帧的位置
- 帧在数据库中所有帧中出现的频率
$f_{i}$被定义为堆栈中的第i个帧，那么对于堆栈中的所有帧$S T=f_{0}, \ldots, f_{N-1}$，权值的计算方式如下：
$\mathit{w}\left(f_{i}\right)=\mathit{lw}_{\alpha}\left(f_{i}\right) * \mathit{gw}_{\beta \gamma}\left(f_{i}\right)$
$l \mathbf{w}_{\alpha}\left(f_{i}\right)$是$f_{i}$的局部权重，对应第一个因素，而$\operatorname{gw}_{\beta \gamma}\left(f_{i}\right)$是$f_{i}$的全局权值，对应了第二个因素。𝛼, 𝛽 and 𝛾是数值超参数，用来提调整模型以适应数据——将算法调整的适应特定的堆栈追踪集合。
对于$f_{i}$，本地的权值的计算公式:
$\mathit{lw}_{\alpha}\left(f_{i}\right)=\frac{1}{i^{\alpha}}$
实践证明离堆栈顶部的帧局部权重更高，因为错误更可能是因为最后的函数调用导致的。
$f_{i}$的全局权重计算根据大伙都了解的信息检索算法来计算：$\mathit{TF}\left(f_{i}\right) * \mathit{IDF}\left(f_{i}\right)$，TF（f）（term frequency）表示帧在特定堆栈中的重要程度，ID（f）(inverse document frequency)表示对于整个堆栈跟踪的库来说，帧(f)有多不常见。在本文中不适用TF部分且认为它等于1，因为不用考虑帧排序，这实际上是关于堆栈中一个帧最重要的信息。这已经在计算$l \mathbf{w}_{\alpha}\left(f_{i}\right)$的时候考虑在内了，因此我们只用用如下的方式计算IDF即可:
$\mathit{IDF}\left(f_{i}\right)=\log \frac{\text { Total num. of stack traces }}{\text { Num. of stack traces } S T: f_{i} \in S T}$
全局权重的计算如下：
$\mathit{gw}_{\beta \gamma}\left(f_{i}\right)=\sigma\left(\beta\left(\operatorname{IDF}\left(f_{i}\right)-\gamma\right)\right)\\\sigma(x)=\frac{1}{1+e^{-x}}$
其中𝛽和𝛾是为了更平滑的调整IDF，我们给堆栈追踪中很常见的帧赋予较小的权重。这些帧可能是使用的开发框架，日志记录或者是线程池，总之是被经常调用的代码块。
Levenshtein Distance的计算
为了用数字表示堆栈跟踪间的差异，文章使用了修改版本的Levenshtein Distance，在经典的Levenshtein Distance包含插入，删除和替换操作的基础上不再考虑转置操作，因为堆栈跟踪中帧的顺序是很重要的，在一个堆栈中调换两个帧的位置是没道理的。
对于两个字符串，经典Levenshtein distance被定义为最少的编辑开销成本，即将一个单词更改为另一个单词所需的最少单字符编辑（插入、删除或替换）次数。
对于两个堆栈跟踪也是用一样的方法，但是这里用到的是之前得到的帧权值。
在计算一个帧的插入，删除或是替换的代价时，我们定义了如下操作成本：插入和删除的代价是帧对应的权重，替换的权重是原帧和新帧的权重之和。
归一化
本文不使用Levenshtein distance的值进行聚类和分类，为了更好理解计算了归一化的相似度值:
$\operatorname{\mathit{sim}}\left(S T^{\prime}, S T^{\prime \prime}\right)=1-\frac{\operatorname{\mathit{dist}}\left(S T^{\prime}, S T^{\prime \prime}\right)}{\sum_{i=0}^{N^{\prime}-1} \mathit{w}\left(f_{i}^{\prime}\right)+\sum_{i=0}^{N^{\prime \prime}-1} \mathit{w}\left(f_{i}^{\prime \prime}\right)}$
在此$\operatorname{\mathit{dist}}\left(S T^{\prime}, S T^{\prime \prime}\right)$就是$S T^{\prime}, S T^{\prime \prime}$的Levenshtein distance，这个步骤让我们更好的理解相似性的结果，就像是深度学习中的softmax函数一样将结果归一化到[0, 1]，通常这样是更好理解的。
