Python - Indeks pojmova


U ovoj lekciji ćemo odraditi primjere programa, koji objedinjavaju materijal nekoliko prethodnih tema, kreiraćemo program za kreiranje indeksa pojmova u zadanom tekstu (glossary) i program za poređenje performansi struktura liste i skupa.



Program Indeks pojmova

Indeks pojmova gradi sortiranu listu svih riječi u zadanom tekstu, koji se učitava iz tekstualnog fajla, zajedno s pozicijama njihovog pojavljivanja:

  • Program prvo učitava naziv tekstualnog fajla u kome se nalazi tekst koji treba analizirati.
  • Pomoću rekurzivne procedure, program redom čita linije fajla i gradi binarno stablo, u koje se smiještaju učitane reči. Nove reči dodaju se zavisno od njihog alfabetskog poretka u odnosu na riječ u tekućem čvoru binarnog stabla: u lijevo podstablo, ako je nova reč ispred, ili u desno podstablo, ako je nova riječ iza riječi u tekućem čvoru. Npr. čitanjem teksta "kad je bio mrak", dobija se binarno stablo kao što je prikazano na slici. Obilazak stabla prema unutrašnjem uređenju (inorder) daje sortirani niz riječi "bio je kad mrak". Kad se prilikom učitavanja teksta kreira čvor za novu riječ ili se posmatrana riječ pronađe u stablu, u tom čvoru stabla se ažurira lista brojeva linija dodavanjem rednog broja tekuće linije teksta.


  • Nakon izgradnje stabla, program prikazuje ukupan broj učitanih linija i procedurom obilaska stabla u unutrašnjem poretku, alfabetski sortiranu listu svih reči, zajedno s listom brojeva linija teksta u kojima se svaka od prikazanih riječi pojavljuje.

Program za kreiranje liste pojmova u jeziku Python, gde se pojavljivanja pojmova prikazuju po linijama teksta, zasniva se na predstavljanju binarnog stabla pomoću ugnježdenih lista sledeće strukture:

[<reč>, <lista_levo_podstablo>, <lista_desno_podstablo>]

Program je realizovan tako da se tekst fajla čita funkcijom binaryTree, jedna po jedna linija teksta. Učitani string jedne linije teksta dijeli se na riječi ugrađenom funkcijom split(). Nakon uklanjanja specijalnih znakova i znakova interpunkcije ugrađenom funkcijom strip, riječ w se dodaje u binarno stablo na odgovarajuće mesto funkcijom treeInsert, uz dodavanje broja linije n u kojoj se riječ pojavila.

Obilazak stabla u unutrašnjem poretku vrši se rekurzivnom funkcijom inorderTraversal, koja vrši ispis sortirane tabele riječi analiziranog teksta sa spiskom linija u kojima se svaka od riječi pojavljuje. Program se može izmjeniti, tako da kao indikator položaja riječi ne koristi redosljed linija teksta, već neki drugi podatak, npr. redosljed grupa linija koje predstavljaju jednu stranicu teksta. Kompletan kod programa za izradu indeksa pojmova, odnosno sortirane liste svih riječi u zadanom tekstu je:

"""Kreiranje liste pojmova u tekstualnom fajlu

    Gradi se i prikazuje lista reči od kojih se sastoji
    tekst u zadanom fajlu. Za svaku reč prikazuju se
    brojevi svih linija teksta u kojima se reč pominje.
"""
import sys

num = 0 # globalni brojač linija
word_count = 0 # globalni brojač reči

def treeInsert(s, w, n):
    if s == []: # inicijalizacija stabla (prvi put)
        s.append([]) # za levu granu
        s.append([])
        s.append([])
        s[0] = (w, [n])
    else:
        while True:
            if w == s[0][0]: # reč već postoji u stablu
                if not n in s[0][1]:s[0][1].insert(len(s[0][1]), n)
                return
            elif w < s[0][0]: # spada u levo podstablo
                if s[1] == []: # reč ne postoji, insert
                    s[1] = [(w, [n]), [], []]
                else:
                    s = s[1] # na levi
            elif w > s[0][0]: # spada u desno podstablo
                if s[2] == []: # reč ne postoji, insert
                    s[2] = [(w, [n]), [], []]
                else:
                    s = s[2] # u desno podstablo

def inorderTraversal(s):
    global word_count
    if (s[1] != []):
        inorderTraversal(s[1])
    word_count += 1
    sys.stdout.write(("%4i" % word_count)+" "+s[0][0])
    for i in range(0, 17 - len(s[0][0])):
        sys.stdout.write(' ')
    for i in s[0][1]:
        sys.stdout.write(str(i) + " ")
    sys.stdout.write('\n')
    if (s[2] != []):
        inorderTraversal(s[2])

def binaryTree(filename):
    global num
    f = open(filename,'r', encoding='utf-8')# pristup fajlu
    r = []
    for line in f:
        num += 1
        wp = line.split()
        for w in wp:
            w = w.strip(".,;?!-\n").lower()
            if len(w) > 0:
                treeInsert(r, w, num)
        return r
tekst = input("Unesite ime fajla s tekstom: ")
stablo = binaryTree(tekst)

