Παρακάτω αναφέρονται οι αλλαγές που έχουν γίνει σε σχέση με το Part 1.

Προστέθηκε το αρχέιο AssistingFunction.c στο οποίο υπάρχουν μερικές βοηθητικές συναρτήσεις γενικού σκοπού.

Ανάλογα με την πρώτη γραμμή του init file (DYNAMIC ή STATIC) δημιουργόυμε το αντίστοιχο είδος trie. Επειδή θέλουμε να αποφύγουμε
τους ελέγχους σε κάθε εντολή (Q A D) για το άν το δέντρο είναι static ή dynamic για να κληθούν οι κατάλληλες, χρησιμοποιούμε δείκτες σε συναρτήσεις, στους οποίους αναθέτονται οι σωστές συναρτήσεις ανάλογα με το δέντρο 1 φορά στην αρχή του προγράμματος. Αν κληθεί η add ή η
delete για το static trie μετά το compress, εκτυπώνονται μηνύματα λάθους στον χρήστη από κάποιες "ψεύτικες" συναρτήσεις που υπάρχουν στο 
StaticTrie.c.
Έχουμε δημιουργήσει διαφορετικά αρχεία για το dynamic trie και για το static trie, τα οποία διαχειρίζονται το αντίστοιχο trie.


StaticTrie:
Εαν το trie που θα δημιουργήσουμε έίναι static, τότε χρησιμοποιούμε διαφορετικό είδος nodes από αυτούς που χρησιμοποιούμε στο dynamic,
οι οποίοι ονομάζονται HyperNodes. Περιέχουν ότι και οι nodes του dynamic, εκτός από το isFinal που έχει αντικατασταθεί με πίνακα από 
shorts που ονομάζεται lengths με τόσες θέσεις όσες και οι λέξεις που έχουν γίνει compress σε αυτόν τον κόμβο. Κάθε θέση του πίνακα περιέχει το 
μέγεθος της αντίστοιχης λέξης με πρόσημο - αν η λέξη δεν είναι Final και + αν είναι. Επίσης οι κόμβοι περιέχουν την μεταβλητή lengths_size στην 
οποία αποθηκεύεται το μέγεθος του πίνακα lengths (άρα και το πλήθος των λέξεων που περιέχει ο κόμβος).
Αρχικά, τα n-grams του αρχείου init γίνονται add στη δομή με την κατάλληλη συνάρτηση, οπότε δημιουργούνται HyperNodes τα οποία περιέχουν μόνο 1 
λέξη. Όταν προστεθούν στη δομή όλα τα n-grams, καλείται η συνάρτηση compress η οποία συμπιέζει το trie, και πλέον η δείκτης σε συνάρτηση add
δείχνει σε μια "ψεύτικη" add, έτσι ώστε να μην μπορεί να κληθεί μετά το compress.
Το compress του trie λειτουργεί ως εξής: Για κάθε κόμβο ακολουθούμε το "μονοπάτι" του όσο αυτός και οι επόμενοι από αυτόν έχουν 1 παιδί.
Αν βρούμε κάποιον με (2 ή περισσότερα παιδιά) ή 0 παιδιά, αντιγράφουμε τις λέξεις των προηγούμενων στον πρώτο HyperNode και διαγράφουμε τους 
ενδιάμεσους.Ύστερα καλούμε την compress για κάθε ένα από τα καινούργια παιδιά του. Για εξοικονόμηση χώρου, διαγράφουμε τον πίνακα children
των κόμβων που είναι φύλλα.
Επίσης η question για τα static trie είναι διαφορετική σε σχέση με αυτή για τα dynamic. Πλέον, για κάθε HyperNode συγκρίνουμε τις λέξεις που
περιέχει με τις λέξεις του input string, μέχρι να εξαντληθούν οι λέξεις του κόμβου και μόνο τότε προχωράμε στον επόμενο HyperNode (αν φυσικά έχει 
πετύχει η αντιστοίχιση μεταξύ των λέξεων του input και των λέξεων του HyperNode).


