JPH07182354A

JPH07182354A - 電子文書の作成方法

Info

Publication number: JPH07182354A
Application number: JP5327420A
Authority: JP
Inventors: Toshihiro Kakimoto; 俊博柿元
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1993-12-24
Filing date: 1993-12-24
Publication date: 1995-07-21

Abstract

(57)【要約】【目的】フルテキスト検索の高速化と記憶容量の節約と
を図った電子文書を効率的に作成することを目的とす
る。【構成】テキスト１０から特定の語をインデックス２０
の見出しとして抽出し、抽出した見出し３１のそれぞれ
に対して出現頻度順に圧縮コード７０を付与して見出し
と圧縮コードとの対応表６０を作成し、対応表に基づい
て見出しとして抽出した語を圧縮コードに置き換えるこ
とによりテキスト１０を圧縮し、見出し３１について圧
縮後のテキスト１０における出現位置を示すリンクデー
タを対応づけてインデックス２０を作成する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、フルテキスト検索用の
インデックスを有した電子文書の作成方法に関する。

【０００２】近年、ハードディスクや光磁気ディスクな
どの大容量記憶媒体の低価格化が進み、個人レベルで大
量のテキストデータの一括管理を手軽に行うことができ
るようになった。また、各種の辞書や百科辞典などをＣ
Ｄ−ＲＯＭに代表される記憶媒体に納めた電子出版物が
商品化されており、パーソナルコンピュータや検索専用
装置などによるテキスト検索が日常化しつつある。

【０００３】このため、検索が容易であり且つ記憶容量
の節約に適した電子文書（テキストファイル）を効率的
に作成する手法が望まれている。

【０００４】

【従来の技術】テキストの中から指定されたキーワード
を含む部分（段落、文など）を抜き出す検索処理に際し
ては、予めテキスト内の語句や文字のそれぞれとそれら
の位置情報（リンクデータ）とを対応づけたインデック
スを作成しておくことにより、インデックスによらずに
テキストの先頭から順にキーワードとテキストとのマッ
チングを行う場合に比べて処理の高速化を図ることがで
きる。

【０００５】従来において、インデックスとしては、品
詞情報（単語辞書）に基づいてテキストを区切った単語
のそれぞれを見出し（エントリー語）とする単語レベル
のインデックス、及びテキストの各文字（１文字単位）
を見出しとする文字レベルのインデックスなどが知られ
ている。

【０００６】単語レベルのインデックスは、文字レベル
のインデックスに比べて見出し数が少なく、インデック
ス自体の小容量化の面で有利である。文字レベルのイン
デックスは、キーワードが文法上の単語に限定されない
という利点を有する。

【０００７】一方、各種のデータ処理システムにおい
て、記憶媒体の有効利用及びデータ通信の効率化などを
図るために、テキストデータの圧縮が行われている。圧
縮手法の内、伸長により完全に復元可能なロスレス型の
手法としては、文字列を圧縮コードに置き換える方法
（ランレングス符号化、ハフマン符号化など）、同一文
字又は文字列の繰り返し部分を文字と繰り返し回数とで
表現する方法、及び、基本の文字列との一致部分を文字
数で表現し且つ不一致部分をその文字で表現する方法な
どが知られている。

【０００８】

【発明が解決しようとする課題】ところで、インデック
スを用いてフルテキスト検索を行う場合、すなわち見出
しと完全に一致する文字列だけでなく見出しを含む任意
の文字列（一部が見出しと一致する文字列）をキーワー
ドとして有効とする場合には、通常は、インデックスの
リンクデータとして、文書単位や段落単位といった概略
の位置情報ではなく、例えば１文字単位の細かな位置情
報が設けられる。そうすることにより、キーワードとテ
キストとのマッチングを迅速化し、いわゆるクイックサ
ーチを実現することができる。

【０００９】しかし、このようなフルテキスト検索用の
インデックスを作成した後に、情報の本体であるテキス
トの圧縮を行うと、圧縮の前後で語句の位置が変わるの
で、インデックスが無意味になってしまう。また、逆に
テキストを圧縮した後にインデックスの作成を行うと、
見出しを抽出するために圧縮データを伸長しなければな
らず、処理系の負担が大きくなるとともにインデックス
の作成に長時間を要する。

【００１０】つまり、従来においては、フルテキスト検
索用のインデックスを有し、且つ圧縮処理を施した電子
文書の作成は困難であった。本発明は、このような問題
に鑑みてなされたもので、各種のコンピュータやワード
プロセッサなどを中心に構成されるデータ処理システム
において、インデックスの付与によるフルテキスト検索
の高速化とデータ圧縮による記憶容量の節約とを図った
電子文書を効率的に作成することを目的としている。

