Changes between Version 7 and Version 8 of FlintTermListTable

Timestamp:

2008-08-21 12:18:18 (2 years ago)

Author:

olly

Comment:

Update for 1.0.7

FlintTermListTable

@@ -5 +5 @@
 == Key Format ==
 
-Quartz stores the key as: lsb ... msb of the docid, until all remaining bytes are zero
+{{{
+pack_uint_preserving_sort(docid)
+}}}
 
-Flint currently uses pack_uint_preserving_sort(docid) - this takes one extra byte compared to
+This takes one extra byte compared to
 Quartz, but means that when appending documents to a database, the insert is always
 in the same place (at the "end" of the table).  This is faster, and produces a more compact
 database without a separate compaction step.
 
-(The eventual plan is to subclass the compare routine so we can store the key
-as compactly as Quartz does but keep the improved sort order.)
+The plan for Chert or later is to subclass the compare routine so we can store the key
+as compactly as Quartz did but keep the improved sort order.
 
 == Tag Format ==
 
-The tag is formed exactly as in Quartz, but may be stored compressed by zlib, which gives a
+If the document isn't indexed by any terms, then the tag is empty.
+
+Otherwise, the tag starts:
+
+{{{
+pack_uint(doclen) +
+pack_uint(termlist_size)
+}}}
+
+Optionally followed by a {{{'0'}}} character (only required if the first term is
+48 characters long!)
+
+Followed by:
+
+{{{
+char(term.size()) +
+term +
+pack_uint(wdf)
+}}}
+
+Followed by zero or more entries, each of which can take one of two forms
+(the first is used when {{{packed < 256}}}):
+
+{{{
+char(packed) +
+char(term.size() - reuse) +
+term.substr(reuse)
+}}}
+
+{{{
+char(reuse) +
+char(term.size() - reuse) +
+term.substr(reuse) +
+pack_uint(wdf)
+}}}
+
+In the above, reuse is the length of the longest common prefix between
+this term and the previous one, and packed is:
+
+{{{
+(wdf + 1) * (prev_term.size() + 1) + reuse
+}}}
+
+Care is needed to avoid the above overflowing - in reality we first check
+that {{{wdf < 127}}} as packed will never fit in a byte if it isn't.
+
+To unpack, we know that {{{reuse <= prev_term.size()}}}
+if this condition doesn't hold, we know we must have the first form and unpack
+it thus:
+
+{{{
+reuse = value % (prev_term.size() + 1);
+wdf = (value / (prev_term.size() + 1)) - 1;
+}}}
+
+The tag may be stored compressed by zlib, which gives a
 decent amount of extra compression.  Very small tags (less than the minimum size
 of compressed output) are stored uncompressed.
 
-Quartz first stores pack_uint(document length), and the number of
-entries in the termlist (this value is stored for quick access - it
-could also be determined by running through the termlist).  It then stores the
-entries, in sorted order.  For the first term, we store:
-termname.length() (in a byte) then the termname, then pack_uint(wdf).
-For subsequent terms, we store: length of the common prefix of this termname
-and the previous one (in a byte), length of string to add to this prefix
-(in a byte) then the string to add, then pack_uint(wdf).
+-----
 
-This is correct
-prior to 0.8.0, 0.8.0 and later will try to squeeze the wdf into the common
-prefix byte - we know that the prefix reuse length is <= the length of the
-previous term, so if this value is >, we take:
-reuse_length = value % (prev_term_length + 1)
-wdf = (value / (prev_term_length + 1)) - 1
-and then we omit the byte which would otherwise store pack_uint(wdf) for this term.
+For chert or later, we could use a similar packing to the above, but combine
+{{{reuse}}} and {{{term.size() - reuse}}} into a two byte value consisting of
+either:
 
-The proposed change is to use a similar packing to that used by quartz in 0.8.0 and
-later, but to combine the reuse_length and
-add_length into a two byte value consisting of either:
+{{{
+reuse + (prev_term.size() + 1) * (term.size() - reuse)
+}}}
 
- * reuse_length + (prev_term_length + 1) * (add_length)
-
- * reuse_length + (prev_term_length + 1) * add_length + (prev_term_length + 1) * (256 - prev_term_length) * wdf
+{{{
+reuse + (prev_term.size() + 1) * (term.size() - reuse) + (prev_term.size() + 1) * (256 - prev_term.size()) * wdf
+}}}
 
 This will allow the wdf byte to be omitted more often.