Bloom Filter:
Προστέθηκε η λειτουργία του Bloom Filter για την αποφυγή εισαγωγής διπλότυπων n-gram στο αποτέλεσμα των questions. Η hash function
που χρησιμοποιείται είναι η MurmurHash2, η οποία παίρνοντας σαν input το key με το οποίο θα γίνει το hash, το μήκος του και έναν
τυχαίο αριθμό (seed), εκτελεί πράξεις πολλαπλασιασμού, xor και ολίσθησης και παράγει έναν ακέραιο. Έτσι, ανάλογα με το πόσες hash functions
θέλουμε να χρησιμοποιήσουμε για τη λειτουργία του Bloom Filter, δίνουμε για το ίδιο key διαφορετικά seeds στην murmur hash, και έτσι 
χρησιμοποιώντας την ίδια συνάρτηση μπορούμε να παράγουμε διαφορετικά αποτελέσματα για το ίδιο key. Ο λόγος που επιλέξαμε την murmur hash
είναι η ταχύτητά της, το οτι έχει ομοιόμορφη κατανομή, και πολύ μικρό ποσοστό συγκρούσεων στα αποτελέσματα που παράγει. Ο πίνακας του bloom 
filter, μετά από κάθε question γίνεται reset, οπότε όλες του οι θέσεις παίρνουν την τιμή 0. 

Σημείωση: Για διαφορετικό μέγεθος questions, το μέγεθος του πίνακα του bloom filter και ο αριθμός των hash finctions που χρησιμοποιούνται είναι 
διαφορετικός. Αυτό όμως δεν μπορεί να παραμετροποιηθεί εαν δεν ξέρουμε κατά μέσο όρο πόσα n-grams θα παράξει κάθε question στο αποτέλεσμά της,
και δεν μπορούμε να το προβλέψουμε ούτε από το μέγεθος του .init αρχείου, αφού δεν υπάρχει συσχέτιση ανάμεσα στο πλήθος των n-grams που βάλαμε 
στην αρχή στο trie με το πλήθος των n-gram του αποτελέσματος μια question (π.χ. υπάρχει περίπτωση στο init να εισάγουμε πολύ μεγάλο αριθμό n-gram 
αλλά τα question να είναι πολύ μικρά). Γι αυτό, για το αρχείο small χρησιμοποιούμε μέγεθος πίνακα 9500 και 4 hash functions, και για το medium 
μέγεθος πίνακα 57500 και 5 hash functions. Προτιμήσαμε να δώσουμε μεγαλύτερο μέγεθος στον πίνακα από το να χρησιμοποιήσουμε περισσότερες hash 
functions, έτσι ώστε να μειωθεί η ταχύτητα εκτέλεσης. Με τις παράπάνω παραμέτρους δεν υπάρχει κανένα false positive στο αποτέλεσμα. Στο αρχείο 
BloomFilter.h κάνουμε define τα παραπάνω νούμερα, και χρησιμοποιούμε κάθε φορά το ζευγάρι που θέλουμε ανάλογα με το input (small ή medium) 
σχολιάζοντας το άλλο ζευγάρι. Προφανώς το ζευγάρι για το medium (57500 - 5) δουλεύει και για το small χωρίς να υπάρχουν false positives(αλλά το 
small εκτελείται σε περισσότερο χρόνο), οπότε έχουμε αφήσει αυτό ασχολίαστο.


LinearHash:
Προστέθηκε η δομή Linear Hash Table στην οποία αποθηκεύονται οι κόμβοι του πρώτου επιπέδου του trie. Έχουν προστεθεί τα αρχεία LinearHash.c
και StaticLinearHash.c τα οποία χρησιμοποιούνται για dynamic και static tries αντίστοιχα. Το static στο StaticLinearHash αναφέρεται
στο είδος των κόμβων που διαχειρίζεται και όχι στην λειτουργία της ίδιας της δομής. Στην πρώτη περίπτωση ο Hash Table περιέχει buckets με 
TrieNodes (dynamic trie) ενώ στη δεύτερη buckets με HyperNodes(static trie). Σαν hash function χρησιμοποιείται και πάλι η Murmur Hash 2.
Στην περίπτωση του static trie το hash γίνεται με βάση μόνο την 1η λέξη του HyperNode. Αρχικά, ο πίνακας που περιέχει τα buckets έχει μέγεθος 
1024, και κάθε bucket έχει 10 θέσεις. Τα μεγέθη αυτά γίνονται define στο DynamicTrie.h και StaticTrie.h , για τους 2 διαφορετικούς Hash Tables.
Αν γίνει overflow σε κάποιο bucket, το μέγεθός του διπλασιάζεται με realloc. Επίσης, σε περίπτωση overflow, το καινούργιο bucket που θα 
δημιουργηθεί έχει τόσες θέσεις όσες και το bucket που προκάλεσε το overflow, έτσι ώστε να αποφύγουμε τα συνεχόμενα overflows-splits στην περίπτωση
που το bucket που προκάλεσε το overflow είναι ίδιο με αυτό που έγινε split.

