KR100424130B1

KR100424130B1 - 데이터 압축 장치, 데이터베이스 시스템, 데이터 통신시스템, 데이터 압축 방법, 기억 매체 및 프로그램 전송장치

Info

Publication number: KR100424130B1
Application number: KR10-2001-0003131A
Authority: KR
Inventors: 마루야마히로시; 다무라겐토; 우라모토나오히코
Original assignee: 인터내셔널 비지네스 머신즈 코포레이션
Priority date: 2000-02-04
Filing date: 2001-01-19
Publication date: 2004-03-24
Also published as: JP3368883B2; US7043686B1; CN1316828A; EP1122655A2; JP2001217720A; EP1122655A3; KR20010078015A; CN1166072C; TW501350B

Abstract

XML이나 ASN.1 등의 트리 로컬 언어에서 문서의 구조 부분에 부호화를 행하는 데이터 압축을 실현한다.

데이터를 부호화하여 압축하는 데이터 압축 장치로서, 데이터가 라벨을 지닌 트리 구조로 표현되는 트리 로컬 언어의 문법 규칙(12)과, 이 트리 로컬 언어로 기재된 문서를 읽어들여, 이 문서를 구조와 콘텐츠로 나누고, 문법 규칙(12)을 이용하여 이 구조를 부호화하는 인코더(11)와, 이 인코더(11)에 의해서 추출된 이 문서의 콘텐츠를 압축 부호화하는 압축기(13)를 구비한다.

Description

데이터 압축 장치, 데이터베이스 시스템, 데이터 통신 시스템, 데이터 압축 방법, 기억 매체 및 프로그램 전송 장치{DATA COMPRESSION APPARATUS, DATABASE SYSTEM, DATA COMMUNICATION SYSTEM, DATA COMPRESSION METHOD, STORAGE MEDIUM AND PROGRAM TRANSMISSION APPARATUS}

본 발명은 XML이나 ASN.1 등의 트리 로컬 언어로 기재된 문서를 압축하는 데이터 압축 방법에 관한 것이다.

XML(Extensible Markup Language)는 문서의 의미 구조를 간단한 마크로 기재(마크업)하는 마크업(markup) 언어의 일종이다. XML에서는 문법을 규정하여, 문서의 구성 요소에 논리적 의미를 갖게 함으로써, 사용자가 독자의 확장을 실행하는 것이 가능하다. 이 때문에, 인터넷에서 데이터 교환에 이용하는 데이터 포맷으로서 기대되고 있다.

XML에는 DTD(문서형 정의 : Document Type Definition)라는 개념이 있어서, 어떤 DTD에 관해서, 문서가 타당(valid)한지의 여부를 판정할 수 있다. 구체적으로는, 예컨대, <BOOK>이라는 노드의 아래에는 <TITLE>, <AUTHOR>, <PUBLISHER>이라는 노드가 이 순서로 각각 1회씩 나타난다고 하는 문법 규칙을 규정한다. 그리고, 소정의 문서가 타당한지 어떤지, 즉, 그 문법 규칙에 의거하고 있는지의 여부를 판정할 수 있다.

XML 문서의 구조는 형식 언어적으로는, 트리 언어 중의 트리 로컬이라 불리는 클래스에 속한다. 트리 로컬 언어란, 데이터가 라벨을 지닌 트리 구조로 표현되고, 또한, 올바른 데이터가 트리의 각 노드 라벨에 대하여 자(子) 노드(child node) 라벨의 정규 언어로 규정되는 식의 트리 언어이다. 즉, 트리 로컬 언어에서는 소정의 문법(XML에 있어서는 DTD로 규정된다)에 속하는 트리의 집합이, 각 노드의 자 노드의 리스트를 규정하는 정규 언어에 의해서 결정지어진다. 이런 종류의 트리 로컬 언어로서는 그 외에, ASN.1(Abstract Syntax Notation 1) 등이 있다.

최근, XML을 이용하여, 네트워크 상의 리소스나 HTML에서는 실현 불가능했던 복잡한 데이터 구조를 기재하여, 비즈니스 어플리케이션을 구축하는 움직임이 확산되고 있다. 이러한 시스템에서는 대규모의 XML 문서가 어플리케이션 사이에서 교환되는 것을 예상할 수 있다.

일반적으로, 데이터 교환을 하거나 데이터베이스에 데이터를 저장하거나 할 때는 송신 효율의 향상이나 저장하는 데이터 파일의 사이즈를 축소하기 위해서, 데이터 파일을 압축한다. 이 때문에, 여러 가지 데이터 포맷에 대하여 적용할 수 있는 범용적인 데이터 압축 기술이나, 특정한 데이터 포맷으로 특화된 데이터 압축 기술 등이 많이 제안되고 있다. 따라서, XML 문서의 교환에 있어서도 이들 데이터 압축 기술을 적용하는 것을 생각할 수 있다. 또한, XML 문서는 태그 명 등에 상당한 리던던트 용도가 있기 때문에, 높은 압축율을 기대할 수 있는 데이터 구조라고 말할 수 있다.

전술한 바와 같이, 데이터 교환을 하거나 데이터베이스에 데이터를 저장하거나 할 때는 데이터 파일을 압축하는 것이 일반적이다. 그리고, XML 등의 트리 로컬 언어에서는 태그 등의 문서 구조를 나타내는 정보 부분에 대하여 높은 압축율을 기대할 수 있다.

예컨대, 데이터 통신에 있어서, 통신 당사자가 문법 G를 공유하고 있고, 서로 상기 문법 G에 대하여 타당한 XML 문서만을 주고받는 것이 보증되는 경우를 생각한다. 또, 전술한 바와 같이 문법 G에 있어서, <BOOK>이라는 노드의 아래에는 <TITLE>, <AUTHOR>, <PUBLISHER>이라는 노드가 이 순서로 각각 1회씩 나타난다고 하는 문법 규칙이 규정되어 있는 것으로 한다. 이 경우, XML 문서의 수신자는 수신한 XML 문서 중에서, 예컨대 <BOOK>이라는 태그를 검출한 경우에, 그 최초의 자 노드는 <TITLE>이라고 예측할 수 있다. 따라서, <TITLE>이라는 정보는 이 가정에서 리던던트이다. 이러한 생각을 이용함으로써, 메시지 길이를 최적화하는 것과 같은 XML 문서의 인코딩 방법이 가능하다. 이것은 XML에 한하지 않고, 임의의 트리 로컬 언어(예컨대, ASN.1)에 대하여도 마찬가지이다.

그러나, 종래, 이러한 트리 로컬 언어에 있어서의 문서의 구조 부분을 부호화하는 압축 방법은 아무 것도 제안되어 있지 않았다.

그래서, 본 발명은 XML이나 ASN.1 등의 트리 로컬 언어에 있어서의 문서의 구조 부분의 부호화를 행하는 데이터 압축을 실현한다.

또한, 본 발명은 트리 로컬 언어로 특화하는 동시에, 다른 범용적인 데이터 압축 기술과 병용함으로써, 높은 압축율을 기대할 수 있는 데이터 압축 방법을 제공한다.

