영어사전에서 영어단어 검색 속도 (2)
옥스포드 영어사전에 등재되어 있는 영어단어 수는 약 30만(3 x 10의5승)개 라고 알려져 있습니다.
일상생활에서 통용되는 단어(방언, 신조어 등..)들까지 합하면 약 100만(10의6승)개의 단어가 있다고 예측해 봅니다.
영어단어 100만개, 한글단어 100만개를 서로 연결한 자료구조로 컴퓨터 메모리에 영한-한영 사전을 구축했을 때
검색 속도에 대해서 다시 정리해 봅니다.
요즘 컴퓨터의 CPU 처리속도는 보통 수 GHz 입니다.
즉, CPU 내부에서 1 클럭(디지털 신호가 On/Off로 변화되는 클럭)은 약 10의-9승초(0.001마이크로초) 걸린다는 것입니다.
CPU 제조사 마다 조금씩 다르겠지만, 1개의 기계명령이 10클럭으로 설계되었다면,
하나의 명령을 수행하는데 0.01 마이크로초가 소요됩니다.
여기서, 하나의 문자를 비교하는데 10개의 기계명령이 필요하다면,
하나의 문자 비교에 0.1마이크로(10의-7승)초가 소요됩니다.
영어단어가 평균 10개의 문자로 구성되었다고 보면,
하나의 영어단어를 비교하는데 약 1마이크로(10의-6승)초가 걸린다고 계산할 수 있습니다.
그렇다면, 컴퓨터 메모리에 100만개의 영어단어가 저장되어 있다고 할때,
하나의 영어단어를 순차 검색하는데 소요되는 시간은 아래와 같이 쉽게 산출해 볼 수 있습니다.
(1) 최선의 경우: 영어단어 1번 비교 --> 1마이크로(10의-6승)초
(2) 최악의 경우: 영어단어 100만번 비교 --> (10의6승) x (10의-6승) --> 1초
(3) 평균: 최악의 경우 / 2 --> 0.5초
위의 결과는 100만개의 단어를 컴퓨터 메모리에 배열형태로 쭉 나열했을때의 자료구조를 가정한 결과입니다.
지난 수십년간 컴퓨터 CPU 처리속도는 수백배 빨라졌습니다.
수십년전의 컴퓨터에 100만개의 단어로 영한사전을 구축했었다면
하나의 단어를 검색하는데 평균 50초(약1분)가 걸렸다고 볼 수 있습니다. 영한사전으로서의 효용성이 없는 셈입니다.
아울러, 단어 검색을 좀더 빠르고 효율적으로 할 수 있도록 인덱스화된 자료구조와 알고리즘을 사용하지 못했다면
효용성은 더더욱 떨어집니다.
제가 요즘 컴퓨터에 영한-한영 사전을 새롭게 구축하고 영한번역학습기, 더 나아가 자연어 기계번역에 도전하고 있는 이유는
바로 수백배 빨라진 CPU 처리속도에 효율적인 자료구조와 알고리즘들을 적용할 수 있기 때문입니다.
컴퓨터 자료구조와 알고리즘은 입력 자료구조 형태와 개수에 따라서 처리 효율이 엄청나게 달라집니다.
입력자료 개수가 수천개 이하라면, 특별한 자료구조와 알고리즘을 사용하지 않아도,
요즘의 CPU에서 빠른 결과를 얻을 수 있습니다.
그러나, 입력자료 개수가 수백만~수천만개 이상에서는 효율적인 자료구조와 알고리즘을 적용하지 않으면
유용한 결과를 얻기 힘듭니다.
일단, 가장 대표적인 자료구조인 트리구조로 영한 사전을 구축하는 경우를 생각해 보겠습니다.
BST(Binary Search Tree), RBT(Red-Black Tree), BTree, TRIE... 등은
모두 트리구조에서 파생되어 발전했다고 볼 수 있습니다.
트리구조를 사용하면 위에서 산출한 순차검색에 비해서 얼마만큼 빨라 질까요?
DBMS에서 많이 사용하고 있는 BTree에 100만개의 단어를 인덱스화 시키면,
BTree의 깊이(height)는 log(10의6승) --> 6이 됩니다.(order가 10인경우)
따라서, BTree에서는 단어를 최소 6번, 최대 6번 x order --> 60번만 비교하면 되고,
위에서 예로든 CPU 클럭으로 시간을 산출하면,
(1) 최소: 6번 비교 --> 6 x 1마이크로초 --> 6마이크로초
(2) 최대: 60번 비교 --> 60 x 1마이크로초 --> 60마이크로초 --> 0.06미리초
100만개의 단어중에서 하나의 단어를 검색할때 최대 0.06미리초만에 검색해 낼 수 있다는 것입니다.
영한-한영 사전을 이 정도의 빠르기로 구축한다면, 영한-한영 문장 번역도 가능하지 않을까요?
문장 번역은 여러개의 알고리즘들을 깊이 있게 적용해야 된다고 봅니다.
문장 번역을 위한 연구들이 많이 진행되고 있을듯 합니다.
가장 선도적으로 구글 번역기가 있구요.
문장 번역을 위해서 또 어떤 제품들이 나와 있을까요?
번역의 정확성은 어느 정도이고, 신뢰할만한 번역을 위해서는 어떤 것들이 필요할까요?
from 알지비(rgbi3307(at)nate.com) on the www.kernel.bz
.
말하기에 앞서, 말씀하신 tree 예제의 경우 '시간복잡도가 O(log n) 이다' 라고 합니다. 시간복잡도가 O(log n)이란, 주어진 데이터 수가 n일 때 필요한 연산 횟수를 f(n)이라고 정의할 때, 모든 1 < n에 대해 f(n) < k log n이 성립하는 어떤 상수 k를 정할 수 있다는 것을 의미합니다.
사전의 속도가 빠른 것과 translation의 속도가 빠른 것은 별개의 문제라고 생각합니다.
차이점을 생각해 봅시다.
dictionary의 경우 literal과 뜻이 1 : 1매칭이 됩니다. 동음이의어가 있을 경우 1:m 매칭이 될 수 있겠습니다만 이 때 동음이의어 중에서 무엇을 골라내는지는,
1) m의 수가 매우 적고
2) 동음이의어 중 "사람이 현재 상황에 맞다고 생각하는걸 판단하기 때문에"
짧은 시간 내에 항상 자신이 원하는 단어의 뜻을 찾아낼 수 있습니다.
언어간의 문장 번역은 위에서 2)번의 영역이 컴퓨터로 들어갑니다. 예를 들어봅시다.
"내가 지금 걸린 이것이 감기다." <- 질병의 의미의 감기 + -(이)다
"줄이 마구마구 감기다." <- 감다의 의미의 감-기-다
여기서 '감기다'는 두 가지 의미가 있습니다. 그 중 무엇이 옳은지에 대한 선택은 문장 내에서의 문법 요소, 문장이 다루고 있는 내용을 넘어서 문맥, 심지어 인간의 상식까지 감안되어야 올바른 결정을 내릴 수 있습니다.
즉, 사전과 번역은 별개의 문제다, 이정도로 요약이 될까요ㅎㅎ
수십년 전에 유럽에서 자국의 언어 간에 translation을 할 때 단어를 사전을 이용해 1 : 1 변환으로 translation을 구현한 적 있다고 하지만..ㅋㅋ
한글과 관련된 제대로된 문장번역 애플리케이션은 아직 랩 수준 아닌가요?ㅎㅎ 자세히는 저도 몰겠네영
신뢰할 만한 번역 알고리즘을 만들기 위해서는 '공부'가 필요하지 않을까요
저도 10년전에는 컴퓨터를 사용한 문장 번역은 어렵지 않을까?
생각했습니다.
학창시절 전산과 전자공학을 전공했는데 영어로 된 기술 서적들이 많이 난해했습니다.
그래서 영어공부도 병행했구요. 가끔 저의 전공과 영어, 2가지를 다 살리는 방향으로
컴퓨터 문장 번역 프로그래밍을 시도 하기도 했습니다.
그때는 학창시절의 습작 정도에 그쳤고, 제가 공부한 영어문장을 데이터 파일에 저장시켜
조회하는 수준의 프로그램 이었죠. 지금도 그때 C언어로 작성했던 프로그램을
꺼내 보고 웃음짓곤 한답니다.
그러나 요즘 자료구조와 알고리즘을 다시 공부하면서, 이것을 잘 응용하고 개선시키면
문장 번역이 가능하리라는 긍정적인 시각을 가지게 되었습니다.
사람이 언어를 구사하는 것도 학습을 통해서 이루어집니다.
극단적인 예로 청각에 장애가 있는 사람은 말도 하지 못합니다.
즉, 청각을 통해서 들은 언어를 머리에 축적시켜 놓지 못하면 꺼내 쓸 수 있는 말도 없게 됩니다.
사람은 요람에서 무덤까지 이르면서 수많은 언어를 듣고 학습합니다.
사람의 두뇌 세포들은 엄청난 저장 용량과 논리적인 판단 능력이 있는 것 같습니다.
시청각을 통해서 학습한 수십만개의 단어들을 논리적으로 조합하여 언어를 구사 하니까요...
그럼 우리가 구사하고 있는 문장의 개수는 몇개나 될까요? 요즘 저는 여기에 관심이 많습니다.
그냥 통크게 퉁 쳐서 다음과 같이 계산해 보겠습니다.
(1) 사전에 등재되어 있는 단어(어휘)의 개수 --> 30만개
(2) 문장 개수 --> 단어의 조합 순열 --> 30만!(팩토리얼)
30만 팩토리얼 이라는 수는 아마 컴퓨터로 계산할 수 없는(데이터 표현 범위 벗어남)
천문학적인 수이지만, 팩토리얼을 계산하는 컴퓨터 알고리즘에 넣어서 정수형이나
더블형의 데이터 타입이 아닌 숫자 문자열로 출력하면 가능할 것 같습니다.
아마, 컴퓨터 화면을 숫자로 가득 채울듯 합니다.
조만간 이것을 계산한 결과를 한번 보여드리겠습니다. 별로 어렵지 않습니다.
(이미 계산한 분이 계시다면 한번 공개해 주세요)
사람의 두뇌 세포들은 이러한 어마어마한 저장용량을 가지고 있고,
게다가 논리적인 판단을 통해서 단어(어휘)들을 문법에 맞게 조합하여
사물을 보는 순간 아주 눈 깜짝할정도의 속도로 문장들을 표현합니다.
실로 엄청난 능력을 가지고 있습니다.
사람의 두뇌를 컴퓨터의 CPU와 메모리에 비유합니다.
컴퓨터의 논리회로는 사람의 두뇌 세포라 볼 수 있습니다.
제가 생각해 볼때, 컴퓨터의 CPU와 메모리는 수십년내로 사람의 두뇌 세포 용량만큼
증가할 수 있다고 봅니다. 이론적으로 머 그렇게 어렵지도 않습니다.
두뇌 세포에 해당하는 논리회로(TTL 트랜지스터) 배열을 계속 증대 시켜 나가면 되니까요...
계산해 보면,
현재 32비트 컴퓨터는 2의32승 --> 4 x 10의9승 --> 40억
64비트 컴퓨터는 2의64승 --> 16 x 10의18승 --> 16000000...(0이 18개 붙어 있는수) --> 16해
128비트 컴퓨터는 2의128승 --> 256 x 10의36승 --> 25600000000... (0이 36개 붙어 있는수) --> 256??
256비트 컴퓨터는... 아마 엄청난 크기의 수를 표현할 수 있고,
메모리도 엄청 늘어날 것입니다.
이러한 하드웨어적인 발전을 보면 머지 않아 사람의 두뇌 세포 용량을 따라 잡을 것입니다.
문제는, 사람의 논리적인 생각처럼 컴퓨터에 자료구조와 알고리즘을 심어주는 것입니다.
저는 여기에 관심이 있습니다.
자료구조와 알고리즘을 공부하다 보면, 아주 단순한 원리에서 부터 출발합니다.
이 원리를 잘 활용하고 개선하면 어렵지 않습니다.
문장 번역을 위한 맞춤형 자료구조와 알고리즘은 구현될 수 있다고 생각합니다.
단, 제가 현재 진행하고 있는 것들은 몇가지 사용자적인 이해가 있어야 합니다만...
조만간 좀더 정립해서 글을 올려 보도록 하겠습니다.
From:
*알지비 (메일: rgbi3307(at)nate.com)
*커널연구회(http://www.kernel.bz/) 내용물들을 만들고 있음.
*((공부해서 남을 주려면 남보다 더많이 연구해야함.))
> 사람이 언어를 구사하는 것도 학습을 통해서
> 사람이 언어를 구사하는 것도 학습을 통해서 이루어집니다.
> 극단적인 예로 청각에 장애가 있는 사람은 말도 하지 못합니다.
언어에 해당하는 소리를 내기가 힘들죠. 언어를 구사하는 능력에 문제가 있진 않아요.
> 즉, 청각을 통해서 들은 언어를 머리에 축적시켜 놓지 못하면 꺼내 쓸 수 있는 말도 없게 됩니다.
언어학에서 사십년도 더 전에 하던 얘길 하시면;;; 축적시켜서 꺼내 쓰는 걸로 구현이 되면 애저녁에 구현했게요. 혼자 생각하시는 것도 좋지만 현대 (전산)언어학 책 조금이라도 읽어보시는게 좋지않을까요? 영구기관 만드는 스타일로 갈 가능성이 농후할 거 같아요. 역설적이게도 프로그래밍 언어들의 이론적 기반을 제공한 노암촘스키가 반복해서 강조한 부분이고, 단순한 원리를 활용하고 개선해서 풀리는 문제가 아니에요.
tj 님께서 쓰신 것에 조금 보충을 하자면 ...
청각에 장애가 있는 경우도 학습을 통해서 말을 할 수 있게 됩니다.
또한, 청각에 장애가 있다고 하더라도 학습 속도가 느릴 뿐이지, 언어를 머리속에 축적시켜놓고 꺼내어 쓸 수 있습니다. 청각에 장애가 있다고 하여 말을 못하는 것은 아닙니다. 교육을 받으면 가능합니다. - 상당한 수준의 인내심과 시간이 걸립니다만 ... 또한, 그러다보니 비용도 많이 들어갑니다. 보통 시간당 12 ~ 20만원이 넘어갑니다. 하루 2 ~ 3시간 정도이고, 일주일에 2 ~ 3 번정도 받아야 하는데... 그 정도만 돼도 경제적 부담이 상당하지요.
독순술 이라는 게 있고, 청각장애가 있는 사람들은 상대방이 말하는 입술 모양을 보고 그 사람이 어떤 말을 하는지 배우고 그 입술 모양과 성대 움직임 이런 것을 배워서 어렵지만 발음을 할 수 있습니다.
그래서 청각장애인중 상당수는 비장애인들과 대화할 때 사람 눈을 보고 대화하는 게 아니라, 상대방의 입을 보고 대화하고, 어두워져서 안 보이면 대화를 못하는 경우가 많습니다.
---------
귓가에 햇살을 받으며 석양까지 행복한 여행을...
웃으며 떠나갔던 것처럼 미소를 띠고 돌아와 마침내 평안하기를...
- 엘프의 인사, 드래곤 라자, 이영도
즐겁게 놀아보자.