I was wondering if we could speed-up lookup in a hash table of strings by only storing the difference between them, like HAMT. Taking this idea to its end, I ended up with a binary PATRICiA prefix-tree data-structure. There is an example of pretty much what I'm doing in the section on PATRICiA trees in Crochemore, Lecroq, 2009, (except they have the byte-order flipped.)
Code
Because there is a lot of code, I am looking for a general review or a review of a part of the code. This all goes into one C
file, but I will break the file down into smaller chunks.
A minimal C
vector-like-type in an X-Macro.
#include <stdlib.h> /* EXIT malloc free qsort */
#include <stdio.h> /* printf */
#include <string.h> /* memmove memcpy */
#include <assert.h> /* assert */
#include <errno.h> /* errno */
#include <limits.h> /* INT_MAX */
/* X-macro for a minimal dynamic array. */
#define MIN_ARRAY(name, Name, type) \
struct Name##Array { type *data; size_t size, capacity; }; \
/* Initialises `a` to idle. */ \
static void name##_array(struct Name##Array *const a) \
{ assert(a), a->data = 0, a->capacity = a->size = 0; } \
/* Destroys `a` and returns it to idle. */ \
static void name##_array_(struct Name##Array *const a) \
{ assert(a), free(a->data), name##_array(a); } \
/* Ensures `min_capacity` of `a`. @param[min_capacity] If zero, does nothing.
@return Success; otherwise, `errno` will be set.
@throws[ERANGE] Tried allocating more then can fit in `size_t` or `realloc`
doesn't follow POSIX. @throws[realloc, ERANGE] */ \
static int name##_array_reserve(struct Name##Array *const a, \
const size_t min_capacity) { \
size_t c0; \
type *data; \
const size_t max_size = (size_t)-1 / sizeof *a->data; \
assert(a); \
if(a->data) { \
if(min_capacity <= a->capacity) return 1; \
c0 = a->capacity; \
if(c0 < 8) c0 = 8; \
} else { /* Idle. */ \
if(!min_capacity) return 1; \
c0 = 8; \
} \
if(min_capacity > max_size) return errno = ERANGE, 0; \
/* `c_n = a1.625^n`, approximation golden ratio `\phi ~ 1.618`. */ \
while(c0 < min_capacity) { \
size_t c1 = c0 + (c0 >> 1) + (c0 >> 3); \
if(c0 >= c1) { c0 = max_size; break; } \
c0 = c1; \
} \
if(!(data = realloc(a->data, sizeof *a->data * c0))) \
{ if(!errno) errno = ERANGE; return 0; } \
a->data = data, a->capacity = c0; \
return 1; \
} \
/* @return Push back a new un-initialized datum of `a`.
@throws[realloc, ERANGE] */ \
static type *name##_array_new(struct Name##Array *const a) { \
assert(a); \
return name##_array_reserve(a, a->size + 1) ? a->data + a->size++ : 0; \
}
Branches array. Each entry represents an internal node, storing two items of information that it needs to represent a tree semi-implicitly in a size_t
.
/* Trie pre-order internal nodes in the style of <Morrison, 1968 PATRICiA>. */
MIN_ARRAY(size, Size, size_t)
/* 12 makes the maximum skip length 512 bytes and the maximum size of a trie is
`size_t` 64-bits: 4503599627370495, 32-bits: 1048575, 16-bits: 15, 8-bits: not
supported at all, sorry, (unlikely since `C++` has additional constraints.) */
#define TRIE_SKIP 12
#define TRIE_SKIP_MAX ((1 << TRIE_SKIP) - 1)
#define TRIE_LEFT_MAX (((size_t)1 << ((sizeof(size_t) << 3) - TRIE_SKIP)) - 1)
/** @return Packs `skip` and `left` into a branch. */
static size_t trie_branch(const size_t skip, const size_t left) {
assert(skip <= TRIE_SKIP_MAX && left <= TRIE_LEFT_MAX);
return skip + (left << TRIE_SKIP);
}
/** @return Unpacks skip from `branch`. */
static size_t trie_skip(const size_t branch)
{ return branch & TRIE_SKIP_MAX; }
/** @return Unpacks left descendent branches from `branch`. */
static size_t trie_left(const size_t branch) { return branch >> TRIE_SKIP; }
/** Overwrites `skip` in `branch`. */
static void trie_skip_set(size_t *const branch, size_t skip) {
assert(branch && skip <= TRIE_SKIP_MAX);
*branch &= ~TRIE_SKIP_MAX;
*branch += skip;
}
/** Increments the left descendants `branch` count. @fixme This will trip an
`assert` if two strings have subsequences that are equal in more than 2^12
bits and then different. */
static void trie_left_inc(size_t *const branch) {
assert(branch && *branch < ~(size_t)TRIE_SKIP_MAX);
*branch += TRIE_SKIP_MAX + 1;
}
/** Decrements the left descendants `branch` count. */
static void trie_left_dec(size_t *const branch) {
assert(branch && *branch > TRIE_SKIP_MAX);
*branch -= TRIE_SKIP_MAX + 1;
}
/** Compares `bit` from the string `a` against `b`.
@return In the `bit` position, positive if `a` is after `b`, negative if `a`
is before `b`, or zero if `a` is equal to `b`. */
static int trie_strcmp_bit(const char *const a, const char *const b,
const size_t bit) {
const size_t byte = bit >> 3, mask = 128 >> (bit & 7);
return !(b[byte] & mask) - !(a[byte] & mask);
}
/** From string `a`, extract `bit`, either 0 or 1. */
static int trie_is_bit(const char *const a, const size_t bit) {
const size_t byte = bit >> 3, mask = 128 >> (bit & 7);
return !!(a[byte] & mask);
}
/** @return Whether `a` and `b` are equal up to the minimum of their lengths'.
Used in <fn:prefix>. */
static int trie_is_prefix(const char *a, const char *b) {
for( ; ; a++, b++) {
if(*a == '\0') return 1;
if(*a != *b) return *b == '\0';
}
}
A lexicographically sorted array of words, which are trie leaves. Branches can be seen as an index to this array.
/** Leaves are string constants necessarily in lexicographic order; `typedef`
because it could be a more complex structure like an associative array. */
typedef const char *Leaf;
MIN_ARRAY(leaf, Leaf, Leaf)
Initialisation code for a trie generated from an array.
/** Trie is a full binary tree; it's either empty or
`|branches| + 1 = |leaves|`. The reason we spilt branches and leaves is it's
`O(1)` to check the leftmost leaf of a branch, which we do on insertion. */
struct Trie { struct SizeArray branches; struct LeafArray leaves; };
/** Initialises `t` to idle. */
static void trie(struct Trie *const t)
{ assert(t); size_array(&t->branches), leaf_array(&t->leaves); }
/** Returns an initialised `t` to idle. */
static void trie_(struct Trie *const t)
{ assert(t); size_array_(&t->branches), leaf_array_(&t->leaves); }
/** Orders `a` and `b` used in <fn:trie_init>. @implements qsort bsearch */
static int vstrcmp(const void *const a, const void *const b)
{ return strcmp(*(const char *const*)a, *(const char *const*)b); }
/** Recursive function used for <fn:trie_init>. Initialise branches of `t`
up to `bit` with `a` to `a_size` array of sorted leaves.
@order Speed \O(`a_size` log E(`a.length`))?; memory \O(E(`a.length`)). */
static void trie_init_branches_r(struct Trie *const t, size_t bit,
const size_t a, const size_t a_size) {
size_t b = a, b_size = a_size, half;
size_t skip = 0;
size_t *branch;
assert(t && a_size && a_size <= t->leaves.size && t->leaves.size
&& t->branches.capacity >= t->leaves.size - 1);
if(a_size <= 1) return;
/* Endpoints of sorted range: skip [_1_111...] or [...000_0_] don't care.
fixme: UINT_MAX overflow. */
while(trie_is_bit(t->leaves.data[a], bit)
|| !trie_is_bit(t->leaves.data[a + a_size - 1], bit)) bit++, skip++;
/* Do a binary search for the first `leaves[a+half_s]#bit == 1`. */
while(b_size) half = b_size >> 1,
trie_is_bit(t->leaves.data[b + half], bit)
? b_size = half : (half++, b += half, b_size -= half);
b_size = b - a;
/* Should have space for all branches pre-allocated in <fn:<PN>init>. */
branch = size_array_new(&t->branches), assert(branch);
*branch = trie_branch(skip, b_size - 1);
bit++;
trie_init_branches_r(t, bit, a, b_size);
trie_init_branches_r(t, bit, b, a_size - b_size);
}
/** Initialises `t` to `a` of size `a_size`, which cannot be zero. For code
brevity, all entries of `a` have to be unique. If this is not the case, the
strings will happily go past the null and cause undefined behaviour.
@return Success. @throws[ERANGE, malloc]
@fixme There's a better way to do this somewhere in the literature? */
static int trie_init(struct Trie *const t, const Leaf *const a,
const size_t a_size) {
Leaf *leaves;
assert(t && a && a_size);
trie(t);
/* This will store space for all of the duplicates, as well. */
if(!leaf_array_reserve(&t->leaves, a_size)
|| !size_array_reserve(&t->branches, a_size - 1)) return 0;
leaves = t->leaves.data;
memcpy(leaves, a, sizeof *a * a_size);
t->leaves.size = a_size;
/* Sort, get rid of duplicates, and initialise branches. */
qsort(leaves, a_size, sizeof *a, &vstrcmp);
/* fixme: this is where we de-duplicate `t->leaves`; left out. */
trie_init_branches_r(t, 0, 0, t->leaves.size);
assert(t->branches.size + 1 == t->leaves.size);
return 1;
}
param_index_get
, supplied with a key
, looks up the position in the index branches, and wrappers.
/** Looks at only the index for potential matches.
@param[result] A index pointer to leaves that matches `key` when true.
@return True if `key` in `trie` may have matched, otherwise `key` is
definitely is not in `trie`. @order \O(`key.length`) */
static int param_index_get(const struct Trie *const t, const char *const key,
size_t *const result) {
/* `(n0, n1]` is the index of pre-order `ancestor` (`n0`) and all
descendant branches. `i` is the leaf index. `left` is all ancestor's left
branches. */
size_t n0 = 0, n1 = t->branches.size, i = 0, left;
size_t ancestor;
size_t byte, key_byte = 0, bit = 0;
assert(t && key && result);
if(!t->leaves.size) return assert(!n1), 0; /* Empty tree. */
assert(n1 + 1 == t->leaves.size); /* Full binary tree. */
while(n0 < n1) {
ancestor = t->branches.data[n0];
bit += trie_skip(ancestor);
/* `key` ends at an internal branch; '\0' is part of `key`. */
for(byte = bit >> 3; key_byte < byte; key_byte++)
if(key[key_byte] == '\0') return 0;
left = trie_left(ancestor);
if(!trie_is_bit(key, bit++)) n1 = ++n0 + left;
else n0 += left + 1, i += left + 1;
}
assert(n0 == n1 && i < t->leaves.size);
*result = i;
return 1;
}
/** @return True if found the exact `key` in `t` and stored it's index in
`result`. */
static int param_get(const struct Trie *const t,
const char *const key, size_t *const result) {
return param_index_get(t, key, result)
&& !strcmp(t->leaves.data[*result], key);
}
/** @return `t` entry that matches trie bits of `key`, (ignoring the don't care
bits,) or null if either `key` didn't have the length to fully differentiate
more then one entry or the `trie` is empty. */
static Leaf index_get(const struct Trie *const t, const char *const key) {
size_t i;
return param_index_get(t, key, &i) ? t->leaves.data[i] : 0;
}
/** @return Exact match for `key` in `t` or null. */
static Leaf trie_get(const struct Trie *const t, const char *const key) {
size_t i;
return param_get(t, key, &i) ? t->leaves.data[i] : 0;
}
index_prefix
, supplied with a prefix
, returns a [low
, high
] for the index branches matching that prefix, and trie_prefix
wrapper.
/** In `t`, which must be non-empty, given a partial `prefix`, stores all leaf
prefix matches between `low`, `high`, only given the index, ignoring don't
care bits. @order \O(`prefix.length`) */
static void index_prefix(const struct Trie *const t, const char *const prefix,
size_t *const low, size_t *const high) {
size_t n0 = 0, n1 = t->branches.size, i = 0, left;
size_t branch;
size_t byte, key_byte = 0, bit = 0;
assert(t && prefix && low && high);
assert(n1 + 1 == t->leaves.size); /* Full binary tree. */
while(n0 < n1) {
branch = t->branches.data[n0];
bit += trie_skip(branch);
/* '\0' is not included for partial match. */
for(byte = bit >> 3; key_byte <= byte; key_byte++)
if(prefix[key_byte] == '\0') goto finally;
left = trie_left(branch);
if(!trie_is_bit(prefix, bit++)) n1 = ++n0 + left;
else n0 += left + 1, i += left + 1;
}
assert(n0 == n1);
finally:
assert(n0 <= n1 && i - n0 + n1 < t->leaves.size);
*low = i, *high = i - n0 + n1;
}
/** @return Whether, in `t`, given a partial `prefix`, it has found `low`,
`high` prefix matches. */
static int trie_prefix(const struct Trie *const t, const char *const prefix,
size_t *const low, size_t *const high) {
assert(t && prefix && low && high);
return t->leaves.size ? (index_prefix(t, prefix, low, high),
trie_is_prefix(prefix, t->leaves.data[*low])) : 0;
}
trie_add_unique
, insert key
, and trie_put
wrapper.
/** Add `datum` to `t`. Must not be the same as any key of trie; it does not
check for the end of the string. @return Success. @order \O(`t.size`)
@throws[ERANGE] Trie reached it's conservative maximum, which on machines
where the pointer is 64-bits, is 4.5T. On 32-bits, it's 1M.
@throws[realloc, ERANGE] */
static int trie_add_unique(struct Trie *const t, Leaf key) {
const size_t leaf_size = t->leaves.size, branch_size = leaf_size - 1;
size_t n0 = 0, n1 = branch_size, i = 0, left, bit = 0, bit0 = 0, bit1;
size_t *branch = 0;
const char *n0_key;
Leaf *leaf;
int cmp;
assert(t && key);
/* Empty special case. */
if(!leaf_size) return assert(!t->branches.size),
(leaf = leaf_array_new(&t->leaves)) ? *leaf = key, 1 : 0;
/* Redundant `size_t`, but maybe we will use it like Judy compression? */
assert(leaf_size == branch_size + 1);
/* Conservative maximally unbalanced trie. Reserve one more. */
if(leaf_size > TRIE_LEFT_MAX) return errno = ERANGE, 0;
if(!leaf_array_reserve(&t->leaves, leaf_size + 1)
|| !size_array_reserve(&t->branches, branch_size + 1)) return 0;
/* Branch from internal node. */
while(branch = t->branches.data + n0, n0_key = t->leaves.data[i], n0 < n1) {
for(bit1 = bit + trie_skip(*branch); bit < bit1; bit++)
if((cmp = trie_strcmp_bit(key, n0_key, bit)) != 0) goto insert;
bit0 = bit1;
left = trie_left(*branch) + 1; /* Leaves. */
if(!trie_is_bit(key, bit++)) trie_left_inc(branch), n1 = n0++ + left;
else n0 += left, i += left;
}
/* Branch from leaf. */
while((cmp = trie_strcmp_bit(key, n0_key, bit)) == 0) bit++;
insert:
assert(n0 <= n1 && n1 <= t->branches.size && n0_key && i <= t->leaves.size
&& !n0 == !bit0);
/* How many left entries are there to move. */
if(cmp < 0) left = 0;
else left = n1 - n0, i += left + 1;
/* Insert leaf. */
leaf = t->leaves.data + i;
memmove(leaf + 1, leaf, sizeof *leaf * (leaf_size - i));
*leaf = key, t->leaves.size++;
/* Insert branch. */
branch = t->branches.data + n0;
if(n0 != n1) { /* Split the skip value with the existing branch. */
const size_t branch_skip = trie_skip(*branch);
assert(branch_skip + bit0 >= bit + !n0);
trie_skip_set(branch, branch_skip + bit0 - bit - !n0);
}
memmove(branch + 1, branch, sizeof *branch * (branch_size - n0));
*branch = trie_branch(bit - bit0 - !!n0, left), t->branches.size++;
return 1;
}
/** Returns a boolean given two `Leaf`. Used for <fn:trie_put>. */
typedef int (*TrieBipredicate)(Leaf, Leaf);
/** Adds `key` to `t` and, if `eject` is non-null, stores the collided element,
if any, as long as `replace` is null or returns true.
@param[eject] If not-null, the ejected datum. If `replace` returns false, then
`*eject == datum`, but it will still return true.
@return Success. @throws[realloc, ERANGE] */
static int trie_put(struct Trie *const t, Leaf key,
Leaf *const eject, const TrieBipredicate replace) {
Leaf *match;
size_t i;
assert(t && key);
/* Add if absent. */
if(!param_get(t, key, &i)) {
if(eject) *eject = 0;
return trie_add_unique(t, key);
}
assert(i < t->leaves.size), match = t->leaves.data + i;
/* Collision policy. */
if(replace && !replace(*match, key)) {
if(eject) *eject = key;
} else {
if(eject) *eject = *match;
*match = key;
}
return 1;
}
index_remove
, removes a path from the root to a leaf, and wrapper trie_remove
.
/** @return Whether leaf index `i` has been removed from `t`. */
static int index_remove(struct Trie *const t, size_t i) {
size_t n0 = 0, n1 = t->branches.size, parent_n0, left;
size_t *parent, *twin; /* Branches. */
assert(t && i < t->leaves.size && n1 + 1 == t->leaves.size);
/* Remove leaf. */
if(!--t->leaves.size) return 1; /* Phase transition to empty. */
memmove(t->leaves.data + i, t->leaves.data + i + 1,
sizeof t->leaves.data * (n1 - i));
/* Traverse trie getting `parent` and `twin`. */
for( ; ; ) {
left = trie_left(*(parent = t->branches.data + (parent_n0 = n0)));
if(i <= left) { /* Pre-order binary search. */
if(!left) { twin = n0 + 1 < n1 ? t->branches.data + n0 + 1 : 0;
break; }
n1 = ++n0 + left;
trie_left_dec(parent);
} else {
if((n0 += left + 1) >= n1)
{ twin = left ? t->branches.data + n0 - left : 0; break; }
i -= left + 1;
}
}
/* Merge `parent` with `twin` before deleting `parent` branch. */
if(twin) /* fixme: There is nothing to guarantee this. */
assert(trie_skip(*twin) < TRIE_SKIP_MAX - trie_skip(*parent)),
trie_skip_set(twin, trie_skip(*twin) + 1 + trie_skip(*parent));
memmove(parent, parent + 1,
sizeof *t->branches.data * (--t->branches.size - parent_n0));
return 1;
}
/** @return Whether `key` has been removed from `t`. */
static int trie_remove(struct Trie *const t, const char *const key) {
size_t i;
assert(t && key);
return param_get(t, key, &i) && index_remove(t, i);
}
trie_graph
and supporting functions that make a GraphViz out of a trie.
/* Testing. */
/** Given `n` in `t` branches, calculate the right child branches. Used in
<fn:trie_graph>. @order \O(log `size`) */
static size_t trie_right(const struct Trie *const t, const size_t n) {
size_t remaining = t->branches.size, n0 = 0, left, right;
assert(t && n < remaining);
for( ; ; ) {
left = trie_left(t->branches.data[n0]);
right = remaining - left - 1;
assert(left < remaining && right < remaining);
if(n0 >= n) break;
if(n <= n0 + left) remaining = left, n0++;
else remaining = right, n0 += left + 1;
}
assert(n0 == n);
return right;
}
/** @return Given `n` in `t` branches, follows the internal nodes left until
it hits a branch. Used in <fn:trie_graph>. */
static size_t trie_left_leaf(const struct Trie *const t, const size_t n) {
size_t remaining = t->branches.size, n0 = 0, left, right, i = 0;
assert(t && n < remaining);
for( ; ; ) {
left = trie_left(t->branches.data[n0]);
right = remaining - left - 1;
assert(left < remaining && right < remaining);
if(n0 >= n) break;
if(n <= n0 + left) remaining = left, n0++;
else remaining = right, n0 += left + 1, i += left + 1;
}
assert(n0 == n);
return i;
}
/** Draw a graph of `t` to `fn` in Graphviz format. */
static void trie_graph_fp(const struct Trie *const t, FILE *fp) {
size_t i, n;
assert(t && fp);
fprintf(fp, "digraph {\n"
"\trankdir = TB;\n"
"\tnode [shape = record, style = filled];\n"
"\tTrie [label = \"{\\Trie"
"\\l|size: %lu\\l}\"];\n", (unsigned long)t->leaves.size);
fprintf(fp, "\tnode [shape = none, fillcolor = none];\n");
for(n = 0; n < t->branches.size; n++) {
const size_t branch = t->branches.data[n];
const size_t left = trie_left(branch), right = trie_right(t, n);
fprintf(fp, "\tbranch%lu [label = \"%lu\"];\n"
"\tbranch%lu -> ", (unsigned long)n, trie_skip(branch),
(unsigned long)n);
if(left) fprintf(fp, "branch%lu [style = dashed]; // left branch\n",
(unsigned long)n + 1);
else fprintf(fp, "leaf%lu [style = dashed]; // left leaf\n",
(unsigned long)trie_left_leaf(t, n));
fprintf(fp, "\tbranch%lu -> ", (unsigned long)n);
if(right) fprintf(fp, "branch%lu; // right branch\n",
(unsigned long)n + left + 1);
else fprintf(fp, "leaf%lu; // right leaf\n",
(unsigned long)trie_left_leaf(t, n) + left + 1);
}
/* This must be after the branches, or it will mix up the order. Since they
have been referenced, one needs explicit formatting? */
for(i = 0; i < t->leaves.size; i++)
fprintf(fp, "\tleaf%lu [label = \"%s\", shape = box, "
"fillcolor = lightsteelblue, style = filled];\n", (unsigned long)i,
t->leaves.data[i]);
fprintf(fp, "\tnode [color = red];\n"
"}\n");
}
/** Graphs `t` in `Graphviz` format in the file `fn`.
@return Success. @throws[fopen, EDOM] */
static int trie_graph(const struct Trie *const t, const char *const fn) {
FILE *fp;
assert(t && fn);
if(!(fp = fopen(fn, "w"))) return 0;
trie_graph_fp(t, fp);
return fclose(fp) ? errno ? 0 : (errno = EDOM, 0) : 1;
}
main
that runs some tests and outputs GraphViz files in graph/
if you have it.
int main(void) {
const char *const words[] = {
"wryer","posturists","nonanswers","collations","renovating","view","kiddingly",
"lineman","elating","convocate","tonically","steradians","disdained",
"hypervigilance","annexational","scabiosas","pinfishes","disinhibited",
"coryphenes","omohyoid","mongoes","tarries","oestrin","decillion","tutorships",
"marriers","photocomposer","finesse","kosmos","jipyapa","nortenos","laminator",
"outgives","lampshades","inhumation","syringes","deiced","herpetologists",
"granulomata","footgear","stemless","lallygagging","expectation","ecus",
"jetplane","pusher","whiffings","bouffes","majorships","unintellectual",
"unhouses","pumy","convalesces","anticodon","rubicelle","simmering","suborned",
"guacharo","cassata","shedlike","chelating","limbering","detect","dandiacal",
"reedify","pegmatite","undignifies","jawbox","feudatories","opticist",
"overmany","synthon","dehisce","volens","nonself","drams","deluded","heisting",
"embosoms","lambda","growthiest","graphing","conepatl","disinclining",
"diffraction","phytotron","klezmorim","greenmailer","kyogens","daydreaming",
"canephors","uncleanlinesses","absinths","headmost","persists","sexiness",
"unanchoring","colickier","aquatinter","absentee","excimer","snakeskin",
"outtook","sybil","aldolizations","boundaries","hypochondrias","whitewashers",
"noninterests","evacuant","fogbow","bemean","nontaxable","bleacheries",
"preserve","puisny","pyrheliometers","peytrals","clypeus","joists","oxygenized",
"plyer","satinwoods","tashed","retailoring","micropuncture","chyle",
"overruffing","allots","pyrosises","squinched","misrelies","rheophil",
"tracheostomy","mischoices","boogymen","manyattas","honestly","indicters",
"cragginesses","epitaphing","tribulate","dishable","concealed","amis","annats",
"trompes","witchetties","napped","pusled","harewoods","napless","deadener",
"besat","overprescribing","liberates","summability","rumrunner","kamichi",
"lymphomas","wellborn","choughs","pudendous","petrochemistry","baboonish",
"hideousness","chanfron","tinnituses","mousts","drill","harborage","bogey",
"trabeated","choofing","utmosts","hypocentral","imidazoles","demology",
"evictees","rotal","axiological","ectozoans","teazes","taleful",
"interchangeable","helmsmanships","unhattings","overruff","playwear","tripart",
"neuropils","conspirers","outthrown","leucotomy","engilt","declarers","pandura",
"agony","saltnesses","saucy","begalling","misinter","regularize","zidovudines",
"ripsaw","hydrogenations","chivvying","disreputability","twirler","germaine",
"bullishnesses","crural","dognapped","flatmate","triceratopses","sighlike",
"heirdoms","maturities","frigged","zoechrome","snottinesses","arefy","bingled",
"scission","byrl","joky","insatiatenesses","tituped","latchets","streaky",
"dualin","perceptible","almudes","reproachfulness","seclude","quintes",
"lawbreakers","odalique","hosepipes","sulfadiazines","spool","chironomies",
"untillable","foreword","marly","cytometries","oxer","carbazoles","adventives",
"epigeic","appropriative","squeezabilities","pomposity","amorists","peplum",
"biogeographical","insertion","neonatal","fleers","omegas","preens","reshaven",
"chevy","gubbah","cachexy","syncope","skewed","hospitalities","cinematic",
"worrels","dispursed","tainted","divinator","impedance","intertexts","whiss",
"synonymical","chromize","lumpiest","hyalonema","entender","itinerates",
"saccharums","exclusives","jo","resurfaced","pompousness","doctrine","dropped",
"jaygees","deputised","appealed","complain","ancientry","otalgy","ferryboats",
"frowzier","allegiance","encalmed","fattens","plasmin","literalized",
"insupportable","approbations","lenity","coexerts","fascinators","medullae",
"taborers","phylloxera","wadings","apostatize","fippences","anecdotes",
"speechifies","impassible","superstrike","unrifled","runbacks","shampoos",
"quinoidal","preformatted","honchos","gigawatt","triodes","lophophores",
"gargarising","hydrological","undeifying","distinctness","cravening",
"phagocytosing","leopardesses","careless","baetyl","showmanship","lankiness",
"racketers","engrossed","hakes","treatment","abstractedly","wirinesses",
"unnilquadiums","greasier","mynas","inexpertness","mooner","digesting",
"rhabdoms","actioners","lauans","semanteme","trapesings","rabatments","maimers",
"heathier","amebean","gainer","diktat","redsear","spoilages","kitties",
"procaryotes","labroids","antiobscenities","stanchels","enjoiner","notoriety",
"pumicating","stupendousness","fidgeters","fecklessly","cawk","boraces",
"technologizing","cycloliths","biffy","penduline","tepefied","infernally",
"subdorsal","confectionary","slenderize","unearthed","camorrista","outpressing",
"unworldly","frankpledges","leveeing","polysyndetons","aguizing","semantra",
"neutralization","hypopharynges","multiwall","spellbinder","parenchymal",
"waiving","happily","anklebones","obligees","monoecies","blindage","bodyshells",
"asperse","cotyledons","forekings","fico","subclaim","chorus","homesteaders",
"prometals","transudates","glamourless","sphygmographs","traversal",
"thimbleriggers","shaken","undefaced","jeopardy","enheartening","dentural",
"fluorides","loganias","gladsomeness","locule","oestrones","militantnesses",
"skrieghs","smouldry","crower","pellicles","sapucaias","underuses","reexplored",
"chlamydia","tragediennes","levator","accipiter","esquisses","intentnesses",
"julienning","tetched","creeshing","anaphrodisiacs","insecurities","tarpons",
"lipotropins","sinkage","slooshes","homoplastic","feateous"},
*const extra[] = { "foo", "bar", "baz", "qux", "quxx", "a" };
const size_t words_size = sizeof words / sizeof *words,
extra_size = sizeof extra / sizeof *extra;
size_t start, end, i;
struct Trie t;
const char *leaf, *eject;
const char *word, *res0, *res1;
int success = EXIT_FAILURE;
if(!trie_init(&t, words, words_size)) goto catch;
trie_graph(&t, "graph/trie0.gv");
word = "lambda";
res0 = index_get(&t, word);
res1 = trie_get(&t, word);
printf("index get: %s --> %s\n"
"exact get: %s --> %s\n", word, res0, word, res1);
word = "slithern";
res0 = index_get(&t, word);
res1 = trie_get(&t, word);
printf("index get: %s --> %s\n"
"exact get: %s --> %s\n", word, res0, word, res1);
word = "pe";
printf("index prefix: %s --> { ", word);
index_prefix(&t, word, &start, &end);
for(i = start; i <= end; i++)
printf("%s%s", i == start ? "" : ", ", t.leaves.data[i]);
printf(" }.\n"
"exact prefix: %s --> { ", word);
if(trie_prefix(&t, word, &start, &end)) for(i = start; i <= end; i++)
printf("%s%s", i == start ? "" : ", ", t.leaves.data[i]);
printf(" }.\n");
word = "qz";
index_prefix(&t, word, &start, &end);
printf("index prefix: %s --> { ", word);
for(i = start; i <= end; i++)
printf("%s%s", i == start ? "" : ", ", t.leaves.data[i]);
printf(" }.\n"
"exact prefix: %s --> { ", word);
if(trie_prefix(&t, word, &start, &end)) for(i = start; i <= end; i++)
printf("%s%s", i == start ? "" : ", ", t.leaves.data[i]);
printf(" }.\n");
assert(t.leaves.size == words_size);
for(i = 0; i < extra_size; i++)
if(!trie_put(&t, extra[i], &eject, 0)) goto catch;
trie_graph(&t, "graph/trie1.gv");
assert(t.leaves.size == words_size + extra_size);
for(i = 0; i < words_size; i++)
leaf = trie_get(&t, words[i]), assert(leaf && leaf == words[i]);
for(i = 0; i < extra_size; i++)
leaf = trie_get(&t, extra[i]), assert(leaf && leaf == extra[i]);
for(i = 0; i < extra_size; i++) {
const int is = trie_remove(&t, extra[i]);
assert(is);
}
trie_graph(&t, "graph/trie2.gv");
assert(t.leaves.size == words_size);
for(i = 0; i < words_size; i++)
leaf = trie_get(&t, words[i]), assert(leaf && leaf == words[i]);
for(i = 0; i < extra_size; i++)
leaf = trie_get(&t, extra[i]), assert(!leaf);
success = EXIT_SUCCESS;
goto finally;
catch:
perror("trie");
finally:
trie_(&t);
return success;
}
Analysis
Random garbage words of a maximum of 64 bytes.
- X-axis is a log scale. Time per element is numerically unstable on low numbers, and includes set-up time.
- In the original paper, this type of trie is a state machine; it has evolved, but I've set it to be an array. This means it's contiguous in-order, but dominated by
O(n)
modifications at largen
with the dynamic array operations. - A trie is competitive with a hash for lookup up to a point; this is especially convenient when modification is done rarely.
- The implementation of a hash table is separate-chaining with singly-linked-lists, load factor
ln 2
(0.69) that has power-of-two resizes; I've copied the words directly into the linked-list structure itself so we don't have an extra redirect. Modification and lookup speed is amortisedO(1)
, but that does not include cache effects and the 32-byte FNV-1a one-at-a-time string hash, which is the liming factor in this case. On English words with have an average of 5 letters, it's even faster, becoming faster then the trie at about 10-20 elements. - With a trie, one doesn't need to worry about collisions, therefore one's type may be simpler then a hash.
- The
ARRAYINIT
andTRIEINIT
lines are very close andTRIEINIT
is always above. This is expected because they both doqsort
and then the trie does more stuff. ARRAYINIT
is oneqsort
amortised alongn
;ARRAYLOOK
isbsearch
for each entry.
Questions
Adding one-at-a-time is way less efficient than initialising it all at once. I don't exactly know what is the run-time of this? Does the master theorem even apply? How could we improving memory access and speed for initialisation?
Before I had a fixed 512-byte limit on bit
. Now I use skip
, which can expand to the limits of the computer, but only 512 bytes between levels on the tree. I assert that this holds, but really I should check and not allow it to get in an inconsistent state. This is a worry, for instance if one tries to use this trie for Ziv-Lempel compression or genomic data it could easily have this limit. What if I merge two skip
values on delete and it overflows the 12-bits? Should I have an undo function?
Finally, this code is very long; any tips on reducing or eliminating sections would be appreciated.
n
small lookups (comparable, but faster.) I edited to show the details of the hash I used, thanks. If one doesn't need the order, prefix matching, and smaĺler size, it's hard to justify the extra code vs a simple hash table. \$\endgroup\$