도 1은 본 실시 형태에 있어서의 문서 압축 시스템의 전체 구성을 설명하는 도면.

도 2는 본 실시 형태에 의한 데이터 압축의 순서를 설명하는 도면.

도 3은 본 실시 형태에 있어서의 인코더의 구성을 설명하는 도면.

도 4는 본 실시 형태의 처리 대상인 XML 문서의 예를 나타내는 도면.

도 5는 도 4의 XML 문서에 있어서의 구조를 나타낸 도면.

도 6은 본 실시 형태에서 이용하는 문법 규칙의 예를 나타내는 도면.

도 7은 도 6의 문법 규칙으로 구축되는 푸시다운 오토머톤(automaton)을 나타내는 도면.

도 8은 푸시다운 오토머톤을 이용한 문법의 체크 수법을 설명하기 위한 구문 트리를 예시적으로 나타낸 도면.

도 9는 도 7의 푸시다운 오토머톤을 이용하여 생성된 부호화 트랜스듀서를 나타낸 도면.

도 10은 도 8의 구문 트리에 대하여 타당성 검증을 한 결과를 예시적으로 나타낸 도면.

도 11은 도 7과 동일한 푸시다운 오토머톤을 이용하여 생성된 복호화 트랜스듀서를 나타낸 도면.

도 12는 속성을 갖는 DTD를, 속성을 갖지 않는 DTD로 변환한 상태를 설명하는 도면.

도 13은 속성을 갖는 XML 문서를, 속성을 갖지 않는 XML 문서로 변환한 상태를 설명하는 도면.

도 14는 본 실시 형태를 데이터 통신 시스템에 적용한 경우의 구성을 설명하는 도면.

도 15는 본 실시 형태를 데이터베이스 시스템에 적용한 경우의 구성을 설명하는 도면.

<도면의 주요 부분에 대한 부호의 설명>

11 : 인코더

12, 22 : 문법 규칙

13 : 압축기

21 : 복원기

23 : 디코더

201 : XML 문서

202 : 구조

203 : 부호화 데이터 열

204 : 콘텐츠

205 : 압축된 XML 문서

이러한 목적 하에, 본 발명은, 데이터를 부호화하여 압축하는 데이터 압축 장치로서, 데이터가 라벨을 지닌 트리 구조로 표현되는 트리 로컬 언어의 문법 규칙을 저장한 문법 저장부와, 이 트리 로컬 언어로 기재된 문서를 읽어들여, 이 문서를 구조와 콘텐츠로 나누고, 문법 저장부에 저장된 문법 규칙을 이용하여 이 구조를 부호화하는 인코더와, 이 인코더에 의해서 추출된 이 문서의 콘텐츠를 압축 부호화하는 압축기를 구비하는 것을 특징으로 하고 있다. 트리 로컬 언어란, 데이터가 라벨을 지닌 트리 구조로 표현되고, 또, 올바른 데이터가 트리의 각 노드 라벨에 대하여 자 노드 라벨의 정규 언어로 규정되는 식의 트리 언어이다.

여기서, 이 인코더는 처리 대상인 문서를 구조와 콘텐츠로 나누는 분할 처리부와, 문법 규칙에 대응하는 푸시다운 오토머톤(automaton)을 구축하는 오토머톤(automaton) 구축부와, 이 오토머톤 구축부에 의해 구축된 상기 푸시다운 오토머톤(automaton)을 이용하여, 상기 분할 처리부에 의해 분할된 상기 문서의 구조에 대한 구문 해석을 행하여, 상기 구조의 부호화된 데이터 열을 생성하는 부호화 데이터 생성부를 구비하는 것을 특징으로 한다.

또한, 이 인코더의 부호화 데이터 생성부는 오토머톤 구축부에 의해 구축된 이 푸시다운 오토머톤 중에 존재하는 선택지(選擇肢)에 대하여 부호를 할당하여, 이 푸시다운 오토머톤을 작동시켜 트리 로컬 언어로 기재된 문서의 구조를 해석했을 때에 이 선택지의 부위에서 선택된 선택지에 할당되어 있는 부호를 출력함으로써, 이 구조의 부호화 데이터 열을 생성하는 것을 특징으로 한다. 이와 같은 구조로 하면, 태그 등의 라벨을 이용하여 기재된 이 문서의 구조를 간단한 부호 열로 변환(부호화)하는 것이 가능해진다.

푸시다운 오토머톤을 이용하여 문서의 구조를 해석할 때는 이 문서의 트리 구조를 깊이 우선으로 탐색하면서 해석을 한다. 즉 부(父) 노드(parent node)로부터의 거리가 같은 계층마다 해석해 나가는 것이 아니라, 깊이 방향의 노드끼리의 관계(부자(父子) 관계)(parental relationship)를 우선시켜 트리를 탐색하면서 해석한다.

또한 여기서, 압축기는 이 트리 로컬 언어로 기재된 문서의 콘텐츠와 함께, 인코더에 의해 부호화된 이 문서의 구조에 대하여도 압축 부호화를 행하는 것을 특징으로 한다. 이 압축기에 의한 압축 수법은 특별히 제한은 없고, 종래부터 이용되고 있는 범용적인 수법을 채용할 수 있다. 인코더에 의해 문서 구조를 부호화한 결과, 어느 정도 규칙적인 데이터 열을 얻을 수 있는 경우는, 이 부호화 데이터 열에 대하여, PKZIP 등의 범용적인 수법을 이용하여 더욱 압축 부호화를 행함으로써, 높은 압축율을 기대할 수 있다. 그래서, 문서의 콘텐츠를 압축할 때에, 이 부호화 데이터 열을 합쳐서 압축하는 것이 바람직하다.

또한, 같은 문서에 있어서의 구조의 부호화 데이터 열과 콘텐츠를 결합한 뒤에 압축을 행함으로써, 구조와 콘텐츠가 다른 파일이 되는 것을 피할 수 있기 때문에, 파일 관리에 있어서도 바람직하다.

