A compression scheme can be selected for an input data stream based on characteristics of the input data stream. For example, when the input data stream is searched for pattern matches, input stream characteristics used to select a compression scheme can include one or more of: type and size of an input stream, a length of a pattern, a distance from a start of where the pattern is to be inserted to the beginning of where the pattern occurred previously, a gap between two pattern matches (including different or same patterns), standard deviation of a length of a pattern, standard deviation of a distance from a start of where the pattern is to be inserted to the beginning of where the pattern occurred previously, or standard deviation of a gap between two pattern matches. Criteria can be established whereby one or more characteristics are used to select a particular encoding scheme.