Class

PurpleTrie

Description [src] 

final class Purple.Trie : GObject.Object {
  /* No available fields */
}

A PurpleTrie is a structure for quick searching of multiple phrases within a text. It’s intended for repeated searches of the same set of patterns within multiple source texts (or a single, big one).

It’s preparation time is O(p), where p is the total length of searched phrases. In current implementation, the internal structure is invalidated after every modification of the PurpleTrie‘s contents, so it’s not efficient to do alternating modifications and searches. Search time does not depend on patterns being stored within a trie and is always O(n), where n is the size of a text.

Its main drawback is a significant memory usage - every internal trie node needs about 1kB of memory on 32-bit machine and 2kB on 64-bit. Fortunately, the trie grows slower when more words (with common prefixes) are added. We could avoid invalidating the whole tree when altering it, but it would require figuring out, how to update longest_suffix fields in satisfying time.

Ancestors

Constructors

purple_trie_new

Creates a new trie.

Functions

purple_trie_multi_find

Processes src and replaces all occuriences of words added to tries in list tries. Entries added to tries on the beginning of the list have higher priority, than ones added further.

purple_trie_multi_replace

Processes src and replaces all occuriences of words added to tries in list tries. Entries added to tries on the beginning of the list have higher priority, than ones added further.

Instance methods

purple_trie_add

Adds a word to the trie. Current implementation doesn’t allow for duplicates, so please avoid adding those.

purple_trie_find

Processes src string and finds all occuriences of words added to trie. It’s O(strlen(src)), if find_cb runs in O(1).

purple_trie_get_reset_on_match

Checks, if the trie will reset its internal state after every match.

purple_trie_get_size

Returns the number of elements contained in the PurpleTrie.

purple_trie_remove

Removes a word from the trie. Depending on used memory pool, this may not free allocated memory (that will be freed when destroying the whole collection), so use it wisely. See #purple_memory_pool_free.

purple_trie_replace

Processes src string and replaces all occuriences of words added to trie. It’s O(strlen(src)), if replace_cb runs in O(strlen(word)) and PurpleTrie:reset-on-match is set.

purple_trie_set_reset_on_match

Enables or disables a feature of resetting trie’s state after every match. When enabled, it will not search for overlapping matches.

Methods inherited from GObject (43)

Please see GObject for a full list of methods.

Properties

Purple.Trie:reset-on-match
No description available.

Signals

Signals inherited from GObject (1)
GObject.Object::notify

The notify signal is emitted on an object when one of its properties has its value set through g_object_set_property(), g_object_set(), et al.

Class structure 

struct PurpleTrieClass {
  GObjectClass parent_class;
  
}
No description available.
Class members
parent_class 
GObjectClass
  No description available.