How I Made a Markov Chain Model from Scratch in C++ During a Global Online Teen Hackathon

Stardance, a global teen online hackathon hosted for teenagers by Hack Club, a nonprofit organization, had just recently ended. I had made many great projects, and I even got a 3D printer, completely for free, because of my work. I was locked and loaded to make another coding project, but I wasn't sure what program I should do it with. So, I stopped for a few days, and eventually found Pixl, something very like Stardance. In fact, they were so similar to each other that I was able to get right back into it and created Corpustein, a blazingly fast N-gram Markov Chain model with a configurable order and a rolling window system, in just 34 hours over 13 days. It is coded completely in the C++20 STL, and it provides an interactive and beautiful TUI just through a user-input loop and ANSI codes.

If you are very confused as to what Corpustein is, it is a mini AI model that generates text token by token using a window of previous tokens (or words) and a container of all the possible n-grams (or groups of X tokens) based on the current window. This is what an N-gram Markov chain (plus a rolling window system) is. It also maintains a set of previously generated tokens to prevent repeating them, but allows common English words to be repeated. Corpustein is also the TUI that lets users interface with it. The thing that makes it different from what you probably think of when you hear "Artificial Intelligence" (most likely a Large Language Model) is that a Markov chain does not remember anything larger than its N-gram window, but an LLM has an attention model, which looks at a very long sequence of tokens to help generate responses. And, with LLMs, semantic similarity is automatically encoded as high-dimensional coordinates in a continuous vector space, while Markov Chains rely on matching exact word sequences. LLMs can also generate reasonable answers to questions they've never seen before because of how they learn more abstract rules, logic, and world knowledge. Whereas Markov Chains usually just repeat fragments of their training data. An LLM is also much slower than a Markov Chain and is way more resource-intensive. Think of Corpustein as a statistical or probabilistic model that generates mostly coherent English.

In my previous project, MDEZ++, I didn't think I got enough experience with actual C++, without the Qt Framework simplifying everything for me. If you want to read the article about it, look here. I definitely can not say the same thing here. I think this was the best thing I've ever done for my low-level coding skills, ever.

Check out the GitHub repository here.

If you are a Hack Club member, you can access the project page here.

If you want a quick download, check this table!

Features

• Fast and Lightweight: Built only on the C++20 STL, Corpustein is fast and consumes virtually no resources.
• Custom Corpus Loading: Users can load custom corpus files to be used by Corpustein. Additionally, Corpustein comes with a vast array of default options already baked into the program for them to load.
• Automatic Configuration: Corpus files contain metadata that provides default settings for the model to use, determined by the content of the corpus by its creator. If the file appears to just be a normal text file without any sort of metadata, it will skip the default settings gracefully.
• Compatibility: With portable, native binaries automatically generated by the CI/CD for both Linux and Windows, Corpustein can be used on just about any system.
• Commands and Settings: Corpustein contains various commands users can run while in the interactive terminal environment to control many things about the model, like the order, maximum sentence count, and much more.
• Alternate Terminal Buffer: Corpustein uses an alternate terminal buffer to make a beautiful, stylized environment. Users are able to enable and disable this alternate terminal buffer right in the CLI.
• Discrete Handling: When the model runs out of token choices, instead of simply stopping the answer, it will choose a new, random token to continue generating text, with the user never knowing it ran out of tokens in the first place.
• Context-Intelligent Repetition Avoidance: Corpustein saves tokens to a history set to prevent repetition in its responses. It references tokens with a set of common English words to never force it into choosing a completely random token because of the avoidance of basic linguistic structural words
• Configurable Typewriting Animation: Instead of throwing the model's entire response to the terminal all at once because of how fast it is, it uses a configurable typewriting animation to make it more appealing.

Devlogs

1: "Minimum Viable Product"

For the past 5.5 hours, I have been working on Corpustein. Corpustein is a Markov Chain built in C++20. I don't have a nice description or branding phrase yet, because I have been waiting for it actually to be slightly usable. Before I make my README, I will set up a GitHub Actions workflow to automatically compile Linux AppImage and Windows EXE files and attach them to Releases. How it works is that the user inputs a prompt, like "What is a transistor?" and the first step is finding a token for the program to start its response with. If you are wondering, a token is one unit of text. Usually, it is a word (that is, for Corpustein), but it could also be a character, punctuation mark, sentence, etc. It will compare the tokens in the user's prompt to the corpus to find a word the user said that is also in the corpus. And basic words like "in", "there", "a", "an", etc., can never be the seed. If it can't find a good seed based on the input text, it will just do a random one. It uses a rolling window where it stores three tokens at once, uses those tokens to find the best next token, and throws out the oldest token from the window so it's still only three tokens. Whenever it runs out of choices, it'll just go get a random window, continue, and everything will be okay. Currently, it has no way to know when to stop. That will be another thing I will do soon. It will just print text forever. The good thing is it doesn't repeat tokens, and it makes understandable sentences.

==================== corpustein v0.1.0 ==================== User: What is a transistor? Corpustein: the transistor in 1947, which significantly compacted computers and led the digital transition. Information technology, particularly optical fiber and main electronic components (resistors, capacitors, etc.) can be created at a microscopic level. Nanoelectronics is Forest in 1914" 

2: "First Release, and Nice Styling!"

I just got the first release out, right here: https://github.com/tyleruploads/corpustein/releases/tag/v0.1.0. And it is precompiled for the user, which is pretty nice. That's from the GitHub Actions Workflow I just made. I also made it look a LOT better! I used an alternate terminal buffer to apply some cool styling.

3: "Added some Settings"

I just added many settings to Corpustein, along with some features too! The first feature is that now, text is streamed to the terminal with a custom typewrite() function. It streams it character by character, waiting a specific amount of time between each one. A setting was added to control the delay between each character. This next setting is probably the most important one, though. I made it so the user can configure the order of the n-gram model. The order is how many tokens it references to figure out the next token. These two settings were originally their own, but I decided to instead make a /set command and put them in there, as /set delay and /set order. I also made a subcommand in /set called max_sentence_count that allows the user to configure how many sentences the model is allowed to output per response. It also automatically scales the maximum tokens per response to 40 times the new sentences. This setting can not be raised higher than 50. Another important thing isthat I gave users the option to enable or disable the alternate buffer. That is pretty important, since if the alternate buffer is on, they can not do any scrolling, and everything is lost when the application is exited. Whereas, without the alternate terminal buffer, they can scroll and keep the responses after they exit the program. This can be accessed by the altbuffer subcommand in /set. Finally, I made it so anything starting with / but isn't a real command will just do the help command instead of outputting text.

4: "A lot of stuff"

Many changes have just been made. Most of these are really large architectural changes. So, here's an ORDERED BY SIGNIFICANCE numbered list.

1. User-Defined and Multiple Default Corpus Support: Now, there are multiple default corpora, as opposed to just one. At the moment, there are 10, consisting of things such as the complete works of William Shakespeare, Mark Twain, and Charles Dickens, every single United States Presidential Inaugural Speech, the Linux Kernel Documentation, and more. Users can also load their own corpora by file path. This can be done with the command /load . Run /load help to view the types. The corpora start with a special format that starts off with a special file signature, then includes some default settings between the signature and the delimiter at the end (===). Here is how a heading looks:

io.github.tyleruploads.corpustein:corpus-file name: The name of the Corpus default_order: An integer between 1 and 8 representing the order of the n-gram model max_sentence_count: An integer representing the maximum sentences for each model's output, which also scales up the maximum tokens and the token history container. === 

1. /stats command: A brand new /stats command has been added! It outputs the name of the current corpus, along with many other things such as the tokens in said corpus, the unique N-gram contexts that occurred as a result of the corpus and the order, and some variables not inherently associated with the corpus, like the maximum sentence count and more.
2. Static Assertion and Preprocessor Directive Right at the Top: Right at the top of the code, a preprocessor directive and static assertion have been added (the static assertion is not in the preprocessor directive). The static assertion ensures it is being compiled with C++20 or higher. The preprocessor directive invokes an error when APP_VERSION is not defined, which prevents a big wall of fatal errors from being shown to the user with no context. APP_VERSION is automatically passed by CMake.

5: "Small but Large Stuff"

I just made some changes to Corpustein that appear small, but are actually large. I will list them here in the order of their commits, because I really don't feel like ordering them by significance again and finicking around with changing all the list numbers on my own when I move around points. The extra half hour is explained in the "Add Features Section to README" point.

• Fixed Silent Error: The code has an unordered set named unordered_repeats that contains a bunch of common English words. The model is programmed to never repeat tokens that are in its token history window, which is equal to four tenths of the maximum token count, which is 40 times greater than the maximum sentence count. If it can not find a token that is not already in the token history after five retries, it will go to a random token. The purpose of the allowed_repeats unordered set is to make sure it is allowed to repeat basic linguistic constructs, such as "the", "and", "he", etc. After checking the code with clang-tidy, I noticed that some of the elements of the unordered set did not have commas after them, which linked some words together. For example, instead of two elements, "himself" and "herself", it was "himselfherself" (just an example; those specific words were not combined in the real program).
• Add Windows Compilation to CI/CD: If you've seen some of my other coding projects, you know that this obviously wasn't done in one commit. It took me four to prevent errors caused by things like not specifying the C++ standard properly (that's what I thought it was when I made the commit, but that wasn't the issue), not using the POSIX version of MinGW, and using Ubuntu 22.04. The Ubuntu version was the main cause of all the errors. With Ubuntu 22.04, it comes with C++11. While it compiled the Linux version fine and used C++20, when I compiled for Windows with the MinGW toolchain, it used C++11 instead of C++20, which obviously didn't work for my application.
• Update README Downloads Section: The downloads section of the README was a bit barren. So, I made a downloads table that now lists the Linux version, the Windows version, and the macOS version (or lack thereof). I also threw in a note for Linux users and for Windows users. The note for Linux users was essentially just: "Mark it as executable" (and some Bash commands in case they're really tired or something and can't do it on their own). But the note for Windows users was essentially just a full tutorial, because I had to include stuff about SmartScreen activation and stuff. And with Linux, I knew I didn't need to write that much, since it's self-evident they have some idea what to do with a tar.gz. The Bash command block was good enough. But for Windows users, I had to throw in the "What do I do with a ZIP File?" segment I derived from my previous project's README.
• Add Features Section to README: This is self-explanatory. I just added some features to the README. But there was a really hard thing with it. Because I know all of my code so good, I couldn't think of anything special or worth nothing about my app. It was just the curse of knowledge. So, I physically printed out my code file and annotated it with my favorite pen (UniBall Signo 207, Black) and made markings like "Modular Design," "Robust Error Handling," "Advanced State Handling," "Fast and lightweight approach," "UX," "Windows UTF-8 Declaration," and a lot of other stuff. Most of it was just nonsense, like if I were a markov model designed to write corporate nonsense. But I eventually narrowed it down. This took about a half hour of manual pen and paper markings not counted by Hackatime, so I am manually adding one extra half hour for this journal entry.
• Add Corpus File and Directory Structure Sections to README: Since Corpustein needs a specific directory structure and supports a custom corpus file format (still plaintext, designed by me, just for this app) to load default settings, I decided to make sure that's evident in the README.
• Add Cornel Movie-Dialog Corpus: I usually don't put single corpora additions in these journal entries. But this one's pretty important, so I decided to. Fun fact: the corpus has 304,719 lines of text. That's a lot. And the really interesting thing is that it has 3,201,791 tokens in it, which makes 1,150,080 unique N-gram contexts with an order of 2. That means there were approximately 10.5 tokens per line. This corpus is definitely the most conversational.

6: "Analysis and Commands"

Those two words, analysis and commands, can summarize this devlog.

For analysis, I made cppcheck, clang-tidy, and (not technically analysis, but close enough), clang-format and address sanitizers automatically run every debug build. It makes the code much more readable, modern, fast, and less error-prone.

For Commands, I added /about, /reload and /history. I really don't need to explain those.

7: "Linux and Optimization"

From my last entry, I have made 6 commits (not counting bumping it to version v0.4.0). Almost all of these relate to either Linux or optimization.

• Allow Linux Users to Store Default Corpora in /usr/local/share/corpustein/corpora: If you are reading that and think it's very peculiar, it'll make sense when you read a bit more. If you don't use Linux and have no clue what /usr/local/share is for, it's where applications store files.
• Make Optimizations and Add Basic Profiling: The optimizations in this point simply consist of making the allowed_repeats unordered set a const reference in the arguments for the get_seed() function (which returns a string), making the tokens vector of strings in the get_ngram_contexts() arguments a const reference, and making another string a const reference. For profiling, I made a Timer class and used it to measure how long it takes to load corpora. I also made it so that when the lines of the corpus are being sent to the variable, it adds newlines where they should be.
• Generate Cleaned Tokens Set at Corpus Loading: Previously, it would clean EVERY SINGLE TOKEN IN THE CORPUS, AFTER EACH AND EVERY PROMPT! That's terrible, since there can be millions of tokens, and they never change after the corpus has been loaded. I have no clue how much faster it made Corpustein, but it must've been a lot. It's probably a lot less resource-intensive now, too.
• Create Linux Setup Script, and add to README: Like my previous project, I had a Linux Setup Script. I copied most of it, then changed a lot of it. The main difference is that Corpustein uses a normal binary and other files it accesses that the user doesn't provide via some sort of UI, but MDEZ++ is just one single AppImage without any files the user doesn't provide via some sort of UI. It took a long, long time. I also added the installation command to the CMakeLists.txt. And I added the script to the README, of course. I am claiming one extra hour because of all of the testing this took, that wasn't in the code editor! I ran the setup script at least 100 times, because it oftentimes didn't work. And, if you're wondering, it was spaced way more than 2 minutes apart between the times I ran the script and made the changes, so the time in between isn't counted. 1 hour is probably an understatement, considering it is 6:11 PM.
• Add /history to README: I simply forgot earlier.

Look at the Linux Setup Script:

8: "Optimization, Modularization, and SIGINT User Directive"

This seems like a weird name, but I'm going with it anyway. On the topic of modularization, I just replaced the ngram_contexts map to hold unordered sets, as opposed to vectors, which greatly sped up the loading. On the topic of modularization, instead of just having one main.cpp, I now also have function_runner.inc and load_corpus.inc. Each holds exactly one lambda function, and they are put in main.cpp with #include statements. If you don't know what an include statement is, it essentially just copies and pastes an entire file right there before compiling. And I made it so that when users press Ctrl + C, instead of just exiting, it'll ask them if they really want to exit. Keep in mind, it still has the feature from before where, when you press Ctrl + C while it is generating text, it will just skip the typewriting animation effect and print it out all at once. And, it's now v0.6.0! I think I'll make it v1.0.0 in a bit, but after I ship it! Yes, that's right, I think it's about time to ship it already! I really can't think of anything else I could add, because it is already so advanced!

EXTRA: Note Sent to Reviewer:

Hello, reviewer! You're probably wondering why I wrote these journal entries like it's a blog article. I came from Stardance, where everything was one. I do recognize that these journals might not be public, and if they aren't, I'll just put them on DEV.to.

Conclusion

If you couldn't tell, this is definitely a long article, probably almost 2,000 words. When I participate in Hack Club events, I keep pushing myself to be a better coder. This was actually my first project in plain C++20 STL, and I learned a lot from it.

Corpustein is currently in the review queue, and I think it's going to go extremely well. On the topic of prizes, here are some things I'm probably going to get:

• Minecraft
• 3D Printing Filament Grant
• Steam Game Grant
• Soldering Iron
• Random Desk Object from Organization

Check out the GitHub Repository here. If you are a Hack Club member, you can access the project page here.

What's the lowest-level thing you've ever done before? Feel free to share in the comments.