🎓 A1Learner
🔍
0 of 53 lessons completed

PyTorch Counting Pairs

An adjacent pair is two symbols that sit side by side in a text, in a fixed order. Byte-pair encoding, or BPE, is a token scheme that counts these pairs and merges the most common one.

Pairs hide inside a short string

The zip built-in pairs each symbol with the next one, and Counter tallies the pairs. The string 'aaabaa' holds five pairs, and the pair 'aa' occurs three times.

from collections import Counter

text = "aaabaa"
pairs = Counter(zip(text, text[1:]))
print(pairs)

Pairs slide along one step at a time

Each pair starts one position later than the pair before it. The pairs of 'abcd' overlap, and the middle symbols each appear in two pairs.

text = "abcd"
pairs = [text[i:i + 2] for i in range(len(text) - 1)]
print(pairs)

The most common pair wins

The most_common method returns the pair with the tallest tally first. In the string below, the pair 'ab' wins with three occurrences.

from collections import Counter

text = "ababab cd"
pairs = Counter(zip(text, text[1:]))
pair, count = pairs.most_common(1)[0]
print("".join(pair), count)

Example

from collections import Counter

CORPUS = 'The sun came up over the hill. Moss the cat woke in the warm house. Nan put milk in a blue bowl. Moss drank the milk and licked her lips. Then Moss went out to the garden.\n\nPip the sparrow sat on the wall. Good morning, Moss, said Pip. Good morning, Pip, said Moss. The sun is warm, said Pip. The sun is warm and the sky is clear, said Moss.\n\nBram the dog ran down the lane. Bram had a stick in his mouth. Drop the stick, Bram, said Nan. Bram dropped the stick. Good dog, said Nan. Bram wagged his tail and barked at the sky.\n\nThe three friends walked to the river. The river ran cold and clear over the white stones. A silver fish jumped in the river. Splash! The fish jumped again. Moss watched the fish. Pip watched the fish. Bram put one paw in the water. The water was cold. Bram shook his wet paw. The friends laughed in the sun.\n\nAt noon, Nan called the friends home. Bread and cheese waited on the table. The friends ate in the garden. The garden smelled of rain and roses. Bees hummed in the warm air. It was a good day, and the day was not over yet.\n\nThe rain came in the night. Rain tapped on the roof. Rain ran down the lane. Rain filled the blue bowl in the garden. Moss sat at the window and watched the rain. Pip hid under the wall. Bram slept by the fire and dreamed of sticks.\n\nIn the morning, the rain was gone. The sun came up over the hill. The lane was wet and the garden was green. A snail crossed the step, slow and silver. Good morning, snail, said Moss. The snail said nothing. The snail had far to go.\n\nNan gave Moss a fish for lunch. Nan gave Bram a bone for lunch. Nan gave Pip a crust of bread. Pip pecked the crust. Bram chewed the bone. Moss ate the fish, bite by bite. Then all three slept in the sun, full and warm and glad.\n\nOne day, a red ball rolled into the garden. The ball rolled past Moss. The ball rolled past Bram. The ball rolled under the wall and stopped by the river. Whose ball is this? said Pip. Tom came down the lane. Tom was a small boy with red boots. My ball! said Tom. Thank you, friends!\n\nTom threw the ball. Bram ran and caught the ball. Tom threw the ball again. Pip flew over the ball. Moss hid in the grass and jumped out. Boo! said Moss. Tom laughed and laughed. The friends played until the sun went down.\n\nWhen the sun went down, the sky turned red and gold. The friends walked home in the soft light. Nan had soup on the fire. The soup was hot and good. Eat, said Nan, and rest. Tomorrow is a new day.\n\nThe moon came up over the hill. The stars came out, one by one. Moss curled on the step. Pip slept in the tree. Bram slept by the door, one ear up. The house was quiet. The river ran on in the dark, cold and clear. Sleep well, little friends, said the moon. And they did.\n\nIn the spring, the garden woke up. Green shoots came out of the dark earth. A bee came to the garden. The bee hummed from rose to rose. Pip sang in the tree. Bram dug a hole by the wall. Moss rolled in the warm grass. Spring is here, said Moss. Spring is here at last.\n\nNan planted seeds in the garden. Small seeds, brown and round. Moss watched the seeds go into the earth. Pip watched for worms. Bram watched for Tom. Rain came, soft and warm. Sun came, warm and gold. The seeds slept in the dark. Then, one morning, a green shoot! And then two! And then ten!\n\nThe shoots grew tall in the summer sun. Red roses opened on the wall. The garden was full of bees and birds. Tom picked peas in the garden. Nan picked beans. Moss picked a warm spot and slept in it. It was a good summer, a long, warm summer.\n\nOne hot day, the friends went up the hill. The hill was high and the grass was dry. From the top of the hill, the friends saw the river. They saw the lane and the house and the garden. They saw the whole world, small and bright. I can see my house, said Tom. I can see my river, said Moss. I can see everything, said Pip, and Pip flew up, up, up into the blue.\n\nAt the top of the hill, the wind blew. The wind blew the grass. The wind blew the tree. The wind took the song of Pip and carried it over the river. Sing again, Pip, said Bram. Pip sang again, loud and sweet. The sun shone. The wind blew. It was good to be alive.\n\nWhen autumn came, the leaves turned gold and red. Leaves fell from the tree. Leaves covered the lane. Bram jumped in the leaves. Moss hid in the leaves. Pip rode on a leaf down to the river. Splash! Pip shook the water off and laughed. Autumn is fun, said Pip. Autumn is cold, said Moss, and Moss went home to the fire.\n\nNan made a pie in the autumn. The pie was full of apples. The house smelled of apples and spice. Tom ate two slices of pie. Bram ate the crumbs. Moss drank warm milk. Pip pecked at a seed cake. Outside, the leaves fell. Inside, the fire burned, warm and bright.\n\nOne cold morning, frost covered the garden. The grass was white. The bowl was ice. The river ran slow under a skin of ice. Moss put one paw on the ice. The ice was cold and hard. Winter is coming, said Moss. Winter is coming soon.\n\nSnow fell in the night, soft and deep. In the morning, the world was white. The hill was white. The lane was white. The tree was white, and the wall was white. Bram ran in the snow. Tom rolled in the snow. Pip sat in the tree and shivered. Come down, Pip, said Nan. Come in by the fire.\n\nBy the fire, the friends were warm. Nan read a story out loud. The story was about a cat, a dog, and a bird. That is us! said Tom. That is us, said Moss, and Moss purred. The snow fell outside. The fire burned inside. It was the best place in the whole white world.\n\nAnd when the snow melted, the river ran fast and full. The sun came up over the hill, warm as ever. Moss sat on the step. Pip sang in the tree. Bram ran down the lane with a stick. Spring had come again, and the friends were glad. The end.'

