§ Pattern Matching

ref : http://www-igm.univ-mlv.fr/~lecroq/string/

1. Brute Force (BF)

x : pattern
y : input
m : size of pattern
n : size of input
O( nm )

#include <stdio.h>
#include <string.h>

#define OUTPUT(x)    printf("%d\n", x )
void BF(char *x, int m, char *y, int n) {
	int i, j;

	/* Searching */
	for (j = 0; j <= n - m; ++j) {
		for (i = 0; i < m && x[i] == y[i + j]; ++i);
		if (i >= m)
			OUTPUT(j);
	}
}

int main()
{
	char y[] = "how are you hello world hello";
	char x[] = "hello";

	BF( x, strlen(x), y, strlen(y) );
	return 0;
}

2. Karp-Rabin (KR)

data structure : hash
hash를 이용하면서도 rehash macro를 구현하여 for loop 를 사용하지 않도록 한다.

#include <stdio.h>
#include <string.h>

#define OUTPUT(x)    printf("%d\n", x )
#define REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b))

void KR(char *x, int m, char *y, int n) {
	int d, hx, hy, i, j;

	/* Preprocessing */
	/* computes d = 2^(m-1) with
	   the left-shift operator */
	for (d = i = 1; i < m; ++i)
		d = (d<<1);

	for (hy = hx = i = 0; i < m; ++i) {
		hx = ((hx<<1) + x[i]);
		hy = ((hy<<1) + y[i]);
	}

	/* Searching */
	j = 0;
	while (j <= n-m) {
		if (hx == hy && memcmp(x, y + j, m) == 0)
			OUTPUT(j);
		hy = REHASH(y[j], y[j + m], hy);
		++j;
	}

}

int main()
{
	char y[] = "how are you hello world hello";
	char x[] = "hello";

	KR( x, strlen(x), y, strlen(y) );
	return 0;
}

3. Shift Or (SO)

bit mask / bit shift 사용
ASZIE : 256
O(nm) → O(n+m)
S[ASIZE][pattern size] : 초기화 (1111 1111) 후 각 ASCII 값에 pattern 에 존재하는 위치 저장
- pattern: hello
- S['h'] = 1111 1110
- S['e'] = 1111 1101
- S['l'] = 1111 0011
- S['o'] = 1110 1111
- lim = 0001 1111 에서 right shift 한번 후 ~() 을 붙인다. (lim = ~(lim >>1))
- j는 1부터 j<<=1 하여 m번 반복
searching 용 bit : state
- state는 lim 과 비교하고 state<<1은 S[y[i]] 와 비교한다.
- state<<1과 S[y[i]]를 OR 연산을 하여 그 결과를 state에 저장한다.
- 이 때, 둘다 0인 부분만 (즉 일치하는 부분) 만 0이 된다.
- pattern에 없는 글자는 S[' '] 에서 모두 1로 초기화 되어있기 때문에
- pattern에 없는 글자를 만나면 state는 도로아미타불이 되어 1111 1111 (~0) 이 된다.
- pattern이 모두 일치하는 경우에만 lim > state가 된다.
look-up table 을 만들어서 memory를 더 쓰기는 했지만, momory를 아끼기 위해 bit 사용
최대 한계 : m이 WORD (32 bits)보다 큰 경우 pattern을 저장할 수 없음
- 확장 bit map을 만들면 되긴 하다.
하지만 아직도 n 회전을 한다. 적어도 n-m+1 만큼 for loop 한다.

#include <stdio.h>
#include <string.h>

#define OUTPUT(x)    printf("%d\n", x )
#define ASIZE    256 

