Η ολοένα αυξανόμενη διείσδυση και χρήση του Internet παγκοσμίως έχει οδηγήσει στην επιτακτική ανάγκη ενός καλά ορισμένου και κοινά αποδεκτού τρόπου αναπαράστασης και ανταλλαγής της πληροφορίας στο διαδίκτυο. Όλο και περισσότερα ετερογενή συστήματα και πλατφόρμες χρειάζονται να ανταλλάξουν δεδομένα και πληροφορίες μεταξύ τους, με τρόπο καλά ορισμένο αλλά ταυτόχρονα δυναμικό και ελαστικό. H XML αναπτύχθηκε για να επιλύσει ακριβώς αυτό το πρόβλημα, της εινιαίας και καθολικά αποδεκτής αναπαράστασης της διακινούμενης πληροφορίας. Η ραγδαία αύξηση όμως του όγκου των δεδομένων που αναπαρίστανται σε XML δημιούργησε την ανάγκη αναζήτησης μέσα στην δενδρική δομή ενός ΧΜL εγγράφου για κάποια συγκεκριμένη πληροφορία. Η ανάγκη αυτή ταυτόχρονα με την ανάγκη για γρήγορη πρόσβαση στους κόμβους του ΧΜL δέντρου, οδήγησε σε διάφορα εξειδικευμένα ευρετήρια καθένα με διαφορετικά χαρακτηριστικά και δομή. Τα δεδομένα όμως στη σύγχρονη κοινωνία της πληροφόρησης δεν παραμένουν στατικά, αλλά διαρκώς αλλάζουν και μεταβάλλονται δυναμικά. Για να μπορέσουν να αναταποκριθούν στη δυναμική αυτή των δεδομένων, τα ευρετήρια θα πρέπει να έχουν τη δυνατότητα να μεταβάλλονται και αυτά δυναμικά και με ελάχιστο κόστος. Ταυτόχρονα με την ανάγκη αναζήτησης συγκεκριμένης πληροφορίας μέσα σε ένα σύνολο XML δεδομένων, γεννήθηκε και η ακριβώς αντίστροφη ανάγκη: το φιλτράρισμα ενός συνόλου XML δεδομένων διαμέσου κάποιων προτύπων και κανόνων ώστε να βρεθούν εκείνα τα δεδομένα που ταιριάζουν με τα αποθηκευμένα πρότυπα και κανόνες. Το πρόβλημα αυτό συναντάται κυρίως στα συστήματα publish/subscribe, στα οποία οι χρήστες ορίζουν τα ενδιαφέροντά τους και το σύστημα αναλαμβάνει να τους αποστέλλει μόνο πληροφορίες και δεδομένα σχετικά με τις προτιμήσεις τους. Η αναπαράσταση της πληροφορίας σε XML οδήγησε τα συστήματα αυτά να ενσωματώσουν αλγορίθμους φιλτραρίσματος των XML δεδομένων διαμέσου ενός συνόλου προτύπων και κανόνων που έχουν ορίσει εκ των προτέρων οι χρήστες του. Στα πλαίσια της μεταπτυχιακής αυτής εργασίας μελετάμε και συγκρίνουμε τις υπάρχουσες τεχνικές δυναμικής δεικτοδότησης και φιλτραρίσματος XML εγγράφων και παρουσιάζουμε έναν νέο, πρωτοποριακό αλγόριθμο φιλτραρίσματος που υπερτερεί των υπαρχόντων. / The increasingly use of Internet worldwide has led to the impulsory need of a standard, well-defined and wide-accepted information representation. More and more heterogeneous systems require exchanging data and information between them, in a well-defined, flexible and dynamic matter. XML was created in order to address the need of a standard and well-defined information representation. However, the boom of information capacity expressed in XML has rised a new problem: that of searching among a huge XML data for a specific information. This problem along with the need of efficient access to the nodes of an XML tree-structured document has led to the proposal of various heuristic indexes, each one with diferrent structure and features. However, because data do not remain static but change dynamically through time, the proposed indexes should have the flexibility to change dynamically accordingly to the data changes, with the minimal cost. Together with the problem of searching through a set of XML documents, a new problem has rised: that of filtering an XML document through a predefined set of patterns and rules. This problem comes from publish/subscribe systems where the users define their interests and preferences and the system undertakes to filter incoming information through the stored user profiles. The vast volume of XML-represented data and information has led those systems to incorporate XML filtering algorithms which filter the incoming XML data streams through the predefined user profiles.

