BW BW

Size: px

Start display at page:

Download "BW BW"

あやかいちぬの
6 years ago
Views:

1 Induced Sorting BW 11T2042B

2 BW BW Induced Sorting BW Induced Sorting A 20 A.1 BW () A.2 BW () i

3 1 1.1 BW BW (BWT Burrows-Wheeler Transform) M. Burrows and D. J. Wheeler 1994 [1] Block-sorting BW BW BW Move-to-front coding( ) [1] BW BW M. Burrows [1] Induced Sorting BW [2] 3 Induced Sorting [3] BW 3 BW Induced Sorting BW BW BW BW 1

4 2.1 S N 1. S N N M M[0, 0],..., M[0, N 1] S[0],..., S[N 1] M[1, 0],..., M[1, N 2], M[1, N 1] S[1],..., S[N 1], S[0] 2. M 3. M L L[0],..., L[N 1] M[N 1, 0],..., M[N 1, N 1] 4. M S I S (L, I) S =shinshu BW (L, I) = (sshiunh,4) ( 1) M 0 s h i n s h u 1 h i n s h u s 2 i n s h u s h 3 n s h u s h i 4 s h u s h i n 5 h u s h i n s 6 u s h i n s h 1 = BW M 0 h i n s h u s 1 h u s h i n s 2 i n s h u s h 3 n s h u s h i 4 s h i n s h u 5 s h u s h i n 6 u s h i n s h (L, I) = (sshiunh,4) (L, I) S BW 1. L F M F M M i F[i] L[i] S () 2

5 2. L F L F [1] 3. (L, I) S L[I] L[I] S L[i] F F [C[i]] S[N 1] = L[I] = F [C[I]], F [C[I]] L[C[I]] S[N 2] = L[C[I]] = F [C[C[I]]],... ( 2) L = s 1 s 2 h 1 i u n h 2 F = h 1 h 2 i n s 1 s 2 u 2 u h h s... S =shinshu ( ) 2.2 BW BW he t M he t he t k BW BW ASCII BW 2.3 BW N N 2 N 3

6 S M i j S S[i] S[i + N 1 mod N] S[j] S[j + N 1 mod N] O(N log N) ( S =aaa... ) 2 N O(N 2 log N) N 3 Induced Sorting BW [2] Induced Sorting O(N) Ge Nong 2011 [3] BW Induced Sorting 3.1 BW S i S suf(s, i) 3 $ $ N Induced Sorting $ suf(s, i) S i suf(s, i) 0,..., N 1 N log N SA S[SA[i]] 2 M[i][0] 4

