几个文本处理的小题目

在北大中文论坛的中文信息处理版有时会看到一些与文本处理有关的问题。想想怎么解答这些问题，其实也挺有意思，有点像解谜游戏。例如今天看到的一个问题：

1 找重码

1.1 问题

怎么找出码表中的重码？假设有码表test.txt：

甲   AB
雅   AB
弟   AC
大   AD
发   BC
收   BC
回   BC
收   CE
名   CE

其中有的汉字有相同的编码。我们的任务是列出有重码的行，例如：

甲   AB
雅   AB
弟   AC
大   AD
发   BC
收   BC
回   BC
收   CE
名   CE

1.2 求解

刚看到这个题目时，我觉得只有编程才能解决。看到其它网友建议用sort、uniq这些工具，我看了看相关工具的帮助，找到一种不编程的解法。

sort --key=2 test.txt | uniq -u --skip-fields=1 > test_uniq.txt
grep -vf test_uniq.txt test.txt > test_dup.txt

用sort排序时，可以指定要排序的列。例如--key=2就是要求按照第二列（field）排序。这里列就是用空白字符（空格、tab）分隔的非空白字符。我们用sort先把输入文件按编码排序。排序是在为使用uniq作准备。

我印象中的uniq是保留连续重复行的第一行。其实，使用-u参数还可以让uniq只打印出不重复的行。使用--skip-fields=N可以让uniq忽略前N列。通过sort和uniq，我们得到了所有不重码的行，保存到uniq.txt。 uniq.txt的内容是

弟   AC
大   AD

在码表中去掉所有不重码的行，就可以得到所有重码的行。grep的-f参数可以将文件中的每一行当作要匹配的模式。-v参数可以列出不匹配的行。在文件2中找与文件1不匹配的行，就相当于在文件2中去掉与文件1匹配的行，这正好是我们想得到的结果。dup.txt的内容是：

甲   AB
雅   AB
发   BC
收   BC
回   BC
收   CE
名   CE

在windows平台可以通过cygwin使用这些工具。我把相关程序放到了主页上（下载）。因为Windows也有一个sort程序，我将cygwin的sort更名为lsort。

2 交集和补集

2.1 问题

有个网友提问如何求两列词组的交集和补集。例如假设有集合A（A.txt）：

中国
人民
共和
祖国
万岁
团结
北京
奥运
红旗
友谊

集合B（B.txt）：

中国
江山
祖国
美好
美誉
一定
万岁

A和B的交集是两者都包含的行，即：

中国
祖国
万岁

集合A中集合B的补集是就是A包含但B不包含的行，即：

人民
共和
团结
北京
奥运
红旗
友谊

数学上的补集要求B是A的子集。本文不做这个限制，只是借用补集这个名词。这位网友要求仅用Excel，不用其它软件。但我们先不管他，看看不用Excel的解法。

2.2 解答一

其实我们只要在A.txt中查找与B.txt匹配的行，就可以得到A与B的交集：

D:\tools>grep -f B.txt A.txt
中国
祖国
万岁

我们在A.txt中查找与B.txt不匹配的行，就得到了集合A中集合B的补集：

D:\tools>grep -vf B.txt A.txt
人民
共和
团结
北京
奥运
红旗
友谊

是不是很简单？不过我后来发现使用grep在文件A中查找文件B只适合于文件B比较小的情况。当文件B比较大时，速度会慢得无法接受。后记讨论更快的求补集和交集的方法。

2.3 解答二

如果指定用Excel，我想不到什么简单的方法，只能用VBA。

2.3.1 VLookup函数

Excel VBA有个VLookup函数：

VLookup(lookup_value,table_array,col_index_num,range_lookup)

lookup_value是要查找的值。

table_array指定查找的范围。table_array可以指定多列，VLookup查找第一列。

col_index_num是找到匹配的单元格后，返回该单元格所在行的第几列。 col_index_num的值应该在1和table_array的列数之间。

range_lookup是个布尔值。range_lookup为FALSE，表示要求完全匹配，找不到就返回错误值。 range_lookup为TRUE时，要求待查找的列是按升序排序的，如果找不到完全匹配的值，就返回小于lookup_value的最大值。

2.3.2 求交集

我们可以用VLookup函数在集合A里找逐一查找集合B的元素。如果找到，这个元素就属于两个集合的交集。代码如下：

Private Sub intersection_Click()
'在s1列中查找s2的单元格。如果找到了就写在res列

Const sheet As String = "Sheet1"   '工作表名字
Const s1_col As Integer = 1    's1列位置
Const s1_row As Integer = 1    '集合1从从s1列的这行开始
Const s2_col As Integer = 2    's2列位置
Dim s2_row As Integer
Const res_col As Integer = 3   '结果所在列
Dim res_row As Integer   '结果列中下一个空行

