Julia编程示例

李东风

2020-04-26

高斯八皇后问题

国际象棋的棋盘是 8×8 的格子。 国际象棋手马克斯·贝瑟尔于 1848 年提出如下问题: 在 8×8 格的国际象棋上摆放八个皇后, 使其不能互相攻击, 即任意两个皇后都不能处于同一行、同一列或同一斜线上, 问有多少种摆法。 高斯认为有 76 种方案。 1854 年在柏林的象棋杂志上不同的编辑发表了 40 种不同的解, 后来有人用图论的方法解出 92 种结果。

穷举法

要用编程的方法解决, 首先想到的是, 每个皇后有64个位置可选, 穷举可以考虑$64^8 \approx 2.8 \times 10^{14}$种组合, 即百万亿级别的组合, 计算量太大。

实际上, 对于每一种可行的摆法, 因为每一行有且仅有一个皇后, 穷举时所以只需要考虑每一行的皇后在那一列, 有$8^8 = 16,777,216$种组合, 即约一千万种组合。 这个组合数目虽然很大, 但对于现代计算机来说可以很快地完成穷举。

先用Python实现。 将一种可能的摆法存入一个长度为8的列表, 每个元素代表对应的行的皇后位置。 虽然可以写一个8重循环, 但是这样的程序过于繁琐。 所以, 采用八进制的想法, 从[0,0,0,0,0,0,0,0]出发, 每次给个位加1, 遇到8就向下一位进1, 直到循环$8^8$次。 写一个函数判断新的一个位置是否合法。

import time

## 检查一种摆法是否合法
## x是长度为8的列表,代表从低位到高位的8进制数字,
## 用每个数字代表一行的棋子所在的列。
def is_solution(x):
    for i in range(7):
        for j in range(i+1, 8):
            di = x[j] - x[i]
            if di==0 or di==j-i or di==i-j :
                return False
    return True

## 穷举进入下一个摆法
def next_board(x):
    x[0] += 1
    for i in range(7):
        if(x[i]==8):
            x[i+1] += 1
            x[i] = 0
    return x

def queens_exaust():
    board = [0]*8
    nmax = 8**8
    ## boards用来存放所有的摆法,
    ## 每种摆法表示为8个元素的列表
    boards = []
    nb = 0
    for i in range(nmax):
        if is_solution(board):
            print(str(nb) + ',' + ','.join(map(str, board)))
            boards.append(board.copy())
            nb += 1

        board = next_board(board)
    return boards


time_start=time.time()
res1 = queens_exaust()
time_end=time.time()
print('穷举法用时', time_end-time_start)
print('解的个数:', len(res1))

用时50秒,得到了92个解。

下面是Julia版本的程序:

## 检查一种摆法是否合法
## x是长度为8的数组,第i个元素是第i行的棋子所在的列序号
function is_solution(x)
    for i in 1:7
        for j in (i+1):8
            di = x[j] - x[i]
            if di==0 || di==j-i || di==i-j
                return false
            end
        end
    end
    return true
end

## 穷举进入下一个摆法
## 把长度为8的数组x看成是有8位数的8进制数,但数字都加1,
## 次序是从低位到高位
function next_board(x)
    x[1] += 1
    for i in 1:7
        if x[i]==9
            ## 进位
            x[i+1] += 1
            x[i] = 1
        end
    end

    return x
end

function queens_exaust()
    board = zeros(Int8, 8) .+ 1
    nmax = 8^8
    nbmax = 1000
    nb = 0
    boards = zeros(Int8, nbmax, 8)
    for i in 1:nmax
        if is_solution(board)
            nb += 1
            println(board)
            boards[nb,:] = board
        end

        board = next_board(board)
    end
    boards = boards[1:nb,:]
    return boards
end
@time queens_exaust()

用时0.93秒,得到92个解。

递归算法