또, 본 발명은, 통신 네트워크를 통해 데이터 송신을 하는 송신측 데이터 처리 장치와, 이 송신측 데이터 처리 장치로부터 송신된 데이터를 이 통신 네트워크를 통해 수신하는 수신측 데이터 처리 장치를 구비한 데이터 통신 시스템으로서, 이 송신측 데이터 처리 장치는, 데이터가 라벨을 지닌 트리 구조로 표현되는 트리 로컬 언어의 문법 규칙을 저장한 제1 문법 저장부와, 이 트리 로컬 언어로 기재된 송신 문서를 읽어들여, 이 송신 문서를 구조와 콘텐츠로 나누고, 제1 문법 저장부에 저장된 문법 규칙을 이용하여 이 송신 문서의 구조를 부호화하는 인코더와, 이 인코더에 의해서 추출된 이 송신 문서의 콘텐츠를 압축 부호화하는 압축기와, 인코더에 의해 부호화된 구조 및 압축기에 의해 압축 부호화된 콘텐츠를 송신하는 송신부를 구비하고, 이 수신측 데이터 처리 장치는, 이 송신측 데이터 처리 장치로부터 송신된 수신하는 수신부와, 송신측 데이터 처리 장치의 제1 문법 저장부에 저장된 문법 규칙과 동일 내용의 문법 규칙을 저장한 제2 문법 저장부와, 송신측 데이터 처리 장치의 압축기에 의한 압축 부호화 수법에 대응하는 복원 수법에 의해, 이 수신부가 수신한 수신 데이터 중 송신 문서의 콘텐츠에 대응하는 데이터를 복원하는 복원기와, 이 수신부가 수신한 수신 데이터 중 송신 문서의 구조에 대응하는 데이터를, 제2 문법 저장부에 저장된 상기 문법 규칙을 이용하여 상기 구조를 복호화하는 디코더를 구비하는 것을 특징으로 한다. 이와 같이, 데이터의 송신측과 수신측에서 미리 공통의 문법 규칙을 준비해 두면, 데이터 통신에 있어서, 트리 로컬 언어로 기재된 문서에 대한 매우 압축율이 높은 압축을 행할 수 있어, 통신 효율을 향상시킬 수 있다는 점에서 매우 우수하다. 또, 비즈니스간 통신에 있어서는 트리 로컬 언어의 문법 규칙으로서 공통의 것을 이용하는 것이 미리 정해지는 것이 일반적이기 때문에, 본 발명을 도입하는 것은 용이하다.

게다가, 본 발명은 데이터를 기억 장치에 저장하여 관리하는 데이터베이스 시스템으로서, 데이터가 라벨을 지닌 트리 구조로 표현되는 트리 로컬 언어의 문법 규칙을 저장한 문법 저장부와, 이 트리 로컬 언어로 기재된 문서를 읽어들여, 이 문서를 구조와 콘텐츠로 나누고, 문법 저장부에 저장된 문법 규칙을 이용하여 이 문서의 구조를 부호화하는 인코더와, 이 인코더에 의해서 추출된 문서의 콘텐츠를 압축 부호화하는 압축기와, 인코더에 의해 부호화된 이 문서의 구조와 압축기에 의해 압축 부호화된 이 문서의 콘텐츠를 저장하는 기억 장치를 구비하는 것을 특징으로 한다.

여기서, 이 압축기는 상기 문서의 콘텐츠와 함께, 상기 인코더에 의해 부호화된 상기 문서의 구조에 대하여도 압축 부호화를 행하는 것을 특징으로 한다. 같은 문서에 있어서의 구조의 부호화 데이터 열과 콘텐츠를 결합한 뒤에 압축을 행함으로써, 높은 압축율을 기대할 수 있고, 또한 구조와 콘텐츠가 다른 파일이 되는 것을 피할 수 있기 때문에, 파일 관리에 있어서도 바람직하다.

또한, 본 발명은, 데이터를 부호화하여 압축하는 데이터 압축 방법으로서, 데이터가 라벨을 지닌 트리 구조로 표현되는 트리 로컬 언어로 기재된 문서를 읽어들여, 이 문서를 구조와 콘텐츠로 나누는 단계와, 이 트리 로컬 언어의 문법 규칙을 이용하여, 이 문서의 구조를 부호화하는 단계와, 이 문서의 콘텐츠를 압축 부호화하는 단계를 포함하는 것을 특징으로 한다.

여기서, 문서의 구조를 부호화하는 단계는, 문법 규칙에 대응하는 푸시다운 오토머톤을 구축하는 단계와, 푸시다운 오토머톤 중에 존재하는 선택지에 대하여부호를 할당하는 단계와, 이 푸시다운 오토머톤을 작동시켜 상기 문서의 구조를 깊이 우선으로 탐색하면서 해석하여, 이 선택지의 부위에서 선택된 선택지에 할당되어 있는 이 부호를 출력하는 단계와, 이 푸시다운 오토머톤을 작동시켜 출력된 이 부호의 열을 이 트리 로컬 언어로 기재된 문서의 구조의 부호화된 데이터 열로서 출력하는 단계를 포함하는 것을 특징으로 한다. 이러한 구성으로 하면, 태그 등의 라벨을 이용하여 기재된 이 문서의 구조를 간단한 부호 열로 변환(부호화)하는 것이 가능해진다.

이 데이터 압축 방법에 있어서, 트리 로컬 언어로 기재된 문서의 구조를 부호화하는 단계에 앞서서, 처리 대상인 이 트리 로컬 언어의 문서의 노드에 속성이 포함되어 있는 경우에, 이 속성을, 이 속성을 갖는 요소의 자 노드로 변환함으로써, 이 트리 로컬 언어의 문법 규칙 및 문서를, 푸시다운 오토머톤으로 다룰 수 있는 트리 구조로 변환하는 단계를 더 포함하는 것을 특징으로 한다. 이와 같이 구성하면, XML과 같이 처리 대상의 문서에 속성이 포함되어 있는 경우에도, 푸시다운 오토머톤을 이용한 구조의 부호화를 할 수 있다는 점에서 바람직하다.

또한, 문서의 구조를 부호화하는 단계의 후에, 범용적인 다른 압축 부호화 수법을 이용하여, 부호화된 문서의 구조를 더욱 압축 부호화하는 단계를 더 포함하는 것을 특징으로 한다. 이와 같은 구성으로 함으로써, 더 높은 압축율을 기대할 수 있다는 점에서 바람직하다.

또, 본 발명은, 컴퓨터에 실행시키는 프로그램을 그 컴퓨터의 입력 수단이 판독할 수 있게 기억한 기억 매체에 있어서, 이 프로그램은, 데이터가 라벨을 지닌트리 구조로 표현되는 트리 로컬 언어로 기재된 문서를 읽어들여, 이 문서를 구조와 콘텐츠로 나누는 처리와, 이 트리 로컬 언어의 문법 규칙을 이용하여, 이 문서의 구조를 부호화하는 처리와, 이 문서의 콘텐츠를 압축 부호화하는 처리를 이 컴퓨터에 실행시키는 것을 특징으로 한다. 이러한 구성으로 하면, 이 프로그램을 인스톨한 온갖 정보 처리 장치에 있어서, 이 트리 로컬 언어로 기재된 문서를 높은 압축율로 압축할 수 있어, 통신 효율이나 기억 효율을 향상시킬 수 있다.

게다가, 본 발명은 컴퓨터에, 데이터가 라벨을 지닌 트리 구조로 표현되는 트리 로컬 언어로 기재된 문서를 읽어들여, 이 문서를 구조와 콘텐츠로 나누는 처리와, 이 트리 로컬 언어의 문법 규칙을 이용하여, 이 문서의 구조를 부호화하는 처리와, 이 문서의 콘텐츠를 압축 부호화하는 처리를 실행시키는 프로그램을 기억하는 기억 수단과, 이 기억 수단으로부터 이 프로그램을 읽어내어 이 프로그램을 송신하는 송신 수단을 구비한 것을 특징으로 한다. 이러한 구성으로 하면, 이 프로그램 전송 장치로부터 이 프로그램을 다운로드하여 인스톨한 온갖 정보 처리 장치에 있어서, 이 트리 로컬 언어로 기재된 문서를 높은 압축율로 압축할 수 있어, 통신 효율이나 기억 효율을 향상시킬 수 있다.

