算法学习笔记(4):计数排序

在宿舍呆着无聊接着在hackerrank上刷水题。这道题由于排序的依据是一定范围内的整数,所以用计数排序效率应当不错。

说到计数排序,实际上思路也很常见。最常见的一个例子就是比赛或者是考试的时候要进行排名。

比如某班有3名同学考了100分,2名同学考了99分,5名同学考了98分。那么很明显,比99分高的同学一共有3名,所以考99分的同学只能是第4名了。

计数排序大概就是做了个数数每个元素前面有多少元素这个事情。先统计最高分多少分,然后依次统计各个分数的学生个数,然后以此叠加就可以统计出前面有多少个学生了。

而且由于不同分数段的学生是按照原顺序放置到新数组中的,所以在原数组中的顺序并不会被打乱,即这个算法是稳定的。这也是为什么这道题可以用计数排序解,因为并不会打乱文本的顺序。

顺便一提,这道题中的最大值max()的复杂度应该是,所以总运行时间应该是。因为计数排序并不涉及到不同元素之间的比较,即不是比较排序,所以的下界并不适用于计数排序。

最后附上这道题的一个无脑解。

# Enter your code here. Read input from STDIN. Print output to STDOUT
n = int(raw_input())
ar = []
idx = []
out = [None]*n
for _ in range(n):
    ar.append(raw_input().split())
    ar[-1][0] = int(ar[-1][0])
    idx.append(ar[-1][0])
    if _<n/2:
        ar[-1][1] = "-"
countlist = [0]*(max(idx)+1)
for item in ar:
    countlist[item[0]]+=1
for i in range(len(countlist)-1):
    countlist[i+1]+=countlist[i]
for item in reversed(ar):
    out[countlist[item[0]]-1]=item
    countlist[item[0]]-=1
for item in out:
    print item[1],

如何编译tslib

前些天用qt4.8做的界面的字体渲染特别难看,所以准备用qt5.4做界面。X宝上买的mini2440并不随机赠送编译好了的qt5.4,所以还得自己从头编译一份。

