Optimal format for storing key/value data optimized for quick key lookup

Question

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.

Example:

The quick brown fox jumps over the lazy dog =>

The: quick,
quick: brown,
brown: fox,
fox: jumps,
...etc

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?

Answer 1

Store your words as hashes. 32 bits is probably fine, especially if you don't mind very occasional "humorous" mistakes due to hash collisions. You'll need a hash dictionary to translate each hash back into a word.

You're going to need to keep a searchable set of records, let's call them "chain records". Each chain record should contain:

• PrecedingWordsHash: the hash of a preceding word or chain of words.
• FollowingWordHash: the hash of the single word that follows.
• Frequency: a count of the frequency of this pattern.
• HasLongerPattern: a boolean indicating whether this entire pattern (preceding word(s) + following word) is itself part of a longer chain stored in another record.

The hashes should be generated by a cheap method that gives good distribution, such as FNV-1a.

I'm going to assume you want to train on the fly, rather than use a pretrained model, so you'll have to use a tree structure rather than a more compact sorted list. The index for the tree will be PrecedingWordsHash; the resulting value will be a list of (FollowingWordHash,Frequency,HasLongerPattern) triplets. These triplets should be kept as compact as possible, and can be mashed into a single 64-bit value: 32 bits for the hash, 31 bits for frequency and 1 bit for the boolean.

How it is used:

Your chatbot would generate its first word: I guess you keep a simple list of first word frequencies (ordered by frequency descending) to achieve this.

Then it searches in its chain records for that first word, and selects one of the possible patterns. If the selected record contains HasLongerPattern set to true, it can optionally select a longer pattern instead.

Because you're going to encounter many sequences that are extremely rare or unique, you should periodically cull all records with frequency lower than some small threshold, say, 3 or 4. Let your records grow as much as possible between culls, to give the opportunity for genuine common word patterns to grow past that threshold.

Because of this culling, you may have rare occasions when you can't find a next word by searching in the tree, and so you may need a fallback list of words that you can choose from.