On Classification of Strings

摘要

In document filtering and content-based routing the aim is to transmit to the user only those documents that match the user's interests or profile. As filtering systems are deployed on the Internet, the number of users can become large. In this paper we focus on the question of how a large set of user profiles can be quickly searched in order to find those that are relevant to the document. In the abstract setting we assume that each profile is given as a regular expression, and, given a set of regular languages (the set of profiles), we want to determine for a given input string (the document) all those languages the input string belongs to. We analyze this problem, called the classification problem for a set of regular languages, and we show that in various important cases the problem can be solved by a small single deterministic finite automaton extended by conditional transitions.