【００１１】

【課題を解決するための手段】請求項１の発明に係る方
法は、上述の課題を解決するため、図１に示すように、
テキスト圧縮データ１１とフルテキスト検索用のインデ
ックス２０とから構成される電子文書１の作成方法であ
って、テキスト１０から特定の語を前記インデックス２
０の見出し３１として抽出し、抽出した前記見出し３１
のそれぞれに対して出現頻度順に圧縮コード７０を付与
して見出しと圧縮コードとの対応表６０を作成するステ
ップ＃３と、前記対応表６０に基づいて、前記見出し３
１として抽出した語を前記圧縮コード７０に置き換える
ことにより、前記テキスト圧縮データ１１を作成するス
テップ＃４と、前記見出し３１について、前記テキスト
圧縮データ１１における出現位置を示すリンクデータ３
２を対応づけて前記インデックス２０を作成するステッ
プ＃５とを有する。

【００１２】請求項２の発明に係る方法は、前記インデ
ックス２０が、前記見出し３１と前記出現位置との対応
関係を示す単語インデックス３０と、前記テキスト１０
に含まれる文字４１と前記見出し３１との対応関係を示
す文字インデックス４０とからなる階層構造を有するも
のである。

【００１３】請求項３の発明に係る方法は、前記圧縮コ
ード７０を、前記出現頻度が少なくなるにつれて段階的
に長くなる可変長データとしたものである。請求項４の
発明に係る方法は、前記単語インデックス３０における
前記見出し３１の配置位置を前記出現頻度順に示す伸長
用アドレスリスト５０を作成するステップ＃５を有する
ものである。

【００１４】請求項５の発明に係る方法は、前記テキス
ト１０の圧縮に際して、前記見出し３１以外の文字列の
内、一定数以上の同一文字のみからなる文字列について
は、前記同一文字の識別コード７６と固定長の文字数デ
ータ７７とからなる繰り返し文字列圧縮コード７５に置
き換えるものである。

【００１５】

【作用】テキスト１０の中から、文法上の単語、又は漢
字やカナなどの同一種類の文字のみからなる文字列（１
文字を含む）などの特定の語が、インデックス２０の見
出し３１として抽出される。

【００１６】抽出された各見出し３１には、その出現頻
度順に固有の圧縮コード７０が付与され、これにより見
出しと圧縮コードとの対応表６０が生成される。その
際、各見出し３１の内、データ長が圧縮コード７０より
短いものは対応表６０の見出し７３からは除外される。

【００１７】そして、テキスト１０の内の見出し３１と
一致する部分（語）が圧縮コード７０に置き換えられ、
テキスト１０を圧縮したテキスト圧縮データ１１が生成
される。つまりインデックス２０の見出し３１を符号化
単位とする圧縮が行われる。

【００１８】その後、各見出し３１について、テキスト
圧縮データ１１における出現位置を示すリンクデータ３
２が対応づけられ、インデックス２０が生成される。

【００１９】

【実施例】図１は本発明を適用した電子文書作成の概要
を示すフローチャートである。ここでは、ハードディス
クなどの所定容量の記憶媒体に、キャラクタコード系の
統一されたテキストデータ１０と、形態素解析のための
単語辞書８０とが格納されているものとする。テキスト
データ１０は、例えば日本語や外国語の文書情報（画像
を含む場合もある）であり、文書作成ソフトウェアによ
って作成され、又はデータ通信により入力されたレコー
ドの集合である。

【００２０】まず、テキストデータ１０の内の改行コー
ドなどの制御コードを識別し、１バイト（英数字など）
又は２バイト（漢字やカナなど）のキャラクタコードか
らなるテキスト（キャラクタコード列）を文毎に分割す
る前処理を行う（＃１）。

【００２１】続いて、文単位のテキストを単語辞書８０
の品詞情報に基づいて単語に分割し、単語辞書８０にお
ける未登録の文字列について、漢字とカナとの境目で区
切るというように同一文字種の語に分割する語分割処理
を行う（＃２）。このとき、文字種情報のみによって分
割を行うようにすれば、処理の所要時間を短縮すること
ができるとともに、単語辞書８０の省略により生じる記
憶媒体の空容量を他に活用することができる。

【００２２】次に、語分割によって得られた多数の語の
内、所定の条件を満足する語を単語インデックス３０の
見出し（以下、「単語見出し」という）として抽出し、
後述のように多数の単語見出しのそれぞれと圧縮コード
とを対応づける対応表６０を作成する（＃３）。