print("Broj linija teksta fajl'{}'={:d}".format(tekst,num))
print("Indeks pojmova:")
print(" Reč Linije")
inorderTraversal(stablo)

U testnom primjeru se analizira tekst poznate dječije pjesme Dušana Radovića. Kreirajte novi teksualni fajl i unesite sljedeći tekst u njega i nazovite vaš faj 'Dusko.txt':

Kad je bio mrak,
kad je bio mrak,
pojurila mačka miša
čak, čak, čak.
Pojurila mačka miša
čak, čak, čak,
a da l’ ga je progutala,
to ni ona nije znala
- jer je bio mrak,
jer je bio mrak…

Rezultat izvršavanja programa, nakon analize sadržaja fajla 'Dusko.txt', je:

Unesite ime fajla s tekstom: dusko.txt
Broj linija teksta fajl'dusko.txt'=1
Indeks pojmova:
 Reč Linije
   1 bio              1
   2 je               1
   3 kad              1 
   4 mrak             1

U spisku riječi se ne pojavljuje skup znakova interpunkcije koji su, prema zadanom spisku, uklonjeni funkcijom strip(). Ovaj skup znakova se po potrebi može ažurirati u kodu programa.



Poređenje performansi struktura liste i skupa

Poređenje performansi struktura liste i skupa može se izvršiti mjerenjem vremena pronalaženja elementa i vremena uklanjanja elementa u strukturama liste i skupa. Radi precizniheg poređenja, svaka od osnovnih operacija pronalaženja i uklanjanja elementa u skupu i listi ponavlja se po 10.000 puta. Program mjeri i prikazuje ukupno vrijeme trajanja svih operacija. Vrijeme se mjeri pomoću metoda time() iz modula time, koji vraća sistemsko vreme time.time(). Datum i vrijeme se interno računaju u odnosu na neki početni datum, koji zavisi od operativnog sistema. Proteklo vreme t je razlika vremena završetka t2 i vremena početka t1 neke operacije t = t2-t1. Kompletan program za poređenje performansi struktura liste i skupa se može napisati kao:

""" Program prikazuje vrijeme izvršavanja nekih operacija
    nad strukturama liste i skupa.
    Testira se:
    (1) vrijeme pronalaženja elementa i
    (2) vrijeme uklanjanja elementa iz struktura liste i skupa.
"""
import random
import time

BROJ_ELEMENATA = 10000

# Kreiranje liste zadane dužine
lista = list(range(BROJ_ELEMENATA))
random.shuffle(lista)

# Kreiranje strukture skupa na osnovu liste
skup = set(lista)

# Pronalaženje elemenata u skupu
vrijemePocetka = time.time() # Vrijeme početka
for i in range(BROJ_ELEMENATA):i in skup
vrijemeZavrsetka = time.time() # Vrijeme završetka
vrijemeTrajanja = int((vrijemeZavrsetka - vrijemePocetka)*1000)
print("Pronalaženje", BROJ_ELEMENATA,"elemenata u skupu traje", vrijemeTrajanja, "ms")

# Pronalaženje elemenata u listi
vrijemePocetka = time.time() # Vrijeme početka
for i in range(BROJ_ELEMENATA):i in lista
vrijemeZavrsetka = time.time() # Vrijeme završetka
vrijemeTrajanja = int((vrijemeZavrsetka - vrijemePocetka)*1000)
print("\nPronalaženje", BROJ_ELEMENATA,"elemenata u listi traje", vrijemeTrajanja, "ms")

# Uklanjanje pojedinačnih elemenata iz skupa
vrijemePocetka = time.time() # Vrijeme početka
for i in range(BROJ_ELEMENATA):skup.remove(i)
vrijemeZavrsetka = time.time() # Vrijeme završetka
vrijemeTrajanja = int((vrijemeZavrsetka - vrijemePocetka)*1000)
print("\nUklanjanje", BROJ_ELEMENATA,"elemenata iz skupa traje", vrijemeTrajanja, "ms")

# Uklanjanje pojedinačnih elemenata iz liste
vrijemePocetka = time.time() # Vrijeme početka
for i in range(BROJ_ELEMENATA):lista.remove(i)
vrijemeZavrsetka = time.time() # Vrijeme završetka
vrijemeTrajanja = int((vrijemeZavrsetka - vrijemePocetka)*1000)
print("\nUklanjanje", BROJ_ELEMENATA,"elemenata iz liste traje", vrijemeTrajanja, "ms")

Rezultat izvršavanja programa, za zadanih 10.000 operacija, je:

Pronalaženje 10000 elemenata u skupu traje 1 ms

Pronalaženje 10000 elemenata u listi traje 1297 ms

Uklanjanje 10000 elemenata iz skupa traje 2 ms

Uklanjanje 10000 elemenata iz liste traje 554 ms

Vidi se da je vrijeme pristupa i vrijeme uklanjanja elemenata iz strukture skupa neuporedivo kraće. Za pronalaženje ili uklanjanje 105 elemenata strukture skup potrebno je manje od 1 milisekunde, dok je za isti broj elemenata strukture liste neophodno nekoliko sekundi.