Συγκέντρωση Περιεχομένου-Ιχνηλάτες (Crawlers)

Ένας ιχνηλάτης του ιστοχώρου (Web crawler) είναι ένα πρόγραμμα το οποίο «φυλλομετρά» το web με ένα αυτόματο και συστηματικό τρόπο. Η διαδικασία αυτή αναφέρεται και ως crawling. Άλλοι συνώνυμοι όροι που χρησιμοποιούνται στη βιβλιογραφία είναι bots, Web spiders, Web robots. Ο ιχνηλάτης αποτελεί βασικό στοιχείο των μηχανών αναζήτησης, και πολλών άλλων web εφαρμογών, καθόσον από αυτόν εξαρτάται η συγκέντρωση, επικαιροποίηση αλλά και η ποιότητα των δεδομένων. Επιπλέον οι ιχνηλάτες μπορεί να χρησιμοποιηθούν για την αυτόματη συντήρηση ενός ιστότοπου (Web site), όπως για παράδειγμα για τον έλεγχο των συνδέσμων ή για την επιβεβαίωση HTML κώδικα, καθώς επίσης μπορούν να χρησιμοποιηθούν για την συλλογή συγκεκριμένου τύπου πληροφορίας από το web, όπως για παράδειγμα την συλλογή e-mail διευθύνσεων (spamming, spambot). Ένας web crawler είναι ένα είδος πράκτορα λογισμικού (bot). Γενικά ο crawler ξεκινά από μια λίστα με URL (Uniform Resource Locator) για να επισκεφτεί τα οποία καλούνται σπόροι (seeds). Καθώς ο ιχνηλάτης επισκέπτεται αυτά τα URL, εντοπίζει όλους τους υπερσυνδέσμους (hyperlinks) σε μια σελίδα και τους προσθέτει στη λίστα των URL για να τα επισκεπτεί στη συνέχεια με μια συγκεκριμένη πολιτική. Επομένως οι ιχνηλάτης είναι ένα πρόγραμμα το οποίο διασχίζει το γράφο του web ακολουθώντας τους συνδέσμους και αυτόματα κατεβάζει τοπικά το περιεχόμενο των σελίδων του web. Η βασική δομή ενός ιχνηλάτη δίνεται στο σχήμα 2-3. Όπως βλέπουμε ο ιχνηλάτης εφοδιάζεται από μια λίστα (ουρά) από URLs. Επισκέπτεται το πρώτο URL κατεβάζει το περιεχόμενο της σελίδας και τυχόν νέους συνδέσμους που υπάρχουν στη σελίδα οι οποίοι και προστίθενται στην αρχική ουρά των URL. Η διαδικασία αυτή επαναλαμβάνεται έως ότου εξαντληθεί η λίστα των URLs. Μια περισσότερο γενική εικόνα ενός ιχνηλάτη του web παρουσιάζεται στο σχήμα 2-4.

crawler1

Σχήμα 3 Η Δομή ενός φυλλομετρητή
Όπως βλέπουμε από το σχήμα ο ιχνηλάτης αποτελείται από τέσσερα βασικά στοιχεία: τη μονάδα ανάκτησης ιστοσελίδων μέσω του πρωτοκόλλου HTTP, (downloader), τη μονάδα ανάλυσης (parsing) των ιστοσελίδων και εξαγωγή των συνδέσμων που περιέχει, (analyzer), τον χρονοπρογραμματιστή (scheduler), μονάδα διαχείρισης των URLs, και τέλος την αποθήκη που συγκεντρώνεται το περιεχόμενο των ιστοσελίδων.

crawler2

