24 Julia编程示例–单词和文本

24.1 词典中单词的练习

24.1.1 二分法查词

设dict是一个字符串数组， 包含了许多单词， 按字典序排列。 为了检查字符串word是否在dict中， 可以用word in dict的写法， 但是这样会进行线性搜索， 效率较低。 因为词典dict是按升序排序的， 可以用二分法搜索。 程序如下：

function indict(dict, word)
    a = 1
    b = length(dict)
    while a <= b
        c = (a + b) ÷ 2
        if dict[c] == word 
            return true
        elseif word < dict[c]
            b = c-1
        else
            a = c+1
        end
    end
    return false
end # function indict(dict, word)

或者将二分法写成递归版本：

function indict_recurse(dict, word)
    a = 1
    b = length(dict)
    if dict[a] == word || dict[b] == word
        return true
    end
    if b-a <= 1
        return false
    end
    c = (a + b) ÷ 2
    if word <= dict[c]
        return indict_recurse(dict[a:c], word)
    else
        return indict_recurse(dict[c:b], word)
    end
end

一个词典文件为words.txt，读入为字符串数组的程序为：

mydict = readlines("words.txt")

有584983个单词。

这些标准的算法应该是有现成的库函数的，待查。

24.1.2 查找良序词

有些单词中的字母出现次序是不违背字母表的前后次序的， 比如act不违反次序， 而cat则违反次序， 成不违反字母表次序的此为良序词(abecedarian)， 重复字母也允许。

一种写法是用for循环， 但需要用firstindex提供第一个字母：

function isabecedarian_for(word)
    i = firstindex(word)
    previous = word[i]
    j = nextind(word, i)
    for c in word[j:end]
        if c < previous
            return false
        end
        previous = c
    end
    return true
end


## 根据单个单词的特征从词典列举的函数，
## `is_f`是用来判断一个单词是否符合的示性函数
function find_words(dict, is_f; printwords = true)
    y = []
    for word in dict
        if is_f(word)
            push!(y, word)
            if printwords
                println(word)
            end
        end
    end
    return y
end

find_words(mydict, isabecedarian_for, printwords=false)

用递归的方法：

function isabecedarian_recurse(word)
    if length(word) <= 1
        return true
    end
    
    i = firstindex(word)
    j = nextind(word, i)
    if word[i] > word[j]
        return false
    else
        return isabecedarian_recurse(word[j:end])
    end
end

find_words(mydict, isabecedarian_recurse, printwords=false)

用while循环的方法：

function isabecedarian_while(word)
    i = firstindex(word)
    j = nextind(word, i)
    while j <= sizeof(word)
        if word[j] < word[i]
            return false
        end
        i = j
        j = nextind(word, i)
    end
    return true
end
find_words(mydict, isabecedarian_while, printwords=false)

24.1.3 查找回文词

如radar这样的词称为回文词(palindrome)， 用while循环分别从头、尾向中间遍历判断：

function ispalindrome(word)
    i = firstindex(word)
    j = lastindex(word)
    while i < j
        if word[i] != word[j]
            return false
        end
        
        i = nextind(word, i)
        j = prevind(word, j)
    end
    return true
end

find_words(mydict, ispalindrome, printwords=false)

24.1.4 找出多次成对字母的单词

像committee这样的单词， 有连续的mm, tt, ee三次双字母出现。 查找这样的单词：

function isdouble3(word)
    pat = r"(.)\1.*(.)\2.*(.)\3"
    return occursin(pat, word)
end

find_words(mydict, isdouble3, printwords=false)

有几千个这样的单词。

如果要查找连续双字母接连不断出现三次的单词：

function isdouble_all(word)
    pat = r"(.)\1(.)\2(.)\3"
    return occursin(pat, word)
end

find_words(mydict, isdouble_all, printwords=true)

结果仅有4个单词： SOTTOOCCUPATA, SOTTOOCCUPATE, SOTTOOCCUPATI, SOTTOOCCUPATO。

上面用了正则表达式。 如果不用正则表达式， 仅使用循环， 则允许中断的版本会略长一些， 而双字母三对连续出现的版本较容易：

function isdouble_while(word)
    if length(word) < 6
        return false
    end
    
    x = collect(word)
    n = length(x)
    for i in 1:(n-5)
        piece = x[i:(i+5)]
        if all(piece[[1,3,5]] == piece[[2,4,6]])
            return true
        end
    end
    
    return false
end

find_words(mydict, isdouble_while, printwords=true)

比正则表达式的版本略慢一些。

24.1.5 查找变位词

如果两个单词使用的字母相同，称其为变位词， 如lasted和salted。

给定一个单词组成的数组， 将其中的变位词集合都找出来。

首先， 将每个单词拆解成字母的序列， 表示成字母排序的元组， 比如“lasted”变成元组(a, d, e, l, s, t)。 然后， 将每个单词填入到一个键为元组， 值为变位词数组的字典中。 最后， 仅保留有变位词的部分， 并将结果排序，输出为单词的元组的数组。 程序如下：

## 将一个单词拆分成字母序的元组
function word_chars(word)
    x = sort!(collect(word))
    return tuple(x)
end

## 在单词的数组中查找所有变位词
function variwords(dict)
    ## 建立排序的字母集合（用元组表示）到单词数组的映射，用字典表示
    d = Dict()
    for word in dict
        tup = word_chars(word)
        if tup in keys(d)
            push!(d[tup], word)
        else
            d[tup] = [word]
        end
    end
    
    ## 筛选有变位词的部分，每一组作为一个元组，然后排序
    res = [tuple(x...) for x in values(d) if length(x) > 1]
    sort!(res)
    
    return res
end
## mydict = readlines("words.txt")
## variwords(mydict)

24.1.6 查找反向成对单词

设dict为一个有几十万单词的字符串数组（词典）， 在其中找到所有互为颠倒次序的单词， 如eva和ave, DVD和DVD。

注意为了效率起见不能进行两两比较， 两两比较需要\(n^2\)级的运算（\(n\)为单词个数）。

比较简单的想法是利用上面的二分法程序， 如：

function reversepairs(dict)
    y = []
    n = length(dict)
    n2 = Int(ceil(n/2))
    for word in dict[1:n]
        rword = reverse(word)
        if indict(dict, rword)
            push!(y, (word, rword))
            println(word, "  ", rword)
        end
    end
    return y
end

上述做法会找到一些重复内容，比如("AVE", "EVA")和("EVA", "AVE")实际是同一个结果。 只要在记录新的反向单词对之前检查一下：

function reversepairs(dict)
    y = []
    n = length(dict)
    n2 = n ÷ 2
    for word in dict[1:n2]
        rword = reverse(word)
        if indict(dict, rword)
            if word <= rword
                newpair = (word, rword)
            else
                newpair = (rword, word)
            end
            if !(newpair in y)
                push!(y, (word, rword))
                println(word, "  ", rword)
            end
        end
    end
    return y
end

在58万单词中搜索用了0.5秒。 注意Julia的函数在传递数组时按引用传递而不会传递数组副本， 所以程序中的indict(dict, rword)调用不会因为制作数组副本而降低效率。

上述程序的效率已经比较满意， 所以不需要进一步改进。 进一步改进可以按单词长度分组， 同一组的单词才需要查找是否反向单词对。

24.1.7 连锁组词

在词典中查找连锁词。 两个单词交替取字母组成一个新词， 如shoe和cold交替取字母组成schooled， 称为连锁词(interlocked words)。

24.1.7.1 两重循环的算法

显然不能遍历所有的两两组合，否则程序效率会很低。 基本的想法是按单词长度分组，查找时仅用同长度词语两倍长度词检查。 对等长度的两个单词两两组合看能否组成单词， 这是两重循环，运算量为\(O(n^2)\)阶。 程序如下：

## 从两个等长的词连锁组词：
function makeinterlock(a, b)
    n = length(a)
    @assert length(b) == n
    aa = collect(a)
    ba = collect(b)
    newa = Array{Char, 1}(undef, n*2)
    newa[1:2:(end-1)] = aa
    newa[2:2:end] = ba
    return join(newa, "")
end

## 在一个词典（数组格式）中查找能够连锁组词的组合
## max_len是用来组词的单词最大允许长度
function interlock(dict, max_len=5)
    ## 将单词分成不同的长度组
    ## 每个单词的长度
    wl = map(length, dict)
    ## 单词的最大长度
    ml = maximum(wl)
    println("最大单词长度：", ml)
    
    ## 按单词长度分组，结果是单词的数组，下标是单词长度
    dictgr = map(i -> dict[wl .== i], 1:ml)
    ## 每组有多少个单词
    gwords = map(length, dictgr)
    println("各长度单词个数：", gwords)
    maxrl = div(ml, 2) # 最大可能的组成长度
    
    result = []
    for wordlen in 2:min(max_len, maxrl) 
        println("==== 由$(wordlen)个字母组成的单词交织：")
        dictsub = dictgr[wordlen]   # 组成单词表
        dictres = dictgr[2*wordlen] # 连锁可能结果单词表
        for a in dictsub
            for b in dictsub
                newword = makeinterlock(a, b)
                if indict(dictres, newword)
                    ##println(a, ", ", b, " ==> ", newword)
                    push!(result, (a, b, newword))
                end
            end
        end
    end
    return result
end

在58万单词的词典中， 最长的词是15个字母， 这样， 两个7字母的单词有可能连锁组词， 而7字母单词有三万多个， 运行2到5个字母单词的查找用了1.5分钟， 估计运行所有搜索需要45分钟。

两两搭配的运算量太大， 需要更合理的算法。 在修改算法之前，先考虑用并行化提高速度。

24.1.7.2 并行化改进

将如下程序保存在interlock.jl源文件中：

## 用二分法查找单词是否在词典中
function indict(dict, word)
    a = 1
    b = length(dict)
    while true
        if dict[a] == word || dict[b] == word
            return true
        end
        n = b - a + 1
        if n <= 2
            return false
        end
        c = (a + b) ÷ 2
        ##println("n = ", n, " word = ", dict[a], ", ", dict[c], ", ", dict[b])
        if word <= dict[c]
            b = c
        else
            a = c
        end
    end
    return false
end

## 将两个单词交叠组成新词，如shoe和cold交替取字母组成schooled。
function makeinterlock(a, b)
    n = length(a)
    @assert length(b) == n
    aa = collect(a)
    ba = collect(b)
    newa = Array{Char, 1}(undef, n*2)
    for i in 1:n
        newa[2*(i-1)+1] = aa[i]
        newa[2*i] = ba[i]
    end
    return join(newa, "")