Oι πληροφορίες που τροφοδοτουν τη βάση δεδομένων των Μηχανών Αναζήτησης προέρχονται από τον Παγκόσμιο Ιστό. Ένα τρέχων ζητούμενο στο πεδίο έρευνας των Μηχανών Αναζήτησης είναι η ανάπτυξη λογισμικού με σκοπό να δίνει την δυνατότητα στον χρήστη να δεικτοδοτεί προσωπικά έγγραφα έτσι ώστε παράλληλα να μπορεί να κάνει αναζητήσεις για εύρεση πληροφοριών και σε έγγραφα που προέρχονται από τον Παγκόσμιο Ιστό αλλά και σε προσωπικά του έγγραφα όλα δεικτοδοτημένα σε μία βάση. Αυτό είναι και το κύριο πρόβλημα που επιλύουμε στην παρούσα εργασία. Με την δυνατότητα αυτήν ουσιαστικά ενοποιείται η διαδικασία της αναζήτησης πληροφοριών στις δυο διαφορετικές πηγές πληροφοριών, τα έγγραφα του Παγκόσμιου Ιστού και τα προσωπικά έγγραφα του χρήστη. / -

Αρχικά θα μελετήσουμε κάποιες έννοιες σχετικές με το δίκτυο της κινητής τηλεφωνίας και θα ασχοληθούμε πιο συγκεκριμένα με τα υποσυστήματα που μεταφέρουν τα γραπτά μηνύματα κινητής τηλεφωνίας. Κύριο μέλημά μας όμως αποτελεί η ανάλυση του τρόπου αποθήκευσης των μηνυμάτων σε συσκευές κινητής τηλεφωνίας και πιο συγκεκριμένα σε συσκευές που έχουν εγκατεστημένο το λειτουργικό σύστημα Android. Θα μελετήσουμε το λειτουργικό σύστημα Android και θα δούμε ποια είναι τα σημαντικότερα πλεονεκτήματά του, ώστε ένας χρήστης να επιλέξει το συγκεκριμένο λειτουργικό σύστημα για τη συσκευή του, αλλά και γιατί αποτελεί πλέον κυρίαρχο λειτουργικό σύστημα για την ανάπτυξη μικροεφαρμογών από τους προγραμματιστές. Ως προς το λειτουργικό Android θα αναλύσουμε εκτενέστερα τον τρόπο αποθήκευσης των γραπτών μηνυμάτων και θα δούμε πως το Android δομεί το κείμενο των μηνυμάτων και τις διάφορες πληροφορίες που παρέχονται από το ίδιο το δίκτυο της κινητής τηλεφωνίας. Θα αναλύσουμε τα σύντομα γραπτά μηνύματα κινητής τηλεφωνίας, γνωστά και ως sms, που είναι η υπηρεσία σύμφωνα με την οποία οι χρήστες ανταλλάσσουν αποκλειστικά κείμενο διατυπώνοντας συναισθήματα, σκέψεις, καθώς και σημαντικές πληροφορίες. Οι πληροφορίες αυτές αποθηκεύονται στη συσκευή κάθε χρήστη και κάθε συσκευή αποτελεί το μοναδικό οικιακό αποθηκευτικό μέσο σε όλο το δίκτυο της κινητής τηλεφωνίας. Οι πληροφορίες που αποθηκεύεται στα sms, αποτελεί σύνθετο πρόβλημα ανάλυσης, καθώς απαρτίζεται από ελλιπής προτάσεις, μεικτό περιεχόμενο ελληνικών και greeklish γραμμάτων, καθώς και συντομογραφίες που ακολουθούν ένα προσωπικό τρόπο γραφής κάποιων λέξεων δίχως να ακολουθείται κάποια νόρμα σύνταξης, ορθογραφίας και συλλαβισμού στο κείμενο. Θα δούμε πως μπορούμε με κατάλληλο φιλτράρισμα της πληροφορίας των γραπτών μηνυμάτων να προσεγγίσουμε όσο το δυνατόν περισσότερο την ανθρώπινη λογική γραφής. Θα αναλύσουμε τα φιλτραρισμένα δεδομένα και θα περιγράψουμε πως μπορεί και ο ίδιος ο χρήστης να συμβάλλει σημαντικά στο φιλτράρισμα αυτό αποκλείοντας λέξεις της αρεσκείας του από τα σύνολο των δεδομένων που θα χρησιμοποιηθούν για ευρετηριοποίηση και πως αυτό επηρεάζει σημαντικά την απόδοση της αναζήτησης. Θα επικεντρωθούμε στις πιο διαδεδομένες δομές δεδομένων που χρησιμοποιούνται για ευρετηριοποίηση και θα αναλύσουμε ποια είναι η κατάλληλότερη δομή που πρέπει να χρησιμοποιηθεί στην περίπτωσή μας και πως αυτή τροποποιήθηκε για το σκοπό της μελέτης μας. Θα αναλύσουμε πως η μετατροπή αυτή αποτέλεσε σημαντική εξέλιξη στην απόδοση του ευρετηρίου μας και πως η αναζήτηση με τη χρήση του ανεστραμμένου ευρετηρίου που αναπτύξαμε απογειώνει την ταχύτητα ανάκτησης των δεδομένων των μηνυμάτων. Τέλος, παραθέτουμε την εφαρμογή που αναπτύξαμε με τη χρήση της γλώσσας προγραμματισμού Java για το λειτουργικό σύστημα Android που ενσωματώνει το ανεστραμμένο ευρετήριο που αναπτύξαμε και βοηθά στην αναζήτηση οποιασδήποτε πληροφορίας από τα γραπτά μηνύματα είτε απευθείας από τη βάση των μηνυμάτων του Android είτε χρησιμοποιώντας το ευρετήριο. / In the current thesis an inverted index was designed for Adroid sms messages which is speeding the information retrieval from the sms database.

