How to do Byte Pair Encoding bigram counting and replacements efficiently in Python?

Question

In the Byte Pair Encoding algorithm, there's a replacement step where it changes the character strings delimited by spaces to bigrams. I.e., given a list of `str` tuples as such: ``` [('t', 'h', 'i', 's', '\ue000'), ('c', 'o', 'r', 'p', 'u', 's', '\ue000'), ('i', 'n', '\ue000'), ('t', 'x', 't', 'f', 'i', 'l', 'e', '\ue000'), ('t', 'h', 'e', '\ue000'), ('s', 'e', 'n', 't', 'e', 'n', 'c', 'e', '\ue000'), ('b', 'a', 'r', '\ue000'), ('a', 'n', 'd', '\ue000'), ('i', 's', '\ue000'), ('f', 'o', 'o', '\ue000'), ('f', 'i', 'r', 's', 't', '\ue000'), ('a', '\ue000'), ('.', '\ue000')] ``` And a string tuple: `('i', 's')` How do I process the list such that it iterates through all the tuple keys and and replace `('i', 's')` with `('is')`?, i.e. the output `Counter` will look something like this: ``` [('t', 'h', 'is', '\ue000'), ('c', 'o', 'r', 'p', 'u', 's', '\ue000'), ('i', 'n', '\ue000'), ('t', 'x', 't', 'f', 'i', 'l', 'e', '\ue000'), ('t', 'h', 'e', '\ue000'), ('s', 'e', 'n', 't', 'e', 'n', 'c'…

Accepted Answer

If you keep your string tuple to length 2 you could use reduce like this:

```
def cons_2(word_list, t):
    j = ''.join(t)
    f = lambda acc, e: acc[:-1] + (j,) if (acc[-1] == t[0] and e == t[1]) else acc + (e,)
    return [reduce(f, i[1:], (i[0],)) for i in word_list]

print cons_2(cin, ('i', 's'))
```

No replacing is involved, `f` is applied for every element `i`, the value of `cin` is not altered instead a new array is made and returned.

Details:

- `reduce` applies `f` for every array element `i` and returns a value to the accumulator `acc`.

- parameters of reduce:

- `f`: function to apply.

- `i[1:]`: the array to iterate with all the elements but the first.

- `(i[0],)`: the initial value of the accumulator, it's a tuple with the first value of the input tuple `i`.

- `f`: is a `lambda` function with the accumulator `acc` and the current element `e` as inputs:

- If the last element of the accumulator is equal to the first element of the string tuple and the current element `e` is equal to the second element of the string tuple, then return the tuple: `acc[-1] + (j,)` else continue with a normal concatenation: `acc + (e,)`.

For string tuples > 2 the idea is the same but we have to manage the tuple's length `l`.

```
def cons_n(word_list, t):
    l = len(t)
    j = ''.join(t)
    f = lambda acc, e: acc[:-l] + (j, e,) if acc[-l:] == t or acc[:l] == t else acc + (e,)
    return [reduce(f, i[l:], (i[:l])) for i in word_list]

print cons_n(cin, ('i', 's'))
```

This should work with n-length string tuples.

Details:

- Same process as above but using `l`: reduce applies `f` to the rest of the elements `i[l:]` and the initial value of the accumulator is a tuple with the first `l` elements: `(i[:l])`.

- Check backward and forward for the `l` elements equal to the string tuple `t`, if true then add the tuple: `acc[:-l] + (j, e,)` else continue with normal concatenation: `acc + (e,)`.

This is a functional approach no data is modified but generated, so should be safe to have multiple processes at the same time (in theory, I'm no expert about the Python interpreter).

If the code above is too weird for people not into functional programming this is another approach:

```
def cons_n_iter(tuple_list, tuple_seq):
     jnt = ''.join(tuple_seq)
     lnt = len(tuple_seq)
     res = []
     for word in tuple_list:
         acc = (word[:lnt])
         for letter in word[lnt:]:
             if acc[-lnt:] == tuple_seq or acc[:lnt] == tuple_seq:
                 acc = acc[:-lnt] + (jnt, letter,)
             else:
                 acc += (letter,)
         res += (acc,)
     return res

print cons_n_iter(cin, ('i', 's'))
```

The logic is the same as the functional approach, same use of the accumulator. In this case the `res` accumulator is explicit because in the examples above `reduce` was taking care of it.

How to do Byte Pair Encoding bigram counting and replacements efficiently in Python?

Solution

Problem

Related problems