X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=XMLTree.cpp;h=8dcdaec6904f8e017e064e912fa129ced60a8b57;hb=c1865639eb1a804ff9363035a2a656b64fd98b9e;hp=bb861a9765e31a34e4114013c26abbeb093b987f;hpb=0f2d33d4ee4291d61750769c2918263c7e485ffa;p=SXSI%2FXMLTree.git diff --git a/XMLTree.cpp b/XMLTree.cpp index bb861a9..8dcdaec 100644 --- a/XMLTree.cpp +++ b/XMLTree.cpp @@ -67,6 +67,16 @@ inline void * umalloc(size_t size){ return dest; } +void XMLTree::print_stats() { + uint total_space = Tags->size()+sizeof(static_sequence*); + total_space += sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)); + cout << "Space usage for XMLTree:" << endl + << " - tags static_sequence: " << Tags->size()+sizeof(static_sequence*) << endl + << " - tags access array: " << sizeof(uint*)+sizeof(uint)*(2+uint_len(tags_blen,tags_len)) << endl + << " ... add Diego structures ... " << endl + << " *total* " << total_space << endl; +} + // Save: saves XML tree data structure to file. void XMLTree::Save(unsigned char *filename) { @@ -101,11 +111,21 @@ void XMLTree::Save(unsigned char *filename) // stores the tags Tags->save(fp); + ufwrite(&tags_blen,sizeof(uint),1,fp); + ufwrite(&tags_len,sizeof(uint),1,fp); + ufwrite(tags_fix,sizeof(uint),uint_len(tags_blen,tags_len),fp); // stores the texts - if (!disable_tc) + if (!disable_tc) { Text->Save(fp); - + int st = CachedText.size(); + ufwrite(&st, sizeof(int),1,fp); + for (int i = 0; i< CachedText.size(); i++){ + st = CachedText.at(i).size(); + ufwrite(&st, sizeof(int),1,fp); + ufwrite(CachedText.at(i).c_str(),sizeof(char),1+CachedText.at(i).size(),fp); + }; + }; fclose(fp); } @@ -184,6 +204,11 @@ XMLTree *XMLTree::Load(unsigned char *filename, int sample_rate_text) // loads the tags XML_Tree->Tags = static_sequence::load(fp); + ufread(&XML_Tree->tags_blen,sizeof(uint),1,fp); + ufread(&XML_Tree->tags_len,sizeof(uint),1,fp); + XML_Tree->tags_fix = new uint[uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)]; + ufread(XML_Tree->tags_fix,sizeof(uint),uint_len(XML_Tree->tags_blen,XML_Tree->tags_len),fp); + s_tree+=2*sizeof(uint)+sizeof(uint)*uint_len(XML_Tree->tags_blen,XML_Tree->tags_len); s_tree+= XML_Tree->Tags->size(); s_text = ftell(fp); @@ -192,20 +217,37 @@ XMLTree *XMLTree::Load(unsigned char *filename, int sample_rate_text) if (!XML_Tree->disable_tc){ XML_Tree->Text = TextCollection::InitTextCollection(sample_rate_text); XML_Tree->Text->Load(fp,sample_rate_text); + int sst; + int st; + ufread(&sst, sizeof(int),1,fp); + for (int i=0;iCachedText.push_back(cppstr); + free(str); + }; + } - else + else { XML_Tree->Text = NULL; - + } s_text = ftell(fp) - s_text; + + + + fclose(fp); - std::cerr << "Tree part is " << s_tree/1024 << " Kbytes,\n" - << "with node->tagid part " << XML_Tree->Tags->size()/1024 << "Kbytes \n" + /*std::cerr << "Tree part is " << s_tree/1024 << " Kbytes,\n" + << "with node->tagid part " << XML_Tree->Tags->size()/1024+(uint_len(XML_Tree->tags_blen,XML_Tree->tags_len)*sizeof(uint))/1024 << "Kbytes \n" << "size of Tag part : " << XML_Tree->Tags->length () << " elements\n" << "sizof(unsigned int)* " << XML_Tree->Tags->length () << " = " << sizeof(unsigned int) * XML_Tree->Tags->length () / 1024 << " Kbytes\n" << "Tag part is " << s_tags/1024 << " Kbytes,\n" - << "Text collection is " << s_text/1024 << " Kbytes \n"; + << "Text collection is " << s_text/1024 << " Kbytes \n";*/ + XML_Tree->print_stats(); return XML_Tree; } @@ -268,6 +310,9 @@ int XMLTree::SubtreeTags(treeNode x, TagType tag) fprintf(stderr, "Error: data structure has not been constructed properly\n"); exit(1); } + if (x == Root()) + x = first_child(Par,x); + int s = x + 2*subtree_size(Par, x) - 1; @@ -368,8 +413,8 @@ TagType XMLTree::Tag(treeNode x) fprintf(stderr, "Error: data structure has not been constructed properly\n"); exit(1); } - - return Tags->access(node2tagpos(x)); + + return get_field(tags_fix,tags_blen,node2tagpos(x)); //Tags->access(node2tagpos(x)); } // DocIds(x): returns the range of text identifiers that descend from node x. @@ -382,6 +427,14 @@ range XMLTree::DocIds(treeNode x) } range r; + if (x == NULLT) + { + r.min = NULLT; + r.max = NULLT; + return r; + }; + + if (indexing_empty_texts) { // faster, no rank needed r.min = x; r.max = x+2*subtree_size(Par, x)-2; @@ -444,9 +497,9 @@ treeNode XMLTree::NextSibling(treeNode x) fprintf(stderr, "Error: data structure has not been constructed properly\n"); exit(1); } - if (x == Root()) + if (x == Root() || x==NULLT) return NULLT; - + return next_sibling(Par, x); } @@ -476,7 +529,7 @@ treeNode XMLTree::TaggedChild(treeNode x, int i, TagType tag) child = first_child(Par, x); // starts at first child of node x if (child==(treeNode)-1) return NULLT; // node x is a leaf, there is no such child while (child!=(treeNode)-1) { - if (Tags->access(node2tagpos(child)) == tag) { // current child is labeled with tag of interest + if (get_field(tags_fix,tags_blen,node2tagpos(child)) /*Tags->access(node2tagpos(child))*/ == tag) { // current child is labeled with tag of interest i--; if (i==0) return child; // we have seen i children of x tagged tag, this is the one we are looking for } @@ -496,6 +549,9 @@ treeNode XMLTree::TaggedDesc(treeNode x, TagType tag) int r, s; treeNode y; + if (isleaf(Par,x)) + return NULLT; + r = (int) Tags->rank(tag, node2tagpos(x)); s = (int) Tags->select(tag, r+1); if (s == -1) return NULLT; // there is no such node @@ -504,6 +560,154 @@ treeNode XMLTree::TaggedDesc(treeNode x, TagType tag) else return y; } +treeNode XMLTree::TaggedDescOnly(treeNode x,TagType *desctags, unsigned int dtlen) +{ + + treeNode res,y; + if (isleaf(Par,x)) + return NULLT; + + res=NULLT; + for (unsigned int i = 0; i < dtlen; i ++ ) + { + y = TaggedDesc(x,desctags[i]); + res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res; + + }; + + return res; + +} + + +treeNode XMLTree::TaggedBelow(treeNode x, TagType *childtags, unsigned int ctlen, + TagType *desctags, unsigned int dtlen) +{ + treeNode fs,y,res; + TagType tag; + + if (isleaf(Par,x)) + return NULLT; + + res = NULLT; + fs = first_child(Par,x); + while (fs != NULLT) { + tag = get_field(tags_fix,tags_blen,node2tagpos(fs)); + + /* Check for first_child */ + for (unsigned int i = 0; i < ctlen; i++) { + if (childtags[i] == tag) + return fs; + }; + + for (unsigned int i = 0; i < dtlen; i++) + if (desctags[i] == tag) + return fs; + + /* check in the descendants */ + res = NULLT; + for (unsigned int i = 0; i < dtlen; i ++ ){ + /* maybe inline by hand */ + y = TaggedDesc(fs,desctags[i]); + res = (res==NULLT || (y != NULLT) &&(y < res)) ? y : res; + }; + if (res != NULLT) + return res; + + fs = next_sibling(Par,fs); + }; + return res; + +} +treeNode XMLTree::TaggedFollOnly(treeNode x,TagType *folltags, unsigned int ftlen,treeNode root) +{ + + treeNode res,y,lim; + lim = find_close(Par,root); + res=NULLT; + for (unsigned int i = 0; i < ftlen; i ++ ) + { + y = TaggedFoll(x,folltags[i]); + res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res; + + }; + + return res < lim ? res : NULLT; + +} + +treeNode XMLTree::TaggedDescOrFollOnly(treeNode x,TagType *folltags, unsigned int ftlen,treeNode root) +{ + + treeNode res,y,lim; + int r,s; + lim = find_close(Par,root); + res=NULLT; + for (unsigned int i = 0; i < ftlen; i ++ ) + { + + r = (int) Tags->rank(folltags[i], node2tagpos(x)); + s = (int) Tags->select(folltags[i], r+1); + if (s == -1) + y = NULLT; // there is no such node + else { + y = tagpos2node(s); + if (y >= lim) + y = NULLT; + }; + res = (res == NULLT) || (( res != NULLT) && (y =! NULLT) && y < res) ? y : res; + + }; + + return res < lim ? res : NULLT; + +} + + +// TaggedNext(x,tag): returns the first node tagged tag with larger preorder than x +// Returns NULLT if there is none. +treeNode XMLTree::TaggedNext(treeNode x, TagType *childtags, unsigned int ctlen, + TagType *folltags, unsigned int flen,treeNode root) + { + treeNode y,old_y,lim,res; + TagType tag; + if (x == NULLT || x == Root()) + return NULLT; + + + lim = find_close(Par,root); + + res = NULLT; + + y = next_sibling(Par,x); + while (y != NULLT) { + tag = get_field(tags_fix,tags_blen,node2tagpos(y)); + for(unsigned int i = 0; i < ctlen;i++) + if (childtags[i] == tag) + return y; + + for(unsigned int i = 0; i < flen;i++) + if (folltags[i] == tag) + return y; + + res = TaggedBelow(y,NULL,0,folltags,flen); + if (res != NULLT) + return res; + + y = next_sibling(Par,y); + }; + //Found nothing in the following sibling of x. + res = NULLT; + for(unsigned int i = 0; i < flen;i++){ + y = TaggedFoll(x,folltags[i]); + res = (y!= x && (res == NULLT || (y != NULLT && y < res)))? y : res; + }; + + return res < lim ? res : NULLT; + + } + + // TaggedPrec(x,tag): returns the first node tagged tag with smaller preorder than x and not an // ancestor of x. Returns NULLT if there is none. treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) @@ -529,9 +733,10 @@ treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) return NULLT; // there is no such node } + // TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in // the subtree of x. Returns NULLT if there is none. -treeNode XMLTree::TaggedFoll(treeNode x, TagType tag) +treeNode XMLTree::TaggedFoll(treeNode x, TagType tag) { if (!finished) { fprintf(stderr, "Error: data structure has not been constructed properly\n"); @@ -539,15 +744,77 @@ treeNode XMLTree::TaggedFoll(treeNode x, TagType tag) } int r, s; - if (x == Root() || (next_sibling(Par,x) == -1 )) + if (x ==NULLT || x == Root()) + return NULLT; + + r = (int) Tags->rank(tag, find_close(Par, x)); + s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag. + if (s==-1) return NULLT; + else return tagpos2node(s); + } + +// TaggedFoll(x,tag): returns the first node tagged tag with larger preorder than x and not in +// the subtree of x. Returns NULLT if there is none. +treeNode XMLTree::TaggedFollBelow(treeNode x, TagType tag, treeNode root) + { + + int r, s; + int lim = node2tagpos(find_close(Par,root)); + if (x ==NULLT || x == Root()) + return NULLT; + + r = (int) Tags->rank(tag,find_close(Par,x)); + s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag. + if (s==-1 || s >= lim) return NULLT; - - r = (int) Tags->rank(tag, node2tagpos(next_sibling(Par, x))-1); + else + return tagpos2node(s); + } + + +// TaggedFollowingSibling(x,tag): returns the first node tagged tag with larger preorder than x and not in +// the subtree of x. Returns NULLT if there is none. +treeNode XMLTree::TaggedFollowingSibling(treeNode x, TagType tag) + { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + + int r, s; + treeNode ns = next_sibling(Par,x); + + if (x == NULLT || x == Root() || ns == -1) + return NULLT; + + r = (int) Tags->rank(tag, node2tagpos(ns)-1); s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag. if (s==-1) return NULLT; else return tagpos2node(s); } + +// TaggedAncestor(x, tag): returns the closest ancestor of x tagged tag. Return +// NULLT is there is none. +treeNode XMLTree::TaggedAncestor(treeNode x, TagType tag) + { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + + if (x == NULLT || x == Root()) + return NULLT; + + treeNode s = parent(Par, x), r = Root(); + while (s != r) { + if (get_field(tags_fix,tags_blen,node2tagpos(s)) /*Tags->access(node2tagpos(s))*/ == tag) return s; + s = parent(Par, s); + } + return NULLT; + } + + // PrevText(x): returns the document identifier of the text to the left // of node x, or NULLT if x is the root node or the text is empty. // Assumes Doc ids start from 0. @@ -671,6 +938,29 @@ treeNode XMLTree::ParentNode(DocID d) return (treeNode)s; } +treeNode XMLTree::PrevNode(DocID d) + { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + + if (d == NULLT) + return NULLT; + + int s; + + if (indexing_empty_texts) s = d; + else s = EBVector->select1(d+1); + if (s == -1) + return NULLT; + + if (inspect(Par,s) == CP) // is a closing parenthesis + return find_open(Par, s); + else // is an opening parenthesis + return NULLT; + + } // OpenDocument(empty_texts): it starts the construction of the data structure for @@ -683,7 +973,7 @@ int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text,bool dtc) found_attributes = false; npar = 0; parArraySize = 1; - ntagnames = 2; + ntagnames = 4; disable_tc = dtc; indexing_empty_texts = empty_texts; @@ -692,7 +982,7 @@ int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text,bool dtc) tags_aux = (TagType *) umalloc(sizeof(TagType)); - TagName = (unsigned char **) umalloc(2*sizeof(unsigned char*)); + TagName = (unsigned char **) umalloc(4*sizeof(unsigned char*)); TagName[0] = (unsigned char *) umalloc(4*sizeof(unsigned char)); @@ -701,6 +991,15 @@ int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text,bool dtc) TagName[1] = (unsigned char *) umalloc(4*sizeof(unsigned char)); strcpy((char *) TagName[1], "<$>"); + + //OJO need to put these in the table too. + TagName[2] = (unsigned char *) umalloc(5*sizeof(unsigned char)); + + strcpy((char *) TagName[2], "/<@>"); + + TagName[3] = (unsigned char *) umalloc(5*sizeof(unsigned char)); + + strcpy((char *) TagName[3], "/<$>"); if (!indexing_empty_texts) @@ -731,20 +1030,35 @@ int XMLTree::CloseDocument() Par = (bp *)umalloc(sizeof(bp)); bp_construct(Par, npar, par_aux, OPT_DEGREE|0); // creates structure for tags - static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(20); - static_permutation_builder * pmb = new static_permutation_builder_mrrr(PERM_SAMPLE, bmb); - static_sequence_builder * ssb = new static_sequence_builder_gmr_chunk(bmb, pmb); + //static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(20); + //static_permutation_builder * pmb = new static_permutation_builder_mrrr(PERM_SAMPLE, bmb); + //static_sequence_builder * ssb = new static_sequence_builder_gmr_chunk(bmb, pmb); // If we found an attribute then "<@>" is present in the tree // if we didn't then it is not. "<$>" is never present in the tree + uint max_tag = 0; + for(uint i=0;i<(uint)npar-1;i++) + max_tag = max(max_tag,tags_aux[i]); + max_tag++; int ntagsize = found_attributes ? 2*ntagnames-1 : 2*ntagnames - 2; - - Tags = new static_sequence_gmr((uint *) tags_aux, (uint) npar-1,ntagsize, bmb, ssb); + tags_aux = (TagType *) urealloc(tags_aux, sizeof(TagType)*(npar + 1)); + tags_aux[npar++] = max_tag; + + static_bitsequence_builder * bmb = new static_bitsequence_builder_brw32(20); + alphabet_mapper *am = new alphabet_mapper_none(); + wt_coder * wc = new wt_coder_huff((uint*)tags_aux,npar,am); + Tags = new static_sequence_wvtree((uint*)tags_aux,npar,wc ,bmb, am); + //Tags = new static_sequence_gmr((uint *) tags_aux, (uint) npar-1,ntagsize, bmb, ssb); + tags_blen = bits(max_tag); + tags_len = (uint)npar; + tags_fix = new uint[uint_len(tags_blen,tags_len)]; + for(uint i=0;i<(uint)npar-1;i++) + set_field(tags_fix,tags_blen,i,tags_aux[i]); delete bmb; - delete pmb; - delete ssb; + //delete pmb; + //delete ssb; // makes the text collection static if (!disable_tc) Text->MakeStatic(); @@ -762,6 +1076,7 @@ int XMLTree::CloseDocument() tags_aux = NULL; finished = true; + print_stats(); return 1; // indicates success in the inicialization } @@ -814,7 +1129,7 @@ int XMLTree::NewOpenTag(unsigned char *tagname) tags_aux[npar] = i; // inserts the new tag id within the preorder sequence of tags npar++; - + return 1; } @@ -838,17 +1153,16 @@ int XMLTree::NewClosingTag(unsigned char *tagname) parArraySize *= 2; } - setbit(par_aux,npar,CP); // marks a new closing opening parenthesis + setbit(par_aux,npar,CP); // marks a new closing parenthesis // transforms the tagname into a tag identifier. If the tag is new, we insert // it in the table. for (i=0; iInsertText(s); + string cpps = (char*) s; + CachedText.push_back(cpps); return 1; // success } @@ -923,7 +1239,7 @@ TagType XMLTree::GetTagId(unsigned char *tagname) // this should be changed for more efficient processing for (i=0; i