# 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.2 Piece Clustering in Area 2  
The pieces in area 2 are located on the right side of an entire document. Because the usual Chinese document typography includes a horizontal arrangement in which words start from the left side [27], area 2 mainly reflects the layout of the ends of paragraphs. As shown in Figure 11, three types of characters (words and punctuation) and blank distributions are observed in the horizontal direction at area 2. The first type is \"from character to character\", which means that the paragraph does not end or the paragraph ends just at the rightmost area of a document; therefore, the entire line in area 2 consists of characters (see the regions surrounded by a red border in Figure 11). The second type is the \"from blank to blank\", which means that the paragraph has ended in the front area; therefore, the entire region in area 2 is blank (see the regions surrounded by a blue border in Figure 11). The third type is the \"from character to blank\", which means that the paragraph ends in area 2 and the left side of the line is a character; therefore, the right side is blank (see the regions surrounded by a green border in Figure 11). In Figure 11, because the position of the end of a paragraph is indeterminate, we use the rightmost part of area 2 in a document as the starting point, and from right to left, the blanks may not be continuous, although the characters must be continuous. Therefore, for the shreds in area 2, this paper proposes a clustering algorithm based on the line position of characters (LPC algorithm). Flowchart of LPC algorithm is shown in Figure 12, and each step of LPC algorithm is described in detail as follows. Figure 11: Different distributions of characters and blanks in area 2. Figure 10: Process of piece clustering in area 1. **LPC (line position of characters) Algorithm:**  
Step 1: We take the remaining sparse pieces in set \(S\) as the shreds to be tested, and after the processing in Section 2.3.1, these pieces make up a set \(X\). Step 2: Using the method proposed in [28], all the rightmost pieces and the pieces in set \(X\) are transformed into the corresponding binary code sequence; therefore, a character block in the piece is represented by 1 and a blank block in the piece is represented by 0. Step 3: According to the results of Section 2.2, a rightmost piece \(L_{di}\) (i.e., the rightmost piece of the \(i\)-th page document) corresponding to the leftmost piece \(L_{ai}\) (i.e., the leftmost piece of the \(i\)-th page document) is randomly selected as the starting point of the cluster. Step 4: The line positions of all 1s in \(L_{di}\) are recorded, and a piece \(X_{j}\) in the set \(X\) is randomly selected. \(X_{j}\) and \(L_{di}\) are compared line by line from top to bottom, and when all lines with 1 in \(L_{di}\) also have 1s in \(X_{j}\) then \(X_{j}\) and \(L_{di}\) belong to the same cluster, whereas if all lines with 1 in \(L_{di}\) are not 1s in \(X_{j}\), then \(X_{j}\) and \(L_{di}\) do not belong to the same cluster. Step 5: Step 4 is repeated until all pieces that conform to the condition that come from the same cluster as \(L_{di}\) in the set \(X\) have been classified. Step 6: The pieces that have been grouped with \(L_{di}\) are defined as a set \(Y\) (\(Y\subset X\)). A piece \(Y_{j}\) is randomly selected from \(Y\) and \(Y_{j}\) is XOR'ed with \(L_{di}\)--two binary code sequences bitwise XOR operation. Finally, the result of the bitwise operation is summed, and the sum expresses the difference degree of the two pieces. Step 7: Step 6 is repeated until all pieces in set \(Y\) XOR with \(L_{di}\). The piece with the greatest difference degree is identified and represents the largest difference in the layout with \(L_{di}\). This piece is the critical piece \(L_{ci}\) between area 2 and area 3 in the \(i\)-th page. Step 8: Repeat Step 3 to Step 7 until all clustering beginning with the rightmost piece is completed; subsequently, the clustering algorithm in area 2 ends. Figure 12: Flowchart of LPC (line position of characters) algorithm.