A data format for a dictionary-based compressed melody data includes a command part and a data part. The command part includes an index for designating an indexed dictionary entry in a dictionary and indicators for indicating modification/update options for the dictionary. The data part is used to modify the indexed dictionary entry to obtain a decoded musical note. A compressor selects a musical note as a dictionary entry according to a statistical model and records an index in the command part. The compressor further stores a difference between a musical note and an existing dictionary entry in the data part. A decompressor reads an indexed dictionary entry from a dictionary thereof and selectively modifies the indexed dictionary entry by the data part in the compressed data. The decompressor optionally updates the dictionary thereof by the decoded musical note. Therefore, the dictionaries of the compressor and the decompressor can be synchronized.