Will look for the words added to the trie within `text`. Output is the original string splitted along the boundaries of the words found. This trie will match the longest possible word first ! Example: ```python >>> trie = Trie() >>> trie.sp
(self, text: str)
| 104 | ref[self._termination_char] = 1 |
| 105 | |
| 106 | def split(self, text: str) -> List[str]: |
| 107 | """ |
| 108 | Will look for the words added to the trie within `text`. Output is the original string splitted along the |
| 109 | boundaries of the words found. |
| 110 | |
| 111 | This trie will match the longest possible word first ! |
| 112 | |
| 113 | Example: |
| 114 | |
| 115 | ```python |
| 116 | >>> trie = Trie() |
| 117 | >>> trie.split("[CLS] This is a extra_id_100") |
| 118 | ["[CLS] This is a extra_id_100"] |
| 119 | |
| 120 | >>> trie.add("[CLS]") |
| 121 | >>> trie.add("extra_id_1") |
| 122 | >>> trie.add("extra_id_100") |
| 123 | >>> trie.split("[CLS] This is a extra_id_100") |
| 124 | ["[CLS]", " This is a ", "extra_id_100"] |
| 125 | ``` |
| 126 | """ |
| 127 | # indexes are counted left of the chars index. |
| 128 | # "hello", index 0, is left of h, index 1 is between h and e. |
| 129 | # index 5 is right of the "o". |
| 130 | |
| 131 | # States are going to capture every possible start (indexes as above) |
| 132 | # as keys, and have as values, a pointer to the position in the trie |
| 133 | # where we're at. This is a partial match for now. |
| 134 | # This enables to keep track of multiple matches while we're iterating |
| 135 | # the string |
| 136 | # If the trie contains, "blowing", and "lower" and we encounter the |
| 137 | # string "blower", we need to split into ["b", "lower"]. |
| 138 | # This is where we need to keep track of multiple possible starts. |
| 139 | states = OrderedDict() |
| 140 | |
| 141 | # This will contain every indices where we need |
| 142 | # to cut. |
| 143 | # We force to cut at offset 0 and len(text) (added later) |
| 144 | offsets = [0] |
| 145 | |
| 146 | # This is used by the lookahead which needs to skip over |
| 147 | # some text where the full match exceeded the place in the initial |
| 148 | # for loop |
| 149 | skip = 0 |
| 150 | # Main loop, Giving this algorithm O(n) complexity |
| 151 | for current, current_char in enumerate(text): |
| 152 | if skip and current < skip: |
| 153 | # Prevents the lookahead for matching twice |
| 154 | # like extra_id_100 and id_100 |
| 155 | continue |
| 156 | |
| 157 | # This will track every state |
| 158 | # that stop matching, we need to stop tracking them. |
| 159 | # If we look at "lowball", we're going to match "l" (add it to states), "o", "w", then |
| 160 | # fail on "b", we need to remove 0 from the valid states. |
| 161 | to_remove = set() |
| 162 | # Whenever we found a match, we need to drop everything |
| 163 | # this is a greedy algorithm, it will match on the first found token |