[박혜웅] 비트 벡터 (bit vector)

• bit-vector for set 의 특징

• • 원소(문헌)을 정수로 식별할 수 있어야 한다.

    • 비트벡터의 각 비트가 각각 정수로 식별되기 때문

  • 처리 속도는 빠름

    • 비트연산을 이용하므로

  • 원소의 값 영역이 작을 때 유용

    • 원소의 간격(원소값이나 원소식별자번호)이 클 경우, 공간을 많이 사용함

  • 원소들 각각에 대해 한 비트를 할당하며, 집합을 일련의 비트로 표현

  • • 집합안에 해당 원소가 있다면 비트를 1(TRUE)로, 없으면 0(FALSE)으로 표현
    • 비트에 접근하기 위하여, mask와 shift를 이용

 

• 정보검색에서 비트벡터의 사용 예

• • 
     

 

• bit-vector for set 의 성능

  • 삽입,삭제

    • O(C)
    • 하드웨어의 나눗셈 연산 속도에 의해 좌우됨
    • 하드웨어의 비트연산속도는 매우 빠르므로 성능에 끼치는 영향이 매우 작음

  • 반복회수

    • O( N/WORDSIZE ): 일반적인 연산시
    • O( N ): Iterate() 연산시

  • 저장공간

    • MAX_ELEMENT/WORDSIZE + sizeof(int)*2

      • sizeof(int)*2 = lower, upper 변수

 

• 값이 i인 원소가 있는지(또는 원소식별자가 i인 원소가 있는지) 확인하는 코드

  1. ( vector[ (i-1)/8 ] << (i-1)%8 ) & 0x01
  2. vector[ (i-1)/8 ] & ( 0x01 >> (i-1)%8 )

  • 8 = sizeof(vector[0])

    • 위 식에서 8은 vector[x]의 크기
    • 일반적으로 1바이트(8비트)의 크기를 사용함
    • 컴퓨터 의 처리단위와 같도록 8의 배수(16,32....) 로 변경 가능

  • i-1

    • i번째 비트를 의미, 실제로 비트번호나 배열인덱스번호가 0에서 시작하므로

  • (i-1)/8

    • vector[ x ] 배열에서 i번째 원소의 정보가 저장된 배열 인덱스 x를 구함

  • (i-1)%8

    • vector[ x ]안에서 i번째 원소의 정보가 존재하는 비트번호

  • 예

    •