end

## 给定短词表和长词表，看短词表中两个单词交叠组成新单词是否在长词表中
## 并行处理
function findinterlock_paral(dictsub, dictres)
    @distributed (vcat) for a in dictsub
        for b in dictsub
            newword = makeinterlock(a, b)
            indict(dictres, newword) ? [a, b, newword] : []
        end
    end
end

## 给定一个单词表，找到交叠词
function interlock_paral(dict)
    ## 将单词分成不同的长度组
    wl = map(length, dict)
    ml = maximum(wl)
    println("最大单词长度：", ml)
    dictgr = map(i -> dict[wl .== i], 1:ml)
    gwords = map(length, dictgr)
    println("各长度单词个数：", gwords)
    maxrl = div(ml, 2) # 最大可能的组成长度
    result = []
    for wordlen in 2:5 # 2:maxrl
        println("==== 由$(wordlen)个字母组成的单词交织：")
        dictsub = copy(dictgr[wordlen]) # 组成单词表
        dictres = copy(dictgr[2*wordlen]) # 结果单词表
        append!(result, findinterlock_paral(dictsub, dictres))
    end
    return result
end

在Julia命令行运行如下程序：

mydict = readlines("words.txt")
using Distributed
addprocs(6)
@everywhere include("interlock.jl")
@time res = interlock_paral(mydict)

运行了21分钟， 并行算法比非并行算法效率提高一倍左右。 程序中调用了Distributed包， 用addprocs(6)增加并行执行的节点数到7个节点， 用@everywhere ...将所有并行节点都需要的程序载入每个节点。 用@distributed (vcat) for ...执行并行的for循环并将每一轮循环的结果用vcat()函数合并起来。

24.1.7.3 改为拆分单词

前面的方法因为需要对两个候选组成词做两重循环， 所以效率较高。 另外的想法是对每个长度为偶数（至少为4）的单词进行拆分， 看拆分出的两个半长度单词是否在词典中。 这个版本只需要单重循环， 所以效率很高。 这就是算法的优势， 前面的算法是\(O(n^2)\)阶的， 而这里的方法是\(O(n)\)阶的。

## 从两个等长的词连锁组词：
function dislock(word)
    @assert length(word) % 2 == 0
    a = word[1:2:(end-1)]
    b = word[2:2:end]
    return a, b
end

## 在一个词典（数组格式）中查找能够连锁组词的组合
## max_len是用来组词的单词最大允许长度
function interlock_dislock(dict, max_len=5)
    ## 将单词分成不同的长度组
    ## 每个单词的长度
    wl = map(length, dict)
    ## 单词的最大长度
    ml = maximum(wl)
    println("最大单词长度：", ml)
    
    ## 按单词长度分组，结果是数组的数组，下标是单词长度
    dictgr = map(i -> dict[wl .== i], 1:ml)
    ## 每组有多少个单词
    gwords = map(length, dictgr)
    println("各长度单词个数：", gwords)
    maxrl = div(ml, 2) # 最大可能的组成长度
    
    result = []
    for wordlen in 2:min(max_len, maxrl) 
        println("==== 由$(wordlen)个字母组成的单词交织：")
        dictsub = dictgr[wordlen]   # 组成单词表
        dictres = dictgr[2*wordlen] # 连锁可能结果单词表
        for word in dictres
            a, b = dislock(word)
            if indict(dictsub, a) && indict(dictsub, b)
                ##println(a, ", ", b, " ==> ", newword)
                push!(result, (a, b, word))
            end
        end
    end
    return result
end

@time interlock_dislock(mydict, 9999)

仅用了0.2秒。

24.1.8 拆字词

有些单词减少某个字母后仍是单词， 继续减少一个单词都持续是单词， 直到变成一个字母的单词为止。 例如，sprite, spite, spit, sit, it, I。 找到所有这样的单词， 并找到最长的一个。

想法是， 从最短的一个字母组成的单词（a, I）开始， 将每种长度的符合条件的词找出来， 每种长度的拆字词保存成一个集合以利查找。 这种思想是“动态规划”的思想， 即需要多次重复计算某一结果时， 将这个结果保存下来重复利用。 找词时利用已经找到的较短拆字词，而不是对每个单词单独试验。

function show_delword(word, all_delwords)
    n = length(word)
    if word ∉ all_delwords[n]
        return
    elseif n==1
        println(word)
    else
        print(word, ", ")
        x = collect(word)
        for i in 1:n
            newword = join([ x[1:(i-1)]; x[(i+1):end] ])
            if newword in all_delwords[n-1]
                show_delword(newword, all_delwords)
                break
            end
        end
    end
end

function delwords(dict, max_len=5)
    ## 将单词分成不同的长度组
    ## 每个单词的长度
    word_lengths = map(length, dict)
    ## 单词的最大长度
    max_word_len = maximum(word_lengths)
    println("最大单词长度：", max_word_len)
    
    ## 按单词长度分组，结果是单词的数组，下标是单词长度
    dictgr = map(i -> dict[word_lengths .== i], 1:max_word_len)
    
    ## 内嵌函数，判断某个单词是否拆字词
    ## 递归调用，使用result中保存的较短拆字词
    function is_delword(word)
        n = length(word)
        x = collect(word)
        for i in 1:n
            newword = join([x[1:(i-1)]; x[(i+1):end]])
            ## 使用已经找到的较短拆字词
            if newword in result[n-1]
                return true
            end
        end
        return false
    end
    
    result = [Set(["A", "I"])]
    nres = min(max_len, max_word_len) 
    for wordlen in 2:nres
        push!(result, Set())
        ## 对长度为wordlen的每个单词判断是否拆字词
        for word in dictgr[wordlen]
            if is_delword(word)
                push!(result[wordlen], word)
            end
        end
    end
    
    ## 显示最长的拆字词
    for wordlen in nres:-1:2
        if length(result[wordlen])>0
            for word in result[wordlen]
                show_delword(word, result)
            end
            break
        end
    end

    return result
end

res = delwords(mydict, 999)

结果最长的拆字词有9个字母：

SBRAMASTI, BRAMASTI, RAMASTI, AMASTI, MASTI, ASTI, STI, TI, I
BINAZIONI, INAZIONI, NAZIONI, AZIONI, ZIONI, IONI, ONI, NI, I
RESPIRATI, ESPIRATI, SPIRATI, PIRATI, IRATI, RATI, ATI, TI, I
SFASCIATI, FASCIATI, ASCIATI, SCIATI, CIATI, IATI, ATI, TI, I
RESPIRATA, ESPIRATA, SPIRATA, PIRATA, IRATA, RATA, ATA, TA, A

24.2 千字文没有重复吗

千字文是著名的国学经典， 南北朝时期周兴嗣所作， 文章涵盖了国文初学者应知的许多基本知识， 四字一句，恰好一千字。 据说这样的一篇长文恰好用了一千个完全不同的字。 我们编制一个Julia程序， 将从网上下载的千字文检查是否有重复字。

千字文简体文本如下：

天地玄黄，宇宙洪荒。日月盈昃，辰宿列张。寒来暑往，秋收冬藏。
闰余成岁，律吕调阳。云腾致雨，露结为霜。金生丽水，玉出昆冈。
剑号巨阙，珠称夜光。果珍李柰，菜重芥姜。海咸河淡，鳞潜羽翔。
龙师火帝，鸟官人皇。始制文字，乃服衣裳。推位让国，有虞陶唐。
吊民伐罪，周发殷汤。坐朝问道，垂拱平章。爱育黎首，臣伏戎羌。
遐迩一体，率宾归王。鸣凤在竹，白驹食场。化被草木，赖及万方。
盖此身发，四大五常。恭惟鞠养，岂敢毁伤。女慕贞洁，男效才良。
知过必改，得能莫忘。罔谈彼短，靡恃己长。信使可覆，器欲难量。
墨悲丝染，诗赞羔羊。景行维贤，克念作圣。德建名立，形端表正。
空谷传声，虚堂习听。祸因恶积，福缘善庆。尺璧非宝，寸阴是竞。
资父事君，曰严与敬。孝当竭力，忠则尽命。临深履薄，夙兴温凊。
似兰斯馨，如松之盛。川流不息，渊澄取映。容止若思，言辞安定。
笃初诚美，慎终宜令。荣业所基，籍甚无竟。学优登仕，摄职从政。
存以甘棠，去而益咏。乐殊贵贱，礼别尊卑。上和下睦，夫唱妇随。
外受傅训，入奉母仪。诸姑伯叔，犹子比儿。孔怀兄弟，同气连枝。
交友投分，切磨箴规。仁慈隐恻，造次弗离。节义廉退，颠沛匪亏。
性静情逸，心动神疲。守真志满，逐物意移。坚持雅操，好爵自縻。
都邑华夏，东西二京。背邙面洛，浮渭据泾。宫殿盘郁，楼观飞惊。
图写禽兽，画彩仙灵。丙舍旁启，甲帐对楹。肆筵设席，鼓瑟吹笙。
升阶纳陛，弁转疑星。右通广内，左达承明。既集坟典，亦聚群英。
杜稿钟隶，漆书壁经。府罗将相，路侠槐卿。户封八县，家给千兵。
高冠陪辇，驱毂振缨。世禄侈富，车驾肥轻。策功茂实，勒碑刻铭。
盘溪伊尹，佐时阿衡。奄宅曲阜，微旦孰营。桓公匡合，济弱扶倾。
绮回汉惠，说感武丁。俊义密勿，多士实宁。晋楚更霸，赵魏困横。
假途灭虢，践土会盟。何遵约法，韩弊烦刑。起翦颇牧，用军最精。
宣威沙漠，驰誉丹青。九州禹迹，百郡秦并。岳宗泰岱，禅主云亭。
雁门紫塞，鸡田赤诚。昆池碣石，钜野洞庭。旷远绵邈，岩岫杳冥。
治本于农，务兹稼穑。俶载南亩，我艺黍稷。税熟贡新，劝赏黜陟。
孟轲敦素，史鱼秉直。庶几中庸，劳谦谨敕。聆音察理，鉴貌辨色。
贻厥嘉猷，勉其祗植。省躬讥诫，宠增抗极。殆辱近耻，林皋幸即。
两疏见机，解组谁逼。索居闲处，沉默寂寥。求古寻论，散虑逍遥。
欣奏累遣，戚谢欢招。渠荷的历，园莽抽条。枇杷晚翠，梧桐蚤凋。
陈根委翳，落叶飘摇。游鹍独运，凌摩绛霄。耽读玩市，寓目囊箱。
易輶攸畏，属耳垣墙。具膳餐饭，适口充肠。饱饫烹宰，饥厌糟糠。
亲戚故旧，老少异粮。妾御绩纺，侍巾帷房。纨扇圆洁，银烛炜煌。
昼眠夕寐，蓝笋象床。弦歌酒宴，接杯举殇。矫手顿足，悦豫且康。
嫡后嗣续，祭祀烝尝。稽颡再拜，悚惧恐惶。笺牒简要，顾答审详。
骸垢想浴，执热愿凉。驴骡犊特，骇跃超骧。诛斩贼盗，捕获叛亡。
布射僚丸，嵇琴阮箫。恬笔伦纸，钧巧任钓。释纷利俗，并皆佳妙。
毛施淑姿，工颦妍笑。年矢每催，曦晖朗曜。璇玑悬斡，晦魄环照。
指薪修祜，永绥吉劭。矩步引领，俯仰廊庙。束带矜庄，徘徊瞻眺。
孤陋寡闻，愚蒙等诮。谓语助者，焉哉乎也。

