一句话：将 CSS 规则合并最小化归约为 CSS 图优化，并用 SMT/Max-SAT 求解，实现语义保持的压缩。
本文研究保持语义的 CSS 最小化（minification），核心是通过合并相似规则来缩减文件。由于 CSS 层叠语义对规则顺序敏感，自动找到最优规则合并并不容易。作者将该问题归约为 CSS-graph 优化：节点加权二分图上的边带依赖顺序，权重表示字符数。为此，论文首次完整形式化 CSS3 选择器，并把选择器相交问题归约为无量词整数线性算术的 SMT 可满足性；对 NP-难的图优化问题则采用 Max-SAT 求解。作者实现了规则合并算法，在约 70 个真实样例（含前 20 热门网站）上测试，并与六个知名 minifier 比较；结果显示本工具节省更多，且与这些 minifier 结合时压缩率显著提升。
Minification is a widely accepted technique that aims at reducing the size of the code transmitted over the web. This article concerns the problem of semantic-preserving minification of Cascading Style Sheets (CSS)—the de facto language for styling web documents—based on merging similar rules. The cascading nature of CSS makes the semantics of CSS files sensitive to the ordering of rules in the file. To automatically identify rule-merging opportunities that best minimise file size, we reduce the rule-merging problem to a problem concerning “CSS-graphs,” i.e., node-weighted bipartite graphs with a dependency ordering on the edges, where weights capture the number of characters. Constraint solving plays a key role in our approach. Transforming a CSS file into a CSS-graph problem requires us to extract the dependency ordering on the edges (an NP-hard problem), which requires us to solve the selector intersection problem. To this end, we provide the first full formalisation of CSS3 selectors (the most stable version of CSS) and reduce their selector intersection problem to satisfiability of quantifier-free integer linear arithmetic, for which highly optimised SMT-solvers are available. To solve the above NP-hard graph optimisation problem, we show how Max-SAT solvers can be effectively employed. We have implemented our rule-merging algorithm and tested it against approximately 70 real-world examples (including examples from each of the top 20 most popular websites). We also used our benchmarks to compare our tool against six well-known minifiers (which implement other optimisations). Our experiments suggest that our tool produced larger savings. A substantially better minification rate was shown when our tool is used together with these minifiers.
DOI 原文 ·
@article{paperbot710,
title = {CSS Minification via Constraint Solving},
author = {Matthew Hague and Anthony W. Lin and Chih-Duo Hong},
journal = {ACM Transactions on Programming Languages and Systems},
volume = {41},
number = {2},
year = {2019},
doi = {10.1145/3310337}
}