Skip to content
Tutorials Center
My learning

Topics

Lesson 113 of 135 ยท Projects

Project: Text Analyzer

Build a text analyzer in C in four stages - read all input into a growing buffer, count lines and words, split words, count them in a hash table and rank the top N.

A word counter sounds like a ten-line program, and the first version really is short. Then the questions arrive. Is "Train," the same word as "train"? Is "child's" one word? What happens when a word is longer than your buffer? How do you count thousands of distinct words without comparing each new word against every word seen so far? Answering those questions well is what turns a toy into a tool, and in C you answer every one of them yourself.

In this project you'll build a text analyzer that reads a passage from the Input box and reports how many characters, words and lines it has, which words appear most often, and a few other statistics. You'll build it in four stages, and each stage is a complete program containing everything so far, because every run starts fresh. Paste your own text into the Input box at any stage and see what the program makes of it.

The project puts many lessons to work at once: reading input until EOF, character classification with ctype.h, dynamic memory and realloc, structures, string functions, hash tables and qsort and bsearch.

The plan

Before writing code, decide how data flows through the program. Some statistics are about lines and characters, and others ignore line breaks completely (a sentence can continue onto the next line). Reading the input once with getchar and computing everything in a single pass is possible, but it tangles unrelated logic together. A cleaner design:

  1. Read the whole input into one growing buffer. For text that fits in memory (a novel is about a megabyte), this is simple and fast.
  2. Count characters, lines and words by scanning the buffer.
  3. Split the buffer into normalized words: lowercase letters, with apostrophes allowed inside a word.
  4. Count each distinct word in a hash table, so each lookup takes roughly constant time.
  5. Rank the words with qsort and print the top N.

Each step is a function with one job, which also makes each stage of this project a small, testable addition.

Stage 1: read everything, count the basics

Reading input of unknown size. You can't know in advance how long the input is, so the buffer has to grow. read_all starts with a small block from malloc and doubles it with realloc whenever it fills up. Doubling matters: growing by a fixed amount (say 64 bytes each time) would copy the data over and over, while doubling keeps the total copying proportional to the input size. This is the same strategy as the dynamic array lesson.

Two realloc rules from the dynamic memory lesson apply here. Never write buf = realloc(buf, size): if realloc fails, it returns NULL but leaves the old block allocated, and that assignment would lose your only pointer to it. Assign to a temporary, check it, and only then replace buf. And always leave room for the terminating '\0', so the buffer is also a valid C string.

What counts as a word? For the basic counts, the program uses the same rule as the Unix wc tool: a word is a run of non-whitespace characters. A flag in_word remembers whether the previous character was part of a word; a word starts whenever a non-space character follows a space (or the beginning of the text). This is a tiny state machine, and it handles multiple spaces, tabs and blank lines without special cases.

What counts as a line? Each '\n' ends a line. But the last line of the Input box often has no newline at the end, so the program adds one more line when the text is not empty and doesn't end with '\n'.

C Stage 1: read all input and count the basics

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The sample has 5 lines and 69 whitespace-separated words. Three details deserve a closer look:

  • (unsigned char)text[i]. The <ctype.h> functions accept an int that must be either EOF or a value representable as unsigned char. Plain char is signed on most desktop compilers, so a byte like 0xE9 would arrive as a negative number, and passing that is undefined behavior. Converting to unsigned char first is the standard fix (see Characters and ASCII).
  • text_counts counts = {0}; zero-initializes every member of the struct, no matter how many there are. Adding a counter later can't leave one uninitialized.
  • Characters are bytes here. chars counts bytes. For English text that's the same thing, but in UTF-8 an accented letter such as "รฉ" takes two bytes, and isalpha (in the default "C" locale) says no to both of them. Real Unicode text handling needs a library; this project sticks to ASCII and says so honestly.

read_all stops at the first '\0' only if you treat the result as a string. The length it returns is the true number of bytes read, which is why count_text takes a length instead of calling strlen. Text files rarely contain zero bytes, but a program that reads unknown input shouldn't silently cut it short.

Stage 2: split the text into real words

The wc rule counts "train." and "train" as different words, and "The" differs from "the". For word frequencies you need normalized words. The rules for this project:

  • A word is a run of letters. Digits, punctuation and spaces separate words, so "twelve stations:" yields "twelve" and "stations".
  • Every letter is converted to lowercase with tolower.
  • An apostrophe between two letters belongs to the word, so "child's" and "it's" stay whole, while a quote mark at the edge of a word is dropped.

next_word implements those rules with a cursor: a const char ** that points at the caller's position in the text. The function skips non-letters, copies the word into the caller's buffer, moves the cursor past the word and returns the word's length. When no words are left, it returns 0. Passing a pointer to the caller's pointer is exactly the "modify the caller's pointer" pattern from Pointers to Pointers.