Top K:
Τέλος, προστέθηκε η λειτουργία top k, με την οποία εκτυπώνονται τα πιό δημοφιλή n-grams σε κάθε ριπή. Η κάθε question, (όπως έχει αναφερθεί και 
στο part 1) επιστρέφει μια λίστα της οποίας κάθε κόμβος περιέχει 1 n-gram. Όλα αύτα τα n-grams συνθέτουν το αποτέλεσμά της. Αυτές οι λίστες 
προστίθενται σε μια άλλη λίστα όταν ολοκληρωθεί κάποιο question. Όταν στο .work αρχείο διαβάσουμε F, τότε εμφανίζουμε τα αποτελέσματα των λιστών
που υπάρχουν στην μεγάλη λίστα και δημιουργούμε έναν πίνακα ο οποίος αποτελείται από δομές ngram_frequency. Οι δομές αυτές περιέχουν 1 n-gram και
τις φορές τις οποίες εμφανίστηκε στην ριπή. Όταν εκυπώνουμε ένα n-gram, καλούμε την MapInsert (βρίσκεται στο AssistingFunctions.c), η οποία
ελέγχει αν αυτό το n-gram υπάρχει ήδη στον πίνακα frequency. Αν υπάρχει ήδη, αυξάνει τον αριθμό εμφανίσεών του κατά 1. Αν δέν υπάρχει το εισάγει,
και θέτει τις εμφανίσεις του σε 1. Οπότε, όταν εκτυπωθεί και το τελευταίο n-gram της τελευταίας question, ο πίνακας περιέχει ταξινομημένα 
αλφαρηθμητικά όλα τα n-grams που εμφανίστηκαν, με τον αριθμό εμφανίσεών τους. Για να εκτυπώσουμε τα Κ πιό δημοφιλή από αυτά κάνουμε το εξής:
βρίσκουμε τον μεγαλύτερο αριθμό εμφανίσεων που υπάρχει στον πίνακα frequency, και δημιουργούμε τον reverse array ο οποίος έχει τόσες θέσεις.
Ύστερα, σε κάθε θέση i του reverse array βάζουμε μια λίστα η οποία περιέχει τα ngrams τα οποία εμφανίστηκαν i φορές (π.χ. στην θέση 5 του reverse
array υπάρχει λίστα με τα n-grams που εμφανίστηκαν 5 φορές στο αποτέλεσμα). Τέλος, ξεκινώντας από το τέλος του reverse array, εμφανίζουμε τα K n-grams, πηγαίνοντας προς τα πίσω. Η λίστα σε κάθε θέση του reverse array είναι ταξινομημένη αλφαρηθθμητικα, άρα αν κάποια n-grams εμφανίζονται
ίδιες φορές, πρώτα θα εκτυπωθεί το μικρότερο.


Στις παρακάτω μετρήσεις αναγράφονται οι χρόνοι στους οποίους τρέχει το πρόγραμμα για small και medium datasets. Φαίνεται ο χρόνος για
static input στο οποίο έχει γίνει compress , για static input στο οποίο δεν χρησιμοποιείται compress (για να υπάρξει αντικειμενική σύγκριση,
χρησιμοποιήσαμε το ίδιο init και work με του static, αλλά το trie αντιμετωπίστηκε σαν dynamic, δηλαδή οι κόμβοι που δημιουργήθηκαν ήταν TrieNodes
και όχι HyperNodes αφου δεν θα είχε νόημα να φτιάξουμε HyperNodes εφόσον δεν θα γίνει compress) και τέλος ο χρόνος για dynamic input.

