Uživatel:Ansa

Z FI WIKI
Přejít na: navigace, hledání

Zpět na XIQE

Ansa alias xansorg @ FI

Zuzana 'Lennonka' Ansorgová, UČO 98595 na ISu
Tato stránka slouží jako neformální poznámkový list k mojí bakalářské práci. Další školní práce najdete na mojí domovské školní stránce.

PV168 - Seminář Java


Bakalářka

Deadliny

Odevzdani + prihlaska k obhaj.: 5. 1. 2007
Obhajoby: 5. 2. 2007 — 9. 2. 2007
Prihlaska ke statnicim: 7. 2. 2007
Statnice: 12. 2. 2007, 9:00, D

Téma

Indexování XML s využitím prvočíselného číslovacího schématu, oficiální zadání na ISu, pro nástroj XIQE

Zápočet za 1. semestr

  • zpracování článku A Prime Number Labeling Scheme for Dynamic Ordered XML Trees
  • článek zde (přístup pouze z domény muni.cz neb přes proxy)
  • text zápočtové práce v PDF

Otazníky

souvislost mezi NodeId a hodnotou uzlu - hodnota uzlu se uchovává ve speciální struktuře

Poznámky z konzultací

Konzultace 18. 4.

  • synchronizace - kde se musí buď
    • synchronizovat nebo
    • nesynchronizovat, ale upozornit v dokumentaci, že není synch. a kde se má synch.
  • testy

Konzultace 3. 4.

  • implementovat prvně bez optimalizací
  • napsat autorům článku, že to mají blbě

Konzultace 9. 3.
API zdola

  • balíky org.xiqe.storage.*:
    • .io (StorageManager{.getBlockCollection!!!}, BlockCollection)
    • .collections (BlockCollectionList, HashTable atd.)
    • .converters -- konvertory ("(de)serializace" objektů)

API shora

  • balík org.xiqe.structures -- impl.:
    • NodeId (parent-label x self-label)
    • DocumentStructureIndex (1) - operace nad indexy dokumentů

Moje poznámky

Průběžně vznikající text práce
bac_thesis.pdf

Nápady k implementaci
storage

  • HashTable -- dvojice <index, uzel>
    • ta ale není nejvhodnější, lépe se hodí BPlusTreeMap

structures

  • NodeId -- equals, hashCode

Simultánní kongruence
aneb Čínská věta o zbytcích a potíže s ní

  • VZOREC

Mám tu takovej a nejde mi podle něho vypočítat to správný číslo...
Vzorec.jpg
Používá se v něm Eulerova totientní funkce fí a možná to není ta správná funkce. Přestože podle všech zdrojů by měla dát výsledek, zaboha mi to nevychází.
Mnohem líp (a hlavně vůbec) to funguje s mezivýsledkem Tk. Zatím si tím nejsem úplně jistá, ale obávám se, že pokud budu chtít aplikovat optimalizaci s indexováním listových uzlů mocninami 2, tak na listové uzly nepůjde Čínská věta o zbytcích použít. Je to proto, že Čínská věta o zbytcích předpokládá, že první ze vstupních posloupností (self-labels) bude mít po párech nesoudělné prvky, což v případě mocnin dvojek nelze splnit. SC by fungovala jenom pro nelistové uzly. Pak je tu otázka, jak tedy zachovat informaci o pořadí listových uzlů?

Textové vs listové uzly

Tak tohle jsem předtím zjevně nepochopila. V tomto projektu se bere listový uzel typu text jako jeden uzel. Tímpádem je jeho pořadí jasné. No ale jak je to s textovými uzly ve standardech??? Co když tam budu mít dva newliny v textovým uzlu? Že by se o takové detaily XIQE nepotřebovalo starat?

Takže teď znovu číslování listových uzlů typu element a pomalu

  • bez optimalizací - normálně
  • s optimalizací "mocniny dvojky" - nelze se zachováním informace o globálním pořadí

Dopracovat

...možná...

  • dovysvětlit kořenový uzel (document root) = virtuální kořenové "nic"
  • kapitola 2.3 by mohla být podrobněji strukturovaná - 2.3.1 DOM a pak 2.3.1.x jeho deriváty
  • podobně u 2.4
  • "součinová label" - remember ZOS!
  • překlad totientní funkce
  • zkontrolovat důkaz

Prototypy

Simultánní kongruence (Python)

#!python

import sys

def tk(k):
	tk = pow(pi/k, k-2) % k
	print "Tk("+str(k)+") = "+str(tk)
	return tk

inp = sys.stdin
out = sys.stdout
labels = []
order = []
ls = []
od = []
pi = 1

out.write("labels> ")
labels = inp.readline().split(" ")
out.write(" ".join(labels))
out.write("order["+str(len(labels))+"]> ")
order = inp.readline().split(" ")
out.write(" ".join(order))
print
for num,x in zip(labels,order):
	ls.append(int(num))
	od.append(int(x))
	pi *= int(num)
print "Input reading finished."
print "C = "+str(pi)
suma = 0
for num,x in zip(ls,od):
	tot = func(num)
	suma += (pi/num) * x * tot
print "Suma before modulo: "+str(suma)
sc = suma % pi
print "Simultaneous congruence is "+str(sc)
print "SC shall be between 0 and "+str(pi)+"\n"

# kontrolni vypis kongruentnich hodnot
for num in ls:
	print "SC mod "+str(num)+" = "+str(sc % num)

Další odkazy