태그 보관물: 파이썬

편집거리 (단어의 유사도 분석)

편집거리 구하기

computer라는 단어와 commuter라는 단어는 매우 유사한데, p -> m으로 한글자만 변경하면 처음 단어에서 두 번째 단어로 바뀌게 된다. 비슷하게 sport라는 단어는 sort라는 단어로 바꾸기 위해서는 p 한글자를 지우면 된다. 혹은 sort에서 p한 글자를 추가하면 된다.

편집거리는 두 문자열 s1, s2에서 몇 번의 추가/삭제/변경으로 변환할 수 있는가를 나타내는 개념이다. 이러한 변경에는

  1. 글자를 교환하기
  2. 글자를 삽입하기
  3. 글자를 삭제하기

의 세 종류의 변경 연산을 할 수 있다. 이를 이용해서 두 단어 사이의 편집거리를 구하는 재귀 함수를 생각해보자.

d('', '') = 0 -- 빈 문자열은 0번
d(s, '') = d('', s) = |s| -- 빈문자열로 변경하는데는 s의 길이만큼의 삭제필요
d(s1+ch1, s2+ch2)
 = min( d(s1, s2) + if ch1 = ch2 then 0 else 1, -- 교환
        d(s1+ch1, s2) + 1, -- 삽입
        d(s2, s2+ch2) + 1  -- 삭제
      )

먼저 빈 문자열 두 개 사이의 편집거리는 0이다. 그리고 한글자로 된 문자열과 빈 문자열 간의 편집거리는 당연히 1이다. 그렇다면 빈 문자열과 길이가 n인 문자열의 편집 거리는 n이 된다.

이제 길이가 0이 아닌 두 문자열의 편집거리를 보자. 두 단어 springprint를 예로 들어보겠다.

  1. 변경: sprin + gprin + t로 볼 때 sprin -> prin으로 변경한 후 g -> t로 바꾸는 변경을 1회 수행한다. 이 때 편집거리는 d(sprin, print) + 1이 될 수 있다. 만약 마지막 글자가 동일하다면 1이 아닌 0을 더한다.
  2. 추가: 혹은 springprint + t로 본다면 spring -> prin으로 변경한 후 t를 추가하는 것이므로 편집거리에 1을 더한 d(spring, prin) + 1이 될 수도 있다.
  3. 삭제: 반대로 sprin + gprint로 본다면 sprin -> print로 변경한 후 g를 삭제하는 것이므로 d(sprin, print) + 1이 될 수 있다.

결국 두 단어의 최소 편집 거리는 변경, 추가, 삭제에 의한 결과 중에서 최소값을 사용한다. 그리고 이는 점점 작은 단위로 내려가서 비교하게 되기에 동적계획법으로 풀어낼 수 있다. 이 단계를 추적해보자.

각 단어에 맨 앞에 공백을 추가한 후 각 원래 단어는 글자를 세로로, 목적지가되는 단어는 가로로 배치하면 아래와 같은 표가 나온다.

# | #  p  r  i  n  t
--------------------
# | 0
s |
p |
r |
i |
n |
g |

이 표의 처음 등장하는 0은 바로 빈 문자열에서 빈 문자열로 바꿀 때의 편집거리이다. 그리고 그 오른쪽으로 빈 문자열에서 각 글자까지의 단어로 변경하는데 필요한 편집거리는 ‘추가’의 케이스만 있으므로 1씩 증가한다.

# | #  p  r  i  n  t
--------------------
# | 0  1  2  3  4  5
s |
p |
r |
i |
n |
g |

이번에는 0의 아래방향을 보자. 여기서는 왼쪽끝에 있는 글자까지의 단어가 빈 문자열이 되기 까지의 편집거리이다. 따라서 s는 한 번의 삭제, sp는 두 번의 삭제가 일어난다. 이 때 sp는 한 번 삭제하면 s가 되므로 s -> #의 편집거리인 1에 1을 더한 값이다. 이런식으로 첫 열을 완성할 수 있다.

# | #  p  r  i  n  t
--------------------
# | 0  1  2  3  4  5
s | 1  *
p | 2
r | 3
i | 4
n | 5
g | 6

이제 위의 표에서 *가 위치한 곳을 보자, 여기는 s -> p로의 편집거리를 쓴다. 여기에는 세 경우가 있다.

  1. s를 삭제한 후 p를 추가한다. => 1 + 1 (표에서는 왼쪽칸 + 1)
  2. p를 추가한 후 s를 삭제한다. => 1 + 1 (표에서는 위쪽칸 + 1)
  3. s -> p로 치환한다. => 0 + 1 (표에서는 대각선 왼쪽위 + 1)

