Data Structures, Algorithms and Applications - Search Engine

Μηχανή Αναζήτησης

• Μηχανή αναζήτησης λέξεων – φράσεων σε κείμενα: Επιστρέφει το αρχείο στο οποίο υπάρχει η λέξη
• Εισαγωγή αρχείων κειμένου στο πρόγραμμα και τη μηχανή αναζήτησης
• Αποθήκευση εσωτερικών δομών σε αρχείο στο δίσκο για γρήγορη επανεκκίνηση του προγράμματος
• Ανάκτηση του αρχείου που δημιουργήθηκε στο προηγούμενο βήμα
• Χρήση τελεστών: παρενθέσεις, AND, OR, NOT
• Απεικόνιση της λίστας των λέξεων ταξινομημένης
• Εισαγωγή – Αφαίρεση αρχείου κειμένου από την αναζήτηση
• Απεικόνιση στοιχείων σχετικών με την δομή δεδομένων π.χ. στατιστικών, μέγεθος δομής σε bytes κλπ, καθώς απεικόνιση στοιχείων επιδόσεων του αλγόριθμου

Περιγραφή

Στόχος του project είναι η κατασκευή μιας απλής μηχανής αναζήτησης (search engine). Η μηχανή αυτή θα λαμβάνει ως είσοδο μία λίστα από αρχεία κειμένου (ASCII Text files), θα βρίσκει τις λέξεις που περιέχουν και χρησιμοποιώντας δομές στη μνήμη του υπολογιστή, θα διατηρεί όλη την απαραίτητη πληροφορία. Στη συνέχεια, ο χρήστης θα εισάγει στην εφαρμογή μέσα από το command line της εφαρμογής μία λέξη (π.χ. δάσος) και η εφαρμογή θα τον πληροφορεί σε ποια αρχεία βρίσκεται η λέξη αυτή. Επίσης για τη διευκόλυνση της αναζήτησης θα πρέπει να υπάρχει η δυνατότητα εισαγωγής από το χρήστη λογικών εκφράσεων (τουλάχιστον με τον τελεστή ΚΑΙ), δηλ λέξη1 ΚΑΙ λέξη2 που θα επιστρέφει τα αρχεία που περιέχουν και τις δύο λέξεις. Περισσότεροι τελεστές (π.χ. OR, NOT) καθώς και η υποστήριξη παρενθέσεων είναι θεμιτοί και επιθυμητοί!

Υλοποίηση

Το project του μαθήματος έγινε μετά από μελέτη των μεθόδων εύρεσης και αποθήκευσης δεδομένων οι οποίες παρουσιάστηκαν στις διαλέξεις του μαθήματος, κυρίως ως προς την ταχύτητα της κάθε μιας. Έτσι χρησιμοποιήθηκε η μέθοδος της συνάρτησης κατακερματισμού (hash function) για την τοποθέτηση των καταχωρήσεων σε πίνακα. Σύμφωνα με αυτή, τα δεδομένα τοποθετούνται σε συγκεκριμένες θέσεις ενός μονοδιάστατου πίνακα μέσω μιας έτοιμης συνάρτησης από τη βιβλιογραφία. Η μέθοδος αυτή προτιμήθηκε από το δέντρο (Binary Search Tree) γιατί έχουμε ταχύτερη αναζήτηση. Συγκεκριμένα, με τη συνάρτηση κατακερματισμού πετυχαίνουμε εύρεση καταχώρησης σε χρόνο Ο(1) ενώ με το B.S.T. σε χρόνο Ο(h), όπου h είναι το ύψος του δέντρου. Η αντιμετώπιση των συγκρούσεων έγινε με τη χρήση απλά συνδεδεμένης λίστας. Δηλαδή κάθε φορά που αντιστοιχούσαν περισσότερες της μίας λέξης σε μία θέση του πίνακα, τότε δημιουργούνταν ένας νέος κόμβος για την τοποθέτηση της συγκρουόμενης λέξης. Για να έχουμε το μικρότερο αριθμό συγκρούσεων, προσπαθήσαμε να έχουμε διπλάσιες διαθέσιμες θέσεις στον πίνακα από τον αριθμό των στοιχείων τα οποία έχουμε προς αποθήκευση. Επιπλέον, το πρόγραμμα δεν κάνει πολλαπλές καταχωρήσεις, απλώς μετράει πόσες φορές εμφανίζεται η κάθε καταχώρηση. Μετράει ακόμα το χρόνο φόρτωσης των καταχωρήσεων από αρχεία, το χρόνο αναζήτησης της κάθε λέξης και το αρχείο στο οποίο υπάρχει η λέξη που αναζητάμε. Η συνάρτηση κατακερματισμού βρέθηκε στη βιβλιογραφία και συγκεκριμένα στο βιβλίο “Compilers: Principles,Techniques and Tools” από Aho, Sethi και Ullman. Σε γενικές γραμμές, δίνονται τέσσερις επιλογές στο χρήστη του προγράμματος: εισαγωγή καταχωρήσεων από αρχείο, διαγραφή των καταχωρήσεων ενός αρχείου, προβολή των καταχωρήσεων και αναζήτηση μιας καταχώρησης. Το πρόγραμμα παίρνει κάθε λέξη από το εκάστοτε αρχείο και την τοποθετεί σε μία θέση του πίνακα ανάλογα με το hash value. Βέβαια, αφαιρούνται οι ειδικοί χαρακτήρες που βρίσκονται σε κάθε αρχείο κειμένου.

Ως γλώσσα υλοποίησης χρησιμοποιείται η C σε λειτουργικό σύστημα winxp.