先记录下编译tslib的过程吧。(具体原理完全不懂啊...

编译器使用了随机赠送的arm-linux-gcc-4.4.3,这里有的下

when-theory-met-practice

下面一段中的一堆变量我也不知道为什么这样定义,不过这样能够成功。其抄袭于这篇博客

$mkdir ~/tmp
$cd ~/tmp
$git clone https://github.com/kergoth/tslib.git tslib
$cd tslib
$export PATH=编译器的路径/bin:$PATH
$export CROSS_COMPILE=arm-none-linux-gnueabi-
$export CC=${CROSS_COMPILE}gcc
$export CFLAGS="-march=armv4t -mtune=arm920t"
$export CXX=${CROSS_COMPILE}"g++"
$export AR=${CROSS_COMPILE}"ar"
$export AS=${CROSS_COMPILE}"as"
$export RANLIB=${CROSS_COMPILE}"ranlib"
$export LD=${CROSS_COMPILE}"ld"
$export STRIP=${CROSS_COMPILE}"strip"
$export ac_cv_func_malloc_0_nonnull=yes
#./autogen.sh
#./configure --host=arm-linux --prefix=你要的安装路径 --enable-shared=yes --enable-static=yes
#make
#make install

另外关于$CFLAGS的设置,可以参考这里

简单来说这样就可以安装成功了,不过还是会碰见一些问题。以下将记录下我碰见的几个简单问题。

1. configure的时候,终端中会显示

checking for arm-linux-gcc… arm-none-linux-gnueabi-gcc
checking whether the C compiler works… no
configure: error: in `/usr/local/tslib':
configure: error: C compiler cannot create executables
See `config.log’ for more details

这个应该需要具体问题具体分析。看config.log文件中的输出信息应该能摸到头绪,我是因为有些依赖没有安装。

#apt-get install lib32stdc++6

安装完之后就没有问题了。

2.undefined macro错误

错误的提示信息是

configure.ac:25: error: possibly undefined macro: AC_DISABLE_STATIC
If this token and others are legitimate, please use m4_pattern_allow.
See the Autoconf documentation.
configure.ac:26: error: possibly undefined macro: AC_ENABLE_SHARED
configure.ac:27: error: possibly undefined macro: AC_LIBTOOL_DLOPEN
configure.ac:28: error: possibly undefined macro: AC_PROG_LIBTOOL

安装libtool即可

#apt-get install libtool

算法学习笔记(3):插入排序、归并排序与逆序数

前些天在挨个做hackerrank上的题目的时候,碰到了这么一道题

题目的完成率并不高,只有百分之三十六点多,我估计了下难度,自己应该是做不出来的,最后果然没做出来。不过在Discussion下面还是看到了些有用的帮助,有人说用mergesort能做出来。于是又仔细的想了想,还是花了些力气做出来了...

题目的内容是计算插入排序一个序列的移动元素的总次数。实际上是计算的序列的逆序数

逆序数的定义上面那个wiki的链接里说的挺清楚的了,数的就是反序排列的数字对数。

比如[1,3,2]的逆序数是1,在插入排序的时候,2会向左移动一次,整个序列变成了[1,2,3]。

[2,3,1]的逆序数是2,在插入排序的时候,1会向左移动两次,整个序列变成[1,2,3]。

hackerrank在排序这一章前面也有一道题是计算插入排序移动次数的,当时按照题目的提示,使用的直接在插入排序的时候,移动一次,加一次,最后依次数出来移动的次数。当然这个的时间复杂度就是,在序列比较长的情况下很容易超时。这种比较『暴力』的方法,显然不适合本题。

mergesort是一种比较简单的方法。可以很容易的想象出,在merge过程中,如果『小序列』非空,每当『大序列』的最小元素被选出来,就意味着逆序数需要自增目前『小序列』中元素个数那么多,因为这个时候『小序列』中的所有元素都比位于他们之后的『大序列』中挑出的最小元素大。

而且mergesort的时间复杂度是,已经是比较排序的最优了,所以也理应在本题中不会超时。

知道这个关键点,代码实现就很容易了,就是增添个自增的语句而已,代码如下所示。

def merge(a,b):
    global answer
    a_flag = 0
    b_flag = 0
    result = []
    while a_flag<len(a) and b_flag<len(b):
        if a[a_flag]>b[b_flag]:
            result.append(b[b_flag])
            answer+=(len(a)-a_flag)
            b_flag+=1
        else:
            result.append(a[a_flag])
            a_flag+=1
    if a_flag==len(a):
        result.extend(b[b_flag:])
    else:
        result.extend(a[a_flag:])
    return result

def mergesort(l):
    if len(l)>1:
        mid = len(l)/2
        a = l[:mid]
        b = l[mid:]
        a = mergesort(a)
        b = mergesort(b)
        return merge(a,b)
    else:
        return l

n = input()
for iterate in range( n ):
    x = input()
    a = [ int( i ) for i in raw_input().strip().split() ]
    answer = 0
    mergesort(a)
    print answer

reportLab渲染pdf

继续之前的工作。因为kindle支持的格式有限,所以剩下的只有mobi,pdf两个选择了。找了半天没找到合适的制作mobi文件的模块,所以选用了一个不错的制作pdf的模块——reportlab。

昨天折腾了半天,发现reportlab-userguide的第二章中最简单的helloworld例程输出的pdf文件在电脑中看还正常,在kindle的竖屏模式中看就没有字了,不过横屏模式倒是可以看到字。

我以一个什么都不知道的普通用户的心态猜测了下,可能是kindle为了尽可能将pdf表现的和txt文件差不多,采用了比较奇葩的解析方式,这样竖屏看的时候字比较大。

于是又把后面几张大概看了看,最后还是成功的输出了可以在kindle上阅读的pdf文件。

# 首先import需要用到的模块
from reportlab.platypus import SimpleDocTemplate, Paragraph, Spacer
from reportlab.lib.styles import getSampleStyleSheet
from reportlab.pdfbase import pdfmetrics
from reportlab.pdfbase.ttfonts import TTFont

其中后两条是为了使用自定义的字体。因为不太清楚kindle支持的中文字体有哪些,所以使用了华文宋体。

# 准备要用到的一些东西
STSong = r"/home/juiceyang/jianshuDownloader/STSong.TTF"
# 将华文中宋字体的注册名为"STSong"的字体,当然也可以取别的名字
pdfmetrics.registerFont(TTFont("STSong", STSong))
# 要生成的pdf的尺寸,对应的是kpw2的6寸屏,单位是postpoints
kpw2_size = (331.2, 476.2)
# 使用华文中宋的style模板,style的属性之类的可以看reportlab-userguide的5.6一节
styles = getSampleStyleSheet()
style = styles["Normal"]
style.fontName = "STSong"

STSong.TTF是从网上下载的字体文件,也许应该换成开源字体,不过为了做样例,就不再细改了。

# 新建一个文档
doc = SimpleDocTemplate("你好世界.pdf", pagesize=kpw2_size)
# 开头先插一个大空白
Story = [Spacer(1, 20)]
# 插入简体中文
chs = "我能吞下玻璃而不伤身体。"
p = Paragraph(chs, style)
Story.append(p)
Story.append(Spacer(1, 10))
# 插入繁体中文
cht = "我克藝吃玻璃,我不毀受傷。"
p = Paragraph(cht, style)
Story.append(p)
Story.append(Spacer(1, 10))
# 插入日文
jap = "私は硝子を食べられます。私を傷付けません。"
p = Paragraph(jap, style)
Story.append(p)
# 韩文不太常见就不测试了,输出文档
doc.build(Story)

最后输出的pdf的效果和在kindle上看得效果分别如下:

pdf

可以看出,kindle中竖屏模式浏览的效果和电脑上看的效果还是有些差别的,明显字大了很多。

简书下载器——使用BeautifulSoup4解析网页

虽然名字是下载器,不过实际上就是用python写的一个网络爬虫,通过某种规则将网页爬完,然后进行解析,获得自己想要获得信息。

而简书上的文章的集合方式大概有3种:

  • 文集(notebook),url为http://www.jianshu.com/notebooks/文集id/latest
  • 专题(collection),url为http://www.jianshu.com/collection/专题id
  • 用户(users),url为http://www.jianshu.com/users/用户id/latest_articles

下载器主要也就是批量下载这三种集合中的文章。

下面用一篇文章来解释下大概的工作原理。

这篇文章的url是http://www.jianshu.com/p/8862a4250944,可以看出来并没有像某些网页一样,带有.html/.php/.asp之类的后缀,是因为服务器有某些机制可以知道在访问这种没有后缀的url的时候,究竟是想访问哪些文件。

以chrome为例,如果按下F12打开Developer Tools,然后再刷新上面那篇文章,那么可以在Network下看到http://www.jianshu.com/p/8862a4250944.html这个文件的GET请求。如果将这个html文件下载下来,看代码的话,会发现我们想要的文章的内容都在这个html文件中有所体现。

就像wikipedia中说的一样,html只是一种组织信息的一种方法,我们所需要的文章中的信息(包括图片、引用等等)都在html文件中有所体现。我们所需要做的,就是通过html tag的类型,将信息分门别类,并下载到本地。最终再通过某种方式,按其性质制作回pdf文件当中去。

所以工作流程大概就是:获得html文件内容,解析html文件,重新排列内容,并制作成pdf文件。

获得html文件的内容可以使用python内置模块urllib/urllib2,我使用了urllib2(其实对于这么小的问题两个用起来差不多)。

import urllib2
html = urllib2.urlopen("http://www.jianshu.com/p/8862a4250944").read()
print html

这面那段代码可以将那片文章的html文件打开,并读出内容。如果便于理解的话,类似于open()和readlines(),只不过readlines()会返回一个list,这个会返回一个str。看输出的话就会发现str对象html的__str__()方法会返回html文件的内容,第一步完成。

解析html文件使用了BeautifulSoup4,安装方法在这片短文中已经简要介绍了。这个工具的功能就像一个筛子,通过html tag的不同,筛出使用者想要的内容。

from bs4 import BeautifulSoup
import urllib2
html = urllib2.urlopen("http://www.jianshu.com/p/8862a4250944").read()
soup = BeautifulSoup(html)
print soup.title

运行上面一段代码,就会发现输出内容为html文件的title标签的内容:

<title>简书干货内容推荐 - 简书</title>

所谓的筛子的功能,大概就是这样,所需要做的就是先预先找好要筛出来的tag的范围,然后用bs4筛出来。通过观察html的结构,可以看出文章的内容集中在<div class="show-content"></div>中,所以我们所需要做的也就只是找到class是show-content的标签,然后将其从html里面提取出来而已。这样第二步也就完成了。

之后也可以再一次通过标签的内容(比如<strong>、<a>、<blockquote>)再次筛选内容。即完成第三步。不过由于目前制作pdf的方法还在学习当中,输出的文件格式还是txt,也就没有必要进行第三步第四步了。所以现在是通过正则表达式直接删除了所有的html标签,丢掉了格式信息。在学习完了pdf制作方法后应该会再次进行第三步和第四步。

写了个批量下载简书文章的工具

前言:这个脚本目前只能用来下载文本,也就是说下载下来的都是txt文件。以后可能会写输出pdf文件的脚本,以后的事以后再说啦┐(´_`)┌

前几天zhihu上有人问怎么批量下简书上的文章到kindle上看,恰好上个学期用了beautifulsoup,趁着手热,写了个简书的批量下载工具。以下是简单的使用方法,linux平台下使用很简单,就不细说了,主要记录下windows的使用过程。

1.首先从这里下载python2,安装就是各种下一步,没什么好说的。

2.从这里右键另存为下载get-pip.py,安装方法就按照网页上的安装。

get-pip

比如下载到了桌面上,就先进入桌面的路径,然后python get-pip.py即可。

3.安装BeautifulSoup,这东西大概理解可以理解为一个筛子,把网页中需要的东西筛选出来。安装方法是在cmd中运行安装命令:

pip install beautifulsoup4

bs4

至此脚本的运行环境已经安装完毕了。

4.从这里下载脚本,下载完解压出来。比如解压到了一个名叫jianshuDownloader-master的文件夹下。在jianshuDownloader-master中新建两个空文件——userlist.txt和notebooklist.txt。

userlist.txt中存放批量下载的用户名。比如我们想批量下载该用户的文章,url为http://www.jianshu.com/users/5104d005424d/latest_articles,我们需要的就是users/和/latest_articles中间的那串字符。简单来说可以把它看成用户的『身份证号』,能唯一识别出是哪个用户。

userlist.txt中可以存放多个用户的『身份证号』,比如我们想下载5104d005424d、7041c064cbd2、2659558557cc三位用户的所有文章,就把他们的『身份证号』每行存一个就行了。

userlist

userlist.txt中存放用户的『身份证号』

 

同理,notebooklist.txt中用来存放文集的编号。比如我们想下载这个这个这个三个文集中的所有文章。就把这三个文集的编号存到notebooklist.txt中,存的方法和userlist.txt的一样,也是一行一个。

notebook

notebooklist.txt里面存文集的编号

 

5.最后一步就是双击main.py,按照提示选择是按用户下载还是按文集下载了。

输入1按用户下载,输入2按文集下载。

由于现在是用正则直接把html里面的标签去掉,所以比较慢,不过既然是为了省鼠标,运行起来别管就好了...以后可能会抛弃这种做法,不过以后的事以后再说啦┐(´_`)┌

另外我也不知道为啥linux下和windows下速度差那么多...

还有windows的cmd里面一涉及到中文就烦得不行,直接用英文了...

下载完成之后会自动退出,然后下载好的txt就放在jianshuDownloader-master\data文件夹下了,在然后拷进kindle里看就好了。

IMG_20150212_052232

随便拷进去一篇文章,大概效果就是这样了

 

后记:这玩意儿纯属一个代码爱好者的练手作,请各位老爷要求不要太高。如果有问题我尽量修改

 

算法学习笔记(2):快排

前言:最近两天又改变了下学习方法。直接看《算法导论》,然后看完立刻实现感觉太直接,自己不需要动脑子,引导性也不是很强。于是去hackerrank上一点点学。昨天把warmup和implement完成了,熟悉了下大概环境。今天把插排和快排看完了。

网上之前一直流传的一个图书馆大妈给书排序的段子形象的解释了快排的思路。

图书馆看见两个志愿者需要把还回来的一堆书按顺序入架, 管理员大妈给他们教的时候说:『你先在这堆书里拉出一本来,把比它号小的扔到一边,比它大的扔到另一边,然后剩下两堆继续这样整,这样排的快!』

从分治法的思维来看,快排和堆排的路数差不多。堆排中是假设左子树和右子树是已经排好了的树,而快排中则是假设左侧的序列和右侧的序列分别是排好了的序列。其实就是每次排序之前都能保证小的在左面,大的在右面。思路很简朴。

对比之下,由于堆排中使用了二叉树的结构,所以在排序这个事情上徒增了复杂度,所以导致了其比快排效率低。

过来人也都对这种『凡事不能搞得太复杂』的思想也有过阐述。

Everything should be made as simple as possible, but no simpler.

——爱因斯坦

万物之始,大道至简,衍化至繁。

——老子《道德经》

说回图书馆大妈的段子。毕竟图书馆大妈不是程序员,只能想到最简朴的快排的方法。事实上,在把书分成三摞(即『比Pivot小的一摞』、『Pivot一摞』、『比Pivot大的一摞』)的不停迭代的过程中,实际上是个把最初的一整摞书摊开的过程。形象的说就是原来一摞书撑死只占A4纸那么大的面积,然而摊开之后会占许多倍原来的面积。即段子中的排序实际上是会多占空间的。

对应的也有一种『原地快排』的算法,并不需要把书按着大小摊开,只需要把书从那一摞里『抽出来』再『塞回去』(对应着其实就是数组元素之间的互相调换)即可以完成排序。《算法导论》上杭也介绍的是这种快排方法。

这种原地快排的代码也不是很复杂,书上写的也很清晰。我觉得一个挺巧妙的地方是《算法导论》中使用两个下标来圈定了『大于Pivot的右侧子数组』。这样处理的时候很直观。

别的关于快排也并没有什么了,毕竟学的时候感觉一切都是那么顺理成章。又想起来小波课上老师说的,『一看都不对的结论肯定有问题』。

算法学习笔记(1)——堆排序

前记:最近回家除了干干所里剩下的活,手头剩了不少时间。于是趁着这个寒假比较长,准备把算法导论看完了。不过隔了很久突然看起,有些生疏,于是准备再实现一遍。选择语言秉承了「人生苦短,我用python」的原则,果断的选择了python。

虽然把代码提交到了github上,不过感觉不能看着书把伪代码翻译一遍就算完了,写完了之后好好感悟一下,记录一下自己的感想也是很重要的,于是准备在博客上大概记录下自己的学习笔记和感想。

所以重点不在于名词定义和原理解释,毕竟wiki上也好,书上也好,都是一翻到处都有。我想记下来的更多的还是自己个人在学习过程中觉得这些算法构思巧妙的地方。

第一天的复习内容是堆排序,我认为巧妙的地方有以下几点。

1.首先这里的堆使用的数据结构是二叉树,在顺序存储二叉树的时候,父节点、左子节点和右子节点的下标之间具有天然的简单倍数、邻近关系。这直接决定了在访问数据时,不需要很大的代价,客观上显著降低了复杂度。

访问各个节点的代码如下所示,为了简便并没有考虑下标越界的异常处理,这也是为了突出原理。用书上的话说就是:

数据抽象、模块化和错误处理等问题往往都被忽略掉了,以便更简练的表达算法的核心内容。

def get_parent(self, index):
	return self.heaplist[index/2+1]

def get_leftchild(self, index):
	return self.heaplist[2*index+1]

def get_rightchild(self, index):
	return self.heaplist[2*index+2]

2.其次,堆排序将一个复杂的工作分成了许多层次,即所谓的分治法(divide-and-conquer)。

逆向思考的话,就是将一个排序问题分解成了「提取最大元素」、「构建最大堆」、「使用两个最大堆一个节点组成一个最大堆」三个层次。

而如果正向思考的话,由于最大堆的最大的节点就是根节点,所以实际问题就变成了「如何将最小的元素都放在叶节点上」、「如何将根节点和某个叶节点交换之后,再次构建最大堆」两步。

虽然实际上使用的方法都是相同的,即从叶节点开始(由于是顺序存储结构,只需要从数组的中间开始倒序进行)构建最大堆,最后自然整个树会变成最大堆;而后将根节点拿出来(《算法导论》中是将根节点放到了数组末尾,由于放到数组末尾之后并不是二叉树的组成部分,其下标与其他节点的下标没有关系,实际就是放到了另一个数组里)。最后自然形成了一定的大小顺序。

从这种角度来看,其实这种排序方法与插排的思想差不多。就是依次为各个元素找到合适的位置,而由于在元素比较多的时候,第一次构建最大堆的时候,所有的元素形成了一定的有序性。所以一般堆排序比插排的效率要高,不过也不是很高,因为受到了算法设计思维(单个、依次操作)的限制。

实现的代码如下所示。

def max_heapify(self, i=0):
	l = 2*i+1
	r = 2*i+2
	if l <= self.length-1 and self.nodelist[l] > self.nodelist[i]:
		largest = l
	else:
		largest = i
	if r <= self.length-1 and self.nodelist[r] > self.nodelist[largest]:
		largest = r
	if largest != i:
		self.nodelist[i], self.nodelist[largest] = self.nodelist[largest], self.nodelist[i]
		self.max_heapify(largest)

def build_max_heap(self):
	for i in reversed(range(0, self.length-2-1)):
		self.max_heapify(i)

def heapsort(self):
	self.build_max_heap()
	for index in reversed(range(1, self.length)):
		self.sortlist.append(self.nodelist[0])
		self.nodelist[index], self.nodelist[0] = self.nodelist[0], self.nodelist[index]
		del self.nodelist[index]
		self.length = len(self.nodelist)
		self.max_heapify()
	self.nodelist = self.heaplist
	self.length = len(self.nodelist)

最终所有的代码在heapsort.py

Linux中读写i2c

最近因为种种原因,要在跑Linux Embedded的上位机中写一个程序,要有界面还要控制i2c和下位机通信。

于是回想起了本科的时候各种搓板子的「悲惨经历」,以及微机原理老师留的在嵌入式OS上随便跑点什么的课后大作业。预估了一下,估计这活挺难的。

不过好在最近一段时间一直在用Linux,或多或少的也了解了一些关于Linux的知识。发现在应用层写个控制i2c的程序实在是太简单啦!

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/ioctl.h>
#include <linux/i2c-dev.h>
#include <linux/i2c.h>
#include "i2c.h"

int slave_read_byte(int fd, unsigned char addr, char* readByte)
{
    fd = ::open(I2CDEV, O_RDWR); //这里需要添加::,在global namespace中找到open函数,close同理。
    if(fd<0)
    {
        return 1;
    }
    if(ioctl(fd, I2C_SLAVE, addr) < 0)
    {
        return 1;
    }
    read(fd, readByte, 1);
    ::close(fd);
    return 0;
}

int slave_write_byte(int fd, unsigned char addr, char* value)
{
    fd = ::open(I2CDEV, O_RDWR);
    if(fd<0)
    {
        return 1;
    }
    if(ioctl(fd, I2C_SLAVE, addr) < 0)
    {
        return 1;
    }
    write(fd, value, 1);
    ::close(fd);
    return 0;
}

然后就ok了,剩下的就可以在pushbutton的slot里读写下位机之类的了。

去除Discuz!论坛生成的乱码

这几天在写「计算网络心理学」这门高大上的神课的大作业:用python写个爬虫爬老师指定的几个论坛。

写的时候发现论坛的帖子的内容中会随机的插有乱码。这倒也不是新鲜事了,原来我一直不知道是干嘛用的。google一下发现好像是为了防止复制党的。

举个例子,随便摘了一个贴子某一层楼的内容。

<font class="jammer">( `) R4 V, C&nbsp;&nbsp;{7 r0 B, R7 R</font><br />
<strong><font size="4"><font color="#0000ff">怎么就“故意篡改”了?</font></font><font size="6"><font color="#ff0000">您的智商不会有问题吧?</font></font></strong><br />
<span style="display:none">$ C$ ]( {, {% x% </span><strong><font size="6"><font color="#ff0000"><br />
<span style="display:none">& j( E- D6 e3 Y; O</span></font></font></strong><font class="jammer">: q, J; Z. y5 r2 v&nbsp;&nbsp;t* t</font><br />
<img src="static/image/smiley/new1/em58.gif" smilieid="192" border="0" alt="" /><br />
<span style="display:none">$ q- d0 @4 K4 z* P+ y4 |) h- ?</span><br />
<span style="display:none">3 p5 h; g% z; g, e7 n) E</span><font class="jammer">% Y8 }1 s/ `) a9 P# j- S! x</font><br />
<br />
<span style="display:none">- R: a$ t&nbsp;&nbsp;F- A7 o! R# L; l</span><strong><font size="3"><font color="#0000ff">你自己当时的帖子,是直接对我的帖子进行回复的,也就是说,是引用了我的内容的,是一样的吧?如果事后改了,那就不一样了。</font></font></strong><font class="jammer">; C; h# C8 Z) W5 c% d4 @</font><br />
<font class="jammer">" h8 _+ e&nbsp;&nbsp;|+ {3 X</font><br />
<font color="#ff0000"><strong>你自己,在几乎同一年月注册了几个马甲账号?还口口声声说别人?</strong></font><br />

可以看出来有很多有规则的乱码,一般都是一个字符,加若干个字符乘2+空格,然后再以一个字符结尾。不过discuz!还是挺厚道的留了个jammer的属性,所以说用正则去掉这些乱码还是挺简单的。

# delete jammers
post_text = re.sub(r'<font class="jammer"[sS]*?/font>|<span style="display:none"[sS]*?/span>', "", post_text)
# delete accessory
post_text = re.sub(r'<ignore_js_op[sS]*?/ignore_js_op>', "", post_text)
# delete updating info
post_text = re.sub(r'<i class="pstatus"[sS]*?/i>', "", post_text)
# delete quote
post_text = re.sub(r'<div[sS]*?/div>', "", post_text)
# delete emoji
post_text = re.sub(r'<img.*?>', "", post_text)
# delete font label, strong label and td label
post_text = re.sub(r'</?strong.*?>|</?font.*?>|</?td.*?>', "", post_text)
# delete n & s in text
post_text = re.sub(r's|<br/>', "", post_text)

总体来说还是挺傻瓜且直观的,从几个测试的贴子的表现来看,效果还不错。不过由于贴子内容的html label可能不止这些,可能删除不干净,另外这门课主要还是关注于用户的发言中的词语之类的,对于数据表格之类的并不是很关注。所以这么处理效果还不错。

如果需要保留表格啊,附件啊,图像啊之类的,应该还需要再具体修改。