'可以配置的值
s2_row = 1      '集合2从从s2列的这行开始
res_row = 1     '结果列从这行开始写

Dim cell As String
Dim s1_last_row As Integer    '集合1的最后一行

'找到集合1的最后一行，空单元格表示结束
s1_last_row = s1_row
cell = Cells(s1_last_row, s1_col)
Do While cell <> ""
    s1_last_row = s1_last_row + 1
    cell = Cells(s1_last_row, s1_col)
Loop

s1_last_row = s1_last_row - 1
If s1_last_row < s1_row Then
    MsgBox ("集合1空")
    Exit Sub
End If
    
Dim tmp As Variant
Dim s1 As Range
Set s1 = Worksheets(sheet).Range(Cells(s1_row, s1_col), Cells(s1_last_row, s1_col))
cell = Cells(s2_row, s2_col)
'用VLookup函数在集合1里找逐一找集合2的单元，如果找到，这个单元就是两个集合的交集
Do While cell <> ""
    tmp = Application.VLookup(cell, s1, 1, False)
    If IsError(tmp) = False Then
        Cells(res_row, res_col) = tmp
        res_row = res_row + 1
    End If
    s2_row = s2_row + 1
    cell = Cells(s2_row, s2_col)
Loop
End Sub

2.3.3 求补集

我们用VLookup函数在集合B里找逐一查找集合A的单元，如果找不到，这个单元就属于在集合A中集合B的补集。代码如下：

Private Sub complement_Click()
'在s2列中查找s1的单元格。如果找到了就什么都不做。如果没找到就把这个单元格写到res列

Const sheet As String = "Sheet2"   '工作表名字
Const s1_col As Integer = 1    's1列位置
Dim s1_row As Integer
Const s2_col As Integer = 2    's2列位置
Const s2_row As Integer = 1    '集合2从从s2列的这行开始
Const res_col As Integer = 3   '结果所在列
Dim res_row As Integer   '结果列中下一个空行

'可以配置的值
s1_row = 1      '集合1从从s2列的这行开始
res_row = 1     '结果列从这行开始写

Dim cell As String
Dim s2_last_row As Integer    '集合1的最后一行

'找到集合2的最后一行，空单元格表示结束
s2_last_row = s2_row
cell = Cells(s2_last_row, s2_col)
Do While cell <> ""
    s2_last_row = s2_last_row + 1
    cell = Cells(s2_last_row, s2_col)
Loop

s2_last_row = s2_last_row - 1
If s2_last_row < s2_row Then
    MsgBox ("集合2空")
    Exit Sub
End If
    
Dim tmp As Variant
Dim s2 As Range
Set s2 = Worksheets(sheet).Range(Cells(s2_row, s2_col), Cells(s2_last_row, s2_col))
cell = Cells(s1_row, s1_col)
'用VLookup函数在集合2里找逐一找集合1的单元，如果找不到，这个单元就属于在集合1里集合2的补集
Do While cell <> ""
    tmp = Application.VLookup(cell, s2, 1, False)
    If IsError(tmp) = True Then
        Cells(res_row, res_col) = cell
        res_row = res_row + 1
    End If
    s1_row = s1_row + 1
    cell = Cells(s1_row, s1_col)
Loop
End Sub

2.3.4 说明

是不是很复杂？

思路其实很简单，但代码看上去还是很繁琐的。从我的主页可下载这个示例的Excel表格。打开这个包含宏的excel表格需要先将"工具-宏-安全性"设到中，然后打开时选择启用宏。

在Excel的“视图”->“工具栏”中打开“控件工具箱”工具栏，点击设计模式按钮可以切换设计模式。在设计模式，可以在按钮的右键菜单中选择“查看代码”。选择“工具”->“宏”->“Visual Basic 编辑器”可以查看表格中的代码。按快捷键Alt+F11可以在Excel表格和代码编辑器之间快速切换。

Excel在处理大数据时速度很慢。我平时用Excel，通常只用它的排序、10进制-16进制转换，很少用VBA。这两个函数是看着帮助，用一个中午写出来的。其实，这是一个反例。它说明选择不恰当的工具可能事倍功半。

3 删除重复行

3.1 解答一

使用UltraEdit可以排序并删除重复项。

3.1 解答二

在Excel中，如果要去掉一列的重复项，可以选择“数据”->“筛选”->“高级筛选”，在弹出的对话框中选中“选择不重复的记录”就可以了。

3.1 解答三

在我写的cnbook中，我把UltraEdit的排序和删除重复项功能分开了。选择“转换”->“删除重复行”可以删除重复行，但不改变原来的顺序。

