해밍코드

해밍코드는 오류를 포함할 수 있는 이진 선형 블록을 보정하는 방법이다. 이와 관련된 코딩 문제를 하나 풀어보도록 하자. 일단 문제는 다음 주소에 있다. www.codewars.com/kata/5ef9ca8b76be6d001d5e1c3e/julia

Codewars: Achieve mastery through challenge

이 문제를 줄리아로 풀면서 몰랐던 것을 제법 알게 되어 정리해본다. 문제는 기본적으로 아스키문자로 구성된 문자열을 암호화하고 복호화하는 것이다. 이 때 암호화된 데이터에 오류가 있는 경우에 오류를 복원하는 기능을 포함하는 것이다. 문제에서는 암호화함수와 복호화 함수를 모두 작성해야 한다.

문제에서는 기본적으로 암/복호화 함수의 알고리듬을 알려준다. 이대로 구현만해도 되고 자신이 알고리듬을 직접 설계해도 된다. 먼저 암호화 함수의 알고리듬은 다음과 같다.

1. 문자열의 모든 글자를 각각 이스키 코드값으로 변환한다.
2. 각코드값을 2진수로 변환한다.
3. 각각의 비트를 3번씩 늘린다 ( 101 -> 111000111 )
4. 전체를 결합한다.

이렇게 만들어진 암호화 데이터는 0과 1이 각각 3번씩 반복될 것이다. 그런데 만약 데이터가 손상된다면 000 이 100 이나 010, 001 등으로 변경될 수 있다는 것이다. (비트의 일부가 잘린 것은 고려하지 않는다.) 3개씩 반복되어야 할 마디에 다른 숫자가 섞여 있다면 더 많은 숫자로 판단한다. 010 은 0이고 101, 110 등은 1로 보겠다는 의미이다.

암호화함수

줄리아의 문자열은 for 문에서 각 글자를 반복하는 것이 가능하고, 이것은 문자열 자체가 반복자처럼 행동할 수 있다는 것이다. 그렇다면 collect() 함수를 사용해서 문자열을 문자(Char)들의 배열로 바꾸는 것이 가능하다는 이야기이다. 이렇게 문자의 배열을 만든 후에는 각 문자를 변환하는 처리를 거친 후 join()하여 하나의 문자열로 만들면 된다. 개별 문자를 처리하려면 먼저 각 문자의 아스키코드값을 비트문자열로 만들어야한다.

줄리아의 문자열은 유니코드 문자열이고, 개별 문자는 4바이트의 유니코드 코드포인트값이다. 따라서 bitstring() 함수를 사용하면 문자를 곧바로 비트문자열로 변환가능하다. 하지만 Char 타입은 4바이트이기 때문에 bitstring() 결과에서 앞 8자리만 취해야 한다.

각 문자를 반복하는 것은 repeat() 함수를 쓰면 된다. repeat('c', 3) -> "ccc"가 되는 식이기 때문이다. 이 동작을 맵핑하면 될 것 같다.

let s = "01011001"
  t = map(s) do c
        repeat(c, 3)
  end
  println(join(t))
end

그런데 이 코드는 제대로 작동하지 않는다. 문자열은 문자의 배열과 다르기 때문이다. 따라서 collect() 함수를 써서 문자의 배열로 만들어야 한다.

let s = "01011001"  
  t = map(collect(s)) do c  
    repeat(c, 3)  
  end  
  println(join(t))  
end

이 때, 물론 취향의 문제이긴 한데 괄호가 많이 중첩되거나 하는 것이 썩 마음에 들지 않기 때문에 파이프(|>)를 사용해서 처리 순서대로 코드를 작성해보려고 한다. 특히 맵핑의 경우 집합 .|> 함수의 형태로 만들 수 있기 때문에 제법 깔끔해보인다.

let s = "01011001"
  s |> collect .|> (c -> repeat(c, 3)) |> join |> println
end
000111000000111000111000

문자열의 각 글자에 대해서 위 연산을 처리해하니, 역시 같은 방식으로 collect()로 쪼개고 변환해서 합쳐주면 되겠다.

