String(3-way quicksort, huffman 코딩)

 

3-way quicksort 알고리즘이다.

문자를 비교해서, 문자가 더 작으면 위로, 더 크면 아래로 보내서 (작은거)(같은거)(큰거)로 나눈다.

이렇게 나누어놓은 문자열들끼리 또 정렬하도록 한다.(재귀)

public class QuickSort3Way {
    public static void sort(String[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(String[] arr, int low, int high) {
        if (high <= low) return;
        int lt = low, gt = high;
        String v = arr[low];
        int i = low;

        while (i <= gt) {
            int cmp = arr[i].compareTo(v);
            if (cmp < 0) swap(arr, lt++, i++);
            else if (cmp > 0) swap(arr, i, gt--);
            else i++;
        }

        sort(arr, low, lt - 1);
        sort(arr, gt + 1, high);
    }

    private static void swap(String[] arr, int i, int j) {
        String tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        String[] arr = { "Quicksort", "is", "a", "divide", "and", "conquer", "algorithm" };
        QuickSort3Way.sort(arr);
        for (String str : arr) {
            System.out.println(str);
        }
    }
}

코드는 간단하다. 다만 헷갈렸던 부분이 있는데,

        while (i <= gt) {
            int cmp = arr[i].compareTo(v);
            if (cmp < 0) swap(arr, lt++, i++);
            else if (cmp > 0) swap(arr, i, gt--);
            else i++;
        }

여기서 else if부분, swap(arr,i,gt--);를 하는데, i++해줘야하는것이 아닌가? 라는 생각을 했었다.

차근차근 확인해보니...

저 스왑이 일어나게되면 맨 아래에있는 문자열과 현재 문자열을 교환하게되는데, 맨 아래에 있던 문자열은 아직 비교하지 않은 문자열이므로, i를 증가시키게 되면 해당 문자열을 비교하지 못하고 넘어가게된다. 따라서 i는 ++하지 않아야한다.

 

---

Huffman 코딩

1. **트리에 대한 비트 스트림 작성하기:**

   Huffman 코딩을 이용해 파일을 압축하려면 먼저 파일 내의 각 문자(또는 기타 데이터 단위)의 빈도를 계산해야 합니다. 이 빈도를 이용해 Huffman 트리를 생성합니다. 

   Huffman 트리는 최소 힙을 이용해 만들 수 있습니다. 가장 빈도수가 낮은 두 노드를 선택하여 새로운 부모 노드를 만들고, 이 부모 노드의 빈도수는 두 자식 노드의 빈도수 합이 됩니다. 이 과정을 트리가 하나의 루트 노드만 남을 때까지 반복합니다.

   이렇게 생성된 트리에서, 각 문자에 대응하는 코드를 얻을 수 있습니다. 루트에서 해당 문자를 가지는 노드까지 왼쪽 경로를 '0', 오른쪽 경로를 '1'로 표시하면, 이 경로가 해당 문자의 Huffman 코드가 됩니다.

   이제 이 트리를 비트 스트림으로 변환할 차례입니다. 트리의 전위 순회를 이용해 각 노드를 방문하고, 각 노드를 방문할 때마다 노드가 잎인지(leaf node) 아닌지에 따라 다른 비트를 출력합니다. 예를 들어, 잎 노드는 '1'과 그 뒤에 따르는 문자에 대한 ASCII 코드를 출력하고, 잎이 아닌 노드는 '0'을 출력합니다. 이렇게 생성된 비트 스트림이 트리를 표현하는 비트 스트림이 됩니다.

2. **비트 스트림 읽기:**

   압축된 파일을 해제하려면 먼저 트리를 표현하는 비트 스트림을 해석해야 합니다. 이를 위해 앞서 설명한 방법을 반대로 적용합니다.

   비트 스트림을 처음부터 읽기 시작합니다. '0'을 만나면 새로운 내부 노드를 만들고, '1'을 만나면 그 다음에 오는 문자에 대한 ASCII 코드를 읽어

 새로운 잎 노드를 만듭니다. 이렇게 트리를 재구성한 후, 나머지 비트 스트림을 이 트리를 이용해 해석하면 원래의 파일 내용을 복구할 수 있습니다.

 

지피티가 설명을 잘 해주길래 가져왔다.

---