[Tentative] Moving slow tokenizer to the Trie world.
Author: Narsil
Pull request: yes

# What does this PR do?

This PR attempts to solve the slow tokenizer `added_tokens` source of slowness.

Currently the splitting is done in O(n) manner, with very non obvious algorithm
to "pre-tokenize" (`tokenize` function). This will yield extremely slow tokenization
even by slow tokenization standards. It also affects slow-only tokenizers like ByT5.

The proposed fix simply moves the splitting into a O(1) algorithm (relative to `added_tokens`).
It does that by manually implementing a real Trie (more information why Python regexp can't be trusted on this: https://stackoverflow.com/questions/42742810/speed-up-millions-of-regex-replacements-in-python-3).

There is at least one know breaking change here, it's that users could rely on token ORDER to force splitting
on some `added_tokens` before others (https://github.com/huggingface/tokenizers/issues/615).
This won't be the case anymore with this code, as the splitting will happen on ~~first~~ longest encounter of `added_tokens` regardless. This is a pretty standard practice.

~~We could instead split on longest match first, but it's also a breaking change (although most likely less breaking).It does mean adding backtracking so the algorithm will be more complex and more state management~~ Edit: Implemented 


Benchmarking code:
```python
import datetime                                                                     
from transformers import GPT2Tokenizer                                                                     
                                                                                    
                                                                                                    
# They used to have to be sorted in reverse by length, otherwise the tokens arent           
newtokens = range(0, 20000)                                                          
newtokens = list(newtokens)                                                          
newtokens.sort(reverse=True)                                                         
newtokens = [f"new_{x}" for x in newtokens]                                       
                                                                                     
slow = GPT2Tokenizer.from_pretrained("gpt2")                                         
                                                                                     
# Add new vocab                                                                      
slow_custom = GPT2Tokenizer.from_pretrained("gpt2")                                 
slow_custom.add_tokens(newtokens)                                                               
                                                                                     
# Differences when tokenising the text...                                           
text = "this is a sentence containing new_200"                                     
for tokenizer in [slow, slow_custom]:                                                
    start = datetime.datetime.now()                                                  
    print(tokenizer.tokenize(text))                                                 
    print(datetime.datetime.now() - start) 
```

This goes from 4~7s on the `slow_custom` to 1ms (and ~0.3ms without `added_tokens`)




<!--
Congratulations! You've made it this far! You're not quite done yet though.

Once merged, your PR is going to appear in the release notes with the title you set, so make sure it's a great title that fully reflects the extent of your awesome contribution.

Then, please replace this with a description of the change and which issue is fixed (if applicable). Please also include relevant motivation and context. List any dependencies (if any) that are required for this change.

Once you're done, someone will review your PR shortly (see the section "Who can review?" below to tag some potential reviewers). They may suggest changes to make the code even better. If no one reviewed your PR after a week has passed, don't hesitate to post a new comment @-mentioning the same persons---sometimes notifications get lost.
-->

<!-- Remove if not applicable -->

Fixes https://github.com/huggingface/tokenizers/issues/615 (unrelated, because users seem to still
be using slow tokenizers there.


@LysandreJik
@patrickvonplaten
@n1t0

## Before submitting
- [ ] This PR fixes a typo or improves the docs (you can dismiss the other checks if that's the case).
- [ ] Did you read the [contributor guideline](https://github.com/huggingface/transformers/blob/master/CONTRIBUTING.md#start-contributing-pull-requests),
      Pull Request section?
- [ ] Was this discussed/approved via a Github issue or the [forum](https://discuss.huggingface.co/)? Please add a link
      to it if that's the case.
- [ ] Did you make sure to update the documentation with your changes? Here are the
      [documentation guidelines](https://github.com/huggingface/transformers/tree/master/docs), and
      [here are tips on formatting docstrings](https://github.com/huggingface/transformers/tree/master/docs#writing-source-documentation).
- [ ] Did you write any new necessary tests?


## Who can review?

Anyone in the community is free to review the PR once the tests have passed. Feel free to tag
members/contributors who may be interested in your PR.

<!-- Your PR will be replied to more quickly if you can figure out the right person to tag with @

 If you know how to use git blame, that is the easiest way, otherwise, here is a rough guide of **who to tag**.
 Please tag fewer than 3 people.

Models:

- albert, bert, xlm: @LysandreJik
- blenderbot, bart, marian, pegasus, encoderdecoder,  t5: @patrickvonplaten, @patil-suraj
- longformer, reformer, transfoxl, xlnet: @patrickvonplaten
- fsmt: @stas00
- funnel: @sgugger
- gpt2: @patrickvonplaten, @LysandreJik
- rag: @patrickvonplaten, @lhoestq
- tensorflow: @LysandreJik

Library:

- benchmarks: @patrickvonplaten
- deepspeed: @stas00
- ray/raytune: @richardliaw, @amogkam
- text generation: @patrickvonplaten
- tokenizers: @n1t0, @LysandreJik
- trainer: @sgugger
- pipelines: @LysandreJik

Documentation: @sgugger

HF projects:

- datasets: [different repo](https://github.com/huggingface/datasets)
- rust tokenizers: [different repo](https://github.com/huggingface/tokenizers)

Examples:

- maintained examples (not research project or legacy): @sgugger, @patil-suraj
- research_projects/bert-loses-patience: @JetRunner
- research_projects/distillation: @VictorSanh

 -->
```bash
RUN_SLOW=1 pytest -sv tests/test_tokenization_*

Results (1250.63s):
    3957 passed
     353 skipped
```

Comments:
@patrickvonplaten It speeds up all the time, but it's only that impressive with adding tons of `added_tokens`. The reason is because of the change in complexity. Even for simple `ByT5` that uses 125 extra `added_tokens` by default, that's already 100x speed (so not really that exotic). 

For "regular" slow tokenizers, with <5 added_tokens the speedup exists but is rather negligible.

Also I've seen 2/3 different issues regarding this. The one reported (https://github.com/huggingface/tokenizers/issues/615) has 8 participants since February, so while not super urgent, there definitely seems to be more than a couple of people doing that.

And always fine adding more documentation, but fwiw it's a pretty standard data structure. 

Hi @LysandreJik Do we have benchmarks  tests anywhere ?

This doesn't fix anything that was broken before, it just make things faster (some usage of the lib was so slow that it was unusable, but it was definitely working).

I could add a test that some tokenization takes too long, but it's always a tricky business to add tests related to timings because it might depend on the hardware running the tests, so it would definitely NOT be a unit test.

@LysandreJik Ok, I added 1 `common` test which fails only on Canine (`extra_id_1` is not valid over there).

Also added Trie specific tests (the one in the doc basically)

Thanks @SaulLu , the matching was incorrect in that edge case where some token is rigourously included in another, then we would match the inner token instead of the first match.

The lookahead part got more complex but will now work in that edge case (which is important to at least follow the documentation)

Regarding the idea of `added_tokens` following order, recaping some offline conversation:
- It's doable, but would make code even more complex. We would need to keep track of ranks in the Trie, whenever we have a full match, resolve all partial matches, sort by order and take the highest rank.
- Seems overly complex for what seems to be pathological cases at best, so out of scope of this one. 

Will merge this later today unless there are still some comments (But I feel it's ok in current state)