JP3003915B2 - 単語辞書検索装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明は単語辞書検索装置に関
し、特に、ワードプロセッサなどの言語処理機能を備え
た機器に用いられる単語辞書検索装置に関する。

【０００２】

【従来の技術および発明が解決しようとする課題】ワー
ドプロセッサ、パーソナルコンピュータなどの情報処理
機器において、国語辞典、英和辞典といった辞書のデー
タを搭載し、電子的に検索できるようにした装置（ここ
では、電子辞書と呼ぶ）が普及し始めている。

【０００３】電子辞書は、一般に、辞書項目数に比例し
た大容量の検索用インデックスが必要である。特に、見
出し語に関するインデックスは見出し語の文字列長がそ
れぞれ異なるために、可変長のインデックス構造をとる
場合が多いが、可変長の構造では、必要な情報へのアク
セスに時間がかかり、また、前後の見出し語項目にアク
セスするためのサイズ情報が必要となり容量が嵩んでし
まうという欠点がある。これを図を参照して説明する。

【０００４】図１１（ａ）および（ｂ）は、従来の可変
長見出し語インデックスの一般的な構造を示す図であ
る。図の可変長見出し語インデックスは先頭３文字イン
デックス２００および見出し語本体インデックス３００
からなる。インデックス２００は見出し語の先頭の３文
字が変わるごとに辞書から抽出された見出し語に対する
本体インデックス３００のオフセット（先頭からの位
置）２０ａからなり、インデックス３００は辞書順に並
べられた見出し語の本体インデックスである（ここでは
簡単化のため、見出し語部分のみが記される）。インデ
ックス３００は各見出し語について項目サイズ３０ａ、
４文字目以降の見出し語文字列３０ｂおよび逆送り用項
目サイズ３０ｃを含むアイテム３０１からなる。見出し
語は可変長であるため、４文字目以降の見出し語文字列
３０ｂは可変長のデータとなり、またこのインデックス
３００の各アイテムを順・逆両方向に辿るためには、図
に示すように、自分自身のサイズを項目サイズ３０ａお
よび逆送り用項目サイズ３０ｃとして予め用意しておか
なければならない。図１１（ｂ）には図１１（ａ）に示
されたインデックス２００および３００についての具体
的な構造が示されている。

【０００５】上述した図１１のインデックス構造は次の
ような欠点（１）〜（３）を有する。

【０００６】（１） 見出し語を辿るときに各見出し語
のサイズ）からオフセット２０ａを求める必要がある。

【０００７】（２） 見出し語本体インデックス３００
は英和辞典を想定した場合、通常１００００語前後で６
４Ｋバイトを超えてしまうため、見出し語本体インデッ
クス３００へのオフセット２０ａが３バイト必要とな
り、見出し語を参照するような他のインデックス、この
場合インデックス２００の容量が嵩む。

【０００８】（３） 見出し語本体自体のサイズが大き
い。上述した図１１（ａ）および（ｂ）で示された見出
し語の可変長の部分を本体インデックスの外部に出して
本体を固定長のインデックス構造にすればアクセス時間
は短くなるが、可変長部分へアクセスするための情報が
余分に必要となるため、容量は可変長のものよりも大き
くなってしまうという課題があった。これを図を参照し
て説明する。

【０００９】図１２（ａ）および（ｂ）は、従来の見出
し語本体をポインタデータのみの固定長にした見出し語
インデックスの構造を示す図である。このインデックス
は先頭３文字インデックス４００、見出し語本体インデ
ックス５００および文字列バッファ６００からなる。イ
ンデックス４００は見出し語の先頭の３文字が変わるご
とに辞書から抽出された見出し語に対する本体インデッ
クス５００のオフセット４０ａからなる。インデックス
５００は見出し語のそれぞれについて４文字目以降の見
出し語文字列へのポインタ５０ｂを含むアイテム５０１
からなる。インデックス５００は図１１のインデックス
構造の欠点の１つである可変長構造を解消するために見
出し語本体をポインタデータ（５０ｂ）のみの固定長に
したものである。文字列バッファ６００には、図１１の
４文字目以降の見出し語文字列３０ｂに対応するデータ
が区切りコード（￥０）を入れて格納される。このイン
デックス構造の具体的な例が図１２（ｂ）に示される。

【００１０】図１２のインデックス構造では、見出し語
を連続した番号で管理できるので、見出し語数が６４Ｋ
までの辞書については、見出し語本体インデックス５０
０へのオフセット４０ａは２バイトですみ、かつ本体イ
ンデックス５００を辿る場合はポインタのインクリメン
ト・デクリメント（１増やす・１減らす）操作でよいた
めアクセス時間も短くなる。しかしながら、この構造で
は依然として、可変長の構造と比べて、本体インデック
ス５００と文字列バッファ６００との消費メモリ容量が
大きくなるという課題が残る。

【００１１】従来から提案されてきた見出し語インデッ
クスの容量削減法は主として、各見出し語の先頭から共
通する何文字かを低次のインデックスにまとめることに
よる差分をとる方式と、見出し語中に頻出する２バイト
コードを１バイトの空き領域に割当てる方式とに大別さ
れる。しかしながら、これらの手法で削減できる消費容
量はごく限られたものであり、従来技術では、固定長の
見出し語インデックス構造をとりながら消費するメモリ
容量を抑制するようなインデックスを構成することはで
きなかった。

【００１２】また、たとえば特開昭６１−２８５５７
３，特開平３−１２７２５４および特開平５−５４０７
７公報に開示の技術では、単語の変化形からの検索や熟
語検索など別途見出し語が必要となるような検索機能を
追加する場合、追加機能に対応するインデックスデータ
分だけ容量を増やすしか方法がなく、容量やコストの制
限のある機種では検索機能の追加は極めて困難であっ
た。これを図を参照して説明する。