Small static input compressed : 0.546 sec
Small static input not compressed : 0.509 sec
Small dynamic input : 0.582 sec

Medium static input compressed : 23.192 sec
Medium static input not compressed :19.746 sec
Medium dynamic input : 27.756 sec

Σε όλες τις παραπάνω μετρήσεις τα αποτελέσματα, όπως προαναφέρθηκε, δεν έχουν false positives και δεν έχουν leaks.


Στις παρακάτω μετρήσεις φαίνεται η χρονική διαφορά μεταξύ του 1ου μέρους και του 2ου για τα small και medium datasets (με dynamic trie 
αφού στο part 1 δεν είχαμε την έννοια του static).

1ο μέρος small: 1.059 sec

2ο μέρος small: 0.582 sec

1ο μέρος medium : 1 min 3.042 sec

2ο μέρος medium : 27.756 sec

Στον φάκελο UnitTest προστέθηκε το αρχείο UnitTestPart2.c στο οποίο γίνονται unit tests κυρίως σχετικά με τις αλλαγές που έχουν γίνει στο
part 2, για διάφορες περιπτώσεις. Σε μερικά tests γίνεται έλεγχος διαφόρων περιπτώσεων. Για μεταγλώττιση αρκεί η εντολή make ή make unit_test_Part2 και για εκτέλεση η εντολή ./UnitTestPart2 . Για διαγραφή του εκτελέσιμου: make clean_part2 .



================================

Part 1:
Παραδόθηκε το αρχείο [tar] με τα εξής αρχεία:

1) Directory "src":

Αρχεία:

i) makefile

ii) main.c
Ανοίγει τα αρχεία που δόθηκαν στη γραμμή εντολών
Δημιουργεί ένα Trie instance και βάζει μέσα του τα n-grams που βρίσκονται στο init_file.
Μετά, εκτελεί τις εντολές που βρίσκονται στο query_file, αγνοώντας προς το παρόν την εντολή F.

iii) Trie.c - Trie.h

Χρησιμοποιούμε ολική απόκρυψη, ο χρήστης έχει πρόσβαση μόνο σε δείκτη σε αρχικό κόμβο και εκτελεί πράξεις μόνο μέσω των συναρτήσεων.
Κατά τη δημιουργία του δέντρου φτιάχνεται ένας αρχικός κόμβος που δεν περιέχει λέξη.
Η δομή TrieNode έχει τα εξής πεδία: word, children, arraySize, numChildren, isFinal

word είναι η λέξη που αποθηκεύεται σε κάθε κόμβο

children είναι ο πίνακας με τα παιδιά του κόμβου για τον οποίο δεσμεύεται κάποιος αρχικός χώρος άσχετα με τα αρχικά παιδιά, αν χρειαστεί διπλασιάζεται και είναι
ταξινομημένος πάντα σε αλφαβητική σειρά ως προς το word
Το children έχει by value τα παιδιά και όχι δείκτες σε αυτά για εκμετάλευση των πλεονεκτημάτων του locality. Δοκιμάστηκε έκδοση και με δείκτες η οποία έτρεξε στο
δεύτερο dataset που ανέβηκε με σημαντική διαφορά, περίπου -10 δευτερόλέπτα σε επεξεργαστές i5(2.67ghz) και amd phenom(3.4ghz)

arraySize το μέγεθος όσο αφορά τη μνήμη του παραπάνω πίνακα.

numChildren πόσα κελιά έχουν όντως μέσα πληροφορία.

isFinal υποδεικνύει αν η λέξη είναι τερματική ή οχι. Είναι τύπου Bool που ορίζεται στο header αρχείο. Το ορίσαμε ως char για να καταναλώνουμε 1 byte και όχι 4 λόγω int.

