摘要

本文將探討如何統計文本文件中每個單詞的出現頻率，具體實現包括 Bash 腳本的經典解法和 Swift 的高效實現。我們不僅會提供完整的代碼，還將逐步拆解邏輯，幫助讀者理解實現細節。同時，文章會分析時間與空間複雜度，並附上運行示例及結果。

描述

寫一個 bash 腳本以統計一個文本文件 words.txt 中每個單詞出現的頻率。

為了簡單起見，你可以假設：

• words.txt只包括小寫字母和 ' ' 。
• 每個單詞只由小寫字母組成。
• 單詞間由一個或多個空格字符分隔。

示例:

假設 words.txt 內容如下：

the day is sunny the the
the sunny is is

你的腳本應當輸出（以詞頻降序排列）：

the 4
is 3
sunny 2
day 1

説明:

• 不要擔心詞頻相同的單詞的排序問題，每個單詞出現的頻率都是唯一的。
• 你可以使用一行 Unix pipes 實現嗎？

題解答案

Bash 實現

我們可以使用一行 Unix 管道命令來高效完成統計任務：

cat words.txt | tr -s ' ' '\n' | sort | uniq -c | sort -rn | awk '{print $2, $1}'

Swift 實現

我們用 Swift 提供更具可讀性和擴展性的解法：

import Foundation

func countWordFrequencies(filePath: String) {
    do {
        let content = try String(contentsOfFile: filePath)
        let words = content
            .split { $0.isWhitespace }
            .map { String($0) }

        var wordCount: [String: Int] = [:]

        for word in words {
            wordCount[word, default: 0] += 1
        }

        let sortedWordCount = wordCount.sorted { $0.value > $1.value }

        for (word, count) in sortedWordCount {
            print("\(word) \(count)")
        }
    } catch {
        print("Error reading file: \(error.localizedDescription)")
    }
}

// 示例調用
let filePath = "path/to/words.txt"
countWordFrequencies(filePath: filePath)

題解代碼分析

Bash 解法

cat words.txt | tr -s ' ' '\n' | sort | uniq -c | sort -rn | awk '{print $2, $1}'

1. cat words.txt: 讀取文件內容。
2. tr -s ' ' '\n': 將所有空格替換為換行符，從而每行一個單詞。
3. sort: 對單詞排序，方便後續統計。
4. uniq -c: 統計每個單詞的出現次數，並輸出格式為 次數 單詞。
5. sort -rn: 按次數降序排列。
6. awk '{print $2, $1}': 調整輸出順序為 單詞 次數。

Swift 解法

1. 讀取文件: 使用 String(contentsOfFile:) 讀取文本內容。
2. 分割單詞: 用 split 按空格切分字符串，並將結果轉換為字符串數組。
3. 統計頻率: 利用字典存儲每個單詞的計數，wordCount[word, default: 0] += 1 實現自動初始化與計數。
4. 排序: 使用 sorted 按頻率降序排列。
5. 輸出結果: 遍歷排序後的數組並打印結果。

示例測試及結果

輸入文件 words.txt:

the day is sunny the the
the sunny is is

Bash 輸出:

the 4
is 3
sunny 2
day 1

Swift 輸出:

the 4
is 3
sunny 2
day 1

時間複雜度

1. Bash 實現:

   • sort: O(n log n)，其中 n 是單詞總數。
   • uniq -c: O(n)。
   • sort -rn: O(n log n)。
   • 總複雜度：O(n log n)。

2. Swift 實現:

   • 讀取與分割: O(n)。
   • 統計頻率: O(n)。
   • 排序: O(k log k)，其中 k 是唯一單詞的個數。
   • 總複雜度：O(n + k log k)。

空間複雜度

1. Bash 實現: 依賴 Unix 管道，無需額外存儲空間，複雜度為 O(1)。
2. Swift 實現: 使用數組和字典存儲單詞和頻率，複雜度為 O(n)。

總結

1. Bash 解法: 簡潔高效，適用於快速處理任務。
2. Swift 解法: 代碼結構清晰，適合需要更多功能擴展的場景。

未來展望

1. 擴展到大規模分佈式文本處理，可引入 Hadoop 或 Spark。
2. 添加多語言支持，處理更復雜的文本格式（如標點符號、大小寫敏感性）。

參考資料

• Bash 文檔
• Swift 官方文檔
• Linux tr 手冊