【００１３】図１３は、従来の見出し語検索機能に派生
語検索機能を追加した場合のインデックス構造の概略を
示す図である。見出し語検索に、見出し語の変化形から
も検索できるようにするための派生語検索機能を追加し
た場合、図１３で示されるようなインデックスが準備さ
れる。詳述するなら、このような検索機能の追加があっ
た場合、通常の方法では、各派生語ごとの派生語見出し
に対して、見出し語の検索インデックスの場合と同様の
構成のインデックスデータを用意し、これらを元にあっ
た見出し語検索用のインデックスデータにいかなるイン
デックスデータも共有することなく付け加えることにな
る。すなわち、元にあった見出し語インデックスデータ
の容量（低次のインデックス６０１、見出し語本体イン
デックス６０２および見出し語用文字列バッファ６０３
の全容量）をＡとし、追加された派生語インデックスデ
ータの容量（低次のインデックス７０１、派生語見出し
インデックス７０２および派生語見出し用文字列バッフ
ァ７０３の全容量）をＢとすると、派生語検索機能が追
加された場合の全体のインデックスデータの容量は（Ａ
＋Ｂ）となる。これは、検索機能を追加すればそれに比
例しただけ確実にインデックス容量が増加することを示
しており、メモリ容量が限られた機種上では、検索機能
追加が困難であり、大変な制約となる。

【００１４】それゆえにこの発明の目的は、インデック
ス部を用いた辞書検索の高速化を図りながら、インデッ
クス部による消費メモリ容量を抑制できる単語辞書検索
装置を提供することである。

【００１５】この発明の他の目的は、検索対象辞書の追
加による検索機能拡張において、辞書検索に用いられる
インデックス部による消費メモリ容量の増加を抑制でき
る単語辞書検索装置を提供することである。

【００１６】

【課題を解決するための手段】請求項１に記載の単語辞
書検索装置は、少なくとも単語辞書の本体データおよび
この辞書検索用のインデックス部を記憶し、指定された
単語をインデックス部を介して辞書本体データから検索
する装置であり、このインデックス部はさらに、文字列
バッファ、本体インデックス、および低次インデックス
を備えて構成される。

【００１７】文字列バッファには、単語辞書中の各単語
について、その文字列の辞書中で該単語の直前に登録さ
れた単語の文字列と一致しない部分文字列である差分文
字列が、そこに既に格納された文字列中のいずれの部分
文字列とも重複することなく順次格納される。

【００１８】本体インデックスは、単語辞書中の各単語
に対応した固定長アイテムを有し、各アイテムには、該
アイテムに対応する単語の文字列の単語辞書中で該単語
の直前に登録された単語の文字列と一致する部分文字列
の長さおよび前述の差分文字列の長さに関する情報、な
らびにこの差分文字列の文字列バッファにおける格納位
置に関する情報が格納される。

【００１９】低次インデックスは、本体インデックス中
の各アイテムの情報を前述の指定単語の文字列に従って
アクセスするためのものである。

【００２０】請求項２に記載の単語辞書検索装置は、請
求項１に記載の装置に、さらに前述のインデックス部を
生成する手段を備えて構成される。

【００２１】このインデックス部生成手段は、情報検出
手段、文字列格納手段、情報格納手段、および低次イン
デックス生成手段をさらに含んで構成される。

【００２２】情報検出手段は、単語辞書中の各単語につ
いて、その文字列と辞書中の該単語の直前に登録された
単語の文字列とを比較し、一致する部分文字列長および
前述の差分文字列長に関する情報、ならびにこの差分文
字列を検出する。

【００２３】文字列格納手段は、情報検出手段により検
出された差分文字列が文字列バッファに既に格納されて
いる文字列中のいずれの部分文字列とも一致しないこと
に応じて、この差分文字列を文字列バッファ中の文字列
後尾に順次追加格納する。

【００２４】情報格納手段は、文字列格納手段による差
分文字列の文字列バッファにおける格納位置に関する情
報ならびに前述の情報検出手段により検出された一致部
分文字列長および差分文字列長に関する情報を前述の本
体インデックスの対応するアイテムに順次格納する。

【００２５】低次インデックス生成手段は、情報格納手
段により各単語の情報が格納されたアイテムの位置に基
づいて前述の低次インデックスを生成する。

【００２６】請求項３に記載の単語辞書検索装置は、請
求項２に記載のインデックス部生成手段が、検索対象辞
書が前述の単語辞書に、これとは異なる単語辞書が追加
されて拡張される場合に拡張インデックス部生成手段を
さらに備えて構成される。

【００２７】この拡張インデックス部生成手段は、さら
に、拡張情報検出手段、拡張文字列格納手段、情報更新
手段、拡張本体インデックス生成手段、および拡張低次
インデックス生成手段を備えて構成される。

【００２８】拡張情報検出手段は、追加される単語辞書
中の各単語について、その文字列と追加辞書中の該単語
の直前に登録された単語の文字列とを比較し、一致する
部分文字列の長さおよび一致しない部分文字列である差
分文字列の長さに関する情報、ならびにこの差分文字列
を検出する。

【００２９】拡張文字列格納手段は、情報検出手段によ
り検出された差分文字列または拡張情報検出手段により
検出された差分文字列が、文字列バッファに既に格納さ
れている文字列中のいずれの部分文字列とも一致しない
ことに応じて、この差分文字列を文字列バッファ中の文
字列後尾に順次追加格納する。

【００３０】情報更新手段は、拡張文字列格納手段によ
り格納された差分文字列の文字列バッファ内における位
置情報を用いて情報格納手段により本体インデックスに
格納された格納位置情報を更新する。

【００３１】拡張本体インデックス生成手段は、拡張文
字列格納手段により格納された差分文字列の文字列バッ
ファ内における位置情報ならびに拡張情報検出手段によ
り検出された追加辞書中の各単語に関する一致部分文字
列長および差分文字列長情報を用いてこの追加辞書に対
応の本体インデックスを生成する。

【００３２】拡張低次インデックス生成手段は、拡張本
体インデックス生成手段により生成された本体インデッ
クスにおける追加辞書中の各単語の情報が格納されたア
イテムの位置に基づいて、追加辞書に対応の低次インデ
ックスを生成する。

【００３３】

【作用】請求項１に記載の単語辞書検索装置では、そこ
に記憶されるインデックス部において、本体インデック
スは各単語に対応の情報を格納するアイテムが固定長で
あるように構成されるとともに、文字列バッファは、辞
書における各単語の前単語との文字列間における差分文
字列を既に格納された文字列中のいずれの部分文字列と
も重複しないようにして格納するよう構成されるので、
本体インデックスおよび文字列バッファに関する消費メ
モリ容量が抑制される。

【００３４】また、前述したように本体インデックスの
各アイテムは固定長であるので、低次インデックスを介
した本体インデックス中の所望アイテムへのアクセス時
間が短縮される。

