# LTmatch: A Method to Abstract Pattern from Unstructured Log
## 3 Log Pattern Extraction Algorithm
### Log Template Extraction Method
#### 3.3.2 Optimized Log Template Extraction Algorithm  
In the basic log template extraction Algorithm 1, the log template for the basic log type warehouse can be obtained. However, as described in Section 3.2.2, when the tree structure of the log storage warehouse is used, in order to ensure the stability of the log template, the basic version of the log template extraction algorithm needs to be improved, and the improved log template extraction algorithm needs to ensure the preview depth length of the word at the position does not change. On the other hand, considering that the advantage of LCS is that the constant part of the log can be accurately obtained, the change of the variable part of the word can be obtained through the precise comparison of the constant part. Therefore, in order to make full use of the advantages of LCS, the improved log template extraction algorithm should be able to further confirm whether the variable corresponds to a single variable or a multivariate variable.  
In order to meet the above requirements, when the log template extraction algorithm is designed, the _depth_ parameter needs to be considered first. During the construction of the log template, if the loop has reached depth, end the loop early and add the first _depth_ words of the logs to be compared directly to the log template. On the other hand, in order to make the information of the final template not only distinguish between variables and constants but also to further refine the variables, the variable part of the algorithm uses two kinds of special signs. One is \"\(<\)\"\(>\)\" to express the single variable, the other one is \"\(<\)\(+\)\(>\)\" to express the multivariate variable. In practice, it is necessary to calculate the longest common subsequence of the two logs to be matched first, and then calculate the lengths of non-matching positions which decision the kinds of special signs to be replaced. If the number of variables between two constant words is greater than or equal to 2, it means that this position is a multivariate variable, so use the special sign \(<\)\(+\)\(>\) for description. Specifically, the log pattern refining algorithm flow is summarized as shown in Algorithm 2.  
```
1:log template in warehouse \(l_{m}\), compared log \(l\), the depth of tree depth
2:log template to return \(retVal\)
3:Initialize:set\(retVal=[]\)
4:\(lcs\gets LCS(l_{m},l)\)
5:if\(length(lcs)<depth\)then
6:return\(retVal\)
7:endif
8:for\(i=length(l)-1,length(l)-2,\ldots,depth\)do
9:if\(length(lcs)==0\)then
10:break
11:endif
12:if\(l[i]==lcs[length(lcs)-1]\)then
13:\(retVal.append(l[i])\)
14:\(lcs.pop()\)
15:else
16:if\(i==length(l)-1\)then
17:\(retVal.append(<*>)\)
18:elseif\(retVal[length(retVal)-1]==<*>\)then
19:\(retVal.pop()\)
20:\(retVal.append(<+>)\)
21:elseif\(retVal[length(retVal)-1]==<+>\)then
22:continue
23:else
24:\(retVal.append(<*>)\)
25:endif
26:endif
27:endfor
28:\(retVal.reverse()\)
29:\(retVal=l[:depth]+retVal\)
```  
**Algorithm 2**Log Template Extraction Algorithm Based On Tree Structure  
According to the Algorithm 2, the template of any two logs can be obtained. The advantage of this algorithm is that it not only increases the information of the log template but also makes the word matching rate algorithm of the log more reasonable because the length of the log template is used in the word matching rate algorithm. Obviously, the position of the multivariate variable in the length should not reflect different length information under the change of the variable length.  
Finally, the entire online log type classification algorithm process represents the Lmatch algorithm in the subsequent experiments if the basic algorithm of log word matching rate, log type warehouse, and log template extraction algorithm in the previous sections are brought into Figure 1. The improved algorithm LTmatch proposed in this paper is obtained by compositing the three optimizations into the process shown in Figure 1.