Long words. The word buffer has a fixed size (MAX_WORD), and a long enough word won't fit. A careless version would write past the end of the buffer; that's the classic buffer overflow. next_word copies at most size - 1 characters but keeps scanning to the real end of the word, and it returns the full length. The caller can then compare the returned length with the buffer size and know the word was truncated. Returning more information than the minimum is a common, useful C idiom: snprintf does the same thing.

C Stage 2: normalized words

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

Look at what the rules did with the tricky second line. "It's" became it's, "o'clock" became o'clock, and the quotes around 'Rain' disappeared because neither apostrophe sits between two letters. The digit 6 is not a word at all. The 45-letter word was stored as its first 31 letters, but its full length was still reported correctly, and nothing was written past the end of the array. The "Longest word" line shows the same truncated spelling next to the true length of 45.

The condition isalpha(p[1]) reads one character past the apostrophe. That's always safe here: the loop only gets there when *p is an apostrophe, so *p isn't the terminator, and p[1] is at worst the '\0' at the end of the buffer.

Normalization rules are design decisions, and every text tool makes them differently. Should "e-mail" be one word? Should "Don't" count as "do" plus "not"? Write your rules down in a comment above the function, as next_word does, so the next reader doesn't have to reverse-engineer them from the loop.

Stage 3: count words with a hash table

Now each word needs a counter. The simplest structure is an array of {word, count} pairs searched from start to end, but then every new word is compared with every stored word. For a text with 20,000 distinct words, that's hundreds of millions of comparisons. A hash table turns the search into: compute a number from the word, use it to pick one small bucket, and compare only with the few words in that bucket.

The table in this stage uses separate chaining: an array of buckets, where each bucket is a linked list of entries. The design decisions:

  • Hash function: FNV-1a. Start with a fixed 32-bit value, and for each byte, XOR it in and multiply by a fixed prime. It's a few lines long, fast and spreads typical words well. Unsigned arithmetic wraps around by definition, so the multiplication overflowing is intended and well-defined (signed overflow would be undefined behavior).
  • Power-of-two capacity. With capacity a power of two, hash & (capacity - 1) picks a bucket with a single AND instead of a slower %.
  • Resize at load factor 0.75. When the number of entries exceeds three quarters of the number of buckets, the table doubles its bucket array and moves every entry into its new bucket. The check size * 4 > capacity * 3 avoids floating point.
  • Each entry owns a copy of its word. The caller's word buffer is reused for the next word, so storing the pointer would be a bug. The C library in our editor doesn't declare strdup in strict C mode (it became standard only in C23, and not every library has caught up), so the program has its own small copy_string.

The table starts deliberately small, with 8 buckets, so you can watch it grow.

C Stage 3: a hash table of word counts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

The table grew from 8 to 16, 32 and finally 64 buckets as the distinct words arrived. After the last resize, the 41 distinct words sit in 30 of the 64 buckets, and the longest chain holds just 3 entries. That is exactly the point: a lookup compares the word with at most three strings, not with all 41.

A few things to notice in the code:

  • table_grow relinks the existing entries. It allocates a new bucket array, but not new entries or new word copies: each entry is moved by changing two pointers. That's cheap, and it means no entry * pointer ever becomes invalid during a resize.
  • Error paths free what they own. If table_add fails halfway, after the entry's malloc but before its word copy, it frees the entry. main frees the table and the text before returning EXIT_FAILURE. Out-of-memory is unlikely here, but practicing complete cleanup on every path is what keeps larger programs leak-free (see Memory Errors).
  • table_count takes const word_table *. Reading a table shouldn't change it, and the const documents and enforces that (const and pointers).

A hash table is only as good as its hash function. Try replacing the body of hash_string with return (uint32_t)strlen(s);. The program still gives correct counts, but most words land in a handful of buckets, the chains get long, and you're back to comparing each word with almost every other. With a large text, that's the difference between milliseconds and minutes.

Stage 4: rank the words and print the report

The final stage adds three features and joins all the pieces into one report.

Stop words. In ordinary English, the most frequent words are always "the", "and", "is" and their friends, which say nothing about the text. The program skips a short list of these stop words. The list is a sorted array of strings, so the program can look words up with bsearch from <stdlib.h> instead of comparing with each one. bsearch passes the comparator a pointer to the key and a pointer to an array element; since the elements are const char *, the element pointer is a const char *const * and must be dereferenced once (see qsort and bsearch). The list must be sorted with the same ordering the comparator uses, here strcmp, or bsearch silently gives wrong answers. The program checks that at startup with an assert-style loop, because a list someone edits by hand will eventually get out of order.