7 suf 0 s h i n s h u $ 1 h i n s h u $ 2 i n s h u $ 3 n s h u $ 4 s h u $ 5 h u $ 6 u $ 7 $ 3 = 7 $ suf 1 h i n s h u $ 5 h u $ 2 i n s h u $ 3 n s h u $ 0 s h i n s h u $ 4 s h u $ 6 u $ SA = ( ) BW L[i] = { S[SA[i] 1] i 0 S[N 1] i = Induced Sorting Induced Sorting 1 Type-S: suf(s, i) < suf(s, i + 1) suf(s, N 1) = $ Type-L: suf(s, i) > suf(s, i + 1) S =shinshu$ suf(s, 0) = shinshu$ > suf(s, 1) = hinshu$ suf(s, 0) Type-L suf(s, i) S[i] suf(s, i) 4 S suf(s, N 1) Type-S suf(s, i) Type-S 5

8 1. S[i] < S(i + 1) 2. S[i] = S(i + 1) suf(s, i + 1) Type-S suf(s, i) Type-L 1. S[i] > S(i + 1) 2. S[i] = S(i + 1) suf(s, i + 1) Type-L 2 Type-S suf(s, i) Type-L suf(s, j) suf(s, j) S[i] = S[j] suf(s, i) > suf(s, j) suf(s, i) suf(s, j) S[i] = S[j] = c 2 2 suf(s, i + 1) suf(s, j + 1) suf(s, i) Type-S suf(s, i) < suf(s, i + 1) suf(s, i + 1) c c 1 c suf(s, j) Type-L suf(s, j) > suf(s, j + 1) suf(s, j + 1) c c 1 c suf(s, i + 1) > suf(s, j + 1) suf(s, i) > suf(s, j) c c Type-L Type-S Type-S 3 Type-S suf(s, i) suf(s, i 1) Type-L Type- S* Type-S Type-L Type- S* Type-S ( 4) Induced Sorting Step0 : Step1 :Type-S* Step2 :Type-S* Type-L 6

9 i S[i] s h i n s h u $ Type L S* S S L S* L S* 4 Step3 :Type-L Type-S N O(N) Step1 Step2 Step1 5 Step2 Step Step2:Type-L Type-S* Type-L S $ σ bkt[c] S c σ bkt bkt[0] bkt[c 1] bkt[0] bkt[c] Type-S* SA 1 Step1 5 Step1 Type-S* SA SA SA[i] n i suf(s, n i ) suf(s, n i 1) Type-L 2 suf(s, n i 1) S[n i 1] suf(s, n i 1) S[n i 1] 5 SA SA[0] suf(s, 11) suf(s, 11 1) = suf(s, 10) L S[10] = v suf(s, 10) SA 0 suf(s, n i 1) Type S Type-L suf(s, n i 1) Type-L 5?! SA Type-L SA 7

10 O(N) Step3:Type-S Step2 Type-L Type-S Step2 SA suf(s, n i ) suf(s, n i 1) Type-S 2 suf(s, n i 1) S[n i 1] suf(s, n i 1) S[n i 1] SA Type-S suf(s, n i 1) Type-S Step3 Type-S Step2 Type-S* SA Type-S SA O(N) Step1 :Type-S* Step1 Type-S* O(N) Step1 Type-S* Induced Sorting O(N) Type-S* 4 S S* S[i] S[j] Type-S* Type-S* S[i... j] $ 5 S* S s1 s1 SA1 S =shinshuuniv$ S* hinsh, huuni, iv$, $ 4 S* 1, 2, 3, 0 s1 s1 = 1230 S* Type-S* S* 8

11 i S[i] s h i n s h u u n i v $ Step0 Type L S S S L S L L L S L S S* * * * * $ h i n s u v Step1 SA[i] Step2 SA[i] ?! ?! ?! ??! ?! ????! ?? Step3 SA[i] !? !? !?? !?? !??? ??? 5 Induced Sorting 9

12 4 S $ S* S* s1 0 s1 n1 6 s1 S n1 N/2 Type-S* 1. S Type-S* SA Type-S* SA S 2. Step2 Type-L 3. Step3 Type-S SA S* 4. s1 s1 5. S* SA Step2 6. s1 1 O(N) 6 1/2 O(N) Induced Sorting O(N) Induced Sorting BW Induced Sorting O(N log N) N log σ O(N 2 ) N S 1 1 N N/4 10

13 6 Induced Sorting S N = N/8 Type-L 0 Type-S 1 Type-S* /2 N/8 N/4 SA N 1 N log N SA ( 7) 11

14 1 S S[0] S[N] SA SA[0] Type-S* SA[N] SA SA[0] S* 1 s1[n1] 2 s1 SA[N n1] s1[n1] s1 SA (SA[0] SA[n1 1]) SA1 SA[0] SA1[n1]( ) SA1 SA[0] 1 s2[n2] 3 s2 SA[n1 n2] s2 SA2 SA[0] SA2( ) SA2[0] SA2[n2 1] s2 S* SA2 SA[0] 1 s3 : s2 S* SA2 SA2 SA[0] SA2( ) SA2 : s1 S* s1 S* SA1 2 SA1 SA[0] SA1( ) s S* SA 1 SA SA[0] SA[N] 7 (3 ) SA () bkt S σ N log σ σ bkt Induced Sorting BW BW L N 12

15 3.3 Induced Sorting Ge Nong [3] [4] BW 1 Induced Sorting 00 FF bkt c bkt[c + 1] bkt[0] SA N log N 8 1 BW BW Induced Sorting Calgary Corpus [5] 13

16 1 S S[0] S[N] SA SA[0] Type-S* SA[N] SA SA [0] S* 1 s1[n1] 2 s1 SA [N n1] s1[n1] SA1 SA[0] SA1[n1]( ) SA1 SA [0] 1 s2[n2] 3 s2 SA [n1 n2] s2 SA2 SA[0] SA2( ) SA2 SA [0] 1 s3 : 2 SA1 SA[0] SA1( ) SA2 SA1 1 SA SA[0] SA[N] 8 (3 ) 4.1 Calgary Corpus [5] 18 Induced Sorting BW Induced Sorting O(N)

17 1 2 = 100[%] book1( ), obj2(), pic() (book1) 10 - (book1) 11 - (obj2) 12 - (obj2) - book , obj , pic pic Calgary Corpus ( ) pic pic 87.1[%] 00 15

18 13 - (pic) 14 - (pic) Induced Sorting Type-S* - obj2 0[%] 0.27[%] book1 pic 1 N book1 N = obj2 6 pic N = N = book pic pic 4 5 N = ( 4) 0.23[%] N ( 5) 0.056[%] book ( 15 18) 16

19 15 - ( 3) 16 - ( 4) 17 - ( 5) 18 - ( 6) 19-17

20 ( ) obj [µs] 344[µs] 2 1[µs] 0.29[%] - ( 19) [%] 5 Induced Sorting BW Induced Sorting Induced Sorting Induced Sorting Induced Sorting O(N) [1] M. Burrows and D. J. Wheeler, A Block-sorting Lossless Data Compression Algorithm, SRC Research Report 124, Digital Systems Research Center, [2] [3] Ge Nong, Sen Zhang, and Wai Hong Chan, Two Efficient Algorithms for Linear Time 18

21 Suffix Array Construction, IEEE Trans. on Computers, vol. 60, no.10, pp , Oct [4] 20Efficient%20Algorithms%20for%20Linear%20Time%20Suffix%20Array% 20Construction.pdf&can=2&q=, [5] Archive Comparison Test,

22 A A.1 BW () #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> unsigned char mask[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 }; // t[i] #define tget(i) ( (t[(i)/8]&mask[(i)%8])? 1 : 0 ) // (Type-L 0,Type-S 1) #define tset(i, b) t[(i)/8]=(b)? (mask[(i) % 8] t[(i) / 8]): ((~mask[(i) % 8])&t[(i) / 8]) #define chr(i) (cs==sizeof(int)? ((int*)s)[i]: ((unsigned char *)s)[i]) #define islms(i) (i>0 && tget(i) &&!tget(i-1)) // void getbuckets(unsigned char *s, int *bkt, int n, int K, int cs, bool end) { int i, sum = 0; // for (i = 0; i <= K; i++){ bkt[i] = 0; // c bkt[c+1] (bkt[0] $ 1 ) for (i = 0; i < n - 1; i++){ bkt[chr(i) + 1]++; bkt[0] = 1; // (end = false) bkt[i] bkt[0],...,bkt[i-1] // (end = true) bkt[i] bkt[0],...,bkt[i] // c bkt[c+1] bkt[c+1]-1 for (i = 0; i <= K; i++){ sum += bkt[i]; bkt[i] = end? sum : sum - bkt[i]; } // Type-L void inducesal(unsigned char *t, int *SA, unsigned char *s, int *bkt, int n, int K, int cs, bool end) { int i, j; // getbuckets(s, bkt, n, K, cs, end); for (i = 0; i < n; i++) { j = SA[i] - 1; if (j >= 0 &&!tget(j)){ SA[bkt[chr(j) + 1]++] = j; } // Type-S void inducesas(unsigned char *t, int *SA, unsigned char *s, int *bkt, int n, int K, int cs, bool end) { int i, j; // getbuckets(s, bkt, n, K, cs, end); for (i = n - 1; i >= 0; i--) { j = SA[i] - 1; if (j >= 0 && tget(j)){ SA[--bkt[chr(j) + 1]] = j; } // K ( $ ) n s SA (Induced Sorting) // s[n-1]=0 ( $ ) n>=2 20

23 void SA_IS(unsigned char *s, int *SA, int n, int K, int cs, int* depth) { // 1 unsigned char *t = (unsigned char *)malloc(n / 8 + 1); if (*t == NULL){ printf(" (%d)\n", LINE ); return; int i, j; // tset(n - 2, 0); // $ Type-L tset(n - 1, 1); // $ Type-S for (i = n - 3; i >= 0; i--){ tset(i, (chr(i) < chr(i + 1) (chr(i) == chr(i + 1) && tget(i + 1) == 1))? 1 : 0); // s1 // int *bkt = (int *)malloc(sizeof(int)*(k + 1)); if (*bkt == NULL){ printf(" (%d)\n", LINE ); return; // getbuckets(s, bkt, n, K, cs, true); // SA -1 for (i = 0; i < n; i++){ SA[i] = -1; // $ n-1 SA[--bkt[chr(n - 1)]] = n - 1; // s[i] Type-S* s[i] i for (i = 1; i < n - 2; i++){ if (islms(i)){ SA[--bkt[chr(i) + 1]] = i; // Type-L Type-S inducesal(t, SA, s, bkt, n, K, cs, false); inducesas(t, SA, s, bkt, n, K, cs, true); free(bkt); // SA n1 Type-S* // n1 n int n1 = 0; for (i = 0; i < n; i++){ if (islms(sa[i])){ SA[n1++] = SA[i]; // S* // SA[n1],...,SA[n-1] for (i = n1; i < n; i++){ SA[i] = -1; // S* int name = 0, prev = -1; for (i = 0; i < n1; i++) { int pos = SA[i]; bool diff = false; // S[pos] S[prev] for (int d = 0; d<n; d++){ // 2 S* if (prev == -1 chr(pos + d)!= chr(prev + d) tget(pos + d)!= tget(prev + d)){ diff = true; break; // d s[pos+d]=s[prev+d] Type-S* // 2 S* else if (d>0 && (islms(pos + d) islms(prev + d))){ break; 21

24 // 2 S* ( ) // name S* if (diff) { name++; prev = pos; // SA[n1] SA[n-1] S* s pos = (pos % 2 == 0)? pos / 2 : (pos - 1) / 2; SA[n1 + pos] = name - 1; // S* SA[n-1-n1] SA[n-1] s1 for (i = n - 1, j = n - 1; i >= n1; i--){ if (SA[i] >= 0) SA[j--] = SA[i]; // // s1 int *SA1 = SA, *s1 = SA + n - n1; // name n1 if (name < n1){ *depth += 1; SA_IS((unsigned char*)s1, SA1, n1, name, sizeof(int), depth); // name n1 S*s1 else { for (i = 0; i < n1; i++){ SA1[s1[i]] = i; // s1 s SA // bkt = (int *)malloc(sizeof(int)*(k + 1)); if (*bkt == NULL){ printf(" (%d)\n", LINE ); return; // Type-S* // getbuckets(s, bkt, n, K, cs, true); // s1 S* s for (i = 1, j = 0; i < n; i++){ if (islms(i)){ s1[j++] = i; // s1 s s S* s S* for (i = 0; i < n1; i++){ SA1[i] = s1[sa1[i]]; // SA for (i = n1; i < n; i++){ SA[i] = -1; // S* for (i = n1-1; i >= 0; i--) { j = SA[i]; SA[i] = -1; if (i == 0){ SA[--bkt[chr(j)]] = j; else{ SA[--bkt[chr(j) + 1]] = j; // Type-S*Type-L Type-S inducesal(t, SA, s, bkt, n, K, cs, false); inducesas(t, SA, s, bkt, n, K, cs, true); 22

25 free(bkt); free(t); } // ( BW ) // int main(int argc, char *argv[]){ int size = atoi(argv[2]); // BW unsigned char* s = (unsigned char*)malloc(size); int* sa = (int*)malloc(sizeof(int)*size); unsigned char* L = (unsigned char*)malloc(size); if ((s == NULL) (sa == NULL) (L == NULL)){ printf(" (%d)\n", LINE ); return 0; int dep; int I; // size-1 $ FILE *fp = fopen(argv[1], "rb"); if (fp == NULL){ printf("open error\n"); return -1; if (fread(s, sizeof(char), size - 1, fp) < size - 1){ printf("size error\n"); return -1; fclose(fp); s[size - 1] = \0 ; // Induced Sorting s dep = 1; SA_IS(s, sa, size, 256, sizeof(char), &dep); // s BW L I int i; for (i = 0; i < size; i++){ if (sa[i] == 0){ L[i] = s[size - 1]; I = i; else{ L[i] = s[sa[i] - 1]; /* printf("\n SA =\n"); for (i = 0; i < size; i++){ printf("%d ", SA[i]); printf("\n"); printf("\n L =\n"); for (i = 0; i < size; i++){ printf("%02x ", L[i]); printf("\n"); */ /* FILE *fp1 = fopen("outsa1.txt", "wb"); if (fp1 == NULL){ printf("open error\n"); return -1; fwrite(sa, sizeof(char), size, fp1); fclose(fp1); */ 23

26 FILE *fp2 = fopen("outl.txt", "wb"); if (fp2 == NULL){ printf("open error\n"); return -1; fwrite(l, sizeof(char), size, fp2); fclose(fp2); FILE *fp3 = fopen("outi.txt", "wt"); if (fp3 == NULL){ printf("open error\n"); return -1; fprintf(fp3, "%d", I); fclose(fp3); free(s); free(sa); free(l); return 0; } A.2 BW () #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> unsigned char mask[] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 }; #define tget(i) ( (t[(i)/8]&mask[(i)%8])? 1 : 0 ) #define tset(i, b) t[(i)/8]=(b)? (mask[(i) % 8] t[(i) / 8]): ((~mask[(i) % 8])&t[(i) / 8]) #define chr(i) (cs==sizeof(int)? ((int*)s)[i]: ((unsigned char *)s)[i]) #define islms(i) (i>0 && tget(i) &&!tget(i-1)) // void getbuckets(unsigned char *s, int *bkt, int n, int K, int cs, bool end) { int i, sum = 0; for (i = 0; i <= K; i++){ bkt[i] = 0; for (i = 0; i < n - 1; i++){ bkt[chr(i) + 1]++; bkt[0] = 1; for (i = 0; i <= K; i++){ sum += bkt[i]; bkt[i] = end? sum : sum - bkt[i]; } // Type-L void inducesal(unsigned char *t, int *SA, unsigned char *s, int *bkt, int n, int K, int cs, bool end) { int i, j; getbuckets(s, bkt, n, K, cs, end); for (i = 0; i < n; i++) { j = SA[i] - 1; if (j >= 0 &&!tget(j)){ SA[bkt[chr(j) + 1]++] = j; } // Type-S void inducesas(unsigned char *t, int *SA, unsigned char *s, int *bkt, int n, int K, int cs, bool end) { int i, j; getbuckets(s, bkt, n, K, cs, end); for (i = n - 1; i >= 0; i--) { 24

27 j = SA[i] - 1; if (j >= 0 && tget(j)){ SA[--bkt[chr(j) + 1]] = j; } // s SA (Induced Sorting) void SA_IS(unsigned char *s, int *SA,int *SAC, int n, int K, int cs, bool *bottom, int *depth) { unsigned char *t = (unsigned char *)malloc(n / 8 + 1); if (*t == NULL){ printf(" (%d)\n", LINE ); return; int i, j; tset(n - 2, 0); tset(n - 1, 1); for (i = n - 3; i >= 0; i--){ tset(i, (chr(i) < chr(i + 1) (chr(i) == chr(i + 1) && tget(i + 1) == 1))? 1 : 0); // s1 int *bkt = (int *)malloc(sizeof(int)*(k + 1)); if (*bkt == NULL){ printf(" (%d)\n", LINE ); return; getbuckets(s, bkt, n, K, cs, true); for (i = 0; i < n; i++){ SA[i] = -1; SA[--bkt[chr(n - 1)]] = n - 1; for (i = 1; i < n - 2; i++){ if (islms(i)) SA[--bkt[chr(i) + 1]] = i; inducesal(t, SA, s, bkt, n, K, cs, false); inducesas(t, SA, s, bkt, n, K, cs, true); free(bkt); // Type-S* SAC n1 int n1 = 0; for (i = 0; i < n; i++){ if (islms(sa[i])) SAC[n1++] = SA[i]; for (i = n1; i < n; i++){ SAC[i] = -1; // SAC[n-1-n1] SAC[n-1] s1 int name = 0, prev = -1; for (i = 0; i < n1; i++) { int pos = SAC[i]; bool diff = false; for (int d = 0; d<n; d++){ if (prev == -1 chr(pos + d)!= chr(prev + d) tget(pos + d)!= tget(prev + d)){ diff = true; break; else if (d>0 && (islms(pos + d) islms(prev + d))){ break; if (diff) { name++; prev = pos; pos = (pos % 2 == 0)? pos / 2 : (pos - 1) / 2; SAC[n1 + pos] = name - 1; for (i = n - 1, j = n - 1; i >= n1; i--){ if (SAC[i] >= 0){ SAC[j--] = SAC[i]; 25

28 // // SA Type-S* int *SA1 = SA, *s1 = SAC + n - n1, *SAC1 = SAC; if (name < n1){ *depth += 1; SA_IS((unsigned char*)s1, SA1, SAC1, n1, name, sizeof(int), bottom, depth); // s1 s SA bkt = (int *)malloc(sizeof(int)*(k + 1)); if (*bkt == NULL){ printf(" (%d)\n", LINE ); return; // S* if (!*bottom){ getbuckets(s, bkt, n, K, cs, true); for (i = 1, j = 0; i < n; i++){ if (islms(i)) s1[j++] = i; for (i = 0; i < n1; i++){ SA1[i] = s1[sa1[i]]; for (i = n1; i < n; i++){ SA[i] = -1; for (i = n1-1; i >= 0; i--) { j = SA[i]; SA[i] = -1; if (i == 0){ SA[--bkt[chr(j)]] = j; else{ SA[--bkt[chr(j) + 1]] = j; inducesal(t, SA, s, bkt, n, K, cs, false); // Type-S(S* ) if (!*bottom){ inducesas(t, SA, s, bkt, n, K, cs, true); else{ *bottom = false; free(bkt); free(t); } // ( BW ) int main(int argc,char *argv[]){ int size = atoi(argv[2]); unsigned char* s = (unsigned char*)malloc(size); // SA SAC int* sa = (int*)malloc(sizeof(int)*size * 2); int* sac = sa + size; unsigned char* L = (unsigned char*)malloc(size); if ((s == NULL) (sa == NULL) (L == NULL)){ printf(" (%d)\n", LINE ); return 0; bool btm; int dep; int I = 0; FILE *fp = fopen(argv[1], "rb"); if (fp == NULL){ 26

29 printf("open error\n"); return -1; if (fread(s, sizeof(char), size - 1, fp) < size - 1){ printf("size error\n"); return -1; fclose(fp); s[size - 1] = \0 ; // Induced Sorting s btm = true; dep = 1; SA_IS(s, sa, sac, size, 256, sizeof(char), &btm, &dep); // s BW L I int i; for (i = 0; i < size; i++){ if (sa[i] == 0){ L[i] = s[size - 1]; I = i; else{ L[i] = s[sa[i] - 1]; /* printf("\n SA =\n"); for (i = 0; i < size; i++){ printf("%d ", SA[i]); printf("\n"); printf("\n L =\n"); for (i = 0; i < size; i++){ printf("%02x ", L[i]); printf("\n"); */ /* FILE *fp1 = fopen("outsa2.txt", "wb"); if (fp1 == NULL){ printf("open error\n"); return -1; fwrite(sa, sizeof(char), size, fp1); fclose(fp1); */ FILE *fp2 = fopen("outl.txt", "wb"); if (fp2 == NULL){ printf("open error\n"); return -1; fwrite(l, sizeof(char), size, fp2); fclose(fp2); FILE *fp3 = fopen("outi.txt", "wt"); if (fp3 == NULL){ printf("open error\n"); return -1; fprintf(fp3, "%d", I); fclose(fp3); free(s); free(sa); free(l); return 0; } 27

スライド 1

スライド 1 参考論文 :Nong, Zhang, and Chan. Two Efficient Algorithms for Linear Suffix Array Construction. (009) Appendix のプログラムの解説プログラムを Microsoft Visual C++ の環境で動かす際の注意点先頭で使いそうなライブラリを指定 #include #include