初步的检查程序如下：

function check_thch(filename)
    ## 读入文件为一个长字符串
    s0 = read(filename, String)
    ## 去掉标点、空格与换行
    s = replace(s0, r"[　，。 \n]" => s"")
    ##println(s)
    x = collect(s)
    if length(x) != 1000
        println("字数不等于1000！")
        return false
    end
    for i in 2:length(x)
        if x[i] in x[1:(i-1)]
            println("第", i, "字符（", x[i], "）重复!")
            return false 
        end
    end
    return true
end 
check_thch("千字文带标点.txt")

结果发现，“吊民伐罪，周发殷汤”与“盖此身发，四大五常”中“发”字重复。

怀疑还有重复字， 另外简体字可能将两个不同的繁体字合并了。 找到繁体字千字文文本如下，检查发现“发”字重复。 注意繁体千字文文本中的空格是中文空格， 在程序中replace()处加入了去掉中文空格的设置。

天地玄黃　宇宙洪荒　日月盈昃　辰宿列張　寒來暑往　秋收冬藏
閏馀成歲　律呂調陽　雲騰致雨　露結爲霜　金生麗水　玉出昆岡
劍號巨阙　珠稱夜光　果珍李柰　菜重芥姜　海鹹河淡　鱗潛羽翔
龍師火帝　鳥官人皇　始制文字　乃服衣裳　推位讓國　有虞陶唐
吊民伐罪　周發殷湯　坐朝問道　垂拱平章　愛育黎首　臣伏戎羌
遐迩一體　率賓歸王　鳴鳳在竹　白駒食場　化被草木　賴及萬方
蓋此身發　四大五常　恭惟鞠養　豈敢毀傷　女慕貞潔　男效才良
知過必改　得能莫忘　罔談彼短　靡恃己長　信使可複　器欲難量
墨悲絲染　詩贊羔羊　景行維賢　克念作聖　德建名立　形端表正
空谷傳聲　虛堂習聽　禍因惡積　福緣善慶　尺璧非寶　寸陰是競
資父事君　曰嚴與敬　孝當竭力　忠則盡命　臨深履薄　夙興溫凊
似蘭斯馨　如松之盛　川流不息　淵澄取映　容止若思　言辭安定
笃初誠美　慎終宜令　榮業所基　籍甚無竟　學優登仕　攝職從政
存以甘棠　去而益詠　樂殊貴賤　禮別尊卑　上和下睦　夫唱婦隨
外受傅訓　入奉母儀　諸姑伯叔　猶子比兒　孔懷兄弟　同氣連枝
交友投分　切磨箴規　仁慈隱恻　造次弗離　節義廉退　顛沛匪虧
性靜情逸　心動神疲　守真志滿　逐物意移　堅持雅操　好爵自縻
都邑華夏　東西二京　背邙面洛　浮渭據泾　宮殿盤郁　樓觀飛驚
圖寫禽獸　畫彩仙靈　丙舍傍啓　甲帳對楹　肆筵設席　鼓瑟吹笙
升階納陛　弁轉疑星　右通廣內　左達承明　既集墳典　亦聚群英
杜稿鍾隸　漆書壁經　府羅將相　路俠槐卿　戶封八縣　家給千兵
高冠陪辇　驅毂振纓　世祿侈富　車駕肥輕　策功茂實　勒碑刻銘
磻溪伊尹　佐時阿衡　奄宅曲阜　微旦孰營　桓公匡合　濟弱扶傾
绮回漢惠　說感武丁　俊乂密勿　多士寔甯　晉楚更霸　趙魏困橫
假途滅虢　踐土會盟　何遵約法　韓弊煩刑　起翦頗牧　用軍最精
宣威沙漠　馳譽丹青　九州禹迹　百郡秦並　嶽宗泰岱　禅主雲亭
雁門紫塞　雞田赤城　昆池碣石　巨野洞庭　曠遠綿邈　岩岫杳冥
治本于農　務資稼穑　俶載南畝　我藝黍稷　稅熟貢新　勸賞黜陟
孟轲敦素　史魚秉直　庶幾中庸　勞謙謹敕　聆音察理　鑒貌辨色
贻厥嘉猷　勉其祗植　省躬譏誡　寵增抗極　殆辱近恥　林臯幸即
兩疏見機　解組誰逼　索居閑處　沈默寂寥　求古尋論　散慮逍遙
欣奏累遣　戚謝歡招　渠荷的曆　園莽抽條　枇杷晚翠　梧桐蚤凋
陳根委翳　落葉飄搖　遊鹍獨運　淩摩绛霄　耽讀玩市　寓目囊箱
易輏攸畏　屬耳垣牆　具膳餐飯　適口充腸　飽饫烹宰　饑厭糟糠
親戚故舊　老少異糧　妾禦績紡　侍巾帷房　纨扇圓絜　銀燭炜煌
晝眠夕寐　藍筍象床　弦歌酒宴　接杯舉觞　矯手頓足　悅豫且康
嫡後嗣續　祭祀烝嘗　稽颡再拜　悚懼恐惶　箋牒簡要　顧答審詳
骸垢想浴　執熱願涼　驢騾犢特　駭躍超骧　誅斬賊盜　捕獲叛亡
布射僚丸　嵇琴阮嘯　恬筆倫紙　鈞巧任釣　釋紛利俗　竝皆佳妙
毛施淑姿　工颦妍笑　年矢每催　曦晖朗曜　璇玑懸斡　晦魄環照
指薪修祜　永綏吉劭　矩步引領　俯仰廊廟　束帶矜莊　徘徊瞻眺
孤陋寡聞　愚蒙等诮　謂語助者　焉哉乎也

除了“发”字还有没有重复？ 这就需要对每个字进行计数， 用字典(Dict)数据类型可以完成这种工作， 程序改为：

function checkall_thch(filename)
    ## 读入文件为一个长字符串
    s0 = read(filename, String)
    ## 去掉标点、空格与换行
    s = replace(s0, r"[　，。[[:space:]]" => s"")
    println(s)
    x = collect(s)
    if length(x) != 1000
        println("字数不等于1000！")
        return false
    end
    d = Dict()
    for xi in x
        d[xi] = get(d, xi, 0) + 1
    end
    ## 找到所以>1的值对应的键值
    for (k, v) in d
        if v>1
            println("“", k, "”出现", v, "次！")
        end 
    end 
    return length(d)==0
end 
checkall_thch("千字文繁体.txt")

结果发现有6个字重复，都是重复一次： “雲”，“昆”，“發”，“戚”，“巨”，“資”。 简体版还有“义”，“盘”，“诚”，“实”，“洁”，“并”字重复。

实际上， 这六处重复都是因为汉字简化引起的， 即使是繁体版，也是因为历史上的简化。

“云”：雲腾致雨；禅主云亭： “雲腾致雨”中的“雲”是气象中的云， “禅主云亭”中的“云”是地名“云云山”。

“昆”：玉出崐冈；昆池碣石： “玉出崐冈”中的昆应为“崐”或“崑”，指昆仑山。 “昆池碣石”中的昆指昆明湖。

“巨”：剑号巨阙；钜野洞庭： 巨阙是剑名， 巨野是简化的钜野，是地名。

“发”：周發殷汤；盖此身髮： 一个是出发的发， 一个是毛发的发， 在古文中是两个字。

“戚”：慼谢欢招；亲戚故旧： “慼”和“慽”都同“戚”， 指忧伤。

“资”：资父事君；务兹稼穑： “资”是供养； “兹”是助词，“这个”的意思。

“洁”：女慕贞絜；纨扇圆潔： “絜”原来读“xié”， 本意是指量物体的周围长度，也泛指衡量， 后来增加了“洁净”含义， 特意增加了一个带三点水的写法。 千字文中这两个字含义是一样的， 原文中用了不同的写法。

24.3 查找重复诗文

24.3.1 问题

一篇比较长的中文文本文件， 比如古诗词集， 长篇小说， 常常因为收集时的疏忽有比较长的文字会重复复制， 而且复制的内容没有连在一起。 用Julia的字符串处理功能找到这些重复内容以及所在的行号。

解决方法有两种思路：

• 利用正则表达式。优点是程序简洁，设计合理的话运行效率高， 缺点是设计困难，设计不合理运行效率不可容忍。
• 用字符串数组直接错位比对。优点是程序思路简单， 可以逐步分解问题解决，功能灵活， 缺点是程序长。

本例在Julia v1.4.0下调试成功。

24.3.2 Julia字符串知识

Julia的字符串是String类型。 字符串可以用整数下标访问，表面上看与字符数组功能相同， 但字符串的整数下标的含义是字节序号， 因为字符串使用Unicode编码， 每个字符占用的字节数可能有差异， 所以有些整数下标是非法下标。 对字符串可以用整数范围作为下标， 但是开始位置也要求是一个字符的开始位置而不能在一个字符编码的中间位置。 为了保证每次使用的整数下标是合法的字符位置， 用nextind(s, n)找到在第n个字节位置之后的第一个合法的字符位置下标。

为了用正常的数组处理方法来处理字符串中的字符， 用collect(s)可以将字符串s转换成一个字符数组， 每个元素是一个字符。

用join(x, delim)可以将字符串数组或者字符数组组合并成一个长字符串。

24.3.3 程序分解

