Δεικτοδότηση Κειμένων με Β-tree (Inverted File)

[babaliaris]

Καλησπέρα!

Έφτιαξα ένα πρόγραμμα σε python το οποίο δέχεται ως είσοδο αρχεία κειμένου (.txt) και δημιουργεί μια βάση δεδομένων η οποία επιτρέπει γρήγορη αναζήτηση λέξεων και ως απάντηση σου λέει σε πια αρχεία βρίσκεται αυτήν η λέξη αλλά και σε ποιο byte (από την αρχή του αρχείου) βρίσκεται.

Θα ήθελα όσοι έχουν χρόνο, να κατεβάσουν το πρόγραμμα μου και να το τρέξουν (Κυρίως ενδιαφέρομαι για χρήστες linux), χρησιμοποιώντας τα αρχεία που έχω ήδη μέσα στο project αλλά και εισάγοντας δικά σας αρχεία κειμένου.

Το project μπορείτε να το κατεβάσετε από https://github.com/babaliaris/Inverted-File.

Πως το χρησιμοποιείται:

Χρειάζεστε python 3 για να το τρέξετε (Δοκιμασμένο σε python 3.6)

1) Βάλτε όλα τα αρχεία κειμένου (.txt) μέσα στον φάκελο "Files Input". Παρακαλώ μην βάλεται αρχεία τύπου binary όπως βίντεο, microsoft office word κτλ αλλά ΜΟΝΟ .txt αρχεία, διαφορετικά το πρόγραμμα θα κρασάρει (Κανονικά θα έπρεπε να το τσεκάρω αυτό αλλά δεν με απασχολούσε και τόσο).

2)Τρέξτε το main.py (είναι το user interface) .

3) Από το menu δώστε το '1' για να δημιουργήσετε την βάση δεδομένων. Θα σας ζητηθεί να δώσετε έναν buffer size (Προτεινόμενο μέγεθος 128) αλλά μπορείτε να βάλετε ότι θέλετε. Όσο ποιο μεγάλο το buffer size τόσο ποιο πολλά παιδιά θα έχει το btree άρα η αναζήτηση θα είναι και ποιο γρήγορη.

4) Τέλος, μόλις δημιουργηθεί το database, διαλέξετε την επιλογή 2 (navigate) πληκτρολογείστε μία λέξη και το σύστημα θα σας απαντήσει.

Παρακαλώ τσεκάρετε επίσης εάν όντως όταν κάνετε μια ερώτηση στην επιλογή navigate σας λέει σωστά σε ποιο αρχείο βρίσκεται αυτήν η λέξη αλλά και σε ποιο byte από την αρχή του κειμένου βρίσκεται. Απλώς ανοίξτε το αρχείο που σας λέει χρησιμοποιώντας python η σε κάποια άλλη γλώσσα προγραμματισμού, κάντε seek τόσα bytes όσα σας λέει και κάντε read(number_of_bytes) όσα bytes είναι η λέξη.

Ευχαριστώ και ελπίζω να σας αρέσει!!!

[WAntilles]

Αν υποθέσουμε ότι ένα κείμενο γίνεται access σε text mode (και όχι binary), και ότι εδώ και πολλά χρόνια όλα τα κείμενα είναι utf8 (που σημαίνει ότι κάθε χαρακτήρας δεν έχει σταθερό μέγεθος σε bytes), ίσως θα ήταν πιο χρήσιμο να λέει σε ποιό χαρακτήρα (ή ποιά λέξη) απαντάται η κάθε λέξη.

[babaliaris]

Αν υποθέσουμε ότι ένα κείμενο γίνεται access σε text mode (και όχι binary), και ότι εδώ και πολλά χρόνια όλα τα κείμενα είναι utf8 (που σημαίνει ότι κάθε χαρακτήρας δεν έχει σταθερό μέγεθος σε bytes), ίσως θα ήταν πιο χρήσιμο να λέει σε ποιό χαρακτήρα (ή ποιά λέξη) απαντάται η κάθε λέξη.

