The state of art in data compression is arithmetic coding, not the better known Huffman method. To a unique data string, arithmetic coding technique assigns a unique fractional value on the number line between 0 and 1. The speed of this algorithm is limited because of its inherent recursive nature. In this paper we present the design of fast decoders using a novel interval tree search method. The decoder can be modeled as a FSM (finite state machine), enabling the application of look-ahead technique to achieve higher speeds. Look-ahead approach leads to slight degradation in performance (in terms of the adder/subtractor delay in the coder/decoder due to increased word lengths). We improve the performance of the decoder by using redundant arithmetic. The tree search method combined with redundant arithmetic and look-ahead leads to desired speed-ups without any degradation in performance.