# Practical Challenge of Shredded Documents: Clustering of Chinese Homologous Pieces
## 2 Clustering Method for Chinese Homologous Pieces
### Piece Clustering Based on the Regional Division
#### 2.3.3 Piece Clustering in Area 3  
For area 3 of a document, the left and right boundary pieces are \(L_{b}\) and \(L_{c}\), respectively, and these pieces on the same page can be obtained from Sections 2.3.1 and 2.3.2. From the view of boundary shreds, the pieces in area 3 can be divided into two cases. In the first case, the boundary pieces \(L_{b}\) and \(L_{c}\) have blank blocks in the same line, as shown in Figure 14a; and in the second case, the boundary pieces \(L_{b}\) and \(L_{c}\) do not have blank blocks in the same line, as shown in Figure 14b. Figure 14: Distribution of pieces in area 3 of a document: **(a)** the boundary pieces \(L_{b}\) and \(L_{c}\) have blank blocks in the same line; **(b)** the boundary pieces \(L_{b}\) and \(L_{c}\) do not have blank blocks in the same line. Figure 13: Comparison of the number of character blocks contained in the pieces of area 2. The red boxes mark the character blocks with the same line position in the different pieces. Based on the above analysis, this paper proposes a double-pronged attack strategy and gradual agglomeration strategy to achieve clustering. In the double-pronged attack strategy, which is applied for Figure 14a, because the text and punctuation in the paragraph are continuous in the horizontal direction instead of intermittent [29], when the two boundary pieces \(L_{b}\) and \(L_{c}\) from the same page have one or more blank blocks in the same line, then the paragraphs in these line positions have ended; therefore, all pieces in area 3 of this page of a document are also blank blocks in these line positions. If the pieces have the same blank blocks with both boundary shreds, then they are in the same cluster as two boundary shreds; otherwise, they are not. In the gradual agglomeration strategy, which is applied for Figure 14b, because the end of a paragraph is random, the pieces in area 3 and both boundary shreds lack uniform distributions of characters and blanks. The interrelationships of the text structures (blocks) in the adjacent pieces are used to gradually match the pieces of area 3 with the boundary shred. Using the basic matching algorithm proposed in reference [20], the boundary shred \(L_{c}\) is taken as a starting point; then, the pieces in area 3 are gradually absorbed into the cluster via matching from right to left. When the matching degree of pieces reaches a threshold, the clustering is complete. The following steps constitute the clustering algorithm, which uses the blanks on the same line to realize piece clustering in area 3. We refer to this algorithm as the \"blanks on the same line\" (BSL) algorithm, and flowchart of BSL algorithm is shown in Figure 15.  
In the above algorithm, the reference grouping is an important part of realizing clustering, and its algorithm flowchart is shown in Figure 16. When the pieces in set \(Z\) are clustered, the number of pairs of left-right reference pieces (L-R reference pieces), i.e., \(k\), needs to be determined first. If \(k=1\), then the shreds are clustered using the double-pronged attack strategy (DA Strategy). If \(k\
eq 1\), then there are several pairs of L-R reference pieces, and according to the relationship of blanks on the same line position (BSLP) in different pairs of L-R reference pieces, we divide the pairs into three cases. For the first case, the BSLPs in \(k\) pairs of left-right reference pieces are different. We take each pair of left-right reference pieces as the reference and use the DA Strategy to group the shreds. For the second case, the BSLPs in \(k\) pairs of left-right reference pieces are identical. We take each pair of left-right reference pieces as the reference and use the gradual agglomeration strategy (GA Strategy) to group the shreds. For the third case, in \(k\) pairs of left-right reference pieces, the BSLPs in \(u\) pairs of the pieces are different,and the BSLPs in \(v\) pairs of the pieces are identical, where \(u+v=k\). First, we take \(u\) pairs of left-right reference pieces as the reference and use the DA Strategy to group the shreds.