为了找到重复部分， 假设文本文件的所有字符保存在一个数组x中， x的每个元素是仅有一个字符的字符串。 想法是， 制作x的副本y， 然后将x与y的元素位置错一个下标位置对齐比较， 错两个下标位置对齐比较， 等等， 找到错位对齐后连续的重合内容。 例如， 设x对应的字符串为"白日依山尽黄河入海流白日依山尽", 则错位10个字符后对其就可以找到"白日依山尽"为重复内容。

如下的函数找到两个等长数组对齐后的连续重合位置：

function array_parteq(x, y; minlen=5)
    n = length(x) # 元素个数
    @assert length(y)==n # 要求x, y长度相同
    eqr = x .== y # 对应元素比较结果的Bull型数组
    
    ## 查找连续的minlen以上个数的true
    eqind = Array{Int64, 1}() # 用来保存找到重合位置的下标
    eqlen = Array{Int64, 1}() # 用来保存找到的重合长度
    
    eqtrue = false # 当前是否连续true
    eqstart = 1 # 连续true 的开始下标
    eql = 0 # 连续true的长度
    for i = 1:n # 对每个元素循环
        if eqr[i] # 当前true
            if eqtrue # i-1为true
                eql += 1 # 继续当前的连续重合段
            else # 当前true， i-1为false, 开始一个新的连续重合段
                eql = 1 
                eqtrue = true
                eqstart = i
            end
        end
        if eqtrue && (!eqr[i] || i==n) 
            # 前面有连续重合段但是当前字符不重合或者当前字符是最后一个元素
            if eql >= minlen # 从istart开始的eql个连续为true且超过minlen
                push!(eqind, eqstart)
                push!(eqlen, eql)
                # else,  不超过minlen则不用处理
            end
            eqtrue = false # 设置保存的上一个比较结果为false
        end
    end # for i

    return (eqind, eqlen)
end # function

其中minlen选项指定多少个元素连续重合才算是重合。 因为无法预估有多少处重合， 所以在保存结果时用了push!()函数， 这样运行效率受到一定影响但是程序比较简洁。

有了对两个等长数组找到连续重合位置的程序后， 对同一个数组中前后不同位置的重复， 只要反复错位比较即可， 程序如下：

function array_parteq(x; minlen=5)
    y = copy(x)
    n = length(x)
    @assert n > 2*minlen
    eqindx = Array{Int64, 1}()
    eqindy = Array{Int64, 1}()
    eqlen = Array{Int64, 1}()
    eqx = Array{typeof(x), 1}()
    for k = (minlen+1):(n - minlen)
        eqik, eqlk = array_parteq(x[1:(n-k)], y[(k+1):n]; minlen=minlen)
        if length(eqik) > 0
            append!(eqindx, eqik)
            append!(eqindy, eqik .+ k)
            append!(eqlen, eqlk)
            for j in eachindex(eqik)
                ##println(x[eqik[j]:(eqik[j] + eqlk[j] - 1)])
                push!(eqx, x[eqik[j]:(eqik[j] + eqlk[j] - 1)])
            end
        end
    end
    return (eqindx, eqindy, eqlen, eqx)
    # 重复的前面部分下标，重复的后面部分下标，重复长度，重复的数组片段
end # function

以上的程序返回内容包括重复内容前一次出现位置（元素下标）， 后一次出现位置， 重复长度（重复元素个数）， 重复内容的数组。

如果用于文本文件查找重复， 可以先将文本文件转换成数组， 数组元素为单个字符组成的字符串。 这样找到重复位置和可以将找到重复内容， 并将重复内容转换成字符串。 但是， 重复位置是按字符序号计算的，不利于人工比对。 所以， 预先建立一个字符序号到行号的对应表， 比如用如下的函数：

function char_linenumber(x)
    n = length(x)
    y = Array{Int64}(undef, n)
    ln = 1
    for i = 1:n
        y[i] = ln
        if x[i] == "\n"
            ln += 1
        end
    end
    return y
end

结果是与字符型数组等长的下标数组， 每遇到一个换行符就将保存的行号加一。

有时重复内容会因为标点符号、空格、换行而打断， 所以下面的实现中还增加了允许剔除这些非文字内容的选项。

在Julia 1.0以上用read(文件名, String)将一个文本文件的各行读入为长字符串。 因为文本文件的换行符在不同操作系统中有所不同， 所以用replace()函数将不同的换行符统一替换成"\n"符。

下面的程序列表中findit()就是主要的函数。 在findit()中， 首先将内容读成一个各行组成的字符串数组， 然后连接成一个长字符串， 统一的换行符为"\n"， 利用逐字符循环在处理非文字内容的同时将字符序号与行号建立对应关系。 然后， 利用上面的数组中查找连续重复的函数查找重复， 这样找到的结果是字符位置和长度， 从中可以取出重复内容字符串， 并将字符位置转换成行号。 然后输出结果保存为输出文件即可。 输出中， 按重复内容长短由大到小排序。

24.3.4 程序列表

整体的程序写成一个模块如下：

## 查找文本文件中较长的重复内容，
## 以5个汉字为重复。

module FindReps

## 对于包含多行的字符数组，建立字符序号到行号的对应关系
## 输入的x是字符串数组，每个元素是一个字符（可为中文）
function char_linenumber(x::Array{Char,1})
    n = length(x)
    y = Array{Int64}(undef, n)
    ln = 1
    for i = 1:n
        y[i] = ln
        if x[i] == "\n"
            ln += 1
        end
    end
    return y
end

## 对一个长字符串，建立字符序号到行号的对应关系
function char_linenumber(x::String)
    n = length(x)
    y = Array{Int64}(undef, n)
    ind = 1
    ln = 1
    i = 1
    while i <= n
        xi = x[ind:ind]
        y[i] = ln
        i += 1
        ind = nextind(x, ind)
        if xi == "\n"
            ln += 1
        end
    end

    return y
end

## 对一个长字符串，建立字符序号到行号的对应关系
function byte_linenumber(x::String; include_ln=true)
    n = sizeof(x)
    y = Array{Int64}(undef, n)
    ln = 1
    j = 1 # 不计入换行符的字节序号
    for i=1:n
        y[i] = ln
        if thisind(x, i) == i && x[i] == '\n'
            ln += 1
            if !include_ln
                y[i] = -1
            end
        end
    end

    if !include_ln
        filter!(x -> x != -1, y)
    end

    return y
end


## 比较两个等长数组，找到相等的超过指定长度部分
function array_parteq(x, y; minlen=5)
    n = length(x) # 元素个数
    @assert length(y)==n # 要求x, y长度相同
    eqr = x .== y # 对应元素比较结果的Bull型数组

    ## 查找连续的minlen以上个数的true
    eqind = Array{Int64, 1}() # 用来保存找到重合位置的下标
    eqlen = Array{Int64, 1}() # 用来保存找到的重合长度

    eqtrue = false # 当前是否连续true
    eqstart = 1 # 连续true 的开始下标
    eql = 0 # 连续true的长度
    for i = 1:n # 对每个元素循环
        if eqr[i] # 当前true
            if eqtrue # i-1为true
                eql += 1 # 继续当前的连续重合段
            else # 当前true， i-1为false, 开始一个新的连续重合段
                eql = 1
                eqtrue = true
                eqstart = i
            end
        end
        if eqtrue && (!eqr[i] || i==n)
            # 前面有连续重合段但是当前字符不重合或者当前字符是最后一个元素
            if eql >= minlen # 从istart开始的eql个连续为true且超过minlen
                push!(eqind, eqstart)
                push!(eqlen, eql)
                # else,  不超过minlen则不用处理
            end
            eqtrue = false # 设置保存的上一个比较结果为false
        end
    end # for i

    return (eqind, eqlen)
end # function

## 比较同一个数组的不同位置有无重复内容，重复长度超过minlen
function array_parteq(x; minlen=5)
    y = copy(x)
    n = length(x)
    @assert n > 2*minlen
    eqindx = Array{Int64, 1}()
    eqindy = Array{Int64, 1}()
    eqlen = Array{Int64, 1}()
    eqx = Array{typeof(x), 1}()
    for k = (minlen+1):(n - minlen)
        eqik, eqlk = array_parteq(x[1:(n-k)], y[(k+1):n]; minlen=minlen)
        if length(eqik) > 0
            append!(eqindx, eqik)
            append!(eqindy, eqik .+ k)
            append!(eqlen, eqlk)
            for j in eachindex(eqik)
                ##println(x[eqik[j]:(eqik[j] + eqlk[j] - 1)])
                push!(eqx, x[eqik[j]:(eqik[j] + eqlk[j] - 1)])
            end
        end
    end
    return (eqindx, eqindy, eqlen, eqx)
    # 重复的前面部分下标，重复的后面部分下标，重复长度，重复的数组片段
end # function


## 从一个文本文件中查找重复内容
function findit(inf, outf="tmp1.txt";
    minlen=5, keep_punct=false, sorted=true)
    ## 将文件读入为一个长字符串
    s0 = read(inf, String)
    ## 将"\r\n", "\n\r"统一为"\n"
    s0 = replace(s0, r"\r\n|\n\r" => s"\n")
    n = length(s0)
    ## x用来保存每个元素一个字的字符数组
    x = Array{Char}(undef, n)
    ## linenums用来保存每个字符的序号到行号的对应
    linenums = Array{Int}(undef, n)

    punct_set = (" ", "\n", "，", "。", "：", "！",
        "？", "“", "”", "=", ",", ".", ";", "!", ":")
    ## 将字符串转换成数组，去掉空格、换行、标点，建立字符下标到行号的对应
    nc = 0 # nc是删除后剩余字符个数计数器
    ind = 1 # 当前字符下标
    linec = 1 # 当前行号
    i = 1 # i是原始字符序号
    while i <= n
        si = s0[ind]
        if keep_punct ||
            (!keep_punct && !(si in punct_set))
            nc += 1
            x[nc] = si
            linenums[nc] = linec
        end
        if si == "\n"
            linec += 1
        end
        i += 1
        ind = nextind(s0, ind)
    end

    x = copy(x[1:nc])
    linenums = copy(linenums[1:nc])
    ##println(array2string(x))
    ##println(linenums)

    eqindx, eqindy, eqlen, eqx = array_parteq(x; minlen=minlen)

    reptext = Array{String}(undef, length(eqx))
    for i in eachindex(eqx)
        reptext[i] = join(eqx[i], "")
    end
    ##print(reptext)

    ## 按重复内容的长度由大到小排序
    if sorted && length(eqx) > 0
        # 按eqindx的次序对结果重排序，类似于R的order()函数
        indsort = sortperm(eqlen, rev=true)
        eqindx = eqindx[indsort]
        eqindy = eqindy[indsort]
        eqlen = eqlen[indsort]
        reptext = reptext[indsort]
    end

    sout = open(outf, "w")
    for i in eachindex(eqindx)
        println(sout, "\n\n重复NO.", i, " =====")
        println(sout, "前行号：", linenums[eqindx[i]])
        println(sout, "后行号：", linenums[eqindy[i]])
        println(sout, "匹配长度：", eqlen[i])
        println(sout, "匹配内容：\n", reptext[i])
    end
    close(sout)
