Καλησπέρα!
Έχω μια άσκηση στην οποία πρέπει να κάνουμε μια δομή δεδομένων γνωστή ως "Inverted File".
Στα αρχεία που θα δημιουργήσω, πρέπει να είναι δομημένα σε σελίδες δίσκου(disk pages). Θεωρούμε
ότι μία σελίδα δίσκου είναι 128 bytes.
Πρέπει να κάνουμε δύο προγράμματα. Το πρώτο διαβάζει ένα αριθμό αρχείων κειμένου και δημιουργεί
2 δομές. Η πρώτη είναι ένα λεξικό το οποίο περιέχει όλες τις λέξεις από όλα τα αρχεία ΜΌΝΟ μία
φορά και επιπλέον δίπλα σε κάθε λέξει υπάρχει και ένας ακέραιος αριθμός που λέει σε ποια σελίδα
του ευρετηρίου θα βρω αυτό που αναζητάω.
Η δεύτερη δομή είναι ένα ευρετήριο το οποίο σε κάθε σελίδα δίσκου αποθηκεύεται το δεδομένο
"σε ποια αρχεία και σε ποιο σημείο του αρχείου από την αρχή βρήκα την συγκεκριμένη λέξη."
Όπως είπα, στο λεξικό υπάρχει ένας ακέραιος αριθμός που λέει σε ποια σελίδα του ευρετηρίου
υπάρχουν τα δεδομένα της συγκεκριμένης λέξης.
Ο στόχος μας είναι να δημιουργήσουμε ένα ένα ταξινομημένο αλφαβητικά λεξιλόγιο έτσι ώστε να
κάνουμε δυαδική αναζήτηση σε αυτό και να βρίσκουμε πολύ γρήγορα κάτι που θέλουμε από το
ευρετήριο.
Για περισσότερες πληροφορίες μπορείτε να διαβάσετε την εκφώνηση της άσκησης
εδώ
Μέχρι τώρα έχω καταφέρει τα εξής:
Δημιουργία της κλάσης WordReader η οποία διαβάζει λέξης από ένα αρχείο.
Δημιουργία της κλάσης DataBase η οποία έχει 2 βασικέ μεθόδους. Την createOnMemory
η οποία δημιουργεί την δομή στην μνήμη του υπολογιστή και η saveOnDisk η οποία
αποθηκεύει την δομής σε 2 αρχεία δομημένα σε σελίδες αρχείου.
Έχω καταφέρει από την saveOnDisk να αποθηκεύω το λεξικό, αλλά το πρόβλημα είναι
στο ευρετήριο.Στο ευρετήριο μπορεί μια λέξη να εμφανίζετε πάρε πολλές φορές μέσα
στα αρχεία και έτσι τα δεδομένα να ξεπερνούν πάρα πολύ τα 128 bytes που σημαίνει ότι
πρέπει να δημιουργήσω επιπλέον σελίδες για να αποθηκεύσω τα δεδομένα, και η κάθε μία
θα πρέπει να συνδέεται μεταξύ τους έτσι ώστε να ξέρω πως να πάω από την μία στην άλλη.
Η σύνδεση μεταξύ των σελιδών με μπερδεύει πάρα πολύ.
Μπορεί κάποιος να με προτείνει κάποια ιεραρχία που πρέπει να ακολουθήσω και πως θα μπορούσα
να σχεδιάσω την λύση του προβλήματος καλύτερα;
Εάν θέλετε ρίξτε και μια ματιά στους κωδικές μου.
WordReader:
import sys, os
class WordReader:
def __init__(this, filename):
try:
this.file = open(filename, "r")
except FileNotFoundError:
print("Error: File \""+filename+"\" not found.")
sys.exit(0)
this.position = 0 #The current position into the file.
this.realSize = 0 #The real size(including unwanted symbols) of the nextWord.
#Unwanted Symbols.
this.unwanted = ["\"", "\n", ";", ",","'", "(", ")", "[", "]",
":", "\t", "-", "_", "+", "-"]
#Symbols that ends a word.
this.wordEnd = [" ", ".", "!", "?"]
#Size of the file.
this.fileSize = os.path.getsize(filename)
#How many words i have read.
this.words = 0
#==========================This method returns the next word into the file==========================#
def nextWord(this):
word = ""
this.realSize = 0
while True:
add = True
char = this.file.read(1)
this.position += 1
this.realSize += 1
#Checking for loop break.
for c in this.wordEnd:
if char == c and word != "":
this.words += 1
return word
elif char == c and word == "":
return None
#Check for unwanted symbols.
for c in this.unwanted:
if char == c:
add = False
break
#Add the char to the word string.
if add:
word += char
#==========================This method returns the next word into the file==========================#
#This method seek a position into the file to start reading from there.
def seek(this, byte):
this.file.seek(byte)
this.potision = byte
#This returns true of the file is not over.
def hasNext(this):
return not this.fileSize <= this.position+1
#This method closes the file.
def close(this):
this.file.close()
DataBase:
from WordReader import WordReader
class DataBase:
def __init__(this, filenames):
this.filenames = filenames
this.pages = 0
this.dictionary = []
this.index = []
this.aditionalBuffers = []
#=======================This method creates the dictionary and the index structure in main memory=======================#
def createOnMemory(this):
pages = 0
#Looping through all given files.
print("Please wait for data base creation...\n")
for filename in this.filenames:
reader = WordReader(filename) #Opening Current File.
print("\tThe program now reads:",this.nameFromPath(filename))
#Getting all the words from the file.
while (reader.hasNext()):
#Reading the next word.
word = reader.nextWord()
#If it's a proper world.
if word != None:
#Calculating the start position of the word into the file.
pos = reader.position - reader.realSize
#Adding the very first word into the dictionary.
if len(this.dictionary) == 0:
this.dictionary.append(word+";"+str(pages)) #Adding the word and the page(pointer) in the dictionary.
this.index.append(filename+","+str(pos)+";") #Adding the index page with the filename and the position of the word.
#ELse
else:
found = False
#Checking to see if the word already exists in the dictionary.
for string in this.dictionary:
#If exists, then just update the index.
if this.substring(string) == word:
found = True
ind = int(this.substring(string, False))
dataString = this.index[ind]
dataString += filename+","+str(pos)+";"
this.index[ind] = dataString
break
#If not exist, then add the word in the dict, and create a new index page.
if not found:
pages += 1
this.dictionary.append(word+";"+str(pages))
this.index.append(filename+","+str(pos)+";")
reader.close()
print("\tDone reading!\n")
this.pages = pages
print("\nThe data base has been created successfuly!")
#=======================This method creates the dictionary and the index structure in main memory=======================#
#===================================This method saves the structures into two files=====================================#
#I currently working on it!
def saveOnDisk(this):
#Process ended!!!
print("Data base has been saved successfuly!")
#===================================This method saves the structures into two files=====================================#
#--------------------------------------------------Private Methods--------------------------------------------------#
#I havent finish this method yet. Im trying to create the index file.
def createIndex(this, string, file, page):
buffer = []
index = 0
for i in range(0, 128):
buffer.append(' ')
if len(string) <= 128 - 1:
for c in string:
buffer[index] = c
index += 1
buffer[index] = '\n'
for c in buffer:
file.write(str.encode(c))
else:
for i in range(0, 127):
buffer[index] = string[0]
string.remove(string[0])
index += 1
buffer[index] = '\n'
this.createIndex(string, string, file, page)
#This method creates the dictionray file.
def createDictionary(this):
this.dictionary.sort()
file = open("/home/babaliaris/labdesc1_1512/Program/dictionary.dat",
"wb")
#====================================Creating The Dictionary File====================================#
#Creating the buffer.
size = 0
buffer = []
for i in range(0, 128):
buffer.append(' ')
for s in this.dictionary:
s = list(s)
if len(s)+1 <= 128 - size - 1: #-1 for end of page character.
for c in s:
buffer[size] = c
size += 1
#Closing the string.
buffer[size] = '\0'
size += 1
else:
buffer[size] = '\n' # End of page.
#Write the buffer us bytes.
for c in buffer:
file.write(str.encode(c))
#Empty the buffer.
size = 0
buffer = []
for i in range(0, 128):
buffer.append(' ')
#Write the string which could not fit in the previous buffer.
for c in s:
buffer[size] = c
size += 1
#Closing the string.
buffer[size] = '\0'
size += 1
#Last page.
buffer[size] = '\n' # End of page.
#Write the buffer us bytes.
for c in buffer:
file.write(str.encode(c)) #Write the buffer us bytes.
file.close()
#====================================Creating The Dictionary File====================================#
#This method gives a substring from a string with this syntax: "word;page_number"
#if before = True then substring = "word" else substring = "page_number".
def substring(this, string, before = True):
string = list(string)
sub = ""
if before:
for char in string:
if char == ";":
return sub
sub += char
else:
start = False
for char in string:
if start:
sub += char
if char == ";":
start = True
return sub
#This method takes a path and returns the name of a file.
#For example if path = "/home/user_name/downloads/file.txt" -----> file.txt
def nameFromPath(this, path):
path = list(path)
slashes = 0
name = ""
for c in path:
if c == '/':
slashes += 1
while(slashes > 0):
if path[0] == '/':
slashes -= 1
path.remove(path[0])
for c in path:
name += c
return name
#--------------------------------------------------Private Methods--------------------------------------------------#
Main:
# -*- coding: UTF-8 -*-
#!/user/bin/python34
from DataBase import DataBase
base = DataBase(["/home/babaliaris/labdesc1_1512/MartinLutherKing.txt", "/home/babaliaris/labdesc1_1512/Kennedy.txt", "/home/babaliaris/labdesc1_1512/Obama.txt"])
base.createOnMemory()
base.saveOnDisk()
My Facebook Programming Page 
