The present invention relates to methods and apparatuses for speech signal encoding and decoding. In accordance with the invention, a discrete time speech signal is encoded by identifying a speech element in the speech signal. If the speech element is identified for the first time, the encoder (108) creates a unique tag representing the speech element and an associating between the speech element and the unique tag in a memory and transmits the speech element in discrete time form and the tag and an indication that the tag is to represent the speech element to a decoder (118). If the speech element was identified before, the encoder (108) obtains a unique tag representing the speech element from the memory, removes the speech element from the speech signal and transmits the unique tag representing the speech element as obtained from the memory.