Αλγόριθμος αυτόματης συμπλήρωσης κειμένου με χρήση συμπαγών δέντρων και δομών δεδομένων

Abstract

Ο κώδικας του προγράμματος αποτελείται από 3 αρχεία .cpp 2 αρχεία .h και το makefile. Συγκεκριμένα τα main.cpp , Node.cpp , Trie.cpp , Node.h και Trie.h . Αρχίζοντας απ’το πιο συγκεκριμένο , ο κόμβος(Node) του κάθε δέντρου περιέχει ένα value που έχει μέσα ενα char και είναι στην προσομοίωση του trie σαν τη τιμη που έχει η από πάνω του ακμή .Επίσης έχει ένα πίνακα ‘παιδιά’ με 27 θέσεις όπου βρίσκονται τα παιδιά του . Στις θέσεις 1-26 είναι κάθε παιδί για ένα γράμμα της αγγλικής αλφαβήτου και στην θέση 27 είναι τελικός κόμβος δηλαδή σχηματίζεται λέξη εκεί και έχει το @ μέσα (δηλαδή φύλλο) . Ακόμα, έχει έναν πίνακα N θέσεων leafPointers που μέσα έχει δείκτες απευθείας στα φύλλα (με το μεγαλύτερο app_ratio(συχνότητα)). Στο Trie υπάρχει το rοot που είναι η ρίζα του δέντρου με value το ' ' και πατέρα έχει τη συνάρτηση add_node η οποία παίρνει σαν ορίσματα όλο το string απ’τη main με την fgets και το βάζει στο δέντρο. Άμα μετά κάποια λέξη υπάρχει ήδη αυξάνει το app_ratio. Κάνει χρήση των συναρτήσεων της κλάσης Νοde checkChild() που ελέγχει αν υπάρχει συγκεκριμένο παιδί ,της goToChild που επιστρέφει ένα συγκεκριμένο παιδί ,της addChild() που δημιουργεί ένα συγκεκριμένο παιδί,της setLeaf() που δημιουργεί ένα φύλλο στον τελευταίο χαρακτήρα του string ώστε να δημιουργηθεί λέξη , της increase_app_ratio() που αυξάνει το app_ratio(syxnothta) εάν ο κόμβος που εισήχθη υπήρχε ήδη στο trie και τέλος της fixLeafPointers() που αναδρομικά φτιάχνει τα leafPοinters του κάθε δέντρου . Επιπρόσθετα παίρνει σαν όρισμα έναν int που λέγεται READ_FROM και άμα είναι 0 σημαίνει ότι το string που πήρε είναι από αρχείο ενώ άμα είναι 1 το πήρε απ’τον χρήστη. Αυτό έχει σημασία γιατί πρώτη φορά που βάζει ο χρήστης μια καινούρια λέξη θέλουμε και να την βάλουμε στο δέντρο και να της κάνουμε το app_ratio 1. Στη main με την χρήση της getchar_silent() διαβάζει χαρακτήρα χαρακτήρα και έχει περιπτώσεις για το καθένα. Αν πάρει γράμμα (κεφαλαίο ή μικρό) τότε το προσθέτει στο input_buffer που είναι το string της κάθε λέξης και στο line_text που είναι το string ολόκληρης της γραμμής μέχρι να πατηθεί ENTER(\n) που μηδενίζει το line_text . Αν πατηθεί backspace σβήνει χαρακτήρες και αν πατηθεί TAB καλεί την συνάρτηση getTAB της Trie η οποία με τη σειρά της εμφανίζει μέσω της printBestMatch (η οποία καλεί την printFinal που είναι συνάρτηση της κλάσης Νοde) τις προτεινόμενες λέξεις για την συμπλήρωση της λέξης πριν το ΤΑΒ . Μετά με τη chooseWord άμα ο χρήστης πληκτρολογήσει έναν αριθμό που αντιστοιχεί στην επιλογή της λέξης που θέλει , του την επιστρέφει καλώντας αυτή με την σειρά της την getWord που είναι συνάρτηση της κλάσης Node η οποία επιστρέφει τη λέξη στην chooseWord που με την σειρά της την επιστρέφει στην main .Έτσι διαγράφουμε αυτό που είχε γραφτεί πριν το TAB και το αντικαθιστούμε με την λέξη που επέλεξε ο χρήστης. Τέλος έχει μια συνάρτηση freeTrie() που αποδεσμεύει τη μνήμη που πιάνει όλο το δέντρο.