  In the random deletion channel, each bit is deleted independently with
probability $p$. For the random deletion channel, the existence of codes of
rate $(1-p)/9$, and thus bounded away from $0$ for any $p < 1$, has been known.
We give an explicit construction with polynomial time encoding and deletion
correction algorithms with rate $c_0 (1-p)$ for an absolute constant $c_0 > 0$.