TrieAdd:
	Ψάχνει με binary search αν υπάρχει ως παιδί το επόμενο token από το string που δόθηκε. Λόγω strtok δεν μπορεί να δοθεί const char*.
	Αν δεν υπάρχει, το δημιουργεί και το βάζει στη σωστή θέση (αυτή που έχει επιστραφεί από το first του binary search) ώστε να μένει ταξινομημένος ο πίνακας.
	Συνεχίζει μέχρι να εξαντληθεί το string που δόθηκε για εισαγωγή και επιστρέφει Bool σύμφωνα με το αν τα κατάφερε.
	Χρησιμοποιείται η συνάρτηση memmove για το γρήγορο shift των στοιχείων του πίνακα μετά την εισαγωγή νέου κόμβου.
	Δοκιμάστηκε και με συναρτήσεις και αναθέσεις με = , το οποίο ήταν ελαφρώς πιο αργό. Υπάρχουν ακόμα ως comment μέσα στο πηγαίο κώδικα.

break_string:
	Σπάει ένα string στις λέξεις του και τις βάζει σε δισδιάστατο πίνακα, μία λέξη ανά γραμμή.
	
TrieQuestion:
	Για κάθε συνδυασμό, αν υπάρχει το ngram από i έως curr_word_index, το προσθέτει στην ουρά.
	Στο τέλος επιστρέφει μία λίστα με τα αποτελέσματα, χωρίς duplicates.
	Χρησιμοποιείται binary search για την αναζήτηση σε κάθε επίπεδο του trie. Δοκιμάστηκε και έκδοση με
	γραμμική αναζήτηση, και η διαφορά στους χρόνους με input το small dataset ήταν της τάξης των 40-45 
	δευτερολέπτων (η έκδοση με το binary search τρέχει γρηγορότερα).
	
TrieDestroy:
	Καταστρέφει τη δομή αναδρομικά, χρησιμοποιώντας την TrieDestroyPrivate γιατί ο χρήστης δεν έχει πρόσβαση στον δείκτη root.
	Κάθε αναδρομή-κόμβος, καταστρέφει τον εαυτό της αφού καλέσει την ίδια συνάρτηση για όλα τα παιδιά.

TrieDelete:
	Κατεβαίνει αναδρομικά το δέντρο μέχρι να μην μπορεί να πάρει άλλο token από το string εισόδου και βρίσκει και μονοπάτι με τα token  που παίρνει κάθε φορα.
	Στο τέλος, φτάνει έναν κόμβο πριν τον τελικό και αν όντως υπάρχει το ngram στη δομή μας, τον καταστρέφει ή του βγάζει το final, καταστρέφει τον εαυτό του και γυρνάει πίσω αναδρομικά
	μέχρι να βρει διακλάδωση ή άλλο final αν δεν έβγαλε απλά το final από τον τελικό. Κάθε κλήση επιστρέφει στην προηγούμενη, αν πρέπει να διαγραφεί ο κόμβος της ή όχι.
	Επειδή ο χρήστης δεν έχει πρόσβαση στο δείκτη root, καλείτα η TrieDeletePrivate.
	
GetFirstToken:
	Παίρνει ένα string, γυρνάει επόμενο token και μέσω δείκτη επιστρέφει αν υπάρχει άλλο token παραπέρα στο string και τη θέση του.
	
iv) Queue.c - Queue.h
	Είναι μια βοηθητική δομή που χρησιμοποιούμε για να σώζουμε τα αποτελέσματα της TrieQuestion.
	Είναι λίστα γενικού σκοπού και μπορεί να έχει σε κάθε κόμβο οποιονδήποτε τύπο, στην περίπτωσή μας σώζει διευθύνσεις string.
	Έχει μία συνάρτηση, ειδική ώστε όταν γίνεται μία πρόσθεση στοιχείου να ελέγχει αν το string υπάρχει ήδη μέσα και να μην το βάζει.


2) Directory "UnitTest:

	Για unit testing χρησιμοποιούμε το Framework του unity.
	Έχουμε μία main μέσα σε ένα αντίγραφο του Trie.c όπου κάνουμε διάφορα τεστ για διάφορες περιπτώσεις, τα οποία κάνουν όλα pass.

i) Directory Unity-master
	Περιέχει ό,τι χρειάζεται για να χρησιμοποιήσουμε το unity.

ii) makefile

iii) mainTEST_TRIE.c
	Εδώ μέσα γίνονται τα τεστ που αναφέραμε παραπάνω.
=============================