awk와 함께하는 algorithm·programming language - huffman coding(1)

발단

프로그래밍 언어로서의 awk는 언어 자체가 제공하는 기능이 상당히 제한된 언어 중에 하나이다. 특히 object, function이 1급 객체가 주는 편리함은 awk를 이용하여 코딩을 하다보면 몸소 깨닫게 된다. 어떻게 보면 c언어 보다도 제한적인데, 그 이유는 언어 자체에서 제공하는 collection은 associative array 하나이고 무엇보다 data type을 사용자가 정의할 수 있는 방법이 없다는 점에서 그렇다(awk에서는 c에서 제공하는 struct 조차 존재하지 않는다). 그리고 awk의 유일한 collection data type인 associative array는 다음과 같은 제한을 가지고 있다:

associative array의 value는 scalar여야 한다(associative array의 value로 associative array 불가).
associative array를 return 할 수 없다.

이 중 후자는 그래도 c언어에서 익숙한 방식으로 out parameter를 이용하거나, call by reference으로 전달된 parameter 자체를 수정하는 방식으로 처리한다 해도 첫 번째 제한이 치명적이다. 왜냐하면 object의 배열을 허용하지 않기 때문에, 동적으로 생성되는 구조를 가진 객체—객체를 표현할 수 있는 유일한 수단이 associative array이니 필연적으로 associative array로 표현됨—를 배열로 관리할 수 없기 때문이다. 즉, awk는 객체의 배열을 허용하지 않는다. 이러한 이유로 같은 구조를 가진 복수 개의 객체를 표현 해야하는 상황에서 p1, p2 등으로 각 객체를 변수로 다루는 것 외의 방법을 생각해 내지 못했고, 이 방법은 동적으로 생성되는 객체를 다룰 수 없기 때문에 지금까지 awk를 이용하여 알고리즘이나 자료구조가 요구되는 코딩에 사용할 수 없는게 오랜 아쉬움이었다.

그래서 huffman.awk의 다음 코드를 보았을 때 한번에 이해가 가지 않았지만 오랫동안 바랐던 그 해결책이었다는 것을 어렴풋이 짐작할 수 있었다:

# Tree stored as parallel arrays:
#   ch[i]   leaf char (empty for internal nodes)
#   fr[i]   frequency
#   lo[i]   leftmost char in subtree (tie-break)
#   lc[i]   left child id
#   rc[i]   right child id

# 중략

  for (c in freq) {
    nn++
    ch[nn] = c; fr[nn] = freq[c]; lo[nn] = c
    lc[nn] = 0; rc[nn] = 0
    active[nn] = 1
  }

# 중략

  if (lc[node] == 0 && rc[node] == 0) {
    code[ch[node]] = (prefix == "" ? "0" : prefix)   # single-char text edge case
    return
  }

이 코드의 의미가 무엇일지 한 3일 정도 생각해 보다가 한 번 각 잡고 이해해 보니 다음과 같은 대응이 성립한다는 것을 알게 되었다:

note

node.ch <-> ch[node]
node.rc <-> rc[node]
node.lc <-> lc[node]

where `node` in rhs represents node_id

Struct of Array(SoA), Array of Struct(AoS)

코딩의 입문이 c나 python이 일반적인 시대에서, 객체의 instance는 속성을 가지는 변수로 간주된다. c의 struct 조차도 node->ch 와 같은 표현으로 이를 강조하고(node["ch"] in python, node.ch in java), node라는 객체가 하위 member(혹은 field)를 소유하는 것으로 인식하는 것은 당연하게 받아들여진다. 이 당연함으로 인하여 객체를 표현하는 다른 방법이 있다는 것을 쉽게 떠올릴 수 없었다.

객체, 변수, 메모리주소