穷举法完全不考虑已经摆放的棋子, 所以另一种更好的做法是使用递归算法, 先在第一行摆下一颗棋子, 这有8种摆法; 然后,在第二行试图摆下第二颗棋子, 使得与第一颗棋子不冲突; 再考虑第三颗棋子, 如此一直到第八颗棋子。 这个过程中如果某颗棋子无法摆放, 就退回到上一颗棋子的下一个位置; 找到一种摆法后, 也考虑最后一颗棋子的下一个位置。

下面是从百度百科网站复制的Python版本的递归算法程序。

## 用长度为8的列表A表示一种摆法,
## 用cur表示当前要摆放的棋子序号,0 <= cur < 8
def queens(A, cur=0):
    if cur == len(A):
        ## 如果当前棋子序号为8,表示找到了一种摆法
        print(','.join(map(str, A)))
        boards.append(A.copy())
        return 0
    ## 对每颗棋子col遍历
    for col in range(len(A)):
        ## 将当前棋子cur摆放在col列,
        A[cur] = col
        ## 设置摆放是否合法的初值为真
        flag = True
        ## 判断cur号棋子摆放在col列,是否与0到cur-1号棋子有冲突
        ## row是用来遍历0到cur-1号棋子的变量
        for row in range(cur):
            ## 以下判断摆放在第cur行、第col列的棋子,
            ## 是否与第row行、A[row]列的棋子冲突
            if A[row] == col or abs(col - A[row]) == cur - row:
                flag = False
                break
        ## 如果摆放第cur号棋子在第col列成功,
        ## 就考虑下一颗棋子(递归调用);
        ## 如果摆放不成功,就摆放到col的下一列继续判断
        ## 这样会遍历每颗棋子与前面棋子的不冲突的位置
        if flag:
            queens(A, cur+1)

boards = []
queens([None]*8)

也是92个结果,用时仅30毫秒。

下面是Julia版本的程序:

## 递归算法
## 用长度为8的数组A表示一种摆法,
## 用cur表示当前要摆放的棋子序号,1 <= cur <= 8
function queens()
    nbmax = 1000
    nb = 0
    boards = zeros(Int8, nbmax, 8)

    function queens_rec(A, cur=1)
        if cur == 9
            ## 如果当前棋子序号为9,表示找到了一种摆法
            nb += 1
            boards[nb,:] = A
            ##println(join(string.(A), ","))
            return
        end # if cur

        ## 对当前要摆放的棋子遍历所有列位置试摆放
        for col in 1:8
            ## 将当前棋子cur摆放在col列,
            A[cur] = col
            ## 设置摆放是否合法的初值为真
            flag = true
            ## 判断cur号棋子摆放在col列,是否与1到cur-1号棋子有冲突
            ## row是1到cur-1号棋子的变量
            for row in 1:(cur-1)
                ## 以下判断摆放在第cur行、第col列的棋子,
                ## 是否与第row行、A[row]列的棋子冲突
                if A[row] == col || abs(col - A[row]) == cur - row
                    flag = false
                    break
                end
            end # for row

            ## 如果摆放第cur号棋子在第col列成功,
            ## 就考虑下一颗棋子(递归调用);
            ## 如果摆放不成功,就摆放到col的下一列继续判断
            ## 这样会遍历每颗棋子与前面棋子的不冲突的位置
            if flag
                queens_rec(A, cur+1)
            end
        end # for col
    end # function queens_rec

    queens_rec(zeros(Int8, 8), 1)
    boards = boards[1:nb,:]
    println("找到解的个数:", nb)

    return boards
end # function queens
@time queens()

找到92个解,用时0.1秒。

找到变换等价的摆法

还可以继续考虑这些解法中那些是不能通过左右反射、上下反射, 旋转90、180、270度得到的。

下面是Python版本的程序, 用矩阵代数表示这些变换, 最后保存为一个csv文件。

## 判断两种摆法是否通过变换可以相同
import numpy as np
from numpy import zeros
import pandas as pd

