关键词: 模式匹配, Unicode编码, KMP算法, B-M算法, Sunday算法

Abstract: When Sunday algorithm is applied into the Chinese version of Unicode, there are some problems. On one hand, it causes the expansion of space if using Chinese characters directly to generate a failed jump table. On the other hand, it can reduce the space consumption at the cost of matching speed when Chinese characters are split into two bytes. Concerning the degradation of time performance produced by applying Sunday algorithm to the character-splitting environment of Chinese version of Unicode, in combination with internal relevance of Chinese unit in Unicode, the improved algorithm in this paper optimized the auxiliary jump table and matching rules in original Sunday algorithm in the character-splitting environment. Consequently, the proposed algorithm not only solves the problem of space expansion, but also improves time performance of Sunday algorithm in this environment. Finally, the improved time and space performance of the algorithm gets proved via simulation.

Key words: pattern matching, Unicode encoding, Knuth-Morris-Pratt (KMP) algorithm, Boyer-Moore (BM) algorithm, Sunday algorithm