python에서의 객체를 생각해보자. python에서 사용자가 생성한 객체를 print 해보면 __str__, __repr__을 명시적으로 구현하지 않는 한, 디폴트 구현인 object의 __str__가 호출되고 이는 해당 객체의 메모리 주소를 반환한다. 잠시 프로그래밍 수업 시간을 떠올려보면, 값은 메모리에 존재하고 변수는 그 메모리주소를 부르는 별칭이라고 할 수 있다. 객체의 경우 그 값은 힙에 존재하며 객체를 변수로 저장했다면 원칙적으로 객체의 값은 변수로도, 직접적인 메모리 주소로도 접근 할 수 있다. 조금 다른 관점에서 보면 sqlite3의 각 row에 암시적으로 부여되는 oid 혹은 _rowid_, oracle에서 select할 때 접근 할 수 있는 rowid도 row라는 객체를 나타내는 표현, 혹은 일종의 변수명이라고 이해할 수 있다.

필드 값을 어떻게 얻을까?

사용자 정의 data type을 지원하는 언어의 메모리구조 그 중에서도 c의 struct를 생각해보자. item이라는 struct가 3개의 member f1(int), f2(char), f3(double)로 구성되어 있다고 하자. 새로운 item 변수를 만들 때 프로그램은 sizeof int, sizeof char, sizeof double을 묶은 메모리 영역을 할당하고 최상단 주소값을 변수명에 바인딩한다. 이때 객체의 필드 값에 관심이 있다고 하자. 변수로 저장한 객체의 특정 필드 값은 어떻게 접근할까? 우리는 이미 방법을 알고 있다. 변수를 이용해 객체의 메모리 주소로 접근해서, 대상이 되는 필드만큼의 offset 만큼 이동하여 값을 찾으면 된다. 코드로 나타내면 item.f1에서 일어나는 일을 말로 풀어서 쓴 것 뿐이다.

여기서 잠시 생각해보자. item.f1으로 필드 값에 접근 할 때, 무슨 일이 벌어진 것일까? 필요했던 정보는 두 가지다. 변수로 표현한 메모리 주소, 그리고 대상 필드. 메모리 주소와 필드를 알면 값이 나오니 다음 함수를 생각해 볼 수 있다. getFieldValue: M x F → V, where M is memory address, and F is field, V is the value 여기서 getFieldValue는 변수와 필드를 받아서 필드 값을 반환하는 함수이다. 위에서 언급한 것과 같이, 메모리 주소는 변수로도 주소값(종종 object id로 표기되는) 그 자체로도 표현될 수 있다. 개념적으로 <object id of node>.ch로도 같은 값을 나타낼 수 있다는 말이다. 조금만 더 생각해 보면, 만약 어떤 방법을 쓰던 상관없이 값만이 관심사라고 한다면 필드의 값을 반환하는 함수는 getFieldValue만 있는 것은 아니다. getFieldValue': F x M → V, where M is memory address, and F is field, V is the value 처럼 필드를 먼저 생각하고 메모리 주소를 받아 필드 값을 얻을 수도 있다. 즉 (변수, 필드, 값)을 (필드, 변수, 값) 로도 필드 값에 접근할 수 있다는 말이다. 여기서 변수는 결국 메모리 주소를 나타내고 메모리 주소는 object id 혹은 id로도 표기할 수 있으므로 (필드, 주소, 값) 혹은 (필드, object id, 값)로 바라 볼 수 있다는 이야기이다. 여기서 중요한 생각의 전환이 일어난다. 객체는 여러개의 필드로 구성된다를 여러개의 필드를 모으면 동등한 객체를 표현할 수 있다는 것이다.

struct of array