이 중 최소거리는 1이므로 *의 자리에는 1이 들어가고 그 오른쪽으로는 1씩 증가한 값이 들어간다. (이들 칸에서도 사실 위와 같은 과정을 통해서 값을 구한다) 그 결과는 아래와 같고, 이를 통해 s -> print는 6회의 편집거리를 갖는다는 것을 알 수 있다.

# | #  p  r  i  n  t
--------------------
# | 0  1  2  3  4  5
s | 1  1  2  3  4  5
p | 2  *
r | 3
i | 4
n | 5
g | 6

두 번째 줄을 계산해보자. sp -> p로 바꾸는 작업이다.

  1. 먼저 *의 왼쪽에서 오른쪽으로 가면서 1을 더한다. 이는 sp -> # 변경 한 후에 p를 추가하는 것을 말하면 이 때의 편집거리는 3(2 + 1)이다.
  2. 혹은 p를 삭제한 후 s -> p 변환을 한다. 이건 2(1 + 1) 이다.
  3. p가 서로 같으므로 sp -> ps -> #의 편집거리와 동일하다. 이 경우에는 1이다.

그리고 이 중 가장 작은 값은 1이므로 *칸에 1을 쓴다. 그리고 그 오른쪽으로는 r, i, n, t를 붙이는 작업이므로 1씩 증가한다.

# | #  p  r  i  n  t
--------------------
# | 0  1  2  3  4  5
s | 1  1  2  3  4  5
p | 2  1  2  3  4  5
r | 3  2  1  2  3  4
i | 4
n | 5
g | 6

같은 방식으로 sprp, pr, pri, prin, print로 변경하는 최소편집거리를 계산하여 다음 줄을 채운다. 당연히 같은 글자가 있으면 왼쪽 위 칸의 값과 같은 값이 최소 거리가 될 것이며, 그렇지 않은 경우에는 왼쪽칸 + 1, 위쪽 칸 + 1, 왼쪽위칸 + 1 한 값 중 가장 작은 값을 쓴다. 이 규칙을 이용해서 나머지 칸을 계속 채워나간다.

# | #  p  r  i  n  t
--------------------
# | 0  1  2  3  4  5
s | 1  1  2  3  4  5
p | 2  1  2  3  4  5
r | 3  2  1  2  3  4
i | 4  3  2  1  2  3
n | 5  4  3  2  1  2
g | 6  5  4  3  2  2

최종적으로 spring -> print의 최소편집거리는 2로 계산되었고 이 과정을 보면

  1. s를 삭제 (2행 1열)
  2. p, r, i, n는 그대로 둔다. (-> 6행 5열)
  3. g -> t로 변경 (7행 6열)

이 되는 셈이다.

최소거리로 증가하는 경로를 따를 수 있는 루트가 2개 이상이 경우도 얼마든지 있다.

두 문자열의 길이에 각 1을 더한 곱 만큼 크기의 배열이 필요한데, 어차피 맨 마지막의 두 행만 사용하게 되므로 파이썬으로 구현은 다음과 같이 작성할 수 있다.

def edit_distance(s1, s2):
    l1, l2 = len(s1), len(s2)
    if l2 > l1:
        return edit_distance(s2, s1)
    if l2 is 0:
        return l1
    prev_row = list(range(l2 + 1))
    current_row = [0] * (l2 + 1)
    for i, c1 in enumerate(s1):
        current_row[0] = i + 1
        for j, c2 in enumerate(s2):
            d_ins = current_row[j] + 1
            d_del = prev_row[j + 1] + 1
            d_sub = prev_row[j] + (1 if c1 != c2 else 0)
            current_row[j + 1] = min(d_ins, d_del, d_sub)
        prev_row[:] = current_row[:]
    return prev_row[-1]

여러 단어들을 비교할 때 각 단어간의 편집거리를 알면 단어의 유사성을 파악할 수 있다. 구글 검색 등에서 검색어에 오타를 낸 경우에 올바른 단어를 찾아줄 수 있는 것도 보통은 한 글자를 잘못 치거나 덜치거나 더친 경우이기 때문에 편집거리가 1~2로 비교적 짧은 오타단어와 정상단어 사이의 관계를 이용해서 제시할 수 있는 원리이다.

(추가) 아래는 Swift3로 구현한 편집거리 계산 함수이다. 2차원 배열을 사용했고, 특정 인덱스의 글자를 뽑아내기 위해서 String 타입을 확장했다.

http://swiftlang.ng.bluemix.net/#/repl/579e9ca06563d8d9272a3ac6

파이썬 커맨드라인 실행방법

Windows7 명령줄도구에서 파이썬 스크립트 실행하기

기본적으로 파이썬을 설치하면 PATH 환경변수에 파이썬의 설치 경로가 추가된다. 이를 확인해보려면 명령프롬프트를 열고 path라고 입력한다음 엔터.

