Home Esplora Aiuto
Registrati Accedi
tarfeef101
/
Triehard-Library
1
0
Forka 0
File Problemi 0 Pull Requests 0 Wiki

Lossless compression based on a variation of tries

Ramo (Branch): working-tareef
Rami (Branch) Tag
Triehard-Lib...
ZIP TAR.GZ
tarfeef101 94b85fe490 migrating remotes, changed some comments 6 anni fa
.nfs0000000003fe627900002241 d217a4d0cb Removed debug lines from print method 7 anni fa
README.md 1bf738f6ef Created a README 6 anni fa
a.out 50f8288068 Updated test file 7 anni fa
source1.h 94b85fe490 migrating remotes, changed some comments 6 anni fa
source2.h 8ef1079219 removing unnecessary continues... so tedious 6 anni fa
source3.h 8fa43f72d6 changed compression calculations to subtract constant size of root nodes 6 anni fa
tasks.txt 94b85fe490 migrating remotes, changed some comments 6 anni fa
test.cc b511b76b44 bugfixes for features in last commit 6 anni fa
test.exe 3e05f3520a i fixed all the things :) 7 anni fa
test.obj 3e05f3520a i fixed all the things :) 7 anni fa
test2.cc 12a6ed7b8c added tasks.txt to keep track of changes to be made.not sure what changes are actually present in the tests... but that's what diff is for 6 anni fa
test3.cc 7d91fae20c fixed compilation errors for test3, started testing/debugging. currently, delete is bugged. whether or not that is because of delete or improper insertion remains to be seen. right now, we have the 4th digit of the string pointing to null where it should point to the 5th element... 6 anni fa
testfile 8fa43f72d6 changed compression calculations to subtract constant size of root nodes 6 anni fa
testfile2 12a6ed7b8c added tasks.txt to keep track of changes to be made.not sure what changes are actually present in the tests... but that's what diff is for 6 anni fa
testfile3 8fa43f72d6 changed compression calculations to subtract constant size of root nodes 6 anni fa

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.