이하, 첨부 도면에 나타내는 실시 형태에 기초하여 본 발명을 상세히 설명한다.

도 1은 본 실시 형태에 있어서의 문서 압축 시스템의 전체 구성을 설명하는 도면이다. 도 1에 있어서, 부호 11은 인코더이며, 압축 대상인 문서를 구조와 콘텐츠로 나누고, 그 구조 부분을, 소정의 기억 장치에 기억된 문법 규칙(12)을 이용하여 부호화한다. 부호 13은 압축기이며, 인코더(11)에 의해 부호화된 구조 부분과, 상기 문서의 콘텐츠 부분을 압축한다. 부호 21은 복원기이며, 압축기(13)에 의해 압축된 문서를 복원한다. 복원기(21)에 의해 복원된 시점에서는 그 문서는, 콘텐츠 부분과 인코더(11)에 의해 부호화된 구조 부분으로 나뉘어져 있다. 부호 23은 디코더이며, 부호화되어 있는 구조 부분을, 소정의 기억 장치에 기억된 문법 규칙(22)을 이용하여 복합화하여, 콘텐츠 부분과 합쳐서, 문서를 복원한다.

본 실시 형태를 데이터 통신시의 데이터 압축에 이용하는 경우는 인코더(11) 및 압축기(13)는 송신측에 놓이고, 복원기(21) 및 디코더(23)는 수신측에 놓이게 된다. 또, 데이터베이스 시스템에 있어서 저장하는 데이터 파일을 압축하기 위해서 이용하는 경우는 데이터의 흐름에 따라서, 인코더(11)가 디코더(23)로서 동작하고, 압축기(13)가 복원기(21)로서 동작한다.

이하, 처리 대상의 트리 로컬 언어로서 XML을 이용하는 경우를 예로 들어 설명한다.

도 2는 본 실시 형태에 의한 데이터 압축의 순서를 설명하는 도면이다. 도 2에 나타내는 본 실시 형태에 의한 데이터 압축 처리에서는 우선, 처리 대상인 XML 문서(201)가 인코더(11)로 읽어들여져, 구조(202)와 콘텐츠(204)로 분해된다. 여기서, 구조(202)란, 상기 XML 문서(201)의 트리 구조, 태그명 및 속성명이며, 콘텐츠(204)란, 상기 XML 문서(201)의 ＃PCDATA 및 속성치이다. XML 문서(201)를 구조(202)와 콘텐츠(204)로 분해하는 것은 구조(202)와 콘텐츠(204)는 통상 전혀 다른 통계적 편차를 가지고 있기 때문에, 독립적으로 압축한 쪽이 효과적 때문이다.

이어서, XML 문서(201)를 분해하여 얻어진 구조(202)가, 인코더(11)에 의해 부호화된다. 구조(202)의 부호화에는 문법 규칙(12)이 이용된다. 여기서는, 처리 대상을 XML 문서로 하고 있기 때문에, 문법 규칙(12)은 DTD에 의해 규정된다. 부호화 처리의 상세한 내용에 관해서는 후술한다. 부호화된 결과인 부호화 데이터 열(203)과 콘텐츠(204)는 압축기(13)에 보내진다.

마지막으로, 압축기(13)에 있어서, 부호화 데이터 열(203)과 콘텐츠(204)가 압축 부호화되고, 이들 데이터를 합쳐서, 압축된 XML 문서(205)가 생성된다. 압축기(13)에 의한 부호화 처리에는 LZ77 등의 이미 알려진 적당한 수법을 이용한다.

여기서, 압축기(13)에 의한 압축 부호화는 주로 콘텐츠(204)에 대하여 행해지게 된다. 그러나, PKZIP 등의 범용적인 압축 부호화 방식은 부호화 데이터 열(203)에 대하여도 유효하다. 후술하는 바와 같이, 본 실시예에서는 부호화 데이터 열(203)은 숫자열로서 출력된다. 따라서, 어느 정도 규칙적인 숫자열인 경우는 높은 압축율을 기대할 수 있다. 그래서, 압축기(13)에서는 콘텐츠(204)와 함께 부호화 데이터 열(203)도 압축 부호화를 행한다. 또, 부호화 데이터 열(203)에 대하여 압축기(13)에 의한 압축을 행할지의 여부는 임의이다. 부호화 데이터 열(203)과 압축기(13)에 의해 압축된 콘텐츠(204)를 단순히 관련짓거나, 또는 결합하여, 송수신하거나, 기억 장치에 저장하거나 하는 식으로 하더라도 좋다.

이상과 같이, 본 실시 형태는 XML 문서(201)에 있어서의 구조(202) 부분을 본 실시 형태에 의한 수법을 이용하여 압축하고, 또한 부호화된 구조(202) 부분과콘텐츠(204) 부분을, 종래의 수법을 이용하여 압축한다. 이 때문에, 본 실시 형태에 의한 데이터 압축은 전체적으로 종래의 여러 가지 압축 수법과 병용하여 행하게 된다.

이상과 같은 식으로 압축된 XML 문서(205)를 복원하는 경우는 전술한 압축 과정의 반대의 과정을 밟아간다. 즉, 우선 복원기(21)에 있어서, 압축기(13)가 압축 부호화에 이용한 수법에 대응하는 수법으로, 부호화 데이터 열(203)과 콘텐츠(204)를 복원한다. 이어서, 디코더(23)에 있어서, 복원된 부호화 데이터 열(203)을, 문법 규칙(12)과 동일한 문법 규칙(22)을 이용하여 복호화한다. 복호화 처리의 상세한 내용에 관하여는 후술한다. 문법 규칙(22)은 DTD에 의해 규정된다. 그리고, 이 복호화 처리에 의해 얻어진 구조(202)와 복원기(21)에 의해 복원된 콘텐츠(204)를 이용하여, XML 문서(201)를 복원한다.

이어서, 본 실시 형태에 의한 XML 문서의 구조에 대한 부호화 처리의 내용을 상세히 설명한다.

여기서는, 처리 대상의 XML 문서는 간단하게 하기 위해, 속성을 포함하지 않는 것으로 하고, XML 문서 중의 모든 실체는 전개되어 있는 것으로 한다. 속성의 취급에 관하여는 후술한다.

도 3은 XML 문서의 구조를 부호화하는 인코더(11)의 구성을 설명하는 기능 블럭도이다. 도 3을 참조하면, 인코더(11)는 처리 대상인 XML 문서(201)를 구조(202)와 콘텐츠(204)로 분할하는 분할 처리부(111)와, 문법 규칙(12)에 기초하여 후술하는 푸시다운 오토머톤을 구축하는 오토머톤 구축부(112)와, 오토머톤 구축부(112)에 의해 구축된 푸시다운 오토머톤을 부호화 트랜스듀서로서 이용하여 구조(202)의 부호화 데이터 열(203)을 생성하는 부호화 데이터 열 생성부(113)를 구비한다.

