From e421727c5a512154cf2c3ff4cf8390eb88d527d7 Mon Sep 17 00:00:00 2001 From: darroyue Date: Tue, 25 Nov 2008 08:38:27 +0000 Subject: [PATCH] added text search functions, fixed the bug when initializing TagName, and some minor changes git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/XMLTree@15 3cdefd35-fc62-479d-8e8d-bae585ffb9ca --- XMLTree.cpp | 164 +++++++++++++++++++++++++++++++++++++++++++++++---- XMLTree.h | 46 ++++++++++++--- makefile | 11 +++- test_XML.cpp | 18 +++--- 4 files changed, 205 insertions(+), 34 deletions(-) diff --git a/XMLTree.cpp b/XMLTree.cpp index a3fefea..ea12fad 100644 --- a/XMLTree.cpp +++ b/XMLTree.cpp @@ -1,6 +1,6 @@ #include "XMLTree.h" -#include + // functions to convert tag positions to the corresponding tree node and viceversa. // These are implemented in order to be able to change the tree and Tags representations, // without affecting the code so much. @@ -51,7 +51,7 @@ void XMLTree::Save(unsigned char *filename) Tags->save(fp); // stores the texts - //Text->Save(fp); + Text->Save(fp); fclose(fp); @@ -105,7 +105,7 @@ XMLTree *XMLTree::Load(unsigned char *filename, int sample_rate_text) XML_Tree->Tags = static_sequence_wvtree::load(fp); // loads the texts - //XML_Tree->Text->Load(fp,sample_rate_text); + XML_Tree->Text->Load(fp,sample_rate_text); fclose(fp); @@ -136,9 +136,9 @@ XMLTree::~XMLTree() delete Tags; Tags = NULL; - //Text->~TextCollection(); - // delete Text; - // Text = NULL; + Text->~TextCollection(); + delete Text; + Text = NULL; initialized = false; finished = false; @@ -147,18 +147,31 @@ XMLTree::~XMLTree() // root(): returns the tree root. treeNode XMLTree::Root() { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } return root_node(Par); } // SubtreeSize(x): the number of nodes (and attributes) in the subtree of node x. int XMLTree::SubtreeSize(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } return subtree_size(Par, x); } // SubtreeTags(x,tag): the number of occurrences of tag within the subtree of node x. int XMLTree::SubtreeTags(treeNode x, TagType tag) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + int s = x + 2*subtree_size(Par, x) - 1; return Tags->rank(tag, s) - Tags->rank(tag, node2tagpos(x)-1); @@ -174,12 +187,22 @@ bool XMLTree::IsLeaf(treeNode x) // IsAncestor(x,y): returns whether node x is ancestor of node y. bool XMLTree::IsAncestor(treeNode x, treeNode y) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + return is_ancestor(Par, x, y); } // IsChild(x,y): returns whether node x is parent of node y. bool XMLTree::IsChild(treeNode x, treeNode y) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + if (!is_ancestor(Par, x, y)) return false; return depth(Par, x) == (depth(Par, y) + 1); } @@ -188,18 +211,33 @@ bool XMLTree::IsChild(treeNode x, treeNode y) // of Sadakane. int XMLTree::NumChildren(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + return degree(Par, x); } // ChildNumber(x): returns i if node x is the i-th children of its parent. int XMLTree::ChildNumber(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + return child_rank(Par, x); } // Depth(x): depth of node x, a simple binary rank on the parentheses sequence. int XMLTree::Depth(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + return depth(Par, x); } @@ -207,6 +245,11 @@ int XMLTree::Depth(treeNode x) // nodes (i.e., tags, it disregards the texts in the tree). int XMLTree::Preorder(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + return preorder_rank(Par, x); } @@ -214,12 +257,22 @@ int XMLTree::Preorder(treeNode x) // nodes (i.e., tags, it disregards the texts in the tree). int XMLTree::Postorder(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + return postorder_rank(Par, x); } // Tag(x): returns the tag identifier of node x. TagType XMLTree::Tag(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + return Tags->access(node2tagpos(x)); } @@ -227,6 +280,11 @@ TagType XMLTree::Tag(treeNode x) // returns {NULLT, NULLT} when there are no texts descending from x. range XMLTree::DocIds(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + range r; if (indexing_empty_texts) { // faster, no rank needed r.min = x; @@ -250,12 +308,22 @@ range XMLTree::DocIds(treeNode x) // Parent(x): returns the parent node of node x. treeNode XMLTree::Parent(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + return parent(Par, x); } // Child(x,i): returns the i-th child of node x, assuming it exists. treeNode XMLTree::Child(treeNode x, int i) - { +{ + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + if (i <= OPTD) return naive_child(Par, x, i); else return child(Par, x, i); } @@ -263,18 +331,33 @@ treeNode XMLTree::Child(treeNode x, int i) // FirstChild(x): returns the first child of node x, assuming it exists. Very fast in BP. treeNode XMLTree::FirstChild(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + return first_child(Par, x); } // NextSibling(x): returns the next sibling of node x, assuming it exists. treeNode XMLTree::NextSibling(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + return next_sibling(Par, x); } // PrevSibling(x): returns the previous sibling of node x, assuming it exists. treeNode XMLTree::PrevSibling(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + return prev_sibling(Par, x); } @@ -283,6 +366,11 @@ treeNode XMLTree::PrevSibling(treeNode x) // efficiently, just iterating among the children of node x until finding the desired child. treeNode XMLTree::TaggedChild(treeNode x, int i, TagType tag) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + treeNode child; child = first_child(Par, x); // starts at first child of node x @@ -301,6 +389,11 @@ treeNode XMLTree::TaggedChild(treeNode x, int i, TagType tag) // the subtree of x. Returns NULLT if there is none. treeNode XMLTree::TaggedDesc(treeNode x, TagType tag) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + int r, s; treeNode y; r = (int) Tags->rank(tag, node2tagpos(x)); @@ -315,6 +408,11 @@ treeNode XMLTree::TaggedDesc(treeNode x, TagType tag) // ancestor of x. Returns NULLT if there is none. treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + int r, s; treeNode node_s, root; r = (int)Tags->rank(tag, node2tagpos(x)-1); @@ -335,6 +433,11 @@ treeNode XMLTree::TaggedPrec(treeNode x, TagType tag) // the subtree of x. Returns NULLT if there is none. treeNode XMLTree::TaggedFoll(treeNode x, TagType tag) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + int r, s; r = (int) Tags->rank(tag, node2tagpos(next_sibling(Par, x))-1); s = (int) Tags->select(tag, r+1); // select returns -1 in case that there is no r+1-th tag. @@ -347,6 +450,11 @@ treeNode XMLTree::TaggedFoll(treeNode x, TagType tag) // Assumes Doc ids start from 0. DocID XMLTree::PrevText(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + if (x == Root()) return NULLT; if (indexing_empty_texts) // faster, no rank needed return (DocID)x-1; @@ -362,6 +470,11 @@ DocID XMLTree::PrevText(treeNode x) // of node x, or NULLT if x is the root node. Assumes Doc ids start from 0. DocID XMLTree::NextText(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + if (x == Root()) return NULLT; if (indexing_empty_texts) // faster, no rank needed return (DocID)x+2*subtree_size(Par, x)-1; @@ -379,6 +492,11 @@ DocID XMLTree::NextText(treeNode x) // ids start from 0. DocID XMLTree::MyText(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + if (!IsLeaf(x)) return NULLT; if (indexing_empty_texts) // faster, no rank needed return (DocID)x; @@ -394,6 +512,11 @@ DocID XMLTree::MyText(treeNode x) // all tree nodes and all text nodes. Assumes that the tree root has preorder 1. int XMLTree::TextXMLId(DocID d) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + if (indexing_empty_texts) return d + rank_open(Par, d)+1; // +1 because root has preorder 1 else { // slower, needs rank and select @@ -407,6 +530,11 @@ int XMLTree::TextXMLId(DocID d) // preorder 0; int XMLTree::NodeXMLId(treeNode x) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + if (indexing_empty_texts) return x - 1 + rank_open(Par, x); else { @@ -419,6 +547,11 @@ int XMLTree::NodeXMLId(treeNode x) // ParentNode(d): returns the parent node of document identifier d. treeNode XMLTree::ParentNode(DocID d) { + if (!finished) { + fprintf(stderr, "Error: data structure has not been constructed properly\n"); + exit(1); + } + int s; if (indexing_empty_texts) s = d; else s = EBVector->select1(d); @@ -457,6 +590,8 @@ int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text) return NULLT; } + TagName = NULL; + if (!indexing_empty_texts) { empty_texts_aux = (unsigned int *)malloc(sizeof(unsigned int)); if (!empty_texts_aux) { @@ -465,7 +600,7 @@ int XMLTree::OpenDocument(bool empty_texts, int sample_rate_text) } } - //Text = TextCollection::InitTextCollection(sample_rate_text); + Text = TextCollection::InitTextCollection((unsigned)sample_rate_text); return 1; // indicates success in the initialization of the data structure } @@ -500,7 +635,7 @@ int XMLTree::CloseDocument() Tags = new static_sequence_wvtree((uint *) tags_aux, (uint) npar-1, wtc, bmb, am); // makes the text collection static - //Text->MakeStatic(); + Text->MakeStatic(); // creates the data structure marking the non-empty texts (just in the case it is necessary) if (!indexing_empty_texts) @@ -600,8 +735,9 @@ int XMLTree::NewClosingTag(unsigned char *tagname) } ntagnames++; - TagName[i] = (unsigned char *)malloc(sizeof(char)*(strlen((const char *)tagname)+1)); - strcpy((char *)TagName[i], (const char *)tagname); + TagName[i] = (unsigned char *)malloc(sizeof(char)*(strlen((const char *)tagname)+2)); + TagName[i][0] = '/'; + strcpy((char *)&(TagName[i][1]), (const char *)tagname); } tags_aux = (TagType *)realloc(tags_aux, sizeof(TagType)*(npar + 1)); @@ -640,7 +776,7 @@ int XMLTree::NewText(unsigned char *s) bitset(empty_texts_aux, npar-1); // marks the non-empty text with a 1 in the bit vector } - //Text->InsertText(s); + Text->InsertText(s); return 1; // success } @@ -667,7 +803,7 @@ int XMLTree::NewEmptyText() bitclean(empty_texts_aux, npar-1); // marks the empty text with a 0 in the bit vector } - // else Text->InsertText(&c); // we insert the empty text just in case we index all the texts + else Text->InsertText(&c); // we insert the empty text just in case we index all the texts return 1; // success } @@ -698,3 +834,5 @@ unsigned char *XMLTree::GetTagName(TagType tagid) return s; } + + diff --git a/XMLTree.h b/XMLTree.h index bb1dbbb..319b9a6 100644 --- a/XMLTree.h +++ b/XMLTree.h @@ -25,12 +25,13 @@ #include #include #include "bp.h" +#include "TextCollection/TextCollection.h" +using SXSI::TextCollection; #include "libcds/includes/static_bitsequence.h" #include "libcds/includes/alphabet_mapper.h" #include "libcds/includes/static_sequence.h" -//#include "TextCollection/TextCollection.h" -//using SXSI::TextCollection; + // this constant is used to efficiently compute the child operation in the tree #define OPTD 10 @@ -70,7 +71,7 @@ class XMLTree { static_sequence_wvtree *Tags; /** The texts in the XML document */ - //TextCollection *Text; + TextCollection *Text; /** Flag indicating whether the whole data structure has been constructed or * not. If the value is true, you cannot add more texts, nodes, etc. */ @@ -251,14 +252,41 @@ public: * Returns NULL in case that the tag identifier is not valid.*/ unsigned char *GetTagName(TagType tagid); - /** saveXMLTree: saves XML tree data structure to file. Every component of - * the collection is stored in different files (same name, different file - * extensions). */ + /** Prefix(s): search for texts prefixed by string s. */ + TextCollection::document_result Prefix(uchar const *s) { + Text->Prefix(s); + } + + /** Suffix(s): search for texts having string s as a suffix. */ + TextCollection::document_result Suffix(uchar const *s) { + Text->Suffix(s); + } + + /** Equal(s): search for texts equal to string s. */ + TextCollection::document_result Equal(uchar const *s) { + Text->Equal(s); + } + + /** Contains(s): search for texts containing string s. */ + TextCollection::document_result Contains(uchar const *s) { + Text->Contains(s); + } + + TextCollection::document_result LessThan(uchar const *s) { + Text->LessThan(s); + } + + /** GetText(d): returns the text corresponding to document with + * id d. */ + uchar* GetText(DocID d) { + Text->GetText(d); + } + + /** Save: saves XML tree data structure to file. */ void Save(unsigned char *filename); - /** load: loads XML tree data structure from file. */ + /** Load: loads XML tree data structure from file. sample_rate_text + * indicates the sample rate for the text search data structure. */ static XMLTree *Load(unsigned char *filename, int sample_rate_text); }; - - #endif diff --git a/makefile b/makefile index a3b0e61..5db952e 100644 --- a/makefile +++ b/makefile @@ -1,12 +1,14 @@ FLAGS = -O9 -I./libcds/includes/ OBJECTS=libcds/lib/libcds.a +OBJECTS_TC= TextCollection/BitRank.o TextCollection/dynFMI.o TextCollection/rbtree.o TextCollection/Tools.o TextCollection/bittree.o TextCollection/handle.o TextCollection/testTextCollection.o TextCollection/CSA.o TextCollection/pos.o TextCollection/TextCollection.o -all: text_collection XMLTree + +all: libcds text_collection XMLTree XMLTree: XMLTree.o bp.o darray.o bpcore.o libcds/lib/libcds.a cp libcds/lib/libcds.a XMLTree.a - ar vrcs XMLTree.a XMLTree.o bp.o darray.o bpcore.o + ar vrcs XMLTree.a XMLTree.o bp.o darray.o bpcore.o $(OBJECTS_TC) XMLTree.o: bp.c bp.h bpcore.c XMLTree.cpp XMLTree.h @@ -24,5 +26,8 @@ bpcore.o: bpcore.c text_collection: make -C TextCollection/ +libcds: + make -C libcds/ + clean: - rm -f *.o \ No newline at end of file + rm -f *.o diff --git a/test_XML.cpp b/test_XML.cpp index 20265cf..c13c04d 100644 --- a/test_XML.cpp +++ b/test_XML.cpp @@ -21,10 +21,10 @@ int main() { XMLTree *X, *Y; int rr, n, i; - unsigned char openTag[]="A", closeTag[]="/A", filename[]="testXML"; + unsigned char openTag[]="A", closeTag[]="/A", filename[]="testXML", text[]="Hello World"; treeNode x; - n = 4999999; + n = 49999; X = new XMLTree(); @@ -42,7 +42,7 @@ int main() X->NewClosingTag(closeTag); if ((1+(int) (2.0*rand()/(RAND_MAX+1.0))) == 1) X->NewEmptyText(); - else X->NewText(NULL); // just a test, NULL string + else X->NewText(text); rr--; } else { @@ -50,14 +50,14 @@ int main() X->NewOpenTag(openTag); if ((1+(int) (2.0*rand()/(RAND_MAX+1.0))) == 1) X->NewEmptyText(); - else X->NewText(NULL); + else X->NewText(text); rr++; } else { X->NewClosingTag(closeTag); if ((1+(int) (2.0*rand()/(RAND_MAX+1.0))) <= 1) X->NewEmptyText(); - else X->NewText(NULL); + else X->NewText(text); rr--; } } @@ -74,13 +74,13 @@ int main() X->Save(filename); - delete X; + //delete X; - X = XMLTree::Load(filename, 32); +// X = XMLTree::Load(filename, 32); - x = X->Root(); + // x = X->Root(); - traverseXML(X, x); + //traverseXML(X, x); } -- 2.17.1