Συζήτηση
Γεια χαρά, Επισκέπτης
Όνομα χρήστη: Κωδικός: Να με θυμάσαι

ΘΕΜΑ: Άσκηση σε δομές δεδομένων.

προγραμματιστη online browser games 10 Χρόνια 3 Μήνες πριν #2222

  • papagalos
  • Το Άβαταρ του/της papagalos
  • Αποσυνδεμένος
  • Ο χρήστης είναι μπλοκαρισμένος
  • Δημοσιεύσεις: 3
Θα ηθελα καποιος προγραμματιστης Online browser games με αρκετες γνωσεις πανω σε PHP 5.3 OOP MySQL HTML5, CSS3, JavaScript & JQuery για προσωπικη δουλεια(δημιουργιας ενος προγραμματος για ενα online παιχνιδακι).

θα ηθελα καποιος να επικοινωνισει στο Αυτή η διεύθυνση ηλεκτρονικού ταχυδρομείου προστατεύεται από τους αυτοματισμούς αποστολέων ανεπιθύμητων μηνυμάτων. Χρειάζεται να ενεργοποιήσετε τη JavaScript για να μπορέσετε να τη δείτε. για αμμεση συνενοηση και ολα τα σχετικα

ευχαριστω για το χρονο σας
Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Άσκηση σε δομές δεδομένων. 8 Χρόνια 1 Εβδομάδα πριν #3555

  • babaliaris1
  • Το Άβαταρ του/της babaliaris1
  • Αποσυνδεμένος
  • python
  • Δημοσιεύσεις: 445
  • Ληφθείσες Ευχαριστίες 75
Καλησπέρα!

Έχω μια άσκηση στην οποία πρέπει να κάνουμε μια δομή δεδομένων γνωστή ως "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()
 
Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.

Άσκηση σε δομές δεδομένων. 8 Χρόνια 6 Ημέρες πριν #3556

  • babaliaris1
  • Το Άβαταρ του/της babaliaris1
  • Αποσυνδεμένος
  • python
  • Δημοσιεύσεις: 445
  • Ληφθείσες Ευχαριστίες 75
Τέλος πάντων, την έλυσα την άσκηση :p

Θα την αναρτήσω να την δείτε όσοι ενδιαφέρεστε .
Πρέπει να είστε εγγεγραμμένο μέλος του Φόρουμ για να κάνετε μια δημοσίευση.
Συντονιστές: pmav99
Χρόνος δημιουργίας σελίδας: 0.420 δευτερόλεπτα

Μοιράσου το!

Powered by CoalaWeb

Λίστα Ταχυδρομείου