Predicate encodings are information-theoretic primitives that can be transformed generically into predicate encryption schemes for a broad class of predicates (Wee, TCC 2014; Chen, Gay, Wee, Eurocrypt 2015). Starting from the observation that predicate encodings admit a purely algebraic characterization equivalent to the original notion, we obtain several new results about predicate encodings. First, we propose two generic optimizations that improve their efficiency. Second, we propose new transformations for boolean combinations of predicate encodings. Third, we develop several new predicate encodings for boolean formulas and arithmetic span programs. In the important case of boolean formulas, our encodings are more efficient and attribute-hiding; moreover, they support revocation and delegation. Finally, we implement our approach and experimentally validate its efficiency gains.