遗传算法解决数学等式(续)

之前的文章(http://blog.foool.net/2017/08/用遗传算法解决简单的数学等式问题/) 中介绍了过如何使用遗传算法解决数学等式问题,即寻找满足等式

(a + 2b + 3c + 4d) – 30 = 0

的一组解。适应函数确定后,影响算法好坏的主要依赖于交叉概率(crossover ratio),变异概率(mutation ratio)、初始基因组大小(即用于交叉变异的基因个数)和基因初始阈值。基因初始阈值指的是基因的取值范围,比如等式中变量a/b/c/d 的取值范围,我在实验中限定变量为大小不超过100 的整数。下面给出本文的几个结论。

一、遗传算法也可以用于寻找唯一解

之前的文章 中寻找的是四元一次等式的一个解,这个解的个数是无穷的,遗传算法能够找到一个解,但每次找到的解也不相同。但如果要用遗传算法解一个包含四个等式的四元一次方程组(唯一解)也是可行的,只是时间话的需要更长。比如遗传算法解四元一次等式平均需294 次迭代,解四元一次方程组需11400 次迭代(所有参数同之前的文章)。本文使用的四元一次方程组为:

(a + 2b + 3c + 4d) – 30 = 0

(2a + 2b + 2c + 2d) – 24 = 0

(3a + 1b + 7c + 1d) – 60 = 0

(4a + 3b + 2c + 1d) – 30 = 0

二、增加初始基因组大小有可能加速算法速度

增加基因组中基因数量,那么每次迭代/循环中的基因数量更多,可能出现解的概率增大。在以四元一次等式为例的实验中,增加基因组大小的确显著减少了迭代的次数,即使考虑了增加基因数目而带来的增量计算,算法仍减少了程序的整体运行时间。

三、增加初始基因组大小也有可能不能加速算法速度

有点调皮了,这个结论是和第二点结论是相左的,如在其他参数相同情况下,随着基因组大小增大,遗传算法在解四元一次方程组需要迭代的次数增加。

四、对于特定问题,参数大小影响算法性能大

下图是在基因组大小为18 时, 遗传算法1000 次测试四元一次等式求解所需要迭代次数的热力图,横坐标是变异率,从5% 到43%,纵坐标是交叉率,从5% 到70% 。热力图颜色范围是0-300,最深颜色表示300 次或300次以上迭代(比如在交叉率是70%,变异率是43%,实际迭代次数是9268次)。

综上,1.借助于适应函数,交叉、变异过程,遗传算法给出了一个在较大解空间快速求解的途径,但具体设计交叉、变异过程需要考虑特定问题;2.选取合适的参数极大影响了遗传算法性能,一般可以通过相似问题(复杂度更低)的参数选择作为参考(但是这种参考也不一定可靠,比如上面例子中,四元一次方程中增大基因组个数可以减少迭代次数,但在四元方程组中增加基因组个数却增加了迭代次数)。

自循环字符串/周期性字符串的判别和概率

问题来源:需要判断一个长度为N 的0/1 二进制字符串是自循环的概率是多少?自循环指的是一个字符串循环移位s 位仍然可以得到其本身,s 小于字符串长度。比如,010010 是自循环的,为将这个字符串循环右移三个bits 字符串还是其本身。

通过自循环字符串特征很容易推导出:自循环字符串是周期性字符串,即字符串完全由若干个相同子串拼接得到,上面例子中重复的子串是 010。并且,自循环字符串移位得到其本身需要的最少步数s 和最小子串长度相同,也就是说,计算得到字符串最小重复子串也就得到了其自循环需要移位数s。

那么问题归结为如何找到一个周期性字符串的最小重复子串

算法:令周期性字符串为S,那么SS 是两个S 的拼接,从SS 第二个字符开始,利用字符串匹配寻找S,如果SS 从第c 个字符开始包含了S 字符串,则S 的最小周期子串长度为c。下面是两个例子:

例子一:S =  010010

SS = 010010010010

  1.  0 1 0 0 1 0 0 1 0 0 1 0  不是S
  2.  0 1 0 0 1 0 0 1 0 0 1 0  不是S
  3.  0 1 0 0 1 0 0 1 0 0 1 0  是S

结束,最小子串长度为3,即010 。

例子二:S =  abaaabaaabaa

SS = abaaabaaabaaabaaabaaabaa

  1.   a b a a a b a a a b a a a b a a a b a a a b a a
  2.   a b a a a b a a a b a a a b a a a b a a a b a a
  3.   a b a a a b a a a b a a a b a a a b a a a b a a
  4.   a b a a a b a a a b a a a b a a a b a a a b a a

结束,最小子串长度为4,即abaa 。

接着统计了下二进制字符长度(X轴)和周期性字符串个数/概率(Y轴)关系。

可见,自循环字符串个数和概率与其字符串长度有关,总的来说:

  1. 长度越长,包含的自循环的字符串个数越多,呈指数增加
  2. 长度越长,字符串可能是自循环的概率降低,呈指数下降
  3. 素数只有两个自循环字符串(全0,全1)
  4. 包含分解因子越多,越可能包含更多自循环字符串

 

用遗传算法解决简单的数学等式问题

[翻译]原文:Genetic Algorithm for Solving Simple Mathematical Equality Problem

[翻译]地址:https://arxiv.org/ftp/arxiv/papers/1308/1308.4675.pdf

[翻译]目的:文章旨在为新手解释什么是遗传算法。并使用遗传算法这个工具一步步解决一个具体的数学问题——求解数学等式的解。

基本理念

在通过遗传算法寻找问题解的过程中,用染色体来表示一个解,一堆染色体叫做种群。染色体由基因构成,基因可以是数值的、符号的也可以是其他类型数据结构(视所解决的问题来定)。染色体通过环境适应度来衡量这个解对于问题的优劣程度。种群中的染色体通过交叉(交配)遗传到下一代,子代染色体是父代基因的组合。基因还会发生突变,遗传算法中使用交叉率和突变率来控制。

算法步骤

  1. 决定染色体数目、循环代数(决定遗传多少代)、突变率和交叉率;
  2. 产生染色体种群,并使用随机值初始化染色体中的基因
  3. 重复步骤4-8(重复次数等于循环代数)
  4. 考量每个染色体的适应值
  5. 染色体选取
  6. 交叉
  7. 变异
  8. 产生新的后代染色体
  9. 得到最终解

算术问题

以求解多元一次不等式 a+2b+3c+4d=30 为例,使用遗传算法找到a b c d 值满足该等式。很显然可以使用这样一个函数衡量适应度

f (x) = |(a + 2b + 3c + 4d) - 30|

a b c d 初始化为0到30之间的一个自然数。

步骤一 初始化                            (下面步骤不完全和算法步骤对应)

随机生成六个染色体Chromosome[1-6]。

Chromosome[1] = [a;b;c;d] = [12; 5; 23; 8]

Chromosome[2] = [a;b;c;d] = [ 2; 21; 18; 3]

Chromosome[3] = [a;b;c;d] = [10; 4; 13; 14]

Chromosome[4] = [a;b;c;d] = [20; 1; 10; 6]

Chromosome[5] = [a;b;c;d] = [ 1; 4; 13; 19]

Chromosome[6] = [a;b;c;d] = [20; 5; 17; 1]

步骤二 评估

计算每个染色体的适应度。

F_obj[1] = Abs(( 12 + 2*05 + 3*23 + 4*08 ) - 30) = 93

F_obj[2] = Abs((02 + 2*21 + 3*18 + 4*03) - 30) = 80

F_obj[3] = Abs((10 + 2*04 + 3*13 + 4*14) - 30) = 83

F_obj[4] = Abs((20 + 2*01 + 3*10 + 4*06) - 30) = 46

F_obj[5] = Abs((01 + 2*04 + 3*13 + 4*19) - 30) = 94

F_obj[6] = Abs((20 + 2*05 + 3*17 + 4*01) - 30) = 55

步骤三 选择

适应度是越小越好,我们将适应度取倒数(加1避免出现除以0的错误),并归一化得到一个概率P

Fitness[1] = 1 / (1+F_obj[1]) = 1 / 94 = 0.0106

Fitness[2] = 1 / (1+F_obj[2]) = 1 / 81 = 0.0123

Fitness[3] = 1 / (1+F_obj[3]) = 1 / 84 = 0.0119

Fitness[4] = 1 / (1+F_obj[4]) = 1 / 47 = 0.0213

Fitness[5] = 1 / (1+F_obj[5]) = 1 / 95 = 0.0105

Fitness[6] = 1 / (1+F_obj[6]) = 1 / 56 = 0.0179

总计 Total = 0.0106 + 0.0123 + 0.0119 + 0.0213 + 0.0105 + 0.0179 = 0.0845

P[1] = 0.0106 / 0.0845 = 0.1254

P[2] = 0.0123 / 0.0845 = 0.1456

P[3] = 0.0119 / 0.0845 = 0.1408

P[4] = 0.0213 / 0.0845 = 0.2521

P[5] = 0.0105 / 0.0845 = 0.1243

P[6] = 0.0179 / 0.0845 = 0.2118

从结果可以看出基因4具有最高的适应度。接下来计算累计概率分布CPD:

C[1] = 0.1254

C[2] = 0.1254 + 0.1456 = 0.2710

C[3] = 0.1254 + 0.1456 + 0.1408 = 0.4118

C[4] = 0.1254 + 0.1456 + 0.1408 + 0.2521 = 0.6639

C[5] = 0.1254 + 0.1456 + 0.1408 + 0.2521 + 0.1243 = 0.7882

C[6] = 0.1254 + 0.1456 + 0.1408 + 0.2521 + 0.1243 + 0.2118 = 1.0

%e4%bf%a1%e6%81%af

然后生成六个随机数R[i=1,2,3,4,5,6],通过这六个随机数在上图中的位置区间选择新的染色体,比如,当随机数在0.4118到0.6639之间则选择染色体4。不难看出,这种方法反应了适应度好的染色体具有更大概率被选择。

随机生成的六个随机数如果是:

R[1] = 0.201

R[2] = 0.284

R[3] = 0.099

R[4] = 0.822

R[5] = 0.398

R[6] = 0.501

那么相应的六个新的染色体是:

NewChromosome[1] = Chromosome[2] = [ 2; 21; 18; 3]

NewChromosome[2] = Chromosome[3] = [10; 4; 13; 14]

NewChromosome[3] = Chromosome[1] = [12; 5; 23; 8]

NewChromosome[4] = Chromosome[6] = [20; 5; 17; 1]

NewChromosome[5] = Chromosome[3] = [10; 4; 13; 14]

NewChromosome[6] = Chromosome[4] = [20; 1; 10; 6]

 

步骤四 交叉

假设交叉率为25%(0.25),那么生成6个随机数,如果随机数小于交叉数,则对应的染色体被选择用于交叉。比如随机数为:R[1] = 0.191, R[2] = 0.259, R[3] = 0.760, R[4] = 0.006, R[5] = 0.159,R[6] = 0.340。那么得到用于交叉的三对染色体是NewChromosome[1], NewChromosome[4] 和NewChromosome[5]。交叉方式为:

NewChromosome[1] >< NewChromosome[4]

NewChromosome[4] >< NewChromosome[5]

NewChromosome[5] >< NewChromosome[1]

下面决定从那个位置进行交叉。因为染色体长度为4,则随机生成1-(4-1) 大小的随机数,随机数用于表示基因从哪里开始交叉。

C[1] = 1 C[2] = 1 C[3] = 2

CrossChromosome[1] = [ 2; 21; 18; 3] >< [20; 5; 17; 1] = [ 2; 5; 17; 1]     // C[1] = 1

CrossChromosome[2] = [20; 5; 17; 1] >< [10; 4; 13; 14] = [20; 4; 13; 14]     // C[2] = 1

CrossChromosome[3] = [10; 4; 13; 14] >< [ 2; 21; 18; 3] = [10; 4; 18; 3]    // C[3] = 2

那么剩余的种群中则有染色体:

NewChromosome[2] = [10; 4; 13; 14]

NewChromosome[3] = [12; 5; 23; 8]

NewChromosome[6] = [20; 1; 10; 6]

CrossChromosome[1] = [ 2; 5; 17; 1]

CrossChromosome[2] = [20; 4; 13; 14]

CrossChromosome[3] = [10; 4; 18; 3] 

步骤五 突变

假设突变概率为10%(0.1)。考虑到6个染色体中每个有6个基因,那么将有4×6×0.1= 2.4 ≈ 2个基因发生突变,通过产生两个1-24范围的数值得到突变染色体位置(假设为12和18)。接着还产生两个1-30之间的随机数作为突变后的结果(假设为2 和 5)。那么得到新的种群如下(红色为突变基因):

Chromosome[1] = [10; 4; 13; 14]

Chromosome[2] = [12; 5; 23; 8]

Chromosome[3] = [20; 1; 10; 2]

Chromosome[4] = [ 2; 5; 17; 1]

Chromosome[5] = [20; 5; 13; 14]

Chromosome[6] = [10; 4; 18; 3] 

步骤六 回到步骤二进行迭代

步骤七 至循环代数次结束

步骤六和步骤七类似,不再赘述。

整个过程如下图所示:

STM32F10x 单片机移植Modbus

最近在做STM32F10x 单片机移植Modbus的工作。Modbus是串口通信中广泛使用的协议,为了将其移植到stm32f10x单片机中,我们通过其开源实现freeModbus 进行了协议分析。stm32f10x 是一款被广泛使用的单片机,具有能耗小、价格低、速度快和中断响应迅速等优点。

首先,本文主要对Modbus 协议分析,有少量涉及到stm32单片机的内容;其次,文章主要以从机作为分析对象。(主从机是通信的一种模式,主机用于发送指令或者查询数据,从机用于应答)。另外Modbus 只有从机开源。

文章中参考了一些网友的资料,如有需要,可以参考下面文章:

  1. STM32单片机嵌入式实战教程 (stm32单片机视频讲解)
  2. Freemodbus RTU在stm32上的移植分析    (包含Modbus 发送接收状态机)
  3. freeModbus 主机的改写 (包含主机部分代码)
  4. http://www.freemodbus.org/ (freeModbus 官网)

下面按照几个方面进行协议分析:

一、单片机上串口通信的数据帧

单片机上串口通信通过数据帧完成,但必须规定一帧的开始和结束才能够进行正常的数据读取。简单的方法就是在帧的两端定义特殊的开始字节和结束字节。但这样的话,要求数据部分不能出现与开始字节和结束字节相同的内容,且帧的开始结束都是由应用程序判断。Modbus使用更“硬件”的方法,它通过两个帧之间的时间间隔来判断一个帧,即如果两个字节相隔一段时间(如传输3.5个字符时间),则认为新的的数据是新的一帧。

二、Modbus 启动流程

我们以freeModbus 为例进行分析(从参考[4] 可以下载到freeModbus 的源代码)。源码中mb.c是Modbus 的主要接口函数,include 目录是头文件,tcp/ascii/rtu 是Modbus 支持的三种传输模式,rtu 是最常用的,本文只涉及rtu模式。

主函数main() 中包含三个部分:

eStatus = eMBInit( MB_RTU, 0x0A, 0, 38400, MB_PAR_EVEN );
eMBInit() 是初始化函数,使用“模式,端口,地址,波特率,校验”几个参数初始化系统硬件相关信息。

eStatus = eMBEnable(  );
使能函数,使得Modbus 整个协议栈工作起来。具体会做开启一些中断等工作。

for( ;; ){
( void )eMBPoll( );
}

这是从机的主要工作部分,系统经过简单的配置和使能后,就进入eMBpoll()这样的服务模式,类似于Linux 中I/O多路复用的epoll(),当有事件发生时则做出相应响应。

整个Modbus工作流程如下图,也可以看出初始化、使能和eMBPoll()服务三个部分。

untitled-flowchart

初始化:eMBInit()在mb.c中根据定义的是rtu 还是asccii等模式会给接口函数(函数指针)进行初始化,这样的好处是对应于不同的模式使用统一的接口函数。当模式为rtu时:

pvMBFrameStartCur = eMBRTUStart;     \\开始接收数据帧
pvMBFrameStopCur = eMBRTUStop;       \\停止接收数据帧
peMBFrameSendCur = eMBRTUSend;       \\数据帧已经发送
peMBFrameReceiveCur = eMBRTUReceive; \\数据帧接收完毕
pvMBFrameCloseCur = MB_PORT_HAS_CLOSE ? vMBPortClose : NULL;
pxMBFrameCBByteReceived = xMBRTUReceiveFSM;       \\接收到数据帧内一个Byte
pxMBFrameCBTransmitterEmpty = xMBRTUTransmitFSM;   \\接收到空
pxMBPortCBTimerExpired = xMBRTUTimerT35Expired;    \\发生T35 中断

其中,然后就进入了rtu模式下的初始化eMBRTUInit(),其中主要是对串口中断和时钟中断进行的初始化(xMBPortSerialInit()和xMBPortTimersInit())。串口中断会开启相应的RCC时钟,配置GPIO口,配置串口模式(速率等),这和一般的单片机串口通信初始化类似;时钟中断初始化也是要开启相应的RCC时钟,设置时钟模式。需要指出:

Modbus用3.5个字符传输时间间隔作为隔断数据的判断依据,即从时钟中断使能开始,3.5个字符传输时间发起一次中断,记作T35

但当速率超过19200时,则使用固定的时间作为中断依据,这些都在eMBRTUInit()源码中有注释。

使能:eMBEnable()是Modbus 的使能函数,主要是通过函数pvMBFrameStartCur()(rtu模式下指向eMBRTUStart())进行串口中断和时钟中断使能。使能就是使得相应功能能够正常开始工作了。

基于事件的服务模式:eMBPoll()用于循环询问是否有新来事件,有则处理。

三、基于事件驱动的服务模式

从eMBPoll() 源码可以看出:

eMBpoll() 使得整个系统处于一个事件驱动的工作模式,当有新事件到达则处理它,否则就一直循环询问。

进入mb.c 中的eMBpoll() 函数可以看到,首先使用

xMBPortEventGet( &eEvent )

获取可能的事件信息,可能的事件有:

  • EV_READY:准备事件,可以开始接收数据了;
  • EV_FRAME_RECEIVED:数据帧到达事件,如果是发给自己的数据帧,则发起一个EV_EXECUTE 的事件;
  • EV_EXECUTE:执行事件,根据已定义的功能码和功能函数对数据帧进行相应处理 (eException = xFuncHandlers[i].pxHandler( ucMBFrame, &usLength ););
  • EV_FRAME_SENT:数据帧已经发送状态

那么什么时候系统会产生事件呢:中断和状态改变。当发生中断时,中断处理函数可能修改系统所处状态,并发起事件。系统中可以使用xMBPortEventPost() 发起事件。

四、各种状态

系统设置了几类状态,如eMBErrorCode 类型的eStatus 表示整个系统的总体状态,有下面几种:

  • MB_ENOERR,            /*!< no error. */
  • MB_ENOREG,            /*!< illegal register address. */
  • MB_EINVAL,               /*!< illegal argument. */
  • MB_EPORTERR,        /*!< porting layer error. */
  • MB_ENORES,             /*!< insufficient resources. */
  • MB_EIO,                      /*!< I/O error. */
  • MB_EILLSTATE,          /*!< protocol stack in illegal state. */
  • MB_ETIMEDOUT        /*!< timeout error occurred. */

eMBState 表示Modbus 协议在系统中的状态,有以下几种:

  • STATE_ENABLED
  • STATE_DISABLED
  • STATE_NOT_INITIALIZED

另外还有数据接收流程和数据发送流程中的不同状态,数据接收状态eRcvState有:

  • STATE_RX_INIT,         /*!< Receiver is in initial state. */
  • STATE_RX_IDLE,        /*!< Receiver is in idle state. */
  • STATE_RX_RCV,         /*!< Frame is beeing received. */
  • STATE_RX_ERROR     /*!< If the frame is invalid. */

数据发送状态eMBSndState有:

  • STATE_TX_IDLE,      /*!< Transmitter is in idle state. */
  • STATE_TX_XMIT       /*!< Transmitter is in transfer state. */

接收状态eRcvState和发送状态eMBSndState都在mbrtu.h/c 中定义,并在mbrtu.c中实现了接收/发送过程的状态机(xMBRTUReceiveFSM和xMBRTUTransmitFSM)。

五、两类状态机

xMBRTUReceiveFSM()和xMBRTUTransmitFSM()两个函数在mbrtu.c中实现了接收和发送过程中的状态机,两种状态机的状态变化在参考[2]中有详细描述,这里引用文中的图。

中断时改变发送接收状态的唯一手段,所以我们必须知道有哪些中断会改变发送和接收状态,从两个状态机来看,无非两种:数据到达或者发送的串口中断和T35对应的时钟中断。

六、两类中断

Modbus 在启动时进行了串口中断初始化和时钟中断初始化,两类中断在有字节到达串口和过了T35时间时会发生中断。串口USART1的中断处理函数为USART1_IRQHandler(),时钟TIM2的中断函数为TIM2_IRQHandler()。前者在portserial.c 中,后者在porttimer.c 中。

下图是串口USART1的中断处理流程,流程中可能不完全包括对发送和接收状态的修改,具体需要在源码中查看。

uart-interrupt-and-fsm

当捕捉到USART1串口中断时,首先判断是接收中断还是发送中断。在接收第一个字节后,会将发送空闲状态(STATE_RX_IDLE)变化为接收状态(STATE_RX_RCV),此后只要不溢出接收缓冲区就一直接收,没接收一个字符,无论哪个状态都要调用vMBPortTimerEnable()重置时钟中断。接收数据首先要求发送处于发送空闲状态(STATE_RX_IDLE),然后逐个发送数据。

timer-interrupt

当时钟TIM2中断使能后,每过T35时间系统就会发起TIM2的中断,并由porttimer里的TIM2_IRQHandler() 函数处理,中断处理函数根据数据接收状态(eRcvState)发起不同的事件,如当系统处于初始化状态(STATE_RX_INIT)过了T35时间,表示系统可以进入准备状态(发起准备系统准备EV_READY)接收数据了;如果系统处于数据接收状态,则表示数据数据已经接收完毕(还记得串口中断中如果一直有连续数据进来,则接收一个字节就重新使能时钟中断);vMBPortTimersDisable()最后失效所有时钟中断(没关系当接收状态发生改变时,系统中断会被开启)。

 

以上赘言是个人总结和网络资料的汇编。

 

Python 和字符编码

Python 2.* 的程序员肯定遇到过这样那样的字符编码问题:

  • 为什么从网站上爬取的html 在本地显示的就不正常?
  • 为什么会显示 UnicodeEncodeError: ‘ascii’ codec can’t encode character 这样的错误
  • python 中encode(),decode() 方法如何使用?

这样的字符编码问题总会让新手、老手都头痛,有时候即使解决了问题也不能完全知道原理。然后似乎这样的问题似乎在Python 3 中却又解决了?Python 3 又是如何解决字符编码问题?。写在python 2.* 即将要退出历史舞台时候,不知道以后python 程序员还会不会遇到这样的问题。但即使python 不会再有编码问题的困扰,更低级的语言可能还是会遇到,字符编码的原理也不会变化。


一、从编码的历史谈起

将任何一门课程(专业)都要从这个课程所研究的历史讲起。这是因为了解了历史问题,才能够明白课程需要解决的真正问题是什么?知道了这些年解决历史问题的方法,才能够反映出最新解决方法的先进性,也明白了为什么我们(课程)要这么做。

字符是信息的一种体现,字符编码也是信息编码的一个子集。如果考虑到古代的绳结记事、甲骨文和壁画也是信息的一种编码,我们这里所讲的字符编码指的是:自然语言字符(文字)在现代计算机上的映射方法。字符编码的来源是人类自然语言(文字),编码结果是存储在现代计算机上的二进制串。之所以是映射,因为每一个自然语言字符所对应的二进制串是唯一的。

large

1.1 ASCII 码表

现代计算机起源于英语为母语的美国,所以最初美国工程师在字符编码中首先考虑的是自己母语的使用方便,即26个英文字母(大小写),0-9数字和常用字符的编码。在1963年颁布了ASCII (American Standard Code for Information Interchange)字符编码表,如下所示:

ASCII 表

ASCII table

ASCII 表包含字符个数128(2^7)个,因此任何一个字符都可以在一个字节内存储下来,不会出现超过一个字节的字符。计算机解码时按字节解码即可,非常方便。ASCII 表不仅定义了像空格(space)、字母等可见字符,还定义了一些不可见字符。使用下面的代码可以输出0-127 的ASCII 码表。

for ii in xrange(0,128) print chr(ii)+'\t'

ASCII码表很好的解决了英语为母语的计算机使用者的信息存储问题,但人类的科技进步的成果也必须全人类共享啊。但如果仅靠一个字节来保存全世界所有语言的字符肯定是不合适的。如果法国人要将自己语言中的 é, è, ê or ë 输入到计算机怎么办呢?更不用说中韩日语以庞大数量汉字为基础了。

1.2 GB2312 中文字符编码

为兼容本地语言,各个国家开始制定了自己语言的编码方法。但为了向下兼容英语,各种编码方法都是在ASCII码上进行了扩展。我国常使用的GB2312 是最常见的中文编码方法,GB2312 于1980 年颁布,所以其标准号是GB2312-1980。GB2312 按两个字节编码一个中文字符,共收集了6763 个汉字和682 个非汉字图形。GB2312 不仅收录了中文,还收录了拉丁字母、希腊字母、日文片假名、平假名字母等。

GB2312 将两个高、低字节(第一个字节为高字节,第二个为低字节)分别称为区字节和位字节,一个区包含94个字,共计94个区。GB2312 规定区字节仅 0xA1-0xF7 (01-87加上0xA0)存储汉字,位字节 0xA1-0xFE 存储汉字。GB2312之所以从A0 开始编码可以避免与ASCII的冲突,比如打开一个GB2312 编码的文件,如果字节值小于128,则这是ASCII字符;如果字节值大于128,则这个字节属于一个汉字。
下面的方法给出了中国字符“您好!”和GB2312 编码后结果:

>>> ("你好").decode('gb2312').encode('gb2312')
'\xc4\xe3\xba\xc3'
>>>

这里需要解释下decode() 和encode() 函数了。首先需要明白Python 中有两种字符串类型,一种是str 字符串,一种是unicode 字符串。比如 ‘你好’ ,’news’,’나는 당신을 사랑합니다’ 是str 字符串,而 u’你好’ 则是unicode 字符串。

decode() 是将str 字符串转化为unicode 字符串

encode() 是将unicode 字符串转化为str 字符串

以GB2312 为代表的区域性字符编码方法还是存在着通用性的问题。

  1. 因为不同国家指定了不同的字符编码方法,相同的0/1 字符串在不同的字符编码方法中很可能对应不同的字符。那么打开一个文件,首先得知道它的编码方法才行。
  2. 为全世界语言字符进行统一的字符编码(或者制定一套各地域字符编码方法的转换规则),两个字节肯定是不够的,那么需要更多字节来存储字符么?

1.3 unicode

unicode 可以看做一个终极的字符编码方法,它给出了地球上常用字符的二进制映射,而且所有的二进制字符串唯一地表示一个字符。当然unicode 也向下兼容ASCII,下面给出了一些字符所对应的二进制、十六进制值。

字符   十六进制    二进制
I      49        01001001
J      4A        01001010
日     65e5      01101001 11100101
ᅱ      FFD6      11111111 11010110
♀      2640      00100110 01000000
♬      266C      00100110 01101100

unicode包含了人类常用的语言字符、标识等字符编码,目标是统一全球字符编码,它也似乎正在向这终极目标迈进。但也可以看出unicode 只给出了字符和二进制串的对应关系,并没有给出存储形式。而不同字符所占用的存储空间可能不同,比如ASCII 在unicode 中只占用了一个字节即可,而常用汉字在unicode 中需要占用两个字节,还有一些罗马字符可能需要三个或以上字节。如果直接存储的话可能导致无法分割字符串,也无法正确解码出字符,比如计算机读到了“65e5”,这是中文的日字还是两个字符(’65’ 和 ‘e5’在unicode 中对对应的字符)呢?

关于unicode 问题:如果计算机读到一个字节,如何判断这个字节是新的字符的开始,还是一个未读完字符的继续呢?

这个问题在ASCII 码表和GB2312 中是不存在的,因为所有字符都是固定长度。那么unicode 可不可以也使用最大的长度字符的字节数来表示呢?当然可以,比如最大unicode 用四个字节可以保存,那么所有的字符都占用四个字节,但问题就是需要的存储空间变得很大。比如unicode 对应字符的存储如下(这么多0 是不是浪费了很多存储空间呢?):

I    00000049
J    0000004A
日   000065e5
ᅱ    0000FFD6
♀    00002640
♬    0000266C

一个可以想到的办法就是在一个8 bits 的字节中,第一位用来保存是否是字符的开始(1表示这是一个新字符,0表示这个字符的unicode 还没有结束),后面七位用来保存unicode 的值。这是一种变长编码方法,即每个字符的编码后所占空间是不同的(下面称作首位编码)。

字符   十六进制     二进制               首位编码
I       49       01001001              11001001
J       4A       01001010              11001010
日      65e5     01101001 11100101     10000001 01010011 01100101
ᅱ       FFD6     11111111 11010110     10000011 01111111 01010110
♀       2640     00100110 01000000     11001100 01000000
♬       266C     00100110 01101100     10010011 00011011

每次解码时,将字符每个字节除去第一位(红色标示)的其他位拼接得到的值作为其unicode 值。但这种方法我能想到的存在问题就是效率低,处理器每次只能一个字节一个字节的处理,读取到第一个字节时并不能知道这个字符占多少个字节,而且没有办法知道中间数据是否发生损坏。而我们常见的UTF-8 却可以很好解决这个问题。

1.4 UTF-8

该UTF-8 出场了,简单地说,UTF-8 是unicode 在计算机中的一种实现方式。和我们上节提到的首位编码类似,也是一种变长编码,每个字符占1-4 个字节。UTF-8 将字节分为数值位和标识位,数值位真正保存字符编码数值标识位表示这个字节是属于哪个字符的、或者该字符占多少个字节。UTF-8 编码方法的:

单字节,首位为标识位0;多字节字符首字节标志位1··10开头,字符占多少字节则有多少1,其他字节标识位10开头;

  • 单字节字符: 0xxxxxxx (以0 开头标志位,数值位用x 表示)
  • 双字节字符: 110xxxxx 10xxxxxx
  • 三字节字符: 1110xxxx 10xxxxxx 10xxxxxx
  • 四字节字符: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

解码时,如果字节首位是0,那么这个字节是个字符;如果字节以i 个1开头,那么这个是一个i 位字符。那么unicode 又是如何填入到UTF-8 的空缺(x)中呢?首先来看看每个多字节UTF-8 编码对应unicode 值的范围:

UTF-8二进制                           unicode二进制
0xxxxxxx                              00-7F
110xxxxx 10xxxxxx                     0080-07FF
1110xxxx 10xxxxxx 10xxxxxx            0800-FFFF
11110xxx 10xxxxxx 10xxxxxx 10xxxxxx   00010000-10FFF

unicode 变为UTF-8 编码非常简单,unicode 二进制按照从低到高,填充UTF-8的数值位,除去那些不真正表示数值的标识位(字节开头的0,10,110,1110和11110),顺序也是由低到高。以汉字“你”为例,看看unicode 如何转换成UTF-8 编码。

>>> (u"你").encode('utf-8')
'\xe4\xbd\xa0'
>>> (u"你")
u'\u4f60'

“你”字unicode 编码为 ‘4f60’ (二进制 ‘01001111 01100000’)。从“你”的unicode 值范围可以看到需要三个字节,接着从低位字节向高位字节填充得到“你”的UTF-8 编码(高位没有填充完则用0补充)。

字符    unicode十六进制   unicode二进制        UTF-8二进制                  UTF-8十六进制
 你        4f60        01001111 01100000   11100100 10111101 10100000    e4bd60

可以看到将UTF-8 用于标记位(红色)的位去掉,合并可以得到原始的unicode 码。

二、文件和终端编码格式

所有的文本文件在计算机中存储的都是一串有限长度的二进制串,只有使用合理的编码方式才能正确地显示文件,但文件本身又是如何告诉编辑器它是如何编码的呢?

2.1 py 文件的字符编码

实际上如果文件本身不申明,编辑器是不知道一个文件所采用的编码方法的。所以编辑器有一个默认的打开方式,比如记事本(notepad)和notepad++ 都默认用ASCII 打开文件。作为Python 初学者可能会遇到下面的一个问题:

故障1:新建一个test.py 文件,用记事本默认打开,输入下面内容:

import os
print "你" 

保存后在终端运行”python test.py” 发现提示错误:

>>python test.py
File "test.py", line 2
SyntaxError: Non-ASCII character '\xc4' in file test.py on line 3, but no encoding 
declared; see http://python.org/dev/peps/pep-0263/ for details

发现提示存在非ASCII 码字符,这是因为在记事本中中文默认使用GB2312编码,”你”的GB2312 编码是”\xc4\xe3″,于是在执行test.py 文件时,出现了无法识别的字符’\xc4’。如果将文件修改为’UTF-8′ 编码时,则可以看到因为”\xc4\xe3″是不合法的字符串,所以显示为它的二进制内容。

utf8save

写过Python 程序的都知道,为了避免py 文件内的编码问题,需要在文件首做一个申明:

#_*_encoding:utf-8_*_

这样,编辑器在开个你这个文件的时候就会默认按照UTF-8 格式打开。当然,UTF-8 也可以换做其他格式。

2.2 python 与文件的字符编码

除了py 文件本身要保存为UTF-8 格式,以避免出现py 文件出现的非ASCII 字符无法被正确的识别。当py 访问其他文件,将数据写入文件时也需要注意字符编码。

故障2:Python2 默认编码是ASCII 码

>>> example = u'你好'
>>> str(example)
Traceback (most recent call last):
File "<pyshell#1>", line 1, in <module>
str(example)
UnicodeEncodeError: 'ascii' codec can't encode characters in position 0-1: 
ordinal not in range(128)
>>> example = u'你好'
>>> open('temp.txt','w').write(example)
Traceback (most recent call last):
File "<pyshell#3>", line 1, in <module>
open('temp.txt','w').write(example)
UnicodeEncodeError: 'ascii' codec can't encode characters in position 0-1: 
ordinal not in range(128)

当用u’字符串’ 的形式申明这个字符串变量时,也就指明了该字符串是使用unicode 字符编码。当如果要将unicode 字符串转换为str 字符串(python2 认为unicode 字符串和str 字符串是不同的)或者写入文件时,python 将默认使用ASCII 码保存数据,而ASCII 码无法识别大于128 的字符,于是报了上面的错误。

类似这样的错误还有:

>>> unicode('abcdef' + chr(255))
Traceback (most recent call last):
...
UnicodeDecodeError: 'ascii' codec can't decode byte 0xff in position 6: 
ordinal not in range(128)

2.3 终端编码

上linux 操作系统课程的时候,我们被教导到:一切都是文件,终端作为一种设备也是文件,当需要输出内容到终端时,实际上也是按照终端对应的字符编码显示相应的内容。

故障3:如果你在windows 终端cmd.exe 运行下面代码(需要安装requests 包)。

import os,sys
import requests
ss = requests.Session()
res = ss.get("http://www.hust.edu.cn/")
con = res.content
print con

这段代码是获取http://www.hust.edu.cn/ 页面的内容,并在终端显示,(如下图)这里出现了乱码。

cmd

但如果你进一步将con 中内容写入到文件或者在linux 下运行这段代码,可能则没有乱码的问题。问题出在哪里呢?原因是因为页面内容是UTF-8 编码(可以在页面源码<meta charset=”utf-8“>中看到 ),而windows 命令提示符cmd 中却使用的是mbcs 字符编码。可以通过下面的命令查看该终端的字符编码

print sys.getfilesystemencoding()

熟悉Linux 的应该知道,终端也是要设置语言格式的,否则在此终端上显示的文件,文件名以及输出到终端的内容会存在乱码。可以通过下面命令设置linux 终端字符编码为UTF-8:

export LC_ALL=en_US.UTF-8
export LANG=en_US.UTF-8
export LANGUAGE=en_US.UTF-8

2.4 str 和unicode

计算机保存的数据,以及从文件中读取的数据都可以理解为str 字符串,str 字符串是需要字符编码才能够被计算机所理解,而unicode 字符串采用统一的字符编码方法。为节省空间等原因计算机并不会直接存储unicode 类型。但在Python2 处理字符数据时,建议全部转化为unicode。

但如果不知道str 字符串编码类型,按照Python2 默认的ASCII 码转换出现大于128 的字节的错误怎么办(UnicodeEncodeError: 'ascii' codec can't encode characters)?

有两种方法:一是用特定的数值(magic number)替代错误的字节;二是干脆忽略错误字节


>>> unicode('\x80abc', errors='replace')
u'\ufffdabc'
>>> unicode('\x80abc', errors='ignore')
u'abc'

同样地,encode() 和decode() 也可以这样使用。

str 字符串和unicode 字符串进行比较,或者合并两个字符串时,首先将它们转换为unicode 格式,再计算它们的值。比如合并str 字符串’你’ 和unicode 字符串u’你’,因为’你’ 按照默认的ASCII 码发现无法解码’你’,于是报错了~~~

>>> '你'+u'你'
Traceback (most recent call last):
 File "<pyshell#0>", line 1, in <module>
 '你'+u'你'
UnicodeDecodeError: 'ascii' codec can't decode byte 0xc4 in position 0: 
ordinal not in range(128)

看下面的例子比较str 和unicode 字符串,python2 按照默认的ASCII 码解码为unicode 过程中发现无法识别的字节,然后就返回不相等(False),并抛出一个异常。

>>> if '你' == u'你':
...    print True
>>> 
>>> '你' == u'你'
__main__:1: UnicodeWarning: Unicode equal comparison failed to convert both argu
ments to Unicode - interpreting them as being unequal
False

正确比较方法应该是:

>>>'你'.decode('gb2312') == u'你':
True
>>> 

如果你在百度或者Google 上搜索解决str 字符串在转码为unicode 时不知道字符编码类型的“问题”时,大部分时候你会看到大家提出在py 文件上加上两句:

reload(sys)
sys.setdefaultencoding('utf-8')

这样py 文件中str 字符串默认以UTF-8 编码。但一位有经验的Python 程序员会告诉你尽量不要这样做,因为这样在对于不是UTF-8 编码的字符时,还是会出现乱码,下节再谈这点。

2.5 _*_encoding:utf-8_*_ 和 reload(sys) sys.setdefaultencoding(‘utf-8’)

有了上面一节的基础,我们大概知道了

#_*_encoding:utf-8_*_

放在py 源代码之前申明,表示py 源文件是UTF-8 编码(即文件中所有的字符都是UTF-8 编码)。这样的好处是如果py 源文件中存在非ASCII 码的字符(你写代码时所输入的UTF-8 字符),python 程序也能够正常的识别为你所输入的字符,而不是按默认为ASCII 码(这样在运行时会抛出无法识别为ASCII 码的错误)。

这种申明文件编码类型是我们推荐的,而下面

reload(sys)
sys.setdefaultencoding('utf-8')

这两句话申明py 文件中所有str 都是UTF-8 编码的,而这种强制定义所有str 字符串为UTF-8 编码是我们不推荐的。比如会遇到下面的问题,在一个测试文件test.py 中有内容:

#_*_encoding:utf-8_*_
import os
import sys
reload(sys)
sys.setdefaultencoding('utf-8')

sym1 =u'♀'+'你'
sym2 = '你'.decode('utf-8').encode('gb2312')
ff = open('temp.txt','w')
ff.write(sym1)
ff.write(sym2)
ff.close()

然后用notepad++打开temp.txt 文件,看到了什么内容呢?

setdefault

不难看出,’♀’ 和’ 你’ 显示都没有问题,但后一个’你’ 就因为使用的是GB2312 编码,写入文件后,前两个字符都是UTF-8 编码,后一个字符GB2312 编码,用UTF-8 格式打开时,最后一个编码肯定就显示不正常了。

当然,上面只是一个例子,很多时候你不会在程序中写出这么buggy 的代码,但是很多时候用python 处理一些非UTF-8 编码的文件或者数据时,就会因为你强制申明str 为UTF-8 编码导致很多问题,比如读取非UTF-8 编码的Oracle 的数据库,修改、添加非UTF-8 编码的文件时,就会产生很多字符编码混乱。因此也有人建议python2 程序员在处理str 时能够显示地使用特定合适的字符编码,而不是默认地使用UTF-8。

Python3 只有unicode 字符串,而没有str 字符串,上面所遇到的字符编码的坑不再有了。

所以—— Bravo~ 学Python3 去吧,骚年!

 

参考文章:

  1. 何世友的日志——立即停止使用setdefaultencoding(‘utf-8’),以及为什么
  2. unicode 编码
  3. Python2 unicode howto

Android 开发笔记(准备工作)

一、开发工具

  • Java 

Android 开发基于Java 语言,所以Java 语言环境必须安装。

  • Android SDK

Android SDK (Software Development Kit) 是开发Android 软件开发包,为开发者提供调用Android API调用,并负责将编译源码。功能类似于传统C++/MFC中开发的库文件加编译器。

从理论上讲,有Java 和Android SDK 就可以开发出结果为apk 的安卓应用了,但在目录、文件管理上比较困难,和其他工具(如模拟器)的扩展也需要手动操作,因此一般开发人员还需要一个开发平台。

  • Android Studio 或者Eclipse 开发平台

开发平台主要功能有三点:1.组织文件和目录;2.自动生成代码;3.扩展其他工具、插件。类似于Visual Studio平台中的管理功能,平台根据类型和作用分目录存放不同文件,比如res 存放静态文件。类似于使用MFC 新建项目时,VS 会自动生成一些通用代码。平台的另外一个好处就是很方便的能够扩展一些工具,比如模拟器,或者是在编译较老的SDK 时,需要从网上下载,平台都能够自动处理。总之,平台好处就是自动化处理一些原本需要人工操作的过程。

  • gradle

linux/C 项目开发中,如果你有了C语言环境(compiler,linker),有了项目所需要的库文件,你还需要通过一定的方法、规则将源文件生成安装程序,这些方法和规则一般写在Makefile 中,不同硬件设备有所区别,所以在安装源码时常通过configure 等脚本生成makefile,最后才make生成最终程序。Android 开发同理,一个Android 项目也需要通过SDK 的一些命令、工具生成中间文件,最后才生成安装程序,而管理这个过程最流行的工具就是gradle。当然不用gradle 也是可以的,只是需要手工敲得命令有些复杂和单调而已。

  • 模拟器(Emulator)

如果你没有真实的设备运行你的Android 程序,模拟器是不错的选择, 但平台中自带的模拟器效率较低,可以考虑其他模拟器,如Genymotion等。

二、安装过程

  1. 安装JDK(Java Development Kit)
  2. 安装Android SDK
  3. 安装Android Studio (下面全部以AS为例,需要VPN支持,或者使用SS并在AS 配置代理)
  4. 安装Android Emulator

三、Android体系结构

Android 基于Linux 操作系统的一个重要原因就是Linux 内核具有良好的硬件设备的支持,比如用于存储的磁盘,用于无线网连接的wifi。通过公共库(Libraries)对底层硬件的封装,为应用框架(Application Framework)和Android Runtime 提供了更具有特色的功能,比如SQLite 提供结构化数据库存储,OpenGL 提供高性能画图等。Android Runtime 基于优化的Java 虚拟机,称作Dalvik Virtuak Machine,任何Android 应用都是运行在这个虚拟机之上,虚拟机可以为应用分配内存和处理进程和进程间通信。应用框架(Application Framework)为程序提供更高层次的工功能服务,比如资源的访问和进程间消息传递等。

anst

四、应用组件

Android 每个应用包含四类组件:

  • Activities        与用户交互
  • Services         与应用有关的后台服务
  • Broadcast Receiver      Android 系统和应用的通信
  • Content Provider       与其他应用的通信

每一个Activity 对应着一块屏幕和一个与用户交互的事件,比如一个Android 邮件应用,有一个activity 是列出所有邮件,一个activity 读邮件,一个activity 写邮件等。所有的activities 都是源自于应用启动时的一个activity,类似于所有函数都是源于main() 函数调用。

一个Service 对应着一个后台持续运行的线程,比如一个后台播放音乐,在比如不中断用户操作的方式从网络上获取数据。

Broadcast Receiver用于回应其他应用或者系统广播的消息。比如一个应用可能发起广播给其他程序某些数据已经下载完毕了,那么Broadcast Receiver 则会截获这则消息并发起相应的动作。

Content Provider 通过请求用于向其他应用提供数据,例如第三方应用请求读取你的通信录。这类请求通过ContentResolver 类处理。一个Content Provider 可以连接多个Content Rsolver。他们关系如下图所示:

Android Training Bangalore

Android 还有其他一些组件,如Manifest 是应用的配置文件,Resources是外部元素,如变量和静态图片等。

五、文件组织结构

以Android Studio 为例,新建一个项目时,会在C:\Users\[your name]\AndroidStudioProjects 下创建你的项目对应的文件夹,而在Android Studio 视图中则有至少manifests、java 和res 三个目录。这三者分别保存配置文件,源代码和资源静态文件。

Screen Shot 2015-11-16 at 10.37.04 PM

  • manifests 目录下有AndroidManifests.xml 文件保存应用的配置信息,它告诉了系统需要哪些资源,以及如何构建起这个应用。
  • java 或src 目录下保存系统的 java 源文件
  • res 保存了用户交互所需要的资源,可能有子文件夹
    • drawable  保存图片
    • layout  保存屏幕布局
    • menu  保存屏幕菜单
    • values 保存为屏幕预定义的值

可能还可能有其他文件夹:

  • gen 是平台IDE 环境在编译时产生的中间文件
  • libs  外部的库文件

六、Android application package (APK) 生成过程

andriod的安装文件.apk如下图所示生成:

apk-structure

  1. .java源文件javac 编译为.class 二进制文件
  2. 项目.class 和其他外部库.class 通过dx编译为classes.dex 二进制可执行文件
  3. aapt 将classes.dex 二进制可执行文件、配置文件AndroidManifest.xml 和Resources 文件打包为apk 文件

知道了这个过程,那么你也可以通过将apk 反编译为xml、资源文件和源码等了。