Σχήμα 4 Αρχιτεκτονική web φυλλομετρητή
Ο downloader εκτός από την ανάκτηση των ιστοσελίδων δημιουργεί και ένα ευρετήριο με τα URLs των σελίδων. Η επιλογή της σειράς με την οποία επισκέπτονται οι κόμβοι του web καθορίζεται από τη μέθοδο Dequeue του χρονοπρογραμματιστή. Συνήθως η επίσκεψη γίνεται με διάσχιση κατά πλάτος-πρώτα (Breadth First Search). Συνήθως ο ιχνηλάτης χρησιμοποιεί πολλές διαδικασίες κατεβάσματος ιστοσελίδων ταυτόχρονα οι οποίες εκτελούνται σε διαφορετικούς επεξεργαστές. Λεπτομέρειες σχετικά με ιχνηλάτες δεν δημοσιεύονται (αποτελούν μυστικά των εταιρειών) ώστε να περιορίζονται οι κακόβουλοι χρήστες (spammers). Ένας ιχνηλάτης μπορεί να είναι εξειδικευμένος (focuced) να συγκεντρώνει σελίδες που είναι σχετικές με ένα προ-καθορισμένο θεματικό πεδίο. Για παράδειγμα το CiteSeerX, μια μηχανή αναζήτησης και ηλεκτρονική βιβλιοθήκη για άρθρα στην επιστήμη των υπολογιστών χρησιμοποιεί εξειδικευμένο crawling για την συγκέντρωση των επιστημονικών άρθρων. Τέλος ένας ιχνηλάτης μπορεί να χρησιμοποιηθεί ως φίλτρο για την συγκέντρωση σελίδων κάποιου συγκεκριμένου τύπου, για παράδειγμα μόνο για HTML σελίδες. Αυτό μπορεί να γίνει όταν ο ιχνηλάτης εξετάζει το URL και μόνο όταν το URL έχει κατάληξη, για παράδειγμα, .html, .htm, να επιτρέπει να κατέβει το αρχείο. Η επίδοση ενός ιχνηλάτη αξιολογείται από τον ρυθμό ανάκτησης σελίδων από το web. Προφανώς ο ρυθμός αυτός έχει περιορισμούς, όπως για παράδειγμα, είναι το εύρος των δικτύων. Συνήθως η διαδικασία αυτή γίνεται παράλληλα από πολλούς εξυπηρετητές ώστε να μεγιστοποιηθεί ο ρυθμός της συγκέντρωσης του περιεχομένου. Η φύση και το μέγεθος του web κάνουν το έργο του ιχνηλάτη, πολύπλοκο, πολύ δύσκολο και όπως θα δούμε, και ο σχεδιασμός ενός συστήματος ιχνηλάτησης του web αποτελεί μια πρόκληση για πολλά προβλήματα.

Πολιτικές ιχνηλάτησης

Κάποια χαρακτηριστικά του web κάνουν την ιχνηλάτηση μια δύσκολη διαδικασία, όπως, για παράδειγμα:

Ο τεράστιος όγκος του web,
Η πολύ μεγάλη συχνότητα αλλαγών στο web και
Η δυναμική παραγωγή web σελίδων.

Ένα μεγάλο μέρος των ιστοσελίδων δεν είναι ορατές, αλλά ανήκουν στο λεγόμενο βαθύ ή μη-επισκέψιμο web (π.χ.βάσεις δεδομένων). Οι σελίδες αυτές είναι επισκέψιμες μόνο όταν υποβληθεί ένα ερώτημα στη βάση δεδομένων. Συβεπώς οι σελίδες αυτές δεν μπορούν να επισκεφτούν με αυτόματο τρόπο. Ο τεράστιος όγκος του ορατού web σημαίνει ότι οι ιχνηλάτες μπορούν να συγκεντρώσουν ένα μόνο μέρος του web και για το λόγο αυτό θα πρέπει να μπουν κάποιες προτεραιότητες. Η μεγάλη συχνότητα μεταβολών στο web σημαίνει ότι έως ότου ένας ιχνηλάτης κατεβάσει τη τελευταία σελίδα από ένα ιστότοπο είναι πολύ πιθανό μια νέα σελίδα να έχει προστεθεί ή κάποιες σελίδες που είχαν ενημερωθεί να διαγραφούν. Επειδή υπάρχει ένας τεράστιος αριθμός διευθύνσεων και επειδή το εύρος των δικτύων δεν είναι άπειρο, θέλουμε να έχουμε κλιμακωτούς και αποτελεσματικούς αλγόριθμους συγκέντρωσης του περιεχομένου του web. Για το λόγο αυτό είναι πολή σημαντική η σειρά με την οποία ένας ιχνηλάτης θα επισκεφτεί τις σελίδες του web. Η αποτελεσματικότητα και κατά συνέπεια και η επίδοση ενός crawler εξαρτάται από:

την πολιτική επιλογής που καθορίζει ποια σελίδα θα ανακτηθεί κάθε φορά,
την πολιτική επίσκεψης μια σελίδας που καθορίζει αν έχουν γίνει αλλαγές στη σελίδα,
Μια πολιτική καλής συμπεριφοράς ( politeness policy) για την αποφυγή συνωστισμού στους ιστότοπους
Μια πολιτική παραλληλισμού της διαδικασίας ιχνηλάτησης η οποία καθορίζει πως πρέπει να συντονιστούν οι ιχνηλάτες που θα χρησιμοποιηθούν για την συγκέντρωση του περιεχομένου του web.

Πολιτική Επιλογής Περιεχομένου

Λόγω του τεράστιου όγκου του web όλες οι μηχανές αναζήτησης συγκεντρώνουν ένα μόνο ποσοστό από τα περιεχόμενα όλου του web, περίπου το 60%. Επομένως είναι πολύ σημαντικό αυτό το ποσοστό του web που θα συγκεντρωθεί να είναι όσο το συνατό περισσότερο αντιπροσωπευτικό και όχι συγκεντρωμένο τυχαία. Αυτό σημαίνει ότι χρειάζεται ένας μηχανισμός καθορισμού της προτεραιότητας των ιστοσελίδων ανάλογα την σημαντικότητά τους. Η σημαντικότητα μιας ιστοσελίδας εξαρτάται από πολλά πράγματα, για παράδειγμα, τη δημοτικότητα των συνδέσμων που δείχνουν προς τη σελίδα. Ο σχεδιασμός μιας αποτελεσματικής πολιτικής επιλογής του περιεχομένου του web δεν είναι καθόλου απλή διαδικασία καθόσον βασίζεται σε μερική πληροφορία. Πράγματι το σύνολο των web σελίδων δεν είναι γνωστό κατά την διάρκεια της ιχνηλάτησης. Για το πρόβλημα αυτό έχουν χρησιμοποιηθεί διάφορες πολιτικές όπως για παράδειγμα, η τεχνική κατά πλάτος-πρώτα (breadth-first), το πλήθος των συνδέσμων που δείχνουν σε μια ιστοσελίδα και η τιμή του Pagerank της σελίδας που ενδεχομένως είναι γνωστή από προηγούμενη ιχνηλάτηση. Πολλές φορές δύο διαφορετικά URLs δείχνουν στο ίδιο περιεχόμενο. Οι ιχνηλάτες συνήθως κάνουν μια μορφή κανονικοποίησης στα URL για να αποφύγουν την ανάκτηση της ίδιας σελίδας πολλές φορές. Με τη κανονικοποίηση αλλάζει το URL και παίρνει μια πρότυπη και συμβατή μορφή. 1.1.3 Πολιτική Επανεπίσκεξης ιστοσελίδων To web αλλάζει από στιγμή σε στιγμή. Εκατομμύρια νέες σελίδες δημιουργούνται καθημερινά και άλλες τόσες αποσύρονται ημηρεσίως. Είναι δυνατόν όσπου να τελειώσει ένας ιχνηλάτης την συγκέντρωση του περιεχομένου ενός ιστότοπου, νέες σελίδες να έχουν εμφανιστεί και άλλες να έχουν αποσυρθεί. Προφανώς μια μηχανή αναζήτησης στο web πρέπει να εντοπίσει εγκαίρως τέτοιες μεταβολές και να διαθέτει πάντα επικαιροποιημένο περιεχόμενο. Στόχος μιας μηχανής αναζήτησης είναι κρατήσει τη «φρεσκάδα» των σελίδων όσο πιο ψηλά. Για την επανα-επίσκεψη των σελίδων έχουν δοκιμαστεί δύο πολιτικές (re-visiting policy).