d:\temp>path
PATH=.......;C:\python34\;C:\python34\scripts\;........

여기서 C:\python34눈 파이썬 인터프리터인 python.exe가 설치되어 있는 곳이고, C:\Python34\Scripts는 그외 파이썬의 부가패키지의 실행파일들이 설치된다. 다른 패키지를 내려받고 설치하도록 도와주는 pip같은 것들이 여기에 설치된다고 보면 된다.

윈도 환경변수 PATH는 실행파일이 있는 위치를 지정하여, 실행파일의 전체 경로를 적지 않고도 해당 파일이 실행될 수 있도록 한다. 파이썬의 설치경로가 PATH에 포함되어 있다면 명령줄 도구에서 파이썬 스크립트를 다음과 같이 실행할 수 있다.

d:\temp> python mycalc.py 1 + 3
4
# 이 때 mycalc.py 는 d:\temp\ 에 위치한다.

OSX나 리눅스에서는 보통 기본적으로 파이썬이 설치되어 있고, 주로 /usr/bin/python이나 /usr/local/bin/python 등의 경로로 설치되어 있다.

py, pyw

환경변수 설정에 어려움을 겪는 사람들이 많아서인지, 요즘의 파이썬 설치 패키지에는 py.exe라는 파일이 포함되어 있다. 이 파일은 파이썬 인터프리터를 실행해주는 역할을 하며, C:\Windows 폴더에 들어가게 된다. 보통 이 경로는 기본적으로 PATH에 포함되어 있기 때문에 다음과 같이 실행해도 된다.

d:\temp> py mycalc.py 1 + 3
4

py.exe는 특히 파이썬이 2개 이상 버전으로 등록된 경우에 유용하게 쓸 수 있다. 예를 들어 파이썬 2.7과 3.4가 동시에 설치되어 있고, 이중 2.7이 PATH에 포함되어 있다면,

  • py : 디폴트 설정 버전을 실행한다.
  • py -2 : Python 2.x 대 버전을 실행한다.
  • py -3 : Python 3.x 대 버전을 실행한다.

PATHEXT

하지만 파이썬 스크립트를 실행할 때 매번 앞에 python 이나 py를 붙이는 것도 귀찮을 때가 있다. 배치 파일 같은걸 만들어서 쓰는 사람도 있을 수 있겠지만, 윈도에서 리눅스처럼 스크립트명 만으로 해당 스크립트를 실행할 수 있다.

리눅스나 OSX에서는 파이썬 소스코드 맨 첫줄에 #! python, #!/usr/bin/python 등으로 인터프리터 명령이나 경로를 지정해놓으면, 해당 인터프리터로 알아서 실행된다. 이는 펄, 루피, JS 스크립트등 모든 스크립트에 대해서 공통적으로 지원되는 기능이다.

파이썬 설치시에 .py 파일을 파이썬과 연결할 것이냐는 걸 물어보는데 (보통은 그냥 체크하고 넘어갈테다) 이 옵션을 사용해서 설치했다면 아마 설정이 되어 있을 것이다.

윈도 환경변수중에는 PATHEXT라는게 있는데, 이는 특정 확장자를 가진 파일을 실행가능한 것으로 인식하게끔한다. 윈도 명령행에서 각 환경변수는 %를 앞뒤로 붙인 이름으로 인식한다.

d:\temp>echo %PATHEXT%
.COM;.EXE;.BAT;.CMD;.VBS..... ;.PYW;.PY

위 와 같은 식으로 .PYW, .PY가 등록되어 있다면 mycalc.py 라는 스크립트는 다음과 같이 실행할 수 있다는 의미이다.

d:\temp> mycalc.py 2 + 3
....?

실행이 되면 좋겠다. 하지만 모든 시스템의 상태가 동일하다고 보장할 수는 없으니 실행이 안되는 사람도 있을 수 있다. 물론, 많은 경우에는 py 명령이면 충분하겠지만, 스크립트 이름만으로 실행하고픈 사람이라면 아마 파이썬으로 여러가지 도구를 만들어서 쓰려는 사람일것이니, 약간의 도움을 주겠다.

assoc, ftype

윈도에서는 특정 파일의 확장자가 어떤 파일인지를 식별하고, 어떻게 실행할 것인지를 따로 저장해서 관리한다. 명령줄에서 이를 확인하고 변경할 수 있는 명령이 assoc, ftype이다.

assoc 명령은 특정 확장자 파일이 어떤 형식인지를 시스템으로부터 알아내거나 이를 변경할 수 있다. 파이썬과 관련된 확장자와 그 파일타입은 다음과 같은 값이 있다.

  • .py=Python.File
  • .pyc=Python.CompiledFile
  • .pyw=Python.NoConFile

