Generating Natural Anagrams: Towards Language Generation Under Hard Combinatorial Constraints

Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, pages 6408–6412, Hong Kong, China, November 3–7, 2019. c⃝2019 Association for Computational Linguistics 6408 Generating Natural Anagrams: Towards Language Generation Under Hard Combinatorial Constraints Masaaki Nishino1 Sho Takase2∗ Tsutomu Hirao1 Masaaki Nagata1 1 NTT Communication Science Laboratories, NTT Corporation {masaaki.nishino.uh,tsutomu.hirao.kp,masaaki.nagata.et}@hco.ntt.co.jp 2 Tokyo Institute of Technology sho.takase@nlp.c.titech.ac.jp Abstract An anagram is a sentence or a phrase that is made by permutating the characters of an in- put sentence or a phrase. For example, “Trims cash” is an anagram of “Christmas”. Ex- isting automatic anagram generation methods can find possible combinations of words form an anagram. However, they do not pay much attention to the naturalness of the generated anagrams. In this paper, we show that simple depth-first search can yield natural anagrams when it is combined with modern neural lan- guage models. Human evaluation results show that the proposed method can generate signif- icantly more natural anagrams than baseline methods. 1 Introduction Making an anagram is one of the most popu- lar wordplay games and has a long history that can be traced back to the time of the Ancient Greeks (Wheatley, 1862). An anagram is a sen- tence or a phrase that is made as a permutation of characters of an input sentence or phrase. For ex- ample, “Trims cash” is an anagram of “Christmas” since the former can be made by permutating the characters contained in the latter. The automatic generation of anagrams is a chal- lenging task since it is NP-hard1. Existing auto- matic anagram generation methods mainly focus on search efficiency in finding word combinations that can form anagrams (Jordan and Monteiro, 2003). However, they place little consideration on the word orders that seem natural to humans. For- tunately, recent progress in NLP techniques now enables natural sentences to be generated in many ∗This work was conducted while the author was at NTT Communication Science Laboratories. 1NP-hardness of anagram generation can be proved by us- ing the fact that it contains an exact cover problem, which has been proven to be NP-complete (Karp, 1972), as a special case. NLP tasks (J´ozefowicz et al., 2016; Gehrmann et al., 2018; Skadina and Pinnis, 2017). However, beam search, the de-facto decoding algorithm used in many language generation methods, cannot be used as-is to generate anagrams since it cannot en- sure that the generated sentences are anagrams. Although beam search variants that can gener- ate sentences that satisfy some constraints have been proposed (Anderson et al., 2017; Hokamp and Liu, 2017), applying them to anagram gener- ation tasks soon becomes intractable. To summa- rize, generating natural anagrams is a challenging task that cannot be solved by simply applying ex- isting methods. In this paper, we propose an anagram generation algorithm. The proposed algorithm is very simple; we run depth-first search to enumerate anagrams. As to the generation procedure, we use a neural language model and character frequency to sup- …

Content truncated to 500 words