도 4에 처리 대상으로 하는 XML 문서의 예를 나타낸다. XML 문서의 콘텐츠란, 내용 모델에 있어서의, ＃PCDATA에 해당하는 부분의 문자열의 리스트이다. 즉, 도 4의 XML 문서에 있어서의 콘텐츠는 "String1", "String2", "String3", "String4"라고 하는 4개의 문자열로 이루어지는 리스트이다. 이것은 예컨대, 널 문자로 끝나는 문자열을 늘어놓은 바이트 열로서, 다음과 같이, 컴팩트하게 표현 가능하다(단 "￥0"는 널 문자를 나타낸다).

"String1￥OString2￥OString3￥OString4￥0"

이 문자열은 전술한 바와 같이, 구조 부분과는 별도로 압축 부호화된다.

또, 도 4의 XML 문서에 있어서의 구조는 도 5에 나타낸 바와 같이 된다. 이것은 도 4의 XML 문서 중의 콘텐츠에 해당하는 문자열을 플레스 홀더()로 대체한 것이다.

본 실시 형태에 있어서, 인코더(11)는 분할 처리부(111)에 의해 도 4에 나타내는 XML 문서로부터 도 5에 나타내는 구조를 빼내어, 오토머톤 구축부(112)에 의해 문법 규칙(12)을 이용하여 푸시다운 오토머톤을 구축하고, 부호화 데이터 열 생성부(113)에 의해 상기 푸시다운 오토머톤을 이용하여 상기 구조를 부호화한다. 도 6은 문법 규칙(12)을 규정하는 DTD의 예를 나타낸다.

분할 처리부(111)에 의한 분할 처리후, 오토머톤 구축부(112)는 문법규칙(12)을 이용한 부호화 처리를 위해, 상기 DTD에 대응하는 푸시다운 오토머톤을 구축한다. 도 6의 DTD에 따르면, 요소 A가 나타난 경우는 다음에, 요소 B, 요소 C가 이 순서로 1회씩 나타난 후에 종료하는 것을 나타낸다. 마찬가지로, 요소 B가 나타났을 때는 다음에, 요소 D가 1회 나타난 후에 종료하는 것을 나타낸다. 또한, 요소 C가 나타났을 때는 다음에, 요소 E 또는 요소 F가 0회 이상 나타난 후에 종료하는 것을 나타낸다. 또한, 요소 E가 나타났을 때는 다음에, 요소 G 또는 요소 H 중 어느 한편이 1회 나타난 후에 종료하는 것을 나타낸다.

도 7은 도 6에 나타낸 DTD에 대응하는 자연스러운 푸시다운 오토머톤을 나타낸 도면이다. 또, 비종단(非終端) 기호 D와 G에 관해서는 종단 기호 ＃PCDATA를 취할 뿐인 자명한 룰이기 때문에, 생략한다.

이러한 오토머톤은 문법의 각 비종단 기호에 대해서 애매함 없이 구축할 수 있다. 따라서, 본 실시 형태를 데이터 통신에 이용하는 경우, 송신측과 수신측과의 공통의 DTD로부터는 완전히 동일한 푸시다운 오토머톤을 구축할 수 있다.

통상, 푸시다운 오토머톤은 입력 열의 구문 해석을 하기 위해서 이용된다. 그 의미에서는 이 푸시다운 오토머톤은, 표층의 심볼 열, 즉, #PCDATA(또는 플레스 홀더 "")의 1개 이상의 라인으로 이루어지는 모든 열을 수리한다. 그러나, 해석의 결과 생성되는 구문 해석 트리로서는 예컨대, 구문 트리의 노드 A의 자(子)로서, 노드 B, 노드 C가 이 순서로 나타나야 하다. 또한, 요소 C의 후에는 블랭크 천이(遷移)로 최종 상태로 천이한다. 이와 같이, 이 푸시다운 오토머톤은 해석이 끝난 XML 문서(예컨대, DOM 트리)와 같은, 구문 해석 트리가 문법을 만족하는지 여부의 체크에 이용할 수도 있다.

도 8에 나타내는 구문 트리를 예로 하여, 푸시다운 오토머톤을 이용한 문법의 체크에 관해서 설명한다. 또, 도 8에 있어서, 각 리프의 #PCDATA는 생략한다.

이 구문 트리가 도 6의 DTD에 규정되는 문법에 의해서 생성 가능한지의 여부를 조사하기 위해서는 이 구문 트리의 각 노드에 대하여, 그 노드의 비종단 기호에 대응하는 오토머톤에 의해서, 그 자 노드의 열이 수리 가능한지의 여부를 조사하면 된다. 예컨대, 요소 A는 자 노드로서 BC라는 열을 가지고 있다. 이것은 비종단 기호 A에 대응하는 오토머톤에 의해서 수리된다(도 7의 A 참조). 따라서, 이 부분에 관해서는 문법을 만족하는 것을 알 수 있다. 같은 식으로, 모든 노드에 관해서, 대응하는 오토머톤을 사용하여 Preorder로 트래버스(깊이 우선으로 탐색한다)하면, 문법의 체크는 종료된다.

구문 해석 트리에 대하여, 푸시다운 오토머톤을 이와 같이 사용하는 것을, 이하의 설명에서는 타당성 검증이라고 부른다. 또, 이상의 조작에서 이용하는 각 비종단 기호에 대한 오토머톤에 관하여는, 종료 상태에의 ε 천이를 제외하고, 결정성으로 최소의 오토머톤인 것으로 한다.

이어서, 오토머톤 구축부(112)는 도 7의 푸시다운 오토머톤을, XML 문서의 구조 부분(도 5 참조)을 부호화하는 트랜스듀서, 즉, 문자열의 구문 해석의 오토머톤으로 변환한다.

도 7의 푸시다운 오토머톤에 있어서, 입력을, 4개의 #PCDATA(또는 플레스 홀더 "")로 이루어지는 라인으로 하고, 개시 기호를 A로 하여 해석을 시작하면, 노드 A, 노드 B, 노드 D가 순서대로 만들어지고, 최초의 ＃PCDATA가 인식된다. 다음에, 노드 C가 만들어진 곳에서 선택지가 발생한다. 즉, 노드 E를 만들어야 할지, 노드 F를 만들어야 할지, 그렇지 않으면 노드 C를 이것으로서 끝내 상위의 노드로 되돌아갈지의 3가지이다. 그래서, 이들 3가지의 선택지에, 라벨의 알파벳 순으로 1, 2, 3이라는 번호를 배당한다(라벨 ε는 항상 최후로 결정한다). 같은 식으로, 룰 E의 최초의 상태도, 노드 G를 만들거나 또는 노드 H를 만든다고 하는 선택지를 갖기 때문에, 이들에 관해서도, 1, 2라는 번호를 할당한다. 또, 여기서는 선택지에 번호를 할당한다고 했지만, 선택지의 식별에 이용하는 부호는 숫자에 한하지 않는다. 알파벳이나 기호 등 임의의 부호를 이용하여 선택지를 특정하는 것이 가능하다.