end # findit

function findit_regex(inf, outf="tmp1.txt";
    minlen=5, keep_punct=false, sorted=true)
    punct_set = (" ", "，", "。", "：", "！",
        "？", "“", "”", "=", ",", ".", ";", "!", ":")
    pat = Regex("(?s)(\\w{$minlen,}).*?(\\1)")
    indx = Array{Int64, 1}() # 重复前段的开始行号
    indy = Array{Int64, 1}() # 重复后段的开始行号
    mlen = Array{Int64, 1}() # 重复字符数
    ma = Array{String, 1}()  # 重复内容

    ## 将文件读入为一个长字符串
    s0 = read(inf, String)
    ## 将"\r\n", "\n\r"统一为"\n"
    s0 = replace(s0, r"\r\n|\n\r" => s"\n")
    ## 如果需要忽略标点，去掉标点
    punct_pat = Regex(string("[", join(punct_set, ""), "]"))
    if !keep_punct
        s0 = replace(s0, punct_pat => s"")
        ## 建立字节序号到行号的对应关系，不计入换行符
        linenums = byte_linenumber(s0, include_ln=false)
        ## 将换行符删除
        s0 = replace(s0, r"\n" => s"")
    else
        linenums = byte_linenumber(s0, include_ln=true)
    end

    for i in eachmatch(pat, s0, overlap=true)
        push!(indx, i.offsets[1])
        push!(indy, i.offsets[2])
        ma1 = i.captures[1]
        push!(mlen, length(ma1))
        push!(ma, ma1)
    end

    ## 按重复内容的长度由大到小排序
    if length(ma) > 0
        # 按eqindx的次序对结果重排序，类似于R的order()函数
        indsort = sortperm(mlen, rev=true)
        indx = indx[indsort]
        indy = indy[indsort]
        mlen = mlen[indsort]
        ma = ma[indsort]
    end

    ## 因为长的重复内容一定也可以产生短的部分重复，
    ## 所以查找这些短的重复并将其标注删除
    goodma = Array{Bool}(undef, length(ma))
    goodma .= true
    nmatch = length(ma)
    if nmatch>0
        for i in nmatch:-1:1
            ma1 = ma[i]
            for j in 1:(i-1)
                if occursin(ma1, ma[j]) && 
                    abs(indx[i] - indx[j]) < sizeof(ma[j])
                    goodma[i] = false
                    break
                end
            end
        end
        indx = indx[goodma]
        indy = indy[goodma]
        mlen = mlen[goodma]
        ma = ma[goodma]
    end

    sout = open(outf, "w")
    for i in eachindex(ma)
        println(sout, "\n\n重复NO.", i, " =====")
        println(sout, "前行号：", linenums[indx[i]])
        println(sout, "后行号：", linenums[indy[i]])
        println(sout, "匹配长度：", mlen[i])
        println(sout, "匹配内容：\n", ma[i])
    end
    close(sout)

end # findit_regex

end # module FindReps

24.3.5 用正则表达式解决问题

正则表达式可以简洁地解决字符串问题。 如下的模式可以表示minlen个字符以上的重复：

Regex("(?s)(\\w{$minlen,}).*?(\\1)")

如果存在多处重复， 以上模式只能找到其中之一， 可以用eachmatch()循环并指定overlap=true选项。 但是， 一旦指定overlap=true， 匹配的速度就严重降低， 而且长的重复内容会产生许多短的重复内容， 比如重复内容"12345678"同时也会产生重复内容"2345678"， "345678"和"45678"。 需要找到这些短的已找到的重复内容， 原则是短的内容是长的内容的一部分而且所处的字节位置差距小于长的重复内容的字节数。

注意正则表达式匹配的位置offsets是按字节计算的， 所以为了将字节位置对应到行号， 编写了如下的自定义函数。 此函数允许去掉换行符后对应。

function byte_linenumber(x::String; include_ln=true)
    n = sizeof(x)
    y = Array{Int64}(undef, n)
    ln = 1
    j = 1 # 不计入换行符的字节序号
    for i=1:n
        y[i] = ln
        if thisind(x, i) == i && x[i] == '\n'
            ln += 1
            if !include_ln
                y[i] = -1
            end
        end
    end

    if !include_ln
        filter!(x -> x != -1, y)
    end

    return y
end

上面的程序列表中的findit_regex()函数实现了用正则表达式查找文本文件重复内容。

24.3.6 改进思路

• 定义一个专用的数据类型， 保存重复的前段字符位置、行号、后端字符位置、行号、重复内容、重复字符数。
• 有时重复内容比较长但是其中仅有一两个字不同， 编写程序允许这样的模糊重复。
• 改进正则表达式方法的运行效率。

24.4 用字典类型作频数计数

24.4.1 频率计数

在基本的描述统计中， 经常需要对某个离散取值的变量计算其频数表， 即每个不同值出现的次数。 如果不利用字典类型， 可以先找到所有的不同值， 将每个值与一个序号对应， 然后建立一个一维数组计数， 每个数组元素与一个变量值对应。

利用字典， 我们不需要预先找到所有不同值，而是直接用字典计数， 每个键值是一个不同的变量值， 每个值是一个计数值。 如

function freq(x)
    y = Dict()
    for xi in x
        y[xi] = get(y, xi, 0) + 1
    end
    return y
end

di = freq("disillusionment")
di

Dict{Any,Any} with 10 entries:
  'n' => 2
  'd' => 1
  'i' => 3
  's' => 2
  'l' => 2
  'u' => 1
  'o' => 1
  'm' => 1
  'e' => 1
  't' => 1

24.4.2 反向映射

将字典看成映射， 能否求其反向的映射呢？ 这里的问题是， 有可能有两个不同的键对应相同的值。 所以，保险起见， 将值作为新的键， 而与值对应的原来的键组成一维数组当作新的值。 例如：

function dict_reverse(dict)
    y = Dict()
    for k in keys(dict)
        v = dict[k]
        if v in keys(y)
            push!(y[v], k)
        else
            y[v] = [k]
        end
    end
    return y
end

dict_reverse(di)

Dict{Any,Any} with 3 entries:
  2 => ['n', 's', 'l']
  3 => ['i']
  1 => ['d', 'u', 'o', 'm', 'e', 't']

可以用get!(collect, key, default)函数简化上面的反向映射程序， 此函数在键存在时返回对应的值， 在键不存在时先建立键到指定的缺省值的映射，然后返回该缺省值。 函数如：

function dict_reverse2(dict)
    y = Dict()
    for k in keys(dict)
        v = dict[k]
        push!(get!(y, v, []), k)
    end
    return y
end

dict_reverse2(di)

Dict{Any,Any} with 3 entries:
  2 => Any['n', 's', 'l']
  3 => Any['i']
  1 => Any['d', 'u', 'o', 'm', 'e', 't']

第二个版本的结果还是略有差别， 因为生成缺省值时用了长度为零的数组， 就无法确定元素类型， 所以值的数组是Any类型数组， 而第一个版本则可以用更具体的类型。

24.4.3 频数表的排序输出

频数表最好能够输出为按频数从高到低排列的格式。 因为字典是没有固定次序的， 所以这时不能用字典给出结果， 可以输出可取值和频数值的两个数组， 或者输出可取值和频数值的元组的数组。 例如：

function freq_order(x)
    y = Dict()
    for xi in x
        y[xi] = get(y, xi, 0) + 1
    end
    
    ## 将字典转换成二元组的数组
    res = [(level, y[level]) for level in keys(y)]
    sort!(res, by = x -> x[2], rev=true)
    return res
end

freq_order("disillusionment")

10-element Array{Tuple{Char,Int64},1}:
 ('i', 3)
 ('n', 2)
 ('s', 2)
 ('l', 2)
 ('d', 1)
 ('u', 1)
 ('o', 1)
 ('m', 1)
 ('e', 1)
 ('t', 1)

24.4.4 一篇英文作品的词频分析

从Gutenberg项目下载了傲慢与偏见的纯文本文件， 读入为各行组成的字符串如下， 将标点换成空格， 然后拆分成单词的数组， 用上面的函数对单词进行频数统计。 可以发现， 最高频的主要是代词、助词。

## 从一个文本文件，拆分出所有的单词并小写，去掉所有标点符号
function getwords(filename; skiplines=0)
    ## 读入为一个长字符串，并删除开始若干行
    lines = readlines(filename)[(skiplines+1):end]
    s0 = join(lines, " ")
    
    ## 将标点符号都改为空格
    s0 = replace(s0, r"[.!?;,:\"\']" => s"" )
    
    ## 按照空格拆分单词
    x = split(s0, r"[ ]+")
    x = lowercase.(x)
    ##print(x[1:100])
    
    return x
end

function word_freqs(filename; skiplines=0, most_frequent=50)
    ## 读入各行
    words = getwords(filename, skiplines = skiplines)
    res = freq_order(words)
    for (word, freq) in res[1:most_frequent]
        println(word, ": ", freq)
    end
    
    println("不同单词的个数：", length(res))
    println("最大频数和单词：", res[1][2], " ", res[1][1])
    
    return res
end

word_freqs("Pride and Prejudice by Jane Austen.txt", skiplines=39)

24.5 用马氏链方法生成随机句子

24.5.1 问题和步骤

从一个英文词典中随机抽取若干个单词， 能够组成一个句子吗？ 一般不能， 一个句子的前后的单词之间是有关系的， 随机抽取的单词前后之间是独立的。

用一种简单的马氏链模型来表示句子的单词之间的关系。 设\(x_1, x_2\)是前两个单词， 则单词\(x_3\)出现在\(x_1, x_2\)之后的概率是依赖于\(x_1, x_2\)的。 我们可以统计不同的\((x_1, x_2)\)组合的概率， 以及给定\((x_1, x_2)\)后\(x_3\)紧随其后的概率。 根据这样统计出来的概率模型去模拟生成\((x_1, x_2)\)， 从条件概率\(P(x_3 | x_1, x_2)\)再生成\(x_3\)， 从条件概率\(P(x_4 | x_2, x_3)\)生成\(x_4\)， 如此生成一个句子。