【００２３】そして、対応表６０に基づいて、テキスト
データ１０の内の単語見出しと一致する部分（上述の語
分割で得られた語）を圧縮コードに置き換えることによ
り、テキストデータ１０を圧縮する（＃４）。つまり、
単語見出しを符号化単位とする圧縮によってテキスト圧
縮データ１１を作成する。

【００２４】このような圧縮と並行して、又は圧縮の終
了後に、単語インデックス３０及び１文字インデックス
４０からなる階層構造（図１０参照）を有したフルテキ
スト検索用のインデックス２０と、圧縮データを伸長す
るためのアドレスリスト５０を作成する（＃５）。

【００２５】なお、単語インデックス３０は、図７に示
すように、多数の単語見出し３１（圧縮対象以外の語を
含む場合もある）と、それらのテキスト圧縮データ１１
内での出現位置（格納アドレス）をバイト単位で示すリ
ンクデータ３２とから構成されている。単語見出し３１
は、マッチングの高速化を図るために、キャラクタコー
ド値順に配置されている。

【００２６】アドレスリスト５０は、対応表６０におけ
る各単語見出し７３について、それらの格納アドレス
（単語インデックス３０を格納したメモリ空間内のアド
レス）を単語見出しの出現頻度順に並べたリストであ
り、出現頻度順の圧縮コード７０とキャラクタコード値
順の単語見出し３１とを対応づける役割を担う。図７の
例では、出現頻度が最も多い単語見出し３１は「情報」
であり、その格納アドレスがアドレスリスト５０の先頭
に格納されている。

【００２７】また、１文字インデックス４０は、図１０
に示すように、単語見出し３１から１文字単位で抽出し
た見出し（以下、「文字見出し」という）４１と、文字
見出し４１を含む単語見出し３１の単語インデックス３
０内での位置を示すリンクデータ４１とから構成されて
いる。

【００２８】上述の各処理によって作成された電子文書
１、すなわちテキスト圧縮データ１１とインデックス２
０とアドレスリスト５０とを構成する一群のビットデー
タは、テキスト情報のデータベースとして管理される。
また、電子出版を行う場合には、ＣＤ−ＲＯＭやメモリ
カードなどに納める情報の原本として用いられる。

【００２９】図２は図１の対応表の作成処理のフローチ
ャート、図３は図１のテキストの圧縮処理のフローチャ
ート、図４は圧縮コード７０の構成を示す図、図５は対
応表６０の構成を示す図である。

【００３０】図２において、対応表６０の作成に際して
は、まず、上述のように分割されたテキストの各語の
内、データ長が３バイト以上である語を単語見出し７３
として重複のないように抽出する（＃３１）。つまり、
圧縮コード７０は１バイト（８ビット）の識別部７１と
可変長（１〜５バイト）の符号部７２とから構成され、
その最短データ長が２バイトであるので、圧縮コード７
０への置換えが無意味である２バイト以下の語を圧縮対
象から除外する。なお、圧縮コード７０の識別部７１
は、テキスト圧縮データ１１における圧縮部（圧縮コー
ド７０）と非圧縮部（キャラクタコード）とを判別する
ために設けられている。

【００３１】次に、抽出した単語見出し７３を出現頻度
順に並べ、各単語見出し７３に対して、圧縮率を高める
ための手法である統計的エンコード法による数値コード
を付与して対応表６０を作成する（＃３２）。数値コー
ドは、圧縮コード７０の符号部７２に対応するビット列
であり、値が大きくなるにつれてバイト単位で段階的に
データ長が増大する。そして、そのデータ長は、表１の
ように先頭部のビットで示される。

【００３２】

【表１】

【００３３】続いて、少なくとも２文字（英数字のみの
場合は３文字）以上の文字列である単語見出し７３のそ
れぞれについて、それらに対応づけられた圧縮コード７
０よりもデータ長が長いか否かをチェックする（＃３
３）。

【００３４】全ての単語見出し７３が圧縮コード７０よ
りも長い場合は、そのまま処理を終える。なお、この場
合には対応表６０の単語見出し７３の語及び総数は、単
語インデックス３０の単語見出し３１と一致することに
なる。