【００３５】請求項２に記載の単語辞書検索装置では、
インデックス部生成手段の文字列格納手段は前述の差分
文字列を文字列バッファに既に格納されている文字列中
のいずれの部分文字列とも一致しないことに応じて、該
差分文字列を該バッファ中に順次追加格納するので、該
バッファ内ではデータが冗長することなく格納されて、
その分バッファの消費メモリ容量が抑制される。

【００３６】また、情報格納手段により各単語の情報は
本体インデックスの固定長アイテムに格納され得る、す
なわち固定長データにして格納されるので、本体インデ
ックスの消費メモリ容量が抑制される。

【００３７】請求項３に記載の単語辞書検索装置の拡張
本体インデックス生成手段は、追加辞書に対する本体イ
ンデックスも、各単語の情報格納先であるアイテムを固
定長にして生成するので、拡張された本体インデックス
による消費メモリ容量の増加を抑制できるとともに、追
加辞書検索時に拡張低次インデックス生成手段により生
成された低次インデックスを介した拡張本体インデック
スへのアクセス時間が短縮される。

【００３８】また、拡張文字列格納手段は、文字列バッ
ファに元の単語辞書と追加された単語辞書とに関する差
分文字列をそこに既に格納された文字列中のいずれの部
分文字列とも重複しないようにして格納し、情報更新手
段は元の単語辞書の本体インデックスの内容を拡張文字
列格納手段により拡張された文字列バッファ内の各差分
文字列の位置情報を用いて更新する。したがって、文字
列バッファが元の単語辞書と追加された単語辞書と共有
され得るようにインデックス部が生成されるので、検索
対象辞書の追加に伴うインデックス部の消費メモリ容量
の増加が抑制される。

【００３９】

【実施例】以下、この発明の一実施例について図面を参
照して説明する。

【００４０】図１は、この発明の一実施例によるインデ
ックスの概略構造を示す図である。図２は、この発明の
一実施例によるインデックスの具体的構造を示す図であ
る。

【００４１】図３は、この発明の一実施例による単語辞
書検索装置の機能ブロック構成図であり、図４は、この
発明の一実施例による単語辞書検索装置のハードウェア
構成図である。

【００４２】まず、図３の各機能ブロックと図４の各ハ
ードウェアとを対応づけて装置の構成について説明す
る。図３において装置は機能として、制御部１１０、入
力部１１１、記憶部１１２、表示部１１３、インデック
スデータ作成部１１４、インデックスデータ追加部１１
５および検索部１１６を含む。

【００４３】入力部１１１はキーボード、ＯＣＲ（光学
式文字読取装置）、ペンなどの入力装置１０４および外
部機器、たとえばコンピュータなどとのデータのやり取
りをするための入力Ｉ／Ｆ（インタフェースの略）１０
２から構成され、検索対象となる文字列や辞書のデータ
などを入力する。

【００４４】記憶部１１２はＲＯＭ（リードオンリメモ
リ）およびＲＡＭ（ランダムアクセスメモリ）で構成さ
れるコンピュータなどの通常の記憶装置１０１からな
り、検索用のインデックスデータ、検索部１１６に関す
る実行用のオブジェクトデータおよび検索結果データな
ど必要な各種データを格納する。

【００４５】表示部１１３は液晶ディスプレイ、ＣＲＴ
（陰極線管の略）などの出力装置１０６およびコンピュ
ータなどとのデータのやり取りをするための出力Ｉ／Ｆ
１０５から構成され、入力文字列、検索結果データなど
を表示する。

【００４６】インデックスデータ作成部１１４は、後述
する作成方法に即して、小容量のインデックスデータを
作成し、これを記憶装置１０１に格納するためのロジッ
クからなり、記憶装置１０１の一部がこれに対応する。

【００４７】インデックスデータ追加部１１５は、後述
する追加方法に即して、追加される容量が極力抑制され
た小容量のインデックスデータを作成し、記憶装置１０
１にこれを格納するためのロジックであり、記憶装置１
０１の一部がこれに対応する。

【００４８】検索部１１６は、入力された検索対象文字
列に関する文字列の比較処理を行ないながら、記憶装置
１０１に格納された検索用インデックスを辿り、検索要
件を満たす辞書の本体データにアクセスして必要なデー
タを抽出するためのロジックであり、記憶装置１０１の
一部がこれに対応する。なお、辞書の本体データおよび
検索部１１６は、説明の便宜上、見出し語のみが格納さ
れた見出し語本体インデックスデータおよび見出し語検
索機能のみに簡単化した。

【００４９】制御部１１０は、前述の各部を制御しなが
ら、記憶装置１０１中のデータ作成部１１４あるいはデ
ータ追加部１１５を呼出してそのロジックを解釈実行し
たり、記憶装置１０１中の検索部１１６を呼出し、一連
の検索ロジックを解釈実行するためのものであり、ＣＰ
Ｕ（中央処理装置の略）１００がこれに対応する。

【００５０】図１および図２は検索用インデックスに関
するメモリ消費容量を極力抑制することが可能な見出し
語インデックスデータの構成を示すものであり、図１に
その概略構造が、図２にその具体的構造がそれぞれ示さ
れる。

【００５１】図１において、本実施例のインデックス構
造は、差分文字列バッファ４および辞書の各見出し語情
報を辞書の配列順に並べて格納した見出し語本体インデ
ックス３を先頭文字による１次インデックス１およびｍ
件ごとの２次インデックス２を介してアクセスできるよ
うな構造となっている。見出し語本体インデックス３は
辞書の各見出し語についてアイテムＩを含み、アイテム
Ｉのサイズは固定長Ｋバイトであり、Ｋの値は扱う辞書
の規模により異なるが、４００００見出し語前後の中規
模の英和辞典の場合、Ｋ＝３で十分である。辞書の規模
が１０数万見出し語になった場合でもＫ＝４で十分であ
る。

