The String-to-Dictionary Matching Problem

The String-to-Dictionary Matching Problem is defined, in which a string is searched for in all the possible concatenations of the elements of a given dictionary, with applications to compressed matching in variable to fixed length encodings, such as Tunstall´s. An algorithm based on suffix trees is suggested and experiments on natural language text are presented suggesting that compressed search might use less comparisons for long enough patterns, in spite of a potentially large number of encodings.