computer science

N-gram

N-gram is a computer science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand N-gram rather than just read about it. In short: An n-gram is a sequence of n adjacent symbols in a particular order. The symbols may be n adjacent letters (including punctuation marks and blanks), syllables, or rarely whole words found in a language dataset; or adjacent phonemes extracted from a speech-recording dataset, or adjacent base pairs extracted from a genome.

Key takeaways

N-gram belongs to computer science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect N-gram to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of N-gram from memory before moving on to harder problems.

Reference excerpt

An n-gram is a sequence of n adjacent symbols in a particular order. The symbols may be n adjacent letters (including punctuation marks and blanks), syllables, or rarely whole words found in a language dataset; or adjacent phonemes extracted from a speech-recording dataset, or adjacent base pairs extracted from a genome. They are collected from a text corpus or speech corpus. If Latin numerical prefixes are used, then n-gram of size 1 is called a "unigram", size 2 a "bigram" (or, less commonly, a "digram") etc. If, instead of the Latin ones, the English cardinal numbers are furtherly used, then they are called "four-gram", "five-gram", etc. Similarly, Greek numerical prefixes such as "monomer", "dimer", "trimer", "tetramer", "pentamer", etc., or English cardinal numbers, "one-mer", "two-mer", "three-mer", etc. are used in computational biology for polymers or oligomers of a known size, called k-mers. When the items are words, n-grams may also be called shingles. In the context of natural language processing (NLP), the use of n-grams allows bag-of-words models to capture information such as word order, which would not be possible in the traditional bag of words setting.

Examples In 1951, Shannon discussed n-gram models of English. For example:

3-gram character model (random draw based on the probabilities of each trigram): in no ist lat whey cratict froure birs grocid pondenome of demonstures of the retagin is regiactiona of cre 2-gram word model (random draw of words taking into account their transition probabilities): the head and in frontal attack on an english writer that the character of this point is therefore another method for the letters that the time of who ever told the problem for an unexpected

Figure 1 shows several example sequences and the corresponding 1-gram, 2-gram and 3-gram sequences. Here are further examples; these are word-level 3-grams and 4-grams (and counts of the number of times they appeared) from the Google n-gram corpus. 3-grams

ceramics collectables collectibles (55) ceramics collectables fine (130) ceramics collected by (52) ceramics collectible pottery (50) ceramics collectibles cooking (45) 4-grams

serve as the incoming (92) serve as the incubator (99) serve as the independent (794) serve as the index (223) serve as the indication (72) serve as the indicator (120)

See also Google Books Ngram Viewer

References

Further reading Manning, Christopher D.; Schütze, Hinrich (1999). Foundations of statistical natural language processing. Cambridge, Mass: MIT Press. ISBN 978-0-262-13360-9. White, Owen; Dunning, Ted; Sutton, Granger; Adams, Mark; Venter, J. Craig; Fields, Chris (1993). "A quality control algorithm for dna sequencing projects". Nucleic Acids Research. 21 (16): 3829–3838. doi:10.1093/nar/21.16.3829. PMC 309901. PMID 8367301. Damerau, Frederick J. (1971). Markov Models and Linguistic Theory. The Hague: Mouton. OCLC 200370. Figueroa, Alejandro; Atkinson, John (2012). "Contextual Language Models For Ranking Answers To Natural Language Definition Questions". Computational Intelligence. 28 (4): 528–548. doi:10.1111/j.1467-8640.2012.00426.x. Brocardo, Marcelo Luiz; Traore, Issa; Saad, Sherif; Woungang, Isaac (2013). "Authorship verification for short messages using stylometry". 2013 International Conference on Computer, Information and Telecommunication Systems (CITS). pp. 1–6. doi:10.1109/CITS.2013.6705711. ISBN 978-1-4799-0168-5.

External links Ngram Extractor: Gives weight of n-gram based on their frequency. Google's Google Books n-gram viewer and Web n-grams database (September 2006) STATOPERATOR N-grams Project Weighted n-gram viewer for every domain in Alexa Top 1M 1,000,000 most frequent 2,3,4,5-grams from the 425 million word Corpus of Contemporary American English Peachnote's music ngram viewer Stochastic Language Models (n-Gram) Specification (W3C) Michael Collins's notes on n-Gram Language Models OpenRefine: Clustering In Depth

Worked examples

Example 1 — a first encounter with N-gram

Start with the simplest possible case. Write down what N-gram claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In computer science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to N-gram before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about N-gram ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of N-gram

In research: N-gram appears in computer science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses N-gram in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: N-gram is common in secondary-school and first-year university syllabi. It links to neighbouring topics Computational linguistics, Corpus linguistics, Language modeling, so understanding it makes those chapters shorter.
In everyday life: Look for N-gram outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study N-gram in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what N-gram means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain N-gram out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is N-gram in simple terms?

Why does N-gram matter?

Because it connects several computer science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study N-gram?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on N-gram.