【００５２】アイテムＩは第１フィールドＦ１および第
２フィールドＦ２を含む。フィールドＦ１は１つ前の見
出し語との重複文字数３ａおよび差分文字列長３ｂとを
データとして含み、第２フィールドＦ２は差分文字列バ
ッファ４へのポインタ３ｃをデータとして含む。インデ
ックス３においては、アイテムＩの１バイト目を第１フ
ィールドに割当て、残りのＫ−１バイトを第２フィール
ドに割当てている。フィールドＦ１では、さらに上位何
ビットかを前単語との重複文字数３ａに割当て、下位の
残りビットを１つ前の見出し語文字列との差分文字列長
３ｂに割当てている。具体的な割当てビット数は扱う辞
書により異なるが、４００００見出し語前後の中程度の
英和辞典の場合、重複文字数３ａに３ビット（すなわち
重複７文字まで）、差分文字列長３ｂに５ビット（すな
わち３１文字まで）をそれぞれ割当ておけば十分であ
る。第２フィールドＦ２にはポインタ３ｃ（差分文字列
バッファ４の先頭からのオフセット位置を表わす）が書
込まれる。これも、４００００見出し語前後の中程度の
英和辞典の場合、２バイトで表現可能である（通常の手
法では３バイト必要である）。

【００５３】１次インデックス１は、先頭文字が変わる
最初の項目Ｉ（見出し語）に対する２次インデックス２
上のオフセット１ａをそれぞれ格納したものであり、英
和辞典の場合、図２に示されるような構成となる。２次
インデックス２は、見出し語の先頭文字が変わるごと、
またはｍ件ごとの見出し語の連番２ａが格納されたもの
である。連番２ａは対応する見出し語の辞書における登
録順番を示し、辞書が装置に入力されるときに同時に得
られる。なお、連番２ａは０から開始される。

【００５４】図２においては、見出し語“ａｄｏｐｔ”
が４０件ごとの見出し語として抽出され、その連番２ａ
が３６０であることを表わしている。

【００５５】見出し語本体インデックス３の１つのアイ
テムＩのサイズは前述したように固定長Ｋバイトである
から、２次インデックス２からアクセスすべきインデッ
クス３上の位置は、（２次インデックス２で得られた連
番２ａ）×Ｋバイト目と速やかに求められることは明ら
かであろう。

【００５６】差分文字列バッファ４には、各見出し語の
文字列を１つ前に登録されている見出し語文字列と先頭
から比較して、最初に一致しなくなる位置から最後の位
置までの部分文字列（差分文字列）がそこに登録された
いずれの部分文字列とも重複することなくすべての見出
し語にわたって切れ目なしに登録されている。

【００５７】図２に示される見出し語本体インデックス
３において、たとえば、見出し語“ａｄｏｒａｂｌｅ”
の項目Ｉ（１０８９バイト目、連番３６３）では、１つ
前の見出し語“ａｄｏｐｔｉｖｅ”と先頭３文字が重複
しているので、重複文字数３ａには３が、差分文字列
“ｒａｂｌｅ”の文字列長は５なので差分文字列長３ｂ
には５がそれぞれセットされる。差分文字列バッファ４
へのポインタ３ｃは、バッファ４中の部分文字列“ｒａ
ｂｌｅ”の先頭文字の位置を指示するようセットされ
る。

【００５８】図１に示されたようなインデックス構造に
しておけば、見出し語本体（アイテムＩ）は固定長とな
るので、見出し語には“連番”でアクセスできる。これ
は、前後のアイテムＩにアクセスしやすくなるうえ、別
のインデックスから見出し語（アイテムＩ）を参照する
ような場合、そのインデックス容量をオフセットデータ
で記述するよりも小さくすることができる。たとえば、
２次インデックス２は、固定長にしておかなければ（た
とえば図１２の先頭３文字インデックス４００の場合）
通常３バイト構造となるが、固定長にしておけば、６４
Ｋ語数以内の規模の辞書であれば２バイト構造で済む。
また、後述する作成方法に従えば、差分文字列バッファ
４が通常のもの（図１２の文字列バッファ６００）の数
分の１程度の容量で構成できるため固定長化による容量
増大（必要となる文字列バッファへのポインタ情報のサ
イズ分）は全く問題にならなくなる。

【００５９】図５は、この発明の一実施例による差分文
字列バッファ４がインデックスデータの容量削減に効果
的な役割を果たすことを示す図である。図５には辞書に
関するソースデータ６と図１２で説明された従来の手法
によるソースデータ６に関する文字列バッファ６００お
よび図１に示された本実施例の手法に従うソースデータ
６に関する差分文字列バッファ４が示される。

【００６０】図１２の従来手法により構成された文字列
バッファ６００は差分文字列を区切り記号（￥０）をつ
けながら丸ごと登録していくので、バッファ６００内に
同じ文字列や部分文字列が異なる場所に複数個存在する
ことになり、バッファ６００内のデータは冗長性のある
データとなっている。これに対して、図１に示された手
法により構成された差分文字列バッファ４は、差分文字
列長の降順にソートされた差分文字列を、これまでにバ
ッファ４に登録された文字列の部分文字列とならない場
合のみ切れ目なしにバッファ４の文字列の最後尾に追加
登録するよう構成されているので、そのデータは冗長性
が抑制されている。図５に示されるように、差分文字列
には類似した文字列が多く出現するので、差分文字列バ
ッファを構成するにはこの実施例に従う方式が効果的で
あることがわかる。

【００６１】図６は、この発明の一実施例によるインデ
ックスデータ作成処理フローチャートである。次に図６
のフローチャートに従ってインデックスデータ作成手順
を説明する。

【００６２】まず、辞書のソースデータから見出し語の
みを取出して辞書順に並べた集合Ｍを準備する（Ｔ
１）。これは図３の入力部１１１を用いて辞書の見出し
語の内容を各見出し語が明確に判別できるようなフォー
マットで記憶装置１０１中のファイルに書込む。なお、
このとき、各見出し語の連番も得られる。

【００６３】次に、各見出し語の先頭文字が変わるごと
あるいはｍ件ごとに抽出された見出し語の０番から数え
た連番２ａを順次登録し、これを２次インデックス２と
する（Ｔ２）。なお１次インデックス１の作成処理は、
このフローでは省略されるが、１次インデックス１には
２次インデックス２の先頭文字の変わり目の辞書連番２
ａが書込まれた位置（２次インデックス２の先頭からの
オフセット１ａ）を順次登録すればよい。

