norm2lzw(vector)

function [output,table] = norm2lzw(vector)
%NORM2LZW   LZW Data Compression (encoder)
%   For vectors, NORM2LZW(X) is the compressed vector of X using the LZW algorithm.
%   [...,T] = NORM2LZW(X) returns also the table that the algorithm produces.
%
%   For matrices, X(:) is used as input.
%
%   Input must be of uint8 type, while the output is a uint16.
%   Table is a cell array, each element containig the corresponding code.
%
%   This is an implementation of the algorithm presented in the article
%   http://www.dogma.net/markn/articles/lzw/lzw.htm
%
%   See also LZW2NORM


%   $Author: Giuseppe Ridino' $
%   $Revision: 1.0 $  $Date: 10-May-2004 14:16:08 $
%
%   Revision:
%       Change the code table structure to improve the performance. 
%       date: 22-Apr-2007
%       by:   Haiyong Xu ([e-mail])
%       

% How it encodes:
%
% STRING = get input character
% WHILE there are still input characters DO
%     CHARACTER = get input character
%     IF STRING+CHARACTER is in the string table then
%         STRING = STRING+character
%     ELSE
%         output the code for STRING
%         add STRING+CHARACTER to the string table
%         STRING = CHARACTER
%     END of IF
% END of WHILE
% output the code for STRING


% ensure to handle uint8 input vector
if ~isa(vector,'uint8'),
	error('input argument must be a uint8 vector')
end

% vector as double row
vector = double(vector(:)');

table = double(0:255)';
global APPENDING;
APPENDING = -1;

% initialize output
output = vector;

% main loop
outputindex = 1;
startindex = 1;
for index=2:length(vector),
    if mod(index, 1000) == 0
        index
        size(table)
    end
	element = vector(index);
	substr = vector(startindex:(index-1));
	code = getcodefor([substr element],table);
	if isempty(code),
		% add it to the table
		output(outputindex) = getcodefor(substr,table);
		[table,code] = addcode(table,[substr element]);
		outputindex = outputindex+1;
		startindex = index;
	else,
		% go on looping
	end
end

substr = vector(startindex:index);
output(outputindex) = getcodefor(substr,table);

% remove not used positions
output((outputindex+1):end) = [];


%%
function code = getcodefor(substr,table)
global APPENDING;

code = double([]);
if length(substr)==1,
	code = substr;
else
    x = size(substr, 2);
    [m, y] = size(table);
    if x < y
        substr = [substr, APPENDING * ones(1, y - x)];
    elseif x > y
        return;
    end
    
    % find which row in codetable equals substr
    x = table - repmat(substr, [m, 1]);
    index = find(sum(abs(x), 2) == 0);
    if numel(index) == 1
        code = index - 1;
    end
end


%%
function [table,code] = addcode(table,substr)
global APPENDING;

x = size(substr, 2);
[code, y] = size(table);
if x > y
    table = [table, repmat(APPENDING * ones(1, x - y), [code, 1])];
elseif x < y
    substr = [substr, APPENDING * ones(1, y - x)];
end

table = [table; substr];