File trie.lua
Functions
insertFileCummulative (trie, file) | Insert into a trie all sub-strings starting at position 1 of the lines read from a file. |
insertFileFull (trie, file) | Insert into a trie all sub-strings of the lines read from a file. |
insertFileSingle (trie, file) | Insert into a trie all plain lines of a file. |
insertListCummulative (trie, list) | Insert into a trie all sub-strings starting at position 1 of a list of strings. |
insertListFull (trie, list) | Insert into a trie all sub-strings of a list of strings. |
insertListSingle (trie, list) | Insert into a trie a list of plain strings. |
insertStringCummulative (trie, s, value) | Insert into a trie all sub-strings of a string starting at position 1 (there are n = len(s) of them). |
insertStringFull (trie, s, value) | Insert into a trie all sub-strings of a string (there are n = len(s) * ( len(s) + 1 ) / 2 of them). |
insertStringSingle (trie, s, value) | Insert into a trie a plain string (not taking sub-strings into account) with an associated value. |
matchStringCummulative (trie, s) | Match all sub-strings of a string starting at position 1 against a trie. |
matchStringFull (trie, s) | Match all sub-strings of a string against a trie. |
matchStringSingle (trie, s) | Search for a plain string in a trie. |
newTrieNode () | Create a new empty trie node. |
showTrie (trie, compact) | Print all strings stored in a trie. |
showTrie__ (node, s, compact) | This function recursively advances through the trie. |
Functions
- insertFileCummulative (trie, file)
-
Insert into a trie all sub-strings starting at position 1 of the lines read from a file.
Parameters:
-
trie
: A trie to insert strings into. -
file
: File to read from. All strings are associated with a value true.
-
- insertFileFull (trie, file)
-
Insert into a trie all sub-strings of the lines read from a file.
Parameters:
-
trie
: A trie to insert strings into. -
file
: File to read from. All strings are associated with a value true.
-
- insertFileSingle (trie, file)
-
Insert into a trie all plain lines of a file.
Parameters:
-
trie
: A trie to insert lines into. -
file
: File to read from. All strings are associated with a value true.
-
- insertListCummulative (trie, list)
-
Insert into a trie all sub-strings starting at position 1 of a list of strings.
Parameters:
-
trie
: A trie to insert strings into. -
list
: A list with strings. All sub-strings are associated with a value true.
-
- insertListFull (trie, list)
-
Insert into a trie all sub-strings of a list of strings.
Parameters:
-
trie
: A trie to insert strings into. -
list
: A list with strings. All sub-strings are associated with a value true.
-
- insertListSingle (trie, list)
-
Insert into a trie a list of plain strings.
Parameters:
-
trie
: A trie to insert strings into. -
list
: A list with strings. All strings are associated with a value true.
-
- insertStringCummulative (trie, s, value)
-
Insert into a trie all sub-strings of a string starting at position 1 (there are n = len(s) of them). Example: insert(t, "Hello", value) inserts strings "H", "He", "Hel", "Hell", "Hello" with associated values value[1], value[2], ..., value[5] into trie t. Any existing values are replaced.
Parameters:
-
trie
: The trie object to insert the string into. -
s
: The string to insert. -
value
: A table of length len(s), containing non-nil values associated with the sub-strings. Alternatively, value can be any non-table expression. This value is then associated with all sub-strings.
-
- insertStringFull (trie, s, value)
-
Insert into a trie all sub-strings of a string (there are n = len(s) * ( len(s) + 1 ) / 2 of them). Example: insert(t, "Hello") inserts strings "H", "He", "Hel", "Hell", "Hello" with associated values value[1][1], value[1][2], ..., value[1][5], strings "e", "el", "ell", "ello" with associated values value[2][1], value[2][2], ..., value[2][4], etc into trie t. Any existing values will be replaced. If there are identical sub-strings, the final associated value is not determined.
Parameters:
-
trie
: The trie object to insert the string into. -
s
: The string to insert. -
value
: A triangular table of length len(s), containing tables of non-nil values associated with the sub-strings. Alternatively, value can be a non-table type expression. This value is then associated with all sub-strings.
-
- insertStringSingle (trie, s, value)
-
Insert into a trie a plain string (not taking sub-strings into account) with an associated value. An existing value is replaced.
Parameters:
-
trie
: The trie object to insert the string into. -
s
: The string to insert. -
value
: A non-nil value associated with the string.
-
- matchStringCummulative (trie, s)
-
Match all sub-strings of a string starting at position 1 against a trie.
Parameters:
-
trie
: The trie object. -
s
: String to search for.
Return value:
- If sub-strings have been identified, return a list with values associated with the matching strings. If no matching sub-strings have been identified, return nil.
-
- matchStringFull (trie, s)
-
Match all sub-strings of a string against a trie.
Parameters:
-
trie
: The trie object. -
s
: String to search for.
Return value:
- If sub-strings have been identified, return a list with values associated with the matching strings. If no matching sub-strings have been identified, return nil.
-
- matchStringSingle (trie, s)
-
Search for a plain string in a trie.
Parameters:
-
trie
: The trie object. -
s
: String to search for.
Return value:
- If the strings is found, return the associated value. If the string could not be found, return nil.
-
- newTrieNode ()
-
Create a new empty trie node. An empty node is a table { next = {}, value = nil }.
Return value:
- An empty trie node.
- showTrie (trie, compact)
-
Print all strings stored in a trie. An exclamation mark indicates identified strings.
Parameters:
-
trie
: The trie object to show. -
compact
: boolean flag: Print strings in compact format?
See also:
-
- showTrie__ (node, s, compact)
-
This function recursively advances through the trie. It prints all characters valid at a node. An underscore indicates the end of an identified string.
Parameters:
-
node
: A trie object. -
s
: String of characters preceeding the current node. -
compact
: boolean flag: Print patterns in compact format?
Usage:
Internal function.
See also:
-