Static Huffman Code

  • 워낙 유명하니 패스.
  • 장점 : prefix code 중 encoded sequence의 길이의 기대값이 optimal한 encoding한 방식이다.
  • 단점 : 각 symbol의 probability를 미리 알아야 한다.

Adaptive Huffman Code

  • symbol별 등장 횟수를 각 node의 weight로 삼고, node가 항상 정렬된 상태를 유지하도록 적절히 swap해주면 된다.
  • https://www.youtube.com/watch?v=c2wu8QOS1EY
  • 개량 버전으로 Algorithm FGK와 V가 있으며, V 기준으로 static huffman code보다 일반적으로 효율적이며, 최악의 경우에도 codeword당 1bit를 더 사용할 뿐이다.

LZ77

  • window size를 정하고, 현재 위치 이전까지의 window buffer에서 현재 위치부터 시작하는 문자열에 겹치는 substring이 있는지 확인한다.
  • https://www.youtube.com/watch?v=l7xeA6py9zM (window buffer 대신 search buffer라는 명칭을 사용한다.)
  • 장점 : locally repeated pattern을 압축하는데 효과적이다.
  • 단점 : window size를 넘는 repeated pattern은 감지하지 못한다.

LZ78

  • 현 위치부터 시작하는 문자열과 가장 많이 겹치는 substring을 dictionary에서 찾아서 substitute하고, 직후 1글자를 encode하고, 그 substring + encode했던 직후 1글자를 새로 dictionary에 등록한다.
  • https://www.youtube.com/watch?v=2PZz-8O3L6A
  • 장점 : LZ77과 달리 runtime에 source statistics을 이용할 수 있다.
  • 단점 : dictionary가 계속 자라난다. (encoded file에는 영향이 없지만 encoding/decoding에 영향)

LZW

Golomb-Rice Code

  • 정수 k를 정한 뒤 n을 2^k로 나눈 몫을 q, 나머지를 r이라 할 때, GR(k, n) = concat(unary(q), binary(k, r))이다.
  • unary(5) = 111110, binary(k, n) = k-bit binary representation of n.
  • 특징 : prefix code이다. |GR(k, n)| = q + k + 1.
  • 장점 : binary compression에서 특정 범위의 symbol의 빈도가 높을 때 압축률이 좋다. 예를 들어, 0 ~ 1048575를 인코딩하는데 0 ~ 15가 대부분인 경우 저 범위의 값을 나타내기 위에 앞에 0 bits를 달지 않아도 된다.
  • 이런 유형의 코드를 (아마 위와 같은 이유로) integer code라고 한다.

Tunstall Code

  • Depth를 정한 뒤, tree가 해당 depth가 될 때까지 probability가 가장 높은 node를 쪼갠다.
  • Fixed length code이긴 한데, 등장할 확률이 높은 구절은 여러 symbol이 묶여서 하나의 code로 encode된다.
  • http://web.engr.oregonstate.edu/~thinhq/teaching/ece499/spring06/runlength_turnstall_golomb.pdf (뒤쪽 tunstall 파트를 보면 된다.)
  • 장점 : Error resilient하다. 즉, flipped bit이 output의 한 alphabet에만 영향을 미친다.
  • 단점 : symbol의 probability를 미리 알아야 하며 fixed length code라는 점에서 LZW에 밀린다.

Arithmetic Code

  • [0, 1) interval을 symbol의 probability를 가지고 쪼개는 작업을 반복적으로 한다. 언제까지? precision이 허락할 때까지.
  • Pre-defined probability distribution에서 시작해서 symbol의 등장 횟수에 따라 확률 분포를 업데이트하는 adaptive 방식으로도 가능하다.
  • https://www.youtube.com/watch?v=-R2a2a1-2MM
  • 장점 : 다른 compression 알고리즘과 연동하여 사용하기 용이하다.
  • 단점 : encoded file의 bit가 하나만 손상되더라도 decoding이 불가능해질 수 있다.
  • 응용 (binary arithmetic coding) : JBIG, JPEG, H.264

'알고리즘' 카테고리의 다른 글

Bidirectional Dijkstra 설명  (0) 2020.03.13
(Approximate) Heavy Hitters, Count-Min Sketch, Bloom Filter  (0) 2020.03.13
Consistent Hashing  (0) 2020.03.13
Universal Hash Family 설명  (0) 2020.03.13
다양한 Cache Replacement Policy 정리  (0) 2020.01.07

https://towardsdatascience.com/the-5-clustering-algorithms-data-scientists-need-to-know-a36d136ef68

 

The 5 Clustering Algorithms Data Scientists Need to Know