function encode(str)
  enc(c) = let s = bitstring(c)[1:8]
    s |> collect .|> (c -> repeat(c, 3)) |> join
  end
  str |> collect .|> enc |> join
end

#  encode("hey")
#  "000111111000111000000000000111111000000111000111000111111111111000000111"

암호화함수는 이렇게 간단했다. 그런데 복호화함수부터는 조금 어려운 부분이 나온다. 앞에서부터 3개씩 끊어서 써야하는 것이다. 배열을 일정한 길이만큼 잘라주는 걸 보통 partition()이라 하는데, 파이썬에서는 파티션해주는 내장함수나 기본라이브러리 함수가 없다.(대신에 간단히 만들 수 있긴하다.) 줄리아에서는 두 가지 방법이 있다. 기본 모듈 중에서 Iterators 모듈이 있는데, 이 모듈에서 private하게 정의된 partition() 함수가 있다. 이 함수는 이터레이터를 리턴하기 때문에 for 문에서 쓸 것이 아니면 역시 collect()를 써서 배열로 바꿔야 한다.

k = encode("h")
Iterators.partition(k, 3) |> collect .|> join 
"000" "111" ...

좀 더 색다른 방법으로는 해당 배열을 3행짜리 2차원 배열로 바꾸는 것이다. 다차원 배열에 대해서는 map() 대신 mapslices()를 사용하면 각 마디에 대해서 개별적인 맵핑을 취할 수 있다. 즉,

1) reshape(x, 3, :) 로 3행짜리 배열을 만든다.
2) mapslices(arr, dims=1) do .. end 로 각 열의 오류를 처리하고 1차월 배열로 만든다.
3) 2의 결과로 코드값을 만들고 이것으로 Char를 생성한다.

먼저 3글자간의 마디를 변환해서 코드로 만드는 과정을 살펴보자.

let bits = "000111111000111000000000"
  # code <- 3글자씩 잘라서 더 많은 값으로 마디를 변환하고, 다시 8비트씩 자른다.
  codes::AbstractArray{UInt8, 2} = let dups = reshape(bits |> collect, 3, :)
    nodups = mapslices(dups, dims=1) do col
      count(==('1'), col) > 1 ? 1 : 0
    end
    reshape(nodups, 8, :)
  end

  # 0, 1의 배열을 2진법으로 정수로 결합
  bits2num(bs) = reduce(bs) do x, y; (x << 1) | y; end
  mapslices(bits2num, codes, dims=1) .|> Char |> join
end
# "h"

위 과정이 실질적인 복호화함수가 된다. 3행 행렬로 만들고 여기에 각 열에서 '1', '0' 중에서 더 많은 문자로 값을 맵핑하도록 변경한다. count() 함수는 count(조건, 배열)의 형태로 쓰는데, 여기서 '조건'이 비교 대상이 아닌 비교 함수로 되어 있다. 좀 불편하긴 하지만, 람다식을 쓰기 보다는 ==(x) 의 형태로 사용하면 좀 더 간단하게 쓸 수 있다. 이 결과를 다시 8비트씩 모으기 위해서 8행으로 reshape하여 codes 를 생성한다.

이제 codes의 각 열은 하나의 문자를 만들기 위한 비트이다. 앞에서부터 각 비트는 왼쪽으로 시프트한 후 다음 비트를 OR 연산으로 합쳐서 정수값으로 변환할 수 있다. 이 과정을 맵핑해주고 결과를 다시 Char()로 맵핑하여 최종적인 문자열을 만들 수 있게 된다.

function decode(bits)
  # code <- 3글자씩 잘라서 더 많은 값으로 마디를 변환하고, 다시 8비트씩 자른다.
  codes::AbstractArray{UInt8, 2} = let dups = reshape(bits |> collect, 3, :)
    nodups = mapslices(dups, dims=1) do col
      count(==('1'), col) > 1 ? 1 : 0
    end
    reshape(nodups, 8, :)
  end
  # 0, 1의 배열을 2진법으로 정수로 결합
  bits2num(bs) = reduce(bs) do x, y; (x << 1) | y; end
  mapslices(bits2num, codes, dims=1) .|> Char |> join
end