Differences

This shows you the differences between two versions of the page.

--- notes:trie [2025/08/11 20:09] – smj-edison
+++ notes:trie [2025/08/11 20:11] (current) – smj-edison
@@ Line 1: / Line 1: @@
-===== Part 1: the Trie =====
+===== Moved to =====
-A Trie is the data structure that underlies Folk's database. It is the index to all Wishes, Claims, and Whens. The Trie works by inserting and removing Clauses. A Clause is an array of space-seperated words, with each word being called a Term. An example Clause, "the sky is blue", would become ["the", "sky", "is", "blue"].
+Moved to [[notes:internals:trie|Part 1: the Trie]]
-Let's insert the Clause into the Trie and see what happens:
-{{notes:pxl_20250811_192744566.jpg?200|}}
-As you can see, the Clause has been turned into a set of nodes in the Trie. Let's try inserting another Clause, "the sky has clouds":
-{{notes:pxl_20250811_193540816.jpg?200|}}
-A Trie is just a tree, with each level being one word*.
-We've now covered inserting, but what about querying? Let's try querying for "the sky has clouds". We'll do this by comparing each Term of the query against the Trie:
-{{notes:trie-lookup-level-1.jpg?400|}}
-{{notes:trie-lookup-level-2.jpg?400|}}
-{{notes:trie-lookup-level-3-part-1.jpg?400|}}
-{{notes:trie-lookup-level-3-part-2.jpg?400|}}
-{{notes:trie-lookup-level-4.jpg?400|}}
-Notice how we never had to check "blue", since that was on a separate branch of the Trie. When there's thousands of nodes, the Trie effectively trims irrelevent branches at each level.
-* Technically, the definition of a trie uses a level for each letter, not for each word. It makes more sense to be for each word in Folk though.