NORMALS or Normal Linguistic Methodology Steganography is a steganography method based on noiseless steganography paradigm or Nostega. In this method, a message is embedded into cover text by modifying the external input of an NLG system (Natural Language Generation) that produce text. The main problem of NORMALS method is small embedding capacity. To solve this problem, this research proposed some method to improve NORMALS method. A better embedding capacity can be achieved by modifying the character encoding used in this research. In addition to modifying the character encoding to make it more efficient, this research also ensures that all the code are evenly distributed, so that in writing the secret message all the code in modified character encoding has almost the same probability to be used. This can reduce suspicion because there is no code that excessively used. The results of the experiments showed that the proposed method has better embedding capacity in hiding the secret message compared to NORMALS, especially for secret messages in the same language with a corpus that is used to modify the character encoding. The proposed method can also be applied using a message to other languages, with reduced embedding capacity. In general, message embedding capacity of proposed method gave the best performance if the secret message written in the same language with the corpus used to modify the character encoding.