还要考虑句子的开头和结尾问题， 有些单词可以出现在句子开头， 有些单词则不能； 结尾也是如此。 所以我们将句子的开头、结尾也作为单词进行分析。

条件概率可以是给定前一个单词， 前两个单词， 前三个单词，等等。

为了估计这些概率， 读入一篇英文的文章， 比如一篇小说， 可以从Gutenburg project网站找到这样的文本文件。 利用这样的文章， 将其拆分成句子， 得到许多句子的样本。 然后， 估计句子中相连的两个词的组合的概率， 以及给定前面两个词以后下一个词的条件概率 （也可以是前面一个词、前面三个词等情况）。 从这些概率随机抽样构造随机句子。

24.5.2 读入文章拆分句子

写如下的从一个文本文件读入文章并切分为句子的函数， 用几段文本进行测试。 设文件“test-markov.txt”内容如下：

It is a truth universally acknowledged, that a single man in possession
of a good fortune, must be in want of a wife.

However little known the feelings or views of such a man may be on his
first entering a neighbourhood, this truth is so well fixed in the minds
of the surrounding families, that he is considered the rightful property
of some one or other of their daughters.

"My dear Mr. Bennet," said his lady to him one day, "have you heard that
Netherfield Park is let at last?"

Mr. Bennet replied that he had not.

"But it is," returned she; "for Mrs. Long has just been here, and she
told me all about it."

Mr. Bennet made no answer.

"Do you not want to know who has taken it?" cried his wife impatiently.

"_You_ want to tell me, and I have no objection to hearing it."

This was invitation enough.

"Why, my dear, you must know, Mrs. Long says that Netherfield is taken
by a young man of large fortune from the north of England; that he came
down on Monday in a chaise and four to see the place, and was so much
delighted with it, that he agreed with Mr. Morris immediately; that he
is to take possession before Michaelmas, and some of his servants are to
be in the house by the end of next week."

"What is his name?"

"Bingley."

"Is he married or single?"

"Oh! Single, my dear, to be sure! A single man of large fortune; four or
five thousand a year. What a fine thing for our girls!"

"How so? How can it affect them?"

"My dear Mr. Bennet," replied his wife, "how can you be so tiresome! You
must know that I am thinking of his marrying one of them."

"Is that his design in settling here?"

"Design! Nonsense, how can you talk so! But it is very likely that he
_may_ fall in love with one of them, and therefore you must visit him as
soon as he comes."

"I see no occasion for that. You and the girls may go, or you may send
them by themselves, which perhaps will be still better, for as you are
as handsome as any of them, Mr. Bingley may like you the best of the
party."

"My dear, you flatter me. I certainly _have_ had my share of beauty, but
I do not pretend to be anything extraordinary now. When a woman has five
grown-up daughters, she ought to give over thinking of her own beauty."

"In such cases, a woman has not often much beauty to think of."

"But, my dear, you must indeed go and see Mr. Bingley when he comes into
the neighbourhood."

"It is more than I engage for, I assure you."

"But consider your daughters. Only think what an establishment it would
be for one of them. Sir William and Lady Lucas are determined to
go, merely on that account, for in general, you know, they visit no
newcomers. Indeed you must go, for it will be impossible for _us_ to
visit him if you do not."

"You are over-scrupulous, surely. I dare say Mr. Bingley will be very
glad to see you; and I will send a few lines by you to assure him of my
hearty consent to his marrying whichever he chooses of the girls; though
I must throw in a good word for my little Lizzy."

"I desire you will do no such thing. Lizzy is not a bit better than the
others; and I am sure she is not half so handsome as Jane, nor half so
good-humoured as Lydia. But you are always giving _her_ the preference."

"They have none of them much to recommend them," replied he; "they are
all silly and ignorant like other girls; but Lizzy has something more of
quickness than her sisters."

"Mr. Bennet, how _can_ you abuse your own children in such a way? You
take delight in vexing me. You have no compassion for my poor nerves."

"You mistake me, my dear. I have a high respect for your nerves. They
are my old friends. I have heard you mention them with consideration
these last twenty years at least."

"Ah, you do not know what I suffer."

"But I hope you will get over it, and live to see many young men of four
thousand a year come into the neighbourhood."

"It will be no use to us, if twenty such should come, since you will not
visit them."

"Depend upon it, my dear, that when there are twenty, I will visit them
all."

Mr. Bennet was so odd a mixture of quick parts, sarcastic humour,
reserve, and caprice, that the experience of three-and-twenty years had
been insufficient to make his wife understand his character. _Her_ mind
was less difficult to develop. She was a woman of mean understanding,
little information, and uncertain temper. When she was discontented,
she fancied herself nervous. The business of her life was to get her
daughters married; its solace was visiting and news.

## 切分句子的程序
## 读入一篇文章，切分句子为数组。
## 用句点空格，句点双撇号作为句子末尾标志。
function getsentences(filename; skiplines=0)
    ## 读入为一个长字符串，并删除开始若干行
    lines = readlines(filename)[(skiplines+1):end]
    s0 = join(lines, " ")
    ## 将常见的缩略词Mr., Mrs.的句点去掉
    s0 = replace(s0, r"(Mr|Mrs)[.]" => s"\1")
    ## 按照句点或叹号或问号，冒号加空格或双撇号作为分隔拆分句子
    x = split(s0, r"[.!?;:][ \"]")
    ## 去掉标点符号，去掉前导和尾随空格
    for i in eachindex(x)
        x[i] = replace(x[i], r"[^a-zA-Z ]" => s"")
        x[i] = replace(x[i], r" +" => s" ")
        x[i] = strip(x[i])
        x[i] = lowercase(x[i])
    end
    return x
end

测试：

sens = getsentences("test-markov.txt")
for s in sens[1:20]
    println(s)
end

部分结果如下：

it is a truth universally acknowledged that a single 
man in possession of a good fortune must be in want of a wife

however little known the feelings or views of such a man 
may be on his first entering a neighbourhood this truth 
is so well fixed in the minds of the surrounding families 
that he is considered the rightful property of some one 
or other of their daughters

mr bennet replied that he had not

for mrs long has just been here and she told me all about it

cried his wife impatiently

this was invitation enough

what is his name

bingley

is he married or single

oh

这说明拆分句子的程序是成功的， 但要注意有些句子仅有一个单词， 因为不用逗号作为句子结尾标志， 所以有时句子很长。

24.5.3 估计概率

设我们考虑前两个单词对下一个单词的影响。 因为句子开头和结尾特殊， 所以将每个句子开头和结尾添加两个表示开头和结尾的特殊单词， 如aaaaa和zzzzz。

用一个词典(Dict)结构记录 统计从前面的单词序列\((x_1, x_2)\)到紧随单词\(x_3\)的词频， 称\((x_1, x_2)\)为前词组，可以由一个、二个、三个等组成， 后词是一个词。 \(x_3\)为后词。 结果用Dict类型保存， 以前词组作为键， 值的第一个元素为键的频数， 第二个元素是用字典表示的后词的频数统计。

## freqs: 频数统计结果；
## sentence: 字符串，一个句子;
## prewords: 前词组的单词个数，如1,2,3等
function anasentence!(freqs, sentence; prewords=2)
    # 每个sentence开头用aaaaa标志，结尾用zzzzz标志。
    sentence_begin = "aaaaa"
    sentence_end = "zzzzz"
    x0 = split(sentence)
    x = vcat(sentence_begin, x0, sentence_end)
    n = length(x)
    if prewords >= n
        prewords = n-1
    end
    for i=prewords:(n-1)
        key = Tuple(x[(i-prewords+1):i])
        if key ∈ keys(freqs)
            freqs[key][1] += 1
            if x[i+1] ∈ keys(freqs[key][2])
                freqs[key][2][x[i+1]] += 1
            else
                freqs[key][2][x[i+1]] = 1
            end
        else
            freqs[key] = [1, Dict()]
            freqs[key][2][x[i+1]] = 1
        end
    end
    return nothing
end

测试运行如：

freqs = Dict()
anasentence!(freqs, "you want to tell me and i have no objection to hearing it", prewords=1)
anasentence!(freqs, "bingley", prewords=1)
freqs

Dict{Any,Any} with 14 entries:
  ("bingley",)   => Any[1, Dict{Any,Any}("zzzzz"=>1)]
  ("you",)       => Any[1, Dict{Any,Any}("want"=>1)]
  ("no",)        => Any[1, Dict{Any,Any}("objection"=>1)]
  ("hearing",)   => Any[1, Dict{Any,Any}("it"=>1)]
  ("me",)        => Any[1, Dict{Any,Any}("and"=>1)]
  ("tell",)      => Any[1, Dict{Any,Any}("me"=>1)]
  ("objection",) => Any[1, Dict{Any,Any}("to"=>1)]
  ("aaaaa",)     => Any[2, Dict{Any,Any}("bingley"=>1,"you"=>1)]
  ("it",)        => Any[1, Dict{Any,Any}("zzzzz"=>1)]
  ("i",)         => Any[1, Dict{Any,Any}("have"=>1)]
  ("and",)       => Any[1, Dict{Any,Any}("i"=>1)]
  ("have",)      => Any[1, Dict{Any,Any}("no"=>1)]
  ("to",)        => Any[2, Dict{Any,Any}("tell"=>1,"hearing"=>1)]
  ("want",)      => Any[1, Dict{Any,Any}("to"=>1)]

freqs = Dict()
anasentence!(freqs, "you want to tell me and i have no objection to hearing it", prewords=2)
anasentence!(freqs, "bingley", prewords=2)
freqs

Dict{Any,Any} with 14 entries:
  ("you", "want")      => Any[1, Dict{Any,Any}("to"=>1)]
  ("me", "and")        => Any[1, Dict{Any,Any}("i"=>1)]
  ("aaaaa", "bingley") => Any[1, Dict{Any,Any}("zzzzz"=>1)]
  ("have", "no")       => Any[1, Dict{Any,Any}("objection"=>1)]
  ("no", "objection")  => Any[1, Dict{Any,Any}("to"=>1)]
  ("to", "tell")       => Any[1, Dict{Any,Any}("me"=>1)]
  ("want", "to")       => Any[1, Dict{Any,Any}("tell"=>1)]
  ("tell", "me")       => Any[1, Dict{Any,Any}("and"=>1)]
  ("to", "hearing")    => Any[1, Dict{Any,Any}("it"=>1)]
  ("hearing", "it")    => Any[1, Dict{Any,Any}("zzzzz"=>1)]
  ("and", "i")         => Any[1, Dict{Any,Any}("have"=>1)]
  ("objection", "to")  => Any[1, Dict{Any,Any}("hearing"=>1)]
  ("aaaaa", "you")     => Any[1, Dict{Any,Any}("want"=>1)]
  ("i", "have")        => Any[1, Dict{Any,Any}("no"=>1)]

