cqdb.h

CRFsuite is a very fast implmentation of the Conditional Random Fields (CRF) algorithm. It handles t

  data.
- <b>Omissible reverse look-up array.</b> The reverse look-up array can be
  omitted if it is not necessary to retrieve strings from integer identifiers.
- <b>Cross platform.</b> The source code can be compiled on Microsoft Visual
  Studio 2005, GNU C Compiler (gcc), etc.
- <b>Simple API.</b> The CQDB API exposes only a few functions.

CQDB is suitable for implementing dictionaries in which fast look-ups of
strings and identifiers are essential while a dictionary update rarely occurs.
The data structure is a specialization (and extension) of the
<a href="http://cr.yp.to/cdb.html">Constant Database</a> proposed by
Daniel J. Bernstein.

CQDB does not support assigning a unique integer identifier for a given string,
modify associations, nor check collisions in strings and identifiers; thus,
it may be necessary to use an existing Quark implementation to manage proper
associations between strings and identifiers on memory.

This library is used by the 
<a href="http://www.chokkan.org/software/crfsuite/">CRFsuite</a> project.

@section download Download

- <a href="http://www.chokkan.org/software/dist/cqdb-1.1.tar.gz">Source code</a>

CQDB is distributed under the term of the
<a href="http://www.opensource.org/licenses/bsd-license.php">modified BSD license</a>.

@section changelog History
- Version 1.1 (2007-12-01):
    - Fixed a bug when a CQDB chunk is embedded to a file.

- Version 1.0 (2007-09-20):
    - Initial release.

@section api Documentation

- @ref cqdb_const "CQDB Constants"
- @ref cqdb_reader "CQDB Reader API"
- @ref cqdb_writer "CQDB Writer API"

@section sample Sample programs
@subsection sample_writer A writer sample

This sample code constructs a database "test.cqdb" with 1,000,000
string/identifier associations,
"00000000"/0, "00000001"/1, ..., "01000000"/1000000.

@code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "cqdb.h"

#define    DBNAME        "test.cqdb"
#define    NUMELEMS    1000000

int main(int argc, char *argv[])
{
    int i, ret;
    char str[10];
    FILE *fp = NULL;
    cqdb_writer_t* dbw = NULL;

    // Open a file for writing.
    fp = fopen(DBNAME, "wb");
    if (fp == NULL) {
        fprintf(stderr, "ERROR: failed to open the file.\n");
        return 1;
    }

    // Create a CQDB on the file stream.
    dbw = cqdb_writer(fp, 0);
    if (dbw == NULL) {
        fprintf(stderr, "ERROR: failed to create a CQDB on the file.\n");
        goto error_exit;
    }

    // Put string/integer associations, "00000001"/1, ..., "01000000"/1000000.
    for (i = 0;i < NUMELEMS;++i) {
        sprintf(str, "%08d", i);
        if (ret = cqdb_writer_put(dbw, str, i)) {
            fprintf(stderr, "ERROR: failed to put a pair '%s'/%d.\n", str, i);
            goto error_exit;    
        }
    }

    // Close the CQDB.
    if (ret = cqdb_writer_close(dbw)) {
        fprintf(stderr, "ERROR: failed to close the CQDB.\n");        
        goto error_exit;
    }

    // Close the file.
    fclose(fp);
    return 0;

error_exit:
    if (dbw != NULL) cqdb_writer_close(dbw);
    if (fp != NULL) fclose(fp);
    return 1;
}

@endcode

@subsection sample_reader A reader sample

This sample code issues string queries "00000000", ..., "01000000" to retrive
integer identifiers (forward lookups) and integer queries 0, ..., 1000000 to
retrieve the strings  "00000000", ..., "01000000". 

@code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "cqdb.h"

#define    DBNAME        "test.cqdb"
#define    NUMELEMS    1000000

