字元RNA单链--自动机，trie图，可学习算法

justkain

　　字元RNA单链--自动机，trie图，可学习算法
　　字元RNA单链
　　
　　作者：周强
　　
　　本算法基于自动机理论，类似于trie树，因为tried树空间消耗过大，而改用了本数据结构和算法。
　　本算法具有以下特点：
　　1.每个节点都为有效节点，无叶子节点（trie树很多叶子节点占用大量空间）。
　　2.具有编码和解码能力（trie树不具备解码能力）。
　　3.在字元最大容量内，具备节点大小及数量和字元数无关的性质（trie树是节点大小个字元数量直接相关的），
　　4.编码或串匹配时间复杂度最坏O(sum(study_index(S)))，最好O(len(S))
　　S表示串，S表示串中第i个字元，len（）求串长，sum（）求和，study_index()字元学习的序。
　　解码时间复杂度为O(len(S))；
　　5.可具备最近访问最小匹配时间复杂度的能力（可选）。
　　
　　数据结构：
　　typedef struct {
　　unsigned short linker;
　　unsigned short jumper;
　　unsigned short prefix;
　　unsigned char  suffix;
　　unsigned char  bflags;
　　} Base;
　　
　　typedef struct {
　　Base           *base;
　　unsigned short allocs;
　　unsigned short limits;
　　unsigned short header;
　　unsigned short nexter;
　　unsigned short jumper[ELEMENTS];
　　} MRNA;
　　
　　每个Base节点由五个成员，每个节点是一个状态转移函数F（prefix，suffix） = jumper，
　　同时节点的linker指向和本节点具有相同前缀prefix的下一个节点。图示如下：
　　|----------------------------------------------+
　　V                                              |
　　jumper -> linker -----------------------> ...... -------->linker
　　prefix       |----------------+                 prefix
　　suffix       V                |                 suffix
　　jumper -> linker ->......-> linker              jumper
　　prefix            prefix
　　suffix            suffix
　　jumper            jumper
　　bflags成员是个标志，用来设置编码分类或其他用途，由使用者定义。
　　套用生物学概念，Base节点代表一个碱基，对应的MRNA就是一个由很多碱基依次排列构成的大分子。
　　MRNA结构中base是存放base节点的指针，allocs用来记录分配的节点数，limits限制最大节点数
　　，这两个在本文示例中未做使用，header字元的个数，nexter下一个可学习的节点偏移，jumper是串中第一个字元对应的跳转--在base中的偏移。
　　
　　学习原理（编码）：
　　当F(prefix,suffix)转移状态还未定义时，获取一个当前可学习节点，并设置该节点的相关参数，返回该节点的偏移作为状态函数的转移状态，可学习节点后移。
　　如果已经定义，检查prefix和suffix是否和该节点的相等，相等则返回该节点的jumper
　　否则，如果prefix相等说明在相同prefix的链中插入过或还没建立这个节点，需要转入linker链中查找，
　　否则，具有相同prefix的链在下一层中，转入该节点的jumper，然后再jumper到的节点的linker中搜索。
　　
　　解码原理：
　　给出一个编码，由于编码和偏移是线性关系，所以可直接定位其状态转移函数，节点中包含上一个状态prefix和对应的后缀suffix，所以向前回溯能得到串的所有后缀，于是可得到串。
　　
　　
　　一下为26个字母的示例代码：
　　#include <ctype.h>
　　#include <stdio.h>
　　#include <stdlib.h>
　　#include <string.h>
　　typedef struct
　　{
　　unsigned short jumper;
　　unsigned short linker;
　　unsigned short prefix;
　　unsigned char suffix;
　　unsigned char bflags;
　　} BASE;
　　typedef struct
　　{
　　BASE  *base;
　　unsigned short allocs;
　　unsigned short limits;
　　unsigned short  nexter;
　　unsigned short  header;
　　unsigned short jumper[26];
　　} MRNA;
　　#define Cell_Study(R,prefix,suffix) \
　　do { \
　　R->base[R->nexter].prefix = prefix; \
　　R->base[R->nexter].suffix = suffix; \
　　R->base[R->nexter].linker = R->nexter; \
　　R->base[R->nexter].jumper = R->nexter; \
　　return R->header + R->nexter++; \
　　} while(0)
　　int Cell_Prefix(MRNA *h,int prefix,int suffix,int study)
　　{
　　int linker = prefix;
　　unsigned short *jumper = NULL;
　　if(linker < h->header)
　　{
　　if(h->jumper[linker] == 0xFFFF)
　　{
　　if(study)
　　{
　　h->jumper[linker] = h->nexter;
　　Cell_Study(h,prefix,suffix);
　　}
　　return -1;
　　}
　　else
　　{
　　linker = h->jumper[linker];
　　}
　　}
　　else
　　{
　　linker -= h->header;
　　}
　　while(linker < h->nexter)
　　{
　　if(h->base[linker].suffix == suffix &&
　　h->base[linker].prefix == prefix )
　　{
　　return h->header + linker;
　　}
　　if(h->base[linker].prefix == prefix)
　　{
　　if(h->base[linker].linker == linker)
　　{
　　if(study)
　　{
　　h->base[linker].linker = h->nexter;
　　Cell_Study(h,prefix,suffix);
　　}
　　return -1;
　　}
　　linker = h->base[linker].linker;
　　}
　　else
　　{
　　if(h->base[linker].jumper == linker)
　　{
　　if(study)
　　{
　　h->base[linker].jumper = h->nexter;
　　Cell_Study(h,prefix,suffix);
　　}
　　return -1;
　　}
　　linker = h->base[linker].jumper;
　　}
　　}
　　return -1;
　　}
　　int Cell_Prefix_(MRNA *h,int prefix,int suffix)
　　{
　　int linker = prefix;
　　int jumper = linker;
　　if(linker < h->header)
　　{
　　if(h->jumper[linker] == 0xFFFF)
　　{
　　h->jumper[linker] = h->nexter;
　　h->base[h->nexter].prefix = prefix;
　　h->base[h->nexter].suffix = suffix;
　　h->base[h->nexter].linker = h->nexter;
　　h->base[h->nexter].jumper = h->nexter;
　　return h->header + h->nexter++;
　　}
　　else
　　{
　　linker = h->jumper[linker];
　　}
　　}
　　else
　　{
　　linker -= h->header;
　　}
　　jumper = linker;
　　while(linker < h->nexter)
　　{
　　if(h->base[linker].suffix == suffix &&
　　h->base[linker].prefix == prefix )
　　{
　　if(prefix < h->header)
　　h->jumper[prefix] = linker;
　　else
　　h->base[jumper].jumper = linker;
　　return h->header + linker;
　　}
　　if(h->base[linker].prefix == prefix)
　　{
　　if(h->base[linker].linker == jumper)
　　{
　　h->base[linker].linker = h->nexter;
　　
　　h->base[h->nexter].prefix = prefix;
　　h->base[h->nexter].suffix = suffix;
　　h->base[h->nexter].linker = jumper;
　　h->base[h->nexter].jumper = h->nexter;
　　if(prefix < h->header)
　　h->jumper[prefix] = h->nexter;
　　else
　　h->base[jumper].jumper = h->nexter;
　　return h->header + h->nexter++;
　　}
　　linker = h->base[linker].linker;
　　}
　　else
　　{
　　if(h->base[linker].jumper == linker)
　　{
　　h->base[linker].jumper = h->nexter;
　　
　　h->base[h->nexter].prefix = prefix;
　　h->base[h->nexter].suffix = suffix;
　　h->base[h->nexter].linker = h->nexter;
　　h->base[h->nexter].jumper = h->nexter;
　　return h->header + h->nexter++;
　　}
　　jumper = linker = h->base[linker].jumper;
　　}
　　}
　　printf("bugs:this branch can't be reached\n");
　　return -1;
　　}
　　int Cell_Suffix(MRNA *h,int prefix)
　　{
　　while(prefix >= h->header)
　　{
　　prefix -= h->header;
　　printf("%c",h->base[prefix].suffix + 'A');
　　prefix = h->base[prefix].prefix;
　　}
　　printf("%c",prefix + 'A');
　　return 0;
　　}
　　int main(int argc,char *argv[])
　　{
　　MRNA mRNA;
　　int suffix;
　　int prefix = -1;
　　mRNA.nexter = 0;
　　mRNA.header = 26;
　　mRNA.limits = 4096;
　　mRNA.allocs = 4096;
　　memset(mRNA.jumper,0xFF,mRNA.header * 2);
　　mRNA.base = malloc(mRNA.allocs * sizeof(BASE));
　　while(suffix = getchar())
　　{
　　if(isalpha(suffix))
　　{
　　suffix = toupper(suffix) - 'A';
　　if(prefix != -1)
　　{
　　printf("f(%d,%d)",prefix,suffix);
　　prefix = Cell_Prefix_(&mRNA,prefix,suffix);
　　printf("=%d\n",prefix);
　　}
　　else
　　{
　　prefix = suffix;
　　}
　　}
　　else
　　{
　　if(prefix != -1)
　　{
　　Cell_Suffix(&mRNA,prefix);
　　printf("<==>%d\n",prefix);
　　prefix = -1;
　　}
　　if(suffix == '#') break;
　　}
　　}
　　printf("Atoms = %d\n",mRNA.nexter);
　　free(mRNA.base);
　　return 0;
　　}
　　
　　Cell_Prefix为工作函数，学习和匹配都是这个函数负则，study = 0是就禁止了学习
　　Cell_Prefix_是改进为最近访问过的串匹配时间复杂度最小的工作函数。
　　Cell_Suffix是解码函数，给出对应编码的串的倒序。
　　Cell_Study是个宏，用于学习，也就是添加新节点。
　　
　　注意：示例程序分配了4096个节点，但未做溢出检查，示例数据量过大可能溢出，造成程序段错误。