Storing and Indexing Text
<div class="MsoNormal">Document indexing</div>
Running text
<div
class="MsoNormal">Conventional inverted indexes for text</div>
- postings lists: mapping terms to occurrences (precise locations vs. whole documents)
- naïvely, each distinct word in the corpus is a term
- keep a B-tree or hash table (or other table structure) of terms
- for each term, list of (document ids) or (document id, {offsets}) pairs
- postings lists typically kept in increasing order
- combining
indexes (boolean queries, proximity queries,
phrases)
- list merging
- efficient merging algorithms involve skipping unmatchable entries
- not every word need be a separate term
- stop words
- word stemming
- authority lists (thesauri)
<div
class="MsoNormal">Suffix trees and suffix arrays</div>
- For
example, indexing every word in this sentence yields the 12 strings:
For example, indexing every word in this sentence yields the 12 strings:
example, indexing every word in this sentence yields the 12 strings:
indexing every word in this sentence yields the 12 strings:
every word in this sentence yields the 12 strings:
word in this sentence yields the 12 strings:
in this sentence yields the 12 strings:
this sentence yields the 12 strings:
sentence yields the 12 strings:
yields the 12 strings:
the 12 strings:
12 strings:
strings:
- store references
to each index point in trie or ordered array (or any
other table structure)
- index points need not be at all word starts, nor only at word starts
- every character, or every syllable start, could be an index point
- some words could be omitted or some special characters could signal index points
- matching phrases can be very efficient
- therefore highly suitable for indexing Chinese and other unsegmented languages
- note: if index points are word starts, a suffix array can be considered as a concatenation of postings lists ordered alphabetically rather than by position
Text structure
<div class="MsoNormal">Pointer-based encoding</div>
- conventional tree representation
- pointer to first child and to next sibling
- parent pointer
- separate pointers for attributes, namespaces, etc.
<div class="MsoNormal">Interval encoding
for structured text</div>
- region indexes (for a span of text)
- similar
to postings lists, but storing <start,end>
pairs
- for
containment checking, any interval numbering will suffice as long as
<s1,
e1> nested within <s2,e2> iff s1 >= s2
and e1 <= e2
-
alternative: <preorder index, postorder index, depth>
Storing
and indexing semistructured data
Recall OEM structure
- OIDs can be any form of persistent address where node
information can be found
- Simple
storage of an edge-labelled digraph:
o
symbol table mapping entry point names to OIDs
o
for each sink node, store the data type and the
atomic value
o
for each compound object, store set of
<label, targetOID> pairs representing outgoing
edges (e.g., keep a table mapping edge label to set of target nodes)
o
finds atomic values rapidly
o
one index per data type
o
complication: type conversions
(e.g., ... spy where number > 5)
- Navigating
edges in reverse
o
too much space and update cost to duplicate the
graph
o
for each node, store set of OIDs
from which at least one edge leads to this node
o
need to verify that edges have correct labels
o
mapping each path starting with an entry point
name to the set of OIDs for target nodes (N.B. this
is the same information as DataGuide)
o
could keep just a
subset (fixed length paths? commonly used paths?)
o
index of subpaths (which ones? storing what info?)
o
possible application of suffix arrays?
References
and related reading