int preSo(char *x, int m, unsigned int S[]) { 
	unsigned int j, lim; 
	int i; 
	for (i = 0; i < ASIZE; ++i) 
		S[i] = ~0; 
	for (lim = i = 0, j = 1; i < m; ++i, j <<= 1) { 
		S[x[i]] &= ~j; 
		lim |= j; 
	} 
	lim = ~(lim>>1); 
	return(lim); 
} 
void SO(char *x, int m, char *y, int n) { 
	unsigned int lim, state; 
	unsigned int S[ASIZE]; 
	int j; 

	/* Preprocessing */ 
	lim = preSo(x, m, S); 

	/* Searching */ 
	for (state = ~0, j = 0; j < n; ++j) { 
		state = (state<<1) | S[y[j]]; 
		if (state < lim) 
			OUTPUT(j - m + 1); 
	} 
} 


int main()
{
	char y[] = "how are you hello world hello";
	char x[] = "hello";

	SO( x, strlen(x), y, strlen(y) );
	return 0;
}

4. Morris-Pratt (MP)

example
- pattern : g a g g g a g g
- mpNext : -1 0 0 1 1 1 2 3 4
- mpNext의 처음은 -1 default
- mpNext 의 의미는, 틀린 문자열이 발견된 위치의 앞서 일치된 문자열속의 접두사와 접미사의 일치수. 즉, shift = i = mpNext[i] 값이 되어 shift 만큼만 밀어주면 된다.
밖의 for loop를 줄일 수 있다.
즉 접두사 접미사가 일치한 것에 대해서 또 비교를 하지 않아도 된다.

#include <stdio.h>
#include <string.h>

#define OUTPUT(x)    printf("%d\n", x )

void preMp(char *x, int m, int mpNext[]) {
	int i, j;

	i = 0;
	j = mpNext[0] = -1;
	while (i < m) {
		while (j > -1 && x[i] != x[j])
			j = mpNext[j];
		mpNext[++i] = ++j;
	}
}

void MP(char *x, int m, char *y, int n) {
	int i, j, mpNext[256];

	/* Preprocessing */
	preMp(x, m, mpNext);

	/* Searching */
	i = j = 0;
	while (j < n) {
		while (i > -1 && x[i] != y[j])
			i = mpNext[i];
		i++;
		j++;
		if (i >= m) {
			OUTPUT(j - i);
			i = mpNext[i];
		}
	}
}

int main()
{
	//int mpNext[256];
	int i;
	char y[] = "how are you gagggagg world hello";
	char x[] = "gagggagg";

	/*
	preMp( x, strlen(x), mpNext );
	for(i=0; i<(strlen(x)+1); i++ )
		printf("%4d", mpNext[i] );
	printf("\n");
	*/
	MP( x, strlen(x), y, strlen(y));
	return 0;
}

5. Knuth-Morris-Pratt

example
- pattern : g a g g g a g g
- kmpNext : -1 0 -1 1 1 0 -1 1 4
- 이 예시에서는 mpNext 에 비해서 7 회전이 줄어들게 된다. (2배 이상 빠르다!)
미리비교를 수행하여 x[i] 와 x[j]를 먼저 비교한다.

#include <stdio.h>
#include <string.h>

#define OUTPUT(x)    printf("%d\n", x )
#define ASIZE  256
#define XSIZE  256

void preKmp(char *x, int m, int kmpNext[]) {
	int i, j;

	i = 0;
	j = kmpNext[0] = -1;
	while (i < m) {
		while (j > -1 && x[i] != x[j])
			j = kmpNext[j];
		i++;
		j++;
		if (x[i] == x[j])
			kmpNext[i] = kmpNext[j];
		else
			kmpNext[i] = j;
	}
}


void KMP(char *x, int m, char *y, int n) {
	int i, j, kmpNext[XSIZE];

	/* Preprocessing */
	preKmp(x, m, kmpNext);

	/* Searching */
	i = j = 0;
	while (j < n) {
		while (i > -1 && x[i] != y[j])
			i = kmpNext[i];
		i++;
		j++;
		if (i >= m) {
			OUTPUT(j - i);
			i = kmpNext[i];
		}
	}
}

