InvertedIndex
Defined in: packages/data/src/multimap/inverted-index.ts:23
A token-to-documents index: the structure behind full-text search.
An IMultimap<Token, DocId> read backwards — instead of “what does this
document contain”, it answers “which documents contain this”. That inversion
is what turns a scan over every document into a lookup plus a set
intersection.
Postings are a Set per token, so indexing the same token twice for one
document is idempotent and hasEntry is O(1). Tokenisation is the caller’s
job: this indexes whatever tokens it is handed, which keeps stemming,
case-folding and language rules out of the data structure.
Time complexity: O(1) for add, has and hasEntry; search is O(smallest
posting list × number of tokens), because it intersects starting from the
rarest token; deleteDocument is O(tokens indexed).
Type Parameters
Section titled “Type Parameters”Token
The token type, usually string.
DocId
The document identifier type.
Implements
Section titled “Implements”IMultimap<Token,DocId>
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new InvertedIndex<
Token,DocId>(iterable?):InvertedIndex<Token,DocId>
Defined in: packages/data/src/multimap/inverted-index.ts:30
Parameters
Section titled “Parameters”iterable?
Section titled “iterable?”Iterable<readonly [Token, DocId], any, any>
Returns
Section titled “Returns”InvertedIndex<Token, DocId>
Methods
Section titled “Methods”[iterator]()
Section titled “[iterator]()”[iterator]():
Iterator<readonly [Token,DocId]>
Defined in: packages/data/src/multimap/inverted-index.ts:38
Returns
Section titled “Returns”Iterator<readonly [Token, DocId]>
Implementation of
Section titled “Implementation of”add(
token,docId):void
Defined in: packages/data/src/multimap/inverted-index.ts:73
O(1). Idempotent: indexing the same pair twice changes nothing.
Parameters
Section titled “Parameters”Token
DocId
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”addAll()
Section titled “addAll()”addAll(
token,docIds):void
Defined in: packages/data/src/multimap/inverted-index.ts:99
O(m) in the number of documents.
Parameters
Section titled “Parameters”Token
docIds
Section titled “docIds”Iterable<DocId>
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”clear()
Section titled “clear()”clear():
void
Defined in: packages/data/src/multimap/inverted-index.ts:47
Removes all elements from the collection.
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”count()
Section titled “count()”count():
number
Defined in: packages/data/src/multimap/inverted-index.ts:43
The total number of (token, document) postings. O(1).
Returns
Section titled “Returns”number
Implementation of
Section titled “Implementation of”countFor()
Section titled “countFor()”countFor(
token):number
Defined in: packages/data/src/multimap/inverted-index.ts:200
O(1).
Parameters
Section titled “Parameters”Token
Returns
Section titled “Returns”number
Implementation of
Section titled “Implementation of”delete()
Section titled “delete()”delete(
token):number
Defined in: packages/data/src/multimap/inverted-index.ts:132
Removes token and every posting under it. O(p) in the posting list.
Parameters
Section titled “Parameters”Token
Returns
Section titled “Returns”number
How many postings were removed.
Implementation of
Section titled “Implementation of”deleteDocument()
Section titled “deleteDocument()”deleteDocument(
docId):boolean
Defined in: packages/data/src/multimap/inverted-index.ts:175
Removes a document from every posting list it appears in.
O(t) in the number of tokens that document was indexed under — the reverse map is carried precisely so this is not a scan of the whole index.
Parameters
Section titled “Parameters”DocId
Returns
Section titled “Returns”boolean
true if the document was indexed.
deleteEntry()
Section titled “deleteEntry()”deleteEntry(
token,docId):boolean
Defined in: packages/data/src/multimap/inverted-index.ts:150
O(1).
Parameters
Section titled “Parameters”Token
DocId
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”documentCount()
Section titled “documentCount()”documentCount():
number
Defined in: packages/data/src/multimap/inverted-index.ts:59
The number of distinct documents indexed. O(1).
Returns
Section titled “Returns”number
documentIds()
Section titled “documentIds()”documentIds():
IterableIterator<DocId>
Defined in: packages/data/src/multimap/inverted-index.ts:210
Every indexed document identifier, in first-indexed order.
Returns
Section titled “Returns”IterableIterator<DocId>
entries()
Section titled “entries()”entries():
IterableIterator<readonly [Token,DocId]>
Defined in: packages/data/src/multimap/inverted-index.ts:215
Every (token, document) posting, grouped by token.
Returns
Section titled “Returns”IterableIterator<readonly [Token, DocId]>
Implementation of
Section titled “Implementation of”get(
token):IterableIterator<DocId>
Defined in: packages/data/src/multimap/inverted-index.ts:64
The documents containing token, in first-indexed order.
Parameters
Section titled “Parameters”Token
Returns
Section titled “Returns”IterableIterator<DocId>
Implementation of
Section titled “Implementation of”has(
token):boolean
Defined in: packages/data/src/multimap/inverted-index.ts:118
O(1). Whether any document holds token.
Parameters
Section titled “Parameters”Token
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”hasEntry()
Section titled “hasEntry()”hasEntry(
token,docId):boolean
Defined in: packages/data/src/multimap/inverted-index.ts:123
O(1).
Parameters
Section titled “Parameters”Token
DocId
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”index()
Section titled “index()”index(
docId,tokens):void
Defined in: packages/data/src/multimap/inverted-index.ts:111
Indexes one document under every one of its tokens — the natural way in.
O(t) in the number of tokens. Adds to whatever is already indexed for
docId; call deleteDocument first to re-index from scratch.
Parameters
Section titled “Parameters”DocId
tokens
Section titled “tokens”Iterable<Token>
Returns
Section titled “Returns”void
keyCount()
Section titled “keyCount()”keyCount():
number
Defined in: packages/data/src/multimap/inverted-index.ts:54
The number of distinct tokens indexed. O(1).
Returns
Section titled “Returns”number
Implementation of
Section titled “Implementation of”keys()
Section titled “keys()”keys():
IterableIterator<Token>
Defined in: packages/data/src/multimap/inverted-index.ts:205
Every indexed token, in first-indexed order.
Returns
Section titled “Returns”IterableIterator<Token>
Implementation of
Section titled “Implementation of”search()
Section titled “search()”search(
tokens):IterableIterator<DocId>
Defined in: packages/data/src/multimap/inverted-index.ts:230
Documents containing every token — a conjunctive query.
Intersects from the rarest token outwards, so the work is bounded by the
shortest posting list rather than the longest. An empty tokens matches
nothing, not everything: “all of no conditions” is not a useful search.
Parameters
Section titled “Parameters”tokens
Section titled “tokens”Iterable<Token>
Returns
Section titled “Returns”IterableIterator<DocId>
searchAny()
Section titled “searchAny()”searchAny(
tokens):IterableIterator<DocId>
Defined in: packages/data/src/multimap/inverted-index.ts:260
Documents containing any of the tokens — a disjunctive query.
Parameters
Section titled “Parameters”tokens
Section titled “tokens”Iterable<Token>
Returns
Section titled “Returns”IterableIterator<DocId>