도 9는 도 7의 푸시다운 오토머톤으로부터 변환된 부호화 트랜스듀서이다.

인코더(11)의 부호화 데이터 열 생성부(113)는 오토머톤 구축부(112)에 의해 구축된 부호화 트랜스듀서를 작동시킨다.

도 9에 나타내는 부호화 트랜스듀서는 타당성 검증(Preorder에서의 룰 적용)을 행한 경우에, 대응하는 선택지 번호가 있으면, 그 번호를 출력한다. 즉, 도 9에 있어서, 룰 A, B, F, H에 관해서는, 선택지가 없기 때문에 아무런 출력을 하지 않고, 룰 C 및 룰 D가 적용된 경우는 해당하는 번호를 출력한다. 예컨대, 도 8의 구문 트리에 대하여 타당성 검증을 한 경우, 트리를 탐색해 감에 따라서, 도 10에 나타낸 바와 같은 번호를 출력한다.

이상의 처리에 의해, "112123"이라는 번호 열을 얻을 수 있다. 이 번호 열은푸시다운 오토머톤의 움직임을 엄밀하게 규정하고 있다. 따라서, 이 번호 열을, 도 4에 나타낸 XML 문서의 구조 부분(도 5)의 부호화된 데이터 열로서 취급할 수 있다.

다음에, 본 실시 형태에 의한 XML 문서의 구조에 대한 복호화 처리의 내용을 설명한다.

전술한 순서를 거쳐 부호화된 XML 문서를 복호하기 위해서는 부호화 트랜스듀서의 입출력을 역으로 하여 적용하면 된다. 따라서, 디코더(23)는 도 7과 동일한 푸시다운 오토머톤을 이용하여 복호화 트랜스듀서를 생성하여, 복호화 처리를 실행한다. 전술한 바와 같이, 오토머톤은 문법의 각 비종단 기호에 대해서 애매함 없이 구축할 수 있기 때문에, DTD로 규정되는 문법 규칙(12)과 문법 규칙(22)이 공통이라면, 디코더(23)에 있어서도 도 7과 완전히 동일한 푸시다운 오토머톤을 구축할 수 있다.

도 11은 도 7과 동일한 푸시다운 오토머톤으로부터 변환된 복호화 트랜스듀서이다. 도 11에 나타내는 복호화 트랜스듀서에 있어서, i/B라는 표현은 「i라는 입력 문자열을 보면, B라는 룰을 부르고, 그 후, 다음 상태로 천이한다」라고 하는 천이를 나타낸다. 이로써, 인코더(11)로부터 출력된 번호열을 입력하여, 대응하는 구문 해석 트리를 생성한다.

전술한 "112123"이라는 번호 열을 입력한 경우, 원래의 번호의 할당 방법으로부터, 이 푸시다운 오토머톤(복호화 트랜스듀서)은 애매함 없이 XML 문서의 부호화 번호 열을 수리할 수 있다. 따라서, 생성되는 구문 해석 트리는 도 8에 나타낸오리지널의 구문 해석 트리와 동일하게 된다. 이에 따라, 상기 XML 문서의 구조 부분이 복원되게 된다.

이어서, 속성의 취급에 관해서 설명한다.

본 실시 형태에서는, 속성은 푸시다운 오토머톤으로 다룰 수 있도록, 트리 구조로 변환한다. 구체적으로는, 속성을 갖는 모든 요소(ELEMEMT)에 관해서, 이들의 속성을 자 노드로서 취하도록 변환한다. 이 때, 속성은 속성명의 알파벳 순으로 나타나는 것으로 한다. 그리고, #REQUIRED인 속성은 그대로 늘어놓는다. 또, ＃IMPLIED인 속성은 선택적인[optional] "?"를 붙인다. 또한, ＃FIXED인 속성에 관하여는 원래 정보가 없기 때문에, 변환후의 DTD에는 포함시키지 않는다.

도 12는 예시적으로, 소정의 DTD에 있어서의 변환 전후의 상태를 비교하는 도면이다. 도 12에 있어서, 좌측에 나타내어지는 DTD는 우측에 나타내어지는 형식으로 변환된다.

이러한 DTD에 따라서, 속성을 포함하는 XML 문서에 있어서도, 속성을 요소로 변환한다. 도 13은 예시적으로, 소정의 XML 문서에 있어서의 변환 전후의 상태를 비교하는 도면이다.

이상과 같은 식으로, DTD와 XML 문서를, 속성을 갖지 않는 상태로 한 후에, 전술한 부호화 처리 및 복호화 처리를 실행한다. 또한, DTD의 변환은 푸시다운 오토머톤을 구축하기 전의 단계에서 미리 행하더라도 좋고, 푸시다운 오토머톤을 구축하는 단계에서 차례대로 행하더라도 좋다. 전자의 경우는 변환후의 새로운 DTD를 이용하여 푸시다운 오토머톤을 구축하는 순서가 된다. 또, 후자의 경우는 원래의(속성을 갖는) DTD로부터 직접 푸시다운 오토머톤을 구성하는 순서가 된다.

이상 설명한 바와 같이, 본 실시 형태는 XML 문서를 압축하는 측과 복원하는 측의 쌍방에 있어서 동일한 DTD를 공유하는 것이 불가결하다. 따라서, 본 실시 형태를 데이터 통신시의 데이터 압축에 이용하는 경우는 송신측 데이터 처리 장치와 수신측 데이터 처리 장치에 각각 동일한 DTD를 준비할 필요가 있다.

도 14는 본 실시 형태를 이용한 데이터 통신 시스템의 구성예를 설명하는 도면이다. 송신측 데이터 처리 장치(1410)에 있어서, 인코더(11)는 데이터 처리부로부터 XML 문서를 수취하여, DTD(1411)(도 1의 문법 규칙(12)에 상당)을 이용하여 구조 부분의 부호화를 행한다. 압축기(13)는 부호화된 구조 부분 및 콘텐츠 부분의 압축을 행한다. 송신부(1412)는 인코더(11) 및 압축기(13)에 의해 압축된 XML 문서를, 통신 네트워크를 통해 수신측 데이터 처리 장치(1420)에 송신한다. 수신측 데이터 처리 장치(1420)에 있어서, 수신부(1422)는 통신 네트워크를 통해 수신한 수신 데이터를 복원기(21)로 보낸다. 복원기(21)는 수취한 수신 데이터의 복원을 행한다. 이 시점에서 XML 문서의 콘텐츠 부분은 복원된다. 디코더(23)는 복원된 수신 데이터의 구조 부분의 부호화 데이터 열을, DTD(1421)(도 1의 문법 규칙(22)에 상당)을 이용하여 복호화한다. 그리고, 복원되어 있는 콘텐츠 부분과 합쳐서 XML 문서를 복원하여, 데이터 처리부로 보낸다. 여기서, 송신측 데이터 처리 장치(1410)의 DTD(1411)와 수신측 데이터 처리 장치(1420)의 DTD(1421)가 동일한 내용으로 되고 있다.

