The Prague Stringology Club Workshop '99

Weiler A. Finamore, Rafael D. de Azevedo and Marcelo da Silva Pinho

On Procedures for Multiple-string Match with Respect to Two Sets

Abstract:
String match procedures with respect to two sets are investigated. The procedures traditionally used for data compression are based on single-string match with respect to a single set (lz78, lzw). Some recent work broadened this view by presenting procedures for multiple-string match with respect to a single set with improved performance as compared to the single-match versions. In this work an algorithm based on double-match with respect to two sets is stated. We do conjecture that multiple-string match procedures with respect to two sets can achieve even better performance. A preliminary analysis corroborating this conjecture with some evidence is reported in this work.

Download article: Article in PostScript Article in PDF
 PostScript   PDF