이 명령을 어떻게 쓰는지 궁금하면 /?를 붙여서 실행해본다. 물론 MS프로그램의 도움말은 30년전부터 그다지 도움은 되지 않는게 대부분이다.

d:\temp>assoc /?
파일 확장명 연결을 보여주거나 수정합니다.

ASSOC [.확장명=[파일 유형]]

  .확장명   파일 유형과 연결할 파일 확장명을 지정합니다.
  파일 유형 파일 확장명과 연결할 파일 유형을 지정합니다.

현재 파일 연결을 보려면 매개 변수 없이 'ASSOC'라고 입력합니다.
ASSOC가 파일 확장명만 가지고 불려진 경우, 해당 파일 확장명에 대한 현재
파일 연결을 보여줍니다. 파일 유형에 대해 아무 것도 지정하지 않으면
명령은 해당 파일 확장명의 연결을 제거합니다.

이제 assoc 명령을 아무런 인자없이 실행하면 전체 리스트를 보여준다.

d:\temp> assoc
...
...

근데 양이 엄청 많을 것이다. 뭐 인내심이 강한 사람이라면 assoc | more와 같이 실행해서 하나하나 찾는 방법이 있겠지만, 우리는 바쁘니까 다음과 같이 실행한다.

d:\temp>assoc | findstr ".py"
.py=Python.File
.pyc=Python.CompiledFile
.pyo=Python.CompiledFile
.pys=pysFile
.pyw=Python.NoConFile

만약 여기에 .py=Python.File이 없다면? 아래와 같이 연결을 만들어준다.

d:\temp>assoc .py=Python.File
.py=Python.File

이제 다음은 ftype으로 해당 타입의 파일을 어떻게 실행할 것인지를 정해준다. 역시 ftype은 assoc과 비슷한 사용법을 가지고 있다. 먼저 파일 타입 연결을 확인한다.

d:\temp>ftype | findstr "python"
Python.CompiledFile="C:\Python34\python.exe" "%1" %*
Python.File="C:\Python34\python.exe" "%1" %*
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Python.NoConFile="C:\Python34\python.exe" "%1" %*

대충 위외 비슷한 값이 나오면 된다. Python.File="C:\Python34\python.exe" "%1" %*이 부분이 가장 중요하다. 만약 없거나 다르게 되어 있다면 수정하도록하자. 단, 여기서 C:\Python34는 파이썬의 설치 경로여야 한다. 파이썬을 다른 데 설치했으면 알아서 잘 변경하도록 하자.

d:\temp>ftype Python.File="C:\Python34\python.exe" "%1" %*
Python.File="C:\Python34\python.exe" "%1" %*

레지스트리

여기까지 했을 때 잘되면 좋은데, 그래도 안되는 경우가 있다. 이건 다 윈도때문인데, 윈도는 레지스트리에 이런 정보를 또 따로 저장하는데, 이게 위에서 설정한 것과 안 맞으면 안되는 경우가 있다. (안맞아도 되는 경우도 있다!)

그래서 이게 안되면 레스트리 편집을 해야하는데, 여기서는 힌트만 주겠다. 왜냐면 레지스트리 편집을 부주의하게 하는 경우, 시스템이 정상작동하지 않는 불상사가 생길 수 있는데 그 책임을 내가 대신 져줄 수는 없기 때문이다. “나는 레지스트리를 잘 모른다” 하는 사람은 그냥 좀 불편해도 py 명령 정도로 만족하고 지내도록 하자.

  1. HKEY_CLASSES_ROOT\.py 키의 값이 Python.File 인지 확인한다.
  2. HKEY_CLASSES_ROOT\Applications\python.exe\shell\open\command 키의 값이 "C:\Python34\python.exe" "%1" %*인지 확인한다.
  3. 일부 시스템의 경우에는 HKEY_CLASSES_ROOT\py_auto_file\shell\open\command 이 키를 참조하여 실행하는 경우가 있다. 역시 "C:\Python34\python.exe" "%1" %*라는 값이 들어가 있는지 확인한다.

일단 여기까지 하면

d:\temp> mycalc 1 + 3
4

와 같이 파이썬 스크립트를 일반 명령처럼 쓸 수 있고, 자신이 생각하기에 유용하다 생각되는 스크립트는 어디 한 군데 몰아놓고 PATH에 추가해두면 유용하게 쓸 수 있다. 나의 경우, 명령줄에서 간단한 수식을 계산할 수 있는 calc.py나 우리 동네 대기 오염 정보를 가져와서 출력해주는 스크립트 등을 만들어서 한군데 모아놓고 사용하고 있다.