【００６４】次に、集合Ｍの隣接する各要素Ｍｉ−１、
Ｍｉに対して、連番ｉが２次インデックス２に登録され
ているものであれば、連番ｉに対応の見出し語本体イン
デックス３の重複文字数Ｄｉ（重複文字数３ａ）に０、
および差分文字列長Ｓｉ（差分文字列長３ｂ）にその見
出し語の文字列長をそれぞれセットし、さらに差分文字
列ＭＳｉに見出し語文字列自体をセットし（Ｔ４）、連
番ｉが２次インデックス２に登録されたものでなけれ
ば、１つ前の見出し語との重複文字数、差分文字列、お
よび差分文字列長を求めて、重複文字数Ｄｉ、差分文字
列ＭＳｉおよび差分文字列長ＭＳｉにそれぞれセットす
る（Ｔ３）。このようにしてすべての見出し語について
抽出された差分文字列ＭＳｉの集合Ｓを、文字列の長さ
の降順にソートし、長さ降順差分文字列集合Ｓ′を作成
する（Ｔ５）。

【００６５】次に、文字列バッファ４を構成するため
に、まず作業用の文字列バッファｍｊｂの初期値を空文
字列に設定し、集合Ｓ′の要素Ｓ′ｉ（ｉ＝０〜ｎ）を
バッファｍｊｂに順に（登録する必要があるもののみ）
登録していく（Ｔ６）。要素Ｓ′ｉをバッファｍｊｂに
登録するか否かは、要素Ｓ′ｉが、これまでに作成され
たバッファｍｊｂ中のいずれかの部分文字列に一致する
か否かで判断され（Ｔ７）、部分文字列と一致すればそ
の部分文字列のバッファｍｊｂ内でのオフセットが求め
られて、文字列バッファ４へのポインタＰｉ（ポインタ
３ｃ）の値としてセットされる（Ｔ８）。ただし処理フ
ロー中には記述されないが、差分文字列が空文字列であ
る場合にはポインタＰｉ（ポインタ３ｃ）には−１がセ
ットされるものとする（Ｔ８）。一方、部分文字列と一
致しない場合は、バッファｍｊｂの文字列の最後尾に要
素Ｓ′ｉの文字列を付け加えることにより差分文字列が
新規登録される。この場合、追加される位置がバッファ
ｍｊｂの文字列の最後尾なので、ポインタＰｉ（ポイン
タ３ｃ）には文字列が追加される前のバッファｍｊｂの
文字列長をセットすればよい（Ｔ９）。ここでのポイン
タＰｉの添字（ｉ）は、差分文字列の長さの順の番号で
あるが、見出し語本体インデックス３へのポインタＰｉ
の格納位置を特定するために、差分文字列を求める際
に、予め添字ｉと見出し語連番との対応づけをしておく
ものとする。

【００６６】見出し語の差分文字列全件に対するインデ
ックスへの登録操作（Ｔ６〜Ｔ９）が完了すれば（Ｔ１
０）、見出し語全件に対して、見出し語本体インデック
ス３の全アイテムＩについての内容が求まり、同時に差
分文字列バッファ４が構成されたことになる（Ｔ１
１）。

【００６７】図７は、この発明の一実施例によるインデ
ックスを用いた検索処理のフローチャートである。図７
のフローチャートは、入力された検索対象文字列と一致
する見出し語文字列が、前述の図６のフローチャートに
従って作成された見出し語本体インデックス３に存在す
るか否かを、１次インデックス１および２次インデック
ス２を辿ることによって確認するための検索手順を表わ
している。図７のフローチャートに従って、この検索手
順を説明する。

【００６８】なお、２次インデックス２中の各項目は
Ｋ′バイトの固定長であると想定する。また、２次イン
デックス２のオフセットｘの項目位置をアクセスして得
られる見出し語の連番２ａをＲ（ｘ）で表わし、同様
に、２次インデックス２のオフセットｘの項目位置をア
クセスして得られる見出し語文字列をＭ（ｘ）で表わ
す。

【００６９】まず、入力装置１０４から入力された文字
列を取込み、検索対象文字列ＩＮＳにセットする（Ｔ２
０）。次に、文字列ＩＮＳの先頭１文字目のコードから
決まる１次インデックス１の項目位置をアクセスし、得
られる１次インデックス１の値、すなわち２次インデッ
クス２へのオフセット１ａを取得しオフセットｏ２にセ
ットする（Ｔ２１）。次に、２次インデックス２の先頭
から（ｏ２＋Ｋ′）バイト目をアクセスする。このアク
セスされた２次インデックス２の項目位置の値、すなわ
ち見出し語本体インデックス３の連番Ｒ（ｏ２＋Ｋ′）
を取得し、得られた連番Ｒ（ｏ２＋Ｋ′）に対応する見
出し語本体インデックス３のアイテムＩをアクセスし、
入力文字列ＩＮＳと一致する見出し語の存在する可能性
のある連番の範囲［Ｒｓ，Ｒｅ］を限定する作業を行な
う（Ｔ２２）。次に、この連番の範囲［Ｒｓ，Ｒｅ］の
限定作業について詳述する。

【００７０】ここで、２次インデックス２のアクセス位
置における連番Ｒ（ｏ２＋Ｋ′）に対応の見出し語文字
列Ｍ（ｏ２＋Ｋ′）を得る手順について説明する。ま
ず、インデックス本体３のアイテムＩがＫバイトの固定
長であるとすれば、インデックス３の先頭から（連番Ｒ
（ｏ２＋Ｋ′）＊Ｋ）バイト目の位置をアクセスすれば
インデックス３の連番Ｒ（ｏ２＋Ｋ′）番目のアイテム
Ｉの内容が得られる。ここで、連番Ｒ（ｏ２＋Ｋ′）は
インデックス２から得られた連番であるため、１つ前の
見出し語との差分はとられていない。したがって、アク
セスしたアイテムＩ中のポインタ３ｃによる差分文字列
バッファ４のアクセス位置から差分文字列長３ｂ分だけ
文字列を呼出してくれば、それが求める見出し語文字列
Ｍ（ｏ２＋Ｋ′）となる。