Δεν υπάρχει πρόβλημα. Θα δεις ότι σε λέει ακριβώς που είναι μέσα στο αρχείο.

[WAntilles]

Δεν είπα ότι κάνεις λάθος.

Είπα ότι να μου πει σε ποιό byte του αρχείου, όταν δεν υπάρχει τρόπος για utf8 κείμενο, να αντιστοιχίσω byte σε χαρακτήρες ή λέξη, αν δεν κάνω parse όλο το κείμενο από την αρχή, είναι πρακτικά άχρηστο.

[babaliaris]

Δεν είπα ότι κάνεις λάθος.

Είπα ότι να μου πει σε ποιό byte του αρχείου, όταν δεν υπάρχει τρόπος για κείμενο, να αντιστοιχίσω byte σε χαρακτήρες ή λέξη, αν δεν κάνω parse όλο το κείμενο από την αρχή, είναι πρακτικά άχρηστο.

Ούτως η άλλος άσκηση ήταν για την σχολή μου

[guardianhelm]

Ψάχνεις feedback πάνω σε κάτι συγκεκριμένο ή απλά να τσεκάρουμε ότι δουλεύει;

- - - Updated - - -

EDIT: Άστο, είμαι γκαβός, τώρα είδα ότι το γράφεις...

- - - Updated - - -

Θα το ψειρίσω όσο μπορώ!

Έστειλα το repository σε ένα rpi, αντέγραψα ό,τι txt αρχείο υπήρχε στο σύστημα μέσα στο directory "File Inputs" και μετά έσβησα όσα είχαν πάνω από 12 (8 + extension) χαρακτήρες στο όνομά τους. Πέτυχα ορισμένα θεματάκια με την παρακάτω σειρά:

1. Αυτό το exception. Από τη στιγμή που εμφανίζεται σε συγκεκριμένη λέξη, βάλε ένα πιο κατατοπιστικό exception output, πχ:

print("Word '{}' is more than 12 characters long and will not be stored in the database.\n".format(word[0]))

. Το str.format γενικά είναι πολύ χρήσιμη μέθοδος για... string formatting, να τη χρησιμοποιείς!
2. Βλέπω επίσης

UnicodeDecodeError: 'utf-8' codec can't decode byte 0x8c in position 0: invalid start byte

σε αρχείο με unicode περιεχόμενο (cp949.txt, κορεάτικα). Νομίζω ότι αυτές οι γλώσσες δεν χωράνε σε ένα byte έτσι κι αλλιώς, οπότε εντάξει, θα ήταν χοντράδα να ζητήσει ο/η καθηγητής/τρια να το κάνετε να παίζει.
3. Σε κάποια αρχεία κάνει πάρα πολλή ώρα (αν είσαι σε linux δοκίμασε μήπως έχεις κι εσύ την ίδια έκδοση του help-tr.txt), αν υπάρχει θα στο εμφανίσει πχ το find / -name "*help-tr.txt".
4. Στο help-es.txt (ισπανικό help του aptitude) και σε κάποια αρχεία ακόμα εμφανίζεται το εξής:

Spoiler:

Traceback (most recent call last):
  File "main.py", line 37, in <module>
    database.create()
  File "~/repos/inverted_file/Inverted File/Source_Files/database.py", line 81, in create
    key = self.tree.insert(word[0], pages)
  File "~/repos/inverted_file/Inverted File/Source_Files/BTree/b_tree.py", line 89, in insert
    current.read( current.children[i+1] )
IndexError: list index out of range

5. Κι άλλο ένα error, επίσης σε 4-5 αρχεία:

Spoiler:

