<commit_before>---
title: (Pretty) Fast $n$-Gram Features with Python
date: 2015-12-02 00:08:59
read: 5
---

Recently I have been experimenting with (pretty) fast $n$-gram extraction for feature space construction. As I have clearly experienced, there are a bunch of caveats while building your own functions. This blog post gives a *very* short introduction to $n$-grams, explains their extraction in examples as well as in code (section 2). And finally gives a very effective and low memory footprint method of extracting them (section 3).

![img](https://raw.githubusercontent.com/cmry/cmry.github.io/9996cb863ab4eb4f7abdb0b55a06a3839d142ab9/assets/img/gram-mast.jpg)

## Extracting $n$-Grams

The extraction of $n$-grams is a commonly used as a so-called bag-of-words
method used in [Natural Language Processing](https://en.wikipedia.org/wiki/Natural_language_processing)
(NLP) to represent a collection of documents. In a very basic example we
want to either distinguish or relate sentence $A$, $B$, and $C$ which are
the following:

``` python
A = 'text about stuff'
B = 'stuff about text'
C = 'text about n-grams'
```

The $n$ in $n$-grams typically refers to a *scope*. One can look at it as going
over the sentence with a window of some size. So with a 1-gram (referred to as
a unigram) we partition the text in chunks of size one. So sentence $A$ would
give us `text`, `about`, and `stuff`. If we would put this into a matrix of
gram * sentence, we would get the following for the three sentences:

|             | $A$    | $B$    | $C$    |
| ----------- |:------:|:------:|:------:|
| text        | 1      | 1      | 1      |
| about       | 1      | 1      | 1      |
| stuff       | 1      | 1      | 0      |
| n-grams     | 0      | 0      | 1      |

Looking at the matrix, one can quickly see that despite the *order* of words,
sentence $A$ and $B$ look the same. If we take their vector they can be observed
to be identical:

$\vec{A} = [1, 1, 1, 0], \vec{B} = [1, 1, 1, 0]$

This is is what it means to have a bag-of-words. Words are thrown into a bag,
scrambled in any order and counted. Order does not matter to the model. So how
can we incorporate some structure into it? Taking word bi-grams, where
$n = 2$ would probably already help our case. Consider:<commit_msg>added small quote to ngram<commit_after>---
title: (Pretty) Fast $n$-Gram Features with Python
date: 2015-12-02 00:08:59
read: 5
---

Recently I have been experimenting with (pretty) fast $n$-gram extraction for feature space construction. As I have clearly experienced, there are a bunch of caveats while building your own functions. This blog post gives a *very* short introduction to $n$-grams, explains their extraction in examples as well as in code (section 2). And finally gives a very effective and low memory footprint method of extracting them (section 3).

![img](https://raw.githubusercontent.com/cmry/cmry.github.io/9996cb863ab4eb4f7abdb0b55a06a3839d142ab9/assets/img/gram-mast.jpg)

## Extracting $n$-Grams

The extraction of $n$-grams is a commonly used as a so-called *bag-of-words*
method used in [Natural Language Processing](https://en.wikipedia.org/wiki/Natural_language_processing)
(NLP) to represent a collection of documents. In a very basic example we
want to either distinguish or relate sentence $A$, $B$, and $C$ which are
the following:

``` python
A = 'text about stuff'
B = 'stuff about text'
C = 'text about n-grams'
```

The $n$ in $n$-grams typically refers to a *scope*. One can look at it as going
over the sentence with a window of some size. So with a 1-gram (referred to as
a unigram) we partition the text in chunks of size one. So sentence $A$ would
give us `text`, `about`, and `stuff`. If we would put this into a matrix of
gram * sentence, we would get the following for the three sentences:

|             | $A$    | $B$    | $C$    |
| ----------- |:------:|:------:|:------:|
| text        | 1      | 1      | 1      |
| about       | 1      | 1      | 1      |
| stuff       | 1      | 1      | 0      |
| n-grams     | 0      | 0      | 1      |

> Read as: the gram `text` occurs in text $A$ one time, while `n-grams` does
not occur in $A$. 

Looking at the matrix, one can quickly see that despite the *order* of words,
sentence $A$ and $B$ look the same. If we take their vector they can be observed
to be identical:

$\vec{A} = [1, 1, 1, 0], \vec{B} = [1, 1, 1, 0]$

This is is what it means to have a bag-of-words. Words are thrown into a bag,
scrambled in any order and counted. Order **does not matter** to the model. So
how can we incorporate some structure into it? Taking word bi-grams, where
$n = 2$ would probably already help our case. Consider:
{'fraction_non_alphanumeric': 0.11264906303236798, 'fraction_numerical': 0.026405451448040886, 'mean_word_length': 3.0283018867924527, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 4, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5294955', 'n_tokens_mistral': 1550, 'n_tokens_neox': 1399, 'n_words': 679}