def board_equals(x, y):
    ## 棋盘的8元素存储到8x8的0-1矩阵存储
    def board_to_mat(z):
        mat = zeros((8,8))
        for i in range(8):
            mat[i,z[i]] = 1
        return mat

    xm = board_to_mat(x)
    ym = board_to_mat(y)

    # 反射变换矩阵
    mat_reflect = zeros((8,8))
    for i in range(8):
        mat_reflect[i,7-i] = 1

    # 左右反射
    def reflect_lr(z):
        return z.dot(mat_reflect)

    # 上下反射
    def reflect_ud(z):
        return mat_reflect.dot(z)

    # 逆时针旋转90度
    def rot090(z):
        return reflect_ud(z.T)

    # 逆时针旋转180度
    def rot180(z):
        return reflect_ud(reflect_lr(z))

    # 逆时针旋转270度
    def rot270(z):
        return reflect_lr(z.T)

    funcs = [reflect_lr, reflect_ud,
             rot090, rot180, rot270]
    for f in funcs:
        ynew = f(ym)
        if(np.all(ynew == xm)):
            return True
    return False

## 标记通过变换可以得到的摆法
def group_boards(boards):
    b = boards.copy()
    nb = len(b)
    ## 用来标记组:
    g = [0]*nb
    ## 找到的组数
    ng = 1

    for j in range(1, nb):
        newgroup = True
        for i in range(0, j):
            ## 判断第j种摆法是否与第i种摆法可转换,
            ## 如果可转换,将第j摆法标记为第i组
            if board_equals(b[i], b[j]):
                newgroup = False
                g[j] = g[i]
                break
        if newgroup:
            g[j] = ng
            ng += 1
    print('找到了{}个组。'.format(ng))

    ## 保存为CSV
    dfbd = pd.DataFrame(boards)
    sdg = pd.Series(g)
    sdg.name = 'group'
    dfbd = dfbd.merge(sdg, left_index=True, right_index=True)
    dfbd.sort_values(['group'], inplace=True)

    dfbd.to_csv('queens_group.csv',
                index_label='board')
    return dfbd

group_boards(boards)

Julia语言版本:

In [10]:
import DataFrames: DataFrame
import CSV