【００３５】また、圧縮コード７０より長いという条件
を満たさない単語見出し７３があれば、図６（ａ）及び
（ｂ）に示すように、その単語見出し７３を対応表６０
から削除し、それよりも出現頻度の少ない単語見出し７
３を繰り上げて対応表６０を修正する（＃３４）。図６
の例では、圧縮コード７０と同一の３バイトであること
から、出現頻度順位が１２９位の単語見出し７３である
英字列「ＯＦＦ」が削除されている。図３において、
テキストの圧縮に際しては、通常の検索ではキーワード
として指定されることがないという理由で、予めインデ
ックスの対象外の語として定められている特定文字（例
えば句読点や括弧などの記述記号）以外の文字からなる
語について、単語見出し７３であるか否かのチェック、
すなわち圧縮コード７０が付与されているか否かのチェ
ックを行う（＃４１，＃４２）。そして、圧縮コード７
０が付与されている場合は、その語を圧縮コード７０に
置き換えて、テキスト圧縮データ１１の一部として所定
の記憶媒体に格納し、圧縮コード７０が付与されていな
い場合は、その語をキャラクタコードの状態で格納する
（＃４３，＃４４）。

【００３６】一方、上述の特定文字からなる語について
は、同一文字からなる３文字以上の文字列であれば、そ
れを繰り返し文字列圧縮コード７５に置き換える（＃４
５，＃４６）。繰り返し文字列圧縮コード７５は、図８
に示すように、１バイトの識別部７６と、同一文字の繰
り返し回数（３〜２５６）を示す１バイトの数値データ
７７とから構成されている。数値データ７７のデータ長
は固定であるので、２５７文字以上の文字列について
は、２５６文字毎に区切られて繰り返し文字列圧縮コー
ド７５に置き換えられる。なお、同一文字からなる連続
した長い文字列としては、例えば記号「−」の羅列によ
る疑似罫線、及び空白などがある。

【００３７】次に、電子文書１によるフルテキスト検索
について説明する。図９は電子文書１を備えた検索シス
テム１００の機能上の構成を示すブロック図、図１０は
フルテキスト検索の一例を示す図である。

【００３８】これらの図において、検索者がキーボード
１０１を用いてキーワードＫＷを指定して検索開始を指
示すると、キー入力処理を担うキーワード入力部１０２
から文字見出しマッチング部１０３へキーワードＫＷが
送られる。ここでは、キーワードＫＷを「情報の」とい
う３文字の文字列とし、この文字列の内の「情報」とい
う語は単語見出し３１として抽出されているものとす
る。

【００３９】文字見出しマッチング部１０３は、例えば
キーワードＫＷを品詞分解して最も長い単語に注目し、
その単語を構成する文字を対象として１文字インデック
ス４０をサーチする。このとき、文字見出し４１も単語
見出し３１と同様にキャラクタコード値順に配置されて
おり、迅速に検索対象文字と文字見出し４１とのマッチ
ングが行われる。

【００４０】図１０の例では、「情」及び「報」の各文
字を順に対象としてマッチングが行われ、これらの各文
字と一致する２つの文字見出し４１のリンクデータ４２
における互いの共通部分、すなわち「情報」という単語
見出し３１の格納位置情報が単語見出しマッチング部１
０４へ送られる。

【００４１】単語見出しマッチング部１０４は、単語イ
ンデックス３０から「情報」という単語見出し３１のリ
ンクデータ３２を読み出し、それをテキスト伸長部１０
５へ送る。なお、キーワードＫＷが単語見出し３１と完
全に一致する場合には、単語見出しマッチング部１０４
は、リンクデータ３２を後述のテキスト出力部１０７へ
送る。

【００４２】テキスト伸長部１０５は、リンクデータ３
２に基づいてテキスト圧縮データ１１の所定部分を読み
出し、アドレスリスト５０を用いて圧縮コード７０をキ
ャラクタコードに変換（伸長）し、「情報」とその直後
の１文字とを合わせた３文字分（キーワード相当分）の
キャラクタコードを位置情報と合わせてテキストマッチ
ング部１０６へ送る。例えば、図１０のように「情報
は」及び「情報の」を送る。

【００４３】テキストマッチング部１０６は、テキスト
伸長部１０５からのキャラクタコード列とキーワードＫ
Ｗとのマッチングを行い、その結果をテキスト出力部１
０７に通知する。

【００４４】テキスト出力部１０７は、キーワードＫＷ
と一致する文字列がある場合には、必要に応じて圧縮コ
ードを伸長して、キーワードＫＷを含む所定範囲（ペー
ジ単位、段落単位、文単位など）をディスプレイ装置１
０８の画面上に表示する。また、キーワードＫＷと一致
する文字列がない場合には、その旨を示すメッセージを
表示する。