Clustering is a Machine Learning technique that involves the grouping of data points. Given a set of data points, we can use a clustering…

towardsdatascience.com

https://bcho.tistory.com/1203

 

클러스터링 #1 - KMeans

클러스터링과 KMeans를 이용한 데이타의 군집화 조대협 (http://bcho.tistory.com) 클러스터링 문제 클러스터링은 특성이 비슷한 데이타 끼리 묶어주는 머신러닝 기법이다. 비슷한 뉴스나 사용 패턴이 유사한 사용..

bcho.tistory.com

https://bcho.tistory.com/1204

 

클러스터링 #2 - Hierarchical clustering (계층 분석)

Hierarchical clustering을 이용한 데이타 군집화 조대협 (http://bcho.tistory.com) Hierarchical clustering (한글 : 계층적 군집 분석) 은 비슷한 군집끼리 묶어 가면서 최종 적으로는 하나의 케이스가 될때까..

bcho.tistory.com

https://bcho.tistory.com/1205

 

클러스터링 #3 - DBSCAN (밀도 기반 클러스터링)

DBSCAN (밀도 기반 클러스터링) 조대협(http://bcho.tistory.com) 기본 개념 이번에는 클러스터링 알고리즘중 밀도 방식의 클러스터링을 사용하는 DBSCAN(Density-based spatial clustering of applications with..

bcho.tistory.com

https://bcho.tistory.com/1206

 

분류모델 (Classification)의 성능 평가

Classification & Clustering 모델 평가 조대협 (http://bcho.tistory.com) 클러스터링과 분류 모델에 대한 성능 평가 방법은 데이타에 라벨이 있는가 없는가에 따라서 방법이 나뉘어 진다. 사실 클러스터링은 라..

bcho.tistory.com

 

'기타' 카테고리의 다른 글

쉘 스크립트 cheatsheet  (0) 2020.03.03
정규표현식 cheatsheet  (0) 2020.03.03
게시판 크롤링 후 검색 기능 개발 로그  (0) 2019.08.02
Mac OS에서 cgdb 설치하기  (0) 2019.05.04
git 정리  (0) 2019.04.29

1. 크롤링

- https://beomi.github.io/gb-crawling/

- https://victorydntmd.tistory.com/245

 

2. 파이썬 기타

- 데몬 만들기 : https://ehclub.co.kr/1321

- 데몬 심화 : https://oddpoet.net/blog/2013/09/24/python-daemon/

 

3. MySQL

- SQL : https://thebook.io/006696/ (오라클 기준. MySQL 사용법은 여기저기 따로 찾아봄.)

- 설치 : https://dejavuqa.tistory.com/317?category=311869

- 데이터타입 : https://ra2kstar.tistory.com/82http://www.incodom.kr/DB_-_%EB%8D%B0%EC%9D%B4%ED%84%B0_%ED%83%80%EC%9E%85/MYSQL

- PyMySql : http://pythonstudy.xyz/python/article/202-MySQL-%EC%BF%BC%EB%A6%AC

 

4. 프론트엔드

- HTML, CSS, Javascript : https://wafflestudio.readthedocs.io/ko/latest/

- React : https://velopert.com/3613

 

5. 백엔드

- Django로 REST API 서버 구축하기 : http://throughkim.kr/2018/05/29/django-rest/

- Django랑 React 연결하기 (도움 많이 됨) : this-programmer.tistory.com/entry/간단한-react-JS-Django-어플리케이션-만들기

- 기존 DB 스키마 가져오기 : https://newpower.tistory.com/203 (DATABASE_ROUTERS랑 app_label 제외하고 그대로 따라하니까 됨.)

- Django에서 SQL 쿼리 날리기 : https://itinerant.tistory.com/27

- Django에서 url의 일부를 parameter로 class based view로 보내는 방법 : https://stackoverflow.com/questions/11494483/django-class-based-view-how-do-i-pass-additional-parameters-to-the-as-view-meth

 

6. 서버 구성

- ssh : http://programmingskills.net/archives/315

- iptime 포트포워딩 : https://esarang.tistory.com/1059

- Ubuntu 서버 구축 & 도메인/호스팅 : https://blog.lael.be/post/8319

- Django : https://cupjoo.tistory.com/39https://developer.mozilla.org/ko/docs/Learn/Server-side/Django/skeleton_website

 

 

 

 

 

'기타' 카테고리의 다른 글

쉘 스크립트 cheatsheet  (0) 2020.03.03
정규표현식 cheatsheet  (0) 2020.03.03
클러스터링 기법 링크  (0) 2019.09.18
Mac OS에서 cgdb 설치하기  (0) 2019.05.04
git 정리  (0) 2019.04.29

 

1. Homebrew를 설치한다.

 

2-1. 쉘에서 brew install gdb를 입력하자.

 

2-2. Homebrew가 시키는 대로 https://sourceware.org/gdb/wiki/BuildingOnDarwin로 가서 (1), (2), (3) 항목을 모두 다 해주자.

 

Note : (2) 항목 중간에 "Start Keychain Access again. Using the contextual menu for the certificate, select Get Info, open the Trust item, and set Code Signing to Always Trust."라는 구절이 나온다. 키체인 접근 창 좌상단의 [시스템]을 누르고 우측에서 gdb-cert를 찾아서 오른클릭을 한 뒤 [정보 가져오기]를 누르라는 소리다. 

 

 

3-1. 쉘에서 brew install cgdb를 입력하자.

 

3-2. ~/.bash_profile에

          export LDFLAGS="-L/usr/local/opt/readline/lib"
          export CPPFLAGS="-I/usr/local/opt/readline/include"

      를 추가해주자.

 

4. 코드를 컴파일 할 때 디버깅 옵션으로 -g를 추가해주자. 안 그러면 어셈블리로 가득한 cgdb 화면을 보게 된다.

 

5. 해피 디버깅!

 

'기타' 카테고리의 다른 글

쉘 스크립트 cheatsheet  (0) 2020.03.03
정규표현식 cheatsheet  (0) 2020.03.03
클러스터링 기법 링크  (0) 2019.09.18
게시판 크롤링 후 검색 기능 개발 로그  (0) 2019.08.02
git 정리  (0) 2019.04.29

기본 개념

파일들의 상태

  • Untracked
  • Tracked : git이 tracking하고 있음.
    • Unmodified
    • Modified : commit 이후 수정되었음.
      • Unstaged
      • Staged : 수정 내역이 차기 commit 대상 리스트에 포함됨. (git add 명령어로 리스트에 포함시킨다.)

commit

  • 각 commit은 snapshot 파일의 포인터를 가지고 있으며, snapshot 파일은 blob 파일들의 포인터를 가지고 있다.[1]
  • 또한 각 commit은 이전 commit의 포인터도 가지고 있다.

브랜치

  • 브랜치는 특정 commit을 가리키는 41바이트의 파일에 불과하다.
  • HEAD 포인터는 현재 작업 중인 브랜치를 가리킨다.
  • merge시에는 fast-forward 또는 recursive strategy가 쓰인다.
    • 전자는 단순히 포인터만 옮겨놓는 반면, 후자는 부모가 둘인 새 commit을 만든다.
  • merge에서 문제가 발생하면 git은 표준 형태로 파일을 고쳐놓으며, 하나를 골라서 add해주자.
    • 이후에 git commit으로 머지를 종료할 수 있다.
  • tracking branch
    • git branch -vv에서 누가 더 앞서가는지 확인할 수 있다.
      • 하지만, 비교는 로컬에서 이뤄진다.
      • 정확한 비교를 위해서는 먼저 git fetch --all을 해줘야 한다.


명령어들

기본 명령어

$ git add <file_name>                                                # untracked, unstaged -> staged
$ git commit                                                         # git commit -m은 써도 되는지 모르겠다.

config 확인/되돌리기

  • git에서 확인하는 config 파일들은 다음과 같다. (priority 순으로 나열)
    1. .git/config (해당 project)
    2. ~/.gitconfig, ~/.config/git/config (해당 사용자)
    3. /etc/gitconfig (전체 사용자)
$ git config --list
$ git config --local --list                                          # 내가 추가한 config 리스트

$ git config [<file-option>] --unset-all <name> [value_regex]        # unset all
$ git config [<file-option>] --remove-section <name>                 # remove specific section

실제 파일 다루기

$ rm a.out                                                           # a.out만 달랑 삭제했으므로 unstaged. 계속 tracking한다.
$ git rm a.out                                                       # git 명령어를 사용했으므로 삭제 행위가 staged되었다. 따라서 더 이상 tracking하지 않는다. 물론 원본도 삭제됨.
$ git rm --cached a.out                                              # staging area에서만 삭제한다. git에서 관리하기 싫은 파일 제거시 사용.

$ git mv <before> <after>                                            # 위와 마찬가지로 git은 mv의 결과를 알고 있다.

status, diff & log

$ git status
$ git status -s                                                      # svn st 모양으로 이쁘게 나옴. awk 먹이기 좋아보인다.
$ git status -v                                                      # diff까지 붙여서 보여준다.

$ git diff                                                           # 마지막으로 staged/committed된 이후의 diff만 보여준다. 즉, unstaged들의 last record와의 diff.
$ git diff --staged                                                  # staging area 내의 파일들의 diff. --cached 명령어도 동일한 기능을 한다.

$ git log                                                            # 최근 log부터 나온다.
$ git log -p -2                                                      # 최근 2 커밋의 diff를 보여준다. -2 옵션이 없으면 싹 다 보여줌.
$ git log --pretty=oneline                                           # 각 커밋의 해시와 메시지를 한 줄씩 보여준다.
$ git log -S <function_name>                                         # 해당 이름의 함수를 건드린 commit만 보여준다.

$ git log -p <ci_hash>                                               # 특정 commit의 직전 버전과의 diff를 보여준다.
$ git diff <ci_hash>~ <ci_hash>                                      # 상동

되돌리기

$ git commit --amend                                                 # 이전의 commit을 덮어쓸 기회를 준다. 메시지 편집 기회도 준다.

$ git reset HEAD <file>                                              # file을, staged -> unstaged
$ git checkout -- <file>                                             # file을, 이전 commit버전으로 덮어써버린다. (commit버전 이후의 수정 내역은 사라진다.)

브랜치 다루기

$ git branch <name>                                                  # 새로운 이름의 브랜치를 만든다. 새 브랜치와 HEAD가 가리키는 브랜치는 동일한 commit을 가리킨다.
$ git checkout <name>                                                # HEAD가 새 브랜치를 가리키게 한다.
$ git co -b <name>                                                   # 위의 두 명령어를 합쳤다.

$ git commit                                                         # commit을 하게 되면 브랜치는 분기된다. 왜? 새롭게 만들어지는 SHA-1 체크섬 hash 값이 다를 테니까.
$ git co master                                                      # master 브랜치로 (뒤로) 이동하며, working dir의 데이터도 해당 시점으로 돌려놓는다.

$ git log --oneline --decorate --graph --all                         # 브랜치 히스토리를 출력한다.
$ git log --color --graph --pretty=format:'%Cred%h%Creset -%C(yellow)%d%Creset %s %Cgreen(%cr) %C(bold blue)<%an>%Creset' --abbrev-commit     # 좀 더 이쁘게 출력한다.
$ git co master; git merge hotfix # master로 돌아가서 hotfix 브랜치를 merge한다. $ git branch -d hotfix # hotfix 브랜치가 더 이상 필요하지 않으면 지운다. $ git branch [-v] # 모든 branch를 보여준다. $ git branch -vv # tracking branch 정보를 보여준다. $ git branch --merged # merge된 branch만 보여준다. (master랑 merge됐으면, merge 직전의 commit을 가리키는 상태로 계속 남는다.) *표시가 없으면 지워도 된다. $ git branch --no-merged # merge되지 않은 branch만 보여준다. -d 옵션으로 지울 수 없다.

Remote와의 작업

$ git remote add <name> <url>
$ git remove -v                                                      # 등록된 remote repo를 모두 보여준다.
$ git remote show <name>                                             # 해당 remote repo의 정보를 보여준다.

$ git clone <url>                                                    # remote를 모조리 복사해온다.
$ git fetch <name>                                                   # remote와 local의 diff를 복사해온다. 하지만 내 작업을 merge해주지는 않는다.
$ git pull <name>                                                    # git fetch + git merge. 따라서 working dir의 데이터까지 바꿔놓는다.

$ git fetch origin                                                   # origin과의 commit diff를 복사해오고, 로컬의 origin/master 포인터가 실제 origin의 master 포인터와 동일한 commit을 가리키게 한다.
$ git co -b master origin/master                                     # fetch만으로는 수정 가능한 브랜치가 만들어지지 않는다. checkout 명령어로 만들어줘야 한다. (clone에서는 자동으로 수행되는 듯)

$ git push origin master                                             # 내 master를 origin의 master에 push한다.
$ git push origin a:b                                                # 내 a를 origin의 b에 push한다.

$ git branch -u origin/master                                        # 현재 branch가 origin/master를 tracking하게 만든다.
$ git fetch --all; git branch -vv                                    # 서버에서 최신 데이터를 받아온 뒤 tracking 상황을 체크한다.

$ git push origin --delete serverfix                                 # origin에서 serverfix 브랜치를 지운다.


기타

  • alias 만들기
$ git config --global alias.st 'status -'s                           # git st == svn st


'기타' 카테고리의 다른 글

쉘 스크립트 cheatsheet  (0) 2020.03.03
정규표현식 cheatsheet  (0) 2020.03.03
클러스터링 기법 링크  (0) 2019.09.18
게시판 크롤링 후 검색 기능 개발 로그  (0) 2019.08.02
Mac OS에서 cgdb 설치하기  (0) 2019.05.04

+ Recent posts