Repository navigation
Terminology
Here's some of the terminology used in some of the discussions and comments throughout the code.
Entropy is a measure of information content. It's measured in bits per symbol. It's believed that the true entropy of English text is around 1 bit per symbol and this is the goal of BWDPerf.
The BWD as a dictionary transform cannot compute a suboptimal dictionary on-line, it needs to buffer up data into blocks or buffers.
A word is a string of symbols. In code, it's represented as a tuple of integers - location of first occurrence and length. The location is a zero-based index in the block.
Words are limited in size by maxWordSize.
Parsing is the process of dividing the block into a stream of words.
Splitting is a part of the parsing process, where we remove all matches of the word in question and replace them with it.
A static dictionary is a list of ordered words that can then be used to parse the block.
A pattern is a structure that can be matched by more than one word. See regex.
The idea of a pattern is that it can represent a lot of similar words using one dictionary entry. This lowers the entropy of the resulting stream at the cost of having to encode extra information about which string exactly was matched.
Examples for a pattern might include:
- The case pattern:
c"some word"will match all of the following:
"some word"
"some Word"
"some WORD"
"Some word"
"Some Word"
"Some WORD"
"SOME word"
"SOME Word"
"SOME WORD"
- The complementary-sequence pattern:
seq"attcg"will match itself and the complementary sequence:
"attcg"
"taagc"
- The verb continuous tense pattern:
verb"*ing"will match any word, ending in "ing":
"doing"
"compressing"
"shining"
"trying"
As you can see, patterns could have matched many strings in the original file. For the decoder to decide which one exactly, it needs extra information. For example, the first pattern has 2 grammatical words, therefore 3^2=9 states are possible. We need a number from 0 to 8 to represent each state. For the sequence pattern, only a bit is enough.
Patterns have many possible structures for endless possibilities. They aren't implemented in code yet.
The ranking function gives us the next best word (according to a metric) to add to the dictionary.
It can be stateful or stateless.
Stateless ranking functions allow for partial re-ranking instead of a full re-rank.
Stateful ranking functions carry a state, that depends on the dictionary calculated so far.
The primitive of the ranking function is the metric used to weigh words. It can also be stateful or stateless.
It follows that a stateless ranking function can't have a stateful primitive. The reverse is possible.
Counting is the process of counting the occurrences of every valid word in the block.
Re-counting is an optimization technique, where instead of counting every word in the block we update the count of affected words.
Matching is a process where we find all locations, that can be replaced by a word.
For example, the word "the" is matched 3 times in the text "the lion and the fox and the mouse".
SA stands for suffix array. That's how it's referred to in the code as well. It's a data structure that holds a sorted list of suffixes.
SA search is when we use the suffix array to search for matches. This improves the time complexity from O(mn) to O(m log n) for a block of size n and a word of size m.
Since searches on the suffix array only happen for words of length less than maxWordLength, we can construct a modified suffix array, where the sorting is only valid for suffixes of length at most maxWordLength. This way, we speed up the suffix array construction from O(n log n) to O(n log m), where usually m is much smaller than n and this results in a 2x-3x perf boost.
Since a boolean array takes up as much space as a byte array, I've implemented a BitVector. Its use case is to store a boolean array in 8 times fewer bytes. Currently, BWD uses it as a way to keep track of what splitting has been done. (In BWD the dictionary is calculated in parallel with parsing, although in the end, we have to parse the whole block again)