Back to search

University of Macedonia Economic and Social Sciences

Parallel and distributed implementations of multiple and two-dimensional pattern matching algorithms

Abstract

dc:description

Η αναζήτηση προτύπων αποτελεί ένα θεμελιώδες πρόβλημα στον κλάδο της Επιστήμης της Πληροφορικής. Σε αυτήν την διατριβή εξετάζεται το πρόβλημα της αναζήτησης πολλαπλών και διδιάστατων προτύπων. Η αναζήτηση πολλαπλών προτύπων μπορεί να οριστεί γενικά ως η εύρεση όλων των θέσεων σε ένα μονοδιάστατο αλφαριθμητικό, το επονομαζόμενο και ως κείμενο (text), στις οποίες εμφανίζονται ένα ή περισσότερα αλφαριθμητικά, τα επονομαζόμενα και ως πρότυπα (patterns), από ένα πεπερασμένο σύνολο προτύπων. Η αναζήτηση διδιάστατων προτύπων μπορεί να οριστεί γενικά ως η εύρεση όλων των θέσεων σε ένα διδιάστατο κείμενο στις οποίες εμφανίζεται ένα διδιάστατο πρότυπο. Η διατριβή αυτή γράφτηκε έχοντας τρεις διαφορετικούς στόχους. Ο πρώτος στόχος περιλαμβάνει την ταξινόμηση και μελέτη των αλγορίθμων που επιλύουν τα προβλήματα της αναζήτησης πολλαπλών και διδιάστατων προτύπων και την αξιολόγηση των επιδόσεων μερικών από τους πιο γνωστούς αλγορίθμους ανά κατηγορία για διαφορετικές παραμέτρους, συμπεριλαμβανομένου του μεγέθους του κειμένου και της αλφαβήτου καθώς και του μήκους των προτύπων. Αν και η θεωρητική μόνο μελέτη των αλγορίθμων μπορεί να είναι χρήσιμη, είναι γνωστό ότι αλγόριθμοι με εξαιρετική θεωρητική απόδοση μπορεί να έχουν, σε αρκετές περιπτώσεις, υποδεέστερες επιδόσεις από αλγόριθμους πιο απλής φύσεως, ανάλογα με τις τεχνικές υλοποίησης ή βελτιστοποίησης, την αρχιτεκτονική του συστήματος και τον τύπο των δεδομένων που χρησιμοποιούνται. Ο δεύτερος στόχος της διατριβής, είναι η βελτίωση της απόδοσης μερικών από τους πιο γνωστούς αλγορίθμους διδιάστατης αναζήτησης προτύπων, του Baker and Bird και του Baeza-Yates and Regnier. Και οι δύο αλγόριθμοι χρησιμοποιούν τον αλγόριθμο αναζήτησης πολλαπλών προτύπων Aho-Corasick ώστε να μετατρέψουν ουσιαστικά το πρόβλημα της αναζήτησης διδιάστατων προτύπων σε πρόβλημα αναζήτησης πολλαπλών προτύπων. Η διατριβή αυτή παρουσιάζει αποτελεσματικές παραλλαγές των δύο αλγορίθμων και αξιολογεί τις επιδόσεις τους για διαφορετικά είδη δεδομένων. Ο τρίτος στόχος αποτελεί την αύξηση των επιδόσεων των αλγορίθμων που επιλύουν τα προβλήματα της αναζήτησης πολλαπλών και διδιάστατων προτύπων, αλλά μέσα από μια διαφορετική προσέγγιση. Καθώς τα μεγέθη των δεδομένων που καλούνται να επεξεργαστούν οι αλγόριθμοι που παρουσιάζονται στη διατριβή αυτή αυξάνονται τα τελευταία χρόνια με σχεδόν εκθετικό ρυθμο, συχνά είναι ανέφικτη η εκτέλεση τους σειριακά από συμβατικούς υπολογιστές. Τα τελευταία χρόνια δημιουργήθηκαν διάφορα εργαλεία και API με σκοπό τη διευκόλυνση των προγραμματιστών ώστε να αξιοποιήσουν την τεράστια επεξεργαστική ισχύ μιας μονάδας επεξεργασίας γραφικών (GPU). Η χρήση μονάδων επεξεργασίας γραφικών στη θέση των επεξεργαστών για την εκτέλεση υπολογισμών γενικού σκοπού είναι γνωστή ως Εκτέλεση Υπολογισμών Γενικού Σκοπού σε Μονάδες Επεξεργασίας Γραφικών (GPGPU). Οι αλ- γόριθμοι αναζήτησης πολλαπλών και διδιάστατων προτύπων που παρουσιάζονται σε αυτή τη διατριβή υλοποιούνται παράλληλα σε διαφορετικές αρχιτεκτονικές συμπεριλαμβανομένων μονάδων επεξεργασίας γραφικών και υβριδικών συστοιχίων υπολογιστών. Επίσης, αναλύονται διαφορετικές τεχνικές υλοποίη- σης και βελτιστοποίησης και η απόδοση των υλοποιήσεων αξιολογείται για διαφορετικές παραμέτρους.

Degree

thesis:*
Grantor dc:publisher
University of Macedonia Economic and Social Sciences
Year dc:date
2013

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Kouzinopoulos, Charalampos
  • Κουζινόπουλος, Χαράλαμπος

Subjects

dc:subject × 19

Rights

dc:rights
Statement dc:rights
  • BY_NC_ND
Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/29868

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Kouzinopoulos, Charalampos; Κουζινόπουλος, Χαράλαμπος. Parallel and distributed implementations of multiple and two-dimensional pattern matching algorithms. University of Macedonia Economic and Social Sciences, 2013. http://hdl.handle.net/10442/hedi/29868