또, 전자 상거래 등의 비즈니스간 통신에서는 어플리케이션끼리 XML 문서를교환하는 경우, DTD는 사전에 합의되어 있는 경우가 대부분이다. 따라서, DTD를 공유하고 있는 것을 전제로, 본 실시 형태를 비즈니스간 통신에 이용할 수 있다.

또, 데이터베이스 시스템에 있어서 저장하는 데이터 파일을 압축하기 위해서 이용하는 경우는, XML 파일의 구조를 부호화하기 위해서 이용한 DTD를, 그대로 복호화할 때에 이용할 수 있기 때문에, DTD가 공유되어 있는지의 여부를 고려할 필요는 없다.

도 15는 본 실시 형태를 이용한 데이터베이스 시스템의 구성을 설명하는 도면이다. 데이터베이스 시스템(1500)에 있어서, 인코더(11)는 데이터 처리부로부터 XML 문서를 수취하여, DTD(1501)(도 1의 문법 규칙(12)에 상당)을 이용하여 구조 부분의 부호화를 행한다. 압축기(13)는 부호화된 구조 부분 및 콘텐츠 부분의 압축을 행한다. 그리고, 인코더(11) 및 압축기(13)에 의해 압축된 XML 문서가 기억 장치(1502)에 저장된다. 기억 장치(1502)에 저장되어 있는 압축된 XML 문서를 읽어내는 경우는 압축기(13)가 복원기(21)로서 동작하고, 인코더(11)가 디코더(23)로서 동작한다. XML 문서의 구조 부분의 복호화에는 부호화시에 이용한 DTD(1501)를 재차 사용한다.

한편, 이상의 설명에서는 트리 로컬 언어로서 XML을 이용한 경우를 예로 설명했지만, ASN.1 등의 다른 트리 로컬 언어에 있어서도 그대로 이용할 수 있다. 다만, 이 경우에 있어서도, 데이터 파일을 압축하는 측과 복원하는 측에서, 전술한 XML에 있어서의 DTD와 같은 문법 규칙을 공유할 필요가 있다.

이상 설명한 바와 같이, 본 발명에 따르면, 트리 로컬 언어에 있어서의 문서의 구조 부분의 부호화를 행하는 데이터 압축을 실현할 수 있다.

또한, 트리 로컬 언어로 특화하는 동시에, 다른 범용적인 데이터 압축 기술과 병용함으로써, 높은 압축율을 기대할 수 있는 데이터 압축 방법을 제공할 수 있다.

Claims

삭제
데이터를 부호화하여 압축하는 데이터 압축 장치로서,

데이터가 라벨을 지닌 트리 구조로 표현되는 트리 로컬 언어의 문법 규칙을 저장한 문법 저장부와,

상기 트리 로컬 언어로 기재된 문서를 읽어들여, 상기 문서를 구조와 콘텐츠로 나누고, 상기 문법 저장부에 저장된 상기 문법 규칙을 이용하여 그 구조를 부호화하는 인코더와,

상기 인코더에 의해서 추출된 상기 문서의 콘텐츠를 압축 부호화하는 압축기

를 구비하고,

상기 인코더는,

처리 대상인 문서를 구조와 콘텐츠로 나누는 분할 처리부와,

상기 문법 규칙에 대응하는 푸시다운 오토머톤(pushdown automaton)을 구축하는 오토머톤 구축부와,

상기 오토머톤 구축부에 의해 구축된 상기 푸시다운 오토머톤을 이용하여, 상기 분할 처리부에 의해 분할된 상기 문서의 구조에 대한 구문 해석을 행하여, 상기 구조의 부호화된 데이터 열을 생성하는 부호화 데이터 생성부

를 구비하는 것을 특징으로 하는 데이터 압축 장치.
제2항에 있어서, 상기 인코더의 상기 부호화 데이터 생성부는 상기 오토머톤 구축부에 의해 구축된 상기 푸시다운 오토머톤 중에 존재하는 선택지에 대하여 부호를 할당하고, 상기 푸시다운 오토머톤을 작동시켜 상기 문서의 구조를 해석했을 때에 상기 선택지의 부위에서 선택된 선택지에 할당되어 있는 상기 부호를 출력함으로써, 상기 구조의 부호화 데이터 열을 생성하는 것을 특징으로 하는 데이터 압축 장치.
제2항에 있어서, 상기 압축기는 상기 문서의 콘텐츠와 함께, 상기 인코더에 의해 부호화된 상기 문서의 구조에 대하여도 압축 부호화를 행하는 것을 특징으로 하는 데이터 압축 장치.
통신 네트워크를 통해 데이터 송신을 하는 송신측 데이터 처리 장치와, 이 송신측 데이터 처리 장치로부터 송신된 데이터를 상기 통신 네트워크를 통해 수신하는 수신측 데이터 처리 장치를 구비한 데이터 통신 시스템으로서,

상기 송신측 데이터 처리 장치는,

데이터가 라벨을 지닌 트리 구조로 표현되는 트리 로컬 언어의 문법 규칙을 저장한 제1 문법 저장부와,

상기 트리 로컬 언어로 기재된 송신 문서를 읽어들여, 상기 송신 문서를 구조와 콘텐츠로 나누고, 상기 제1 문법 저장부에 저장된 상기 문법 규칙을 이용하여 그 구조를 부호화하는 인코더와,

상기 인코더에 의해서 추출된 상기 송신 문서의 콘텐츠를 압축 부호화하는 압축기와,

상기 인코더에 의해 부호화된 상기 구조 및 상기 압축기에 의해 압축 부호화된 상기 콘텐츠를 송신하는 송신부

를 구비하고,

상기 인코더는,

처리 대상인 문서를 구조와 콘텐츠로 나누는 분할 처리부와,

상기 제1 문법 저장부에 저장된 상기 문법 규칙에 대응하는 푸시다운 오토머톤을 구축하는 오토머톤 구축부와,

상기 오토머톤 구축부에 의해 구축된 상기 푸시다운 오토머톤을 이용하여, 상기 분할 처리부에 의해 분할된 상기 문서의 구조에 대한 구문 해석을 행하여, 상기 구조의 부호화된 데이터 열을 생성하는 부호화 데이터 생성부

를 구비하며,

상기 수신측 데이터 처리 장치는,

상기 송신측 데이터 처리 장치로부터 송신된 수신하는 수신부와,

상기 송신측 데이터 처리 장치의 상기 제1 문법 저장부에 저장된 문법 규칙과 동일 내용의 문법 규칙을 저장한 제2 문법 저장부와,

상기 송신측 데이터 처리 장치의 상기 압축기에 의한 압축 부호화 수법에 대응하는 복원 수법으로, 상기 수신부가 수신한 수신 데이터 중 상기 송신 문서의 콘텐츠에 대응하는 데이터를 복원하는 복원기와,

