Speeding up String Searching Algorithms for Nonuniform Texts

概要

論文の詳細を見る
The string searching problem is to find all occurrences of a pattern in a text string. All string searching algorithms can be generally described as a cycle of two-step processing: the checking step, which determines whether the pattern matches with a substring of the text, and the skipping step, which determines the location of next substring possibly matching with the pattern. The fewer the number of character comparisons in the checking step and the farther the jump in the skipping step, the faster the algorithm is. Most of previous work focused on improvement of jump distance in the skipping step. In this paper, we focus on the other important aspect: reducing the number of character comparisons in the checking step based on the feature that the distribution of characters is always nonuniform in natural languages. According to our observation that the character which least occurs in the text is the character which is the most difficult to be matched with in the pattern, we propose a simple method, called cycle method, to reduce the number of character comparisons in the checking step without using any prior knowledge. This method can be used to improve most of the existing algorithms as a general speeding up technique. The empirical experiment shows that performance of improved algorithms is better than that of original algorithms on both the number of character comparisons and the running time.
一般社団法人情報処理学会の論文
1997-07-15

Speeding up String Searching Algorithms for Nonuniform Texts

スポンサーリンク

概要

著者

関連論文

スポンサーリンク