According to one embodiment, a compression device includes a coding information generation unit. The unit determines code lengths that are respectively associated with a plurality of symbols, based on a frequency of occurrence of each of the plurality of symbols. When the plurality of symbols include one or more first symbols that are respectively associated with one or more first code lengths exceeding an upper limit, the unit changes the first code lengths to the upper limit, selects, from one or more second symbols of the plurality of symbols that are respectively associated with one or more second code lengths shorter than the upper limit, at least one symbol in descending associated code length order, changes at least one code length associated with the symbol to the upper limit.