Abulafia: a Markov-Chain text generator

A small C program that reads a .txt file, builds a Markov chain from it, and uses that chain to answer questions typed interactively by the user with generated, plausible-sounding sentences.

What it does

You give Abulafia a text file (a book, a collection of articles, any reasonably-sized body of text). It learns which words tend to follow which others in that text. Then, in a chat-like loop, you type a question and Abulafia replies with a sentence generated by walking through the learned word transitions, loosely "anchored" to a word from your question.

The output is not real natural-language understanding - it's a statistical mimicry of the input text's style. With a small corpus, answers will look very close to verbatim excerpts (few alternatives exist at each step); with a large, varied corpus, the generated sentences become much more novel.

How it works

flowchart TD
    A[Start: ./abulafia corpus.txt] --> B[Load and tokenize corpus.txt]
    B --> C["Build the chain: for every word pair w1,w2,<br/>record the words seen right after it"]
    C --> D["Prompt: You: ..."]
    D --> E{User input}
    E -->|"exit / quit / EOF"| Z[Exit]
    E -->|question| F["pick_seed(): look for a chain pair<br/>starting with a word from the question"]
    F --> G{Match found?}
    G -->|yes| H["Seed = matching pair (w1, w2)"]
    G -->|no| I["Seed = random pair (w1, w2)"]
    H --> J[Print w1 w2]
    I --> J
    J --> K["Look up next words for (w1, w2)"]
    K --> L{Any known next word?}
    L -->|no| P[Stop: dead end]
    L -->|yes| M[Pick one at random,<br/>weighted by frequency]
    M --> N[Print it]
    N --> O{Sentence-ending punctuation<br/>and min length reached?<br/>or max length reached?}
    O -->|yes| P
    O -->|no| Q["Slide window: (w1, w2) -> (w2, next word)"]
    Q --> K
    P --> D

Building

Requires a C compiler (gcc by default) and make.

make

This produces an abulafia executable. To remove it:

make clean

Usage

./abulafia corpus.txt

or, via the Makefile (uses corpus.txt by default, override with FILE=):

make run FILE=corpus.txt

Once started, the program prints how many words and word-pairs it learned, then prompts for input:

Markov chain ready (1532 words, 1140 unique pairs).
Ask a question (type 'exit' to quit):

You: where does the cat live?
> the black cat sleeps on the roof of the house near the garden.

You: exit

Type exit or quit (or send EOF, e.g. Ctrl-D) to leave.

Test corpus

moby.txt is the full text of Moby-Dick; or, The Whale by Herman Melville, downloaded from Project Gutenberg (public domain) and kept in the repo as a ready-to-use, sufficiently large corpus for trying out and demoing the chain (~216k words, ~1.2 MB). A small input produces answers that closely echo the source almost verbatim, since few alternative continuations exist at each step; a corpus this size gives the chain enough alternatives per word pair to produce noticeably more varied, novel-sounding sentences.

Try it with:

make run FILE=moby.txt

Implementation details

The whole program lives in a single file, abulafia.c.

Tokenization. The input file is split on whitespace only (fscanf(f, "%s", ...)). Punctuation stays attached to the word it follows (e.g. "casa." is one token), which is a cheap way to later detect sentence boundaries without a separate parsing pass.
Markov chain, order 2. The chain's key is a pair of consecutive words (w1, w2), mapped to the list of words observed to follow that pair anywhere in the source text. A word that follows a given pair more often is stored multiple times in that list, so picking a random entry from it naturally reproduces the original transition frequencies (higher-probability continuations are more likely to be picked).
Storage. Pairs are kept in a fixed-size hash table (HASH_SIZE buckets) with separate chaining, using the djb2 string hash combined for both words. A flat array of every distinct pair (all_entries) is kept alongside the table so the program can pick a uniformly random pair without walking the whole table.
Answering a question. pick_seed() splits the question into words and looks for one that matches the first word of some known pair in the chain (case-insensitive, punctuation-stripped comparison); if several match, one is chosen at random, which loosely ties the reply to the question's topic. If no word matches anything in the chain, a uniformly random pair is used instead, so the program always produces some output.
Generation. Starting from the seed pair, generate_answer() repeatedly looks up the current pair's list of possible next words, picks one at random, prints it, and slides the pair forward by one word (w1, w2 -> w2, next). Generation stops when: the current pair has no recorded continuation (a "dead end" in the chain), a word ending in ., ? or ! is produced (once at least GEN_MIN_WORDS words have been emitted), or GEN_MAX_WORDS is reached as a safety cap.
Memory. The program allocates freely (strdup, growable arrays) and never frees, relying on process exit to reclaim memory - reasonable for a short-lived interactive CLI tool.