๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An improved adaptive string searching algorithm

โœ Scribed by Z. Liu; X. Du; N. Ishi

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
56 KB
Volume
28
Category
Article
ISSN
0038-0644

No coin nor oath required. For personal study only.

โœฆ Synopsis

Sunday's OM algorithm can reduce the number of character comparisons by making use of information of character distribution in an alphabet. Smith's adaptive algorithm uses dynamic statistics to reduce comparisons, and its performance is close to that of the OM algorithm in the number of character comparisons. Smith's algorithm has the advantage of language independence. Its drawback is that it runs slowly because of maintaining an ordering list. This paper presents an improved adaptive method which dispenses with the ordering list. This method treats the pattern as a circle, and first compares the mismatched character in the last checking operation. This method is slightly worse than Smith's method in the number of character comparisons, but it is much better in the running time. ยฉ1998 John Wiley & Sons Ltd.

๐Ÿ“œ SIMILAR VOLUMES

On Simon's string searching algorithm
On Simon's string searching algorithm
โœ Christophe Hancart ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 487 KB
BIDAโˆ—: an improved perimeter search algo
BIDAโˆ—: an improved perimeter search algorithm
โœ Giovanni Manzini ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 937 KB

In this paper we present a new bidirectional heuristic search algorithm. Our algorithm can be viewed as a perimeter search algorithm, and it uses a new technique for reducing the number of heuristic evaluations. We also prove some general results on the behavior of iterative deepening perimeter sea

An improved algorithm for solving the ba
An improved algorithm for solving the banded cyclic string-to-string correction problem
โœ Chung Kuo-Liang ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 339 KB

The banded cyclic string-to-string correction (BCSSC) problem is a generalized version of the cyclic string-to-string correction (CSSC) problem, and has some applications in stereo matching and speech recognition. This note presents an improved algorithm for solving the BCSSC problem and the time co