pairs = Counter(zip(CORPUS, CORPUS[1:]))
ranked = sorted(pairs.items(), key=lambda item: (-item[1], "".join(item[0])))

print(f"Adjacent pairs counted: {sum(pairs.values())}")
print(f"Distinct pairs: {len(pairs)}")
print("Top five pairs:")
for pair, count in ranked[:5]:
    print(f"{''.join(pair)!r}: {count}")

Key points

  • Pair: two adjacent symbols taken together, such as the pair 'he'
  • A text of n symbols holds n - 1 adjacent pairs
  • Each pair is tallied at every position where it occurs
  • The corpus holds 5,781 adjacent pairs across 358 distinct pairs
  • Equal counts break toward the pair that sorts first as text
  • The winning pair is the pair the next merge replaces everywhere

In this example, every adjacent pair in the corpus is counted exactly once per occurrence. The corpus holds 5,781 pairs, and 358 distinct pairs appear among them. The winning pair is 'e ' with 251 occurrences, a letter plus the space that follows it. The pair 'he' follows with 204, and ' t' takes third place with 164. Fourth and fifth place go to 'd ' with 158 and '. ' with 155, so sentence endings rank as high as letter pairs. Four of the top five pairs contain a space, which shows how much of this text is word endings. The next lesson merges the winner and counts again.

Note

The count here runs over single characters, and merged tokens join the count later

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

What does BPE do with the most common adjacent pair?