【００７１】このようにして得られた見出し語文字列Ｍ
（ｏ２＋Ｋ′）と入力文字列ＩＮＳとを辞書順の大小比
較によって比較し、入力文字列ＩＮＳの方が見出し語文
字列Ｍ（ｏ２＋Ｋ′）よりも小さければ、文字列ＩＮＳ
は文字列Ｍ（ｏ２）よりは大きいか等しいので、入力文
字列ＩＮＳと一致する可能性のある見出し語の存在範囲
は連番の範囲［Ｒ（ｏ２），Ｒ（ｏ２＋Ｋ′）］である
ことがわかる。一方、入力文字列ＩＮＳが見出し語文字
列Ｍ（ｏ２＋Ｋ′）よりも小さくなく、かつ文字列Ｍ
（ｏ２＋Ｋ）＞文字列Ｍ（ｏ２）ならば、入力文字列Ｉ
ＮＳと一致する可能性のある見出し語は範囲［Ｒ（ｏ
２），Ｒ（ｏ２＋Ｋ′）］中にはなかったことがわか
る。この場合は、２次インデックス２の現在のアクセス
位置に続く次の項目位置（ｏ２＋２Ｋ′）バイト目をア
クセスして連番Ｒ（ｏ２＋２Ｋ′）および見出し語文字
列Ｍ（ｏ２＋２Ｋ′）を求め、再び大小比較を行ない、
範囲［Ｒ（ｏ２＋Ｋ′），Ｒ（ｏ２＋２Ｋ′）］（文字
列Ｍ（ｏ２＋２Ｋ′）＞文字列Ｍ（ｏ２＋Ｋ′）の場
合）または範囲［Ｒ（ｏ２），Ｒ（ｏ２＋２Ｋ′）］
（文字列Ｍ（ｏ２＋２Ｋ′）＝Ｍ（ｏ２＋Ｋ′）の場
合）が入力文字列ＩＮＳの存在範囲となっているかどう
かを調べる。以下同様の操作を、入力文字列ＩＮＳがイ
ンデックス２の連番から得られる見出し語文字列よりも
小さくなるまで（このときの２次インデックス２のオフ
セット位置を（ｏ２＋Ｎ＊Ｋ′）とする）行なう。求め
る連番の範囲の連番Ｒｅは連番Ｒ（ｏ２＋Ｎ＊Ｋ′）で
あり、連番Ｒｓは、Ｘ＜Ｎとして、文字列Ｍ（ｏ２＋Ｘ
＊Ｋ′）≠文字列Ｍ（ｏ２＋Ｘ−１）＊Ｋ′）となるよ
うな、オフセット位置（ｏ２＋Ｎ＊Ｋ′）に最も近いオ
フセット位置（ｏ２＋Ｘ＊Ｋ）に対応する連番Ｒ（ｏ２
＋Ｘ＊Ｋ′）である。

【００７２】次の処理では上述のようにして決定された
検索範囲の連番［Ｒｓ，Ｒｅ］に従って、初期連番Ｒｓ
から順に対応する見出し語本体インデックス３中のデー
タにアクセスし、対応の見出し語文字列を求め、その都
度入力文字列ＩＮＳと求められた見出し語文字列との辞
書順に従う大小比較を行なう。ここで、２次インデック
ス２で得られた連番Ｒｓからそれ以降の連番に対応の見
出し語文字列を得る手続（Ｔ２３）を以下に説明する。

【００７３】まず、説明の便宜上、フローを制御するた
めの変数ｉ＝Ｒｓ、見出し語文字列ＷＤｉ−１＝“ ”
（空文字列）と設定する。最初は、変数ｉが２次インデ
ックス２から直接に得られた連番であるため、この連番
に対応の見出し語については１つ前の見出し語との差分
はとられていないので（図６のＴ４参照）、差分文字列
バッファ４のポインタ３ｃｉ（本体インデックス３から
得られる連番ｉに対応のポインタ３ｃ）で示される位置
から３ｂｉ（インデックス３から得られる連番ｉに対応
の差分文字列長３ｂ）バイトだけ文字列を読出してくれ
ば、それがそのまま見出し語文字列ＷＤｉとなる。

【００７４】なお、見出し語本体インデックス３の連番
ｉに対応のアイテムＩをアクセスするには、アイテムＩ
がたとえばＫバイト固定長であるとすれば、先頭からｉ
＊Ｋバイト目の位置をアクセスすればよい。連番ｉをイ
ンクリメントして次の見出し語文字列ＷＤｉを求めるに
は、１つ前の見出し語文字列ＷＤｉ−１の先頭から３ａ
ｉバイト（インデックス３から得られる連番ｉに対応の
重複文字数３ａ）分の文字列に、差分文字列長３ｂｉ≠
０ならば、差分文字列バッファ４のポインタ３ｃｉで示
される位置から差分文字列長３ｂｉ分の文字列を結合す
ればよい。

【００７５】このようにして差分が復元されたｉ番目の
見出し語文字列ＷＤｉと入力文字列ＩＮＳとを辞書順に
従い大小比較し一致すれば該当する見出し語は見出し語
文字列ＷＤｉに特定できたことになり（Ｔ２４，Ｔ２
５）、一致しなければ、連番ｉ＜連番Ｒｅの範囲内（Ｔ
２６で“Ｎ”）で連番ｉをインクリメントして（Ｔ２
７）、次の見出し語との大小比較を順次行なう。連番の
範囲［Ｒｓ，Ｒｅ］内に一致する見出し語がなければ入
力文字列ＩＮＳに該当する見出し語項目がなかったこと
が特定される（Ｔ２８）。

【００７６】ここで、上述した既存の見出し語検索用の
インデックスデータに新たな見出し語検索用のインデッ
クスデータを追加する場合を説明する。

