Faster implementation for SentencePieceExtractor
Author: e-mon
Pull request: yes

# What does this PR do?

This PR is to improve `SentencePieceExtractor` extract method performance, which took several minutes when targeting vocabularies of tens of thousands of words.

For 44,876 words ( [repository](https://huggingface.co/rinna/japanese-gpt-1b) ), it used to take 290 seconds, but now it takes 0.2 seconds.
I've added a simple test, but let me know if you need anything else.
The experimental conditions and code are as follows.

result
```
vocabulary length: 44876, max word length: 16
normal: 290.2607123851776 secs
improved: 0.18401217460632324 secs
```

code
```python
import pickle
import time
from collections import defaultdict
from typing import List

vocab = pickle.load(open('vocab.pkl', 'rb'))

def normal(vocab: dict) -> List[str]:
    merges = []
    for piece_l in vocab.keys():
        for piece_r in vocab.keys():
            merge = f"{piece_l}{piece_r}"
            piece_id = vocab.get(merge, None)
            if piece_id:
                merges += [(piece_l, piece_r, piece_id)]
    return merges

def improved(vocab: dict) -> List[str]:
    merges = []
    prefixes = dict()
    for word in vocab.keys():
        for i in range(len(word)):
            prefixes[word[: i + 1]] = {word} | prefixes.setdefault(word[: i + 1], set())

    for word in vocab.keys():
        if len(prefixes[word]) > 1:
            for candidate in prefixes[word]:
                if word != candidate:
                    if candidate[len(word) :] in vocab:
                        piece_id = vocab.get(candidate, None)
                        merges += [(word, candidate[len(word) :], piece_id)]
    return merges

print(f'vocabulary length: {len(vocab)}, max word length: {max(len(word) for word in vocab.keys())}')
start = time.time()
result_normal = normal(vocab)
print(f'normal: {time.time() - start} secs')

start = time.time()
result_improved = improved(vocab)
print(f'improved: {time.time() - start} secs')

# confirm that results match
assert sorted(result_normal, key=lambda val: val[2]) == sorted(result_improved, key=lambda val: val[2])
```


## Before submitting
- [x] Did you read the [contributor guideline](https://github.com/huggingface/transformers/blob/main/CONTRIBUTING.md#start-contributing-pull-requests),
      Pull Request section?
- [x] 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.

@n1t0, @LysandreJik


Comments:
The docs for this PR live [here](https://moon-ci-docs.huggingface.co/docs/transformers/pr_17199). All of your documentation changes will be reflected on that endpoint.

Please have a look and let me know your feedback. 
@sgugger, @LysandreJik, @patil-suraj,  @n1t0

cc @Narsil and @SaulLu 

Hi @e-mon ,

Thanks for looking into this. 
Is this code used often ? This code was written hastily and was supposed to only run once (since we can save the `tokenizer.json` within the `tokenizers` library which should load again pretty fast.

Since we're looking at optimizing this code I propose another version which seems even faster:
https://gist.github.com/Narsil/a6b927c4973d4d0a63b1765cfff38e55

(I am using a smaller vocab for faster testing, since the slow is really excruciatingly slow).


This issue has been automatically marked as stale because it has not had recent activity. If you think this still needs to be addressed please comment on this thread.

Please note that issues that do not follow the [contributing guidelines](https://github.com/huggingface/transformers/blob/main/CONTRIBUTING.md) are likely to be ignored.

Or shall we just parallize it?

```
# coding=utf-8
# Copyright 2018 The HuggingFace Inc. team.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
"""
Utilities to convert slow tokenizers in their fast tokenizers counterparts.

All the conversions are grouped here to gather SentencePiece dependencies outside of the fast tokenizers files and
allow to make our dependency on SentencePiece optional.
"""

import warnings
from typing import Dict, List, Tuple

from tokenizers import AddedToken, Regex, Tokenizer, decoders, normalizers, pre_tokenizers, processors
from tokenizers.models import BPE, Unigram, WordPiece
import multiprocessing
from functools import partial
from .utils import requires_backends
def merge_core(vocab,vocab_scores,piece_ls):
    merges = []
    for piece_l in piece_ls:
        for piece_r in vocab.keys():
            merge = f"{piece_l}{piece_r}"
            piece_score = vocab_scores.get(merge, None)
            if piece_score:
                merges += [(piece_l, piece_r, piece_score)]
    return merges;


class SentencePieceExtractor:
    """
    Extractor implementation for SentencePiece trained models. https://github.com/google/sentencepiece
    """

    def __init__(self, model: str):
        requires_backends(self, "sentencepiece")
        from sentencepiece import SentencePieceProcessor

        self.sp = SentencePieceProcessor()
        self.sp.Load(model)

    def extract(self, vocab_scores=None) -> Tuple[Dict[str, int], List[Tuple]]:
        """
        By default will return vocab and merges with respect to their order, by sending `vocab_scores` we're going to
        order the merges with respect to the piece scores instead.
        """
        sp = self.sp
        vocab = {sp.id_to_piece(index): index for index in range(sp.GetPieceSize())}
        if vocab_scores is not None:
            vocab_scores, reverse = dict(vocab_scores), True
        else:
            vocab_scores, reverse = vocab, False
        pool_obj = multiprocessing.Pool();
        merges=pool_obj.map(partial(merge_core,vocab,vocab_scores),vocab.keys())
        # Merges
        # merges = []
        # for piece_l in vocab.keys():
        #     for piece_r in vocab.keys():
        #         merge = f"{piece_l}{piece_r}"
        #         piece_score = vocab_scores.get(merge, None)
        #         if piece_score:
        #             merges += [(piece_l, piece_r, piece_score)]
        merges = sorted([item for sublist in merges for item in sublist], key=lambda val: val[2], reverse=reverse);
        merges = [(val[0], val[1]) for val in merges]
        return vocab, merges

```