int main()
{
	int i;
	char y[] = "how are you gagggagg world hello";
	char x[] = "gagggagg";

	KMP( x, strlen(x), y, strlen(y));
	return 0;
}

6. Boyer-Moore

비교를 pattern의 뒤에서부터 한다.
bad character : bad character 가 다시 만날때까지의 최소 길이
- 맨 뒷칸을 기준으로 몇칸 떨어져 있는지 기록한 table이 bmBc[] 이다. 만약 pattern에 값이 없으면 ?!?!

#include <stdio.h>
#include <string.h>

#define OUTPUT(x)    printf("%d\n", x )
#define MAX(a,b)  (((a)>(b))?(a):(b))
#define ASIZE  256
#define XSIZE  256

void preBmBc(char *x, int m, int bmBc[]) {
	int i;

	for (i = 0; i < ASIZE; ++i)
		bmBc[i] = m;
	for (i = 0; i < m - 1; ++i)
		bmBc[x[i]] = m - i - 1;
}


void suffixes(char *x, int m, int *suff) {
	int f, g, i;

	suff[m - 1] = m;
	g = m - 1;
	for (i = m - 2; i >= 0; --i) {
		if (i > g && suff[i + m - 1 - f] < i - g)
			suff[i] = suff[i + m - 1 - f];
		else {
			if (i < g)
				g = i;
			f = i;
			while (g >= 0 && x[g] == x[g + m - 1 - f])
				--g;
			suff[i] = f - g;
		}
	}
}

void preBmGs(char *x, int m, int bmGs[]) {
	int i, j, suff[XSIZE];

	suffixes(x, m, suff);

	for (i = 0; i < m; ++i)
		bmGs[i] = m;
	j = 0;
	for (i = m - 1; i >= 0; --i)
		if (suff[i] == i + 1)
			for (; j < m - 1 - i; ++j)
				if (bmGs[j] == m)
					bmGs[j] = m - 1 - i;
	for (i = 0; i <= m - 2; ++i)
		bmGs[m - 1 - suff[i]] = m - 1 - i;
}


void BM(char *x, int m, char *y, int n) {
	int i, j, bmGs[XSIZE], bmBc[ASIZE];

	/* Preprocessing */
	preBmGs(x, m, bmGs);
	preBmBc(x, m, bmBc);

	/* Searching */
	j = 0;
	while (j <= n - m) {
		for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
		if (i < 0) {
			OUTPUT(j);
			j += bmGs[0];
		}
		else
			j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
	}
}
int main()
{
	int i;
	char y[] = "how are you gagggagg world hello";
	char x[] = "gagggagg";

	BM( x, strlen(x), y, strlen(y));
	return 0;
}

§ Generic sort

1. generic swap

swap 함수는 call by address로 구현하여 실제 값이 swap 될 수 있도록 한다.
인자로 받아오는 type을 모두 지원해줘야 하는데, c에서는 함수 오버로딩을 지원하지 않으므로
이때 쓸수 있는 technique 이 void pointer
integer 4 byte / double 8 byte / char 4 byte 이기 때문에 int size 인자를 추가한다.

void swap (char *a, char *b, int size) 
{
   int i;
   char t;
   for (i=0; i<size; i++) {
      t = *a[i];
      *a[i] = *b[i];
      *b[i] = t;
   }
}

// main
int a, b;
int ad, bd;

