3.2.1 Tokenization for biomedical text

In this section, we use biomedical text as an example of how domain-dependent tokenization can be done and the impact it has on downstream tasks. Biomedical text can be regarded as a sublanguage because it is substantially different than documents written in general language. The former contains more syntactic use of word-internal punctuation, such as “/” (forward slash) and “-” (dash) among the biomedical terms (Temnikova et al. Reference Temnikova, Nikolova, Baumgartner, Angelova and Cohen2013). This phenomenon applies not only in English but also in other languages such as Bulgarian, French, and Romanian (Névéol et al. Reference Névéol, Robert, Anderson, Cohen, Grouin, Lavergne, Rey, Rondet and Zweigenbaum2017; Mitrofan and Tufiş Reference Mitrofan and Tufiş2018). Moreover, Grön and Bertels (Reference Grön and Bertels2018) showed that many errors in processing biomedical clinical text are due to missing white space or nonstandard use of punctuation, such as “2004:hysterectomie” and “2004 : hysterectomie”. A custom script for postprocessing can reduce the tokenization errors, after the corpus of electronic health records is divided into words using the NLTK tokenizer. Figure 2 illustrates that the percentage of tokenization errors is reduced in the sections of complaints, anamnesis, history, examination, conclusion, and comments. The data are from Table 1 in Grön and Bertels (Reference Grön and Bertels2018). The postprocessing includes Greek letter normalization and break point identification (Jiang and Zhai Reference Jiang and Zhai2007). For instance, “MIP-1- $\alpha$ ” and “MIP-1 $\alpha$ ” should both tokenize to “MIP 1 alpha”. Note that the hyphen does more than separating elements in a single entity, so simply removing it is not always appropriate. The hyphen in parentheses “(-)” can also indicate a knocked-out gene, such as “PIGA (-) cells had no growth advantage” in Cohen et al. (Reference Cohen, Ogren, Fox and Hunter2005).

Table 1. Number and percentage of false positives for each type of pattern matching. The data are from Table 3 in Cohen et al. (Reference Cohen, Acquaah-Mensah, Dolbey and Hunter2002), and the rows after the first one refer to the extra tokens discovered beyond strict pattern matching

Trieschnigg et al. (Reference Trieschnigg, Kraaij and de Jong2007) also pointed out that tokenization decisions can contribute more to system performance than the text model itself. The text string “NF- $\kappa$ B/CD28-responsive” has at least 12 different tokenization results, depending on the preprocessing techniques used. The various approaches in tokenization resulted in up to 46 percent difference in the precision for document retrieval. The baseline version “nf $\kappa$ b cd responsive” keeps only lowercase letters without numbers, and this achieves 32 percent precision in document retrieval. Another version “NF- $\kappa$ B/CD28-responsive” has only 17 percent, where the text string is separated by white space without further normalization. A custom tokenizer result “nf kappa nfkappa b cd 28 respons bcd28respons” has 40 percent precision, which is the highest among the 12 combinations attempted by Trieschnigg et al. (Reference Trieschnigg, Kraaij and de Jong2007). The last version replaces Greek letters with their English names and stems the word from “response” to “respons”. This version also regards “nf”, “kappa”, and “nfkappa” as different tokens to increase the likelihood of getting a match. The same applies to the separate tokens “b”,“cd”, “28”, “respons”, and the combined token “bcd28respons”. In addition to precision, we should also examine the recall to capture as many relevant gene names as they exist in the biomedical corpus.

Biomedical information retrieval often incorporates approximate string matching (a.k.a. fuzzy matching) for gene names (Morgan et al. Reference Morgan, Lu, Wang, Cohen, Fluck, Ruch, Divoli, Fundel, Leaman and Hakenberg2008; Cabot et al. Reference Cabot, Soualmia, Dahamna and Darmoni2016), because this allows small variations to be considered as the same gene name. Verspoor, Joslyn, and Papcun (Reference Verspoor, Joslyn and Papcun2003) discovered that approximately 6 percent of gene oncology terms are exact matches in the biomedical text, showing the necessity of non-exact matches to find the remaining 94 percent. For example, Figure 3 depicts that tokenization choices of the gene name “alpha-2-macroglobulin” lead to different results of pattern matching in biomedical text. With a strict pattern matching heuristic, there were 1846 gene names found in the corpus. Then, more flexible pattern matching methods can find additional gene names and increase the recall. For instance, the case-insensitive heuristic found an extra 864 gene names, and the vowel sequence heuristicFootnote 6 discovered an extra 586 matches. The data in Figure 3 are from Table 2 in Cohen et al. (Reference Cohen, Acquaah-Mensah, Dolbey and Hunter2002), and the concern of low precision (i.e., false positives) can be mitigated by discarding weaker matches. For each type of pattern matching used, Table 1 lists the number and percentage of false positives in the discovered tokens. The data are from Table 3 in Cohen et al. (Reference Cohen, Acquaah-Mensah, Dolbey and Hunter2002), and the rows after the first one refer to the extra tokens discovered beyond strict pattern matching. Most pattern matching schemes generated fewer than one-third of false positives, except that the vowel sequence heuristic produced 85% of false positives.

Figure 3. Tokenization decisions in the gene “alpha-2-macroglobulin” lead to different pattern matching results. The data are from Table 2 in Cohen et al. (Reference Cohen, Acquaah-Mensah, Dolbey and Hunter2002).

Approximate string matching in tokenization is also helpful in NER of biomedical and chemical terms (Akkasi et al. Reference Akkasi, Varoğlu and Dimililer2016; Bhasuran et al. Reference Bhasuran, Murugesan, Abdulkadhar and Natarajan2016; Kaewphan et al. Reference Kaewphan, Mehryary, Hakala, Salakoski and Ginter2017), but the tokenization methods still have room for improvement. Both Cohen et al. (Reference Cohen, Tanabe, Kinoshita and Hunter2004) and Groza and Verspoor (Reference Groza and Verspoor2014) show that choices in handling punctuation affect the tokenization results and eventually affect NER as well. Term variation can easily result in poor results of biomedical concept recognition, especially in noncanonical forms. A slight change such as “apoptosis induction” versus “induction of apoptosis” can result in the two entities being assigned into different equivalence classes (Cohen et al. Reference Cohen, Roeder, Baumgartner, Hunter and Verspoor2010).

