今天的课程内容是：

为什么讲了这么多我也不清楚。然后作业也挺多，最烧脑的想必是：

为了对字符串文本进行加密，凯撒发明了如下的加密方式：

  • 把一个英文字母替换为它在字母表中后面的第 3 个字母。
  • 如果到达了字母表的末尾 (即：字母 z)，则回转到第一个字母 a。
  • 也即，字母 z 的后继字母是 a。

下面，我们按照这种方式，分别定义 加密 和 解密 两个函数。

加密 / encode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import Data.Char(ord, chr, isLower)
-- ord :: Char -> Int        // 将字符转换为编码值
-- chr :: Int -> Char        // 将编码值转换为字符
-- isLower :: Char -> Bool   // 判断字符是否为小写字母

encode :: Int -> String -> String
encode n xs = [ shift n x | x <- xs ]

shift :: Int -> Char -> Char
shift n c | isLower c  =  int2let $ mod (let2int c + n) 26
          | otherwise  =  c

let2int :: Char -> Int
let2int c = ord c - ord 'a'

int2let :: Int -> Char
int2let n = chr $ ord 'a' + n

解密 / crack

对凯撒加密后的字符串进行解密的关键：

  • 在英文语料中，不同字母出现的频率是不同的。

下面定义 table 依次记录了 26 个英文字母的出现百分比：

1
2
3
4
table :: [Float]
table = [ 8.1, 1.5, 2.8, 4.2, 12.7, 2.2, 2.0, 6.1, 7.0,
          0.2, 0.8, 4.0, 2.4,  6.7, 7.5, 1.9, 0.1, 6.0,
          6.3, 9.0, 2.8, 1.0,  2.4, 0.2, 2.0, 0.1 ]

chi-square statistic：一种对一组 期望频率 (expected frequencies) 和 一组 观察频率 (observed frequencies) 进行比较的标准方法。

假设存在两个长度为 n 的频率序列：期望频率序列 es；观察频率序列 os。则两者的 chi-square statistic 定义如下： $$ \sum\limits_{i=0}^{n-1}\dfrac{(es_i-os_i)^2}{es_i^2} $$ 注：你可能需要用到函数 fromIntegral :: (Integral a, Num b) => a -> b，它可以实现从整数类型到浮点数类型的转换。

我们来看一下这个题目。主要思想是：暴力枚举 26 个偏移量，偏移后得到一段文字，再根据各种字母的出现频率与英文语料中的统计学数据，从而根据最小的 chi-square statistic 确定哪个偏移量对应的文字“最像”英文。

看下我的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
module HW5 where

import Data.Char (chr, isLower, ord)

table :: [Float] 
table = [ 8.1, 1.5, 2.8, 4.2, 12.7, 2.2, 2.0, 6.1, 7.0, 
          0.2, 0.8, 4.0, 2.4,  6.7, 7.5, 1.9, 0.1, 6.0, 
          6.3, 9.0, 2.8, 1.0,  2.4, 0.2, 2.0, 0.1 ] 

crack :: String -> String
crack xs  =  encode (-factor) xs 
    where   
        factor = position (minimum chitab) chitab      
        chitab = [ chisqr (rotate n table') table | n <- [0..25] ]
        table' = freqs xs

position :: Eq a => a -> [a] -> Int
position x' []     = 0
position x' (x:xs) = if x == x' then 0 else 1 + position x' xs

rotate :: Int -> [a] -> [a]
rotate n s = [ p | r <- [0..25], (p,q) <- zip s [0..25], q == mod (r + n) 26]

freqs :: String -> [Float]
freqs s = [ fromIntegral (100 * length [ z | z <- s, z == chr ((ord 'a') + x) ]) / fromIntegral (length s) | x <- [0..25] ]

chisqr :: [Float] -> [Float] -> Float
chisqr [] _          = fromIntegral 0
chisqr _  []         = fromIntegral 0
chisqr (o:os) (e:es) = (o - e) ^ 2 / (e ^ 2) + chisqr os es

为了测试之，我从 2025 年 9 月 25 日 The Economist 网站上发布的 Donald Trump is trying to silence his critics. He will fail 中节选了第一段进行测试。相符甚好。