이제 사용자 정의 객체의 배열을 생각해보자. 우리에게 익숙한 객체지향 사고방식에서 사용자 정의 data type 객체의 배열을 만들면(혹은 프로그램이 사용자정의 객체를 한 곳에 모아 배열처럼 관리한다고 가정하면) 이는 객체에 해당하는 한 단위의 메모리 구조를 가진 item으로 구성된 배열이 되고 이것이 array of struct이다. 사용자 정의 데이터 타입을 지원하지 않는 언어에서는 어떻게 객체의 배열을 표현할까? 위의 생각의 전환을 적용하면 된다. 객체 그 자체를 만드는 것이 아니다. 객체와 동일하게 해석되는 구조를 만들고 object id를 이용해 객체를 우회적으로 표현하는 것이다. 구체적으로는 각 필드마다 배열을 할당해서 객체마다 increasing seqence로 구성된 id를 부여하고 객체의 각 필드를 나타내는 배열에서 같은 id를 이용해 조회하면 된다는 것이다. 코드로 보자면 item 의 배열 중 2번째 element는 다음과 같이 3개 변수의 조합으로 나타낸다. f1[2], f2[2], f3[2] ↔ item[2] where item[2].f1 = f1[2], item[2].f2 = f2[2], item[2].f3 = f3[2]. 이것이 사용자 정의 data type을 지원하지 않는 언어에서 객체의 배열을 나타내는 방법인 struct of array 이다.

사실, 우리는 struct of array를 이용해 객체를 표현하는 예시를 자주 접할 수 있다. 다만 객체를 field 들의 모음으로 생각하지 못했 던 것 뿐이다.

pandas나 parquet 같은 열지향 데이터구조를 이용해 원본 row를 재구성 하는 경우
sqlite3나 oracle에서 rowid를 이용해 row에 접근하는 경우 (row는 각 필드 배열의 rowid를 이용해 얻은 값을 그러모아 만든 객체로 볼 수 있다.)

여기까지 오면 for 문 안의 nn++; ch[nn] = c; fr[nn] = freq[c]; lo[nn] = c; lc[nn] = 0; rc[nn] = 0의 의미가 node를 생성하는 것임을 이해할 수 있다. 특히 필드마다 배열을 두고 id를 이용해 객체를 재구성하는 방식의 좋은 점은, id가 단일한 값(보통 increasing sequence)으로 관리 되기 때문에 다른 객체의 id를 값으로 가지는 필드를 사용자 정의 객체에 두면 associative array의 값이 나타내는 id가 associative array를 간접적으로 표현할 수 있다는 점이다. 그리고 note를 참고하면 code[ch[node]] 는 code of node.ch를 의미하는 것을 이해할 수 있다.

huffman coding with awk

이제 우리는 awk에서 객체를 표현할 수 있는 방법을 알았으므로, 사용자 정의 데이터타입이 없어서 풀지 못했던 알고리즘 문제를 awk를 이용해 풀 수 있다(왜 awk로 풀어야 하는지는 묻지 말자. 취향이다). 허프만 코딩을 생각하자. 허프만 코딩은 문자열 압축 방법 중 하나로 각 문자의 사용 빈도를 이용하여 자주 등장하는 문자일 수록 짧은 코드를 부여하여 문자를 압축하는 기법이다. 먼저 주어진 문자열에서 각 문자의 등장 빈도를 세어 counter 를 만든다. 이후 counter에서 char과 frequency를 이용해 허프만 트리를 구성한다. 허프만 트리는 이진 트리 형태이고 각 노드는 char과 frequency를 데이터로 가지며, left child와 right child로 다른 node를 지정한다. 참고한 구현(huffman.awk)에서는 tie-brake를 위해 leftmost라는 노드의 데이터 필드를 추가한다. 이를 구조로 나타내면 다음과 같다:

struct {
  left: node_id,
  right: node_id,
  char: optional<char>,
  freq: int,
  lefmost: char
} node
with node id: nid

새로운 노드는 다음과 같이 생성한다:

function node_new(ch, fq, l, r, lm) {
  _nid++ # node 객체가 생성될 때마다 부여하는 global node id 변수
  char[_nid] = ch
  freq[_nid] = fq
  left[_nid] = l ? l : 0 # left child가 있다면 지정, 없다면 센티넬 0
  right[_nid] = r ? r : 0 # right child가 있다면 지정, 없다면 센티넬 0
  leftmost[_nid] = lm ? lm : ch # leftmost를 직접 지정했다면 그 값으로, 없다면 노드 문자와 같은 값으로 지정
  return _nid # 새로 생성한 node객체의 id를 반환
}