有了对一个句子的统计， 只要对整篇文章所有句子遍历一遍， 每次更新词频数据freqs即可。

对所有句子的统计：

## x为句子的数组
function anasentences(x; prewords=2)
    freqs = Dict()
    for xi in x
        anasentence!(freqs, xi, prewords=prewords)
    end
    return freqs
end

为了方便按概率抽样， 应该将统计得到结果转换成句首前词组概率， 前词组到后词的条件概率。 函数如下：

function freq2prob(dict)
    sentence_begin = "aaaaa"
    sentence_end = "zzzzz"
    
    ## 句首前词组的概率表
    heads = Dict(prefix => dict[prefix][1] 
        for prefix in keys(dict) 
            if prefix[1] == sentence_begin)
    nheads :: Float64 = sum(values(heads))
    for prefix in keys(heads)
        heads[prefix] /= nheads
    end

    ## 各个前词组对应到后词的条件概率
    chains = Dict(prefix => dict[prefix][2]  
        for prefix in keys(dict))
    for prefix in keys(chains)
        npost :: Float64 = sum(values(chains[prefix]))
        for word in keys(chains[prefix])
            chains[prefix][word] /= npost
        end
    end
    return heads, chains
end

24.5.4 生成随机句子

有了这些概率表和条件概率表， 就可以生成一个随机句子了。 方法是， 先按照句首前词组的概率抽取一个句首， 从句首的后词中按条件概率抽取一个后词， 组成新的前词组， 根据新的前词组的条件概率表再抽取一个后词， 如此继续。 如果抽取到了句尾， 就结束并返回随机句子。 如果生成的某个前词组没有后词（不在统计的前词组中）， 就从句首重新抽取。

不考虑运算效率， 先给一个从存储单词概率的词典中按概率随机抽取一个单词的函数：

## 从一个小规模的频数表按比例抽取的函数
## dict是键到概率的映射字典
function rdiscrete(dict)
    u = rand()
    cump = 0.0
    for (k, v) in dict
        cump += v
        if u <= cump
            return k
        end
    end
    return nothing
end

生成随机句子的函数：

## 输入句首词组的概率表和条件概率表，生成一个随机句子
function sentence_sample(heads, chains, prewords=2)
    sentence_begin = "aaaaa"
    sentence_end = "zzzzz"
    
    ## 可能抽取到无法继续的链，就从头重复
    while true
        ## 抽取句首的前词组
        newpre = rdiscrete(heads)
        ## 句子的单词的数组
        x = collect(newpre)
        
        ## 反复抽取后词，如果无对应的后词则组句失败从头再来
        ## 如果抽取到句尾标志则生成句子结果
        while true
            ## 根据newpre抽取后词
            if newpre in keys(chains) 
                suf = rdiscrete(chains[newpre])
                push!(x, suf)
            else 
                break # 重新生成句首
            end 
            
            ## 如果后词是句尾，返回抽取结果
            if suf == sentence_end
                return join(x[2:(end-1)], " ")
            end
            
            ## 将前词组的后半部分与抽取的后词组成新的前词组
            if length(newpre) < prewords
                newpre = (newpre..., suf)
            else
                newpre = (newpre[2:end]..., suf)
            end
        end # while true
        
    end # while true
    
end # function

24.5.5 测试已有程序

下面将所有已有程序整合为一个程序文件， 并用一些测试文本进行测试。

## 切分句子的程序
## 读入一篇文章，切分句子为数组。
## 用句点空格，句点双撇号作为句子末尾标志。
function getsentences(filename; skiplines=0)
    ## 读入为一个长字符串，并删除开始若干行
    lines = readlines(filename)[(skiplines+1):end]
    s0 = join(lines, " ")
    ## 将常见的缩略词Mr., Mrs.的句点去掉
    s0 = replace(s0, r"(Mr|Mrs)[.]" => s"\1")
    ## 按照句点或叹号或问号，冒号加空格或双撇号作为分隔拆分句子
    x = split(s0, r"[.!?;:][ \"]")
    ## 去掉标点符号，去掉前导和尾随空格
    for i in eachindex(x)
        x[i] = replace(x[i], r"[^a-zA-Z ]" => s"")
        x[i] = replace(x[i], r" +" => s" ")
        x[i] = strip(x[i])
        x[i] = lowercase(x[i])
    end
    return x
end

## 分析一个句子，更新频数统计结果
## freqs: 频数统计结果；
## sentence: 字符串，一个句子;
## prewords: 前词组的单词个数，如1,2,3等
function anasentence!(freqs, sentence; prewords=2)
    # 每个sentence开头用aaaaa标志，结尾用zzzzz标志。
    sentence_begin = "aaaaa"
    sentence_end = "zzzzz"
    x0 = split(sentence)
    x = vcat(sentence_begin, x0, sentence_end)
    n = length(x)
    if prewords >= n
        prewords = n-1
    end
    for i=prewords:(n-1)
        key = Tuple(x[(i-prewords+1):i])
        if key ∈ keys(freqs)
            freqs[key][1] += 1.0
            if x[i+1] ∈ keys(freqs[key][2])
                freqs[key][2][x[i+1]] += 1.0
            else
                freqs[key][2][x[i+1]] = 1.0
            end
        else
            freqs[key] = [1.0, Dict()]
            freqs[key][2][x[i+1]] = 1.0
        end
    end
    return nothing
end

## 输入句子的词组，输出频数统计
function anasentences(sentences; prewords=2)
    freqs = Dict()
    for xi in sentences
        anasentence!(freqs, xi, prewords=prewords)
    end
    return freqs
end

## 将频数统计转换成句首词组的概率，和给定前词后各个后词的条件概率
function freq2prob(dict)
    sentence_begin = "aaaaa"
    sentence_end = "zzzzz"
    
    ## 句首前词组的概率表
    heads = Dict(prefix => dict[prefix][1]
        for prefix in keys(dict) 
            if prefix[1] == sentence_begin)
    nheads = sum(values(heads))
    for prefix in keys(heads)
        heads[prefix] /= nheads
    end

    ## 各个前词组对应到后词的条件概率
    chains = Dict(prefix => dict[prefix][2]
        for prefix in keys(dict))
    for prefix in keys(chains)
        npost = sum(values(chains[prefix]))
        for word in keys(chains[prefix])
            chains[prefix][word] /= npost
        end
    end
    return heads, chains
end

## 从概率表（用字典表示）生成一个随机抽样的程序
## 效率有待改进，或查找Julia标准库函数
function rdiscrete(dict)
    u = rand()
    cump = 0.0
    for (k, v) in dict
        cump += v
        if u <= cump
            return k
        end
    end
    return nothing
end

## 输入句首词组概率表和条件概率表，输出一个随机句子
function sentence_sample(heads, chains; prewords=2)
    sentence_begin = "aaaaa"
    sentence_end = "zzzzz"
    
    ## 可能抽取到无法继续的链，就从头重复
    while true
        ## 抽取句首的前词组
        newpre = rdiscrete(heads)
        ## 句子的单词的数组
        x = collect(newpre)
        
        ## 反复抽取后词，如果无对应的后词则组句失败从头再来
        ## 如果抽取到句尾标志则生成句子结果
        while true
            ## 根据newpre抽取后词
            if newpre in keys(chains) 
                suf = rdiscrete(chains[newpre])
                push!(x, suf)
            else 
                break # 重新生成句首
            end 
            
            ## 如果后词是句尾，返回抽取结果
            if suf == sentence_end
                return join(x[2:(end-1)], " ")
            end
            
            ## 将前词组的后半部分与抽取的后词组成新的前词组
            if length(newpre) < prewords
                newpre = (newpre..., suf)
            else
                newpre = (newpre[2:end]..., suf)
            end
        end # while true
        
    end # while true
    
end # function

在上面的anasentence!函数中， 将计数的初值1改成了1.0， 这样后面变成小于1的概率值就没有类型问题。

测试：

## 读入一篇短文章，转换成句子
sens = getsentences("test-markov.txt")
## 从句子的词组，生成频数统计结果
freqs = anasentences(sens, prewords=2)
## 转换为句首词组概率和条件概率
heads, chains = freq2prob(freqs)
## 生成10个随机句子
for i in 1:10
    println(sentence_sample(heads, chains, prewords=2))
end

结果：

its solace was visiting and news
nonsense how can you talk so
my dear to be in the minds of the party
you mistake me my dear to be in want of a good fortune must be in want of a wife
but you are overscrupulous surely
you want to know who has taken it
however little known the feelings or views of such a man may be on his first entering a neighbourhood this truth is so well fixed in the minds of the party
i have heard you mention them with consideration these last twenty years at least
you mistake me my dear mr bennet was so much delighted with it that he is considered the rightful property of some one or other of their daughters
i certainly have had my share of beauty but i do not

这些句子表面看是合乎语法的句子， 但是实际含义则牛唇不对马嘴。

上面的调用过程比较麻烦， 我们写一个输入一个文件名， 生成指定个数的随机句子的函数：

## 输入文本文件名，输出指定个数的随机句子的数组
function file2ramdom_sentences(filename; n=1, skiplines=0, prewords=2)
    sentences = getsentences("test-markov.txt", skiplines=skiplines)
    ## 从句子的词组，生成频数统计结果
    freqs = anasentences(sentences, prewords=prewords)
    ## 转换为句首词组概率和条件概率
    heads, chains = freq2prob(freqs)
    ## 生成n个随机句子
    rand_sens = []
    for i in 1:n
        push!(rand_sen, 
            sentence_sample(heads, chains, prewords=2))
    end
    return rand_sens
end # function

24.5.6 制作模块和闭包

上面的程序自己用还是可以的， 如果要给别人用， 就有许多不必要的细节。 通用的程序（不仅仅给程序员自己使用的程序）一般要进行封装， 使得用户只看到必须的使用接口。 Julia的模块可以实现这样的目的， 封装到一个模块后， 我们可以用export命名仅输出file2random_sentences()函数。

但是，这样就不方便重复地生成多批句子（每一批都要重复读入原始文本）， 也不方便扩展， 比如， 从多个文本文件生成词频， 从自己的句子库生成词频。