function board_equals(x, y)
    ## 棋盘的8元素存储到8x8的0-1矩阵存储
    function board_to_mat(z)
        mat = zeros(8,8)
        for i in 1:8
            mat[i,z[i]] = 1
        end # for i
        return mat
    end # board_to_mat

    xm = board_to_mat(x)
    ym = board_to_mat(y)

    # 反射变换矩阵
    mat_reflect = zeros(8,8)
    for i in 1:8
        mat_reflect[i,9-i] = 1
    end # for i

    # 左右反射
    function reflect_lr(z)
        return z * mat_reflect
    end # reflect_lr

    # 上下反射
    function reflect_ud(z)
        return mat_reflect * z
    end # reflect_ud

    # 逆时针旋转90度
    function rot090(z)
        return reflect_ud(z')
    end # rot090

    # 逆时针旋转180度
    function rot180(z)
        return reflect_ud(reflect_lr(z))
    end # rot180

    # 逆时针旋转270度
    function rot270(z)
        return reflect_lr(z')
    end # rot270

    funcs = [reflect_lr, reflect_ud, rot090, rot180, rot270]

    for i in 1:length(funcs)
        f = funcs[i]
        ynew = f(ym)
        if all(ynew .== xm)
            return true
        end # if
    end # for f

    return false
end # board_equals

## 标记通过变换可以得到的摆法
function group_boards(boards)
    b = copy(boards)
    nb = size(b, 1)
    g = zeros(Int, nb)
    ng = 1
    g[1] = 1

    for j in 2:nb
        newgroup = true
        for i in 1:(j-1)
            ## 判断第j种摆法是否与第i种摆法可转换,
            ## 如果可转换,将第j摆法标记为第i组
            if board_equals(b[i,:], b[j,:])
                g[j] = g[i]
                newgroup = false
                break
            end # if
        end # for i
        if newgroup
            ng += 1
            g[j] = ng
        end # if
    end # for j

    ## 保存为csv
    println("找到分组个数:", ng)
    grouped = [1:nb boards g]
    qn = ["solution"; "Q" .* string.(1:8); "group"]
    df = DataFrame(grouped, Symbol.(qn))
    sort!(df, :group)
    CSV.write("queens_group_julia.csv", df)
    
    return grouped
end # group_boards

boards = queens()
grouped = group_boards(boards);
找到解的个数:92
找到分组个数:17

结果的CSV文件:

solution,Q1,Q2,Q3,Q4,Q5,Q6,Q7,Q8,group
1,1,5,8,6,3,7,2,4,1
22,3,6,4,2,8,5,7,1,1
33,4,2,7,3,6,8,5,1,1
60,5,7,2,6,3,1,4,8,1
89,8,2,4,1,7,5,3,6,1
92,8,4,1,3,6,2,7,5,1
2,1,6,8,3,7,4,2,5,2
15,3,5,2,8,6,4,7,1,2
42,4,7,5,2,6,1,3,8,2
51,5,2,4,7,3,8,6,1,2
90,8,2,5,3,1,7,4,6,2
91,8,3,1,6,2,5,7,4,2
3,1,7,4,6,8,2,5,3,3
78,6,4,7,1,3,5,2,8,3
4,1,7,5,8,2,4,6,3,4
71,6,3,5,7,1,4,2,8,4
5,2,4,6,8,3,1,7,5,5
28,3,8,4,7,1,6,2,5,5
36,4,2,8,6,1,3,5,7,5
41,4,7,3,8,2,5,1,6,5
52,5,2,6,1,7,4,8,3,5
57,5,7,1,3,8,6,4,2,5
65,6,1,5,2,8,3,7,4,5
88,7,5,3,1,6,8,2,4,5
6,2,5,7,1,3,8,6,4,6
39,4,6,8,3,1,7,5,2,6
54,5,3,1,6,8,2,4,7,6
64,5,8,4,1,7,2,6,3,6
74,6,3,7,2,8,5,1,4,6
87,7,4,2,8,6,1,3,5,6
7,2,5,7,4,1,8,6,3,7
23,3,6,8,1,4,7,5,2,7
45,4,8,1,5,7,2,6,3,7
70,6,3,1,8,5,2,4,7,7
73,6,3,7,2,4,8,1,5,7
86,7,4,2,5,8,1,3,6,7
8,2,6,1,7,4,8,3,5,8
37,4,6,1,5,2,8,3,7,8
56,5,3,8,4,7,1,6,2,8
77,6,4,2,8,5,7,1,3,8
80,6,8,2,4,1,7,5,3,8
85,7,3,8,2,5,1,6,4,8
9,2,6,8,3,1,4,7,5,9
27,3,7,2,8,6,4,1,5,9
31,4,2,5,8,6,1,3,7,9
46,4,8,5,3,1,7,2,6,9
47,5,1,4,6,8,2,7,3,9
62,5,7,4,1,3,8,6,2,9
66,6,2,7,1,3,5,8,4,9
84,7,3,1,6,8,5,2,4,9
10,2,7,3,6,8,5,1,4,10
12,2,8,6,1,3,5,7,4,10
30,4,1,5,8,6,3,7,2,10
43,4,7,5,3,1,6,8,2,10
50,5,2,4,6,8,3,1,7,10
63,5,8,4,1,3,6,2,7,10
81,7,1,3,8,6,4,2,5,10
83,7,2,6,3,1,4,8,5,10
11,2,7,5,8,1,4,6,3,11
21,3,6,4,1,8,5,7,2,11
32,4,2,7,3,6,8,1,5,11
44,4,8,1,3,6,2,7,5,11
49,5,1,8,6,3,7,2,4,11
61,5,7,2,6,3,1,8,4,11
72,6,3,5,8,1,4,2,7,11
82,7,2,4,1,8,5,3,6,11
13,3,1,7,5,8,2,4,6,12
16,3,5,7,1,4,2,8,6,12
14,3,5,2,8,1,7,4,6,13
38,4,6,8,2,7,1,3,5,13
55,5,3,1,7,2,8,6,4,13
79,6,4,7,1,8,2,5,3,13
17,3,5,8,4,1,7,2,6,14
25,3,6,8,2,4,1,7,5,14
26,3,7,2,8,5,1,4,6,14
35,4,2,8,5,7,1,3,6,14
58,5,7,1,4,2,8,6,3,14
67,6,2,7,1,4,8,5,3,14
68,6,3,1,7,5,8,2,4,14
76,6,4,1,5,8,2,7,3,14
18,3,6,2,5,8,1,7,4,15
24,3,6,8,1,5,7,2,4,15
34,4,2,7,5,1,8,6,3,15
40,4,7,1,8,5,2,6,3,15
53,5,2,8,1,4,7,3,6,15
59,5,7,2,4,8,1,3,6,15
69,6,3,1,8,4,2,7,5,15
75,6,3,7,4,1,8,2,5,15
19,3,6,2,7,1,4,8,5,16
29,4,1,5,8,2,7,3,6,16
20,3,6,2,7,5,1,8,4,17
48,5,1,8,4,2,7,3,6,17

词典中单词的练习

二分法查词

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

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

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

mydict = readlines("words.txt")

查找反向词

设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")实际是同一个结果。 只要在记录新的反向单词对之前检查一下:

if indict(dict, rword)
            newpair = sort((word, rword))
            if !(newpair in y)
                push!(y, (word, rword))
                println(word, "  ", rword)
            end
        end

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

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

连锁组词

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

显然不能遍历所有的两两组合,否则程序效率会很低。 基本的想法是按单词长度分组,查找时仅用同长度词语两倍长度词检查。 程序如下:

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 interlock(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 = dictgr[wordlen] # 组成单词表
        dictres = copy(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
end

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

两两搭配的运算量太大, 需要更合理的算法。 可考虑并行化。

并行化改进

将如下程序保存在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("/teachers/lidf/docs/Julia/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()函数合并起来。

千字文没有重复吗

千字文是著名的国学经典, 南北朝时期周兴嗣所作, 文章涵盖了国文初学者应知的许多基本常识, 四字一句,恰好一千字。 据说这样的一篇长文恰好用了一千个完全不同的字。 大家编制一个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"[ ,。 \n]" => s"")
    ##println(s)
    x = collect(s)
    if length(x) != 1000
        println("字数不等于1000!")
        return false
    end
    d = Dict()
    for xi in x
        if xi in keys(d)
            d[xi] += 1
        else 
            d[xi] = 1
        end 
    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é”, 本意是指量物体的周围长度,也泛指衡量, 后来增加了“洁净”含义, 特意增加了一个带三点水的写法。 千字文中这两个字含义是一样的, 原文中用了不同的写法。

查找重复诗文

问题

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

解决方法有两种思路:

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

本例在Julia v1.0.0下调试成功。 Julia v0.6的字符串处理函数与v1.0略有差别。

Julia字符串知识

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

为了用正常的数组处理方法来处理字符串中的字符, 用如下的自定义函数将字符串转换成数组, 数组的每一个元素是一个字符组成的字符串:

function string2array(s)
    n = length(s) # 字符个数,汉字也算一个字符
    x = Array{String}(undef, n) # 结果数组预分配内存
    ind = 1 # 当前的合法字符下标
    i = 1 # 当前字符序号
    while i <= n
        x[i] = s[ind:ind] # 取出当前字符作为字符串存入结果数组
        i += 1 # 下一字符
        ind = nextind(s, ind) # 找到下一个合法字符对应的字节序号
    end
    return x
end

这里x = Array{String}(undef, n)是Julia 1.0版要求的数组初始化方式, undef表示元素初始化为未定义值,n是元素个数。 程序利用了循环逐个字符地填入结果数组。 注意结果数组时预先分配的, 而不是用push!()函数逐个地添加元素, 每次调用push!()都会造成内存重新分配从而损失效率。

事实上,collect(s)可以将字符串s转换成一个字符数组, 每个元素是一个字符。

为了将字符串数组合并成一个长字符串, 中间用指定字符串分隔,可以用如下的自定义函数:

function array2string(x, delim="")
    if delim != ""
        x .= x .* delim
    end
    reduce(*, x)
end

这里用了reduce()函数。 reduce()输入一个二元运算函数和一个一维数组, 将所有的数组元素连续地进行运算得到一个标量结果。 对字符串,*表示连接两个字符串。 注意在要求有分隔符时,用了.=.*这样的写法。

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

程序分解

为了找到重复部分, 假设文本文件的所有字符保存在一个数组x中, x的每个元素是仅有一个字符的字符串。 想法是, 制作x的副本y, 然后将xy的元素位置错一个下标位置对齐比较, 错两个下标位置对齐比较, 等等, 找到错位对齐后连续的重合内容。 例如, 设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", 利用逐字符循环在处理非文字内容的同时将字符序号与行号建立对应关系。 然后, 利用上面的数组中查找连续重复的函数查找重复, 这样找到的结果是字符位置和长度, 从中可以取出重复内容字符串, 并将字符位置转换成行号。 然后输出结果保存为输出文件即可。 输出中, 按重复内容长短由大到小排序。

程序列表

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

In [1]:
## 查找文本文件中较长的重复内容,
## 以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
Out[1]:
FindReps

用正则表达式解决问题

替换后可以简洁地解决字符串问题。 如下的模式可以表示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()函数实现了用替换后查找文本文件重复内容。

改进思路

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

随机句子

读入一篇英文的文章, 比如一篇小说, 可以从Gutenburg project网站找到这样的文本文件。 利用这样的文章, 将其拆分成句子, 得到许多句子的样本。 然后, 根据句子中前后两个词之间的条件概率, 构造随机句子。 进一步可以考虑前面的两个词的条件下后一个词的条件概率, 以此构造随机句子。

完整的实现如下。

In [2]:
## 使用前后单词的条件概率作马氏分析,
## 从而制作随机句子。
## 以一篇英文文本文档为素材。

module MarkovArticle

export make_sencence_sampler, random_sentences

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

## 频数表程序,输入一维数组,输出每个不同值的频数,以字典形式返回
function histogram(x)
    d = Dict()
    for xi in x
        if xi ? keys(d)
            d[xi] = 1
        else
            d[xi] += 1
        end
    end
    d
end

## 切分句子的程序
## 读入一篇文章,切分句子为数组。
## 用句点空格,句点双撇号作为句子末尾标志。
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] = lowercase(x[i])
    end
    return x
end
##getsentences("Pride and Prejudice by Jane Austen.txt", skiplines=30)

## 输入由句子组成的词组,
## 建立从前词组到后随词的映射的频数表。
## 前词组可以是一个词,二个词,三个词等,
## 后词是一个词。
## 每个映射是一个字典项,
## 以前词组作为键,
## 而值包括前词组的概率,
## 以及一个子概率表,子概率表为后词到期概率的映射。
## 所有的频数都有一个降序排列的索引数组。
## 首先是一个句子的处理程序。
## freqs: 频数统计结果;
## sentence: 字符串,一个句子;
## prewords: 前词组的单词个数,如1,2,3等
function anasentence!(freqs, sentence; prewords=2)
    # 每个sentence开头用aaaaa标志,结尾用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
## 多个句子的马氏概率分析
## x是以句子为元素的向量
function anasentences(x; prewords=2)
    freqs = Dict()
    for xi in x
        anasentence!(freqs, xi, prewords=prewords)
    end
    return freqs
end

## 输入一篇文章,得到马氏概率分析
function anatext(filename; skiplines=0, prewords=2)
    ## 读入句子为数组
    x = getsentences(filename, skiplines=skiplines)
    ## 以句子为样本,获得前词到后词的映射的频数表
    dict = anasentences(x, prewords=prewords)
    ## 将频数都转换成概率
    n = 0 # 总的前词组数
    for prefix in keys(dict)
        n += dict[prefix][1]
    end
    probpre = []
    for prefix in keys(dict)
        dict[prefix][1] /= n
        push!(probpre, dict[prefix][1])
    end
    ## 每个前词组确定后的后词的频数分布也转换成概率
    for prefix in keys(dict)
        nn = sum(values(dict[prefix][2]))
        for k in keys(dict[prefix][2])
            dict[prefix][2][k] /= nn
        end
    end
    ## 建立前词概率分布降序排列的索引
    #indpre = sortperm(probpre, rev=true)
    ## 建立前词概率降序排列后的累积百分比
    #cumpre = cumsum(probpre[indpre])

    #return (dict, indpre, cumpre)
    return dict
end
##anatext("Pride and Prejudice by Jane Austen.txt", skiplines=30)


## 从一个小规模的频数表按比例抽取的函数
## 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 make_sencence_sampler(filename; skiplines=0, prewords=2)
    dict = anatext(filename; skiplines=0, prewords=2)

    ## 建立句首的字典
    dicthead = Dict()
    freq0 = 0.0
    for (k, (freq, d2)) in dict
        if k[1] == sentence_begin
            dicthead[k] = freq
            freq0 += freq
        end
    end
    ## 将句首字典的频数归一化
    for k in keys(dicthead)
        dicthead[k] /= freq0
    end

    ## 抽取句首前词组的内嵌函数
    function random_head()
        return rdiscrete(dicthead)
    end

    ## 抽取后词的内嵌函数
    function random_follow(newprefix)
        if newprefix ? keys(dict)
            return nothing
        end
        ## 对newprefix为前词组的各个后词进行随机抽样,
        ## 先建立相应的子频数表
        dsub = dict[newprefix][2] # 这是后词的概率分布表字典
        return rdiscrete(dsub)
    end

    # 抽取整句的闭包作为函数发生器的输出
    function ()
        x = []
        # 抽取句首的前词组
        newpre = random_head()
        append!(x, newpre)

        ## 重复抽取后词,如果无对应的后词返回空集,
        ## 重复直到抽取到句子结尾为止
        while true
            ## 根据newpre抽取后词
            suf = random_follow(newpre)
            ## 如果前词组没有对应的后词,失败
            if suf == nothing
                return ""
            end
            ## 如果后词是句尾,返回抽取结果
            if suf == sentence_end
                return join(x[2:(end-1)], " ")
            end
            ## 将前词组的后半部分与抽取的后词组成新的前词组
            push!(x, suf)
            if length(newpre) < prewords
                newpre = (newpre..., suf)
            else
                newpre = (newpre[2:end]..., suf)
            end
        end
    end
end
## random_sentence = MarkovArticle.make_sencence_sampler("Pride and Prejudice by Jane Austen.txt"; skiplines=39, prewords=2)

## 输入一篇文章,建立抽样器,并输出多个随机句子的程序
function random_sentences(filename, n=1; skiplines=0, prewords=2)
    sampler = make_sencence_sampler(filename; skiplines=skiplines, prewords=prewords)
    x = Array{String,1}(undef, n)
    i = 0
    j = 0
    maxit = 10_000
    while i < n && j < maxit
        j += 1
        item = sampler()
        if item != ""
            i += 1
            x[i] = item
        end
    end
    return x
end
# y = MarkovArticle.random_sentences("Pride and Prejudice by Jane Austen.txt", 100; skiplines=39, prewords=1)

## 问题:必须遇到句尾标志才结束可能造成许多长句子,尤其是用句点作为句子结尾时
end # module MarkovArticle
Out[2]:
MarkovArticle
XML 地图 | Sitemap 地图