Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Byte Pair Encoding (BPE) Merges

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

Bạn sẽ học được gì

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

Đề bài

Xem bản dịch

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.

Ràng buộc

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

0 ≤ num_merges ≤ 200

Ví dụ

Ví dụ 1
Đầu vào:
words = ["low", "lower", "lowest"]
num_merges = 2

Kết quả mong đợi:
expected = ["lo", "low"]
Đầu vào:
std::vector<std::string> words = {"low", "lower", "lowest"};
long long num_merges = 2;

Kết quả mong đợi:
std::vector<std::string> expected = {"lo", "low"};
Đầu vào:
string[] words = new string[] {"low", "lower", "lowest"};
long num_merges = 2;

Kết quả mong đợi:
string[] expected = new string[] {"lo", "low"};

Giải thích

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"].

Ví dụ 2
Đầu vào:
words = ["aaa"]
num_merges = 3

Kết quả mong đợi:
expected = ["aa", "aaa"]
Đầu vào:
std::vector<std::string> words = {"aaa"};
long long num_merges = 3;

Kết quả mong đợi:
std::vector<std::string> expected = {"aa", "aaa"};
Đầu vào:
string[] words = new string[] {"aaa"};
long num_merges = 3;

Kết quả mong đợi:
string[] expected = new string[] {"aa", "aaa"};

Giải thích

"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"].

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

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

Gợi ý 2

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

Gợi ý 3

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

Độ phức tạp mong đợi

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

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.