因为马氏链随机抽样依赖的是概率表， 所以我们可以生成一个抽样器， 这个抽样器是一个函数， 每次调用抽样器都可以产生一个随机句子， 而不需要重复分析原始文本的工作。 这就需要保存生成的概率表， 需要抽样器能访问独立的概率表， 也就是说， 可以有两个抽样器使用不同的概率表。 这样， 使用全局变量保存概率表就不够好。 我们用闭包(closure)来解决这个问题。 闭包是一个函数的内嵌函数， 被作为了函数的返回值， 因为Julia的句法作用域规则， 闭包会包含定义它的函数的局部空间中的变量。 这样， 每个抽样器就可以保存自己的概率表。

另一种办法是为概率表设计一个数据结构（使用struct）， 然后生成随机句子的程序一该数据结构为输入。

下面的程序将上面的已有程序进行了修改， 写成了模块。 修改包括：

• 句子开头和结尾标志定义成了模块的全局常值变量；
• 将注释改成了函数名前面三双撇号包括的文档的格式；
• 为用户提供了从句子数组生成的抽样器和从文本文件生成的抽样器， 用了多重派发和重载使用相同的函数名。

module MarkovArticle

export getsentences, make_sentence_sampler

const sentence_begin = "aaaaa"
const sentence_end = "zzzzz"

"""
读入一篇文章切分成句子的数组。

用句点空格，句点双撇号作为句子末尾标志。
句点也可以是叹号、问号、分号、冒号。
"""
function getsentences(filename; skiplines=0)
    ## 读入为一个长字符串，并删除开始若干行
    lines = readlines(filename)[(skiplines+1):end]
    s0 = join(lines, " ")
    ## 将常见的缩略词Mr., Mrs.的句点去掉
    s0 = replace(s0, r"(Mr|Mrs)[.]" => s"\1")
    ## 按照句点或叹号或问号，冒号加空格或双撇号作为分隔拆分句子
    x = split(s0, r"[.!?;:][ \"]")
    ## 去掉标点符号，去掉前导和尾随空格
    for i in eachindex(x)
        x[i] = replace(x[i], r"[^a-zA-Z ]" => s"")
        x[i] = replace(x[i], r" +" => s" ")
        x[i] = strip(x[i])
        x[i] = lowercase(x[i])
    end
    return [string(xi) for xi in x]
end

"""
分析一个句子，更新频数统计结果

Input:
  freqs: 频数统计结果；
  sentence: 字符串，一个句子;
  prewords: 前词组的单词个数，如1,2,3等
"""
function anasentence!(freqs, sentence; prewords=2)
    # 每个sentence开头用sentence_begin(aaaaa)标志，
    # 结尾用sentence_end(zzzzz)标志。
    x0 = split(sentence)
    x = vcat(sentence_begin, x0, sentence_end)
    n = length(x)
    if prewords >= n
        prewords = n-1
    end
    for i=prewords:(n-1)
        key = Tuple(x[(i-prewords+1):i])
        if key ∈ keys(freqs)
            freqs[key][1] += 1.0
            if x[i+1] ∈ keys(freqs[key][2])
                freqs[key][2][x[i+1]] += 1.0
            else
                freqs[key][2][x[i+1]] = 1.0
            end
        else
            freqs[key] = [1.0, Dict()]
            freqs[key][2][x[i+1]] = 1.0
        end
    end
    return nothing
end

"""
输入句子的词组，输出频数统计
"""
function anasentences(sentences; prewords=2)
    freqs = Dict()
    for xi in sentences
        anasentence!(freqs, xi, prewords=prewords)
    end
    return freqs
end

"""
将频数统计转换成句首词组的概率，和给定前词后各个后词的条件概率
"""
function freq2prob(dict)
    
    ## 句首前词组的概率表
    heads = Dict(prefix => dict[prefix][1]
        for prefix in keys(dict) 
            if prefix[1] == sentence_begin)
    nheads = sum(values(heads))
    for prefix in keys(heads)
        heads[prefix] /= nheads
    end

    ## 各个前词组对应到后词的条件概率
    chains = Dict(prefix => dict[prefix][2]
        for prefix in keys(dict))
    for prefix in keys(chains)
        npost = sum(values(chains[prefix]))
        for word in keys(chains[prefix])
            chains[prefix][word] /= npost
        end
    end
    return heads, chains
end

"""
从句子数组产生两个概率表
"""
function sentences2prob(sentences; prewords=2)
    freqs = anasentences(sentences; prewords=prewords)
    freq2prob(freqs)
end

"""
从概率表（用字典表示）生成一个随机抽样的程序
"""
## 效率有待改进，或查找Julia标准库函数。
function rdiscrete(dict)
    u = rand()
    cump = 0.0
    for (k, v) in dict
        cump += v
        if u <= cump
            return k
        end
    end
    return nothing
end

"""
输入句首词组概率表和条件概率表，输出一个随机句子
"""
function prob_sentence_sample(heads, chains; prewords=2)
    
    ## 可能抽取到无法继续的链，就从头重复
    while true
        ## 抽取句首的前词组
        newpre = rdiscrete(heads)
        ## 句子的单词的数组
        x = collect(newpre)
        
        ## 反复抽取后词，如果无对应的后词则组句失败从头再来
        ## 如果抽取到句尾标志则生成句子结果
        while true
            ## 根据newpre抽取后词
            if newpre in keys(chains) 
                suf = rdiscrete(chains[newpre])
                push!(x, suf)
            else 
                break # 重新生成句首
            end 
            
            ## 如果后词是句尾，返回抽取结果
            if suf == sentence_end
                return join(x[2:(end-1)], " ")
            end
            
            ## 将前词组的后半部分与抽取的后词组成新的前词组
            if length(newpre) < prewords
                newpre = (newpre..., suf)
            else
                newpre = (newpre[2:end]..., suf)
            end
        end # while true
        
    end # while true
    
end # function

"""
输入句子数组，生成随机句子抽样器的函数（函数工厂）

Input:
  x: 句子的数组
  prewords: 用前面的几个词作为后一个词的条件
"""
function make_sentence_sampler(x :: Array{String,1}; prewords=2)
    ## 从句子数组生成两个概率表
    heads, chains = sentences2prob(x; prewords=prewords)
    
    ## 用无名函数作为返回值
    function ()
        prob_sentence_sample(heads, chains; prewords=prewords)
    end
end

"""
输入一个文件名，生成随机句子抽样器的函数（函数工厂）

Input:
  x: 文件名
  prewords: 用前面的几个词作为后一个词的条件
"""
function make_sentence_sampler(x :: String; prewords=2, skiplines=0)
    ## 从文件读入并转换为句子
    sentences = getsentences(x, skiplines=skiplines)
    ## 从句子数组生成两个概率表
    heads, chains = sentences2prob(sentences; prewords=prewords)
    
    ## 释放sentences的存储空间
    sentences = []
    
    ## 用无名函数作为返回值
    function ()
        prob_sentence_sample(heads, chains; prewords=prewords)
    end
end

end # module MarkovArticle

注意， 每次修改了模块后， 应该重启Julia进程， 否则可能无法实际更新修改。 Jupyter、VSC等界面可能利用了Revise.jl库来自动重新载入模块。

输入一个文本文件名， 生成10个随机句子的测试：

using Main.MarkovArticle: make_sentence_sampler
f = make_sentence_sampler("test-markov.txt", prewords=1)
for i=1:10
    sen = f()
    println(sen)
end

when a bit better than her sisters
cried his design
my dear you are always giving her daughters
how can you are twenty i am sure she fancied herself nervous
single man of beauty
mr morris immediately
they are my dear mr bennet replied that account for i am thinking of threeandtwenty years had been here
ah you and news
however little lizzy has not know what a fine thing for our girls
it that he had not pretend to hearing it is not pretend to visit them

f2 = make_sentence_sampler("test-markov.txt", prewords=2)
for i=1:10
    sen = f2()
    println(sen)
end

when a woman has not often much beauty to think of
it is returned she
her mind was less difficult to develop
you are as handsome as jane nor half so handsome as jane nor half so goodhumoured as lydia
sir william and lady lucas are determined to go merely on that account for in general you know they visit no newcomers
it is very likely that he may fall in love with one of them mr bingley will be very glad to see many young men of four thousand a year
i certainly have had my share of beauty but i do not know what i suffer
my dear you must know that i am sure she is not a bit better than the others
but you are as handsome as any of them
it is more than i engage for i assure you

f3 = make_sentence_sampler("test-markov.txt", prewords=3)
for i=1:10
    sen = f3()
    println(sen)
end

mr bennet made no answer
only think what an establishment it would be for one of them
only think what an establishment it would be for one of them
you mistake me my dear
in such cases a woman has not often much beauty to think of
but consider your daughters
but my dear you flatter me
i dare say mr bingley will be very glad to see you
i see no occasion for that
when a woman has five grownup daughters she ought to give over thinking of her own beauty

可以看出， 用到三个词作为条件时， 因为输入文本只有小说的一章， 所以几乎会照抄原文了。

测试用句子数组作为输入：

using Main.MarkovArticle: getsentences, make_sentence_sampler
sentences = getsentences("test-markov.txt", skiplines=0)
ff2 = make_sentence_sampler(sentences, prewords=2)
for i=1:10
    sen = ff2()
    println(sen)
end

what a fine thing for our girls
four or five thousand a year come into the neighbourhood
it is more than i engage for i assure you
is he married or single
you are overscrupulous surely
i have a high respect for your nerves
my dear you must go for it will be impossible for us to visit him as soon as he comes into the neighbourhood
i see no occasion for that
you and the girls may go or you may send them by themselves which perhaps will be very glad to see you
but it is very likely that he is considered the rightful property of some one or other of their daughters

输入傲慢与偏见全文， 生成以三个单词为条件的10个随机句子：

ff3 = make_sentence_sampler("Pride and Prejudice by Jane Austen.txt", skiplines=39, prewords=3)
for i=1:10
    sen = ff3()
    println(sen)
end

i am sure i had no difficulty in believing that a man who has been the study of thoroughbass and human nature
and in the evening
but i can hardly be just to him
and she condescended to give me his directions which i particularly begged him to do whatever occasion might suggest to be advisable for continuing their pursuit
i do not know
the comfort to her of all her former professions of regard
but though we have both i hope improved in civility
but that is one great difference between us
very welland this offer of marriage in this way
pray go to see them she concluded her to be indifferent because i wished it in reason

在利用了整部长篇小说以后， 利用三个词作为条件的随机句子再也不是照抄原文了， 也就造成了许多无意义的句子。