A symbol string detection unit detects the second symbol string matching the first symbol string having a predetermined length n from input character strings. A matching length detection unit detects a matching length k between the third symbol string following the first symbol string and the fourth symbol string following the second symbol string. A coding unit codes an input symbol string based on the symbol string detected by the symbol string detection unit and the matching length k detected by the matching length detection unit.