Tokenize and Count

easyFREEText ProcessingNLP 1: Foundations

Given a string of text, split it into lowercase words (splitting on whitespace), and return a dictionary mapping each word to its frequency count.

Words should be converted to lowercase before counting. The output dictionary should be printed with keys in sorted order.

Example:

Input: "The cat sat on the mat"
After lowercasing and splitting: ["the", "cat", "sat", "on", "the", "mat"]
Frequencies: {"cat": 1, "mat": 1, "on": 1, "sat": 1, "the": 2}

Example

Input

The cat sat on the mat

Output

{'cat': 1, 'mat': 1, 'on': 1, 'sat': 1, 'the': 2}

Reasoning

Input: text is one line, The cat sat on the mat: six words separated by single spaces. Two of them, "The" and "the", differ only in capitalisation.
Normalise case: once every letter is lower case, "The" and "the" are the same token, so the word list becomes the, cat, sat, on, the, mat: six tokens but only five distinct words.
Count: each distinct word maps to how many times it occurs. "the" occurs at positions 1 and 5, so its count is $2$ ; cat, sat, on and mat occur once each. The counts sum to $2 + 1 + 1 + 1 + 1 = 6$ , the token total.
Output: the dictionary {'cat': 1, 'mat': 1, 'on': 1, 'sat': 1, 'the': 2}, with keys in alphabetical order: c < m < o < s < t. Sentence position plays no part, which is why 'the' comes last even though it is the first word.
Notice: without lower-casing, The and the would be two separate keys, each with count $1$ .

Constraints

Input: A single line of text (string)
Split on whitespace only
Convert all words to lowercase before counting
Output: A dictionary printed with keys in sorted order
Words contain only alphabetic characters and whitespace

Learn this in

NLP FundamentalsML Study Plan Text RepresentationNLP Study Plan

More from NLP 1: Foundations

Embedding Lookupeasy Cosine Similarity Calculatoreasy Binary Vectorizereasy Document Term Matrixeasy Character Frequency Countereasy

Concept primer

Background Knowledge

The problem "Tokenize and Count" falls under the category of Text Processing in Natural Language Processing (NLP). To tackle this problem, one needs to understand the basics of text preprocessing, which includes tokenization. Tokenization is the process of splitting a string of text into individual words or tokens. This is a crucial step in many NLP tasks as it allows for the analysis of text at the word level. Another key concept here is the idea of frequency counting, which involves counting how many times each word appears in a given text. This can provide insights into the importance or relevance of words within the context of the text.

Understanding how to work with strings and dictionaries in programming is also essential. Specifically, knowing how to split strings into substrings (in this case, words), and how to use dictionaries to store and retrieve data (such as word frequencies) is vital. The requirement to convert words to lowercase before counting highlights the importance of case sensitivity in text processing. By converting all words to lowercase, the algorithm ensures that the same word in different cases (e.g., "The" and "the") is not counted as two separate words.

The output requirement of printing the dictionary with keys in sorted order introduces the concept of data sorting, which is a fundamental operation in programming. Sorting data can make it easier to analyze or compare, and in this case, it ensures that the word frequencies are presented in a consistent and readable manner.

Algorithm/Approach

The general approach to solving this type of problem involves a combination of string manipulation, dictionary operations, and sorting. The algorithm pattern can be summarized as follows: tokenize the input string into individual words, count the frequency of each word using a dictionary, and then sort the dictionary by keys before outputting the result. This pattern is commonly seen in text processing tasks where the goal is to analyze or summarize the content of a piece of text.

Step-by-Step Strategy

To implement the solution:

Split the input string into individual words based on whitespace.
Convert each word to lowercase to ensure case-insensitive counting.
Create a dictionary to store the frequency of each word.
Iterate through the words and update their frequencies in the dictionary.
Sort the dictionary by keys (the words) before outputting the result.
Print the sorted dictionary, which represents the word frequencies.

Common Pitfalls

Things to watch out for include:

Forgetting to convert words to lowercase, leading to incorrect frequency counts.
Not handling punctuation next to words (though not explicitly mentioned in the problem, it's a common issue in text processing).
Incorrectly sorting the dictionary, or forgetting to sort it altogether.

Time & Space Complexity

The expected time complexity for this problem is $O(n \log n)$ , where $n$ is the number of unique words. This is because the algorithm involves sorting the dictionary by keys, which has a time complexity of $O(n \log n)$ for $n$ items. The space complexity is $O(n)$ , as in the worst case, every word in the input string could be unique, requiring a dictionary of size $n$ .

solution.py

Python 3.13

Test results