class_docstr: Trie in Python. Creates a Trie out of a list of words. The trie is used to split on `added_tokens` in one pass
  Loose reference https://en.wikipedia.org/wiki/Trie
class_docstr_tok: ["Trie","in","Python",".","Creates","a","Trie","out","of","a","list","of","words",".","The","trie","is","used","to","split","on","`","added_tokens","`","in","one","pass","Loose","reference","https",":","\/\/en.wikipedia.org\/wiki\/Trie"]
docstr: 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.split("[CLS] This is a extra_id_100")
  ["[CLS] This is a extra_id_100"]
  
  >>> trie.add("[CLS]")
  >>> trie.add("extra_id_1")
  >>> trie.add("extra_id_100")
  >>> trie.split("[CLS] This is a extra_id_100")
  ["[CLS]", " This is a ", "extra_id_100"]
  ```
docstr_tok: ["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.split","(","``","[","CLS","]","This","is","a","extra_id_100","''",")","[","``","[","CLS","]","This","is","a","extra_id_100","''","]",">",">",">","trie.add","(","``","[","CLS","]","''",")",">",">",">","trie.add","(","``","extra_id_1","''",")",">",">",">","trie.add","(","``","extra_id_100","''",")",">",">",">","trie.split","(","``","[","CLS","]","This","is","a","extra_id_100","''",")","[","``","[","CLS","]","''",",","``","This","is","a","``",",","``","extra_id_100","''","]","``","`"]
code: def split(self, text: str) -> List[str]:
      """
      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.split("[CLS] This is a extra_id_100")
      ["[CLS] This is a extra_id_100"]
  
      >>> trie.add("[CLS]")
      >>> trie.add("extra_id_1")
      >>> trie.add("extra_id_100")
      >>> trie.split("[CLS] This is a extra_id_100")
      ["[CLS]", " This is a ", "extra_id_100"]
      ```
      """
      # indexes are counted left of the chars index.
      # "hello", index 0, is left of h, index 1 is between h and e.
      # index 5 is right of the "o".
  
      # States are going to capture every possible start (indexes as above)
      # as keys, and have as values, a pointer to the position in the trie
      # where we're at. This is a partial match for now.
      # This enables to keep track of multiple matches while we're iterating
      # the string
      # If the trie contains, "blowing", and "lower" and we encounter the
      # string "blower", we need to split into ["b", "lower"].
      # This is where we need to keep track of multiple possible starts.
      states = OrderedDict()
  
      # This will contain every indices where we need
      # to cut.
      # We force to cut at offset 0 and len(text) (added later)
      offsets = [0]
  
      # This is used by the lookahead which needs to skip over
      # some text where the full match exceeded the place in the initial
      # for loop
      skip = 0
      # Main loop, Giving this algorithm O(n) complexity
      for current, current_char in enumerate(text):
          if skip and current < skip:
              # Prevents the lookahead for matching twice
              # like extra_id_100 and id_100
              continue
  
          # This will track every state
          # that stop matching, we need to stop tracking them.
          # If we look at "lowball", we're going to match "l" (add it to states), "o", "w", then
          # fail on "b", we need to remove 0 from the valid states.
          to_remove = set()
          # Whenever we found a match, we need to drop everything
          # this is a greedy algorithm, it will match on the first found token
          reset = False
  
          # In this case, we already have partial matches (But unfinished)
          for start, trie_pointer in states.items():
              if "" in trie_pointer:
                  # This is a final match, we need to reset and
                  # store the results in `offsets`.
  
                  # Lookahead to match longest first
                  # Important in case of extra_id_1 vs extra_id_100
                  # Here we are also actively looking for other earlier partial
                  # matches
                  # "[CLS]", "L", we need to match CLS even if L is special
                  for lookstart, looktrie_pointer in states.items():
                      if lookstart > start:
                          # This partial match is later, we can stop looking
                          break
                      elif lookstart < start:
                          # This partial match is earlier, the trie pointer
                          # was already updated, so index is + 1
                          lookahead_index = current + 1
                          end = current + 1
                      else:
                          # Here lookstart == start and
                          #      looktrie_pointer == trie_pointer
                          # It wasn't updated yet so indices are current ones
                          lookahead_index = current
                          end = current
                      next_char = (
                          text[lookahead_index]
                          if lookahead_index < len(text)
                          else None
                      )
                      if "" in looktrie_pointer:
                          start = lookstart
                          end = lookahead_index
                          skip = lookahead_index
  
                      while next_char in looktrie_pointer:
                          looktrie_pointer = looktrie_pointer[next_char]
                          lookahead_index += 1
                          if "" in looktrie_pointer:
                              start = lookstart
                              end = lookahead_index
                              skip = lookahead_index
  
                          if lookahead_index == len(text):
                              # End of string
                              break
                          next_char = text[lookahead_index]
                      # End lookahead
  
                  # Storing and resetting
                  offsets.append(start)
                  offsets.append(end)
                  reset = True
                  break
              elif current_char in trie_pointer:
                  # The current character being looked at has a match within the trie
                  # update the pointer (it will be stored back into states later).
                  trie_pointer = trie_pointer[current_char]
  
                  # Storing back the new pointer into the states.
                  # Partial matches got longer by one.
                  states[start] = trie_pointer
              else:
                  # The new character has not match in the trie, we need
                  # to stop keeping track of this partial match.
                  # We can't do it directly within the loop because of how
                  # python iteration works
                  to_remove.add(start)
  
          # Either clearing the full start (we found a real match)
          # Or clearing only the partial matches that didn't work.
          if reset:
              states = {}
          else:
              for start in to_remove:
                  del states[start]
  
          # If this character is a starting character within the trie
          # start keeping track of this partial match.
          if current >= skip and current_char in self.data:
              states[current] = self.data[current_char]
  
      # We have a cut at the end with states.
      for start, trie_pointer in states.items():
          if "" in trie_pointer:
              # This is a final match, we need to reset and
              # store the results in `offsets`.
              end = len(text)
              offsets.append(start)
              offsets.append(end)
              # Longest cut is always the one with lower start so the first
              # item so we need to break.
              break
  
      return self.cut_text(text, offsets)
  
imports: import bisect
  import itertools
  import re
  import unicodedata
  from collections import OrderedDict
  from typing import Any, Dict, List, Optional, Tuple, Union, overload
  from .tokenization_utils_base import ENCODE_KWARGS_DOCSTRING, ENCODE_PLUS_ADDITIONAL_KWARGS_DOCSTRING, INIT_TOKENIZER_DOCSTRING, AddedToken, BatchEncoding, EncodedInput, EncodedInputPair, PreTokenizedInput, PreTokenizedInputPair, PreTrainedTokenizerBase, TextInput, TextInputPair, TruncationStrategy
  from .utils import PaddingStrategy, TensorType, add_end_docstrings, logging
label_desc: Use image node_id 3 for calling the Trie obj's underlying member method code with example usage: obj.split(text) and returns: self