바이트 페어 인코딩(BPE) 병합

GPT 계열 토크나이저는 바이트 페어 인코딩을 사용합니다. 한 글자씩에서 시작해, 가장 흔한 이웃 쌍을 새로운 기호로 반복해서 합칩니다.

1. words의 각 단어를 문자로 나눕니다. 반복되는 단어는 여러 번 셉니다.
2. 모든 단어에서 인접한 기호 쌍을 모두 셉니다.
3. 가장 자주 나오는 쌍을 고릅니다. 동률이면 (첫 기호, 두 번째 기호)를 문자열로 비교해 가장 작은 쌍을 고릅니다.
4. 그 쌍이 나오는 곳을 왼쪽에서 오른쪽으로 모두 합친 기호로 바꾸고, 합친 기호를 기록합니다.
5. 이를 num_merges번 반복하며, 기호가 두 개 이상 남은 단어가 없으면 일찍 멈춥니다.

bpe_merges(words, num_merges)를 구현하세요.

입력

words: 학습용 단어 (소문자).

num_merges: 학습할 병합 횟수.

출력

합친 기호를 학습한 순서대로 반환하세요.

제약 조건

1 ≤ 단어 수 ≤ 1,000, 1 ≤ 각 단어의 길이 ≤ 30

0 ≤ num_merges ≤ 200

예시

입력:
words = ["low", "lower", "lowest"]
num_merges = 2

예상 출력:
expected = ["lo", "low"]

입력:
std::vector<std::string> words = {"low", "lower", "lowest"};
long long num_merges = 2;

예상 출력:
std::vector<std::string> expected = {"lo", "low"};

입력:
string[] words = new string[] {"low", "lower", "lowest"};
long num_merges = 2;

예상 출력:
string[] expected = new string[] {"lo", "low"};

입력:
words = ["aaa"]
num_merges = 3

예상 출력:
expected = ["aa", "aaa"]

입력:
std::vector<std::string> words = {"aaa"};
long long num_merges = 3;

예상 출력:
std::vector<std::string> expected = {"aa", "aaa"};

입력:
string[] words = new string[] {"aaa"};
long num_merges = 3;

예상 출력:
string[] expected = new string[] {"aa", "aaa"};

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

• Sennrich, Haddow and Birch, Neural Machine Translation of Rare Words with Subword Units
• Hugging Face course, Byte-Pair Encoding tokenization