Traceback (most recent call last):
  File "main.py", line 37, in <module>
    database.create()
  File "/home/pmelissi/repos/inverted_file/Inverted File/Source_Files/database.py", line 81, in create
    key = self.tree.insert(word[0], pages)
  File "/home/pmelissi/repos/inverted_file/Inverted File/Source_Files/BTree/b_tree.py", line 104, in insert
    current.addKey(new_word, new_page)
  File "/home/pmelissi/repos/inverted_file/Inverted File/Source_Files/BTree/b_node.py", line 336, in addKey
    self.__split__()
  File "/home/pmelissi/repos/inverted_file/Inverted File/Source_Files/BTree/b_node.py", line 251, in __split__
    new_root.addKey(  self.keys[mid].word, self.keys[mid].page )
  File "/home/pmelissi/repos/inverted_file/Inverted File/Source_Files/BTree/b_node.py", line 336, in addKey
    self.__split__()
  File "/home/pmelissi/repos/inverted_file/Inverted File/Source_Files/BTree/b_node.py", line 263, in __split__
    child.read(self.children[i])
  File "/home/pmelissi/repos/inverted_file/Inverted File/Source_Files/BTree/b_node.py", line 470, in read
    page = struct.unpack( 'i', buffer[i+12:i+16] )[0]
struct.error: unpack requires a bytes object of length 4

Εδώ φαίνεται σαν να είναι μεγαλύτερο το i + 16 από το συνολικό μέγεθος του buffer, οπότε δεν βρίσκει να πάρει 4

Μερικές γενικές παρατηρήσεις as I go, άσχετες με την εργασία αυτή καθεαυτή, αλλά σχετικές με το development:

1. Γενικά μη βάζεις κενά σε directory names. 99% δεν θα έχεις θέμα, αλλά better safe than sorry.
2. Προσωπική άποψη, αλλά μη χρησιμοποιείς μια αγγλικά μια ελληνικά στα ονόματα που δίνεις, πόσο μάλλον greeklish. Είναι λίγο άσχημο
3. Προσπάθησε να διαχωρίζεις το user interface design από το logic του προγράμματος. Αντί πχ να ασχολείσαι manually με το πώς θα κάνεις wrap τους χαρακτήρες χρησιμοποίησε μια έτοιμη βιβλιοθήκη όπως το textwrap που κάνει και πιο εύκολη την αλλαγή του line length.
4. Έχεις σε κάποια σημεία τριπλές/τετραπλές for. Σπάστες και φτιάξε συναρτήσεις. Πχ στο database.py μία συνάρτηση μόνη της για διάβασμα αρχείου (οι δύο εσωτερικές for δηλαδή). Το overengineering είναι κακό, αλλά operations που έχουν ξεκάθαρο χαρακτήρα κατά τη γνώμη μου δεν υπάρχει λόγος να προσπαθείς να τα χωρέσεις σε μία συνάρτηση.
5. Στα exceptions σε κάποια σημεία σπας το stacktrace για να κάνεις print ένα καινούριο μήνυμα λάθους. Μπορείς να το κάνεις ξανά throw μέσα στο catch (except), αν θες με νέο μήνυμα λάθους, χωρίς να κάνεις force το print στο stdout.

Γενικά αξιοπρεπής η προσπάθεια! Τι έτος είσαι αν επιτρέπεται και η εργασία είναι ατομική ή ομαδική;

- - - Updated - - -

Όσο για αυτό που ρώτησες, εγώ θα σου έλεγα να φτιάξεις μια συνάρτηση που θα καλεί το κανονικό πρόγραμμα για κάποιο input, θα συλλέγει τα αποτελέσματα και μετά για το καθένα θα επαληθεύει ότι η λέξη στη συγκεκριμένη θέση είναι το query.

Σαν queries μπορείς να έχεις το λεξικό του corpus σου, το σύνολο δηλαδή των λέξεων που περιέχονται στα αρχεία εισόδου, οπότε θα είσαι καλυμμένος 100%.

Αυτό φυσικά εφόσον έχεις αρκετό χρόνο να το κάνεις