swap (&a, &b, sizeof(a));
swap(&ad, &bd, sizeof(ad);

caller 에서 warning이 많이 발생하기 때문에 이를 막기 위해서 명시적 casting을 해준다.
즉 &a, &b 로 넘겨주는게 아니라, 함수의 인자 type에 맞게 casting 하여 넘겨준다.

swap( (char*)&a, (char*)&b, sizeof(a) )

하지만 이렇게 되면 사용할때마다 캐스팅을 해주느라 쓰기 불편해진다.
이를 해결하기 위해 void pointer을 사용하자 !
하지만 void pointer을 쓸때는 첨자를 사용할 수 없다. (ex. *a[i])
따라서 실제로 주소에 접근할 때 casting을 하여 컴파일러에게 얼마만큼 움직이면 될지를 알려주어야 한다.

void swap (void *a, void *b, int size) 
{
   int i;
   char t;
   char *aa = (char*)a;
   char *bb = (char*)b;

   for (i=0; i<size; i++) {
      t = *aa[i];
      *aa[i] = *bb[i];
      *bb[i] = t;
   }
}

void generic_swap(void *a, void *b, int size)
{
   char t;
   do {
      t = *(char *)a;
      *(char *)a++ = *(char *)b;
      *(char *)b++ = t;
   } while (--size >0);
// 실제 generic swap 함수
// size를 0과 비교하기 때문에 (우리가 짠 코드는 i과 size 비교) 좀더 유리하다
}

2. generic sort

void bubble(int *a, int n)
{
   int i, j;
   for (i=0; i<n-1; i++)
      for (j=0;j<n-1-i; j++)
         if (a[j] > a[j+1])
            generic_swap(a+j, a=j+1, sizeof(a[0]));
}

int main()
{
int a[] = {4, 3, 5, 2, 7, 1, 6};
int i;

bubble(a, 7);
for (i=0; i<7;t++)
   printf("%4d", a[i]);
printf("\n");
return 0;
}

값이 필요한 알고리즘은 일반화 할 수 없다.
즉, sort에서는 값을 비교하기 위해 값이 필요하므로 sorting, 검색 등은 일반화 할 수 없다.
void 포인터만으로는 짤 수 없다. → 일반화를 위한 ! "비교"를 유저에게 위임하자.
함수 포인터를 사용

int int_cmp(const void* a, const void* b)
{
   return (*(int*)a - *(int*)b) > 0;
}

# 모든 type 을 sort 하기 위해서
# 하나의 원소의 size를 size로 넣어준다.  
void bubble (void *a, int n, int size, int (*cmp)(const void*, const void*))
{
   ...
   # void pointer 를 직접 사용할 수 없으므로 
   # pointer 수동 계산해준다. 
   if (cmp ((char*)a+j*size, (char*)a+(j+1)*size)>0)
   ...
}

qsort (퀵 소트) 도 호환 가능

§ Bit algorithm

1. find first set

단순히 << shift를 이용해 비교를 하면 최악의 경우 O(n) search 해야 한다.
__ffs 함수를 사용하게 되면 bit를 절반씩 쪼개서 bit mask 로 비교를 하므로 O(log2n) search 만 하면 된다.
하지만 아래 코드는 최상위 bit가 0이거나 1일때 결과가 같아지게 된다.
먼저 word가 0 인지 아닌지부터 체크하고 ffs 하면 된다.

 // for int (32 bit)   
 14 int __ffs(int word)
 15 {
 16     int num = 0;
 17  
 18     if ( (word & 0xffff) == 0 ) {
 19         // 00000000 00000000 11111111 1111111
 20         // if == 0 --> at least 16 bit
 21         num += 16;
 22         word >>= 16;
 23     }
 24  
 25     if ( (word & 0xff) == 0 ) {
 26         // 00000000 1111111
 27         // if == 0 -->  +8
 28         num += 8;
 29         word >>= 8;
 30     }
 31  
 32     if ( (word & 0xf) == 0 ) {
 33         // 00001111
 34         num += 4;
 35         word >>= 4;
 36     }
 37  
 38     if ( (word & 0x3) == 0 ) {
 39         // 0011
 40         num += 2;
 41         word >>= 2;
 42     }
 43  
 44     if ( (word & 0x1) == 0)
 45         num += 1;
 46  
 47     return num;
 48 }

if (bitmap != 0)
  __ffs
else
  error !

2. find next bit

확장 bitmap search

int bitmap[4] = {0, };
bitmap[3] |= 1 << 4;
// bitmap[100/32] |= 1 << 100%32;

// 하면 100번째에 들어간다. 
// 100 = 32 * 3 + 4

example
- real time (RT) process : 0 ~ 99
- normal process : 100 ~ 139
- 만약 normal process 구간에서만 search를 하고 싶다면, 부분 bit열 search를 위한 logic 이 find_next_bit 라고 한다.
find_next_bit ( input, 유효 bit 수, 유효 bit 시작점 )

3.hamming weight

example
- input : 0x12345678
- input : 0001 0010 0011 0100 0101 0110 0111 1000
- mask1 : 0101 0101 0101 0101 0101 0101 0101 0101
- (x & m1) + ((x >> 1) & m1) output : 0001 0001 0010 0100 0101 0101 0110 0100
- compare
  - 00 01 00 10 00 11 01 00 01 01 01 10 01 11 10 00 (input)
  - 00 01 00 01 00 10 01 00 01 01 01 01 01 10 01 00 (output)
  - 즉, 2 bit씩 나눠서 보면 mask1 의 결과는 2 bit끼리의 bit의 개수가 기록된다.
- mask2 : 0011 0011 0011 0011 0011 0011 0011 0011
- input : 0001 0010 0011 0100 0101 0110 0111 1000
- out : 0001 0001 0010 0001 0010 0010 0011 0001
  - 이번에는 4 bit씩 나눠서 보면 mask2 의 결과는 4 bit끼리의 bit 개수가 기록된다.

  3 const int m1    = 0x55555555; // 01010101 ...
  4 const int m2    = 0x33333333; // 00110011 ...
  5 const int m4    = 0x0f0f0f0f;
  6 const int m8    = 0x00ff00ff;
  7 const int m16   = 0x0000ffff;
  8 const int h01   = 0x01010101;
  9      
 10 int popcount_a(int x)
 11 {    
 12     x = (x & m1) + ((x >> 1) & m1); // 2bit count
 13     x = (x & m2) + ((x >> 2) & m2); // 4bit count 
 14     x = (x & m4) + ((x >> 4) & m4);
 15     x = (x & m8) + ((x >> 8) & m8);  
 16     x = (x & m16) + ((x >> 16) & m8);
 17      
 18     return x;
 19 }

popcount_a 가 O(log2n) 으로 계산을 줄였지만, 연산자가 많다.
- 연산자가 한 줄에 4개나 쓰여서 CPU 속도가 느려지게 된다.
popcount_b
- 2bit 의 경우의 수는 00 01 10 11 밖에 없다.
- 이 때의 bit count 세면 00 01 01 10 이 된다.
- popcount_b 에서 m1에 대한 식은, 원본 bit에서 앞의 bit의 밀어서 count 한거를 원본에서 뺀게 count 라는 것
  - 원본 - 앞 bit = count
  - 00 - 0 = 00
  - 01 - 0 = 01
  - 10 - 1 = 01
  - 11 - 1 = 10
popcount_c
- 3번째 까지는 8번째까지 bit수 count (여기까지는 popcount_b와 동일)
- ex) 0x12345678 -> 0x02030404
- h01 을 이용한다 ! (h01 = 0x01010101)
- h01을 곱하면, 0x02030404 * 0x01010101 = 결과 부분에서 0x00 0000 1100 0000 1이 있는 부분이, 2bit씩 잘라내서 더한것과 동일한 결과를 얻게 된다. 이를 나중에 24만큼 밀어준 결과부분만 가져오면 된다.
- 요즘 CPU는 곱을 빨리할 수 있기 때문에 연산을 줄일 수 있다.
- open source __sw_hweight32 도 이걸 이용하고 있음

 21 int popcount_b(int x)
 22 {
 23     x -= (x >> 1) &m1;
 24     x = (x & m2) + ((x >> 2) & m2);
 25     x = (x + (x >> 4)) & m4;
 26     x += x >> 8;
 27     x += x >> 16;
 28  
 29     return x & 0x7f;
 30 }
 31  
 32 int popcount_c(int x)
 33 {
 34     x -= (x >> 1) &m1;
 35     x = (x & m2) + ((x >> 2) & m2);
 36     x = (x + (x >> 4)) & m4;
 37  
 38     return (x * h01) >> 24;
 39 }
 40