상기 수신부가 수신한 수신 데이터 중 상기 송신 문서의 구조에 대응하는 데이터를, 상기 제2 문법 저장부에 저장된 상기 문법 규칙을 이용하여 그 구조를 복호화하는 디코더

를 구비하는 것을 특징으로 하는 데이터 통신 시스템.
데이터를 기억 장치에 저장하여 관리하는 데이터베이스 시스템으로서,

데이터가 라벨을 지닌 트리 구조로 표현되는 트리 로컬 언어의 문법 규칙을 저장한 문법 저장부와,

상기 트리 로컬 언어로 기재된 문서를 읽어들여, 상기 문서를 구조와 콘텐츠로 나누고, 상기 문법 저장부에 저장된 상기 문법 규칙을 이용하여 그 구조를 부호화하는 인코더와,

상기 인코더에 의해서 추출된 상기 문서의 콘텐츠를 압축 부호화하는 압축기와,

상기 인코더에 의해 부호화된 상기 문서의 구조와 상기 압축기에 의해 압축 부호화된 상기 문서의 콘텐츠를 저장하는 기억 장치

를 구비하고,

상기 인코더는,

처리 대상인 문서를 구조와 콘텐츠로 나누는 분할 처리부와,

상기 문법 규칙에 대응하는 푸시다운 오토머톤을 구축하는 오토머톤 구축부와,

상기 오토머톤 구축부에 의해 구축된 상기 푸시다운 오토머톤을 이용하여, 상기 분할 처리부에 의해 분할된 상기 문서의 구조에 대한 구문 해석을 행하여, 상기 구조의 부호화된 데이터 열을 생성하는 부호화 데이터 생성부

를 구비하는 것을 특징으로 하는 데이터베이스 시스템.
제6항에 있어서, 상기 압축기는 상기 문서의 콘텐츠와 함께, 상기 인코더에 의해 부호화된 상기 문서의 구조에 대하여도 압축 부호화를 행하는 것을 특징으로 하는 데이터베이스 시스템.
삭제
데이터를 부호화하여 압축하는 데이터 압축 방법으로서,

데이터가 라벨을 지닌 트리 구조로 표현되는 트리 로컬 언어로 기재된 문서를 읽어들여, 상기 문서를 구조와 콘텐츠로 나누는 단계와,

상기 트리 로컬 언어의 문법 규칙을 이용하여, 상기 문서의 구조를 부호화하는 단계와,

상기 문서의 콘텐츠를 압축 부호화하는 단계

를 포함하고,

상기 문서의 구조를 부호화하는 단계는,

상기 문법 규칙에 대응하는 푸시다운 오토머톤을 구축하는 단계와,

상기 푸시다운 오토머톤 중에 존재하는 선택지에 대하여 부호를 할당하는 단계와,

상기 푸시다운 오토머톤을 작동시켜 상기 문서의 구조를 깊이 우선으로 탐색과 동시에 해석하여, 상기 선택지의 부위에서 선택된 선택지에 할당되어 있는 상기 부호를 출력하는 단계와,

상기 푸시다운 오토머톤을 작동시켜 출력된 상기 부호의 열을 상기 문서의 구조의 부호화된 데이터 열로서 출력하는 단계

를 포함하는 것을 특징으로 하는 데이터 압축 방법.
제9항에 있어서, 상기 문서의 구조를 부호화하는 단계에 앞서서,

처리 대상인 상기 트리 로컬 언어의 문서의 노드에 속성이 포함되어 있는 경우에, 그 속성을, 그 속성을 갖는 요소의 자 노드로 변환함으로써, 상기 트리 로컬 언어의 문법 규칙 및 상기 문서를, 상기 푸시다운 오토머톤으로 다룰 수 있는 트리 구조로 변환하는 단계를 더 포함하는 것을 특징으로 하는 데이터 압축 방법.
제9항에 있어서, 상기 문서의 구조를 부호화하는 단계의 후에,

범용적인 다른 압축 부호화 수법을 이용하여, 상기 부호화된 상기 문서의 구조를 더욱 압축 부호화하는 단계를 더 포함하는 것을 특징으로 하는 데이터 압축 방법.
컴퓨터에서 실행되는 프로그램을 기록한, 컴퓨터로 읽을 수 있는 기록 매체에 있어서,

상기 프로그램은,

데이터가 라벨을 지닌 트리 구조로 표현되는 트리 로컬 언어로 기재된 문서를 읽어들여, 그 문서를 구조와 콘텐츠로 나누는 처리와,

상기 트리 로컬 언어의 문법 규칙을 이용하여, 상기 문서의 구조를 부호화하는 처리와,

상기 문서의 콘텐츠를 압축 부호화하는 처리

를 상기 컴퓨터에서 실행하고,

상기 문서의 구조를 부호화하는 처리는,

상기 문법 규칙에 대응하는 푸시다운 오토머톤을 구축하는 처리와,

상기 푸시다운 오토머톤 중에 존재하는 선택지에 대하여 부호를 할당하는 처리와,

상기 푸시다운 오토머톤을 작동시켜 상기 문서의 구조를 깊이 우선으로 탐색과 동시에 해석하여, 상기 선택지의 부위에서 선택된 선택지에 할당되어 있는 상기 부호를 출력하는 처리와,

상기 푸시다운 오토머톤을 작동시켜 출력된 상기 부호의 열을 상기 문서의 구조의 부호화된 데이터 열로서 출력하는 처리

를 포함하는 것을 특징으로 하는 기록 매체.
프로그램 전송 장치에 있어서,

데이터가 라벨을 지닌 트리 구조로 표현되는 트리 로컬 언어로 기재된 문서를 읽어들여 그 문서를 구조와 콘텐츠로 나누는 처리와, 상기 트리 로컬 언어의 문법 규칙을 이용하여 상기 문서의 구조를 부호화하는 처리와, 상기 문서의 콘텐츠를 압축 부호화하는 처리를 컴퓨터에 실행시키는 프로그램을 기억하는 기억 수단과,

상기 기억 수단으로부터 상기 프로그램을 읽어내어 그 프로그램을 송신하는 송신 수단

을 구비하고,

상기 문서의 구조를 부호화하는 처리는,

상기 문법 규칙에 대응하는 푸시다운 오토머톤을 구축하는 처리와,

상기 푸시다운 오토머톤 중에 존재하는 선택지에 대하여 부호를 할당하는 처리와,

상기 푸시다운 오토머톤을 작동시켜 상기 문서의 구조를 깊이 우선으로 탐색과 동시에 해석하여, 상기 선택지의 부위에서 선택된 선택지에 할당되어 있는 상기 부호를 출력하는 처리와,

상기 푸시다운 오토머톤을 작동시켜 출력된 상기 부호의 열을 상기 문서의 구조의 부호화된 데이터 열로서 출력하는 처리

를 포함하는 것을 특징으로 하는 프로그램 전송 장치.