Ranking. A hash table has no useful order, so the program copies a pointer to every entry into a flat array, then sorts the array with qsort. The comparator sorts by count, highest first, and breaks ties alphabetically. Without the tie-breaker, words with equal counts would come out in an order that depends on the hash function and on qsort's internals, and the output would change whenever either did. Sorting pointers instead of entries means each swap moves 8 bytes, and the table itself stays untouched.

The report prints the basic counts from stage 1, the number of distinct words with and without stop words, and the top N words with a small bar chart made of # characters.

C Stage 4: the complete text analyzer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with scanf or fgets), it gets the next line from this box.

With the stop words gone, the top of the list finally says something about the text: it's about a train, which appears 4 times, and words like "never", "counts", "driver" and "bridges" follow. Notice that "count" and "counts" are still separate words. Merging word forms is called stemming, and it's a much harder problem than it looks; that's one of the extension ideas below.

Some details of the final program:

  • table_entries allocates at least one element. malloc(0) may return either NULL or a unique pointer, depending on the library. For an empty input, table.size is 0, and a NULL result would look like an out-of-memory error. Asking for at least one element sidesteps the ambiguity.
  • qsort with 0 elements is fine, and shown is the smaller of TOP_N and the number of distinct words, so a two-word input prints a two-line ranking instead of reading past the end of ranked.
  • The stop word list is static const char *const. The first const says the characters can't change; the second says the pointers in the array can't be redirected. Together with static, the list is private to this file and lives in read-only memory.
  • "it's" is in the list. Because next_word keeps apostrophes, the stop list has to use the same normalized form, or "it's" would slip through. Every stage of a text pipeline must agree on the rules of the previous one.

Try a few experiments in the Input box: paste a paragraph from something you wrote, type the same word with different capitalization, or leave the box empty and check that the program reports zeros instead of crashing.

Ideas to extend it

  • Read the top N from the first input line with fgets and strtol, rejecting anything that isn't a positive number.
  • Sentences. Count runs of ., ! and ? as sentence ends (so "..." counts once) and report the average sentence length.
  • Simple stemming. Strip a trailing "s" from words longer than three letters before counting, and compare the rankings. Then find the words this rule breaks ("bus", "glass").
  • Longest words. Keep the five longest distinct words in a small sorted array as the words arrive.
  • Bigger texts. Replace TOP_N printing with a histogram of word lengths, and test the program with a long text to see how the table resizes.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does read_all assign the result of realloc to a temporary variable instead of writing buffer = realloc(buffer, capacity * 2)?

    A failed realloc returns NULL and leaves the original block untouched. Assigning straight to buffer would leak that block, and the program couldn't even free it.
  2. 2. With the rules of next_word, what words does the input 'Rain' isn't 4 cats! produce?

    Letters are lowercased, the quotes around Rain are dropped because they don't sit between two letters, the apostrophe in isn't does, and the digit 4 is not part of any word.
  3. 3. The table has 16 buckets and already holds 12 distinct words. What happens when a 13th distinct word is added?

    The load factor goes above 0.75 (52 > 48), so table_grow allocates 32 buckets and moves each existing entry into its new bucket by changing pointers.
  4. 4. Why does compare_entries break ties with strcmp?

    Without a tie-breaker, equal elements may end up in any order. Comparing the words makes the output fully determined, which also makes the program easy to test.
  5. 5. What goes wrong if someone adds "but" at the end of the stop_words array without re-sorting it?

    Binary search relies on sorted order to discard half of the array at each step. An unsorted list gives wrong answers silently, which is why stop_words_sorted checks the order before anything else runs.

Summary

  • Read input of unknown size into a buffer that doubles with realloc; assign realloc's result to a temporary, and keep room for '\0'.
  • A one-flag state machine (in_word) counts words without special cases for repeated spaces or blank lines.
  • Pass (unsigned char) values to <ctype.h> functions, and remember that char counts bytes, not Unicode characters.
  • Normalize words with written-down rules: letters only, lowercase, apostrophes inside words. A cursor parameter (const char **) lets a function advance through the caller's text.
  • Never overflow a fixed buffer: copy at most size - 1 characters and return the full length so the caller can detect truncation.
  • A chained hash table with FNV-1a, a power-of-two bucket count and resizing at load factor 0.75 keeps lookups fast; entries own copies of their keys.
  • Rank results by sorting an array of pointers with qsort and a comparator that breaks ties; look up sorted lists with bsearch, and check that they really are sorted.
  • Free everything on every path, including error paths.

Next: Project: Tic-Tac-Toe, where you'll build the game on a 2D array, read moves from the Input box and write a computer player that never loses.