popcount_d
- x &= x-1;
- 0001 0010 0011 0100 0101 0110 0111 1000
- 0001 0010 0011 0100 0101 0110 0111 0111
- ________________________________________ &
- 0001 0010 0011 0100 0101 0110 0111 0000 -> count = 1
- 1이 지워지는 만큼 counting 이 된다.
- 하지만 성능이 좋을까? 보통의 경우 유리한 것이 아니라, 1을 가진 bit 수가 현저히 적을 때 ! 유리하다.
- 32 bits 중에서 2개만 1일때 2번만에 찾아낼 수 있어서 유리하다. log2n 보다 적을때 유리하다.
- 특별한 경우에만 performance가 좋기 때문에 오픈소스에서는 popcount_c를 사용한다.

 32 int popcount_d(int x)
 33 {
 34     int count;
 35     for (count = 0; x; count++)
 36         x &= x - 1;
 37  
 38     return count;
 39 }
 40

4. bit reverse

lookup table
2^8 = 256 개 (16 x 16 matrix 를 만들어 미리 계산해둔다.)
0x12 를 넣으면 1행 2열을 읽어온다.
- 0x12 → 0x21 이 아니라 0001 0010 → 0100 1000 즉 0x48 이 된다.
- lookup table 을 미리 써두고 이용한다.
- unsigned char (8bit) 에 대해서 16x16 = 256 크기의 table을 만들어 두고 사용한다.
- 최대 한계는 16bit에 대해서는 (size 65532) lookup table을 만들 수 없다.
- unsigned short (16bit) 를 계산할때는, 8bit 씩 reverse하고 앞 뒤 8bit를 swap 한다.
- unsigned int (32bit) 도 16bit씩 reverse하고 앞 뒤 16bit를 swap 한다.

 11 u8 bitrev8(u8 x)
 12 {    
 13     return byte_rev_table(x);
 14 }    
 15      
 16 u16 bitrev16(u16 x)
 17 {    
 18     return (bitrev8(x & 0xff) << 8) | bitrev8(x >> 8);
 19 }    
 20      
 21 u32 bitrev32(u32 x)
 22 {    
 23     return (bitrev16(x & 0xffff) << 16) | bitrev16(x >> 16);  
 24 }

