# Word Frequency
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/word-frequency)
Canonical: https://scaleengineer.com/dsa/problems/word-frequency
---
## Problem
Write a bash script to calculate the frequency of each word in a text file `words.txt`.

For simplicity sake, you may assume:

* `words.txt` contains only lowercase characters and space `' '` characters.
* Each word must consist of lowercase characters only.
* Words are separated by one or more whitespace characters.

**Example:**

Assume that `words.txt` has the following content:

the day is sunny the the
the sunny is is

Your script should output the following, sorted by descending frequency:

the 4
is 3
sunny 2
day 1

**Note:**

* Don't worry about handling ties, it is guaranteed that each word's frequency count is unique.
* Could you write it in one-line using [Unix pipes](http://tldp.org/HOWTO/Bash-Prog-Intro-HOWTO-4.html)?

# Approaches
## Pure Bash Script with Associative Array
This approach uses bash scripting features, specifically an associative array, to count word frequencies. It reads the file, iterates through each word, and uses the word as a key in an associative array to store its count. Finally, it formats the output and uses the `sort` utility to order the results.
**Time:** O(M + U log U) · **Space:** O(U * L_avg)
**Pros:** The logic is explicit and may be easier to understand for those familiar with general-purpose programming languages.; It's a self-contained script that doesn't rely on a long chain of commands.
**Cons:** Less efficient than the piped approach because the bash interpreter is slower than compiled C utilities for text processing.; The `$(cat words.txt)` construct reads the entire file into memory before the loop starts, which can be problematic for very large files.
### Explanation
This method involves writing a more traditional script that leverages bash's built-in data structures. 

An associative array is the perfect tool for this job, acting like a hash map or dictionary in other programming languages. We can use the words themselves as keys and their frequencies as values.

The script performs the following steps:
1.  An associative array named `word_counts` is declared using `declare -A`.
2.  A `for` loop iterates through each word from `words.txt`. The command substitution `$(cat words.txt)` splits the file content into words based on whitespace.
3.  For each `word`, the expression `((word_counts[$word]++))` increments the count for that word. If a word is encountered for the first time, bash automatically initializes its count to 0 before incrementing.
4.  Once all words are counted, a second `for` loop iterates over all the keys (the unique words) in the `word_counts` array.
5.  Inside this loop, `echo "$word ${word_counts[$word]}"` prints the word followed by its stored frequency.
6.  The entire output of this loop is then piped to the `sort -k2 -nr` command, which sorts the lines numerically (`-n`) in reverse (`-r`) order based on the second field (`-k2`), which is the count.

```java
#!/bin/bash

# Declare an associative array to store word counts
declare -A word_counts

# Read words from the file and count their frequencies
# Note: This reads the whole file into memory.
for word in $(cat words.txt); do
    ((word_counts[$word]++))
done

# Print the words and their counts, then sort by the count (second column).
for word in "${!word_counts[@]}"; do
    echo "$word ${word_counts[$word]}"
done | sort -k2 -nr
```
### Algorithm
- Declare a bash associative array, let's call it `word_counts`.
- Use a `for` loop to iterate over every word in the input file `words.txt`. The construct `$(cat words.txt)` is used to provide the list of words.
- Inside the loop, for each `word`, increment its corresponding counter in the associative array: `((word_counts[$word]++))`. If the word is not yet a key in the array, it's automatically created with a value of 0 before being incremented.
- After the loop finishes, the `word_counts` array holds all unique words and their frequencies.
- Loop through the keys of the array (`"${!word_counts[@]}"`) to print each word and its count in the format `word count`.
- The output of this loop is piped to `sort -k2 -nr`. This command sorts the lines based on the second column (`-k2`) numerically (`-n`) and in reverse (descending) order (`-r`).

## Pipelined Unix Commands (One-Liner)
This is the canonical and most efficient approach in a Unix-like environment. It constructs a pipeline of standard command-line utilities, where the output of each command becomes the input for the next. This method is concise, powerful, and leverages highly optimized tools built for text processing.
**Time:** O(M log M) · **Space:** O(M * L_avg)
**Pros:** Extremely concise and idiomatic for shell scripting.; Highly efficient as it uses specialized, compiled C utilities designed for high-performance text manipulation.; Scales well to very large files because of the streaming nature of pipes and the ability of tools like `sort` to use temporary disk space (external sorting).
**Cons:** The chain of commands can be cryptic for beginners not familiar with Unix utilities like `tr`, `uniq`, and `awk`.; Involves the overhead of creating multiple processes and pipes, though this is typically negligible for this task.
### Explanation
The one-liner approach leverages the power of Unix pipes (`|`) to chain together a sequence of simple, highly optimized commands. Each command does one thing well, and by combining them, we can create a powerful and efficient data processing pipeline.

The pipeline works as follows:
1.  `cat words.txt`: First, we get the content of the file and stream it to standard output.
2.  `tr -s ' ' '\n'`: The text stream is piped to `tr` (translate). `tr -s ' ' '\n'` replaces each sequence of one or more spaces with a single newline. This effectively tokenizes the input, placing each word on a separate line.
3.  `sort`: The resulting list of words is piped to `sort`, which sorts them alphabetically. This is crucial because `uniq -c` only works on adjacent, identical lines.
4.  `uniq -c`: The sorted list is piped to `uniq -c`. This command removes consecutive duplicate lines and prepends each unique line with the number of times it occurred.
5.  `sort -nr`: The output, now in `count word` format, is piped to another `sort`. `sort -nr` performs a numeric (`-n`) and reverse (`-r`) sort, ordering the words by frequency in descending order.
6.  `awk '{print $2, $1}'`: Finally, the sorted list is piped to `awk` for reformatting. The simple script `'{print $2, $1}'` prints the second column (the word) followed by the first column (the count), producing the final desired output.

```java
# Read from the file words.txt and output the word frequency list to stdout.
cat words.txt | tr -s ' ' '\n' | sort | uniq -c | sort -nr | awk '{print $2, $1}'
```

An alternative, and often more robust, method for the tokenization step is to use `grep`:

```java
# This version is more robust as it specifically extracts sequences of letters.
grep -o '[a-z]+' words.txt | sort | uniq -c | sort -nr | awk '{print $2, $1}'
```
### Algorithm
- **Tokenize**: Use `tr -s ' ' '\n'` to convert all sequences of one or more spaces into single newline characters. This puts each word on its own line.
- **Sort**: Use `sort` to sort the list of words alphabetically. This is a necessary step for `uniq` to work correctly.
- **Count**: Use `uniq -c` to collapse the sorted list of words. It removes duplicates and, with the `-c` flag, prepends each unique word with its frequency count. The output format is `count word`.
- **Sort by Frequency**: Use `sort -nr` to sort the lines numerically (`-n`) and in reverse (`-r`) order. This sorts the words by their frequency, from highest to lowest.
- **Format Output**: Use `awk '{print $2, $1}'` to swap the columns, changing the format from `count word` to the desired `word count`.