在cnbook中还有一个“多文件删除重复行”的功能。选择“文件”->“批处理”，选择要处理的文件，在“可选择的处理”列表中选择“多文件删除重复行”。假设例如文件a的内容是：

1
2
7

文件b的内容是

2
3
5

文件c的内容是

4
5
7
8

执行“多文件删除重复行”后，文件a的内容是

1
2
7

文件b的内容是

3
5

文件c的内容是

4
8

4 结束语

作为程序员，我们必须对自己所写的每行代码负责，让它易于理解，不易腐烂。但代码注定要变质，程序员也肯定会犯错误。要做到绝对不犯错误可能只有一个方法，那就是不写代码。尽量用好现有的工具，可能会使世界更简单一些。

从解决问题的过程中感受到乐趣是程序员的一个重要能力，繁重的压力很容易让程序员忘掉这种朴素的快乐，愿我们能保有它而不失去。

5 后记

5.1 求补集

网友1975xxzzasohu发现本文的找重码方法在处理1000行数据时程序就不能退出。我试验了一下，发现问题出在：

grep -vf test_uniq.txt test.txt > dup.txt

这个命令一直没有返回。可见grep的-v参数不适合大数据。从test.txt中去掉test_uniq.txt所包含的行其实就是求test.txt中test_uniq.txt的补集。这说明2.2节的求补集方法也不适合大数据。让我们看看其它求补集的方法。

5.1.1 用cnbook求补集

使用cnbook 其实可以实现求补集。只要在test_uniq.txt的每行最后加上“=”，即将“$”替换成“=”。然后将test_uniq.txt设为第一张自定义替换表。然后打开test.txt，将“^(.+)$”替换成“\T{\1}”，就是将test_uniq.txt中出现过的行替换成空行。然后再删除空行，既将“^$”替换成“\d”就可以了。上面提到的3个替换都应选中“正则表达式”。

5.1.2 用sed求补集

cnbook的思路也可以用sed实现。只要用sed执行脚本（mk_rep_sed.sed）：

s/.*/s\/&\/\//
$a\
/^$/d\

将test_uniq.txt处理成一个将test_uniq.txt包含的行替换成空行并删除空行的sed脚本（rep.sed）。然后再对test.txt执行rep.sed就可以了。即：

sed -f mk_rep_sed.sed test_uniq.txt > rep.sed
sed -f rep.sed test.txt > test_dup.txt
del rep.sed

5.1.3 用sort和uniq求补集

其实还有一种更简单、更快捷的方法，只需要执行一条命令：

cat test.txt test_uniq.txt|lsort|uniq -u > test_dup.txt

你能看懂这条命令吗？它为什么能从test.txt中去掉test_uniq.txt已经包含的行？

使用这个方法的前提是test_uniq.txt必须是test.txt的子集。将两个文件连在一起并排序后，重复的行就会被排在一起。重复的行就是test_uniq.txt和test.txt都有的行。因为test_uniq.txt是test.txt的子集，test_uniq.txt的所有行在test.txt中都有，所以不重复的行必然就是test_uniq.txt中没有，但test.txt有的行。 “uniq -u”保留这些不重复的行，就得到了test_uniq.txt在test.txt中的补集。

5.2 求交集

按照5.1.3的思路，将两个文件连在一起并排序后，重复的行就会被排在一起。重复的行就是两个文件都有的行，即两个文件的交集。用“uniq -d”可以保留重复的行，即：

cat a.txt b.txt|sort|uniq -d > c.txt

“uniq -d”保留重复行的一次出现。所以c.txt就是a.txt和b.txt的交集。

5.3 求并集

求并集很简单,就是将两个文件连接、排序后用uniq去掉重复行就可以了。

cat a.txt b.txt|sort|uniq > c.txt

5.4 命令行

linux的命令行用“;”分隔命令。windows的命令行用“&”分隔命令。

linux程序（包括移植到windows上的linux程序）的命令行选项都有短选项（1个字母）和长选项（1个单词）两种方式。短选项由“-”开头，长选项由“--”开头。如果选项有参数，短选项和参数间用空格分隔，长选项和参数间用“=”分隔。例如：

sort -k 3 a.txt

和

sort -key=3 a.txt

是等价的。

linux和windows都支持用TAB键自动补全。那么，如果需要在命令行的选项参数中输入TAB，应该怎么输入呢？例如sort命令允许用-t参数设定分隔符。如果我们想指定TAB为分隔符，我们怎么输入？在linux上可以输入：

sort -t ' ' -k 2 t.txt

输入第一个单引号后，先按Ctrl+v，然后按tab键，就输入了TAB。在特殊字符前输入Ctrl+v 可以让特殊字符被当作普通字符处理。在Windows上我没有找到在命令行输入tab的方法，写在批处理文件里也不行。这也算Windows的一个小缺陷吧。