Ομοιόμορφη πολιτική, όλες οι σελίδες επανα-επισκέπτονται με την ίδια συχνότητα ανεξάρτητα από το πόσο συχνά αλλάζουν,
Αναλογική πολιτική, πιο τακτικά επανα-επισκέπτονται οι σελίδες που αλλάζουν συχνά.

Από τις δύο αυτές πολιτικές στη πράξη πιο αποτελεσματική έχει αποδειχτεί η πρώτη. Και στις δύο αυτές πολιτικές δεν λαμβάνεται υπόψη πόσο σημαντική είναι μια σελίδα δηλαδή όλες οι σελίδες θεωρούνται ποιοτικά ίσες.

Πολιτική Καλής Συμπεριφοράς

Όταν ένας crawler εκτελεί πολλαπλά αιτήματα ανά δευτερόλεπτο και κατεβάζει μεγάλα αρχεία μπορεί να απασχολεί τον εξυπηρετηρή του οποίου η επίδοση μπορεί να πέσει δραματικά. Αυτό είναι ένα αρνητικό στοιχείο για πολλές εφαρμογές γιατί:

Απασχολείται το δίκτυο του οποίου το εύρος είναι πεπερασμένο
Υπερφορτώνεται ο εξυπηρετητής (overload),

Μια αραχνοπαγίδα έχει ως αποτέλεσμα ο crawler να πέσει σε ατέρμονο loop με αποτέλεσμα να καταρρεύσει. Μια μερική λύση των προβλημάτων αυτών βρίσκεται στο πρωτόκολλο εξαιρέσεων των ρομπότ (robots exclusion protocol), γνωστό ως πρωτόκολλο robots.txt το οποίο χρησιμοποιείτε από τους διαχειριστές για να επισημάνουν τα μέρη εκείνα του εξυπηρετητή τους τα οποία δεν πρέπει να πειράξει ο ιχνηλάτης. Ένας «ευγενικός» crawler εναλλάσει διαδοχικές αιτήσεις μεταξύ δύο ξενιστών (hosts) καθώς επίσης διαδοχικές αιτήσεις στον ίδιο εξυπηρετητή γίνονται εφόσον περάσουν κάποια δευτερόλεπτα. Οι εμπορικές μηχανές αναζήτησης έχουν την δυνατότητα να δηλώσουν ένα αριθμό που δηλώνει τα δευτερόλεπτα που πρέπει να περάσουν μεταξύ δύο διαδοχικών αιτημάτων στον ίδιο εξυπηρετητή. Η τεχνική αυτή λύνει το πρόβλημα που προκύπτει στη περίπτωση που ένας εξυπηρετητής δεν είναι διαθέσιμος οπότε κατά την προσπάθεια σύνδεσης δημιουργείται σφάλμα (time out). Επομένως ο ιχνηλάτης θα πρέπει να επισκέφτεται πολλές φορές τις σελίδες ενός τέτοιου εξυπηρετητή έως ότου τον βρει διαθέσιμη.

Πολιτική Παραλληλισμού

Κατανεμημένη συγκέντρωση του web σημαίνει κατανεμημένη επεξεργασία κατά την οποία χρησιμοποιούνται ταυτόχρονα πολλές μηχανές για να συγκεντρώσουν και να ευρετηριάσουν το περιεχόμενο του web. Σκοπός μας είναι η μεγιστοποίηση της συχνότητας κατεβάσματος web περιεχομένου και ταυτόχρονα η ελαχιστοποίηση του κόστους επικοινωνίας (overhead) από τον παραλληλισμό. Προφανώς θα πρέπει να αποφεύγουμε να κατεβάσουμε τις ίδιες σελίδες πολλές φορές. Για το σκοπό αυτό το σύστημα ιχνηλάτησης απαιτεί μια πολιτική για την εκχώρηση νέων URL που προκύπτουν κατά τη διάρκεια ιχνηλάτησης σε διαφορετικούς υπολογιστές, για να μη βρεθούν τα ίδια URL σε διαφορετικές διεργασίες ιχνηλάτησης. Συνήθως υπάρχουν δύο πολιτικές εκχώρησης του φόρτου στους επεξεργαστές: Πολιτική Δυναμικής Εκχώρησης. Με τη πολιτική αυτή ένας κεντρικός εξυπηρετητής εκχωρεί δυναμικά νέα URL σε διαφορετικούς crawlers. Αυτό επιτρέπει στον κεντρικό εξυπηρετητή να ισοζυγίσει το φόρτο σε κάθε ιχνηλάτη. Με τη πολιτική αυτή ωστόσο, ο κεντρικός εξυπηρετητής μπορεί να δημιουργεί πρόβλημα καθυστέρησης (bottleneck), γι’ αυτό η περισσότερη δουλειά πρέπει να μεταφερθεί στις κατανεμημένες διεργασίες ιχνηλάτησης. Πολιτική Στατικής εκχώρησης. Με αυτή τη πολιτική, υπάρχει ένας σταθερός κανόνας ο οποίος ορίζει πως θα γίνει η εκχώρηση των URL στους ιχνηλάτες.

