Computer Science/알고리즘 (13) 썸네일형 리스트형 허프만 코딩 2 - 문자열 압축과 추출 지난 포스팅(https://taeminator1.tistory.com/51)에서 허프만 코딩이 무엇인지 알아보았고, 허프만 코드를 생성하는 방법과 허프만 코드가 "더 짧은 심벌 트릭"에서 적절한 심벌이 될 수 있는 이유에 대해 알아보았다. 이번 시간에는 허프만 코드를 이용해 실제 압축과 추출을 구현하기 위한 전체 과정을 살펴보려고 한다. 크게 "압축"과 "추출" 두 가지 동작에 대해 설명할 것이다. (추가로 동작이 제대로 이루어졌는지 확인하기 위한 "검증"도 필요할 수 있다) 압축: 입력받은 문자열을 압축하여 새로운 문자열을 생성 추출: 입력받은 문자열에서 원래 문자열 추출 전체 과정을 살펴본 다음, 문자열이 주어졌을 때, 각각의 과정의 결과가 어떻게 되는지 설명하려고 한다. 먼저 전체 과정은 다음과 같.. 허프만 코딩 1 - 허프만 코드 구하기 허프만 코딩(Huffman Coding)은 이전 포스팅(https://taeminator1.tistory.com/49)에서 언급한 "더 짧은 심벌 트릭(shorter-symbol trick)"의 일종이다. 더 짧은 심벌 트릭은 압축하려는 문자열에서 자주 사용되는 문자일수록 짧은 심벌을 부여하여 압축하는 방법이다. 허프만 코딩은 이러한 심벌을 허프만 코드를 이용해서 압축하는 방법이다. 허프만 코딩의 핵심은 아무래도 허프만 코드를 구하는 것이다. 허프만 코드를 구하는 방법을 살펴보기 전에, "더 짧은 심벌 트릭"에서 "심벌"이 되기 위한 조건을 살펴보자. 다음과 같은 두 가지 조건이 있다. 빈도수가 많을수록 심벌의 자릿수가 적어야 한다 임의의 심벌이 다른 심벌의 첫 부분이 아니어야 한다 먼저 첫 번째 조건은.. 데이터 압축 압축은 기존의 데이터를 변형하여 더 적은 용량을 갖는 데이터로 만드는 데에 그 목적이 있다. 물론 압축 결과로 생기는 부가 데이터 등으로 인해 데이터의 용량이 늘어나는 경우도 있지만 기본 목적은 데이터 용량을 줄이는 것이다. 이러한 압축은 데이터의 손실 여부에 따라 두 가지로 나눌 수 있다. 압축 후 추출하는 과정에서 데이터 손실이 발생했다면 손실 압축, 그렇지 않다면 무손실 압축이다. 백업 파일을 저장할 때, 때때로 압축 프로그램을 쓴다. 일반적으로 데이터의 용량이 줄어들고 하나의 파일로 묶을 수 있어 데이터 관리나 전송을 용이하게 한다. 이렇게 압축된 데이터를 풀면 압축하기 전 그대로의 데이터를 얻을 수 있다. 무손실 압축이 적용된 것이다. 또 다른 예로 인터넷 사이트에서 동영상을 다운로드할 때, 화.. [Swift]Random Surfer Trick 동작 확인 이전 포스팅에서 Random Surfer Trick을 직접 구현해 보았다(https://taeminator1.tistory.com/39). 이번 포스팅에서는 실제 출력된 결과를 바탕으로 분석을 해보려고 한다. 이후 등장하는 표의 예제 결과는 repeatNumber를 10만으로 하고(실제 예제에서는 100만으로 하였지만 백분율이어서 10을 나눠 10만으로 표기하였다), surfPossiblity를 15로 설정한 결과이다. 먼저 실행 횟수에 따라 결과에 차이가 있었다. 1000번을 반복할 경우, 실행할 때마다 변화율의 차이가 심했지만, 실행 횟수가 증가할수록 변화율에 큰 변화가 없었다. 변화율의 관점에서 봤을 때, 100000번 정도가 적당한 것으로 판단되어 이후 실행부터 repeatNumber를 10000.. [Swift]Random Surfer Trick 구현 구글의 검색엔진이 어떻게 세계 최강의 자리에 단시간에 오를 수 있었을까?? 존 매코믹은 "미래를 바꾼 아홉 가지 알고리즘"에서 그 이유 중 하나로 "Page Rank" 알고리즘을 꼽는다. 초창기 구글은 검색엔진을 사용하는 사용자에게 유용한 정보를 제공하기 위해, 두 가지 큰 절차를 따랐다. 첫 번째로 인덱싱이고 두 번째가 페이지 랭크이다. 인덱싱은 페이지에 포함되어 있는 단어들(HTML을 구성하는 텍스트들)의 페이지별 위치를 구성하는 기술이고, 페이지 랭크는 사용자가 입력한 내용이 포함된 페이지들 중에 어떤 페이지를 우선적으로 보여줄 것인지(높은 순위로 매길지)에 대한 기술이다. 이번 포스팅에서는 Page Rank의 다양한 알고리즘 중에서 Random Surfer Trick을 구현해 보려고 한다. Ran.. 이전 1 2 다음
