Experimental Results on String Matching Algorithms

T. LECROQ

IBP-Litp 1994/12: Rapport de Recherche Litp / Litp research reports
25 pages - Décembre/December 1994 - Document en anglais.

Titre / Title: Experimental Results on String Matching Algorithms

Résumé : Nous présentons des résultats expérimentaux sur des algorithmes de recherches de mots qui sont connus pour etre rapide en pratique. Nous comparons ces algorithmes selon deux critères : le nombre d'inspections de caractères du texte et le temps d'exécution. Ces expériences montrent que pour de grands alphabets et des mots courts l'algorithme Quick Search de Sunday est le plus performant et pour de petits alphabets et des mots longs c'est l'algorithme Reverse Factor de Crochemore et alii est le plus performant.

Abstract : We present experimental results for string matching algorithms which are known to be fast in practice. We compare these algorithms through two aspects: the number of text characters inspections and the running time. These experiments show that for large alphabets and small patterns the Quick Search algorithm of Sunday is the most performant and that for small alphabets and large patterns it is the Reverse Factor algorithm of Crochemore et alii which is the most performant.

Publications internes Litp 1994 / Litp research reports 1994