<p>BPE is one of the three algorithms to deal with the unknown word problem(or languages with rich morphology that require dealing with structure below the word level) in an automatic way: byte-pair encoding, unigram language modeling, WordPiece, and the BPE tokenization schema has two parts: a token learner and a token segmenter.</p>
<blockquote>
<p>The token learner takes a raw training corpus (sometimes roughly pre- separated into words, for example by whitespace) and induces a vocabulary, a set of tokens. The token segmenter takes a raw test sentence and segments it into the tokens in the vocabulary.</p>
</blockquote>
<p>The algorithm has a parameter k which means k merges or k new symbols in the final vocabulary.</p>
<p>Let's train the BPE using this line: <code>Pen Penapple Apple Pen</code> adapted from <a href="https://en.wikipedia.org/wiki/PPAP_(Pen-Pineapple-Apple-Pen)" rel="nofollow noreferrer">PPAP</a>, and show how the unknown/rare &quot;words&quot; <code>penapplepen</code> and <code>applepen</code> in the test data can be automatically reduced into known subword units.</p>
<h1>Learning</h1>
<p><a href="https://i.stack.imgur.com/ExQa4.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ExQa4.png" alt="enter image description here" /></a></p>
<p>First, after some preprocessing(case mapping, regex based pre-tokenization, and adding end-of-word symbol _) we obtain the following strings C(as our corpus) and their frequencies(frequency: string):</p>
<pre><code>2: p e n _    
1: p e n a p p l e _  
1: a p p l e _  
</code></pre>
<p>The vocabulary V is [_, p, e, n, a, l]</p>
<p>Now let's run the first round of the for-loop in the above pseudocode:</p>
<pre><code>p, e &lt;- most frequent pair in {(p, e): 3, (e, n): 3, (n, _): 2, (a, p): 2, (p, p): 2, (p, l): 2, (l, e): 2, (e, _): 2, (n, a): 1}    
pe &lt;- p + e   
[_, p, e, n, a, l, pe] &lt;- [_, p, e, n, a, l] + pe    
C becomes this: 
    2: pe n _    
    1: pe n a p p l e _  
    1: a p p l e _ 
</code></pre>
<p>Let's run the second merge as follows:</p>
<pre><code>p, e &lt;- most frequent pair in {(pe, n): 3, (n, _): 2, (a, p): 2, (p, p): 2, (p, l): 2, (l, e): 2, (e, _): 2, (n, a): 1}    
pen &lt;- pe + n   
[_, p, e, n, a, l, pe, pen] &lt;- [_, p, e, n, a, l, pe] + pen    
C becomes this: 
    2: pen _    
    1: pen a p p l e _  
    1: a p p l e _ 
</code></pre>
<p>And here are the next merges if we take k as N &gt;= 9:</p>
<pre><code>Merge          Current V 
(pen, _)       [_, p, e, n, a, l, pe, pen, pen_]  
(a, p)         [_, p, e, n, a, l, pe, pen, pen_, ap]
(ap, p)        [_, p, e, n, a, l, pe, pen, pen_, ap, app]
(app, l)       [_, p, e, n, a, l, pe, pen, pen_, ap, app, appl]
(appl, e)      [_, p, e, n, a, l, pe, pen, pen_, ap, app, appl, apple]
(apple, _)     [_, p, e, n, a, l, pe, pen, pen_, ap, app, appl, apple, apple_]
(pen, apple_)  [_, p, e, n, a, l, pe, pen, pen_, ap, app, appl, apple, apple_, penapple_]
</code></pre>
<p>We see that after 9 iterations of merging, there are no adjacent pairs in C.</p>
<h1>Parsing</h1>
<blockquote>
<p>The token parser just runs on the test data the merges we have learned from the training data, greedily, in the order we learned them. (Thus the frequencies in the test data don’t play a role, just the frequencies in the training data).</p>
</blockquote>
<p>In this step we test the parser using this sentence: <code>Applepen PenapplePen</code>. As usual, we do the preprocessing we did in the training step and obtain:</p>
<pre><code>a p p l e p e n _   
p e n a p p l e p e n _ 
</code></pre>
<p>and follow the merging order:</p>
<pre><code>(p, e), (pe, n), (pen, _), (a, p), (ap, p), (app, l), (appl, e), (apple, _), (pen, apple_)
</code></pre>
<p>First, (p, e). We merge p and e in the test data and get:</p>
<pre><code>a p p l e pe n _    
pe n a p p l e pe n _  
</code></pre>
<p>Second, the (pe, n) and get:</p>
<pre><code>a p p l e pen _    
pen a p p l e pen _ 
</code></pre>
<p>.....<br />
After all the 9 turns of merging we get(if k &lt;= 9 we just apply the first k merges in this step; if k is 2 refer to <a href="https://stackoverflow.com/a/68624271/3552975">this answer</a>):</p>
<pre><code>apple pen_    
pen apple pen_
</code></pre>
<p>And the final tokenized test sentence is [apple, pen_, pen, apple, pen_], and the unknown(unseen in the training data) word <code>penapplepen</code> can also be separated.</p>
<p>Referneces:</p>
<ol>
<li><a href="https://arxiv.org/pdf/1508.07909.pdf" rel="nofollow noreferrer">Neural Machine Translation of Rare Words with Subword Units</a></li>
<li><a href="https://web.stanford.edu/%7Ejurafsky/slp3/ed3book_dec302020.pdf" rel="nofollow noreferrer">Speech and Language Processing</a></li>
<li><a href="https://genius.com/Pikotaro-ppap-pen-pineapple-apple-pen-lyrics" rel="nofollow noreferrer">PPAP (Pen Pineapple Apple Pen)</a></li>
</ol>
Explain bpe (Byte Pair Encoding) with examples?
<p>Can somebody help to explain the basic concept behind the <strong>bpe model</strong>? Except <a href="https://arxiv.org/abs/1508.07909" rel="noreferrer">this paper</a>, there is no so many explanations about it yet.  </p>

<p>What I have known so far is that it enables NMT model translation on open-vocabulary by encoding rare and unknown words as sequences of subword units.</p>

<p>But I want to get a general idea of how it works without going through the paper.</p>