initial version

1 files changed, 355 insertions, 0 deletions

diff --git a/src/suffixtree.cpp b/src/suffixtree.cpp
new file mode 100644
index 0000000..604531f
--- /dev/null
+++ b/src/suffixtree.cpp
@@ -0,0 +1,355 @@
+/******************************************************************************
+ *
+ * $Id$
+ *
+ * Copyright (C) 1997-1999 by Dimitri van Heesch.
+ *
+ * Permission to use, copy, modify, and distribute this software and its
+ * documentation under the terms of the GNU General Public License is hereby 
+ * granted. No representations are made about the suitability of this software 
+ * for any purpose. It is provided "as is" without express or implied warranty.
+ * See the GNU General Public License for more details.
+ *
+ * All output generated with Doxygen is not covered by this license.
+ *
+ */
+
+#include <stdio.h>
+#include "suffixtree.h"
+
+#define MAXWORDLEN 1024
+
+//----------------------------------------------------------------------------
+
+bool writeString(QFile &f,const char *s)
+{
+  int len=strlen(s)+1;
+  return (f.writeBlock(s,len)!=len);
+}
+
+bool writeNumber(QFile &f,int num)
+{
+  return (f.putch((num>>24)&0xff)==-1) ||
+         (f.putch((num>>16)&0xff)==-1) ||
+         (f.putch((num>>8)&0xff)==-1)  ||
+         (f.putch(num&0xff)==-1);
+}
+
+bool writeEncodedNumber(QFile &f,uint number)
+{
+  bool error=FALSE;
+  uint n=number;
+  while (n>=128)
+  {
+    int frac=n&0x7f;
+    error = error || (f.putch(frac|0x80)==-1);
+    n>>=7;
+  }
+  error = error || (f.putch(n)==-1); 
+  return error; 
+}
+
+int encodedNumberSize(uint number)
+{
+  uint n=number;
+  int size=1;
+  while (n>=128) { size++; n>>=7; }
+  return size;
+}
+
+//----------------------------------------------------------------------------
+
+int SuffixNodeList::compareItems(GCI item1,GCI item2)
+{
+  SuffixNode *n1=(SuffixNode *)item1;
+  SuffixNode *n2=(SuffixNode *)item2;
+  return strcmp(n1->label,n2->label);
+}
+
+SuffixNode::SuffixNode(const char *lab) : references(0)
+{
+  children = new SuffixNodeList;
+  children->setAutoDelete(TRUE); 
+  label=lab;
+  totalFreq=0;
+  branchOffset=0;
+}
+
+SuffixNode::~SuffixNode() 
+{
+  delete children;
+}
+
+void SuffixNode::addReference(int refId,int inName,int fullWord)
+{
+  totalFreq++;
+  uint s=references.size();
+  if (s>0 && references.at(s-1).id==refId) // word occured in the same document
+  {
+    references.at(s-1).freq++;             // increase word's frequency
+    references.at(s-1).flags=((references.at(s-1).flags & INNAME_MASK) 
+                              | (inName<<INNAME_BIT))
+                         +((references.at(s-1).flags & FULLWORD_MASK) 
+                              | (fullWord<<FULLWORD_BIT))
+                         +((references.at(s-1).flags & WORDINNAME_MASK) 
+                              | ((inName & fullWord)<<WORDINNAME_BIT));
+  }
+  else
+  {
+    references.resize(s+1);
+    references.at(s).id=refId;
+    references.at(s).freq=1; 
+    references.at(s).flags=(inName<<INNAME_BIT)
+                       +(fullWord<<FULLWORD_BIT)
+                       +((inName && fullWord)<<WORDINNAME_BIT);
+  }
+}
+
+int SuffixNode::insert(const char *word,int refId,int inName,int fullWord)
+{
+  int numNewNodes=0;
+  //printf("SuffixNode::insert(%s,%d)\n",word,refId);
+  SuffixNode *sn=children->first();
+  while (sn)
+  {
+    char *lab=sn->label.data();
+    char w=word[0],l=lab[0],i=0;
+    while (w!=0 && l!=0 && w==l) { i++; w=word[i]; l=lab[i]; }
+    if (w==0 && l==0) // match found
+    {
+      sn->addReference(refId,inName,fullWord);
+      return numNewNodes;
+    }
+    if (i>0) // w and l contain a common prefix of length i
+    {
+      if (l==0) // w!=0 => follow this branch
+      {
+        sn->addReference(refId,inName,FALSE);
+        numNewNodes+=sn->insert(&word[i],refId,inName,fullWord);
+      }
+      else // l!=0 => split branch
+      {
+        char leftlab[MAXWORDLEN];
+        memcpy(leftlab,lab,i);
+        leftlab[i]='\0';
+        SuffixNode *r  = new SuffixNode(leftlab);
+        numNewNodes++;
+        SuffixNode *n2 = children->take();
+        // copy reference info
+        r->references  = n2->references.copy();
+        int j,refSize  = r->references.size();
+        for (j=0;j<refSize;j++) 
+        {
+          //r->references[j].fullWord=FALSE;
+          //r->references[j].wordInName=FALSE;
+          r->references[j].flags &= ~(FULLWORD_MASK|WORDINNAME_MASK);
+        }
+        r->totalFreq   = n2->totalFreq;
+        //printf("root branch `%s'\n",leftlab);
+        if (w!=0) // two sub branches
+        {
+          SuffixNode *n1 = new SuffixNode(&word[i]);
+          numNewNodes++;
+          n1->addReference(refId,inName,fullWord);
+          r->addReference(refId,inName,FALSE);
+          r->children->append(n1);
+          //printf("Right branch `%s'\n",&word[i]);
+        }
+        else // one sub branch
+        {
+          r->addReference(refId,inName,fullWord);
+        }
+        //printf("Left branch `%s'\n",&lab[i]);
+        n2->label=&lab[i];
+        r->children->append(n2);
+        children->append(r);
+      }
+      return numNewNodes;
+    }
+    sn=children->next();
+  }
+  //printf("new branch `%s'\n",word);
+  SuffixNode *n=new SuffixNode(word);
+  numNewNodes++;
+  n->addReference(refId,inName,fullWord);
+  children->append(n);
+  return numNewNodes;
+}
+
+void SuffixNode::dump(int level,const char *prefix)
+{
+  uint i;
+  if (references.size()>0)
+  {
+    printf("%s (level=%d offset=%d freq=%d) ",
+           prefix,level,branchOffset,totalFreq);
+    for (i=0;i<references.size();i++) 
+      printf("%d->%d ",references.at(i).id,references.at(i).freq);
+    printf("\n");
+  }
+  SuffixNode *sn=children->first();
+  while (sn)
+  {
+    sn->dump(level+1,prefix+("-"+sn->label)); 
+    sn=children->next();
+  } 
+}
+
+void SuffixNode::resolveForwardReferences(int &offset)
+{
+  if (children->count()>0)
+  {
+    if (label.length()>0) offset++; // terminator for the previous level
+    branchOffset=offset;
+  }
+  else
+    branchOffset=0;
+  SuffixNode *sn=children->first();
+  while (sn)
+  {
+    offset+=sn->label.length()+5;
+    uint i,refs=sn->references.size();
+    if (refs>0)
+    {
+      offset+=encodedNumberSize(sn->totalFreq);
+      offset+=encodedNumberSize((sn->references[0].id<<3)+
+                                 sn->references[0].flags);
+      offset+=encodedNumberSize(sn->references[0].freq);
+      for (i=1;i<refs;i++)
+      {
+        offset+=encodedNumberSize(
+                   ((sn->references.at(i).id - sn->references.at(i-1).id)<<3)+
+                     sn->references.at(i).flags);
+        offset+=encodedNumberSize(sn->references.at(i).freq);
+      }
+      offset+=encodedNumberSize(0);
+    }
+    //printf("Lab=%s offset=%d\n",sn->lab.data(),offset);
+    sn=children->next();
+  } 
+  sn=children->first();
+  while (sn)
+  {
+    //printf("Lab=%s offset=%d\n",sn->lab.data(),offset);
+    sn->resolveForwardReferences(offset);
+    sn=children->next();
+  } 
+}
+
+int SuffixNode::size()
+{
+  int s=0;
+  if (label.length()>0 && children->count()>0) s++; // for the terminator
+  SuffixNode *sn=children->first();
+  while (sn)
+  {
+    uint i,refs=sn->references.size();
+    s+=sn->size()+sn->label.length()+5;
+    if (refs>0)
+    {
+      s+=encodedNumberSize(sn->totalFreq);
+      s+=encodedNumberSize(
+                  (sn->references[0].id<<3)+
+                   sn->references[0].flags);
+      s+=encodedNumberSize(sn->references[0].freq);
+      for (i=1;i<refs;i++)
+      {
+        s+=encodedNumberSize(
+                ((sn->references.at(i).id - sn->references.at(i-1).id)<<3)+
+                  sn->references.at(i).flags);
+        s+=encodedNumberSize(sn->references.at(i).freq);
+      }
+      s+=encodedNumberSize(0);
+    }
+    sn=children->next();
+  } 
+  return s;
+}
+
+bool SuffixNode::write(QFile &f)
+{
+  bool error=FALSE;
+  if (children->count()>0 && label.length()>0) error=error || (f.putch(0)==-1);
+  SuffixNode *sn=children->first();
+  while (sn)
+  {
+    //offset+=sn->lab.length()+1+2*sizeof(int);
+    int i,refs=sn->references.size();
+    error=error || writeString(f,sn->label);
+    error=error || writeNumber(f,sn->branchOffset|((refs==0)?0x80000000:0));
+    if (refs>0)
+    {
+      error=error || writeEncodedNumber(f,sn->totalFreq);
+      error=error || writeEncodedNumber(f,
+                 (sn->references[0].id<<3)+
+                  sn->references[0].flags);
+      error=error || writeEncodedNumber(f,sn->references[0].freq);
+      for (i=1;i<refs;i++)
+      {
+        error=error || writeEncodedNumber(f,
+                ((sn->references[i].id - sn->references[i-1].id)<<3)+
+                  sn->references[i].flags);
+        error=error || writeEncodedNumber(f,sn->references[i].freq);
+      }
+      error=error || writeEncodedNumber(f,0);
+    }
+    //printf("Lab=%s offset=%d\n",sn->lab.data(),offset);
+    sn=children->next();
+  } 
+  sn=children->first();
+  while (sn)
+  {
+    error=error || sn->write(f);
+    sn=children->next();
+  } 
+  return error;
+}
+
+//----------------------------------------------------------------------------
+
+SuffixTree::SuffixTree()
+{
+  root=new SuffixNode("");
+  nodes=1;
+}
+
+SuffixTree::~SuffixTree()
+{
+  delete root;
+}
+
+void SuffixTree::insertWord(const char *word,int index,bool inName)
+{
+  QString suffix=word;
+  uint i;
+  for (i=2;i<suffix.length()-1;i++) 
+  {
+    //printf("Inserting suffix %s\n",suffix.right(i).data());
+    nodes+=root->insert(suffix.right(i),index,inName?1:0,FALSE);
+  }
+  nodes+=root->insert(word,index,inName?1:0,TRUE);
+}
+
+void SuffixTree::dump()
+{
+  root->dump(0,"");
+}
+
+void SuffixTree::resolveForwardReferences()
+{
+  int offset=8;
+  root->resolveForwardReferences(offset);
+}
+
+int SuffixTree::size()
+{
+  return root->size();
+}
+
+bool SuffixTree::write(QFile &f)
+{
+  if (!f.isOpen()) { printf("File not open\n"); return FALSE; }
+  bool error=FALSE;
+  error = error || root->write(f);
+  return !error;
+}