  The Lempel-Ziv parsing of a string (LZ77 for short) is one of the most
important and widely-used algorithmic tools in data compression and string
processing. We show that the Lempel-Ziv parsing of a string of length $n$ on an
alphabet of size $\sigma$ can be computed in $O(n\log\log\sigma)$ time ($O(n)$
time if we allow randomization) using $O(n\log\sigma)$ bits of working space;
that is, using space proportional to that of the input string in bits. The
previous fastest algorithm using $O(n\log\sigma)$ space takes
$O(n(\log\sigma+\log\log n))$ time. We also consider the important rightmost
variant of the problem, where the goal is to associate with each phrase of the
parsing its most recent occurrence in the input string. We solve this problem
in $O(n(1 + (\log\sigma/\sqrt{\log n}))$ time, using the same working space as
above. The previous best solution for rightmost parsing uses
$O(n(1+\log\sigma/\log\log n))$ time and $O(n\log n)$ space. As a bonus, in our
solution for rightmost parsing we provide a faster construction method for
efficient 2D orthogonal range reporting, which is of independent interest.
