Existing approaches for time series similarity computing are the core of many data analytics tasks. Given the considered data volumes, or simply the need for fast response times, they often rely on shorter representations, usually with information loss. This incurs approximate comparisons where precision is a major issue. We present and experimentally evaluate ASAX, a new approach for segmenting time series before their transformation into symbolic representations. ASAX reduces significantly the information loss incurred by possible splittings at different steps of the representation calculation, particularly for datasets with unbalanced (nonuniform) distributions. We provide theoretical guarantees on the lower bound of similarity measures, and our experiments illustrate that our method outperforms the state of the art, with significant gain in precision for datasets with unbalanced distributions.