Copyright 1993 INIST-CNRS CC BY 4.0 Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.4871392
Database:
PASCAL Archive
Weitere Informationen
An efficient algorithm to perform multiple pattern match in a string is described in this paper. The proposed match algorithm combines the concept of deterministic finite state automata (DFSA) and Boyer-Moore's algorithm to achieve better performance. Actual experiments were held and the result shows that in the average case it is able to perform pattern match operations sublinearly, i.e., it does not need to inspect every character of the string to perform pattern match operations. The analysis shows that the number of characters to be inspected decreases as the length of patterns increases, and increases slightly as the total number of patterns increases. To match an eight-character pattern in an English string using the proposed algorithm, it inspects only about 17% of all characters of the string, and 33% of all characters of the string when the number of patterns is seven.
