모든 챌린지
보통 0명 해결 정답률 0%

Byte Pair Encoding (BPE) Merges

Learn subword merges the way GPT tokenizers do: repeatedly merge the most frequent pair of adjacent symbols.

배우게 될 내용

  • Count pairs of adjacent symbols
  • Merge the most frequent pair repeatedly
  • Understand how GPT-style tokenizers are built

문제

번역본 보기

GPT-style tokenizers use Byte Pair Encoding: start from single characters and repeatedly merge the most common pair of neighbors into a new symbol.

  1. Split every word in words into characters. Repeated words count multiple times.
  2. Count every pair of adjacent symbols across all words.
  3. Pick the most frequent pair. If pairs tie, pick the one that is smallest when you compare (first symbol, second symbol) as strings.
  4. Replace every occurrence of that pair, left to right, with the merged symbol, and record the merged symbol.
  5. Repeat num_merges times, or stop early when no word has two symbols left.

Implement bpe_merges(words, num_merges).

Input

words: The training words (lowercase letters).

num_merges: How many merges to learn.

Output

Return the merged symbols in the order they were learned.

제약 조건

1 ≤ number of words ≤ 1,000, 1 ≤ length of each word ≤ 30

0 ≤ num_merges ≤ 200

예시

예시 1
입력:
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"};

설명

Pairs: "l o" and "o w" appear 3 times each; the tie goes to "l o" ("l" < "o"), giving "lo". Now "lo w" appears 3 times, giving "low". Result: ["lo", "low"].

예시 2
입력:
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"};

설명

"aaa" has the pair "a a" twice. Merging left to right gives "aa" + "a". Then "aa a" merges into "aaa", and the word is a single symbol, so the third merge has nothing to do. Result: ["aa", "aaa"].

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

Track the current symbol sequence for each word and repeatedly count neighboring pairs across all repeated words.

힌트 2

Use pair counting plus deterministic tie-breaking by comparing the pair as two strings, and then update every word left to right.

힌트 3

Watch words that shrink to one symbol; when no adjacent pair exists anywhere, stop even if merges remain.

예상 복잡도

O(num_merges * total_symbols) time, O(total_symbols) extra space

참고 자료

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

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

아직 통과한 풀이가 없습니다. 풀어서 1위를 차지하세요.

다른 사람의 풀이 보기

커뮤니티 솔루션

아직 공개된 풀이가 없습니다. 문제를 풀고 첫 풀이를 공유하세요.