Startseite Erkunden Hilfe
Registrieren Anmelden
tarfeef101
/
Triehard-Library
1
0
Fork 0
Dateien Issues 0 Pull-Requests 0 Wiki

Lossless compression based on a variation of tries

Struktur: 73363891a5
Branches Tags
Triehard-Lib...
ZIP TAR.GZ
tarfeef101 73363891a5 fixed insertion logicgit add -A now, inserting an extension of a prexisting string works. still looking into issues with curmag being up to date everywhere, i totally forget how i coded this originally :D vor 7 Jahren
.nfs0000000003fe627900002241 d217a4d0cb Removed debug lines from print method vor 7 Jahren
README.md 1bf738f6ef Created a README vor 7 Jahren
a.out 50f8288068 Updated test file vor 7 Jahren
source1.h 73363891a5 fixed insertion logicgit add -A now, inserting an extension of a prexisting string works. still looking into issues with curmag being up to date everywhere, i totally forget how i coded this originally :D vor 7 Jahren
source2.h 7d36ac24f1 Changed to source1, created source2 vor 7 Jahren
test.cc 42daef5230 fixed logic for insertion: now, when a string is inserted into a tree where a prefix of it exists, and the first character after said prefix is the same as the end of that prefix, it does not just add to the magnitude of that node, but properly branches off from there and creates a new node vor 7 Jahren
test.exe 3e05f3520a i fixed all the things :) vor 7 Jahren
test.obj 3e05f3520a i fixed all the things :) vor 7 Jahren
testfile 73363891a5 fixed insertion logicgit add -A now, inserting an extension of a prexisting string works. still looking into issues with curmag being up to date everywhere, i totally forget how i coded this originally :D vor 7 Jahren

README.md

Triehard-Library

A simple library for Triehards, a variation on a compressed binary trie.

Compared to Patricia Tries, these tries do not store "compressed" substrings as the full length of the non-shared part. These take an entirely different approach. Since patricia tries take non-shared substrings and just store them in one node, they reduce the number of nodes, but not storage space. This also means searching them takes, one average, log (m) (where m is height of the tree) plus k, where k is the length of the string since a full comparison still occurs.

On the other hand, triehards compress by reducing the actual amount of data being stored. Each node has a pointer to its children (as usual), a flag to indicate if a stored value ends there (as usual), and a magnitude. This magnitude represents the amount of repeat digits represented by this node. So, if we have a string 11011110, there are 4 nodes, of magnitudes 2, 1, 4, and 1, respectively. This allows for compression based on repeat digits, without increasing the size (each node is of constant size, and there are less nodes than the total length of all strings when compression is possible). This makes the storage overhead lower than O(n) where n is the length of all strings.

As for searching, these retain the same efficiency as a standard trie O(k), compared to the longer search times of patricia tries. Since the compression is based on repeat digits instead of unshared substrings, this allows for standard searching to still occur.