Generating all Possible Palindromes from Ngram Corpora

Alexandre Papadopoulos, Pierre Roy, Jean-Charles Régin, François PachetIJCAI 2015

Introduction

Creating a palindrome is a feat of "human virtuosity" because it imposes a brutal dual constraint: the text must make sense at the word level (vocabulary and grammar) while remaining perfectly symmetrical at the character level. From a computational perspective, this is a significant challenge. Character-by-character generation struggles with word validity, while word-by-word search faces an exploding search space due to the unknown center of the palindrome. Standard AI tools like Mixed Integer Programming or SAT solvers typically fail because the number of variables is not fixed.

Methodology: The Graph-Based Approach

The researchers address this by representing the language model as a directed graph. Their approach involves three main steps:

1. The Forward and Backward Graphs

The Forward Graph ($G_f$) represents a corpus (such as the Google Ngram dataset) where nodes correspond to specific character positions within words. Edges represent the flow from one character to the next or transitions between words based on Ngram probabilities.

Character-level graph representation of a word corpus, showing transitions within and between words.

The Backward Graph ($G_b$) is essentially the forward graph mirrored, representing the corpus read in reverse.

2. Graph Conjunction (The "Secret Sauce")

The core innovation is the construction of a Palindrome Graph ($G_p$) via a tensor product (graph conjunction) of the forward and backward graphs. A node in this new graph exists only if the character in the forward traversal matches the character in the backward traversal.

The Palindrome Graph (Gp) constructed via graph conjunction, where each node represents a valid character match from both ends.

By traversing this combined graph from "initial" states (the start/end of words) toward "terminal" states (the symmetry point), any path found is guaranteed to be a valid palindrome. Pruning rules are implemented to discard paths that cannot reach a valid center, maintaining linear complexity relative to the corpus size.

Datasets and Semantic Control

The method was evaluated using several distinct corpora to "flavor" the generated palindromes:

  • Google Ngram Corpus: 2-grams occurring more than 50,000 times for linguistic naturalness.
  • The King James Bible: For religious or archaic tones (e.g., "God all I had, I hid...").
  • Project Gutenberg "Military Art": For tactical or martial themes (e.g., "Drawn in war, died...").

This demonstrates that by changing the underlying corpus, the authors can bias the semantics. Furthermore, by using different corpora for the forward and backward graphs, they can generate ambigrams—sentences that mean one thing forward and another backward.

Key Results and Performance

The algorithm demonstrates remarkable efficiency and scale:

  • World Record Length: It generated a palindrome of 84,541 words (200,001 characters), far exceeding previous human-authored records.
  • Efficiency: Building the graph for the King James Bible (nearly 1 million words) took less than 3 seconds. Once built, the system can generate 10,000 unique palindromes in under a second.
  • Syntactic Flexibility: The method integrates with Part-of-Speech (PoS) patterns, allowing palindromes to follow specific grammatical structures like Subject-Verb-Object (SVO).

Conclusion

While the palindromes are technically perfect and follow local Ngram logic, they often lack deep global meaning. A massive palindrome is a combinatorial triumph but can read like a "fever dream." Future work will focus on optimization—moving from mere satisfiability to generating "good" palindromes using evolutionary search or better scoring metrics for thematic consistency.

Summary updated

BibTeX
@inproceedings{papadopoulos2015generating,
  author = {Alexandre Papadopoulos and Pierre Roy and Jean-Charles Régin and François Pachet},
  title = {{Generating all Possible Palindromes from Ngram Corpora}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure