For a completely fun project, I want to write a Markov chain chat bot.

The algorithm used is quite simple - break down incoming sentences into tokens, storing what words tend to come after each token (with perhaps a "weight" as more usage is brought in). This would mean that, on average, a sentence would take up twice its length as it's broken down into pairs.


The quick brown fox jumps over the lazy dog =>

The: quick,
quick: brown,
brown: fox,
fox: jumps,

If an incoming word matches something I already have, then the next word is appended to that key, and we continue from a random value with that key.

I need to store these K/V sets in some way where I can look up a lot of words very quickly. For our test sentence above, I need to look across my entire corpus somewhere in the neighborhood of nine times. That is, I iterate over the incoming sentence, tokenize and store it, and then search for each word in order, retrieve a random value from the matching key, and continue until some arbitrary length limit.

Main challenges in order of importance:

  • Search speed: Humor in textual chats is often timing-based, so I need the ability to perform quick lookups over a potentially hundreds of megabytes of plaintext data.

  • Data resilience: Having run one of these bots before, I can tell you that communities tend to become enamored of their bot's "personality". Having to excise large portions of the corpus due to corruption is something I'd like to avoid if at all possible. This would seem to eliminate most naive binary storage or compression methods.

  • Memory usage: While I could just, say, in Python, keep a massive nested dictionary object in memory and pickle/depickle it at shutdown/startup, this seems like the kind of naive solution that would result in hilarious memory usage in short order. While I don't have a hard limit here, I'd like to be able to run this on, say, an AWS T2.micro or thereabouts.

Accuracy is not a huge problem. If I'm running out of some arbitrary amount of time, and need to terminate a search early and just take the "next best thing", such as whatever my iterator is standing on at the moment the time runs out, that is acceptable (and would probably be even a bit humorous)

Using an external database of some kind like Redis or Elasticsearch is not completely out of the question, but I'd like to avoid it if it's not absolutely the best tool for the job.

How would I best structure and address this ever-growing key/value wordlist so that it meets the requirements?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.