Βασική επιδίωξη της παρούσας διατριβής είναι η διερεύνηση των δυνατοτήτων του πεδίου της επιστήμης των υπολογιστών που πραγματεύεται την αποθήκευση και την επεξεργασία πληροφορίας, μέσα στο περιβάλλον που έχουν σχηματίσει οι σύγχρονες εφαρμογές. Τα τελευταία χρόνια, η πληροφορία που είναι διαθέσιμη σε ηλεκτρονική μορφή, έχει γιγαντωθεί με αποτέλεσμα να είναι αναγκαία η ανάπτυξη νέων τεχνικών για την αποτελεσματική αποθήκευση και επεξεργασία αυτής. Δύο πολύ χαρακτηριστικές και σημαντικές εφαρμογές, στις οποίες ανακύπτουν συνεχώς νέα προβλήματα, είναι η διαχείριση Βιολογικών δεδομένων, όπως π.χ. οι ακολουθίες γονιδιωμάτων, καθώς και η διαχείριση πληροφορίας από τον παγκόσμιο ιστό, όπως π.χ. τα έγγραφα HTML, XML ή οι συντομεύσεις (urls). Στόχος είναι ανάπτυξη δομών δεικτοδότησης πάνω στην πληροφορία έτσι ώστε τα σχετικά ερωτήματα με αυτή να απαντώνται αποδοτικά και πολύ πιο γρήγορα από το να ψάχναμε εκτενώς μέσα σε αυτή. Χαρακτηριστικά τέτοια ερωτήματα είναι η εύρεση προτύπων (pattern matching) ή ο εντοπισμός επαναλαμβανόμενων μοτίβων (motif extraction). Πιο συγκεκριμένα, τα ϑέματα στα οποία εστίασε η παρούσα διατριβή είναι τα ακόλουϑα: - Εντοπισμός Περιοδικοτήτων σε συμβολοσειρές. Στην ενότητα αυτή δίνεται μια σειρά από αλγόριθμους για την εξαγωγή περιοδικοτήτων από συμβολοσειρές. Δίνονται αλγόριθμοι για την εξαγωγή μέγιστων επαναλήψεων, της περιόδου του καλύμματος και της ρίζας μιας συμβολοσειράς. Οι αλγόριθμοι αυτοί χρησιμοποιούν ώς βάση το δένδρο επιθεμάτων και οι περισσότεροι από αυτούς είναι γραμμικοί. - Δεικτοδότηση Βεβαρημένων Ακολουθιών. Στην επόμενη ενότητα η μελέτη εστιάζει στην δεικτοδότηση βεβαρημένων ακολουθιών, καθώς και στην απάντηση ερωτημάτων σε αυτές όπως η εύρεση προτύπων, η εύρεση επαναλήψεων, η εύρεση καλυμμάτων, κ.α.. Οι βεβαρημένες ακολουθίες είναι ακολουθίες όπου σε κάθε ϑέση τους έχουμε εμφάνιση όλων των συμβόλων του αλφαβήτου της ακολουθίας, έχοντας λάβει ένα συγκεκριμένο βάρος. Οι βεβαρημένες ακολουθίες αναπαριστούν βιολογικές ακολουθίες είτε νουκλεοτιδίων είτε αμινοξέων και στην ουσία περιγράφουν την πιθανότητα εμφάνισης ενός συμβόλου του αλφαβήτου σε μια συγκεκριμένη ϑέση της ακολουθίας ή κάποιες συγκεκριμένες βιολογικές ιδιότητες που διαθέτουν οι ρυθμιστικές πρωτεΐνες σε κάθε ϑέση της ακολουθίας. Για την διαχείριση αυτών των ιδιόμορφων ακολουθιών προτείνεται ως δομή δεικτοδότησης το βεβαρημένο δένδρο επιθεμάτων (Weighted Suffix Tree), ένα δένδρο με παρόμοια δομικά χαρακτηριστικά με αυτά του γενικευμένου δένδρου επιθεμάτων. Στην παρούσα εργασία δίνεται ο ορισμός του βεβαρημένου δένδρου επιθεμάτων και αλγόριθμοι κατασκευής του σε γραμμικό χρόνο και χώρο. -Εξαγωγή μοτίβων από βεβαρημένες Ακολουθίες. Με την χρήση του βεβαρημένου δένδρου επιθεμάτων υλοποιούνται ένα σύνολο αλγόριθμων εξαγωγής επαναληπτικών δομών από βεβαρημένες ακολουθίες. Πιο συγκεκριμένα, δίνονται αλγόριθμοι για την εύρεση μέγιστων ευγών,επαναλαμβανόμενων μοτίβων και κοινών μοτίβων από περισσότερες της μίας βεβαρημένες ακολουθίες. - Αλγόριθμοι Σύστασης Σελίδων Παγκόσμιου Ιστού με χρήση τεχνικών επεξεργασίας συμβολοσειρών. Αρκετές εφαρμογές παγκόσμιου ιστού (συστήματα σύστασης ή συστήματα κρυφής μνήμης) προσπαθούν να προβλέψουν τις προθέσεις ενός επισκέπτη είτε για να του προτείνουν είτε για να προφορτώσουν μία σελίδα. Για το σκοπό αυτό προσπαθούν να εκμεταλλευτούν οποιαδήποτε εμπειρία που έχει καταγραφεί στο σύστημα από προηγούμενες προσπελάσεις. Προτείνεται νέος τρόπος δεικτοδότησης και αναπαράστασης της πληροφορίας που εξάγεται από τα διαθέσιμα δεδομένα, όπως οι προσβάσεις των χρηστών από τα logfilesκαι το περιεχόμενο των σελίδων. Για την εξόρυξη γνώσης από τα παραπάνω δεδομένα, αυτά αναπαριστώνται ως συμβολοσειρές και στη συνέχεια επεξεργάζονται και δεικτοδοτούνται από ένα γενικευμένο βεβαρημένο δένδρο επιθεμάτων. Το δένδρο αυτό συμπυκνώνει αποδοτικά τα πιο συχνά αλλά και πιο ουσιαστικά μοτίβα προσπελάσεων και χρησιμοποιείται, αφότου κατασκευαστεί, σαν ένα μοντέλο για την πρόβλεψη των κινήσεων τον επισκεπτών ενός ιστοτόπου. / The basic goal of this thesis is to explore the possibilities of the field of computer science that deals with storing and processing information in the environment that formed by the modern applications. In recent years, the information that is available in electronic form, has met an enormous growth. Thus it is necessary to develop new techniques for efficient storage and processing. Two very specific and important applications in which constantly new problems arise are, the management of biological data, such as genome sequences, and the management information from the Web, such as documents HTML, XML or shortcuts (urls). The objective is the development of data structures for indexing information so that the questions are able to be answered in less time than looking explicitly in information. Such questions are to find patterns (pattern matching) or the identification of repeated motifs (motif extraction). In particular, the issues on which this thesis has focused are: - Locating Periodicities in strings. This section provides a series of algorithms for the extraction of periodicities of strings. We propose algorithms for the extraction of maximum repetitions of the cover, period and the seed of a string. The algorithms used are based on suffix tree and they are optimal. - Weighted Sequences indexing. In the next section, the study focuses on indexing of weighted sequences, and to answer questions like finding models, pairs, covers etc. in them. The weighted sequences are sequences where each position consists of all the symbols of the alphabet in sequence, having each one a specific weight. For the management of these sequences a particular indexing structure is proposed with the name Weighted Suffix Tree, a tree with structural features similar to those of the generalized suffix tree. In this work we propose the definition of the weighted suffix tree and construction algorithms in linear time and memory space. With the utilization of weighted suffix tree on a set of weighted sequences we propose algorithms for extracting repetitive structures from a set of weighted sequences. More specifically, we propose algorithms for finding maximum pairs, repeated motifs and common patterns of more than one weighted sequences -Recommendation Algorithms for web pages using strings processing algorithms. Several web applications (Recommendation systems or cache systems) want to predict the intentions of a visitor in order to propose or to preload a webpage. For this purpose systems try to exploit any experience that is recorded in the system from previous accesses. A new method for indexing and representing of information extracted is proposed upon the recorder data, from the user accesses in log files and content pages. For extracting knowledge from these data, the information is represented as strings and then treated and processed as weighted sequences. All these sequences are indexed by a generalized weighted sequence tree.