int main(int argc, char *argv[])
{
    int i, j, ret;
    long size = 0;
    char str[10], *value = NULL, *buffer = NULL;
    FILE *fp = NULL;
    cqdb_t* db = NULL;

    // Open the database.
    fp = fopen(DBNAME, "rb");
    if (fp == NULL) {
        fprintf(stderr, "ERROR: failed to open the file\n");
        return 1;
    }

    // Obtain the file size.
    fseek(fp, 0, SEEK_END);
    size = ftell(fp);
    fseek(fp, 0, SEEK_SET);

    // Read the content of the file at a time.
    buffer = (char *)malloc(size);
    if (buffer == NULL) {
        fprintf(stderr, "ERROR: out of memory.\n");
        goto error_exit;
    }
    fread(buffer, 1, size, fp);
    fclose(fp);
    fp = NULL;

    // Open the database on the memory.
    db = cqdb_reader(buffer, size);
    if (db == NULL) {
        fprintf(stderr, "ERROR: failed to open a CQDB on the file.\n");
        goto error_exit;
    }

    // Forward lookups: strings to integer identifiers.
    for (i = 0;i < NUMELEMS;++i) {
        sprintf(str, "%08d", i);
        j = cqdb_to_id(db, str);
        // Validity check.
        if (j < 0 || i != j) {
            fprintf(stderr, "ERROR: inconsistency error '%s'/%d.\n", str, i);
            goto error_exit;    
        }
    }

    // Reverse lookups: integer identifiers to strings.
    for (i = 0;i < NUMELEMS;++i) {
        sprintf(str, "%08d", i);
        value = cqdb_to_string(db, i);
        // Validity check.
        if (value == NULL || strcmp(str, value) != 0) {
            fprintf(stderr, "ERROR: inconsistency error '%s'/%d.\n", str, i);
            goto error_exit;    
        }
    }

    // Delete the instance of the CQDB.
    cqdb_delete(db);
    free(buffer);

    return 0;

error_exit:
    if (fp != NULL) fclose(fp);
    if (buffer != NULL) free(buffer);
    return 1;
}

@endcode

@section performance Performance

An experiment for performance comparision with
<a href="http://www.oracle.com/database/berkeley-db/">Berkeley DB (BDB) 4.5.20</a>
and <a href="http://qdbm.sourceforge.net/">Quick Database Manager (QDBM) 1.8.75</a>
was conducted.
Constructing a database with 1,000,000 string/identifier associations,
"00000000"/0, "00000001"/1, ..., "01000000"/1000000, this experiment issued
string queries "00000000", ..., "01000000" (forward lookups) and integer
queries 0, ..., 1000000 (reverse lookups) to the database. Since BDB and
QDBM do not support reverse lookups, reverse items (key: identifier,
value: string) were inserted to the database in addition to the forward items
(key: string, value: integer). Microsoft Windows Vista Business was running on
the test environment (Intel Core2Duo 6600 (2.40GHz) processor, Intel G965
chipset, 2GB main memory, and Seagate ST3320620 HDD).
The test codes were compiled with Microsoft Visual Studio 2005.

This table shows the elapsed time for constructing the database (write time),
the elapsed time for processing with the queries (read time), and the size of
the database generated by each database library.
The read/write access was extremely faster than those of other database
libraries. The database was smaller than half the size of those generated by
other libraries.
This results suggest that the CQDB has the substantial advantage over the
existing database libraries for implementing a static quark database.

<table>
<tr>
<th>Database</th><th>Parameters</th><th>Write time [sec]</th><th>Read time [sec]</th><th>Database size [MB]</th>
</tr>
<tr align="right">
<td align="left">Constant Quark Database (CQDB) 1.0</td>
<td align="left">Default (none)</td>
<td><b>1.48</b></td><td><b>0.65</b></td><td><b>35.2</b></td>
</tr>
<tr align="right">
<td align="left">Berkeley DB (BDB) 4.5.20</td>
<td align="left">Default</td>
<td>91.8</td><td>37.5</td><td>79.7</td>
</tr>
<tr align="right">
<td align="left">Berkeley DB (BDB) 4.5.20</td>
<td align="left">table_size=4000000; cache_size=200MB</td>
<td>57.8</td><td>37.5</td><td>79.7</td>
</tr>
<tr align="right">
<td align="left">Quick Database Manager (QDBM) 1.8.75</td>
<td align="left">Default</td>
<td>95.4</td><td>80.6</td><td>76.3</td>
</tr>
<tr align="right">
<td align="left">Quick Database Manager (QDBM) 1.8.75</td>
<td align="left">table_size=4000000</td>
<td>15.7</td><td>12.0</td><td>92.2</td>
</tr>
</table>

@section reference Reference
- <a href="http://cr.yp.to/cdb.html">cdb</a> by Daniel J. Bernstein.
- <a href="http://www.corpit.ru/mjt/tinycdb.html">TinyCDB</a> by Michael Tokarev.
- <a href="http://www.unixuser.org/~euske/doc/cdbinternals/index.html">Constant Database (cdb) Internals</a> by Yusuke Shinyama.
- <a href="http://www.burtleburtle.net/bob/hash/index.html">Hash Functions and Block Ciphers</a> by Bob Jenkins.

*/

#endif/*__CQDB_H__*/