【００７７】この追加は上述した差分文字列バッファ４
の特性を効果的に活用して行なわれる。検索対象となる
辞書にもよるが、差分文字列バッファ４は相当な大きさ
のバッファとなるわけであるが、このような文字列バッ
ファ４に対して、同種の言語の平均的な長さの差分文字
列を追加登録する場合、追加される差分文字列は、それ
までに登録された文字列バッファ４中の部分文字列と一
致することが極めて多い。本実施例では、このような差
分文字列バッファ４に重複する部分文字列が存在するの
を防いで、バッファ４の容量増大を抑制する。これを次
に説明する。図８には、この発明の一実施例による差分
文字列バッファが検索機能追加において効果的な役割を
果たすことを示す図である。たとえば、図８のソースデ
ータ６で見出し語“ａｄｏｐｔ”以下、見出し語““ａ
ｄｏｒａｔｉｏｎ”までは既に構成された差分文字列バ
ッファに存在するが、見出し語“ａｄａｐｔ”以下、見
出し語“ａｄａｐｔｉｏｎ”までは元の辞書にはなく、
今新たにそれらの見出し語を追加しなければならない状
況を考えると、追加分を単独で差分文字列バッファに構
成する場合は図８のバッファ８に示されるような１５バ
イト必要であるが、予め用意された差分文字列バッファ
７が利用できる場合はバッファ９に示されるように僅か
７バイト追加するだけでよい。これは、全く新規に差分
文字列によるバッファを作成するよりもこれまでに構成
された既存の差分文字列バッファに新たな差分文字列を
追加する方がメモリ容量の削減という点で効果的である
ことを表わしている。既存の差分文字列バッファに新た
な差分文字列を追加するには、追加する差分文字列の集
合と、追加される側の差分文字列バッファ４を構成する
基となった差分文字列の集合とを合わせて、再び差分文
字列バッファを最初から作成することにより行なう。こ
れにより、追加分の差分文字列と既存の差分文字列とに
よりデータの冗長性が抑制された差分文字列バッファ４
の共有化が図られる。

【００７８】図９は、この発明の一実施例による見出し
語検索機能に派生語検索機能を追加する場合のインデッ
クス構造の概略を示す図である。図９に示されるよう
に、差分文字列バッファは見出し語検索機能および派生
語検索機能の両機能により共有されていることがわか
る。

【００７９】図１０は、この発明の一実施例による差分
文字列バッファの共有化によるインデックスデータの追
加処理のフローチャートである。図１０のフローチャー
トに基づいて、差分文字列バッファの共有化によるイン
デックスデータの追加手順を説明する。なお、ここで
は、既存の見出し語集合Ｍに新たな見出し語集合Ａを追
加する場合を想定する。既存の見出し語集合Ｍ＝｛Ｍ
０，Ｍ１，…、Ｍｎ｝に新たな見出し語集合Ａ＝｛Ａ
０，Ａ１，…，Ａｍ｝を追加することにより、図６で述
べたようにして集合Ａの集合Ｍのそれと同様の構造を有
した１次および２次インデックスが作成される（Ｔ３
０，Ｔ３１）。

【００８０】次に、図６で述べた見出し語本体インデッ
クスの作成手順（図６のＴ３およびＴ４参照）に従っ
て、集合Ａの各要素に対しても重複文字数ＡＤｉ、１つ
前の見出し語との差分文字数ＡＳｉおよび差分文字列Ａ
ＡＳｉが求められる（Ｔ３２）。そして、既存の見出し
語集合Ｍに対する差分文字列ＭＳｉと追加分の差分文字
列ＡＡＳｉとを合わせた全体の差分文字列集合Ｓ＝｛Ｍ
Ｓ０，…、ＭＳｎ，ＡＡＳ０，…，ＡＡＳｍ｝が求めら
れ、集合Ｓの要素を文字列長順にソートした集合Ｓ′＝
｛Ｓ０′，…、Ｓｋ′｝（ただしｋ＝ｎ＋ｍ＋１）が作
成される（Ｔ３３）。

【００８１】集合Ｓ′からその文字列バッファｍｊｂを
構成する手順（Ｔ３４〜Ｔ３７）は、図６で示されたも
のと全く同様である（図６のＴ６〜Ｔ９参照）。バッフ
ァｍｊｂが構成されると、集合Ｓ′の各要素に対するバ
ッファｍｊｂへのポインタが同時に求められるので、集
合Ｍの各要素の差分文字列バッファへのポインタＰＭｊ
と集合Ａの各要素に対する差分文字列バッファへのポイ
ンタＰＡｊがセットされる。これにより、集合Ｍおよび
集合Ａのそれぞれに対する見出し語本体インデックスが
構成されたことになる（Ｔ３９）。

【００８２】このように、図１０のフローチャートに従
って作成された別の見出し語本体インデックス３も、固
定長データであり、その前後への項目（アイテムＩ）へ
のアクセス時間が短くなるように構成される。また、こ
のフローチャートにより作成された差分文字列バッファ
は、データの冗長がなく、かつ元の見出し語インデック
スの差分文字列バッファと共有される形で再構成され
る。再構成された文字列バッファは、区切り記号（￥
０）で差分文字列を並べた通常のものよりも消費容量が
小さく（数１０Ｋの見出し語件数の辞典に対して通常の
１／１０程度）できる。また、共有せずに単独で作成す
る場合よりもその消費容量を小さく（数１０Ｋの見出し
語件数の追加に対して単独で作成されたバッファの１／
２程度）構成できるので、この実施例によれば、別の見
出し語インデックスデータを追加して検索機能の向上を
図った場合でも、それらデータ追加によるメモリ消費容
量の増加分を効果的に抑制することが可能となる。

【００８３】

【発明の効果】請求項１または２に記載の単語辞書検索
装置によれば、インデックス部において文字列バッファ
は、差分文字列を冗長なく格納するよう構成され、さら
に本体インデックスは各単語に対応して設けられ、かつ
各単語に関する検索のための情報を格納するアイテムが
固定長となるよう構成されるので、インデックス部によ
る消費メモリ容量を小さくすることが可能となる。これ
により、装置に必要とされるメモリ容量が低減されて、
装置のコストダウンを達成できるという効果がある。

【００８４】また、本体インデックス部には固定長アイ
テムの構造が採用されるので、低次インデックスを介し
た本体インデックスへのアクセス時間が短縮されて、検
索処理の高速化が図れるという効果がある。

【００８５】請求項３に記載の単語辞書検索装置によれ
ば、検索対象辞書の追加によりインデックス部の拡張が
行なわれたとしても、拡張本体インデックス生成手段に
より追加辞書に対する本体インデックスも、その各アイ
テムは固定長にして生成されるので、追加された本体イ
ンデックスによる消費メモリ容量の増加が抑制されると
ともに、各アイテムへのアクセス時間が短縮化されて、
追加辞書を対象とした検索処理の高速化が図られるとい
う効果がある。

【００８６】また、拡張文字列格納手段および情報更新
手段により、文字列バッファはそこに格納されるデータ
の冗長性が抑制され、さらに元の単語辞書と追加単語辞
書とにより共有され得るので、検索対象辞書の追加に伴
うインデックス部の消費メモリ容量の増加が抑制され
て、装置の機能向上およびコストパフォーマンスの向上
が同時に図られるという効果がある。