Οι μηχανές αναζήτησης είναι ένα ανεκτίμητο εργαλείο για την ανάκτηση πληροφοριών από το διαδίκτυο. Απαντώντας στα ερωτήματα του χρήστη, επιστρέφουν μια λίστα με αποτελέσματα, ταξινομημένα κατά σειρά, με βάση τη συνάφεια του περιεχομένου τους προς το ερώτημα. Ωστόσο, αν και οι μηχανές αναζήτησης είναι σίγουρα αρκετά καλές στην αναζήτηση συγκεκριμένων ερωτημάτων, όπως είναι η εύρεση μιας συγκεκριμένης ιστοσελίδας, αντίθετα μπορούν να είναι λιγότερο αποτελεσματικές όσον αφορά την αναζήτηση ασαφών, προς αυτές, ερωτημάτων, όπως για παράδειγμα όταν συναντούμε το φαινόμενο της αμφισημίας, όπου μια λέξη μπορεί να πάρει περισσότερες από μία έννοιες μέσα στα συμφραζόμενα διαφορετικής πρότασης. Άλλο ένα παράδειγμα ερωτήματος είναι όταν υπάρχουν περισσότερες από δύο υποκατηγορίες και νοήματα σ’ ένα ερώτημα, πράγμα που σημαίνει ότι ο χρήστης θα πρέπει να διατρέξει έναν μεγάλο αριθμό αποτελεσμάτων για να βρει αυτά που τον ενδιαφέρουν. Στόχος της παρούσας διπλωματικής εργασίας είναι η ανάπτυξη ενός έμπειρου συστήματος, που θα μετά-επεξεργάζεται τις απαντήσεις μας κλασικής μηχανής αναζήτησης και θα ομαδοποιεί τα αποτελέσματα σε μια ιεραρχία από κατηγορίες με βάση το περιεχόμενο τους. Οι σημαντικότερες σημερινές λύσεις πάνω στο πρόβλημα της αντιστοίχησης των αποτελεσμάτων σε συστάδες είναι τα συστήματα Vivisimo, Carrot, CREDO και SnakeT. Η συνεισφορά που προτείνεται στη παρούσα εργασία, είναι η χρήση μίας σειράς τεχνικών που βελτιώνουν την ποιότητα των ομάδων απάντησης. Μία πρωτότυπη τεχνική που χρησιμοποιήθηκε στην παρούσα εργασία είναι η αναδιατύπωση των ερωτημάτων (query reformulation) μέσω διαφόρων στρατηγικών. Ο λόγος που παρουσιάζονται τέτοιες στρατηγικές, είναι επειδή συχνά οι χρήστες τροποποιούν ένα προηγούμενο ερώτημα αναζήτησης ώστε να ανακτήσουν καλύτερα αποτελέσματα ή κι επειδή πολλές φορές δεν μπορούν να διατυπώσουν σωστά ένα ερώτημα λόγω της μη γνώσης επιθυμητών αποτελεσμάτων. Επιπλέον, επωφεληθήκαμε από τη Wikipedia αντλώντας δεδομένα από τους τίτλους των σελίδων αλλά κι από τις κατηγορίες στις οποίες ανήκουν αυτές οι σελίδες. Αυτό γίνεται μέσω της σύνδεσης των συχνών όρων που ανήκουν στα κείμενα των αποτελεσμάτων αναζήτησης με τη σημασιολογική εγκυκλοπαίδεια Wikipedia, με σκοπό την εξαγωγή των διαφορετικών εννοιών και νοημάτων του κάθε όρου. Ειδικότερα, αναζητείται στη Wikipedia η ύπαρξη σελίδας (ή σελίδων για το φαινόμενο της αμφισημίας) που αντιστοιχίζονται στους όρους αυτούς με αποτέλεσμα τη χρησιμοποίηση του τίτλου και της κατηγορίας ως επιπρόσθετη πληροφορία. Τέλος η Wikipedia χρησιμοποιείται και στην ανάθεση ετικετών στις τελικές συστάδες ως επιπρόσθετη πληροφορία κάθε ξεχωριστού κειμένου που βρίσκεται στη συστάδα. / -