C++ String B-Tree Library

Features

• Very easy to use, see doxygen documentation for the description of API or example below
• Perform lookup in a very huge lexicon with only two disk access
• Can be used to store patricia trie on disk (class TrieToStr)
• It is well suited for static lexicon. If you want to add a new lexicon entry, this implementation need to rewrite the full file
• You can use it for non-commercial and commercial purposes, licensed under terms of GNU LGPL license

Download

Download Clustering-0.1.tgz
Doxygen Documentation: view online or download

Example

Here is a simple example that use this library :

#include "strBTree/io.h"
#include "strBTree/SortStringsFile.h"
#include "strBTree/StringBTree.h"

int main(int argc, char **argv)
{
  // First of all, write lexicon entry in a huge file
  FILE *f = fopen("lexicon", "wb");
  assert(f);

  // Lexicon entry are read outside of this scope unordered and
  // duplicates...
  const char *l1 = "1first lexicon entry";
  const char *l2 = "0second lexicon entry";
  const char *l3 = "2third lexicon entry";

  // Imagine that we received lexicon entry in order l3, l1, l3, l2, l1

  StringBTree::writeString(f, l3, strlen(l3));
  StringBTree::writeString(f, l1, strlen(l1));
  StringBTree::writeString(f, l3, strlen(l3));
  StringBTree::writeString(f, l2, strlen(l2));
  StringBTree::writeString(f, l1, strlen(l1));
  fclose(f);

  // Sort file, first boolean indicates that I want the sort program
  // to compute frequency of identicals pattern (it will output a file
  // lexicon.freqs), the second boolean indicates that I want
  // to remove duplicate entries
  StringBTree::SortStringsFile sort("lexicon", true, true);
  sort.start("/tmp", 2);
  uint64_t nbValues = sort.getNbValues();
  std::cout << "Nb Entries : " <<  nbValues << std::endl;
  
  StringBTree::StrBTree bTree("lexicon", nbValues);
  
  // Create String B Tree
  bTree.constructBTree("btree");
  std::cout << l1 << " : " << bTree.getEntry(l1, strlen(l1)) << std::endl;
  std::cout << l2 << " : " << bTree.getEntry(l2, strlen(l2)) << std::endl;
  std::cout << l3 << " : " << bTree.getEntry(l3, strlen(l3)) << std::endl;
  std::cout << "other : " << bTree.getEntry("other", 5) << std::endl;
}

This example produces the following output :

Nb Entries : 3
1first lexicon entry : 2
0second lexicon entry : 1
2third lexicon entry : 3
other : 0