# A Compression-Based Toolkit for Modelling and Processing Natural Language Text
## 4 Sample Applications Provided by the Toolkit
### Search Algorithms  
The Tawa toolkit implements several search algorithms for the method that is used to search for the best transformation TTM_perform_transform method). Various search algorithms can be used to prune the search space produced when the transformations specified by one or more calls to the TTM_add_transform method. Both the Viterbi dynamic programming algorithm [18] and the stack decoding algorithm [26] have been implemented in the toolkit and are available for the developer to trade off accuracy, memory and execution speed. The Viterbi algorithm guarantees that the segmentation with the best compression will be found by using a trellis-based search--all possible segmentation search paths are extended at the same time and the poorer performing alternatives that lead to the use of the same conditioning context are discarded. One of the drawbacks of the Viterbi algorithm is that it is an exhaustive search rather than a selective one, unlike sequential decoding algorithms commonly used in convolutional coding which rely on search heuristics to prune the search space [42]. [PERSON] et al. 's [9] Chinese word segmentation method used a variation of the sequential decoding algorithm called the stack algorithm--an ordered list of the best paths in a segmentation tree is maintained, and only the best path in terms of some metric is extended while the worst paths are deleted. The metric they used was the compression codelength of the segmentation sequence in terms of the order 5 PPMD model. This variation has also been implemented in the toolkit. In the stack algorithm's ordered list, paths vary in length (essentially, it is like a best first search whereas the Viterbi search is more like a breadth first search). For deleting the worst paths, the traditional method is that the list is set to some maximum length, and all the worst paths longer than this length are deleted. For [PERSON] et al. 's [8] PPM word segmenter and in the toolkit, another variation was used instead. All the paths in the ordered list except the first one were deleted if the length of the path plus \(m\) was still less than the length of the first's path, where \(m\) is the maximum order of the PPM model. The reasoning behind this pruning heuristic is that it is extremely unlikely (at least for natural language sequences) that the bad path could ever perform better than the current best path as it still needs to encode a future \(m\) characters despite being already worse in codelength. One further pruning method was also found to significantly improve execution speed. As for the Viterbi algorithm, poorer performing search paths that lead to the same conditioning context are discarded. However, unlike the Viterbi algorithm, search paths vary in length, so only poorer performing search paths with both the same length and conditioning context are discarded. These heuristics have been implemented in the toolkit. In order to illustrate some important aspects of the search process, Figure 3 provides examples of initial search trees for the **segment** and **markup** tools for the small sample text '_the_'. The search tree for this text for the word segmentation problem (using the tool **segment**) is shown in the left box of the figure. The transformed sequences delimited by quotes '' are shown in each node of the tree with an underscore being used (to make it more visible) to indicate where a space has been inserted into the sequence. The root node is for the start of the search where no symbol has been inserted yet. The branching factor of the tree is two as there are two possible transformations--the symbol being processed in the source text is kept unchanged (as represented by the gray nodes); and a space is added after the symbol being processed (as represented by the hashed nodes). So, for example, there are two nodes at level 1 of the tree. Here the first symbol to be processed is the letter '_t_'. Two possible search paths are generated--one for the letter unchanged ('_t_') and one with a space added to it ('_t_').