Άλλα Προβλήματα

Αραχνοπαγίδες (Spider trap). Μια αραχνοπαγίδα είναι ένα σύνολο από ιστοσελίδες οι οποίες έχουν δημιουργηθεί είτε σκόπιμα είτε όχι με σκοπό να αναγκάσουν τον ιχνηλάτη να κάνει ένα άπειρο πλήθος αιτήσεων και έτσι στο τέλος να καταρρεύσει. Αραχνοπαγίδες μπορεί να δημιουργηθούν για να πιάσουν κακόβουλο λογισμικό (spambots) τα οποία δεσμεύουν ένα μέρος του εύρους του δικτύου. Πλαίσια (frames). Ορισμένες σελίδες αποτελούνται από υποσελίδες. Ο χρήστης βλέπει μια μοναδική σελίδα χωρισμένη σε τμήματα που το καθένα όμως αντιστοιχεί σε διαφορετικό πλαίσιο. Ο φυλλομετρητής κατεβάζοντας των HTML κώδικα της αρχικής σελίδας θα πρέπει να εντοπίσει τα URLs των διαφορετικών πλαισίων να ανακτήσει το περιεχόμενό τους και να το θεωρήσει ως περιεχόμενο της αρχικής σελίδας . Javascript και Flash. Πολλές web σελίδες χρησιμοποιούν Javascript για τη δημιουργία συνδέσμων. Ο φυλλομετρητής θα πρέπει να αφαιρεί αυτούς του συνδέσμους, κάτι το οποίο, δεν είναι προφανές σε πολλές περιπτώσεις. Επιπλέον πολλές σελίδες έχουν ενσωματωμένα αρχεία Flash που εκτός από βίντεο και ήχο περιέχουν και κείμενο και συνδέσμους.

Αναφορές

Kobayashi, M. and Takeda, K. (2000)."Information retrieval on the web".ACM Computing Surveys (ACM Press) 32 (2): 144–173.
Baeza-Yates, R., Castillo, C., Marin, M. and Rodriguez, A. (2005). Crawling a Country: Better Strategies than Breadth-First for Web Page Ordering. In Proceedings of the Industrial and Practical Experience track of the 14th conference on World Wide Web, pages 864–872, Chiba, Japan. ACM Press.
Chakrabarti, S. (2003).Mining the Web. Morgan Kaufmann Publishers.
Robert C. Miller and Krishna Bharat. SPHINX: A Framework for Creating Personal, Site Specific Web Crawlers. In Proceedings of WWW7, Brisbane Australia, April 1998

Ιχνηλάτες Ανοιχτού Κώδικα

crawler4j, Είναι γραμμένος σε Java και διατίθεται με Apache License.
Heritrix, Είναι ένας crawler των Internet Archive γραμμένος σε java.
Nutch, Είναι γραμμένος σε java και διατίθεται με Apache License. Μπορεί να χρησιμοποιηθεί με το πακέτο κατασκευής ευρετηρίων του lucene.
WebSPHINX, (Website-Specific Processors for HTML INformation eXtraction ) είναι μια βιβλιοθήκη κλάσεων της Java και ένα διαδραστικό περιβάλλον ανάπτυξης για ιχνηλάτες του ιστοχώρου.