Hello, everyone.
This lecture for the data structure and algorithm is Trie in 12th chapter advanced data structure.
The height of BST the index structure we talked about before will be log n if its input is a random dataset.
It is acceptable
But it will degenerate if the input is ordered.
Of course, there are some balanced tree,
But it will degenerate if the input is ordered.
like red-black tree, AVL tree , splay tree and so on.
We will get a balanced tree structure if the data is random in the whole space.
This idea mainly comes from information retrieval.
We want a good retrieval performance.
So Trie comes from the word 'retrieval'.
As for English words, it's obviously a space division by English alphabet.
For general situation we use binary Trie cause all the information in computer is stored in binary format.
Let's take a look at the 26-way Trie.
All the strings start with letter 'a' show in this subtree.
We divide the space by the 2nd letter at the 2nd step.
But pay attention to this tree. All the words have the same length.
That is any word can't be another word's prefix.
We should distinguish this situation when a word is the prefix of another word.
We need to mark at some splace in Trie.
Take the word'an' for example.
'an' is the prefix of the other two words.
So we should mark with asterisk here.
For the purpose of unification, we asterisk the place where a word ends.
We can do some compression in this tree especially near the leaves.
Compress the subtree without branches.
Why don't we compress is near the root?
Cause the process of constructing Trie is an extension from an empty tree.
These initiate branches will split and grow.
So we don't have to compress at the beginning.
We just compress the structure near the leaves.
And all the information is stored at the leaves.
The mapping, the information of the word storing at the leaves, is similar to dictionary.
The internal nodes (not leaves) play a part in indexing the information.
Let's take a look at binary Tries on 6-bit data(i.e. range from 0 to 63 by decimal system).
We divide it according to the position in the space.
Binary Tries will be generated by this binary division.
Let's map this binary Trie into binary coding.
The root corresponds to the highest bit of the binary number.
If it's 0, we go left. If not, go right.
We can see that the node with number 2 has a single branch.
In this situation, we can compress it.
After compressing, the structure of the binary Trie is getting more compact.
And it will be faster occur for retrieval.
The maximum retrieving length depends on the length of binary number.
One good application of Trie is suffix tree.
We find all the non-empty substrings for a single string.
These substrings constitude a set of strings.
We constitude the set with every non-empty suffix.
We can build a 26-way Trie with this set.
These grey nodes have single branch.
So they are compressible.
The tree after compressing is called suffix tree.
Suffix tree can be constructed in O(n).
This algorithm is developed by Ukkonen.
It's amazing algorithm.
Another data structure related to suffix tree is suffix array.
We sort all the suffixes.
And use suffix array(SA) to record index of suffixes of original string.
Besides, we record the longest common prefix of adjacent suffixes.
These two arrays record all the information we gonna use later.
Let's take a look at the suffix of index 5 and the suffix of index 1.
Their common prefix's length is 3, that is ALA.
These two arrays(SA and lcp) organize a very efficent indexing structure.
Let's take a look at the relationship between suffix array and suffix tree.
How to construct suffix tree once we get the suffix array.
The root is defined by the first suffix in the dictionary.
The common prefix length of the first suffix and the second is 3.
Split at this position.
Then the second suffix is added.
What about the third suffix? It share a single letter with the second suffix.
Then split again.
Keep doing this.
Suffix array contains two array.
One is called SA or Rank.
It represents the suffix's starting index of original string after sorting.
And array lcp or array height.
it represents the longest common prefix of the two adjacent suffix.
We build the suffix tree with the help of two arrays.
Suffix tree and suffix array are totally equivalent.
Their difference is the process of constructure.
We can use DC3 or doubling algorithm to build suffix array.
And use UKK algorithm to build suffix tree.
DC3 and UKK algorithm have better efficiency.
Assume the length of the original string is n.The algorithm can build it in O(n).
Both suffix array and suffix tree have good applications.
Let's think about this.
how to construct Trie with Chinese words?
Chinese words is constructed by Chinese characters.
Chinese characters are very large.
So Trie is not suitable.
Actually, Trie has varieties. That is three-array trie.
And two-array trie can have a good organization of Chinese characters.
Actually, Trie has varieties. That is three-array trie.
Some papers about suffix array and suffix tree has lots of applications.
Like frequent pattern mining, cluster, DNA comparison and so on.
Suffix array is easy to implement.
So we can use suffix array in some easy applications.
while suffix tree is not.
But once we build it.
It's very convenient to do some operations.
Thank you