【００４５】上述の実施例によれば、１文字インデック
ス４０を設けてインデックス２０を階層構造としたの
で、検索に際して単語見出し３１に含まれる任意の１文
字をキーワードＫＷとして指定することができる。ま
た、検索の高速化を図ることができる。

【００４６】上述の実施例によれば、テキストを語に分
割する際に、品詞情報による分割手法と文字種情報によ
る分割手法とを併用したので、キーワードＫＷとして使
用される確率の高い自立語を単語見出し３１として抽出
することができるとともに、単語辞書８０に未登録の固
有名詞なども確実に単語見出し３１として抽出すること
ができるので、単語辞書８０の語彙数が少ない場合であ
っても、単語インデックス３０の充実を図ることができ
る。

【００４７】

【発明の効果】本発明によれば、各種のデータ処理シス
テムにおいて、インデックスの付与によるフルテキスト
検索の高速化とデータ圧縮による記憶容量の節約とを図
った電子文書を効率的に作成することができる。

【００４８】請求項２の発明によれば、検索の利便性を
高めることができる。請求項３の発明によれば、データ
圧縮率を高めることができる。請求項４の発明によれ
ば、検索の高速化を図ることができる。

【図面の簡単な説明】

【図１】本発明を適用した電子文書作成の概要を示すフ
ローチャートである。

【図２】図１の対応表の作成処理のフローチャートであ
る。

【図３】図１のテキストの圧縮処理のフローチャートで
ある。

【図４】圧縮コードの構成を示す図である。

【図５】対応表の構成を示す図である。

【図６】対応表の修正の一例を示す図である。

【図７】単語インデックスとアドレスリストとの対応関
係を示す図である。

【図８】繰り返し文字列圧縮コードの構成を示す図であ
る。

【図９】本発明に係る電子文書を備えた検索システムの
機能上の構成を示すブロック図である。

【図１０】図９の検索システムにおけるフルテキスト検
索の一例を示す図である。

【符号の説明】１電子文書１０テキストデータ（テキスト）１１テキスト圧縮データ２０インデックス３１単語見出し（見出し）３２リンクデータ４０１文字インデックス（文字インデックス）４１文字見出し（文字）５０アドレスリスト６０対応表７０圧縮コード７５繰り返し文字列圧縮コード７６識別部（識別コード）７７数値データ（文字数データ）

Claims

【特許請求の範囲】

【請求項１】テキスト圧縮データ（１１）とフルテキス
ト検索用のインデックス（２０）とから構成される電子
文書（１）の作成方法であって、テキスト（１０）から特定の語を前記インデックス（２
０）の見出し（３１）として抽出し、抽出した前記見出
し（３１）のそれぞれに対して出現頻度順に圧縮コード
（７０）を付与して見出しと圧縮コードとの対応表（６
０）を作成するステップ（＃３）と、前記対応表（６０）に基づいて、前記見出し（３１）と
して抽出した語を前記圧縮コード（７０）に置き換える
ことにより、前記テキスト圧縮データ（１１）を作成す
るステップ（＃４）と、前記見出し（３１）について、前記テキスト圧縮データ
（１１）における出現位置を示すリンクデータ（３２）
を対応づけて前記インデックス（２０）を作成するステ
ップ（＃５）とを有することを特徴とする電子文書の作
成方法。
【請求項２】前記インデックス（２０）は、前記見出し
（３１）と前記出現位置との対応関係を示す単語インデ
ックス（３０）と、前記テキスト（１０）に含まれる文
字（４１）と前記見出し（３１）との対応関係を示す文
字インデックス（４０）とからなる階層構造を有するこ
とを特徴とする請求項１記載の電子文書の作成方法。
【請求項３】前記圧縮コード（７０）は、前記出現頻度
が少なくなるにつれて段階的に長くなる可変長データか
らなることを特徴とする請求項１又は請求項２記載の電
子文書の作成方法。
【請求項４】前記単語インデックス（３０）における前
記見出し（３１）の配置位置を前記出現頻度順に示す伸
長用アドレスリスト（５０）を作成するステップ（＃
５）を設けたことを特徴とする請求項１乃至請求項３の
いずれかに記載の電子文書の作成方法。
【請求項５】前記テキスト（１０）の圧縮に際して、前
記見出し（３１）以外の文字列の内、一定数以上の同一
文字のみからなる文字列については、前記同一文字の識
別コード（７６）と固定長の文字数データ（７７）とか
らなる繰り返し文字列圧縮コード（７５）に置き換える
ことを特徴とする請求項１乃至請求項４のいずれかに記
載の電子文書の作成方法。