Pretrained word embeddings for biomedical text are gradually increasing in popularity (Wang et al. Reference Wang, Liu, Afzal, Rastegar-Mojarad, Wang, Shen, Kingsbury and Liu2018), and one example is the BioBERT (Lee et al. Reference Lee, Yoon, Kim, Kim, Kim, So and Kang2020), which is pretrained on PubMed abstracts and PMC (PubMed Central) articles. Since different language models have different requirements on letter casing and punctuation, the BERT model (Devlin et al. Reference Devlin, Chang, Lee and Toutanova2018) supports multiple variants of input catering to various NLP applications (Ek, Bernardy, and Chatzikyriakidis Reference Ek, Bernardy and Chatzikyriakidis2020). Nevertheless, researchers still need to tokenize biomedical text into words before they can leverage pretrained embeddings and do it in accordance with the preprocessing protocol used in preparing the embedding training corpus (Corbett and Boyle Reference Corbett and Boyle2018; Pais et al. Reference Pais, Ion, Avram, Mitrofan and Tufis2021). Another challenge in leveraging these pretrained word embeddings is that word vectors may not reflect the internal structure of the words. For instance, the related words “deltaproteobacteria” and “betaproteobacteria” should be close (but not too close) in the embedding space; however, this relationship is not accounted for in the word2vec or GloVe models. Zhang et al. (Reference Zhang, Chen, Yang, Lin and Lu2019) proposed BioWordVec to leverage the subword information in pretraining, allowing the model to better predict new vocabulary from the subwords in the corpus.

3.2.2 Tokenization for various natural languages

Beyond general English and biomedical texts, tokenizing non-English corpora also has challenges that can affect the text mining performance. Most languages have compound terms that span multiple tokens, such as “sin embargo” (however) in Spanish and “parce que” (because) in French (Grana, Alonso, and Vilares Reference Grana, Alonso and Vilares2002). Habert et al. (Reference Habert, Adda, Adda-Decker, de Marëuil, Ferrari, Ferret, Illouz and Paroubek1998) applied eight different tokenization methods on a French corpus of size 450,000 and attempted to concatenate the compound terms (see Section 3.7 for multiword expressions). The number of words in the corpus differed by more than 10 percent, while the number of sentences could range from approximately 14,000 to more than 33,000. French also has contractions similar to English (e.g. “don’t” means “do not”) (Hofherr Reference Hofherr and Ackema2012). The article “l” (the) can be attached to the following noun, such as “l’auberge” (the hostel). The preposition “d” (of) works similarly, such as “noms d’auberge” (names of hostels). More details on handling word-internal punctuation will be discussed in Section 3.4.2.

Consider the case of Arabic tokenization. In Arabic, a single word can be segmented into at most four independent tokens, including prefix(es), stem, and suffix(es) (Attia Reference Attia2007). One example is the Arabic word “ ” (“and our book”, or “wktAbnA” as the Buckwalter transliteration). This word is separated into three tokens: the prefix “” “w” (and), the stem “” “ktAb” (book), and a possessive pronoun “‘nA” (our) (Abdelali et al. Reference Abdelali, Darwish, Durrani and Mubarak2016). Note that Arabic writes from right to left, so the first token starts from the rightmost part of the word (Aliwy Reference Aliwy2012). Most text preprocessing systems now have a simple configuration for right-to-left languages (Litvak and Vanetik Reference Litvak and Vanetik2019), and the Python NLTK module nltk.corpus.reader.udhr supports major right-to-left languages including Arabic and Hebrew.Footnote 7

It is challenging to tokenize CJK languages because they use characters rather than letters, and each language contains thousands of characters (Zhang and LeCun Reference Zhang and LeCun2017). As a result, CJK tokenizers often encounter the OOV problem, and it is possible to get OOV characters as well as OOV words (Moon and Okazaki Reference Moon and Okazaki2021). Plus, CJK languages do not contain white space as obvious word boundaries in the corpus (Moh and Zhang Reference Moh and Zhang2012). Researchers have attempted to mitigate these problems by borrowing information from a parallel corpus of another language, commonly in multilingual corpora for translation (Luo, Tinsley, and Lepage Reference Luo, Tinsley and Lepage2013; Zhang and Komachi Reference Zhang and Komachi2018). Thanks to recent advances in neural networks and pretrained models like BERT (Devlin et al. Reference Devlin, Chang, Lee and Toutanova2018), there has been progress in identifying CJK words that span multiple characters (Hiraoka, Shindo, and Matsumoto Reference Hiraoka, Shindo and Matsumoto2019). Moreover, tokenization results can be improved by leveraging subword information within the same language (Moon and Okazaki Reference Moon and Okazaki2020), and even subword pooling from other similar languages (Ács, Kádár, and Kornai Reference Ács, Kádár and Kornai2021). Tokenization in multiple languages helps not only in machine translation (Domingo et al. Reference Domingo, Garca-Martnez, Helle, Casacuberta and Herranz2018) but also in adversarial text generation (Li et al. Reference Li, Shao, Song, Qiu and Huang2020).

3.4.1 Separating punctuation from strings

Researchers often need to separate punctuation from strings in text preprocessing—not only to obtain the words but also to retrieve the syntactic information conveyed in the punctuation (Nunberg Reference Nunberg1990; Briscoe Reference Briscoe1996). For example, in the sentence “We sell cars, scooters, and bikes.”, the two commas separate the noun objects and the period indicates the end of the sentence. This shows that punctuation provides grammatical information to POS tagging (Olde et al. Reference Olde, Hoeffner, Chipman, Graesser and Research Group1999). Note that inconsistent use of punctuation can be worse than no punctuation (Bollmann Reference Bollmann2013), and in this case, discarding punctuation is preferable. Furthermore, using punctuation to separate text into shorter strings is helpful in machine translation, especially for long and complicated sentences (Yin et al. Reference Yin, Ren, Jiang and Kuroiwa2007). Parsing punctuation as part of input not only improves the quality of translation between European languages (Koehn, Arun, and Hoang Reference Koehn, Arun and Hoang2008) but also provides bilingual sentence alignment for a Chinese-English corpus (Yeh Reference Yeh2003).

