# Efficient Online Log Parsing with Log Punctuations Signature
## 3 Methodology
### Step 3 Search Signature Group  
In this step, we search the signature group to find the most suitable template. The signature group maintains templates with the same signature in a list. The collision index is also the average number of templates in each signature group. Each signature corresponds to a signature group, and the corresponding relationship is recorded in a hash table. By looking at the hash table, we can quickly find the signature group. Due to the small number of templates in each signature group, we find the most suitable template by calculating the log similarity one by one.  
In practice, we traverse the template list in the signature group to find the template with the largest similarity compared with the current log message. If the similarity is greater than a given _similarity threshold_, the template index will be returned. Like prior work, we consider that log messages with the same event type have the same length (cf. Section 2). So, if the length is not the same, the similarity value is zero. The similarity between the log message and the log template is defined as the number of identical tokens divided by the total number.  
In addition, we found that some log templates are very similar because they have the same prefix tokens, and only the last few tokens are different. For example, BGL E99 _\"program interrupt: fp cr field..........*>\"_ and E100 _\"program interrupt: fp cr update..........<*>\"_. We apply a soft prefix tokens matching method before calculating the log similarity to deal with this case. To be specific, we compare the first \(N\) non-punctuation tokens between the template and the message. If tokens in the same position do not contain digital characters and are not the same, we think the template does not match. The user specifies the variable \(N\) as a hyperparameter called _prefix threshold_. The complete process of log similarity calculation is shown in Algorithm 2.  
As each signature group contains an independent subset of the whole messages, existing online log parsing methods can also be applied to search templates inside each signature group. Take Drain for example, the core data structure of Drain is a fixed-depth tree. If we want to utilize Drain to search signature groups, we build such a tree structure and adopt all Drain steps inside each signature group. In our experiment, we introduce our log signature method to Spell and Drain in this way.  
```
Input: The split \(template\_token\_list\); the split \(content\_token\_list\); prefix threshold \(pt\). Output: A number ranges \([0,1]\) representing the log similarity.
1\(m,n=len(template\_token\_list),len(content\_token\_list);// the length of token list should be the same
2 if\(m\)!=\(n\)then
3 return0
4 end
5\(count,total=0,0\);
6 for\(t\)l,\(t\)2 in zip(template\_token\_list,content\_token\_list)do
7 if\(t\)1 in\(P\)UNCTULATION\(\_\)TABLE or\(t\)2 in\(P\)UNCTULATION\(\_\)TABLE then // punctuations should be the same
8 if\(t\)1!=\(t\)2 then
9 return0
10 end if
11 else
12 if\(t\)1==\(t\)2 then
13\(count+=1\);
14
15 end if
16// soft prefix tokens matching
17 ifnot(t1 contains digital character or\(t\)2 contains digital character)then
18 if\(pt>0\)then
19 return0
20 end if
21
22 end if
23\(total+=1\);
24\(pt-=1\);
25
26 end if
27
28 end for
29 return\(count/total\)
```  
**Algorithm 2**Log similarity