【図面の簡単な説明】

【図１】この発明の一実施例によるインデックスの概略
構造を示す図である。

【図２】この発明の一実施例によるインデックスの具体
的構造を示す図である。

【図３】この発明の一実施例による単語辞書検索装置の
機能ブロック構成図である。

【図４】この発明の一実施例による単語辞書検索装置の
ハードウェア構成図である。

【図５】この発明の一実施例による差分文字列バッファ
がインデックスデータの容量削減に効果的な役割を果た
すことを示す図である。

【図６】この発明の一実施例によるインデックスデータ
作成処理のフローチャートである。

【図７】この発明の一実施例によるインデックスを用い
た検索処理のフローチャートである。

【図８】この発明の一実施例による差分文字列バッファ
が検索機能追加において効果的な役割を果たすことを示
す図である。

【図９】この発明の一実施例による見出し語検索機能に
派生語検索機能を追加する場合のインデックス構造の概
略を示す図である。

【図１０】この発明の一実施例による差分文字列バッフ
ァの共有化によるインデックスデータの追加処理のフロ
ーチャートである。

【図１１】（ａ）および（ｂ）は、従来の可変長見出し
語インデックスの一般的な構造を示す図である。

【図１２】（ａ）および（ｂ）は、従来の見出し語本体
をポインタデータのみの固定長にした見出し語インデッ
クスの構造を示す図である。

【図１３】従来の見出し語検索機能に派生語検索機能を
追加した場合のインデックス構造の概略を示す図であ
る。

【符号の説明】

１ １次インデックス ２ ２次インデックス ３ 見出し語本体インデックス ４ 差分文字列バッファ １１０ 制御部 １１１ 入力部 １１２ 記憶部 １１３ 表示部 １１４ インデックスデータ作成部 １１５ インデックスデータ追加部 １１６ 検索部 １ａ オフセット ２ａ 連番 ３ａ 前単語との重複文字数 ３ｂ 差分文字列長 ３ｃ 差分文字列バッファへのポインタ なお、各図中同一符号は同一または相当部分を示す。

Claims (3)

(57)【特許請求の範囲】
1. 【請求項１】 少なくとも単語辞書の本体データおよび
   前記辞書検索用のインデックス部を記憶し、指定された
   単語を前記インデックス部を介して前記辞書本体データ
   から検索する単語辞書検索装置であって、 前記インデックス部はさらに、 前記辞書中の各単語について、その文字列の前記辞書中
   で該単語の直前に登録された単語の文字列と一致しない
   部分文字列である差分文字列が、そこに既に格納された
   文字列中のいずれの部分文字列とも重複することなく順
   次格納される文字列バッファと、 前記辞書中の各単語に対応した固定長アイテムを有し、
   各アイテムには対応する単語の文字列の前記辞書中で該
   単語の直前に登録された単語の文字列と一致する部分文
   字列の長さおよび前記差分文字列の長さに関する情報、
   ならびに前記差分文字列の前記文字列バッファにおける
   格納位置に関する情報が格納される本体インデックス
   と、 前記本体インデックス中の各アイテムの情報を前記指定
   単語の文字列に従ってアクセスするための低次インデッ
   クスとを備えた、単語辞書検索装置。
2. 【請求項２】 前記単語辞書検索装置は、前記インデッ
   クス部を生成する手段をさらに備え、 前記インデックス部生成手段は、 前記辞書中の各単語について、その文字列と前記辞書中
   の該単語の直前に登録された単語の文字列とを比較し、
   前記一致部分文字列長および前記差分文字列長に関する
   情報、ならびに前記差分文字列を検出する情報検出手段
   と、 前記検出された差分文字列が前記文字列バッファに既に
   格納されている文字列中のいずれの部分文字列とも一致
   しないことに応じて、該差分文字列を前記文字列バッフ
   ァ中の文字列後尾に順次追加格納する文字列格納手段
   と、 前記文字列格納手段による前記差分文字列の前記文字列
   バッファにおける格納位置に関する情報ならびに前記情
   報検出手段により検出された前記一致部分文字列長およ
   び前記差分文字列長に関する情報を前記本体インデック
   スの対応する前記アイテムに順次格納する情報格納手段
   と、 前記情報格納手段により前記各単語の情報が格納された
   アイテム位置に基づいて、前記低次インデックスを生成
   する手段とをさらに含む、請求項１に記載の単語辞書検
   索装置。
3. 【請求項３】 前記インデックス部生成手段は、検索対
   象辞書が前記単語辞書に、これとは異なる単語辞書が追
   加されて拡張される場合に、拡張された前記インデック
   ス部を生成する手段を有し、 前記拡張インデックス部生成手段は、 前記追加辞書中の各単語について、その文字列と前記追
   加辞書中の該単語の直前に登録された単語の文字列とを
   比較し、一致する部分文字列の長さおよび一致しない部
   分文字列である差分文字列の長さに関する情報、ならび
   に該差分文字列を検出する拡張情報検出手段と、 前記情報検出手段により検出された差分文字列または前
   記拡張情報検出手段により検出された差分文字列が、前
   記文字列バッファに既に格納されている文字列中のいず
   れの部分文字列とも一致しないことに応じて、該差分文
   字列を前記文字列バッファ中の文字列後尾に順次追加格
   納する拡張文字列格納手段と、 前記拡張文字列格納手段により格納された前記差分文字
   列の前記文字列バッファ内の位置情報を用いて前記情報
   格納手段により前記本体インデックスに格納された格納
   位置情報を更新する手段と、 前記拡張文字列格納手段により格納された前記差分文字
   列の前記文字列バッファ内の位置情報ならびに前記拡張
   情報検出手段により検出された前記追加辞書中の各単語
   に関する一致部分文字列長および差分文字列長に関する
   情報を用いて前記追加辞書に対応の前記本体インデック
   スを生成する拡張本体インデックス生成手段と、 前記拡張本体インデックス生成手段により生成された本
   体インデックスにおける前記追加辞書中の各単語の情報
   が格納されたアイテム位置に基づいて、前記追加辞書に
   対応の前記低次インデックスを生成する拡張低次インデ
   ックス生成手段とをさらに備えた、請求項２に記載の単
   語辞書検索装置。