We would like to highlight the application of discourse parsing, because this is a difficult research problem central to many tasks such as language modeling, machine translation, and text categorization (Joty et al. Reference Joty, Carenini, Ng and Murray2019). Discourse parsing needs the punctuation information to identify the relations between segments of text (Ji and Eisenstein Reference Ji and Eisenstein2014). Punctuation marks can serve as discourse markers to separate a text string into shorter parts, along with many conjunction words (Marcu Reference Marcu2000). A sentence with or without sentence-internal punctuation can have different meanings, and here is an example from Truss (Reference Truss2004): “A panda eats shoots and leaves.” means that a panda eats shoots and also eats leaves. But the sentence with a comma, “A panda eats, shoots and leaves.”, means that a panda eats something, shoots a gun, and leaves the scene. Figure 4(a) and (b) depict the two hierarchical structures, respectively. The syntactic structure from punctuation feeds into discourse structure (Venhuizen et al. Reference Venhuizen, Bos, Hendriks and Brouwer2018). For more complicated text structures, Ghosh et al. (Reference Ghosh, Johansson, Riccardi and Tonelli2011) leveraged a cascade of conditional random fields to automate discourse parsing, based on different sets of lexical, syntactic, and semantic characteristics of the text.

Figure 4. Hierarchical structure of a sentence with or without a comma. The sentence example is from Truss (Reference Truss2004).

