Repository navigation
Structure of the repository
This is a description of what code does what and how this repo is structured. Skip to the goodies in the src folder.
At the root we have /LICENSE.md, /README.md, /.gitignore, .vscode/. .github/.
These are pretty common configurations for any repo. The .gitignore is .NET specific and generated by the dotnet tool.
There is a solution file BWDPerf.sln that contains a reference to all the projects - it's more of a consistency thing, not much is done there.
The data/ folder contains testing files. Most notably, there's enwik4 through enwik8, the Calgary corpus is located in data/calgary/.
book11 and book111 are temporary, they're prefixes of book1 from the Calgary corpus, as to represent a smaller text file that is not XML heavy like enwik4.
The .md files are text files, usually very small to be able to track what the algorithm is doing. They're with the extension .md because VSCode shows one-line markdown files in multiple lines and makes it easier to read.
The data/genetic/ subfolder contains a python script and a copy-paste of some random DNA sequence from NCBI. It hasn't been updated since the initial commit and you can contribute under the issue #4.
The tests/ folder contains a mstest project. Tests are automatically executed at push using a github action.
There exist tests for different tools and algorithms, so it's a mix of integration tests and unit tests.
The docs/ folder contains articles of research (by myself) and other documentation manifests for different components of the project.
There is a docs/content/ folder containing markdown files, while compiled html is in the root. The reason for this is that the docs folder is hosted using github pages and github pages uses a shitty math engine.
The structure of the docs folder is a work in progress.
Since the project is a .NET 5 library it is not an executable. For rapid testing and trying things out, I use the examples/ folder.
Assume it is always changing until v1.0. After that, it will contain multiple projects that showcase different examples and a separate folder for rapid testing will be created.
The src/ folder contains the library. It is divided into the Architecture, Interfaces, Tools, and Transforms subfolders.
In essence, BWDPerf is a data pipeline. The algorithm BWD is independent of the architecture. The idea is to allow multiple compression schemes and order of algorithms for easy exploring around. In fact, the future of BWDPerf (probably after v2.0) is a visualization project, where the inner workings of compression are demonstrated simply and understandably. Read more about the architecture of the project here: todo link.
The src/Architecture/ folder contains extension methods that tie together the pipeline.
The src/Interfaces/ folder contains interfaces (as general as can be) of the main components in compression algorithms. You can see IModel for modeling data and predictions, ICoder for forward blocks in the pipeline, etc.
To create a new generic component (one that operates on any alphabet of symbols), add an interface that describes how this new component behaves.
The src/Tools/ folder contains commonly used tools. Read more about the tools here: todo link.
The src/Transforms/ folder contains different transforms. Transforms are the building blocks of any data pipeline. They're defined by the ICoder and IDecoder interfaces.
Transforms modify the data - converting it into new symbols, grouping it together, or encoding it as bytes, reordering it...
There are generally 3 types of transforms - sources, main transforms, and serializers. Sources and serializers stand at the ends of the pipeline - sources providing the data and serializers encoding it into a file or uploading it to a network.
Let's start with sources.
There are currently 2 sources in the src/Transforms/Sources/ folder. One for reading files one symbol at a time (streaming variant) and another for reading files in blocks (buffered variant). BWD requires a whole block of memory and thus only uses the buffered source. But when decoding, the streaming source is used because it is simple to request the next byte.
There are 2 different serializers in the src/Transforms/Serializers/ folder. One is for writing to files and one for discarding the output. It is useful to be able to discard the output if you're building a metrics pipeline and only want to measure or benchmark some specific component; you usually generate some output that is useless and don't need to write a new serializer.
The file serializer requires you have converted the data to some structure of bytes and writes them to a file asynchronously.
Unlike the tools/ folder, the src/Transforms/Tools/ folder contains common components, tools, that you can use in your pipeline. A very common example is the MeasureEntropy tool.
The src/Transforms/Modeling/ folder contains the code for modeling. Models are used for predictions in entropy coders.
TODO: make those links.
The Submodels/ folder contains elementary models like order-n models.
The Mixers/ folder contains mixers of models.
Those combine predictions by multiple models and mix them to create a more refined prediction.
Mixers are also considered (non-elementary) models and implement the IModel interface.
TODO: add a link Quantizers take models as input and quantize their prediction to a fraction (usually some k/2^n) that is used by entropy coders to encode symbols.
Converters are obsolete. I'm developing Alphabet structures to replace them.
The implementations of algorithms are in the src/Transforms/Algorithms/ folder. There are currently 2 subfolders for BWD and entropy coder but stuff like BWT can be easily added (especially since there's a suffix array data structure implemented already).
Right now there's a simple not very efficient implementation of rANS as an entropy coder, which stores all predictions in the forward direction and then encodes them backward. You can contribute by adding a good range coder.
There are simple BWDEncoder and BWDDecoder classes that implement the ICoder and IDecoder interfaces and fit BWD into the pipeline.
The BWD class is extracted and contains the logic to find an optimal dictionary.
The Options class contains options for BWD and will soon be obsolete since BWD can automatically detect the best options (mainly word size).
The Counting folder contains implementations of the counting component - counting repeated words. There is only one class but if a fundamentally different counting technique is discovered, I might implement another one.
The Ranking folder contains different ranking functions.
And the entities folder contains different types used by BWD. Mainly that is the BWDictionary and BWDStream types, which are contained in a BWDBlock. Also, a word and a ranked word type for storing words as references in the buffer instead of physical strings (this also ensures every word object exists somewhere in the buffer).