본문 바로가기
Study

유용한 알고리즘 모음

by SeulKom 2010. 1. 14.

Bloom Filter (=Parallel Join Filter)
  - 확률적으로 멤버쉽을 테스트하는 자료 구조, 실시간 탐지에 유용
     hashing기법을 사용해서, 많은 block들의 miss, hit여부를 비교적 작은 data structure를 이용하여 저장
     False positive 가능


Dancing Link
  - NP-Complete 문제의 하나인 exact cover (subset의 collection이 다시 set을 정확하게 구성하는 조합)를 풀기 위해 알고리
    즘
x의 기반이 되는 자료구조


Trie
  - prefix가 일치하는 인덱스를 통해 빠르게 값을 찾을 수 있는 자료구조로서, 동적인 해시 트리라고 할 수 있다.


Suffix Tree
  - suffix가 일치하는 인덱스 자료구조로서, 특정 문자열의 패턴을 검출하는 도구로 사용


Splay Tree
  - 최근에 접근했던 데이터를 다시 빠르게 접근할 수 있는 자료구조로써 균형잡힌 이진 탐색 트리 구조(AVL)


Rope
  - string 타입의 확장 자료형, STL rope container 참조


R-tree
  - 2차원 공간 데이터의 포함 관계를 나타내기에 적합한 자료구조


KD-tree
  - 다차원 공간 데이터의 구간 탐색이나 이웃 탐색에 유리한 자료구조


Bit array
  - 비트맵 자료구조


QuadTree
  - sparse한 2차원 데이터의 공간적인 관계를 표시하거나 이미지 표현에 유용한 자료구조


Inverted Index
  - 문서에 포함된 키워드가 문서를 가리키도록 만들어진 인덱스 자료구조, full text search에 가장 쉽게 사용되는 자료 구조


Disjoint-Set data structure
  - 집합을 partition 하거나 MST를 찾는 알고리즘을 지원하는 자료구조


Binary space partitioning
  - 복잡한 구조의 객체를 단순한 볼록 다각형으로 partition 하는 알고리즘, 3D 객체를 2D 화면에 렌더링 하면서 색칠할 때 복
    잡한 색칠 순서를 결정하는 데 도움을 주는 방법


Van Emde Boas tree
  - 기본 연산의 수행 시간이 O(log log n)인 트리 자료 구조. 한정된 2^n 비트 키 공간에서 특정 키를 이진 탐색으로 찾아내기
    에 유리한 트리들의 트리 구조

Huffman coding
  - 무손실 압축 알고리즘에 이용되는 기본 코딩 방식


Binomial heap
  - 주로 두 개의 heap을 합치는 데 사용되는 binary heap


Fibonacci heap


Pairing heap


Spiral Storage
  - 점진적으로 커지는 해시 기반의 저장소


Judy array
  - Hash table 보다 빠른 해시 자료구조. 빠르고 공간 사용량이 적어서 주로 cache 알고리즘에 이용


Cuckoo hashing
  - 해시 충돌 해소 알고리즘. 새로운 키를 놓을 때 같은 자리에 이미 놓여있던 기존 키를 다른 위치로 옮기고 새로운 키를 그
    자
리에 놓는 방법


Circular buffer
  - 링 버퍼


Counted B-tree
  - 중앙값이나 백분위수를 빠르게 찾을 수 있는 b-tree 변형


Suffix array
 - 부분 문자열을 빠르게 찾을 수 있는 인덱스 자료구조


Binary decision diagram
 - binary decision tree를 효율적으로 재배치한 자료구조로서 회로 설계에서 주로 사용


Skiplist
  -  계층적인 구조로 만들어진 리스트, 일반 linked list와는 달리 random access에 유리. 이진 탐색 트리의 장점을 도입한 list


출처 : http://terzeron.net/wp/
반응형

댓글0