Another issue we would like to discuss is the challenge of parsing nonstandard use of punctuation in social media text (Farzindar and Inkpen Reference Farzindar and Inkpen2020). Text messages often contain repeated punctuation such as “!!” and “??”, and these symbols are typically used as an emphasis of emotion, without adding extra lexical information (Liu and Jansen Reference Liu and Jansen2013). This emotional context is helpful in sentiment analysis (Rosenthal and McKeown Reference Rosenthal and McKeown2013), while in many other applications, it is acceptable to map repeated punctuation to a single one (Verma and Marchette Reference Verma and Marchette2019). We also need to be careful in processing emoticons because each of them should be assigned to a token, rather than being separated into characters (Rahman Reference Rahman2017). We recommend starting with a predefined list of emoticons to identify them in the text corpus, and one example list is available on Wikipedia.Footnote 8 Emoticons that contain all punctuation are easier to detect, such as “:)” and “:-(”. On the other hand, emoticons that contain both letters and punctuation are relatively harder to detect, such as “:p” and “;D” (Clark and Araki Reference Clark and Araki2011). In addition, the symbol @ can be part of an emoticon “@_@” or can be used as a mention to another user on social media. Similarly, the symbol # can be part of another emoticon “#)” or serve as the start of a hashtag. More about mentions (@username) and hashtags (#hashtag) will be discussed in Section 4.2.

Finally, if researchers are unsure whether the information from punctuation would be needed in their NLP work, we recommend separating punctuation from strings first. In this way, researchers still have the option to remove the punctuation tokens later. In comparison, if researchers remove punctuation from the corpus in the beginning, it is much harder to restore the punctuation unless they are willing to restart from the raw data.

3.4.2 Removing punctuation

Removing punctuation generally simplifies the text analysis and allows researchers to focus on words in the text corpus (Gentzkow, Kelly, and Taddy Reference Gentzkow, Kelly and Taddy2017; Denny and Spirling Reference Denny and Spirling2018). According to Carvalho, de Matos, and Rocio (Reference Carvalho, de Matos and Rocio2007), removing punctuation improves the performance of information retrieval. In NLP applications where punctuation is not of primary interest, it is easier to remove punctuation from the corpus than to normalize the nonstandard usage of punctuation for consistency (Cutrone and Chang Reference Cutrone and Chang2011; Fatyanosa and Bachtiar Reference Fatyanosa and Bachtiar2017). This is why many introductory books on NLP include removing punctuation as an early step of text preprocessing (Dinov Reference Dinov2018; Kulkarni and Shivananda Reference Kulkarni and Shivananda2019).

Moreover, many text mining models do not handle nonword characters well, so removing these characters beforehand is helpful in such situations. For instance, word2vec (Mikolov et al. Reference Mikolov, Chen, Corrado and Dean2013) takes a text corpus as input and produces efficient word representations in vector space, but word2vec does not support punctuation due to the optimized design toward words. Even when a text mining model allows nonword characters, it treats a word with punctuation as a different token than the same word without punctuation. Hence, the punctuation symbols can hurt the performance of modern parsers. The problem is that when punctuation exists in the input text, many parsers heavily rely on this feature, making it difficult to handle sentences with nonstandard use of punctuation. As a result, prediction suffers from punctuation inconsistency, and previous researchers have referred to the situation as “a nightmare at test time” (Søgaard, de Lhoneux, and Augenstein Reference Søgaard, de Lhoneux and Augenstein2018). Removing punctuation as feature deletion improves the robustness of a model (Globerson and Roweis Reference Globerson and Roweis2006).

Nevertheless, removing punctuation also removes the underlying semantic information from the corpus, which can have a negative effect on some NLP applications. In sentiment analysis, emotions in a sentence can be expressed from different punctuation, so removing punctuation would have a negative effect on the analysis results (Effrosynidis, Symeonidis, and Arampatzis Reference Effrosynidis, Symeonidis and Arampatzis2017). For example, “He liked the cake!” is different than “He liked the cake?”. Generally,“!” expresses a stronger emotion, while “?” often reverses the intention of the sentence. Wang et al. (Reference Wang, Liu, Song and Lu2014a) built a model using both words and punctuation to identify product reviews as positive or negative, and the model performed better than using only words without punctuation. In digital forensics, punctuation is also an important feature for authorship identification. The ALIAS (Automated Linguistic Identification and Assessment System) methodology performs many computation linguistic calculations to distinguish text written by different authors, and one aspect is the frequency and types of punctuation (Craiger and Shenoi Reference Craiger and Shenoi2007). A sentence in quotation marks can refer to a conversation or a quote from existing literature, so the writing style in that sentence can be highly different from the author’s usual style. This information can be used to determine who said what (Pareti et al. Reference Pareti, O’Keefe, Konstas, Curran and Koprinska2013), and Thione and van den Berg (Reference Thione and van den Berg2007) developed a US patent to use the quotation marks in text for speaker attribution.

If researchers decide to remove punctuation from the text corpus, a straightforward way to do so is using regular expressions. This is part of string processing in almost all programming languages. A starting list is the ASCII printable characters,Footnote 9 which consist of a white space, punctuation, uppercase English letters, lowercase English letters, and the numbers 0–9. Note that different languages have different space characters (e.g., Chinese vs. English) (Craven Reference Craven2004). In Python, the code from string import punctuation provides a string of commonly used punctuation symbols, including the open and close brackets. In $\mathsf{R}$ , the regular expression [:punct:] from the function grep also gives the same set of punctuation symbols as Python does. The $\mathsf{R}$ package tm (Feinerer and Hornik Reference Feinerer and Hornik2018) has a function removePunctuation for easy implementation.

We need to be careful in treating word-internal punctuation, especially contractions (e.g., “you’re” vs. “you are”). Although most contractions drop out during the stopword removal phase since they are stopwords, some contractions have non-ignorable semantic meaning (e.g., “n’t” means “not”). Python NLTK includes the package contractions to split contracted words, and GutenTagFootnote 10 as an extension toolkit makes it possible to preserve within-word hyphenations and contractions (Brooke, Hammond, and Hirst Reference Brooke, Hammond and Hirst2015). We can also map contractions into their non-contracted forms (e.g., map “don’t” into “do not”) using a predefined list,Footnote 11 and this is beneficial to negation handling (Anderwald Reference Anderwald2003). For higher precision of contraction-splitting, we can use the Python library pycontractions (Beaver Reference Beaver2019) to incorporate context to determine the original form of ambiguous contractions. For example, the sentence “I’d like to know how I’d done that!” contains two “I’d”—the first one is from “I would” and the second one is from “I had”. However, many researchers remove punctuation without handling the contractions (Battenberg Reference Battenberg2012; Soriano, Au, and Banks Reference Soriano, Au and Banks2013; Xue et al. Reference Xue, Chen, Hu, Chen, Zheng and Zhu2020), so the demonstrations in this article do not include the contraction-mapping step.

3.5.1 Existing stopword lists

According to Manning et al. (Reference Manning, Raghavan and Schütze2008), most researchers use a predefined stopword list to filter out the general stopwords, and the list typically includes fewer than 1000 words in their surface forms. For instance, “have” and “has” count as two separate stopwords in the list. Shorter lists include the Python NLTK (127 English stopwords) (Bird et al. Reference Bird, Loper and Klein2009) and the $\mathsf{R}$ package stopwords (175 stopwords) (Benoit, Muhr, and Watanabe Reference Benoit, Muhr and Watanabe2017). For longer lists, the Onix Text Retrieval Toolkit (Lextek International n.d) provides two versions—one with 429 words and the other with 571 words, where both lists are available in the $\mathsf{R}$ package lexicon (Rinker Reference Rinker2018a). Although Atwood (Reference Atwood2008) optimized the SQL query performance for information retrieval by removing the 10,000 most common English words from their corpus, this is an extreme case and we do not recommend removing so many stopwords. Schofield, Magnusson, and Mimno (Reference Schofield, Magnusson and Mimno2017) showed that a list of approximately 500 stopwords would already remove 40–50 percent of the corpus. Zipf (Reference Zipf1949) showed that the distribution of words is right-skewed, and that the word with the nth highest frequency is expected to appear only $1/n$ times as likely as the word with the highest frequency. Figure 5 is an illustration of the Zipf’s law, assuming that the most frequent word appears 1 million times in a hypothetical corpus. Zhang (Reference Zhang2008) and Corral, Boleda, and Ferrer-i Cancho (Reference Corral, Boleda and Ferrer-i Cancho2015) also show that stopwords are often the most common words in the corpus, which applies to most languages like English, French, or Finnish.

Figure 5. Illustration of the Zipf’s law (Zipf Reference Zipf1949).

An existing list often serves as a starting point for removing stopwords, and many researchers modify the list before use (Blanchard Reference Blanchard2007; Heimerl et al. Reference Heimerl, Lohmann, Lange and Ertl2014), in order to optimize text mining results (Amarasinghe, Manic, and Hruska Reference Amarasinghe, Manic and Hruska2015). For instance, since the list contains several words for negation (e.g., “no”, “not”), removing these words would alter the meaning of the context. Then the negation words should be excluded from the stopword list, and more details are discussed in Section 3.5.2. In addition to standard stopword lists, alternative options include publicly available e-books, such as Alice’s Adventures in Wonderland by Lewis Carroll, which can be used as a benchmark corpus to filter out nontechnical words from a technical database (Brooke et al. Reference Brooke, Hammond and Hirst2015). Project GutenbergFootnote 12 contains more than 60,000 e-books, whose US copyrights have expired.Footnote 13 Even better, this corpus is directly available in the $\mathsf{R}$ package gutenbergr (Robinson Reference Robinson2018). Good candidates for a stopword list should be a book of general content, so the technical words in the database would be more likely to stay. Since a book usually contains thousands of words, using one book as a stopword list would be sufficient. Choosing multiple books provides limited benefits because most general words (e.g., “where” and “say”) have already been removed by the first book.

There is a trade-off between using shorter stopword lists and longer ones, and it is up to the researchers to determine which works best for their text dataset. Using a shorter stopword list preserves more semantic information in the corpus, but the vocabulary size reduction may be insufficient. Using a longer stopword list further reduces the data, but words with potentially important information may also be accidentally eliminated from the corpus. Since words removed at the beginning would not return to the scope of data analysis, we need to be more cautious in using a longer stopword list (Fox Reference Fox1989). Therefore, we recommend starting from a short stopword list to retain potentially important “stopwords”. If the text mining results contain too many irrelevant words, we can gradually remove them by adding more words to the stopword list. This is a reversible process because if we find key insights are missing in the new version of the corpus, we can always select an earlier version with a smaller amount words removed.

3.5.2 Known issues with removing stopwords

Even in NLP applications where removing stopwords is safe and appropriate, we need to remember that the removed stopwords are permanently excluded from the corpus and will not re-enter the model (Yang and Wilbur Reference Yang and Wilbur1996). Therefore, we have to beware of unintentional removal of important text information. Some phrases contain only stopwords, and the whole phrase is removed if we filter out stopwords at the beginning. Examples include the band “The The” and the phrase “to be or not to be” from Hamlet. Multiword expressions consisting of both stopwords and non-stopwords face a slightly better situation. For example, the novel title “Gone with the Wind” becomes “Gone Wind” after we remove stopwords—the phrase still exists, but it is no longer understandable.

Being able to find stopwords is crucial for titles, especially in a search engine for media and/or e-commerce content (Lazarinis Reference Lazarinis2007). Although information retrieval generally ignores stopwords (Singhal Reference Singhal2001), Google Search allows the user to put a phrase in quotation marks for exact matching,Footnote 14 and so do most other search engines (White and Morris Reference White and Morris2007; Wilson Reference Wilson2009). Hence in text preprocessing, when the subject indicates that the corpus may have stopword-formed phrases, n-gramming should be done first to preserve the semantic information of these phrases. Moreover, if the NLP application involves dependency parsing or semantic reasoning, we have to be careful in removing stopwords, especially prepositions (Hartrumpf, Helbig, and Osswald Reference Hartrumpf, Helbig and Osswald2006). For example, the sentence “The box is in the house, and the toy is in the box.” will mean something different if we remove both “in”s. Hansen et al. (Reference Hansen, Hansen, Simonsen and Lioma2018) suggested not removing stopwords at all in syntax dependency parsing, because they may contain important syntactic information for sentence structure.

Finally, researchers should exclude “no” and “not” from the stopword list, because filtering out negation terms often reverts the meaning of the whole phrase. For example, the sentence “Zach doesn’t know physics.” becomes “zach know physics” (opposite meaning) after we remove the stopwords. It is possible to retain semantic information through antonym replacement or bigram creation. For instance, “not good” can be replaced with “bad” or “not $\_$ good” (as a bigram) (Perkins Reference Perkins2014; Chai Reference Chai2017). However, neither approach is perfect because the scope of “not” may be different than the word immediately following the negation (Councill, McDonald, and Velikovich Reference Councill, McDonald and Velikovich2010). Consider the sentence “He was not driving the car and she left to go home.” If we simply invert “not drive”, we lose the context that someone else may be driving the car instead (Fancellu, Lopez, and Webber Reference Fancellu, Lopez and Webber2016). Automatically detecting the scope of negation is a challenging problem (Blanco and Moldovan Reference Blanco and Moldovan2011), and recent advances include using deep learning approaches (Qian et al. Reference Qian, Li, Zhu, Zhou, Luo and Luo2016) and bidirectional LSTM (Fancellu et al. Reference Fancellu, Lopez, Webber and He2017; Morante and Blanco Reference Morante and Blanco2021).

3.6.1 Comparison of stemming and lemmatization

Before we compare stemming and lemmatization, we need to distinguish between inflectional and derivational morphology. Inflectional morphology refers to the word modification for grammatical purposes (e.g., verb tense, singular or plural noun form), without changing the word’s meaning or POS (Baerman Reference Baerman2015). When we normalize the word “enjoyed” to its base form “enjoy”, we are removing the inflectional morpheme from the word. On the other hand, derivational morphology adds a morpheme to the word and changes its semantic meaning and/or its POS (Crystal Reference Crystal1999). When we normalize the word “enjoyable” (adjective) to its base form “enjoy” (verb), the removed suffix is derivational because it changed the word from a verb to an adjective.

Stemming uses rules to reduce each word to its root (stem), and this strips off both inflectional and derivational variations. For English words, a commonly used stemming method is the Porter algorithm (Porter Reference Porter1980), along with the $\mathsf{R}$ package SnowballC (Bouchet-Valat Reference Bouchet-Valat2019).Footnote 15 This algorithm implements suffix stripping rules for word reduction, such as replacing “ies” with “i” and removing the last “s” before a consonant other than “s” (making a plural noun singular). The Porter algorithm also uses regular expressions and determines which rule takes priority. For instance, “hopping” becomes “hop”, but “falling” becomes “fall”, not “fal”. Due to the removal of suffixes, some tokens are not valid words and look like typos, such as “enjoi” (enjoy) and “challeng” (challenge). Other stemming algorithms include the Lovins stemmer (Lovins Reference Lovins1968) and the Lancaster stemmer (Paice and Hooper Reference Paice and Hooper2005).

Lemmatization groups the inflectional forms of each word to its lemma (Sinclair Reference Sinclair2018), but lemmatization also considers the POS of the word (Bergmanis and Goldwater Reference Bergmanis and Goldwater2018) (e.g., noun, verb, adjective, or adverb). The WordNetLemmatizer package in Python NLTK analyzes the POS tag in a sentence input and lemmatizes each word, using the English lexical database WordNet.Footnote 16 The lemmatizer can also be used on isolated words by mapping to a single, most common lemma, or provide different outputs based on the specified POS tag. For instance, the word “leaves” can have the lemma “leave” (verb) or “leaf” (noun). Another example is mapping “better” and “best” to the same lemma “good”, which would not have been picked up by a stemmer. Lemmatization is especially useful in parsing morphologically rich languages, whose grammatical relations (e.g., subject, verb, object) are indicated by changes to the words (Tsarfaty et al. Reference Tsarfaty, Seddah, Goldberg, Kübler, Candito, Foster, Versley, Rehbein and Tounsi2010). Examples of such languages include Turkish, Finnish, Slovene, and Croatian (Gerz et al. Reference Gerz, Vulić, Ponti, Naradowsky, Reichart and Korhonen2018).

Lemmatization has a higher time complexity than stemming, but given modern big data technology, we do not need to be overly concerned about computational speed. Assume that the text corpus contains N words, and that each sentence has M words on average. Stemming takes O(N) time because the algorithm processes each word exactly once throughout the corpus. In comparison, lemmatization takes O(MN) time because the algorithm reads in the whole sentence to identify the context and POS tag beforehand. A compromise is context-free lemmatization, which produces the appropriate lemmas without using the whole context (Namly et al. Reference Namly, Bouzoubaa, El Jihad and Aouragh2020). By leveraging existing inflection tables, this method has achieved some success in English, Dutch, and German (Nicolai and Kondrak Reference Nicolai and Kondrak2016). Nevertheless, the actual computation time is often acceptable for either method. Mubarak (Reference Mubarak2017) lemmatized 7.4 million Arabic (a morphologically rich language) words on a personal laptop within 2 minutes, indicating that the computational speed is usually fast. Note that English has only eight inflectional morphemes,Footnote 17 and many researchers still use stemming for simplicity (Kao and Poteet Reference Kao and Poteet2007; Meyer, Hornik, and Feinerer Reference Meyer, Hornik and Feinerer2008).

3.6.2 Known issues

Neither stemming nor lemmatization is perfect. Both methods suffer from over-consolidation of words—assigning two word forms with clearly different meanings to the same token, such as mapping both “computer” and “computation” to the token “comput” (Jivani Reference Jivani2011). A known way to avoid over-consolidation is to use the lempos format (lemma with POS tag, e.g., “set $\_$ NOUN”), as implemented by Akhtar, Sahoo, and Kumar (Reference Akhtar, Sahoo and Kumar2017) and Ptaszynski et al. (Reference Ptaszynski, Lempa, Masui, Kimura, Rzepka, Araki, Wroczynski and Leliwa2019). Moreover, some words require context to determine its true base form or lemma. A fundamental question to ask is whether we should perform stemming and/or lemmatization in the first place. The answer would be “yes” in most cases, but depending on the goal of the text data mining project, we may have to reconsider the pros and cons of consolidating word forms before making the decision.

A risk of consolidating word forms is the loss of sentiment information (Haddi, Liu, and Shi Reference Haddi, Liu and Shi2013; Potts nd). Words of the same root can have different sentiments, but they are mapped to the same token. For example, both “objective” (positive) and “objection” (negative) are mapped to “object” under the Porter stemming algorithm. As a result, we do not know whether the token “object” indicates something positive or negative. Bao et al. (Reference Bao, Quan, Wang and Ren2014) also show that both stemming and lemmatization negatively affect Twitter sentiment classification. Even conservative lemmatization can have a negative impact on POS tagging and NER (Cambria et al. Reference Cambria, Poria, Gelbukh and Thelwall2017). Some named entities would not be recognizable after the corpus is lemmatized, such as the American rock band “Guns N’ Roses” versus “gun n rose”. Therefore, it is better to perform these NLP steps before we lemmatize the corpus.

Another risk is losing the spelling variation as a writing style element, which can be detrimental to authorship attribution (Stamatatos Reference Stamatatos2008). For instance, spelling discrepancies exist between American English and British English, such as “center” versus “centre” and “canceled” (one “l”) versus “cancelled” (two “l”s). Assume we have two documents—one in American English and the other in British English. The two documents should be written by different people, since it is unlikely that someone would use both forms in writing. But after we perform stemming/lemmatization and map each pair to the same token, we cannot distinguish between the two English variations. One potential solution is to identify the words with spelling variations and add an underline character to each word, making the stemmer/lemmatizer “think” they are different tokens. In this way, the algorithm would preserve these words in their original forms.

3.7.1 Constructing N-grams from a text document

We create n-grams as phrases of n consecutive words in a text document (Gries and Mukherjee Reference Gries and Mukherjee2010), using a moving window of length n across the text, that is, “shingling” (Broder et al. Reference Broder, Glassman, Manasse and Zweig1997; Huston, Culpepper, and Croft Reference Huston, Culpepper and Croft2014). We use the definition of word-based n-grams, which is different than the character-based n-gram definition, which refers to a string of n characters (Houvardas and Stamatatos Reference Houvardas and Stamatatos2006). Words are also called unigrams, while bigrams and trigrams denote the two-word and three-word phrases in the corpus, respectively.

A document consisting of n words would have n unigrams, $n-1$ bigrams, and $n-2$ trigrams. For example, the text “one should be humble while studying advanced calculus” contains eight unigrams, seven bigrams, and six trigrams as below:

• Unigrams: “one”, “should”, “be”, “humble”, “while”, “studying”, “advanced”, “calculus”

• Bigrams: “one should”, “should be”, “be humble”, “humble while”, “while studying”, “studying advanced”, “advanced calculus”

• Trigrams: “one should be”, “should be humble”, “be humble while”, “humble while studying”, “while studying advanced”, “studying advanced calculus”

The ordering of text preprocessing modules is key to success. Converting the string of text into unigrams is equivalent to tokenization (see Section 3.2), and this is a prerequisite for removing stopwords and n-gramming (Putra, Gunawan, and Suryatno Reference Putra, Gunawan and Suryatno2018; Chaudhary and Kshirsagar Reference Chaudhary and Kshirsagar2018). Note that this example inputs a full sentence in raw text, without stopword removal or stemming/lemmatization. As a result, the unigrams contain general stopwords such as “one” and “be”, which are not ideal. The unigram “studying” is not reverted to its base form “study”, either. That’s why removing stopwords and stemming/lemmatization are often performed before n-gramming (Anandarajan et al. Reference Anandarajan, Hill and Nolan2019; Arief and Deris Reference Arief and Deris2021), as illustrated in Figure 1.

In terms of semantic meaning, only the phrase “advanced_calculus” seems special enough to be a multiword expression because it is the name of a college-level class. We need systematic methods to determine which n-grams are multiword expressions and which are not (Baldwin and Kim Reference Baldwin and Kim2010). Moreover, n-gramming has limitations because some multiword expressions are not n consecutive words (i.e., n-grams). They may skip a few words in between and hence are called skip-grams (Guthrie et al. Reference Guthrie, Allison, Liu, Guthrie and Wilks2006). This reflects the challenge of modeling long-distance dependencies in natural languages (Deoras, Mikolov, and Church Reference Deoras, Mikolov and Church2011; Merlo Reference Merlo2019).

In general, multiword expressions should be both practically and statistically significant. Practical significance means that the phrase is of practical interest, that is, it occurs many times in the corpus. Rare phrases should be removed from the n-gram pool (Grobelnik and Mladenic Reference Grobelnik and Mladenic2004). On the other hand, statistical significance means that the words forming the multiword expression have a relatively high probability to stay together (Brown et al. Reference Brown, Desouza, Mercer, Pietra and Lai1992). Thus, a multiword expression should be an n-gram of statistical interest, rather than n words that just happen to appear together many times. Sections 3.7.2 and 3.7.3 will discuss the practical and statistical significance requirements for multiword expressions. This is by no means the only way to determine which n-grams are multiword expressions; other methods include finding the longest common subsequence (Duan et al. Reference Duan, Lu, Wu, Hu and Tian2006) and using linguistic features of each sentence (Boukobza and Rappoport Reference Boukobza and Rappoport2009).

3.7.2 Multiword expressions: Practical significance

For practical significance, the easiest way is to set a minimum frequency and consider any n-gram to be a multiword expression if its number of occurrences is higher than the cutoff (Wei et al. Reference Wei, Miao, Chauchat, Zhao and Li2009). Since general stopwords have been removed from the corpus, uninformative bigrams (e.g., “you are”, “is an”) are less likely to appear. The article “a”, “an”, or “the” often precedes a noun, and such bigrams (e.g., “the artist”) are not helpful, either. Setting a cutoff frequency ensures that the multiword expressions are of practical interest, and this approach has proven success in computational linguistics (Pantel and Pennacchiotti Reference Pantel and Pennacchiotti2006; Lahiri and Mihalcea Reference Lahiri and Mihalcea2013). As a note of caution, Wermter and Hahn (Reference Wermter and Hahn2005) showed that a high number of occurrences does not always mean the n-gram is a term, that is, a multiword expression with special meaning. An example is in the biomedical field, the phrase “t cell response” has a higher frequency than “long terminal repeat”, but the latter is a term while the former is not.

The cutoff frequency can be determined empirically, and Microsoft Azure Machine Learning Studio recommends a starting value of 5 as the minimum frequency for multiword expressions (Microsoft 2019). Previous researchers had success in using the cutoff frequency of 5, while they analyzed a corpus of 450 political blog posts, with around 289,000 total words at the time when the corpus was ready for n-gramming (Soriano et al. Reference Soriano, Au and Banks2013; Au Reference Au2014). Inevitably, a low threshold of minimum frequency results in a steep increase in computation time as the corpus gets larger due to the need of processing the massive number of low-frequency n-grams (Brants et al. Reference Brants, Popat, Xu, Och and Dean2007). The New York Times Annotated Corpus (Sandhaus Reference Sandhaus2008) contains more than 1.8 million newspaper articles and more than 1.05 billion words, so Berberich and Bedathur (Reference Berberich and Bedathur2013) set the cutoff frequency to 100. The ClueWeb09 dataset (Callan et al. Reference Callan, Hoy, Yoo and Zhao2009) is even larger, with more than 50 million web documents and more than 21.4 billion English words. Accordingly, Berberich and Bedathur (Reference Berberich and Bedathur2013) increased the cutoff frequency to 1000. The Google Syntactic Ngrams English corpus (Goldberg and Orwant Reference Goldberg and Orwant2013) consists of more than 345 billion words, and Ng, Bansal, and Curran (Reference Ng, Bansal and Curran2015) set the cutoff frequency to as high as 10,000.

The histograms of n-grams for each n are right-skewed (Ha et al. Reference Ha, Hanna, Ming and Smith2009; Bardoel Reference Bardoel2012). The distribution generally follows the power law (Jean-Baptiste Reference Jean-Baptiste1916; Newman Reference Newman2005), just like the illustration of Zipf’s law (Zipf Reference Zipf1949) in Figure 5. The vast majority of bigrams appear only once, and the phenomenon of trigrams is more extreme. Dressel (Reference Dressel2016) demonstrated that only 19 percent of the trigrams occurred more than once in their corpus before stopwords were removed. We also n-grammed the publicly available e-book Wuthering Heights from Project Gutenberg (Robinson Reference Robinson2018), which contains 120,772 total words and 9207 total distinct words in the corpus. Table 2 provides the n-gram statistics of Wuthering Heights: over a quarter of unigrams (words) appear 5 or more times in the corpus, so it is viable to further examine the frequency trends of the unigrams. For bigrams, more than three-quarters of them appear only once, leaving us with about a quarter of the unique bigrams to analyze. Finally, more than 90 percent of the trigrams and 4-grams appear only once in the corpus, showing that only a small percentage of longer n-grams may be of interest.

Table 2. The n-gram statistics of Wuthering Heights

Remark. N-grams should not be calculated over sentence boundaries (Buerki Reference Buerki2017), but Huston, Moffat, and Croft (Reference Huston, Moffat and Croft2011) showed that using sentence boundaries as separation can greatly reduce the number of 4-grams produced. Since the majority of longer n-grams will be dropped by the thresholding, empirically it does not matter whether sentence boundaries are considered in the n-gramming process.

3.7.3 Multiword expressions: Statistical significance

For statistical significance, we focus on conditional probability (Jurafsky and Martin Reference Jurafsky and Martin2008)—given one or more words, the probability of another word immediately following the sequence. In mathematical notation, a string of n words is written as $w_1 w_2 \cdots w_n$ . For the bigram $w_1 w_2$ , the conditional probability of $w_2$ following $w_1$ is

(1) \begin{equation}P(w_2 | w_1) = \dfrac{P(w_1 w_2)}{P(w_1)} = \dfrac{\text{Count}(w_1 w_2)}{\text{Count}(w_1)},\end{equation}

where the function Count(s) outputs the frequency of the word string s in the corpus.

Assuming the corpus contains N words, we have the probability of getting each word as $P(w) = \text{Count}(w)/N$ , and the probability of getting each bigram as $P(w v) = \text{Count}(w v)/(N-1)$ . The only difference is that the corpus contains $N-1$ bigrams. When N is sufficiently large, N and $N-1$ are asymptotically equal, so we do not make a distinction in calculating $P(w_2 | w_1)$ .

To determine whether the bigram $w_1 w_2$ is a multiword expression, we test against the two competing hypotheses:

• $H_0:\; P(w_2 | w_1) \leq P(w_2)$

• $H_1:\; P(w_2 | w_1) > P(w_2)$

The framework is adopted from Chai (Reference Chai2022). This is a one-sided hypothesis test because only a large $P(w_2 | w_1)$ is of interest. When the p-value is less than 0.05, we reject $H_0$ and conclude that $w_1 w_2$ is a multiword expression.

We can extend the bigram testing scheme to n-grams, but the conditional probability of seeing the nth word given the first $n-1$ words, $P(w_n | w_1 \cdots w_{n-1})$ , is unreasonable to compute. Chances are high that the $(n-1)$ word phrase appears only once in the corpus, making this conditional probability 100 percent, which is not what we are looking for. Instead, we can approximate the conditional probability with

(2) \begin{equation}P(w_n | w_1 \cdots w_{n-1}) \approx P(w_n | w_{n-1}) = \dfrac{\text{Count}(w_{n-1} w_n)}{\text{Count}(w_{n-1})},\end{equation}

where the Markov assumption states that $w_n$ depends on only the previous word $w_{n-1}$ (Fosler-Lussier Reference Fosler-Lussier1998; Tran and Sharma Reference Tran and Sharma2005). Then, the n-gramming question is reduced to whether $w_{n-1} w_n$ is a multiword expression, and the hypothesis testing framework still applies.

Many automated tools are available to perform n-gramming, but most of them simply pull all n-grams from the input text. For example, the function tokens_ngrams in the $\mathsf{R}$ package quanteda (Benoit et al. Reference Benoit, Watanabe, Wang, Nulty, Obeng, Müller and Matsuo2018) generates the n-grams, but this package does not provide support for how to test n-grams for multiword expressions. It is still up to the researcher to determine which ones are multiword expressions of length n, that is, the n-grams of interest. Fortunately, the implementation of Equation (1) is not difficult for bigrams. The n-gramming results can also be affected by the choices within other text preprocessing operations, such as tokenization, letter case normalization, and stopword removal (Al-Molegi et al. Reference Al-Molegi, Alsmadi, Najadat and Albashiri2015; Jimenez et al. Reference Jimenez, Maxime, Le Traon and Papadakis2018).

A manual way to create multiword expressions of length 3 or 4 is to run the bigram generation and testing algorithm twice (Henry Reference Henry2016). If the concatenation of a word and a bigram passes the test, the trigram becomes a multiword expression of length 3. If the concatenation of two bigrams passes the test, the 4-gram becomes a multiword expression of length 4. One drawback is that $w_1 w_2 w_3$ being a multiword expression does not always imply $w_1 w_2$ and/or $w_2 w_3$ are also multiword expressions. But given the Markov assumption in Equation (2), we can safely presume that counterexamples are rare, that is, $w_3$ mostly depends on only the previous word $w_2$ .

For an n-gram to be a multiword expression, both practical and statistical significance are essential requirements. Practical significance requires each multiword expression to appear a minimum number of times in the corpus, so the selected n-grams would be presumed to have semantic importance. Statistical significance ensures that the multiword expressions are unlikely to be words co-occurring by chance (Dror et al. Reference Dror, Baumer, Shlomov and Reichart2018), but the conditional probability $P(w_2 | w_1)$ would not be accurate without $w_1 w_2$ of sufficient frequency in the corpus, that is, practical significance.

3.7.4 N-gramming: Computational issues

Although the number of total n-grams grows linearly with the total number of words in the document, detecting multiword expressions in the corpus is computationally expensive due to the large number of distinct n-grams (McNamee and Mayfield Reference McNamee and Mayfield2007; Vilares et al. Reference Vilares, Vilares, Alonso and Oakes2016). If the vocabulary contains V distinct words, the number of distinct unigrams of the corpus has O(V) complexity. As the length n increases, the size of the n-gram pool grows exponentially—the complexity increases to $O(V^2)$ for distinct bigrams and to $O(V^3)$ for distinct trigrams. Nevertheless, the effort needed may not generate a good return of investment, especially for long n-grams. For aggregated statistics of text data, the n-gram frequency is right-skewed and most of the detected n-grams appear only once in the corpus. Accordingly, most studies do not investigate the corpus past 4-grams (Lin and Hovy Reference Lin and Hovy2003; Barrón-Cedeño and Rosso Reference Barrón-Cedeño and Rosso2009), not to mention longer n-grams. As a result, long multiword expressions are difficult to detect in n-gramming (Raff and Nicholas Reference Raff and Nicholas2018; Raff et al. Reference Raff, Fleming, Zak, Anderson, Finlayson, Nicholas and McLean2019).

The good news is that long multiword expressions may be discovered via researchers’ understanding of the data content. The presence of such phrases may follow patterns and/or contain non-ignorable information, and we can apply subject matter knowledge of the corpus to create a list of long n-grams which are likely to be multiword expressions. We should retrieve these phrases directly from the data, rather than shingling the entire corpus to generate all n-grams when n is large. After obtaining the frequency of such phrases, we can determine whether it is appropriate to remove them from the corpus. If the answer is yes, then the text corpus can be further reduced. Below are some scenarios that produce long multiword expressions. Upon detection, these phrases can be easily removed without losing excessive semantic information.

• The sales limitation phrase “must be 18 or older” is a multiword expression in a text corpus of digital advertisements. This phrase indicates the product’s legal age range, so the product should not be marketed to underage people such as middle school students. But from a computational advertising standpoint, this multiword expression does not provide any information about the product itself, making it difficult to match ads to users (Soriano et al. Reference Soriano, Au and Banks2013).

• In a political blog corpus about the 2012 Trayvon Martin shooting incident,Footnote 18 the research group at Duke Statistical Science discovered an extremely long multiword expression—because one blogger included the Second Amendment to the United States Constitution in every post as a signature. The statement is “A well regulated Militia, being necessary to the security of a free State, the right of the people to keep and bear Arms, shall not be infringed.” Although controversial, this shows the blogger’s perspective toward gun laws (Chai Reference Chai2017).

The decision to apply n-gramming for text preprocessing or not depends on the NLP application. N-gramming is beneficial to applications that focus on words and phrases as consecutive words, such as text classification (Beitzel et al. Reference Beitzel, Jensen, Lewis, Chowdhury and Frieder2007; Narala, Rani, and Ramakrishna Reference Narala, Rani and Ramakrishna2017) and probabilistic topic modeling (Acree Reference Acree2016; Luiz et al. Reference Luiz, Olden, Kennard, Crook, Douglas, Saunders and King2019). N-gramming also identifies multiword expressions, which can enhance the vocabulary database in word embeddings (Goodman, Zimmerman, and Hudson Reference Goodman, Zimmerman and Hudson2020). In machine translation, n-gramming can be used for the hard-to-translate parts, because translation is not a one-to-one mapping between words (Du, Yu, and Zong Reference Du, Yu and Zong2018). But since n-gramming does not provide context to phrases, this approach will be of limited help in logical reasoning (Bernardy and Chatzikyriakidis Reference Bernardy and Chatzikyriakidis2019; Zhou et al. Reference Zhou, Duan, Liu and Shum2020). Instead, special techniques are needed for multiword expressions (Rikters and Bojar Reference Rikters and Bojar2017) and also for proper names (e.g., transliteration from Latin to Cyrillic characters) (Petic and G fu 2014; Mansurov and Mansurov Reference Mansurov and Mansurov2021).