§ Data 무결성 관련

1. parity bit

네트워크를 타고 client 에 전송이 되었을 때, 데이터 오류를 검증할 용도로 사용
1의 개수가 홀수일때는 맨 앞 bit에 1을 넣고, 1의 개수가 짝수일때는 맨 앞 bit에 0을 넣는다.
- hweight 이용하여 1의 개수 파악
- hweight(data)%2 일 경우 data |= 0x80; (1000 0000)
parity bit가 적용되면 1의 개수가 항상 짝수이기 때문에, 받는 쪽에서도 hweight 이용하여 1의 개수 파악
최대 한계 : 짝수개의 bit가 변형되면 error를 찾을 수 없다.

2. check sum

송신부와 수신부의 코드가 같다.

아스키 코드 128 bit 중에서 7bit (Ex) a 97 0110 0001 ref ) https://github.com/imguru-mooc/opensource-datastructure-algorithm

Algorithm - jjin-choi/study_note GitHub Wiki

§ Pattern Matching

§ Generic sort

§ Bit algorithm

§ Data 무결성 관련

⚠️ GitHub.com Fallback ⚠️

Algorithm - jjin-choi/study_note GitHub Wiki

§ Pattern Matching

§ Generic sort

§ Bit algorithm

§ Data 무결성 관련

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️