Ranked BPE Merges

Problem

Apply a ranked byte-pair-style merge table to a list of string tokens. merges is ordered from highest priority (rank 0) to lowest, with each rule [left,right].

At each iteration, choose the lowest-rank rule currently present in adjacent tokens. Merge every non-overlapping occurrence of that pair in a left-to-right pass by concatenating its strings. Recompute applicable ranks and repeat until no rule applies. Return the remaining strings. This is a specified token-string model, not a complete pretrained tokenizer.

def ranked_bpe(tokens, merges):

Constraints

• tokens contains 0..64 nonempty strings; merges has 0..32 unique pairs of nonempty strings.
• Rules are case-sensitive; each merge reduces token count.
• Inputs satisfy these constraints; invalid-input handling is not graded. Use only Python standard library and NumPy.

Examples

Arguments: [
  [
    "a",
    "b",
    "c"
  ],
  [
    [
      "a",
      "b"
    ]
  ]
]
Expected result: [
  "ab",
  "c"
]

Arguments: [
  [
    "a",
    "b",
    "c"
  ],
  [
    [
      "b",
      "c"
    ],
    [
      "a",
      "b"
    ]
  ]
]
Expected result: [
  "a",
  "bc"
]