We propose a preorder tree which satisfies an order relation: Keys placed at nodes appear in lexicographic order, when the tree is traversed in preorder. Algorithms for search, insertion and deletion are given. The number of key comparisons in the search is investigated theoretically and by simulation studies and compared with the case of binary search trees. We also give an algorithm for constructing a preorder tree which minimizes the number of key comparisons. Simulation experiments confirm the effectiveness of optimization.

This paper proposes and evaluates a character or symbol code system called EPICS for multilingual information processing. EPICS integrates a variable-length coding system using 16-bit units and a smart virtual machine. EPICS enhances the interchangeability of data. The variable-length coding system provides a huge code space. This huge space can include not only standardized code sets but also non-standardized codes of ancient symbols and user-specific symbols. The smart virtual machine executes inputs as instructions and is dynamically customizable. It allows us to define and modify instructions during runtime and provides us with customization facilities. Customization facilities can be used to specify a sorting order and normalization. Customization also makes it possible for an information producer (sender) to express his intentions or annotations in data and for an information consumer (receiver) to process the data depending on his needs. Moreover, customization enables one to send compressed data and decompression program fragments incrementally and efficiently without predefined decompression algorithms.