Lempel-Ziv algorithm realization

Lempel-Ziv 复杂度程序

随着人们对非线性方法的分析越加深入，他们发现，虽然关联维度和最大李雅谱诺夫指数在分析脑电时具有一定的帮助，但是它们对数据的依赖性太强，对干扰和噪 声太敏感，而且要得到可靠的结果需要大量的数据，这对于高度不平稳的脑电波来说无疑是相当大的局限。科研人员迫切需要一种数据量少且具有一定抗干扰能力的 方法，这时LZ复杂度算法应运而生，它是一种表征时间序列里出现新模式的速率的方法。这个方法最先由Lempel和Ziv提出，因此取名为Lempel- Ziv复杂度。直到1987年，才由Kaspar和Schuster提出了该算法的计算机实现方法。

对于一个待求字符串S(S1，S2，…，Sn)以及另一个字符串Q(q1，q2，…，qn)，SQ表示S和Q的级联，SQ=( S1，S2，…，Sn，q1，q2，…，qn)。令SQv是SQ减去最后一个字符所得字符串。判断Q是否是SQv的一个子串，如果Q是SQv的一个子串，说明Q中的字符是可从S复制的，这时把待求序列的下一个字符级联到Q。如果Q不是SQv的一个子串，则表示Q是插入字符。这时把Q级联到S，S=SQ，重新构造Q，重复以上过程直到Q取待求序列的最后一位结束。每次Q级联到S，表明出现一种新模式，用c表示一个字符串中新模式的数量。例如对于S=(10101010)，应用上面的方法可以得到c(8)=3个新模式：1，0 ，101010。

具体的Matlab程序如下：

function BinaryData = DataBinarization( data )

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%    DataBinarization:     数据二值化处理

%    AUTHOR : Andy Wu

%    DATE:     2010/05/01

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

MeanData = median(data);

[l,c] = size(data);

BinaryData(1:l,1:c) = '0';

for i=1:c

   Tno =  data(:,i) > MeanData(i) ;

   BinaryData(Tno,i) = '1';

end

return;

function [lzc]=ComplexityCompute(x)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%  计算一维信号的复杂度

%  x:  the signal is vector

%  lzc:  the complexity of the signal

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%模式初始值

c = 1;

%S Q SQ初始化

S = x(1);Q = [];SQ = [];

for i=2:length(x)

   Q = strcat(Q,x(i));

   SQ = strcat(S,Q);

   SQv = SQ(1:length(SQ)-1);

   if isempty(findstr(SQv,Q))   %如果Q不是SQv中的子串，说明Q是新出现的模式，执行c 加1操作

       S = SQ;

       Q = [];

       c = c+1;

   end

end

b = length(x)/log2(length(x));

lzc = c/b;

return;