JPH10319990A - 単語辞書データの圧縮方法、単語辞書データの展開方法、音声認識装置、音声認識機能付きナビゲーションシステム及び記録媒体 - Google Patents

Abstract

(57)【要約】 【課題】 単語音声認識に用いて有効なグラフ形式の単
語辞書データへ変換し、さらに転送時に有利かつ容易に
展開可能なようにデータ圧縮を施す。 【解決手段】 図５に示すグラフ辞書データを第２の変
換処理にて「ほ，あ，＼，ん，み，＼，ま，ちょ，＼，
ち，＼，Ｗ，１，＼，う＼，Ｊ，８，Ｗ，２，き，＼，
た，＼，Ｗ，３，＼，い，＼，お，＼，い，＼，Ｗ，
４，＼」という圧縮辞書データに変換する。これは、頂
点に割り付けられたラベルを、「ほ」→「ん」→「ま」
→「ち」→「Ｗ」→……という先行順走査を基本としな
がら、「ほ」については兄弟「あ」があり、「ん」につ
いては兄弟「み」があり、「ま」については兄弟「ち
ょ」があるため、それらについてもついでに走査してい
くという「第２の走査順」に従って並びかえている。そ
して、自己の兄弟関係を他と区別するための識別データ
として「＼」を設定してある。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、例えばナビゲーシ
ョンシステムにおける目的地の設定等を音声によって入
力できるようにする場合等に用いる音声認識などに用い
て有効な単語辞書データの圧縮方法、単語辞書データの
展開方法、音声認識装置、音声認識機能付きナビゲーシ
ョンシステム及び記録媒体に関する。

【０００２】

【従来の技術及び発明が解決しようとする課題】従来よ
り、入力音声を予め記憶されている複数の比較対象パタ
ーン候補と比較して認識する方法あるいはその方法を用
いた装置が既に実用化されている。例えばカーナビゲー
ションシステムなどにおいて目的地等を音声で入力する
ために用いる音声認識装置などがそうである。この単語
音声の認識に際しては、まず、外部からの入力音声を分
析して音響的特徴量を抽出し、周知のＤＰマッチング法
等によって、その抽出された音響的特徴量の時系列デー
タを、単語辞書に認識すべき単語毎に登録されている音
響的特徴量を用いて、何れかの単語の音響的特徴量に最
も近似したデータ列毎に区分し、その区分したデータ列
毎に、対応する音響的特徴量が表わす単語を割り当てる
ことによって、入力音声の単語系列を認識する。そし
て、その認識結果はナビゲーション装置側に出力され
る。

【０００３】ナビゲーションという性質を考えれば、こ
の指示データの中心を成すのが上述した目的地等を示す
地名データである。そして、この地名データは、ナビゲ
ーション処理に用いる地図データの一部という性質か
ら、新規に追加されたりあるいは更新される状況も多く
想定される。そのため、その新規追加あるいは更新に対
応しようとすると、音声認識装置に対して外部から地名
データに対応する単語辞書データを供給する必要があ
る。

【０００４】しかしながら、ナビゲーション装置から音
声認識装置へ大規模な単語辞書データを転送すると、そ
の通信時間が長くなり、実用的でなくなる。また、地名
の場合には、単語を構成する音節データの等しい単語が
複数存在する可能性が高い。その理由の一つとして、あ
る特定の地名以外に、東西南北や上中下などが追加され
たような地名が多く存在することが挙げられる。また、
別の理由として、同じ場所を示す場合に複数の言い換え
が存在する可能性があることも挙げられる。つまり、
「本町」を「ほんまち」といったり「ほんちょう」とい
ったすることなどである。

【０００５】そのため、例えば地名のように、音節デー
タの等しい単語が複数存在するような単語群からなる単
語辞書データにおいては、通常の単語毎にテキスト形式
で作成したデータではなく、それらをグラフ形式の単語
辞書データとすることも有利である。つまり、グラフ形
式の代表例である木構造で言えば、同じ音節データを持
つ単語同士を同じ親を持つように割り付ければよいから
である。

【０００６】但し、このようなグラフ形式の単語辞書デ
ータに変換するには大量のメモリとなり高性能なＣＰＵ
が必要とされる。従って、音声認識装置側にそれらを備
えることは実用的ではなく、やはり、外部で作成した単
語辞書データを転送する必要があり、上述したのと同様
の問題がある。

【０００７】本発明は、このような問題を解決するた
め、例えば単語音声認識に用いて有効なグラフ形式の単
語辞書データへ変換し、さらに転送時に有利かつ容易に
展開可能なようにデータ圧縮を施すことのできる単語辞
書データの圧縮方法、そしてその単語辞書データの展開
方法、音声認識装置、音声認識機能付きナビゲーション
システム及び記録媒体を提供することを目的とするもの
である。

【０００８】

【課題を解決するための手段及び発明の効果】本発明の
単語辞書データの変換方法は、単語を構成する音節デー
タの等しい単語が複数存在するような単語群をテキスト
形式で作成した単語辞書データを圧縮する方法であっ
て、前記テキスト形式の単語辞書データを、木構造を基
本とするが頂点へ到達する通路の個数は必ずしも１では
ない木構造類似の有向グラフ形式に対応するよう、前記
音節データ及び単語終了を示す識別データを第１の走査
順にしたがって各頂点に割り付けると共に、各頂点毎に
自分の子及び兄弟識別用のデータを持たせたグラフ辞書
データに変換する第１の変換処理と、前記第１の変換処
理によって得た前記グラフ辞書データに対し、前記木構
造類似の有向グラフの頂点に割り付けられた音節及び単
語終了を示す識別データを、前記第１の走査順に基本的
には従いながら前記頂点に兄弟が存在する場合には当該
兄弟についても走査していく第２の走査順に従って並び
かえると共に、自己の兄弟関係を他と区別するための識
別データとを持たせた圧縮辞書データに変換する第２の
変換処理と、を行なうことによって、前記単語辞書デー
タを実質的に圧縮することを特徴とする。

【０００９】本発明方法は、単語を構成する音節データ
の等しい単語が複数存在するような単語群をテキスト形
式で作成した単語辞書データを圧縮することを前提とし
ている。この「単語を構成する音節データの等しい単語
が複数存在するような単語群」を持つ単語辞書としては
種々考えられるが、例えば後述するようにナビゲーショ
ンシステムにおいて音声にて目的地などを入力する場合
には、地名を表す単語群が対象となるが、この地名の場
合には特に音節データの等しい単語が複数存在する可能
性が高い。その理由の一つとして、ある特定の地名以外
に、東西南北や上中下などが追加されたような地名が多
く存在することが挙げられる。また、別の理由として、
同じ場所を示す場合に複数の言い換えが存在する可能性
があることも挙げられる。つまり、「本町」を「ほんま
ち」といったり「ほんちょう」といったすることなどで
ある。

【００１０】もちろん、このような地名を表す単語群に
限らず、他にも同様の性質を持つ単語群であれば適用で
き、また後述する作用・効果を好適に発揮できる。本発
明方法によれば、テキスト形式で作成された単語辞書デ
ータを、以下に示すように、まず、第１の変換処理によ
ってグラフ辞書データに変換し、続いて、第２の変換処
理によってそのグラフ辞書データをさらに圧縮辞書デー
タに変換する。

【００１１】（１）第１の変換処理 グラフ辞書データへの変換は、木構造を基本とするが頂
点へ到達する通路の個数は必ずしも１ではない木構造類
似の有向グラフ形式に対応するよう、音節データ及び単
語終了を示す識別データを第１の走査順にしたがって各
頂点に割り付けると共に、各頂点毎に自分の子及び兄弟
識別用のデータを持たせたグラフ辞書データに変換す
る。

【００１２】なお、「木構造類似の有向グラフ形式」と
は、基本的には木構造に準じているが、頂点へ到達する
通路の個数は必ずしも１ではなく複数でもよい、つまり
一旦分岐した頂点がその後「合流」することを許してい
るので、このように呼ぶこととする。

【００１３】そして、各頂点に割り付けられた音節デー
タ及び単語終了を示す識別データを毎に自分の子及び兄
弟を識別するためのデータを持たせることで、木構造で
いうところの親子の順番で各音節データをつなげていけ
ば単語データとなる。日本語の場合には音節データは約
１１０個程度しかなく、特に最初の１つあるいは２つ以
上が同じ音節データとなる単語は多いため、それらの同
じ音節データについては重複して持たなくてよいため、
辞書データとして記憶しておく際などに有利である。も
ちろん、日本語に限らず、音節データ自体は、どの言語
においても極端に多いことはないため、同じ音節データ
については重複して持たなくてよく、辞書データとして
記憶しておく際などに有利であることは同様である。

【００１４】また、第１の走査順としては、例えば先行
順走査（preorder traversal）を採用することが考えら
れる。ここでいう「走査」とは、ある順番に従って各頂
点を訪問していくことを指すが、「先行順走査」とは、
根を訪問し、次に子を根とする部分木を順番に走査（こ
の走査も先行順走査である。）していくことを指す。も
ちろん、他の走査として「inorder traversal」や「pos
torder traversal」があるが、これらの走査であっても
実現は可能である。

【００１５】（２）第２の変換処理 第２の変換処理では、このようなグラフ辞書データをさ
らに圧縮辞書データに変換する。圧縮辞書データは、グ
ラフ辞書データに対し、木構造類似の有向グラフの頂点
に割り付けられた音節及び単語終了を示す識別データ
を、第１の走査順に基本的には従いながら頂点に兄弟が
存在する場合には当該兄弟についても走査していく第２
の走査順に従って並びかえると共に、自己の兄弟関係を
他と区別するための識別データとを持たせたものであ
る。

【００１６】つまり、第１の変換処理によって得たグラ
フ辞書データの状態では、各頂点の音節データ毎に、
自分の子を識別するためのデータと、兄弟を識別する
ためのデータを持っていることとなるが、この第２の変
換処理によって得られる圧縮辞書データの状態では、上
記の自分の子を識別するためのデータは有しておら
ず、それだけでもデータ量が減る。

【００１７】さらに、上記のように各音節データ毎に
兄弟を識別するためのデータを持っているのではなく、
その代わりに、自己の兄弟関係を他と区別するための識
別データを持っている。この「自己の兄弟関係を他と区
別するための識別データ」としては、例えば所定の音節
が末弟であることを示すデータを用いたり、兄弟数を示
すデータを用いたりすることが考えられる。このように
すれば、例えば、同一の兄弟関係となる音節データが５
つ存在すれば、その５つの音節データに対して兄弟数５
というデータだけを持たせるか、あるいはその末弟とな
る音節データだけにその末弟であることを示すデータを
持たせるだけでよい。

【００１８】この具体例で言えば、第１のグラフ辞書デ
ータの状態では５つの音節データ毎に兄弟を識別するた
めのデータが必要であったが、第２のグラフ辞書データ
の状態では、兄弟数を示す「５」か末弟の音節データだ
けに識別のデータを持たせればよいので、データ量が減
ることとなる。その結果、さらなるデータ圧縮が実現さ
れることとなる。

【００１９】このように自分の子を識別するためのデー
タは有しておらず、さらに、兄弟を識別するためのデー
タとしても、データ５つの音節データに対して兄弟数を
示す「５」か末弟の音節データだけに識別のデータを持
たせればよいのは、本第２の変換処理の次のような性質
に起因する。すなわち、第２の変換処理は、構造類似の
有向グラフの頂点に割り付けられた音節データを、基本
的には第１の走査順に従いながら頂点に兄弟が存在する
場合には当該兄弟についても走査していく第２の走査順
に従って並びかえている。それと共に、自己の兄弟関係
を他と区別するための識別データとを持たせている。つ
まり、親子関係や兄弟関係を識別するためのデータを音
節データ毎に設定しなくても、並びかえた音節データの
順番自体が、木構造類似の有向グラフにおける親子や兄
弟の関係を何等かの形で示すこととなるのである。但
し、順番自体だけでは足らないので、自己の兄弟関係を
他と区別するための識別データとを持たせてある。これ
により、まず音節データ毎の兄弟関係を解析することは
可能となり、また、兄弟関係が判れば、並びかえた音節
データの順番と共に解析することで、明示しない親子関
係も判ることとなる。

【００２０】したがって、このようにして得た圧縮辞書
データは、データ量としても相対的に少なくなり、例え
ば単語辞書データを用いる装置へ外部から転送しようと
した場合の通信時間が短縮できるなど、種々のメリット
がある。また、その単語辞書データを用いる装置におい
ては、圧縮辞書データを所定の形式のグラフ辞書データ
へ展開して使用することが考えられるが、その展開処理
も容易に行える。

【００２１】一方、上述した単語辞書データの圧縮方法
によって圧縮された圧縮辞書データを展開する方法とし
ては、例えば、圧縮辞書データ中の音節及び単語終了を
示す識別データが第２の走査順にしたがって並び替えら
れていると共に、頂点に兄弟が存在する場合にはその兄
弟関係を他と区別するための識別データが存在すること
に基づき、その圧縮辞書データ中の音節及び単語終了を
示す識別データに加え、当該音節及び単語終了を示す識
別データ毎に自分の子を識別するためのデータを設定し
て第２のグラフ辞書データに展開する方法が挙げられ
る。

【００２２】これは、上述した単語辞書データの圧縮方
法での第２の変換処理における変換過程を考慮して、逆
に、圧縮辞書データ中の音節及び単語終了を示す識別デ
ータ毎に、自分の子を識別するためのデータを復活させ
るのである。つまり、圧縮辞書データ中の音節及び単語
終了を示す識別データは、第２の走査順にしたがって並
び替えられていると共に、頂点に兄弟が存在する場合に
はその兄弟関係を他と区別するための識別データが設定
されているため、その点を考慮すれば、木構造類似の有
向グラフの頂点の親子関係から自分の子は容易に解析で
きるのである。

【００２３】なお、このようにして展開した第２のグラ
フ辞書データは、上述した圧縮方法での第１の変換処理
によって得たグラフ辞書データの状態と必ずしも同じで
はない。上述のグラフ辞書データでは、各頂点に割り付
けられた音節データ及び単語終了を示す識別データ毎に
自分の子及び兄弟を識別するためのデータを持たせてい
たが、本展開処理において得る第２のグラフ辞書データ
では、自分の兄弟を識別するためのデータを各頂点に割
り付けられた音節データ及び単語終了を示す識別データ
毎に持たせなくてはならないことはない。この情報につ
いては、兄弟関係を他と区別するための識別データのま
まで残しておいても構わない。

【００２４】いずれにしても、各頂点に割り付けられた
音節データ及び単語終了を示す識別データに加えて、当
該データ毎に自分の子を識別するためのデータと、兄弟
関係を他と区別するための識別データを最低限持つこと
ができるため、この第２の辞書データは単語辞書として
十分用いることができる。

【００２５】なお、上述した単語辞書データの圧縮方法
においては、第１の変換処理及び第２の変換処理を経る
ことは実質的にデータ圧縮となるのであるが、これは、
単語を構成する音節データを木構造類似の有向グラフの
頂点に割り付けることを前提とした特殊なデータ圧縮で
ある。つまり、例えば可変長符号化といった一般的なデ
ータ圧縮技法ではなく、圧縮対象の単語群の音節データ
にかかる性質に基づくものである。したがって、第２の
変換処理によって圧縮辞書データに変換された単語辞書
データを、さらに所定のデータ圧縮方法を用いて圧縮し
てもよい。この「所定のデータ圧縮方法」とは、上述し
た例えば可変長符号化といった一般的なデータ圧縮技法
による圧縮方法である。

【００２６】このようにすれば、さらなるデータ圧縮を
実現することができる。そして、このように所定のデー
タ圧縮方法によってさらなるデータ圧縮をした場合に
は、圧縮辞書データの展開方法としても、所定の圧縮方
法によって圧縮された状態の前記単語辞書データを、当
該所定の圧縮方法による圧縮前の状態である前記圧縮辞
書データに伸長し、当該伸長した前記圧縮辞書データ中
の前記音節及び単語終了を示す識別データが前記第２の
走査順にしたがって並び替えられていると共に、前記頂
点に兄弟が存在する場合にはその兄弟関係を他と区別す
るための識別データが存在することに基づき、その圧縮
辞書データ中の音節及び単語終了を示す識別データに加
え、当該音節及び単語終了を示す識別データ毎に自分の
子を識別するためのデータを設定して第２のグラフ辞書
データに展開することが考えられる。

【００２７】なお、上述したこのような単語辞書データ
の圧縮方法や展開方法を実行するプログラムは、例え
ば、コンピュータシステム側で起動するプログラムとし
て備えられる。このようなプログラムの場合、例えばフ
ロッピーディスク、光磁気ディスクやＣＤ−ＲＯＭ、ハ
ードディスク等の機械読取り可能な記録媒体に記憶し、
必要に応じてコンピュータシステムにロードして起動す
ることにより用いることができる。この他、ＲＯＭやバ
ックアップＲＡＭを機械読み取り可能な記録媒体として
前記プログラムを記憶しておき、このＲＯＭあるいはバ
ックアップＲＡＭをコンピュータシステムに組み込んで
用いてもよい。

【００２８】一方、上述した単語辞書データの圧縮方法
にて圧縮した単語辞書データを用いる音声認識装置とし
ては、例えば、次に示すような構成を挙げることができ
る。その構成は、認識すべき複数の単語の音響的特徴量
が、各単語毎に予め格納された単語辞書記憶手段と、外
部からの入力音声を分析して音響的特徴量を抽出する音
響分析手段と、該音響分析手段にて抽出された音響的特
徴量の時系列データを、前記単語辞書記憶手段に格納さ
れた音響的特徴量に最も近似したデータ列毎に区分し、
データ列毎に、対応する音響的特徴量が表わす単語を割
り当て、前記入力音声の単語系列を認識する音声認識手
段と、該音声認識手段による認識結果を外部装置に出力
する出力手段と、を備えた音声認識装置において、前記
単語辞書データを、前記請求項１乃至５のいずれかに記
載の単語辞書データの圧縮方法によって前記圧縮辞書デ
ータに変換された状態で外部装置から入力する圧縮辞書
データ入力手段と、前記圧縮辞書データ入力手段を介し
て入力した前記圧縮辞書データを、前記請求項７又は８
に記載の単語辞書データの展開方法によって前記第２の
グラフ辞書データに展開する圧縮辞書データ展開手段と
を備え、前記単語辞書記憶手段には、前記圧縮辞書デー
タ展開手段によって前記第２のグラフ辞書データに展開
された状態の単語辞書データが記憶されていることを特
徴とするものである。

【００２９】本音声認識装置においては、単語辞書記憶
手段に、認識すべき複数の単語の音響的特徴量が、音声
認識手段にて認識すべき単語の音響的特徴量として各単
語毎に格納されている。そして、外部から音声が入力さ
れると、まず、音響分析手段が、その入力音声を分析し
て音響的特徴量を抽出する。すると、音声認識手段が、
音響分析手段にて抽出された音響的特徴量の時系列デー
タを、単語辞書記憶手段に格納された単語の音響的特徴
量に最も近似したデータ列毎に区分し、その区分したデ
ータ列毎に、対応する音響的特徴量が表わす単語を割り
当ることによって、入力音声中の単語系列を認識する。
また、このように音声認識手段が入力音声中の単語系列
を認識すると、その認識結果は出力手段を介して外部装
置に出力する。つまり、使用者が音声入力した必要な単
語系列のみが提供されることとなる。

【００３０】そして、この音声認識装置においては、単
語辞書記憶手段に単語辞書データは次のようにして記憶
される。つまり、圧縮辞書データ入力手段が、上述した
単語辞書データの圧縮方法によって圧縮辞書データに変
換された状態で単語辞書データを外部装置から入力す
る。そして、圧縮辞書データ展開手段が、その入力した
圧縮辞書データを、上述した単語辞書データの展開方法
によって第２のグラフ辞書データに展開する。この第２
のグラフ辞書データに展開された状態の単語辞書データ
が単語辞書記憶手段に記憶されることとなる。

【００３１】このように、圧縮辞書データに変換された
状態で単語辞書データを外部装置から入力することがで
きるので、単語辞書データを外部装置から入力する際の
通信時間を短縮することができる。また、単語辞書記憶
手段には記憶されている単語辞書データは、単語音声の
認識処理にとっては有効な形式であるグラフ辞書形式の
データである。例えばテキスト形式の単語辞書データと
して入力された場合には、それをグラフ形式の辞書デー
タの変換するために要する時間とメモリがかなり多く必
要となるが、そのような不利が生じない。

【００３２】なお、上述した音声認識装置においては、
圧縮辞書データに変換された状態で単語辞書データを外
部装置から入力し、それを第２のグラフ辞書データに展
開してから単語辞書記憶手段に記憶するようにしたが、
単語辞書記憶手段には、圧縮辞書データ入力手段によっ
て外部装置から入力した圧縮辞書データの状態で記憶し
ておき、電源投入時又は音声認識処理実行時に、圧縮辞
書データ記憶手段から読み出した圧縮辞書データを第２
のグラフ辞書データに展開するような構成も採用でき
る。

【００３３】このようにすれば、記憶しておく必要のあ
る単語辞書データのデータ量が相対的に少なくて済む。
つまり、単語辞書データ記憶手段を例えば不揮発性メモ
リで構成するならば、その不揮発性メモリの容量が少な
くてもよくなる。なお、第２のグラフ辞書データに展開
するのが音声認識処理実行時であるならば、その展開時
にのみ必要な揮発性メモリも少なくて済む。

【００３４】また、このような音声認識装置と、ナビゲ
ーション装置とを備えたナビゲーションシステムとして
は、例えば次に示すような構成が考えられる。すなわ
ち、前記音声認識装置の前記音声入力手段は、前記ナビ
ゲーション装置がナビゲート処理をする上で指定される
必要のある所定のナビゲート処理関連データの指示を利
用者が音声にて入力するために用いられるものであり、
前記出力手段は、前記音声認識手段による認識結果を前
記ナビゲーション装置に出力するよう構成されている音
声認識機能付きナビゲーションシステムであって、前記
ナビゲーション装置は、前記単語辞書データを、前記請
求項１乃至４のいずれかに記載の単語辞書データの圧縮
方法によって前記圧縮辞書データに変換された状態で記
憶しておく圧縮辞書データ記憶手段と、所定の辞書転送
必要時に前記圧縮辞書データ記憶手段から前記圧縮辞書
データを読み出し、前記音声認識装置に転送する辞書デ
ータ転送手段と、を備えていることを特徴とする。

【００３５】本ナビゲーションシステムによれば、ナビ
ゲーション装置の圧縮辞書データ記憶手段が、単語辞書
データを圧縮辞書データに変換された状態で記憶してお
り、所定の辞書転送必要時に圧縮辞書データ記憶手段か
ら圧縮辞書データを読み出し、音声認識装置に転送す
る。

【００３６】本ナビゲーションシステムの場合には、音
声認識装置にて認識されたナビゲート処理関連の指示デ
ータがナビゲーション装置に送られ、その指示データに
基づくナビゲーション処理を行なうこととなる。ナビゲ
ーションという性質を考えれば、この指示データの中心
を成すのが地名データである。そして、この地名データ
は、上述したように音節データの等しい単語が複数存在
する可能性が高いという固有の性質に加え、ナビゲーシ
ョン装置側の地図データの一部という性質から新規追加
あるいは更新される状況も多く想定される。

【００３７】そのため、その新規追加あるいは更新に対
応しようとすると、音声認識装置に対して外部から地名
データに対応する単語辞書データを供給する必要があ
る。なぜなら、地名の新規追加あるいは更新は、基本的
にテキスト形式のデータとして実現されることが考えら
れるが、それらを上述のグラフ形式の単語辞書データと
するには大量のメモリとなり高性能なＣＰＵが必要とさ
れる。従って、音声認識装置側にそれらを備えることは
実用的ではなく、外部でそれらの新規追加あるいは更新
に対応して作成されたグラフ形式の単語辞書データを供
給する必要が出て来る。但し、グラフ形式の辞書データ
であってもデータサイズはかなり大きいため、ナビゲー
ション装置から音声認識装置へ単語辞書データを転送す
ることを考えると、大規模な単語辞書データをそのまま
の状態で転送することは通信時間が長くなり、やはり実
用的ではない。そのため、圧縮辞書データの状態にした
上で、音声認識装置側に転送することで、上記通信時間
を短縮することができる。

【００３８】なお、「所定の辞書転送必要時」とは、例
えばナビゲーション装置における地図データの更新時や
バッテリオフ時などが考えられる。また、ナビゲーショ
ン装置が音声認識装置側への転送するための単語辞書デ
ータを圧縮辞書データの状態で記憶しているのである
が、この圧縮辞書データへの変換は、ナビゲーション装
置自体が行ってもよいし、あるいは、外部装置にてその
変換を行なうようにし、ナビゲーション装置は外部装置
から圧縮辞書データを入力して記憶するようにしてもよ
い。上述したように、グラフ形式の単語辞書データとす
るには大量のメモリとかなり高性能なＣＰＵが必要とさ
れる。従って、ナビゲーション装置側にそれらを備える
のでなく、外部装置としての例えばワークステーション
などで変換するようにすることが現実的である。

【００３９】

【発明の実施の形態】図１は本発明の実施形態としての
カーナビゲーションシステム２の全体構成を示すブロッ
ク図である。本カーナビゲーションシステム２は、位置
検出器４、地図データ入力器６、操作スイッチ群８、こ
れらに接続された制御回路１０、制御回路１０に接続さ
れた外部メモリ１２、表示装置１４及びリモコンセンサ
１５及び音声認識装置３０を備えている。なお制御回路
１０は通常のコンピュータとして構成されており、内部
には、周知のＣＰＵ、ＲＯＭ、ＲＡＭ、Ｉ／Ｏ及びこれ
らの構成を接続するバスラインが備えられている。

【００４０】位置検出器４は、周知の地磁気センサ１
６、ジャイロスコープ１８、距離センサ２０、及び衛星
からの電波に基づいて車両の位置を検出するＧＰＳ（Gl
obalPositioning System）のためのＧＰＳ受信機２２を
有している。これらのセンサ等１６，１８，２０，２２
は各々が性質の異なる誤差を持っているため、複数のセ
ンサにより、各々補間しながら使用するように構成され
ている。なお、精度によっては上述した内の一部で構成
してもよく、更に、ステアリングの回転センサ、各転動
輪の車輪センサ等を用いてもよい。

【００４１】地図データ入力器６は、位置検出の精度向
上のためのいわゆるマップマッチング用データ、地図デ
ータ及び目印データを含む各種データを入力するための
装置である。媒体としては、そのデータ量からＣＤ−Ｒ
ＯＭを用いるのが一般的であるが、メモリカード等の他
の媒体を用いても良い。

【００４２】表示装置１４はカラー表示装置であり、表
示装置１４の画面には、位置検出器４から入力された車
両現在位置マークと、地図データ入力器６より入力され
た地図データと、更に地図上に表示する誘導経路や後述
する設定地点の目印等の付加データとを重ねて表示する
ことができる。

【００４３】また、本カーナビゲーションシステム２
は、リモートコントロール端末（以下、リモコンと称す
る。）１５ａを介してリモコンセンサ１５から、あるい
は操作スイッチ群８により目的地の位置を入力すると、
現在位置からその目的地までの最適な経路を自動的に選
択して誘導経路を形成し表示する、いわゆる経路案内機
能も備えている。このような自動的に最適な経路を設定
する手法は、ダイクストラ法等の手法が知られている。
操作スイッチ群８は、例えば、表示装置１４と一体にな
ったタッチスイッチもしくはメカニカルなスイッチ等が
用いられ、各種入力に使用される。

【００４４】そして、音声認識装置３０は、上記操作ス
イッチ群８あるいはリモコン１５ａが手動操作により目
的地などを指示するために用いられるのに対して、利用
者が音声で入力することによっても同様に目的地などを
指示することができるようにするための装置である。

【００４５】この音声認識装置３０は、音声認識部３１
と、対話制御部３２と、音声合成部３３と、音声入力部
３４と、「音声入力手段」としてのマイク３５と、ＰＴ
Ｔ（Push-To-Talk）スイッチ３６と、スピーカ３７とを
備えている。音声認識部３１は、音声入力部３４から入
力された音声データを、対話制御部３２からの指示によ
り入力音声の認識処理を行い、その認識結果を対話制御
部３２に返す。対話制御部３２は、その認識結果及び自
身が管理する内部状態から、音声合成部３３への応答音
声の発声指示や、システム自体の処理を実行する制御回
路１０に対して例えばナビゲート処理のために必要な目
的地を通知して設定処理を実行させるよう指示する処理
を実行する。このような処理が確定後処理であり、結果
として、この音声認識装置３０を利用すれば、上記操作
スイッチ群８あるいはリモコン１５ａを手動しなくて
も、音声入力によりナビゲーションシステムに対する目
的地の指示などが可能となるのである。

【００４６】また前記音声入力部３４は、マイク３５に
て取り込んだ周囲の音声をデジタルデータに変換して音
声認識部３１に出力するものであり、本実施形態におい
ては、利用者がＰＴＴスイッチ３６を押しながらマイク
３５を介して音声を入力するようにされている。つま
り、ＰＴＴスイッチ３６が押されていない場合には、音
声入力部３４は音声認識部３１へ音声データを出力しな
いようにされている。

【００４７】ここで、音声認識部３１と対話制御部３２
の構成について図２を参照してさらに詳しく説明する。
図２に示すように、音声認識部３１は照合部３１ａと辞
書部３１ｂとで構成されており、対話制御部３２は後処
理部３２ａ、通信制御部３２ｂ及び辞書制御部３２ｃで
構成されている。

【００４８】音声認識部３１においては、照合部３１ａ
が、音声入力部３４から取得した音声データに対し、辞
書部３１ｂ内に記憶されている辞書データを用いて照合
を行ない、入力音声中の単語系列を認識する。詳しく
は、音声入力部３４から入力された音声データを順次音
響分析して音響的特徴量（例えばケプストラム）を抽出
し、この音響分析によって得られた音響的特徴量時系列
データを得る。そして、周知のＤＰマッチング法によっ
て、この時系列データをいくつかの区間に分けて、各区
間が辞書部３１ｂに格納されたどの単語に対応している
かを求める「音声認識手段」としての処理を実行する。

【００４９】照合部３１ａでの認識結果は対話制御部３
２の後処理部３２ａへ送られる。後処理部３２ａは、例
えば通信制御部３２ｂを介して制御回路１０へデータを
送って所定の処理をするように指示する確定後処理を実
行したり、あるいは音声合成部３３へ音声データを送っ
て発音させるように指示する処理を実行する。

【００５０】また、対話制御部３２の辞書制御部３２ｃ
は、通信制御部３２ｂを介して制御回路１０から転送さ
れた後述の「圧縮辞書データ」をデータ展開し、さらに
辞書展開してから音声認識部３１の辞書部３１ｂへ書き
込む。これら「データ展開」や「辞書展開」については
後述する。

【００５１】ここで、カーナビゲーションシステム２の
動作について簡単に説明しておく。カーナビゲーション
システム２の電源オン後に、表示装置１４上に表示され
るメニューから、ドライバーがリモコン１５ａ（操作ス
イッチ群８でも同様に操作できる。以後の説明において
も同じ）により、案内経路を表示装置１４に表示させる
ために経路情報表示処理を選択した場合、あるいは、音
声認識装置３０を介して希望するメニューをマイク３５
を介して音声入力することで、対話制御部３２から制御
回路１０へ、リモコン１５ａを介して選択されるのを同
様の指示がなされた場合、次のような処理を実施する。
すなわち、ドライバーが表示装置１４上の地図に基づい
て、音声あるいはリモコンなどの操作によって目的地を
入力すると、ＧＰＳ受信機２２から得られる衛星のデー
タに基づき車両の現在地が求められ、目的地と現在地と
の間に、ダイクストラ法によりコスト計算して、現在地
から目的地までの最も短距離の経路を誘導経路として求
める処理が行われる。そして、表示装置１４上の道路地
図に重ねて誘導経路を表示して、ドライバーに適切なル
ートを案内する。このような誘導経路を求める計算処理
や案内処理は一般的に良く知られた処理であるので説明
は省略する。

【００５２】さて、本カーナビゲーションシステム２に
おいては、上述したように、音声認識装置３０は制御回
路１０から圧縮辞書データを転送してもらい、対話制御
部３２の辞書制御部３２ｃがその圧縮辞書データをデー
タ展開し、さらに辞書展開してから音声認識部３１の辞
書部３１ｂへ書き込む。この圧縮辞書データは、外部装
置、例えばワークステーションなどを用いて生成され
る。この手順は、図３に示すように、テキスト形式で作
成された単語辞書データを、第１の変換処理によってグ
ラフ辞書データに変換し、続いて、第２の変換処理によ
ってそのグラフ辞書データをさらに圧縮辞書データに変
換する。さらに、本実施形態の場合には例えば可変長符
号化といった一般的なデータ圧縮を施し、そのデータ圧
縮された「圧縮辞書データ」を、地図データ及びその他
のデータと共にナビゲーションシステム用の地図ＣＤに
書き込む。そして、この地図ＣＤ内のデータが地図デー
タ入力器６（図１参照）を介して制御回路１０に読み込
まれ、上述したように音声認識装置３０に転送されるの
である。

【００５３】図３の（ｅ）に示す「圧縮辞書データ」に
変換されるまでの処理等について、さらに説明する。ま
ず、図３（ａ）に示す「テキスト辞書データ」について
説明する。上述したように、これはテキスト形式で作成
された単語辞書データであるが、本実施形態の場合に
は、ナビゲーションにおける目的地などを音声認識する
ためのものなので、単語としては主に地名である。この
地名を表す単語群の性質を考えると、単語を構成する音
節データの等しい単語が複数存在するという点が挙げら
れる。その理由の一つとして、ある特定の地名以外に、
東西南北や上中下などが追加されたような地名が多く存
在することが挙げられる。また、別の理由として、同じ
場所を示す場合に複数の言い換えが存在する可能性があ
ることも挙げられる。つまり、「本町」を「ほんまち」
といったり「ほんちょう」といったすることなどであ
る。

【００５４】なお、本実施形態における単語辞書データ
の圧縮方法への理解を容易にするため、テキスト辞書デ
ータとして、次に示す具体例を用いて今後の説明を行な
う。 （１）ほん（まち｜ちょう） （２）ほみ （３）ほみきた （４）あいおい この具体例において、数字（１）〜（４）は単語番号を
示している。また、（まち｜ちょう）における（）は優
先順位を示しており、｜は選択肢を示す。つまり、（ま
ち｜ちょう）は「まち」あるいは「ちょう」のいずれか
一つを選択することとなり、（１）の「ほん（まち｜ち
ょう）」は、「ほんまち」あるいは「ほんちょう」を示
す。但し、「ほんまち」が「ほんちょう」に優先する。
また、本例では使用していないが、［］を付すことで省
略可を示すこともできる。

【００５５】次に、図３（ｂ）の、テキスト辞書データ
を第１の変換処理によってグラフ辞書データに変換する
処理について説明する。この第１の変換処理を説明的に
記述すると、「木構造を基本とするが頂点へ到達する通
路の個数は必ずしも１ではない木構造類似の有向グラフ
形式に対応するよう、音節データ及び単語終了を示す識
別データを第１の走査順にしたがって各頂点に割り付け
ると共に、各頂点毎に自分の子及び兄弟識別用のデータ
を持たせたグラフ辞書データに変換する」ということと
なる。

【００５６】具体例を参照する方が理解が容易になるの
で、図４に示すテキスト辞書データが第１の変換処理に
よって変換された結果としてグラフ辞書データの具体例
を図５〜図７に示す。なお、図５〜図７は同じグラフ辞
書データを示しており、図５は、「木構造類似の有向グ
ラフ形式」で表現した場合であり、図６は同じものをポ
インタ表現で示し、図７は配列表現で示したものであ
る。

【００５７】図５に示す「木構造類似の有向グラフ形
式」は、基本的には木構造に準じているが、頂点へ到達
する通路の個数は必ずしも１ではなく複数でもよい、つ
まり一旦分岐した頂点がその後「合流」することを許し
ているので、このように呼ぶこととする。そして、この
場合の「第１の走査順」はいわゆる「先行順走査（preo
rder traversal）を採用している。ここでいう「走査」
とは、ある順番に従って各頂点を訪問していくことを指
すが、「先行順走査」とは、根を訪問し、次に子を根と
する部分木を順番に走査（この走査も先行順走査であ
る。）していくことを指す。なお、ここで、「親」とは
直前の頂点、「子」とは次の頂点、「兄弟」とは同じ親
を持つ頂点同士をそれぞれ意味する。

【００５８】つまり、例えば上述したテキスト辞書デー
タの単語（１）〜（３）は全て「ほ」で始まるため同じ
親を持つ。また、「ほんまち」と「ほんちょう」は「ほ
ん」まで同じなので、次の「ま」と「ちょ」が兄弟関係
となる。また、「ほん（まち｜ちょう）」と「ほみ」を
考えると、「ほ」の次の「ん」と「み」が兄弟関係とな
る。なお、図５において、矢印（→）は辺を表し、一重
丸（○）は頂点を表し、二重丸（◎）は受理頂点、すな
わち単語に対する頂点を表す。なお、受理頂点における
数字は単語番号を示している。

【００５９】例えば、「ほんまち」と「ほんちょう」は
同じ地名を表す単語であるので、最終的には合流させて
同一の単語を意味させている。つまり同じ受理頂点１に
至るようにしている。また、「ほみ」と「ほみきた」は
「ほみ」が共通であり、さらに「ほみ」だけで単語が終
了しているので、「ほみ」と表した後に受理頂点２を表
し、さらにその後に「きた」と続け、そこで単語が終了
するので受理頂点３を表している。

【００６０】一方、図６では、各ラベル毎に子と兄弟を
示している。ここでは音節データ「ほ」，「ん」，
「ま」，「ち」などをラベルとするが、さらに単語が終
了していることを示すデータとしての「Ｗ」もラベルと
している。図７も同様に各ラベル毎に子と兄弟を示して
いるが、これは配列表現で示したものである。各ラベル
は、上述した第１の走査順、すなわちここでは先行順走
査に従って、「ほ，ん，ま，ち，Ｗ，ちょ，う，み，
Ｗ，き，た，あ，い，お，い，Ｗ」という順番に並べら
れており、ラベル番号１〜１７がそれぞれ割り付けられ
ている。そして、各ラベルに対して、兄弟（Ｂｒｏｓ）
と子（Ｃｈｉｌｄ）のラベル番号が設定されている。例
えば、ラベル番号１の「ほ」に対しては兄弟としてラベ
ル番号１３、子としてラベル番号２が設定されているの
で、兄弟はラベル番号１３の「あ」であり、子はラベル
番号２の「ん」であることが判る。なお、単語が終了し
ていることを示すデータとしての「Ｗ」のラベルについ
ては、単語番号を子のデータとして設定してある。例え
ば、ラベル番号５の「Ｗ」については「ほんまち」とい
う単語の終了を示しており、単語番号が１であるので、
子のデータとして「１」が設定されている。

【００６１】次に、図３（ｄ）に示した「グラフ辞書デ
ータを第２の変換処理によって圧縮辞書データに変換す
る処理」について説明する。この第２の変換処理にて生
成される圧縮辞書データを説明的に記述すると、「第１
の変換処理にて得たグラフ辞書データに対し、木構造類
似の有向グラフの頂点に割り付けられた音節及び単語終
了を示す識別データを、第１の走査順に基本的には従い
ながら頂点に兄弟が存在する場合には当該兄弟について
も走査していく第２の走査順に従って並びかえると共
に、自己の兄弟関係を他と区別するための識別データと
を持たせたもの」となる。

【００６２】具体例を参照する方が理解が容易になるの
で、上述した図５〜図７に示すグラフ辞書データがこの
第２の変換処理にて変換された圧縮辞書データの具体例
を図８に示す。つまり、この場合の圧縮辞書データは、
「ほ，あ，＼，ん，み，＼，ま，ちょ，＼，ち，＼，
Ｗ，１，＼，う＼，Ｊ，８，Ｗ，２，き，＼，た，＼，
Ｗ，３，＼，い，＼，お，＼，い，＼，Ｗ，４，＼」と
なる。

【００６３】上述した図５の木構造類似の有向グラフの
頂点に割り付けられた音節及び単語終了を示す識別デー
タ（ラベル）を、第１の走査順に基本的には従いながら
頂点に兄弟が存在する場合にはその兄弟についても走査
していく「第２の走査順」に従って並びかえている。上
述の第１の走査順が先行順走査であるので、「ほ」→
「ん」→「ま」→「ち」→「Ｗ」→……という先行順走
査を基本としながら、「ほ」については兄弟「あ」があ
り、「ん」については兄弟「み」があり、「ま」につい
ては兄弟「ちょ」があるため、それらについてもついで
に走査していく。そして、自己の兄弟関係を他と区別す
るための識別データとして「＼」を設定してある。例え
ば「ほ，あ」の次に「＼」を入れるなどである。

【００６４】図７に示すグラフ辞書データを図８に示す
圧縮辞書データに変換する際の具体的な処理については
後述するが、このような圧縮辞書データにした場合の効
果について説明する。つまり、第１の変換処理によって
得たグラフ辞書データ（図５〜図７）の状態では、各頂
点の音節データ毎に、自分の子を識別するためのデー
タと、兄弟を識別するためのデータを持っていること
となるが、この第２の変換処理によって得られる圧縮辞
書データ（図８）の状態では、上記の自分の子を識別
するためのデータは有しておらず、それだけでもデータ
量が減る。

【００６５】さらに、上記のように各音節データ毎に
兄弟を識別するためのデータを持っているのではなく、
その代わりに、自己の兄弟関係を他と区別するための識
別データ（＼）を持っている。この識別データとしての
「＼」は、図８に示す場合では、所定の音節が末弟であ
ることを示すデータとして用いている。つまり、図８に
示す例では、「ほ，あ」という兄弟関係では「あ」が末
弟であるので、その後に「＼」を設定してある。この例
では兄弟が２つしかないが、例えば、同一の兄弟関係と
なる音節データが５つ存在すれば、その５つの音節デー
タに対して末弟となる音節データだけにその末弟である
ことを示すデータを持たせるだけでよい。そのため、上
述した自分の子を識別するためのデータは有していない
ことによるデータ量削減に加え、さらなるデータ量削減
が実現できる。その結果、さらなるデータ圧縮が実現さ
れることとなる。

【００６６】なお、「自己の兄弟関係を他と区別するた
めの識別データ」としては、上述の末弟であることを示
すだけでなく、例えば兄弟数を示すデータであってもよ
い。つまり、図８の例で言えば、「ほ，あ」という兄弟
関係について兄弟数が「２」であることが判ればそれで
もよい。この場合でも、兄弟数がいくら多くなってもそ
の兄弟数を示すデータを持たせればよいので、グラフ辞
書データの場合のような各音節データ毎に兄弟を示すデ
ータを持つことがなく、やはりデータ量が減ることとな
る。

【００６７】ところで、圧縮辞書データが、このように
自分の子を識別するためのデータは有しておらず、さら
に、兄弟を識別するためのデータとしても、データ５つ
の音節データに対して末弟の音節データだけに識別デー
タ（＼）を持たせればよいのは、第２の変換処理の次の
ような性質に起因する。すなわち、第２の変換処理は、
構造類似の有向グラフの頂点に割り付けられた音節デー
タを、基本的には第１の走査順に従いながら頂点に兄弟
が存在する場合には当該兄弟についても走査していく第
２の走査順に従って並びかえている。それと共に、自己
の兄弟関係を他と区別するための識別データとを持たせ
ている。つまり、親子関係や兄弟関係を識別するための
データを音節データ毎に設定しなくても、並びかえた音
節データの順番自体が、木構造類似の有向グラフにおけ
る親子や兄弟の関係を何等かの形で示すこととなるので
ある。但し、順番自体だけでは足らないので、自己の兄
弟関係を他と区別するための識別データとを持たせてあ
る。これにより、まず音節データ毎の兄弟関係を解析す
ることは可能となり、また、兄弟関係が判れば、並びか
えた音節データの順番と共に解析することで、明示しな
い親子関係も判ることとなる。

【００６８】したがって、このようにして得た圧縮辞書
データは、データ量としても相対的に少なくなり、例え
ば単語辞書データを用いる装置へ外部から転送しようと
した場合の通信時間が短縮できるなど、種々のメリット
がある。また、その単語辞書データを用いる装置におい
ては、圧縮辞書データを所定の形式のグラフ辞書データ
へ展開して使用することが考えられるが、その展開処理
も容易に行えるのである。

【００６９】続いて、上記説明中では後述するとしてお
いた「図７に示すグラフ辞書データを図８に示す圧縮辞
書データに変換する際の具体的な処理」について説明す
る。図１０に示すように、処理が開始すると、最初のス
テップＳ１０において変数ｎを初期値１に設定し、続く
Ｓ２０では、Ｎｕｍ（ｉ）を初期値０に設定する。な
お、ｉ＝０，１，……Ｎである。このような初期設定が
終了した後、Ｓ３０にて圧縮処理が開始する。

【００７０】この圧縮処理の詳細を図１１，１２を参照
して説明する。なお、図１１，１２は圧縮（ｐ）処理と
して一般化して表してあり、ｐ＝１の場合が圧縮（１）
処理となる。従って、図１０のＳ３０は、圧縮（１）処
理である。図１１の最初のステップＳ１１０では変数ｑ
＝ｐに設定する。つまり、圧縮（１）処理であればｑ＝
ｐ＝１となる。そして、続くＳ１２０においてｑと０と
を比較し、ｑ＝０であればＳ１８０へ移行するが、ｑ＝
０でなければＳ１３０へ移行する。

【００７１】Ｓ１３０では、Ｎｕｍ（ｑ）＝ｎに設定す
ると共に、ｎをインクリメント（ｎ＝ｎ＋１）する。そ
して、続くＳ１４０では、Ｌａｂｅｌ（ｑ）の内容を単
語終了を示す「Ｗ」と比較し、Ｌａｂｅｌ（ｑ）の内容
ｓが「Ｗ」であればＳ１７０へ移行し、Ｌａｂｅｌ
（ｑ）の内容ｓが「Ｗ」でなければＳ１５０へ移行す
る。

【００７２】Ｓ１７０では、Ｌａｂｅｌ（ｑ）の内容ｓ
が「Ｗ」であるため、「Ｗ」を出力すると共にＣｈｉｌ
ｄ（ｑ）を出力する。一方、Ｓ１５０では、Ｌａｂｅｌ
（ｑ）の内容ｓが「Ｗ」でないので、Ｌａｂｅｌ（ｑ）
自体を出力する。Ｓ１５０あるいはＳ１７０の処理後
は、Ｓ１６０へ移行する。

【００７３】Ｓ１６０では、変数ｑ＝Ｂｒｏｓ（ｑ）と
してＳ１２０へ戻り、Ｓ１２０以下の処理を繰り返す。
一方、Ｓ１２０にてｑ＝０であると判断された場合に移
行するＳ１８０では、「＼」を出力する。そして、図１
２に示すようにＳ１９０へ移行する。

【００７４】Ｓ１９０では、図１１の最初のステップＳ
１１０と同様、変数ｑ＝ｐに設定する。つまり、圧縮
（１）処理であればこの場合もｑ＝ｐ＝１となる。そし
て、続くＳ２００においてｑと０とを比較し、ｑ＝０で
あれば本圧縮（ｐ）処理を終了するが、ｑ＝０でなけれ
ばＳ２１０へ移行する。

【００７５】Ｓ２１０では、Ｌａｂｅｌ（ｑ）を「Ｗ」
と比較し、Ｌａｂｅｌ（ｑ）の内容ｓが「Ｗ」であれば
Ｓ２４０へ移行し、Ｌａｂｅｌ（ｑ）の内容ｓが「Ｗ」
でなければＳ２２０へ移行する。Ｓ２２０では、Ｎｕｍ
（Ｃｈｉｌｄ（ｑ））が０より大きいかどうかを判断す
る。Ｎｕｍ（Ｃｈｉｌｄ（ｑ））＞０であれば（Ｓ２２
０：ＹＥＳ）、Ｓ２５０へ移行し、「Ｊ」を出力すると
共にＮｕｍ（Ｃｈｉｌｄ（ｑ））を出力してから、Ｓ２
４０へ移行する。一方、Ｎｕｍ（Ｃｈｉｌｄ（ｑ））≦
０であれば（Ｓ２２０：ＮＯ）、Ｓ２３０へ移行して、
圧縮（Ｃｈｉｌｄ（ｑ））処理を行なう。この圧縮（Ｃ
ｈｉｌｄ（ｑ））処理は、再帰読み出し処理であり、図
１１〜図１２の処理を行なうこととなる。Ｓ２３０の処
理後はＳ２４０へ移行する。

【００７６】上述のＳ２１０でＬａｂｅｌ（ｑ）の内容
ｓが「Ｗ」である場合、及びＳ２３０あるいはＳ２５０
の処理に移行するＳ２４０では、変数ｑ＝Ｂｒｏｓ
（ｑ）としてＳ２００へ戻り、Ｓ２００以下の処理を繰
り返す。以上が圧縮処理を示すフローチャートの説明で
あるが、より理解を容易にするために、図７に示すグラ
フ辞書データが図８に示す圧縮辞書データに変換される
場合の途中経過を示しながら、さらに説明する。

【００７７】図１３は、図１０のＳ３０での圧縮（１）
処理の内容を概念的に示したものである。つまり、圧縮
（１）処理が実行されていく途中で、図１２のＳ２３０
での圧縮（Ｃｈｉｌｄ（ｑ））処理が実行される。圧縮
（１）処理はｐ＝１の場合の処理であるので、Ｓ１９０
においてｑ＝ｐ＝１となり、Ｓ２３０では圧縮（Ｃｈｉ
ｌｄ（１））処理となる。すなわち図７を参照するとＣ
ｈｉｌｄ（１）＝２であるので、この場合のＳ２３０は
圧縮（２）処理となる。

【００７８】このようにして、結果的には圧縮（１４）
処理が終了すると、圧縮（１）処理が終了することとな
る。図１３におけるＡ点は圧縮（２）処理に移行する直
前を示し、同じくＢ点は圧縮（２）処理が終了した時点
を示し、Ｃ点は圧縮（１４）処理が終了した時点を示す
る。図１４では、これらＡ点、Ｂ点及びＣ点での状態
（途中経過）を示している。

【００７９】まず、Ａ点に至るまでの経過を順に見てみ
る。圧縮（１）処理では、ｐ＝１であるので、図１１の
Ｓ１１０にてｑ＝ｐ＝１となり、Ｓ１２０では、ｑ＝１
＞０であるため、Ｓ１３０へ移行する。Ｓ１３０では、
Ｎｕｍ（ｑ（＝１））＝ｎ（＝１）に設定する。これ
は、図１０のＳ１０にてｎ＝１に設定されているためで
ある。また、Ｓ１３０では、ｎをインクリメントして、
ｎ＝２とする。

【００８０】続くＳ１４０では、Ｌａｂｅｌ（１）の内
容を単語終了を示す「Ｗ」と比較するが、Ｌａｂｅｌ
（１）の内容は「ほ」であり「Ｗ」でないため、Ｓ１５
０へ移行し、Ｌａｂｅｌ（１）自体、すなわち「ほ」を
出力する。続くＳ１６０ではｑ＝Ｂｒｏｓ（ｑ）とする
が、Ｂｒｏｓ（１）は図７より１３であるため、ｑ＝１
３としてＳ１２０へ戻る。

【００８１】このＳ１６０の処理後に戻ったＳ１２０で
は、当然ｑ＝１３であり０でないため、Ｓ１３０へ移行
し、Ｎｕｍ（ｑ（＝１３））＝ｎ（＝２）に設定する。
前回のＳ１３０の処理でｎ＝２にインクリメントされて
いたので、Ｎｕｍ（１３）＝２となる。また、ｎをさら
にインクリメントして、ｎ＝３とする。

【００８２】続くＳ１４０では、Ｌａｂｅｌ（１３）の
内容を単語終了を示す「Ｗ」と比較するが、Ｌａｂｅｌ
（１３）の内容は「あ」であり「Ｗ」でないため、Ｓ１
５０へ移行し、Ｌａｂｅｌ（１３）自体、すなわち
「あ」を出力する。続くＳ１６０ではｑ＝Ｂｒｏｓ
（ｑ）とするが、Ｂｒｏｓ（１３）は図７より０である
ため、ｑ＝０としてＳ１２０へ戻る。

【００８３】このＳ１６０の処理後に戻ったＳ１２０で
は、ｑ＝０であるため、Ｓ１８０へ移行し、「＼」を出
力する。ここまでの処理によって、「ほ」と「あ」と
「＼」が出力され、図１４のＡ点の場合に示すように、
「ほ」に対応するＮｕｍ（１）＝１、「あ」に対応する
Ｎｕｍ（１３）＝２が設定される。また、この状態での
圧縮辞書データは、図１５にＡ点の場合を示したように
「「ほ，あ，＼」となる。

【００８４】次に、Ｂ点に至るまでの経過を順に見てみ
る。上述したＳ１８０へ移行して「＼」を出力する処理
の後、すなわちＳ１９０から説明する。Ｓ１９０では、
図１１の最初のステップＳ１１０と同様、変数ｑ＝ｐに
設定する。つまり、この場合はまだ圧縮（１）処理の途
中であるので、ｑ＝ｐ＝１となる。そして、続くＳ２０
０においてｑが０でないので、Ｓ２１０へ移行し、Ｌａ
ｂｅｌ（１）を「Ｗ」と比較する。Ｌａｂｅｌ（１）は
「ほ」で「Ｗ」ではないので、Ｓ２２０へ移行する。

【００８５】Ｓ２２０では、Ｎｕｍ（Ｃｈｉｌｄ
（１））が０より大きいかどうかを判断する。Ｃｈｉｌ
ｄ（１）は図７より「２」であるため、Ｎｕｍ（Ｃｈｉ
ｌｄ（１））＝Ｎｕｍ（２）であり、図１４のＡ点での
状態を示す場合から判るようにＮｕｍ（２）＝０であ
る。そのため、Ｓ２２０で否定判断となってＳ２３０へ
移行する。Ｓ２３０では、圧縮（Ｃｈｉｌｄ（１））処
理を行なう。Ｃｈｉｌｄ（１）＝２であるため、このＳ
２３０では圧縮（２）処理を、再帰読み出し処理として
行なうこととなる。

【００８６】圧縮（２）処理では、ｐ＝２であるので、
図１１のＳ１１０にてｑ＝ｐ＝２となり、Ｓ１２０で
は、ｑ＝２＞０であるため、Ｓ１３０へ移行する。Ｓ１
３０では、Ｎｕｍ（ｑ（＝２））＝ｎ（＝３）に設定す
る。また、Ｓ１３０では、ｎをさらにインクリメントし
て、ｎ＝４とする。

【００８７】続くＳ１４０では、Ｌａｂｅｌ（２）の内
容を単語終了を示す「Ｗ」と比較するが、図７から判る
ようにＬａｂｅｌ（２）の内容は「ん」であり、「Ｗ」
でないため、Ｓ１５０へ移行し、Ｌａｂｅｌ（２）の
「ん」を出力する。続くＳ１６０ではｑ＝Ｂｒｏｓ
（ｑ）とするが、Ｂｒｏｓ（２）は図７より８であるた
め、ｑ＝８としてＳ１２０へ戻る。

【００８８】このＳ１６０の処理後に戻ったＳ１２０で
は、当然ｑ＝８であり０でないため、Ｓ１３０へ移行
し、Ｎｕｍ（ｑ（＝８））＝ｎ（＝４）に設定する。前
回のＳ１３０の処理でｎ＝４にインクリメントされてい
たので、Ｎｕｍ（８）＝４となる。また、ｎをさらにイ
ンクリメントして、ｎ＝５とする。

【００８９】続くＳ１４０では、Ｌａｂｅｌ（８）の内
容を単語終了を示す「Ｗ」と比較するが、Ｌａｂｅｌ
（８）の内容は「み」であり「Ｗ」でないため、Ｓ１５
０へ移行し、Ｌａｂｅｌ（８）自体、すなわち「み」を
出力する。続くＳ１６０ではｑ＝Ｂｒｏｓ（ｑ）とする
が、Ｂｒｏｓ（８）は図７より０であるため、ｑ＝０と
してＳ１２０へ戻る。

【００９０】このＳ１６０の処理後に戻ったＳ１２０で
は、ｑ＝０であるため、Ｓ１８０へ移行し、「＼」を出
力する。圧縮（２）処理では、ここまでの処理によって
「ん」と「み」と「＼」が出力される。

【００９１】その後、上述した圧縮（１）処理中にてＳ
２３０の圧縮（２）処理に移行したように、圧縮（２）
処理中におけるＳ２３０では、圧縮（Ｃｈｉｌｄ
（２））処理を行なう。図７から判るようにＣｈｉｌｄ
（２）＝３であるため、このＳ２３０では圧縮（３）処
理を、再帰読み出し処理として行なうこととなる。

【００９２】圧縮（３）処理の詳細は省略するが、上述
した圧縮（２）処理と同様にして、「ま」と「ちょ」と
「＼」が出力される。そして、圧縮（３）処理中におけ
るＳ２３０では、圧縮（Ｃｈｉｌｄ（３））処理を行な
う。図７から判るようにＣｈｉｌｄ（３）＝４であるた
め、このＳ２３０では圧縮（４）処理を、再帰読み出し
処理として行なうこととなる。

【００９３】圧縮（４）処理では、図１１のＳ１５０に
てＬａｂｅｌ（４）の「ち」を出力する。続くＳ１６０
ではｑ＝Ｂｒｏｓ（ｑ）とするが、この場合Ｂｒｏｓ
（４）は図７より０であるため、ｑ＝０としてＳ１２０
へ戻り、Ｓ１８０へ移行して「＼」を出力することとな
る。したがって、「ち」と「＼」が出力されただけでＳ
１９０へ移行する。そして、Ｓ２００，Ｓ２１０，Ｓ２
２０と処理が進み、Ｓ２３０にて、圧縮（Ｃｈｉｌｄ
（４））処理を行なう。図７から判るようにＣｈｉｌｄ
（４）＝５であるため、このＳ２３０では圧縮（５）処
理を、再帰読み出し処理として行なうこととなる。

【００９４】圧縮（５）処理では、図１１のＳ１１０に
てｑ＝ｐ＝５となり、Ｓ１３０にてＮｕｍ（５）＝ｎ＝
８，ｎ＝８＋１＝９と設定する。そして、Ｓ１４０で
は、Ｌａｂｅｌ（５）の内容が単語終了を示す「Ｗ」で
あるため、Ｓ１７０へ移行する。そして、Ｓ１７０に
て、「Ｗ」を出力すると共にＣｈｉｌｄ（ｑ）を出力す
る。この場合、Ｃｈｉｌｄ（５）＝１となるため、この
１も出力する。

【００９５】そして、続くＳ１６０ではｑ＝Ｂｒｏｓ
（ｑ）とするが、Ｂｒｏｓ（５）は図７より０であるた
め、ｑ＝０としてＳ１２０へ戻り、ｑ＝０であるため、
Ｓ１８０へ移行し、「＼」を出力する。圧縮（５）処理
では、ここまでの処理によって「Ｗ」と「１」と「＼」
が出力される。

【００９６】Ｓ１８０の処理後に移行するＳ１９０で
は、ｑ＝ｐ＝５であり、Ｓ２００、Ｓ２１０と移行する
が、Ｓ２１０では、Ｌａｂｅｌ（５）が「Ｗ」であるの
で、そのままＳ２４０へ移行する。そして、Ｓ２４０で
ｑ＝Ｂｒｏｓ（ｑ）とするが、Ｂｒｏｓ（５）は図７よ
り０であるため、ｑ＝０としてＳ２００へ戻り、Ｓ２０
０にてｑ＝０であるため、圧縮（５）処理を終了する。

【００９７】この圧縮（５）処理は、上述した圧縮
（４）処理中のＳ２３０で実行される再帰読み出し処理
のため、圧縮（５）処理が終了すると、圧縮（４）処理
中のＳ２４０へ移行する。このＳ２４０ではｑ＝Ｂｒｏ
ｓ（ｑ）とするが、Ｂｒｏｓ（４）は図７より０である
ため、ｑ＝０としてＳ２００へ戻り、Ｓ２００にてｑ＝
０であるため、圧縮（４）処理を終了する。

【００９８】この圧縮（４）処理は、上述した圧縮
（３）処理中のＳ２３０で実行される再帰読み出し処理
のため、圧縮（４）処理が終了すると、圧縮（３）処理
中のＳ２４０へ移行する。このＳ２４０ではｑ＝Ｂｒｏ
ｓ（ｑ）とするが、Ｂｒｏｓ（３）は図７より６である
ため、ｑ＝６としてＳ２００へ戻る。Ｓ２００にてｑ＝
６であるためＳ２１０へ移行し、Ｌａｂｅｌ（６）は
「ちょ」で「Ｗ」ではないのでＳ２２０へ移行する。

【００９９】Ｓ２２０ではＮｕｍ（Ｃｈｉｌｄ（６））
が０より大きいかどうかを判断するが、Ｃｈｉｌｄ
（６）は図７より「７」である。この時点ではＮｕｍ
（Ｃｈｉｌｄ（６））＝Ｎｕｍ（７）は０であるため、
Ｓ２３０へ移行し、圧縮（Ｃｈｉｌｄ（６））処理、す
なわち圧縮（７）処理を再帰読み出し処理として行な
う。

【０１００】圧縮（７）処理では、図１１のＳ１３０に
てＮｕｍ（７）＝ｎ＝９，ｎ＝９＋１＝１０と設定す
る。そして、Ｓ１５０にてＬａｂｅｌ（７）の「う」を
出力する。続くＳ１６０ではｑ＝Ｂｒｏｓ（ｑ）とする
が、この場合Ｂｒｏｓ（７）は図７より０であるため、
ｑ＝０としてＳ１２０へ戻り、Ｓ１８０へ移行して
「＼」を出力することとなる。したがって、「う」と
「＼」が出力されただけでＳ１９０へ移行する。

【０１０１】そして、Ｓ１９０にてｑ＝７とし、Ｓ２０
０，Ｓ２１０と処理が進み、続くＳ２２０では、Ｎｕｍ
（Ｃｈｉｌｄ（７））が０より大きいかどうかを判断す
る。Ｃｈｉｌｄ（７）は図７より「５」であるが、Ｎｕ
ｍ（５）は圧縮（５）処理のＳ１３０にて「８」に設定
されているので、この場合のＳ２２０は肯定判断とな
り、Ｓ２５０へ移行する。

【０１０２】したがって、Ｓ２５０にて「Ｊ」を出力す
ると共に、Ｎｕｍ（Ｃｈｉｌｄ（７））＝Ｎｕｍ（５）
＝８を出力してから、Ｓ２４０へ移行する。これが、図
８の圧縮辞書データでいえば「Ｊ，８」の部分である。
Ｓ２４０ではｑ＝Ｂｒｏｓ（ｑ）とするが、Ｂｒｏｓ
（７）は図７より０であるため、ｑ＝０としてＳ２００
へ戻り、Ｓ２００にてｑ＝０であるため、圧縮（７）処
理を終了する。

【０１０３】この圧縮（７）処理は、上述した圧縮
（３）処理中のＳ２３０で実行される再帰読み出し処理
のため、圧縮（７）処理が終了すると、圧縮（３）処理
中のＳ２４０へ移行する。この際、Ｓ２３０での圧縮
（７）が圧縮（Ｃｈｉｌｄ（６））であることを考える
と、この場合のｑは６である。Ｓ２４０ではｑ＝Ｂｒｏ
ｓ（ｑ）とするが、Ｂｒｏｓ（６）は図７より０である
ため、ｑ＝０としてＳ２００へ戻り、Ｓ２００にてｑ＝
０であるため、本圧縮（３）処理が終了する。

【０１０４】そして、この圧縮（３）処理は、上述した
圧縮（２）処理中のＳ２３０で実行される再帰読み出し
処理のため、圧縮（３）処理が終了すると、圧縮（２）
処理中のＳ２４０へ移行する。この際、Ｓ２３０での圧
縮（３）処理が圧縮（Ｃｈｉｌｄ（２））処理であるこ
とを考えると、Ｓ２４０ではｑ＝Ｂｒｏｓ（２）とする
が、Ｂｒｏｓ（２）は図７より８であるため、ｑ＝８と
してＳ２００へ戻り、Ｓ２００にてｑ＝８であるため、
Ｓ２１０へ移行する。Ｓ２１０の処理では、Ｌａｂｅｌ
（８）は「み」で「Ｗ」ではないのでＳ２２０へ移行す
る。

【０１０５】Ｓ２２０では、Ｎｕｍ（ＣｈｉｌｄＮ
（８））が０より大きいかどうかを判断する。Ｃｈｉｌ
ｄ（８）は図７より「９」であるが、Ｎｕｍ（９）は０
であるため、Ｓ２３０へ移行し、圧縮（Ｃｈｉｌｄ
（８））処理を行なう。Ｃｈｉｌｄ（８）＝９であるた
め、このＳ２３０では圧縮（９）処理を、再帰読み出し
処理として行なうこととなる。

【０１０６】圧縮（９）処理では、図１１のＳ１１０に
てｑ＝ｐ＝９となり、Ｓ１３０にてＮｕｍ（９）＝ｎ＝
１０，ｎ＝１０＋１＝１１と設定する。そして、Ｓ１４
０では、Ｌａｂｅｌ（９）の内容が単語終了を示す
「Ｗ」であるため、Ｓ１７０へ移行する。そして、Ｓ１
７０にて、「Ｗ」を出力すると共にＣｈｉｌｄ（ｑ）を
出力する。この場合、Ｃｈｉｌｄ（９）＝２となるた
め、この２も出力する。

【０１０７】そして、続くＳ１６０ではｑ＝Ｂｒｏｓ
（ｑ）とするが、Ｂｒｏｓ（９）は図７より１０である
ため、ｑ＝１０としてＳ１２０へ戻る。このＳ１６０の
処理後に戻ったＳ１２０では、当然ｑ＝１０であり０で
ないため、Ｓ１３０へ移行し、Ｎｕｍ（１０））＝ｎ＝
１１、ｎ＝１１＋１＝１２と設定する。続くＳ１４０で
は、Ｌａｂｅｌ（１０）の内容を単語終了を示す「Ｗ」
と比較するが、Ｌａｂｅｌ（１０）の内容は「み」であ
り「Ｗ」でないため、Ｓ１５０へ移行し、Ｌａｂｅｌ
（１０）自体、すなわち「き」を出力する。

【０１０８】続くＳ１６０ではｑ＝Ｂｒｏｓ（ｑ）とす
るが、Ｂｒｏｓ（１０）は図７より０であるため、ｑ＝
０としてＳ１２０へ戻る。このＳ１６０の処理後に戻っ
たＳ１２０では、ｑ＝０であるため、Ｓ１８０へ移行
し、「＼」を出力する。

【０１０９】圧縮（９）処理では、ここまでの処理によ
って「Ｗ」と「２」と「き」と「＼」が出力される。Ｓ
１８０の処理後に移行するＳ１９０では、ｑ＝ｐ＝９で
あり、Ｓ２００、Ｓ２１０と移行するが、Ｓ２１０で
は、Ｌａｂｅｌ（９）が「Ｗ」であるので、そのままＳ
２４０へ移行する。そして、Ｓ２４０でｑ＝Ｂｒｏｓ
（ｑ）とするが、Ｂｒｏｓ（９）は図７より１０である
ため、ｑ＝１０としてＳ２００へ戻る。続くＳ２１０で
は、Ｌａｂｅｌ（１０）が「き」であり「Ｗ」ではない
ので、Ｓ２２０へ移行する。

【０１１０】Ｓ２２０ではＮｕｍ（Ｃｈｉｌｄ（１
０））が０より大きいかどうかを判断するが、Ｃｈｉｌ
ｄ（１０）は図７より「１１」である。この時点ではＮ
ｕｍ（Ｃｈｉｌｄ（１０））＝Ｎｕｍ（１１）は０であ
るため、Ｓ２３０へ移行し、圧縮（Ｃｈｉｌｄ（１
０））処理、すなわち圧縮（１１）処理を再帰読み出し
処理として行なう。

【０１１１】圧縮（１１）処理では、図１１のＳ１１０
にてｑ＝ｐ＝１１となり、Ｓ１３０にてＮｕｍ（１１）
＝ｎ＝１２，ｎ＝１２＋１＝１３と設定する。そして、
Ｓ１４０では、Ｌａｂｅｌ（１１）の内容が「た」であ
り「Ｗ」ではないので、Ｓ１５０へ移行し、Ｌａｂｅｌ
（１１）自体、すなわち「た」を出力する。

【０１１２】続くＳ１６０ではｑ＝Ｂｒｏｓ（ｑ）とす
るが、Ｂｒｏｓ（１１）は図７より１２であるため、ｑ
＝１２としてＳ１２０へ戻る。ｑ＝１２は０でないので
Ｓ１３０へ移行し、Ｓ１３０にてＮｕｍ（１２）＝ｎ＝
１３，ｎ＝１３＋１＝１４と設定する。

【０１１３】そして、Ｓ１４０では、Ｌａｂｅｌ（１
２）の内容が単語終了を示す「Ｗ」であるため、Ｓ１７
０へ移行する。そして、Ｓ１７０にて、「Ｗ」を出力す
ると共にＣｈｉｌｄ（ｑ）を出力する。この場合、Ｃｈ
ｉｌｄ（１２）＝３となるため、この３も出力する。

【０１１４】そして、続くＳ１６０ではｑ＝Ｂｒｏｓ
（ｑ）とするが、Ｂｒｏｓ（１２）は図７より０である
ため、ｑ＝０としてＳ１２０へ戻る。このＳ１６０の処
理後に戻ったＳ１２０では、ｑ＝０であるためＳ１８０
へ移行する。そして、Ｓ１８０にて「＼」を出力する。
したがって、「た」と「＼」が出力されただけでＳ１９
０へ移行する。

【０１１５】Ｓ１９０では再度ｑ＝ｐ＝１１とし、ｑは
０でないためＳ２１０へ移行する。Ｓ２１０では、Ｌａ
ｂｅｌ（１１）が「た」で「Ｗ」ではないためＳ２２０
へ移行する。Ｓ２２０では、Ｎｕｍ（Ｃｈｉｌｄ（１
１））が０より大きいかどうかを判断する。Ｃｈｉｌｄ
（１１）は図７より「１２」であるが、この時点でＮｕ
ｍ（１２）はまだ「０」であるので、Ｓ２３０へ移行
し、圧縮（Ｃｈｉｌｄ（１１））処理、すなわち圧縮
（１２）処理を再帰読み出し処理として行なう。

【０１１６】圧縮（１２）処理では、図１１のＳ１３０
にてＮｕｍ（１２）＝ｎ＝１３，ｎ＝１３＋１＝１４と
設定する。そして、Ｓ１４０では、Ｌａｂｅｌ（１２）
の内容が単語終了を示す「Ｗ」であるため、Ｓ１７０へ
移行する。そして、Ｓ１７０にて、「Ｗ」を出力すると
共にＣｈｉｌｄ（ｑ）を出力する。この場合、Ｃｈｉｌ
ｄ（１２）＝３となるため、この３も出力する。

【０１１７】そして、続くＳ１６０ではｑ＝Ｂｒｏｓ
（ｑ）とするが、Ｂｒｏｓ（１２）は図７より０である
ため、ｑ＝０としてＳ１２０へ戻り、ｑ＝０であるた
め、Ｓ１８０へ移行し、「＼」を出力する。ここまでの
処理によって「Ｗ」と「３」と「＼」が出力される。

【０１１８】そして、Ｓ１９０にてｑ＝ｐ＝１２とし、
Ｓ２００、Ｓ２１０と移行するが、Ｓ２１０では、Ｌａ
ｂｅｌ（１２）が「Ｗ」であるので、そのままＳ２４０
へ移行する。そして、Ｓ２４０でｑ＝Ｂｒｏｓ（ｑ）と
するが、Ｂｒｏｓ（１２）は図７より０であるため、ｑ
＝０としてＳ２００へ戻り、Ｓ２００にてｑ＝０である
ため、圧縮（１２）処理を終了する。

【０１１９】この圧縮（１２）処理は、上述した圧縮
（１１）処理中のＳ２３０で実行される再帰読み出し処
理のため、圧縮（１２）処理が終了すると、圧縮（１
１）処理中のＳ２４０へ移行する。このＳ２４０ではｑ
＝Ｂｒｏｓ（ｑ）とするが、Ｂｒｏｓ（１１）は図７よ
り０であるため、ｑ＝０としてＳ２００へ戻り、Ｓ２０
０にてｑ＝０であるため、圧縮（１１）処理を終了す
る。

【０１２０】また、この圧縮（１１）処理は、上述した
圧縮（９）処理中のＳ２３０で実行される再帰読み出し
処理のため、圧縮（１１）処理が終了すると圧縮（９）
処理中のＳ２４０へ移行する。この際、Ｓ２３０での圧
縮（１１）が圧縮（Ｃｈｉｌｄ（１０））であることを
考えると、Ｓ２４０ではｑ＝Ｂｒｏｓ（１０）とする
が、Ｂｒｏｓ（１０）は図７より０であるため、ｑ＝０
としてＳ２００へ戻り、Ｓ２００にてｑ＝０であるた
め、圧縮（９）処理を終了する。

【０１２１】この圧縮（９）処理は、上述した圧縮
（２）処理中のＳ２３０で実行される再帰読み出し処理
のため、圧縮（９）処理が終了すると、圧縮（２）処理
中のＳ２４０へ移行する。この際、Ｓ２３０での圧縮
（９）処理が圧縮（Ｃｈｉｌｄ（８））であることを考
えると、Ｓ２４０ではｑ＝Ｂｒｏｓ（８）とするが、Ｂ
ｒｏｓ（８）は図７より０であるため、ｑ＝０としてＳ
２００へ戻り、Ｓ２００にてｑ＝０であるため、圧縮
（２）処理を終了する。

【０１２２】以上説明した圧縮（２）処理までが終了す
ることによって、図７に示す「ほ，ん，ま，ち，Ｗ，ち
ょ，う，み，Ｗ，き，た，あ」までの番号１〜１３の各
ラベルに対するＮｕｍ（ｉ）が、図１４のＢ点の場合に
示すように、「１，３，５，７，８，６，９，４，１
０，１１，１２，１３，２」と設定される。そして、こ
の順番に各ラベルを並び替えると共に、単語終了を示す
「Ｗ」と単語番号、さらには合流を示す「Ｊ」とその合
流先のラベル番号を加えると、この時点での圧縮辞書デ
ータは、図１５のＢ点の場合に示すように、「ん，み，
＼，ま，ちょ，＼，ち，＼，Ｗ，１，＼，う＼，Ｊ，
８，Ｗ，２，き，＼，た，＼，Ｗ，３，＼」となる。

【０１２３】次に、Ｃ点に至るまでの経過を順に見てみ
る。上述した圧縮（２）処理が終了した後から説明す
る。この圧縮（２）処理は、上述した圧縮（１）処理中
のＳ２３０で実行される再帰読み出し処理のため、圧縮
（２）処理が終了すると、圧縮（１）処理中のＳ２４０
へ移行する。このＳ２４０ではｑ＝Ｂｒｏｓ（ｑ）とす
るが、Ｂｒｏｓ（１）は図７より１３であるため、ｑ＝
１３としてＳ２００へ戻る。Ｓ２００にてｑ＝１３であ
るためＳ２１０へ移行し、Ｌａｂｅｌ（１３）は「あ」
で「Ｗ」ではないのでＳ２２０へ移行する。

【０１２４】Ｓ２２０ではＮｕｍ（Ｃｈｉｌｄ（１
３））が０より大きいかどうかを判断するが、Ｃｈｉｌ
ｄ（１３）は図７より「１４」である。この時点ではＮ
ｕｍ（Ｃｈｉｌｄ（１３））＝Ｎｕｍ（１４）は０であ
るため、Ｓ２３０へ移行し、圧縮（Ｃｈｉｌｄ（１
３））処理、すなわち圧縮（１４）処理を再帰読み出し
処理として行なう。

【０１２５】圧縮（１４）処理では、図１１のＳ１１０
にてｑ＝ｐ＝１４と設定し、Ｓ１３０にてＮｕｍ（１
４）＝ｎ＝１４，ｎ＝１４＋１＝１５と設定する。続く
Ｓ１４０では、Ｌａｂｅｌ（１４）の内容が「い」であ
り単語終了を示す「Ｗ」ではないため、Ｓ１５０にてＬ
ａｂｅｌ（１４）の「い」を出力する。続くＳ１６０で
はｑ＝Ｂｒｏｓ（ｑ）とするが、この場合Ｂｒｏｓ（１
４）は図７より０であるため、ｑ＝０としてＳ１２０へ
戻り、ｑ＝０であるため、Ｓ１８０へ移行し、「＼」を
出力する。

【０１２６】したがって、「い」と「＼」が出力された
だけでＳ１９０へ移行する。Ｓ１９０では再度ｑ＝ｐ＝
１４とし、ｑは０でないためＳ２１０へ移行する。Ｓ２
１０では、Ｌａｂｅｌ（１４）が「い」で「Ｗ」ではな
いためＳ２２０へ移行する。Ｓ２２０では、Ｎｕｍ（Ｃ
ｈｉｌｄ（１４））が０より大きいかどうかを判断す
る。Ｃｈｉｌｄ（１４）は図７より「１５」であるが、
この時点でＮｕｍ（１５）はまだ「０」であるので、Ｓ
２３０へ移行し、圧縮（Ｃｈｉｌｄ（１４））処理、す
なわち圧縮（１５）処理を再帰読み出し処理として行な
う。

【０１２７】圧縮（１５）処理では、図１１のＳ１１０
にてｑ＝ｐ＝１５とし、Ｓ１３０にてＮｕｍ（１５）＝
ｎ＝１５，ｎ＝１５＋１＝１６と設定する。そして、Ｓ
１４０では、Ｌａｂｅｌ（１５）の内容が「お」であり
単語終了を示す「Ｗ」ではないため、Ｓ１５０にてＬａ
ｂｅｌ（１５）の「お」を出力する。続くＳ１６０では
ｑ＝Ｂｒｏｓ（ｑ）とするが、この場合Ｂｒｏｓ（１
５）は図７より０であるため、ｑ＝０としてＳ１２０へ
戻り、ｑ＝０であるため、Ｓ１８０へ移行して、「＼」
を出力する。

【０１２８】したがって、「お」と「＼」が出力された
だけでＳ１９０へ移行する。Ｓ１９０では再度ｑ＝ｐ＝
１５とし、ｑは０でないためＳ２１０へ移行する。Ｓ２
１０では、Ｌａｂｅｌ（１５）が「お」で「Ｗ」ではな
いためＳ２２０へ移行する。Ｓ２２０では、Ｎｕｍ（Ｃ
ｈｉｌｄ（１５））が０より大きいかどうかを判断す
る。Ｃｈｉｌｄ（１５）は図７より「１６」であるが、
この時点でＮｕｍ（１６）はまだ「０」であるので、Ｓ
２３０へ移行し、圧縮（Ｃｈｉｌｄ（１５））処理、す
なわち圧縮（１６）処理を再帰読み出し処理として行な
う。

【０１２９】圧縮（１６）処理では、図１１のＳ１１０
にてｑ＝ｐ＝１６とし、Ｓ１３０にてＮｕｍ（１６）＝
ｎ＝１６，ｎ＝１５＋１＝１７と設定する。そして、Ｓ
１４０では、Ｌａｂｅｌ（１６）の内容が「い」であり
単語終了を示す「Ｗ」ではないため、Ｓ１５０にてＬａ
ｂｅｌ（１６）の「い」を出力する。続くＳ１６０では
ｑ＝Ｂｒｏｓ（ｑ）とするが、この場合Ｂｒｏｓ（１
６）は図７より０であるため、ｑ＝０としてＳ１２０へ
戻り、ｑ＝０であるため、Ｓ１８０へ移行して、「＼」
を出力する。したがって、「い」と「＼」が出力された
だけでＳ１９０へ移行する。

【０１３０】Ｓ１９０では再度ｑ＝ｐ＝１６とし、ｑは
０でないためＳ２１０へ移行する。Ｓ２１０では、Ｌａ
ｂｅｌ（１６）が「い」で「Ｗ」ではないためＳ２２０
へ移行する。Ｓ２２０では、Ｎｕｍ（Ｃｈｉｌｄ（１
６））が０より大きいかどうかを判断する。Ｃｈｉｌｄ
（１６）は図７より「１７」であるが、この時点でＮｕ
ｍ（１７）はまだ「０」であるので、Ｓ２３０へ移行
し、圧縮（Ｃｈｉｌｄ（１６））処理、すなわち圧縮
（１７）処理を再帰読み出し処理として行なう。

【０１３１】圧縮（１７）処理では、図１１のＳ１１０
にてｑ＝ｐ＝１７とし、Ｓ１３０にてＮｕｍ（１６）＝
ｎ＝１７，ｎ＝１５＋１＝１８と設定する。そして、Ｓ
１４０では、Ｌａｂｅｌ（１７）の内容が単語終了を示
す「Ｗ」であるため、Ｓ１７０へ移行し、「Ｗ」を出力
すると共に、Ｃｈｉｌｄ（１７）＝４を出力する。続く
Ｓ１６０ではｑ＝Ｂｒｏｓ（ｑ）とするが、この場合Ｂ
ｒｏｓ（１７）は図７より０であるため、ｑ＝０として
Ｓ１２０へ戻り、ｑ＝０であるため、Ｓ１８０へ移行し
て、「＼」を出力する。

【０１３２】したがって、「Ｗ」と「４」と「＼」が出
力されてＳ１９０へ移行する。Ｓ１９０では再度ｑ＝ｐ
＝１７とし、ｑは０でないためＳ２１０へ移行する。Ｓ
２１０では、Ｌａｂｅｌ（１７）が「Ｗ」であるためＳ
２４０へ移行する。Ｓ２４０では、ｑ＝Ｂｒｏｓ（ｑ）
とするが、Ｂｒｏｓ（１７）は図７より０であるため、
ｑ＝０としてＳ２００へ戻り、Ｓ２００にてｑ＝０であ
るため、圧縮（１７）処理を終了する。

【０１３３】この圧縮（１７）処理は、上述した圧縮
（１６）処理中のＳ２３０で実行される再帰読み出し処
理のため、圧縮（１７）処理が終了すると、圧縮（１
６）処理中のＳ２４０へ移行する。このＳ２４０ではｑ
＝Ｂｒｏｓ（ｑ）とするが、Ｂｒｏｓ（１６）は図７よ
り０であるため、ｑ＝０としてＳ２００へ戻り、Ｓ２０
０にてｑ＝０であるため、圧縮（１６）処理を終了す
る。

【０１３４】また、圧縮（１６）処理は、上述した圧縮
（１５）処理中のＳ２３０で実行される再帰読み出し処
理のため、圧縮（１６）処理が終了すると、圧縮（１
５）処理中のＳ２４０へ移行する。このＳ２４０ではｑ
＝Ｂｒｏｓ（ｑ）とするが、Ｂｒｏｓ（１５）は図７よ
り０であるため、ｑ＝０としてＳ２００へ戻り、Ｓ２０
０にてｑ＝０であるため、圧縮（１５）処理を終了す
る。

【０１３５】同様に、圧縮（１５）処理は、上述した圧
縮（１４）処理中のＳ２３０で実行される再帰読み出し
処理のため、圧縮（１５）処理が終了すると、圧縮（１
４）処理中のＳ２４０へ移行する。このＳ２４０ではｑ
＝Ｂｒｏｓ（ｑ）とするが、Ｂｒｏｓ（１４）は図７よ
り０であるため、ｑ＝０としてＳ２００へ戻り、Ｓ２０
０にてｑ＝０であるため、圧縮（１４）処理を終了す
る。

【０１３６】そして、この圧縮（１４）処理は、上述し
た圧縮（１）処理中のＳ２３０で実行される再帰読み出
し処理のため、圧縮（１４）処理が終了すると、圧縮
（１）処理中のＳ２４０へ移行する。この際、Ｓ２３０
での圧縮（１４）処理が圧縮（Ｃｈｉｌｄ（１３））で
あることを考えると、Ｓ２４０ではｑ＝Ｂｒｏｓ（１
３）とするが、Ｂｒｏｓ（１３）は図７より０であるた
め、ｑ＝０としてＳ２００へ戻り、Ｓ２００にてｑ＝０
であるため、圧縮（１）処理を終了する。

【０１３７】以上説明した圧縮（１４）処理が終了する
ことによって圧縮（１）処理が全て終了し、図７に示す
「ほ，ん，ま，ち，Ｗ，ちょ，う，み，Ｗ，き，た，
あ，い，お，い，Ｗ」という番号１〜１７の各ラベルに
対するＮｕｍ（ｉ）が、図１４のＣ点の場合に示すよう
に、「１，３，５，７，８，６，９，４，１０，１１，
１２，１３，２，１４，１５，１６，１７」と設定され
る。そして、この順番に各ラベルを並び替えると共に、
単語終了を示す「Ｗ」と単語番号、さらには合流を示す
「Ｊ」とその合流先のラベル番号を加えると、最終的な
圧縮辞書データとして、図１５のＣ点の場合に示すよう
に、「ん，み，＼，ま，ちょ，＼，ち，＼，Ｗ，１，
＼，う＼，Ｊ，８，Ｗ，２，き，＼，た，＼，Ｗ，３，
＼い，＼，お，＼，い，＼，Ｗ，４，＼」となる。

【０１３８】以上は、グラフ辞書データを圧縮辞書デー
タに変換する際の具体的な処理について説明したが、上
述したように、このように圧縮辞書データに変換された
後、本実施形態の場合にはデータ圧縮を施し、そのデー
タ圧縮された「圧縮辞書データ」を、地図データ及びそ
の他のデータと共にナビゲーションシステム用の地図Ｃ
Ｄに書き込む。そして、この地図ＣＤ内のデータが地図
データ入力器６（図１参照）を介して制御回路１０に読
み込まれ、上述したように音声認識装置３０に転送され
るのである。

【０１３９】そして、音声認識装置３０の対話制御部３
２における辞書制御部３２ｃは、この転送された圧縮辞
書データをデータ展開し、さらに辞書展開してから音声
認識部３１の辞書部３１ｂへ書き込む。圧縮時には圧縮
辞書データに対して例えば可変長符号化といった一般的
なデータ圧縮を施すこととしているので、データ展開は
その圧縮方法に対応した伸長方法を採用すればよいの
で、詳しい説明は省略する。

【０１４０】一方、辞書展開も、圧縮時における第２の
変換処理に対応した展開方法となるのであるが、この辞
書展開方法を説明的に記述すると、「圧縮辞書データ中
の音節及び単語終了を示す識別データが第２の走査順に
したがって並び替えられていると共に、頂点に兄弟が存
在する場合にはその兄弟関係を他と区別するための識別
データが存在することに基づき、その圧縮辞書データ中
の音節及び単語終了を示す識別データに加え、当該音節
及び単語終了を示す識別データ毎に自分の子を識別する
ためのデータを設定して第２のグラフ辞書データに展開
する」方法となる。

【０１４１】これは、上述した単語辞書データの圧縮方
法での第２の変換処理における変換過程を考慮して、逆
に、圧縮辞書データ中の音節及び単語終了を示す識別デ
ータ毎に、自分の子を識別するためのデータを復活させ
るのである。つまり、圧縮辞書データ中の音節（上述例
では各ラベルが相当する。）及び単語終了を示す識別デ
ータ（上述例では「＼」が相当する。）は、第２の走査
順にしたがって並び替えられていると共に、頂点に兄弟
が存在する場合にはその兄弟関係を他と区別するための
識別データが設定されているため、その点を考慮すれ
ば、図５〜図７に示した木構造類似の有向グラフの頂点
の親子関係から自分の子は容易に解析できるのである。

【０１４２】具体例を参照する方が理解が容易になるの
で、図５〜図７に示すテキスト辞書データが第２の変換
処理によって変換された結果として第２のグラフ辞書デ
ータの具体例を図９に示す。図９からも判るように、
「ほ，あ，う，み，……」という各ラベル（Ｌａｂｅ
ｌ）に対して、自分の子（Ｃｈｉｌｄ）を識別するため
のデータがラベル番号で設定されている。また、兄弟が
存在する場合にはその兄弟関係を他と区別するための識
別データがＬａｓｔの項目に「１」として設定されてい
る。

【０１４３】なお、この図９からも判るように、第２の
グラフ辞書データは、上述した圧縮方法での第１の変換
処理によって得たグラフ辞書データ（図７参照）の状態
と必ずしも同じではない。上述の図７のグラフ辞書デー
タでは、各ラベル毎に自分の子及び兄弟を識別するため
のデータを持たせていたが、本展開処理において得た図
９の第２のグラフ辞書データでは、自分の兄弟を識別す
るためのデータを各ラベル毎に持たせなくてはならない
ことはない。

【０１４４】いずれにしても、各ラベルのデータに加え
て、当該データ毎に自分の子を識別するためのデータ
と、兄弟関係を他と区別するための識別データを最低限
持つことができるため、この第２の辞書データは単語辞
書として十分用いることができる。

【０１４５】続いて、図８に示す圧縮辞書データを図９
に示す第２のグラフ辞書データに展開する際の具体的な
処理について説明する。図１６に示すように、処理が開
始すると、最初のステップＳ１０１０において変数ｎを
初期値１に設定し、続くＳ１０２０では展開処理を実行
する。

【０１４６】この展開処理の詳細を図１７，１８を参照
して説明する。図１７の最初のステップＳ１１１０では
変数ｔ＝ｎに設定する。つまり、最初は初期値ｎ＝１と
なる。そして、続くＳ１１２０においてｘ＝次の入力デ
ータとし、Ｓ１１３０ではそれが「Ｊ」であるかどうか
を判断する。

【０１４７】Ｓ１１３０にて入力データｘが「Ｊ」であ
ると判断された場合には、Ｓ１１８０へ移行し、ｘ＝次
の入力データとしてから、Ｓ１１９０にて、そのｘを戻
り値として本処理をリターンする。一方、入力データｘ
が「Ｊ」でなければＳ１１４０に移行し、Ｓ１１４０に
て「＼」であるかどうかを判断する。入力データｘが
「＼」であると判断された場合には、Ｓ１２１０へ移行
し、Ｌａｓｔ（ｎ−１）を１に設定してから、図１８０
のＳ１２２０へ移行する。なお、Ｓ１２２０以降の処理
は後述する。

【０１４８】入力データｘが「＼」でないと判断された
場合には、Ｓ１１５０へ移行し、「Ｗ」であるかどうか
を判断する。入力データｘが「Ｗ」であると判断された
場合には、Ｓ１２００へ移行し、Ｌａｂｅｌ（ｎ）を
「Ｗ」に設定し、さらにＣｈｉｌｄ（ｎ）を次の入力デ
ータに設定してから、Ｓ１１７０へ移行する。

【０１４９】一方、入力データｘが「Ｗ」でないと判断
された場合には、Ｓ１１６０へ移行し、Ｌａｂｅｌ
（ｎ）＝ｘ、すなわちＳ１１２０にてｘとして設定した
次の入力データとし、さらにＣｈｉｌｄ（ｎ）＝０とし
てから、Ｓ１１７０へ移行する。Ｓ１１７０では、Ｌａ
ｓｔ（ｎ）を０に設定し、さらにｎをインクリメント
（ｎ＝ｎ＋１）してから、Ｓ１１２０へ戻る。

【０１５０】続いて図１８のＳ１２２０以降の処理を説
明する。Ｓ１２２０では変数ｋ＝ｔとし、続くＳ１２３
０ではＣｈｉｌｄ（ｋ）を０と比較する。Ｃｈｉｌｄ
（ｋ）が０でなければそのままＳ１２５０へ移行する
が、Ｃｈｉｌｄ（ｋ）＝０であればＳ１２４０の処理を
実行してからＳ１２５０へ移行する。なお、Ｓ１２４０
の処理は、図１７，図１８の展開処理を再帰読み出し処
理として実行すると共に、その処理がリターンされた場
合の戻り値をＣｈｉｌｄ（ｋ）にセットする処理であ
る。

【０１５１】Ｓ１２５０では、Ｌａｓｔ（ｋ）を１と比
較し、Ｌａｓｔ（（ｋ）が１でなければＳ１２６０にて
ｋをインクリメント（ｋ＝ｋ＋１）としてＳ１２３０へ
戻るが、Ｌａｓｔ（ｋ）＝１であれば、Ｓ１２４０にて
ｔを戻り値として本処理をリターンする。

【０１５２】以上が展開処理を示すフローチャートの説
明であるが、より理解を容易にするために、図８に示す
圧縮辞書データを図９に示す第２のグラフ辞書データに
展開する際の途中経過を示しながら、さらに説明する。
図１９は、図１６のＳ１０２０での展開処理の内容を概
念的に示したものである。つまり、展開処理は、処理が
実行されていく途中で、図１８のＳ１２４０に示す展開
処理が再帰読み出し処理として実行される。

【０１５３】図１９におけるＡ点はＳ１２４０での再帰
読み出しによる展開処理が実行される前の時点を示し、
同じくＢ点はＳ１２４０での再帰読み出しによる展開処
理がＳ１２７０においてリターンした時点を示し、Ｃ点
は展開処理が最後まで終了した時点を示す。図２０はＡ
点での状態（途中経過）、図２１はＢ点での状態、図２
２はＣ点での状態を示している。

【０１５４】また、図２３には、上述のＡ点、Ｂ点、Ｃ
点における未入力データを示す。まず、Ａ点に至るまで
の経過を順に見てみる。図１７のＳ１１１０ではｔ＝ｎ
＝１とし、Ｓ１１２０にて、ｘとして最初の入力データ
「ほ」をセットする。「Ｊ」でも、「＼」でも、「Ｗ」
でもないため、Ｓ１１６０にてＬａｂｅｌ（１）＝
「ほ」とし、さらにＣｈｉｌｄ（１）＝０とする。さら
に、Ｓ１１７０にてＬａｓｔ（１）を０とする。

【０１５５】このＳ１１７０にてｎ＝１＋１＝２とされ
るので、Ｓ１１２０へ戻ってｘにセットされる２番目の
入力データ「あ」については、Ｓ１１６０にてＬａｂｅ
ｌ（２）＝「あ」とし、さらにＣｈｉｌｄ（２）＝０と
する。さらに、Ｓ１１７０にてＬａｓｔ（２）を０とす
る。

【０１５６】そして、このＳ１１７０にてにｎ＝２＋１
＝３とされるので、Ｓ１１２０へ戻ってｘにセットされ
る３番目の入力データ「＼」については、Ｓ１１４０の
判断にてＳ１２１０に移行する。そして、Ｓ１２１０に
てＬａｓｔ（ｎ−１）＝１、つまりｎ＝３であるので、
Ｌａｓｔ（２）を１とする。

【０１５７】ここまでの処理によって、図２０に示すよ
うに、ラベル「ほ」についてはＬａｓｔが「０」でＣｈ
ｉｌｄも「０」、ラベル「あ」についてはＬａｓｔが
「１」でＣｈｉｌｄが「０」となる。次に、Ｂ点に至る
までの経過を順に見てみる。

【０１５８】上述したＳ１２１０の処理後は、図１８の
Ｓ１２２０に移行する。Ｓ１２２０では変数ｋ＝ｔ＝１
とし、続くＳ１２３０ではＣｈｉｌｄ（１）を０と比較
する。この時点では図２０に示すように、Ｃｈｉｌｄ
（１）＝０であるため、Ｓ１２４０へ移行して、図１
７，図１８の展開処理を再帰読み出し処理として実行す
る。

【０１５９】再帰読み出し処理としての図１７の最初の
ステップＳ１１１０では、ｔ＝ｎ＝３とする。これは、
上述の展開処理中に実行した２回目のＳ１１７０におい
てｎ＝３とインクリメントしたからである。Ｓ１１２０
では、ｘとして次の入力データをセットする。これは、
図２３におけるＡ点での未入力データの最初のデータで
あり、図８の圧縮グラフ辞書データでいえば４番目のデ
ータにあたる「ん」をセットする。

【０１６０】この「ん」は、「Ｊ」でも、「＼」でも、
「Ｗ」でもないため、Ｓ１１６０にてＬａｂｅｌ（３）
＝「ほ」とし、さらにＣｈｉｌｄ（３）＝０とする。さ
らに、Ｓ１１７０にてＬａｓｔ（３）を０とする。この
Ｓ１１７０にてにｎ＝３＋１＝４とされるので、Ｓ１１
２０へ戻ってｘにセットされる次の入力データ「み」に
ついては、Ｓ１１６０にてＬａｂｅｌ（４）＝「み」と
し、さらにＣｈｉｌｄ（４）＝０とする。さらに、Ｓ１
１７０にてＬａｓｔ（４）を０とする。このＳ１１７０
にてｎ＝４＋１＝５とされる。

【０１６１】Ｓ１１７０後にはＳ１１２０へ戻り、次の
入力データ「＼」をｘにセットする。この入力データ
「＼」については、Ｓ１１４０の判断にてＳ１２１０に
移行する。そして、Ｓ１２１０にてＬａｓｔ（ｎ−１）
＝１、つまりｎ＝５であるので、Ｌａｓｔ（４）を１と
する。

【０１６２】ここまでの処理によって、３番目のラベル
「ん」についてはＬａｓｔが「０」でＣｈｉｌｄも
「０」、４番目のラベル「み」についてはＬａｓｔが
「１」でＣｈｉｌｄが「０」となる。続くＳ１２２０で
は変数ｋ＝ｔ＝３とし、Ｓ１２３０ではＣｈｉｌｄ
（３）を０と比較する。この時点では、Ｃｈｉｌｄ
（３）＝０であるため、Ｓ１２４０へ移行して、図１
７，図１８の展開処理を再帰読み出し処理として実行す
る。

【０１６３】再帰読み出し処理としての図１７の最初の
ステップＳ１１１０では、ｔ＝ｎ＝５とする。上述した
「ん，み，＼」の３つの入力データに対する処理と同様
に、それに続く「ま，ちょ，＼」の３つの入力データに
対する再帰読み出しによる展開処理がなされることによ
って、５番目のラベル「ま」についてはＬａｓｔが
「０」でＣｈｉｌｄも「０」、６番目のラベル「ちょ」
についてはＬａｓｔが「１」でＣｈｉｌｄが「０」とな
る。

【０１６４】続くＳ１２２０では変数ｋ＝ｔ＝５とし、
Ｓ１２３０ではＣｈｉｌｄ（５）を０と比較する。この
時点では、Ｃｈｉｌｄ（５）＝０であるため、Ｓ１２４
０へ移行して、図１７，図１８の展開処理を再帰読み出
し処理として実行する。再帰読み出し処理としての図１
７の最初のステップＳ１１１０では、ｔ＝ｎ＝７とす
る。上述した処理と同様に、「ま，ちょ，＼」に続く
「ち，＼」の２つの入力データに対する再帰読み出しに
よる展開処理では、７番目のラベル「ち」についてはＬ
ａｓｔが「１」でＣｈｉｌｄが「０」となる。

【０１６５】そして、上記同様にＳ１２１０後に移行す
るＳ１２２０では変数ｋ＝ｔ＝７とし、Ｓ１２３０では
Ｃｈｉｌｄ（７）を０と比較する。この時点では、Ｃｈ
ｉｌｄ（７）＝０であるため、Ｓ１２４０へ移行して、
図１７，図１８の展開処理を再帰読み出し処理として実
行する。

【０１６６】再帰読み出し処理としての図１７の最初の
ステップＳ１１１０では、ｔ＝ｎ＝８とする。上述した
処理と同様に、「ち，＼」に続く「Ｗ，１，＼」の３つ
の入力データに対する再帰読み出しによる展開処理で
は、図１７の最初のステップＳ１１１０では、ｔ＝ｎ＝
８とする。そして入力データが「Ｗ」の場合にＳ１１５
０の判断処理にてＳ１２００へ移行するため、Ｓ１２０
０において、Ｌａｂｅｌ（８）＝「Ｗ」とし、さらにＣ
ｈｉｌｄ（８）として次の入力データである「１」をセ
ットする。そして、さらに次の入力データが「＼」であ
るため、Ｓ１２１０にてＬａｓｔ（８）＝１となる。し
たがって、８番目のラベル「Ｗ」についてはＬａｓｔが
「１」でＣｈｉｌｄも「１」となる。

【０１６７】この場合、Ｓ１２１０後に移行するＳ１２
２０ではｋ＝ｔ＝８となり、Ｓ１２３０では、Ｃｈｉｌ
ｄ（ｋ）＝Ｃｈｉｌｄ（８）＝１であり、０でないため
Ｓ１２５０へ移行する。そして、Ｌａｓｔ（８）＝１で
あるため、Ｓ１２７０へ移行し、ｔ（＝８）を戻り値と
してリターンする。

【０１６８】この入力データ「Ｗ，１，＼」に対する再
帰読み出しによる展開処理は、図１７の最初のステップ
Ｓ１１１０でｔ＝ｎ＝７とした、入力データ「ち，＼」
に対する展開処理中におけるＳ１２４０での再帰読み出
し処理であるため、ｔ＝８を戻り値としてリターンされ
た場合には、Ｓ１２４０にてＣｈｉｌｄ（ｋ）＝８とな
る。つまり、Ｓ１２２０にてｋ＝ｔ＝７とした処理中で
あるため、結果的にＣｈｉｌｄ（７）＝８となる。

【０１６９】そして、続くＳ１２５０では、Ｌａｓｔ
（ｋ）＝Ｌａｓｔ（７）＝１であるため、Ｓ１２７０へ
移行し、ｔ（＝７）を戻り値としてリターンする。この
入力データ「ち，＼」に対する再帰読み出しによる展開
処理は、図１７の最初のステップＳ１１１０でｔ＝ｎ＝
５とした、入力データ「ま，ちょ，＼」に対する展開処
理中におけるＳ１２４０での再帰読み出し処理であるた
め、ｔ＝７を戻り値としてリターンされた場合には、Ｓ
１２４０にてＣｈｉｌｄ（ｋ）＝７となる。つまり、Ｓ
１２２０にてｋ＝ｔ＝５となり、結果的にＣｈｉｌｄ
（５）＝７となる。

【０１７０】そして、続くＳ１２５０では、Ｌａｓｔ
（ｋ）＝Ｌａｓｔ（５）＝０であるため、Ｓ１２６０へ
移行し、ｋ＝ｋ＋１＝６とインクリメントしてＳ１２３
０へ戻る。続くＳ１２３０では、Ｃｈｉｌｄ（ｋ）＝Ｃ
ｈｉｌｄ（６）＝０であるため、Ｓ１２４０へ移行し、
図１７，図１８の展開処理を再帰読み出し処理として実
行する。

【０１７１】再帰読み出しによる展開処理としての図１
７の最初のステップＳ１１１０では、ｔ＝ｎ＝９とす
る。この場合のＳ１１２０でのｘ＝次の入力データは上
述した「Ｗ，１」に続く「う」であり、さらに次の入力
データが「＼」であるため、「う」についてはＬａｓｔ
が「１」でＣｈｉｌｄが「０」となる。この場合はＳ１
１７０ではｎ＝１０にインクリメントされており、Ｓ１
２１０後に移行するＳ１２２０ではｋ＝ｔ＝９として、
Ｓ１２３０以降の処理を行なう。

【０１７２】そして、Ｓ１２３０ではＣｈｉｌｄ（９）
＝０であるためＳ１２４０へ移行する。Ｓ１２４０で
は、上記「う，＼」に続く「Ｊ，８」の２つの入力デー
タに対する再帰読み出しによる展開処理を実行する。再
帰読み出しによる展開処理としての図１７の最初のステ
ップＳ１１１０では、ｔ＝ｎ＝１０とする。そして入力
データが「Ｊ」であり、Ｓ１１３０の判断処理にてＳ１
１８０へ移行するため、Ｓ１１８０において、ｘ＝次の
入力データ＝「８」とする。そして、Ｓ１１９０におい
てｘ＝８を戻り値としてリターンする。

【０１７３】この入力データ「Ｊ，８」に対する再帰読
み出しによる展開処理は、入力データ「う，＼」に対す
る展開処理中におけるＳ１２４０での再帰読み出し処理
であるため、ｘ＝８を戻り値としてリターンされた場合
には、Ｓ１２４０にてＣｈｉｌｄ（ｋ）＝８となる。こ
の「う，＼」に対する展開処理はＳ１２２０にてｋ＝ｔ
＝９とされた状態であるので、結果的にＣｈｉｌｄ
（９）＝８となる。

【０１７４】そして、続くＳ１２５０では、Ｌａｓｔ
（ｋ）＝Ｌａｓｔ（９）＝１であるため、Ｓ１２７０へ
移行し、ｔ＝９を戻り値としてリターンする。この入力
データ「う，＼」に対する再帰読み出しによる展開処理
は、ｋ＝ｔ＝５とした入力データ「ま，ちょ，＼」に対
する展開処理中において、Ｓ１２６０にてｋ＝ｋ＋１＝
６とインクリメントした後にＳ１２３０へ戻り、Ｓ１２
３０にてＣｈｉｌｄ（６）＝０であるため、移行したＳ
１２４０での処理である。そのため、ｔ＝９を戻り値と
してリターンされたこの場合には、Ｓ１２４０にてＣｈ
ｉｌｄ（６）＝９となる。

【０１７５】そして、続くＳ１２５０では、Ｌａｓｔ
（ｋ）＝Ｌａｓｔ（６）＝１であるため、Ｓ１２７０へ
移行し、ｔ（＝５）を戻り値としてリターンする。この
入力データ「ま，ちょ，＼」に対する再帰読み出しによ
る展開処理は、図１７の最初のステップＳ１１１０でｔ
＝ｎ＝３とし、Ｓ１２２０ではｋ＝ｔ＝３とした入力デ
ータ「ん，み，＼」に対する展開処理中におけるＳ１２
４０での再帰読み出し処理であるため、ｔ＝７を戻り値
としてリターンされた場合には、Ｓ１２４０にてＣｈｉ
ｌｄ（３）＝５となる。

【０１７６】そして、続くＳ１２５０では、Ｌａｓｔ
（ｋ）＝Ｌａｓｔ（３）＝０であるため、Ｓ１２６０へ
移行し、ｋをインクリメントする。つまり、ｋ＝３＋１
＝４となる。そして、Ｓ１２６０後に移行するＳ１２３
０ではＣｈｉｌｄ（３）を０と比較する。この時点で
は、Ｃｈｉｌｄ（３）＝０であるため、Ｓ１２４０へ移
行して、図１７，図１８の展開処理を再帰読み出し処理
として実行する。

【０１７７】再帰読み出しによる展開処理としての図１
７の最初のステップＳ１１１０では、ｔ＝ｎ＝１０とす
る。この場合のＳ１１２０でのｘ＝次の入力データは上
述した「Ｊ，８」に続く「Ｗ」である。つまり、Ｓ１２
００にて、Ｌａｂｅｌ（１０）＝「Ｗ」とし、さらにＣ
ｈｉｌｄ（１０）として次の入力データである「２」を
セットする。また、Ｓ１１７０ではＬａｓｔ（１０）＝
０とし、ｎ＝１０＋１＝１１にインクリメントする。

【０１７８】そして、Ｓ１１２０では、さらに続く入力
データが「き」であるため、Ｓ１１６０にてＬａｂｅｌ
（１１）＝「き」、Ｃｈｉｌｄ（１１）＝０となり、さ
らにＳ１１７０では、Ｌａｓｔ（１１）＝０とすると共
に、ｎ＝１１＋１＝１２にインクリメントする。

【０１７９】その後の入力データが「＼」であるため、
Ｓ１２１０にてＬａｓｔ（１１）＝１となり、Ｓ１２２
０へ移行する。したがって、１０番目のラベル「Ｗ」に
ついてはＬａｓｔが「０」でＣｈｉｌｄが「２」とな
り、１１番目のラベル「き」についてはＬａｓｔが
「１」でＣｈｉｌｄが「０」となる。

【０１８０】Ｓ１２２０では、ｋ＝ｔ＝１０として、Ｓ
１２３０以降の処理を行なう。そして、Ｓ１２３０では
Ｃｈｉｌｄ（１０）＝２であるためＳ１２５０へ移行す
る。Ｓ１２５０では、Ｌａｓｔ（ｋ）＝Ｌａｓｔ（１
０）＝０であるため、Ｓ１２６０へ移行し、ｋ＝ｋ＋１
＝１１とインクリメントしてＳ１２３０へ戻る。続くＳ
１２３０では、Ｃｈｉｌｄ（ｋ）＝Ｃｈｉｌｄ（１１）
＝０であるため、Ｓ１２４０へ移行し、図１７，図１８
の展開処理を再帰読み出し処理として実行する。

【０１８１】再帰読み出しによる展開処理としての図１
７の最初のステップＳ１１１０では、ｔ＝ｎ＝１２とす
る。この場合のＳ１１２０でのｘ＝次の入力データは上
述した「き，＼」に続く「た」である。つまり、Ｓ１１
６０にて、Ｌａｂｅｌ（１２）＝「た」とし、さらにＣ
ｈｉｌｄ（１２）＝０をセットする。また、Ｓ１１７０
ではＬａｓｔ（１２）＝０とし、ｎ＝１２＋１＝１３に
インクリメントする。

【０１８２】そして、Ｓ１１２０では、さらに続く入力
データが「＼」であるため、Ｓ１２１０にてＬａｓｔ
（１２）＝１となり、Ｓ１２２０へ移行する。したがっ
て、１２番目のラベル「た」についてはＬａｓｔが
「１」でＣｈｉｌｄが「０」となる。

【０１８３】Ｓ１２２０では、ｋ＝ｔ＝１２として、Ｓ
１２３０以降の処理を行なう。そして、Ｓ１２３０では
Ｃｈｉｌｄ（１２）＝０であるため、Ｓ１２４０へ移行
し、図１７，図１８の展開処理を再帰読み出し処理とし
て実行する。再帰読み出しによる展開処理としての図１
７の最初のステップＳ１１１０では、ｔ＝ｎ＝１３とす
る。この場合のＳ１１２０でのｘ＝次の入力データは上
述した「た，＼」に続く「Ｗ」である。つまり、Ｓ１２
００にて、Ｌａｂｅｌ（１３）＝「Ｗ」とし、さらにＣ
ｈｉｌｄ（１３）＝次の入力データ＝３をセットする。
また、Ｓ１１７０ではＬａｓｔ（１３）＝０とし、ｎ＝
１３＋１＝１４にインクリメントする。

【０１８４】そして、Ｓ１１２０では、さらに続く入力
データが「＼」であるため、Ｓ１２１０にてＬａｓｔ
（１３）＝１となり、Ｓ１２２０へ移行する。したがっ
て、１３番目のラベル「Ｗ」についてはＬａｓｔが
「１」でＣｈｉｌｄが「３」となる。

【０１８５】Ｓ１２２０では、ｋ＝ｔ＝１３として、Ｓ
１２３０以降の処理を行なう。そして、Ｓ１２３０では
Ｃｈｉｌｄ（１３）＝３であるためＳ１２５０へ移行す
る。Ｓ１２５０では、Ｌａｓｔ（ｋ）＝Ｌａｓｔ（１
３）＝１であるため、Ｓ１２７０へ移行し、ｔ＝１３を
戻り値としてリターンする。

【０１８６】この入力データ「Ｗ，３，＼」に対する再
帰読み出しによる展開処理は、図１７の最初のステップ
Ｓ１１１０でｔ＝ｎ＝１２とし、Ｓ１２２０にてｋ＝ｔ
＝１２とした入力データ「た，＼」に対する展開処理中
におけるＳ１２４０での再帰読み出し処理であるため、
ｔ＝１３を戻り値としてリターンされた場合には、Ｓ１
２４０にてＣｈｉｌｄ（１２）＝１３となる。

【０１８７】そして、続くＳ１２５０では、Ｌａｓｔ
（ｋ）＝Ｌａｓｔ（１２）＝１であるため、Ｓ１２７０
へ移行し、ｔ＝１２を戻り値としてリターンする。この
入力データ「た，＼」に対する再帰読み出しによる展開
処理は、図１８のステップＳ１２２０でｋ＝ｔ＝１０と
し、Ｓ１２６０にてｋ＝ｋ＋１＝１１とインクリメント
した後にＳ１２３０へ戻り、Ｓ１２３０にてＣｈｉｌｄ
（１１）＝０であるため、移行したＳ１２４０での再帰
読み出し処理であるため、ｔ＝１２を戻り値としてリタ
ーンされた場合には、Ｓ１２４０にてＣｈｉｌｄ（１
１）＝１２となる。

【０１８８】そして、続くＳ１２５０では、Ｌａｓｔ
（ｋ）＝Ｌａｓｔ（１１）＝１であるため、Ｓ１２７０
へ移行する。この場合はＳ１２２０でｋ＝ｔ＝１０とし
た場合の処理であるため、ｔ＝１０を戻り値としてリタ
ーンする。そして、この処理は、図１７の最初のステッ
プＳ１１１０でｔ＝ｎ＝３とし、Ｓ１２２０ではｋ＝ｔ
＝３とした入力データ「ん，み，＼」に対する展開処理
中において、さらにＳ１２６０にてｋ＝３＋１＝４とイ
ンクリメンしてＳ１２３０へ戻り、Ｓ１２３０にてＣｈ
ｉｌｄ（４）＝０であるために実行したＳ１２４０での
再帰読み出し処理であるため、ｔ＝１０を戻り値として
リターンされた場合には、Ｓ１２４０にてＣｈｉｌｄ
（４）＝１０となる。

【０１８９】そして、続くＳ１２５０では、Ｌａｓｔ
（ｋ）＝Ｌａｓｔ（４）＝１であるため、Ｓ１２７０へ
移行する。この場合はＳ１２２０でｋ＝ｔ＝３とした場
合の処理であるため、ｔ＝３を戻り値としてリターンす
る。ここでの再帰読み出しによる展開処理は、図１７の
最初のステップＳ１１１０でｔ＝ｎ＝１とし、Ｓ１２２
０ではｋ＝ｔ＝１とした入力データ「ほ，あ，＼」に対
する展開処理を実行している途中での処理であるため、
ｔ＝３を戻り値としてリターンされた場合には、Ｓ１２
４０にてＣｈｉｌｄ（１）＝３となる。

【０１９０】ここまでの一連の処理によって、図２１に
示すように、ラベル番号１の「ほ」〜ラベル番号１３の
「Ｗ」のそれぞれについて、Ｌａｓｔの値が「０」か
「１」のいずれかに設定され、Ｃｈｉｌｄについても、
ラベル番号２の「あ」以外については「０」以外の値が
設定されている。つまり、自分にとっての子となる関係
のラベルの番号が付与されることとなる。

【０１９１】次に、Ｃ点に至るまでの経過を順に見てみ
る。上述したＳ１２４０の処理後は、Ｓ１２５０へ移行
する。Ｓ１２５０ではＬａｓｔ（ｋ）＝Ｌａｓｔ（１）
＝０であるため、Ｓ１２６０へ移行し、ｋをインクリメ
ントする。つまり、ｋ＝１＋１＝２となる。そして、Ｓ
１２６０後に移行するＳ１２３０ではＣｈｉｌｄ（ｋ）
＝Ｃｈｉｌｄ（２）＝０であるため、Ｓ１２４０へ移行
し、図１７，図１８の展開処理を再帰読み出し処理とし
て実行する。

【０１９２】この場合の再帰読み出しによる展開処理と
しての図１７の最初のステップＳ１１１０では、ｔ＝ｎ
＝１４とする。この場合のＳ１１２０でのｘ＝次の入力
データは上述した「Ｗ，２，＼」に続く「い」である。
つまり、Ｓ１１６０にて、Ｌａｂｅｌ（１２）＝「い」
とし、さらにＣｈｉｌｄ（１４）＝０をセットする。ま
た、Ｓ１１７０ではＬａｓｔ（１４）＝０とし、ｎ＝１
４＋１＝１５にインクリメントする。

【０１９３】そして、Ｓ１１２０では、さらに続く入力
データが「＼」であるため、Ｓ１２１０にてＬａｓｔ
（１４）＝１となり、Ｓ１２２０へ移行する。したがっ
て、１４番目のラベル「い」についてはＬａｓｔが
「１」でＣｈｉｌｄが「０」となる。

【０１９４】Ｓ１２２０では、ｋ＝ｔ＝１４として、Ｓ
１２３０以降の処理を行なう。そして、Ｓ１２３０では
Ｃｈｉｌｄ（１４）＝０であるため、Ｓ１２４０へ移行
し、図１７，図１８の展開処理を再帰読み出し処理とし
て実行する。この場合の再帰読み出しによる展開処理と
しての図１７の最初のステップＳ１１１０では、ｔ＝ｎ
＝１５とする。この場合のＳ１１２０でのｘ＝次の入力
データは上述した「い，＼」に続く「お」である。つま
り、Ｓ１１６０にて、Ｌａｂｅｌ（１５）＝「お」と
し、さらにＣｈｉｌｄ（１５）＝０をセットする。ま
た、Ｓ１１７０ではＬａｓｔ（１５）＝０とし、ｎ＝１
５＋１＝１６にインクリメントする。そして、Ｓ１１２
０では、さらに続く入力データが「＼」であるため、Ｓ
１２１０にてＬａｓｔ（１５）＝１となり、Ｓ１２２０
へ移行する。

【０１９５】したがって、１５番目のラベル「お」につ
いてはＬａｓｔが「１」でＣｈｉｌｄが「０」となる。
Ｓ１２２０では、ｋ＝ｔ＝１５として、Ｓ１２３０以降
の処理を行なう。そして、Ｓ１２３０ではＣｈｉｌｄ
（１５）＝０であるため、Ｓ１２４０へ移行し、図１
７，図１８の展開処理を再帰読み出し処理として実行す
る。

【０１９６】この場合の再帰読み出しによる展開処理と
しての図１７の最初のステップＳ１１１０では、ｔ＝ｎ
＝１６とする。この場合のＳ１１２０でのｘ＝次の入力
データは上述した「お，＼」に続く「い」である。つま
り、Ｓ１１６０にて、Ｌａｂｅｌ（１６）＝「い」と
し、さらにＣｈｉｌｄ（１６）＝０をセットする。ま
た、Ｓ１１７０ではＬａｓｔ（１６）＝０とし、ｎ＝１
６＋１＝１７にインクリメントする。そして、Ｓ１１２
０では、さらに続く入力データが「＼」であるため、Ｓ
１２１０にてＬａｓｔ（１６）＝１となり、Ｓ１２２０
へ移行する。

【０１９７】したがって、１６番目のラベル「い」につ
いてはＬａｓｔが「１」でＣｈｉｌｄが「０」となる。
Ｓ１２２０では、ｋ＝ｔ＝１６として、Ｓ１２３０以降
の処理を行なう。そして、Ｓ１２３０ではＣｈｉｌｄ
（１６）＝０であるため、Ｓ１２４０へ移行し、図１
７，図１８の展開処理を再帰読み出し処理として実行す
る。

【０１９８】この場合の再帰読み出しによる展開処理と
しての図１７の最初のステップＳ１１１０では、ｔ＝ｎ
＝１７とする。この場合のＳ１１２０でのｘ＝次の入力
データは上述した「い，＼」に続く「Ｗ」である。つま
り、Ｓ１１５０の判断処理からＳ１２００へ移行し、Ｓ
１２００にて、Ｌａｂｅｌ（１７）＝「Ｗ」とし、さら
にＣｈｉｌｄ（１７）＝次の入力データ＝４をセットす
る。また、Ｓ１１７０ではＬａｓｔ（１７）＝０とし、
ｎ＝１７＋１＝１８にインクリメントする。

【０１９９】そして、Ｓ１１２０では、さらに続く入力
データが「＼」であるため、Ｓ１２１０にてＬａｓｔ
（１７）＝１となり、Ｓ１２２０へ移行する。したがっ
て、１７番目のラベル「Ｗ」についてはＬａｓｔが
「１」でＣｈｉｌｄが「４」となる。

【０２００】Ｓ１２２０では、ｋ＝ｔ＝１７として、Ｓ
１２３０以降の処理を行なう。そして、Ｓ１２３０では
Ｃｈｉｌｄ（１７）＝４であるためＳ１２５０へ移行す
る。Ｓ１２５０では、Ｌａｓｔ（ｋ）＝Ｌａｓｔ（１
７）＝１であるため、Ｓ１２７０へ移行し、ｔ＝１７を
戻り値としてリターンする。

【０２０１】この入力データ「Ｗ，４，＼」に対する再
帰読み出しによる展開処理は、図１７の最初のステップ
Ｓ１１１０でｔ＝ｎ＝１６とし、Ｓ１２２０にてｋ＝ｔ
＝１６とした入力データ「い，＼」に対する展開処理中
におけるＳ１２４０での再帰読み出し処理であるため、
ｔ＝１６を戻り値としてリターンされた場合には、Ｓ１
２４０にてＣｈｉｌｄ（１６）＝１７となる。

【０２０２】そして、続くＳ１２５０では、Ｌａｓｔ
（ｋ）＝Ｌａｓｔ（１６）＝１であるため、Ｓ１２７０
へ移行し、ｔ＝１６を戻り値としてリターンする。この
入力データ「い，＼」に対する再帰読み出しによる展開
処理は、図１７の最初のステップＳ１１１０でｔ＝ｎ＝
１５とし、Ｓ１２２０にてｋ＝ｔ＝１５とした入力デー
タ「お，＼」に対する展開処理中におけるＳ１２４０で
の再帰読み出し処理であるため、ｔ＝１６を戻り値とし
てリターンされた場合には、Ｓ１２４０にてＣｈｉｌｄ
（１５）＝１６となる。

【０２０３】そして、続くＳ１２５０では、Ｌａｓｔ
（ｋ）＝Ｌａｓｔ（１５）＝１であるため、Ｓ１２７０
へ移行し、ｔ＝１５を戻り値としてリターンする。この
入力データ「お，＼」に対する再帰読み出しによる展開
処理は、図１７の最初のステップＳ１１１０でｔ＝ｎ＝
１４とし、Ｓ１２２０にてｋ＝ｔ＝１４とした入力デー
タ「い，＼」に対する展開処理中におけるＳ１２４０で
の再帰読み出し処理であるため、ｔ＝１５を戻り値とし
てリターンされた場合には、Ｓ１２４０にてＣｈｉｌｄ
（１４）＝１５となる。

【０２０４】そして、この処理は、図１７の最初のステ
ップＳ１１１０でｔ＝ｎ＝１とし、Ｓ１２２０ではｋ＝
ｔ＝１とした入力データ「ん，み，＼」に対する展開処
理中において、さらにＳ１２６０にてｋ＝１＋１＝２と
インクリメンしてＳ１２３０へ戻り、Ｓ１２３０にてＣ
ｈｉｌｄ（２）＝０であるために実行したＳ１２４０で
の再帰読み出し処理であるため、ｔ＝１４を戻り値とし
てリターンされた場合には、Ｓ１２４０にてＣｈｉｌｄ
（２）＝１４となる。

【０２０５】そして、続くＳ１２５０では、Ｌａｓｔ
（ｋ）＝Ｌａｓｔ（２）＝１であるため、Ｓ１２７０へ
移行して、本処理をリターンする。ここまでの一連の処
理によって、図２２に示すように、ラベル番号１の
「ほ」〜ラベル番号１７の「Ｗ」のそれぞれについて、
Ｌａｓｔの値が「０」か「１」のいずれかに設定され
る。また、Ｃｈｉｌｄについても、上述したＢ点での状
態を示す図２１ではラベル番号２の「あ」が「０」であ
ったが、それにも値「１４」が設定されている。もちろ
ん、新規に作成したラベル番号１４の「い」〜ラベル番
号１７の「Ｗ」のそれぞれについてのＣｈｉｌｄも設定
されている。

【０２０６】以上説明した単語辞書データの圧縮方法や
展開方法を実行するプログラムは、例えば圧縮する際に
使用するワークステーションや、展開する際に使用する
音声認識装置３０側の対話制御部３２（図１，２参照）
などのコンピュータシステム側で起動するプログラムと
して備えられる。このようなプログラムの場合、例えば
フロッピーディスク、光磁気ディスクやＣＤ−ＲＯＭ、
ハードディスク等の機械読取り可能な記録媒体に記憶
し、必要に応じてコンピュータシステムにロードして起
動することにより用いることができる。この他、ＲＯＭ
やバックアップＲＡＭを機械読み取り可能な記録媒体と
してプログラムを記憶しておき、このＲＯＭあるいはバ
ックアップＲＡＭをコンピュータシステムに組み込んで
用いてもよい。

【０２０７】本カーナビゲーションシステム２の場合に
は、音声認識装置３０にて認識されたナビゲート処理関
連の指示データが制御回路１０に送られ、その指示デー
タに基づくナビゲーション処理を行なうこととなる。ナ
ビゲーションという性質を考えれば、この指示データの
中心を成すのが地名データである。そして、この地名デ
ータは、上述したように音節データの等しい単語が複数
存在する可能性が高いという固有の性質に加え、ナビゲ
ーション装置側の地図データの一部という性質から新規
追加あるいは更新される状況も多く想定される。つま
り、地図データ入力器６を介して更新データの入力が可
能である。

【０２０８】そして、その地図データの新規追加あるい
は更新に対応しようとすると、音声認識装置３０に対し
て外部から地名データに対応する単語辞書データを供給
する必要がある。地名の新規追加あるいは更新は、基本
的にテキスト形式のデータとして実現されることが考え
られるが、それらを上述のグラフ形式の単語辞書データ
とするには大量のメモリとなり高性能なＣＰＵが必要と
される。従って、音声認識装置３０側にそれらを備える
ことは実用的ではなく、外部でそれらの新規追加あるい
は更新に対応して作成されたグラフ形式の単語辞書デー
タを供給する必要が出て来る。但し、グラフ形式の辞書
データであってもデータサイズはかなり大きいため、制
御回路１０から音声認識装置３０へ単語辞書データを転
送することを考えると、大規模な単語辞書データをその
ままの状態で転送することは通信時間が長くなり、やは
り実用的ではない。そのため、圧縮辞書データの状態に
した上で、音声認識装置３０側に転送することで、上記
通信時間を短縮することができる。

【０２０９】以上、本発明はこのような実施例に何等限
定されるものではなく、本発明の主旨を逸脱しない範囲
において種々なる形態で実施し得る。例えば、上述した
図１０〜図１２で示した圧縮処理や、図１６〜図１８で
示した展開処理は、本発明の単語辞書データの圧縮方法
や展開方法を実現する場合の一例であり、この処理内容
自体には限定されない。つまり、図１０〜図１２で示し
た圧縮処理は、「木構造を基本とするが頂点へ到達する
通路の個数は必ずしも１ではない木構造類似の有向グラ
フ形式に対応するよう、音節データ及び単語終了を示す
識別データを第１の走査順にしたがって各頂点に割り付
けると共に、各頂点毎に自分の子及び兄弟識別用のデー
タを持たせたグラフ辞書データに変換する」処理を具体
的に示した一例である。同様に、図１６〜図１８で示し
た展開処理は、「圧縮辞書データ中の音節及び単語終了
を示す識別データが第２の走査順にしたがって並び替え
られていると共に、頂点に兄弟が存在する場合にはその
兄弟関係を他と区別するための識別データが存在するこ
とに基づき、その圧縮辞書データ中の音節及び単語終了
を示す識別データに加え、当該音節及び単語終了を示す
識別データ毎に自分の子を識別するためのデータを設定
して第２のグラフ辞書データに展開する」処理を具体的
に示した一例である。また、上記実施形態では、ナビゲ
ーション装置の制御回路１０が音声認識装置３０側への
転送するための単語辞書データを圧縮辞書データの状態
でナビ用ＣＤに書き込むようにしている（図３参照）。
そして、この圧縮辞書データへの変換は例えばワークス
テーションなどで実行するようにしている。これは、グ
ラフ形式の単語辞書データとするには大量のメモリとか
なり高性能なＣＰＵが必要とされるため、ワークステー
ションなどで実行することが現実的であることに基づい
ている。但し、ナビゲーション装置の制御回路１０自身
がその圧縮辞書データへの変換処理を実行しても構わな
い。

【０２１０】また、本発明の圧縮処理は、上述した「…
…音節データ及び単語終了を示す識別データを第１の走
査順にしたがって各頂点に割り付けると共に……」に示
すように、「第１の走査順」にしたがうこととしてお
り、上記実施形態では、この第１の走査順として先行順
走査（preorder traversal）を採用した。もちろん、他
の走査として「inorder traversal」や「postorder tra
versal」があるが、これらの走査であっても実現は可能
である。

【０２１１】なお、上記実施形態では、カーナビゲーシ
ョンシステムに適用した例として説明したが、音声認識
機能を用いて利用者の指示を入力するようなシステムと
してはそれ以外にも種々考えられ、それらのシステムに
ついても同様に実現可能である。但し、カーナビゲーシ
ョンシステムの場合には車載機器用として用いるという
限定と、目的地などを地名で入力する必要があるという
点で、本発明の単語辞書データの圧縮方法や展開方法を
適用する際のメリットが非常に大きいと考えられる。

【図面の簡単な説明】

【図１】本発明の実施形態としてのカーナビゲーション
システムの概略構成を示すブロック図である。

【図２】実施形態の音声認識装置における音声認識部と
対話制御部の構成を示すブロック図である。

【図３】圧縮辞書データを生成する際の手順を示す説明
図である。

【図４】テキスト辞書データの具体例を示す説明図であ
る。

【図５】グラフ辞書データの具体例を示す説明図であ
る。

【図６】グラフ辞書データの具体例をポインタ表現で示
す説明図である。

【図７】グラフ辞書データの具体例を配列表現で示す説
明図である。

【図８】圧縮辞書データの具体例を示す説明図である。

【図９】第２のグラフ辞書データの具体例を示す説明図
である。

【図１０】圧縮処理を示すフローチャートである。

【図１１】圧縮処理を示すフローチャートである。

【図１２】圧縮処理を示すフローチャートである。

【図１３】図１０のＳ３０での圧縮（１）処理の内容を
概念的に示す説明図である。

【図１４】グラフ辞書データが圧縮辞書データに変換さ
れる場合の途中経過を示す説明図である。

【図１５】グラフ辞書データが圧縮辞書データに変換さ
れる場合の途中経過を示す説明図である。

【図１６】展開処理を示すフローチャートである。

【図１７】展開処理を示すフローチャートである。

【図１８】展開処理を示すフローチャートである。

【図１９】展開処理の内容を概念的に示す説明図であ
る。

【図２０】圧縮辞書データが第２のグラフ辞書データに
展開される場合の途中経過であって、図１９におけるＡ
点での状態を示す説明図である。

【図２１】圧縮辞書データが第２のグラフ辞書データに
展開される場合の途中経過であって、図１９におけるＢ
点での状態を示す説明図である。

【図２２】圧縮辞書データが第２のグラフ辞書データに
展開される場合の途中経過であって、図１９におけるＣ
点での状態を示す説明図である。

【図２３】圧縮辞書データが第２のグラフ辞書データに
展開される場合の図１９におけるＡ，Ｂ，Ｃ点での未入
力データを示す説明図である。

【符号の説明】

２…カーナビゲーションシステム ４…位置検出器 ６…地図データ入力器 ８…操作スイッチ
群 １０…制御回路 １２…外部メモリ １４…表示装置 １５…リモコンセ
ンサ １５ａ…リモコン １６…地磁気セ
ンサ １８…ジャイロスコープ ２０…距離センサ ２２…ＧＰＳ受信機 ３０…音声認識装
置 ３１…音声認識部 ３１ａ…照合部 ３１ｂ…辞書部 ３２…対話制御
部 ３２ａ…後処理部 ３２ｂ…通信制御
部 ３２ｃ…辞書制御部 ３３…音声合成
部 ３４…音声入力部 ３５…マイク ３６…ＰＴＴスイッチ ３７…スピーカ

Claims (13)

【特許請求の範囲】
1. 【請求項１】 単語を構成する音節データの等しい単語
   が複数存在するような単語群をテキスト形式で作成した
   単語辞書データを圧縮する方法であって、 前記テキスト形式の単語辞書データを、木構造を基本と
   するが頂点へ到達する通路の個数は必ずしも１ではない
   木構造類似の有向グラフ形式に対応するよう、前記音節
   データ及び単語終了を示す識別データを第１の走査順に
   したがって各頂点に割り付けると共に、各頂点毎に自分
   の子及び兄弟識別用のデータを持たせたグラフ辞書デー
   タに変換する第１の変換処理と、 前記第１の変換処理によって得た前記グラフ辞書データ
   に対し、前記木構造類似の有向グラフの頂点に割り付け
   られた音節及び単語終了を示す識別データを、前記第１
   の走査順に基本的には従いながら前記頂点に兄弟が存在
   する場合には当該兄弟についても走査していく第２の走
   査順に従って並びかえると共に、自己の兄弟関係を他と
   区別するための識別データとを持たせた圧縮辞書データ
   に変換する第２の変換処理と、 を行なうことによって、前記単語辞書データを実質的に
   圧縮することを特徴とする単語辞書データの圧縮方法。
2. 【請求項２】 前記第１の走査順は先行順走査であるこ
   とを特徴とする請求項１に記載の単語辞書データの圧縮
   方法。
3. 【請求項３】 前記第２の変換処理において用いられる
   自己の兄弟関係を他と区別するための識別データとし
   て、所定の音節が末弟であることを示すデータを用いた
   ことを特徴とする請求項１又は２に記載の単語辞書デー
   タの圧縮方法。
4. 【請求項４】 前記第２の変換処理において用いられる
   自己の兄弟関係を他と区別するための識別データとし
   て、兄弟数を示すデータを用いたことを特徴とする請求
   項１又は２に記載の単語辞書データの圧縮方法。
5. 【請求項５】 前記第２の変換処理によって前記圧縮辞
   書データに変換された単語辞書データを、さらに所定の
   データ圧縮方法を用いて圧縮することを特徴とする請求
   項１乃至４のいずれかに記載の単語辞書データの圧縮方
   法。
6. 【請求項６】 前記請求項１乃至５のいずれかに記載の
   単語辞書データの圧縮方法が、コンピュータシステムに
   よって実行するプログラムとして記録されたことを特徴
   とする機械読み取り可能な記録媒体。
7. 【請求項７】 前記請求項１乃至４のいずれかに記載の
   単語辞書データの圧縮方法によって圧縮された前記圧縮
   辞書データを展開する方法であって、 前記圧縮辞書データ中の前記音節及び単語終了を示す識
   別データが前記第２の走査順にしたがって並び替えられ
   ていると共に、前記頂点に兄弟が存在する場合にはその
   兄弟関係を他と区別するための識別データが存在するこ
   とに基づき、その圧縮辞書データ中の音節及び単語終了
   を示す識別データに加え、当該音節及び単語終了を示す
   識別データ毎に自分の子を識別するためのデータを設定
   して第２のグラフ辞書データに展開する単語辞書データ
   の展開方法。
8. 【請求項８】 前記請求項５に記載の単語辞書データの
   圧縮方法によって圧縮された前記圧縮辞書データを展開
   する方法であって、 前記所定の圧縮方法によって圧縮された状態の前記単語
   辞書データを、当該所定の圧縮方法による圧縮前の状態
   である前記圧縮辞書データに伸長し、 当該伸長した前記圧縮辞書データ中の前記音節及び単語
   終了を示す識別データが前記第２の走査順にしたがって
   並び替えられていると共に、前記頂点に兄弟が存在する
   場合にはその兄弟関係を他と区別するための識別データ
   が存在することに基づき、その圧縮辞書データ中の音節
   及び単語終了を示す識別データに加え、当該音節及び単
   語終了を示す識別データ毎に自分の子を識別するための
   データを設定して第２のグラフ辞書データに展開する単
   語辞書データの展開方法。
9. 【請求項９】 前記請求項７又は８に記載の単語辞書デ
   ータの展開方法が、コンピュータシステムによって実行
   するプログラムとして記録されたことを特徴とする機械
   読み取り可能な記録媒体。
10. 【請求項１０】 認識すべき複数の単語の音響的特徴量
    が、各単語毎に予め格納された単語辞書記憶手段と、 外部からの入力音声を分析して音響的特徴量を抽出する
    音響分析手段と、 該音響分析手段にて抽出された音響的特徴量の時系列デ
    ータを、前記単語辞書記憶手段に格納された音響的特徴
    量に最も近似したデータ列毎に区分し、各データ列毎
    に、対応する音響的特徴量が表わす単語を割り当て、前
    記入力音声の単語系列を認識する音声認識手段と、 該音声認識手段による認識結果を外部装置に出力する出
    力手段と、 を備えた音声認識装置において、 前記単語辞書データを、前記請求項１乃至５のいずれか
    に記載の単語辞書データの圧縮方法によって前記圧縮辞
    書データに変換された状態で外部装置から入力する圧縮
    辞書データ入力手段と、 前記圧縮辞書データ入力手段を介して入力した前記圧縮
    辞書データを、前記請求項７又は８に記載の単語辞書デ
    ータの展開方法によって前記第２のグラフ辞書データに
    展開する圧縮辞書データ展開手段とを備え、 前記単語辞書記憶手段には、前記圧縮辞書データ展開手
    段によって前記第２のグラフ辞書データに展開された状
    態の単語辞書データが記憶されていることを特徴とする
    音声認識装置。
11. 【請求項１１】 認識すべき複数の単語の音響的特徴量
    が、各単語毎に予め格納された単語辞書記憶手段と、 外部からの入力音声を分析して音響的特徴量を抽出する
    音響分析手段と、 該音響分析手段にて抽出された音響的特徴量の時系列デ
    ータを、前記単語辞書記憶手段に格納された音響的特徴
    量に最も近似したデータ列毎に区分し、各データ列毎
    に、対応する音響的特徴量が表わす単語を割り当て、前
    記入力音声の単語系列を認識する音声認識手段と、 該音声認識手段による認識結果を外部装置に出力する出
    力手段と、 を備えた音声認識装置において、 前記単語辞書データを、前記請求項１乃至５のいずれか
    に記載の単語辞書データの圧縮方法によって前記圧縮辞
    書データに変換された状態で外部装置から入力する圧縮
    辞書データ入力手段を備え、 前記単語辞書記憶手段には、前記圧縮辞書データ入力手
    段によって外部装置から入力した前記圧縮辞書データが
    記憶されており、 さらに、電源投入時又は音声認識処理実行時に、前記圧
    縮辞書データ記憶手段から読み出した前記圧縮辞書デー
    タを、前記請求項７又は８に記載の単語辞書データの展
    開方法によって前記第２のグラフ辞書データに展開する
    圧縮辞書データ展開手段を備えることを特徴とする音声
    認識装置。
12. 【請求項１２】 請求項１０又は１１に記載の音声認識
    装置と、ナビゲーション装置とを備え、前記音声認識装
    置の前記音声入力手段は、前記ナビゲーション装置がナ
    ビゲート処理をする上で指定される必要のある所定のナ
    ビゲート処理関連データの指示を利用者が音声にて入力
    するために用いられるものであり、前記出力手段は、前
    記音声認識手段による認識結果を前記ナビゲーション装
    置に出力するよう構成されている音声認識機能付きナビ
    ゲーションシステムであって、前記ナビゲーション装置
    は、 前記単語辞書データを、前記請求項１乃至４のいずれか
    に記載の単語辞書データの圧縮方法によって前記圧縮辞
    書データに変換された状態で記憶しておく圧縮辞書デー
    タ記憶手段と、 所定の辞書転送必要時に前記圧縮辞書データ記憶手段か
    ら前記圧縮辞書データを読み出し、前記音声認識装置に
    転送する辞書データ転送手段と、 を備えていることを特徴とするナビゲーションシステ
    ム。
13. 【請求項１３】 請求項１２に記載にナビゲーションシ
    ステムにおいて、 前記単語辞書データを、前記請求項１乃至５のいずれか
    に記載の単語辞書データの圧縮方法によって前記圧縮辞
    書データに変換された状態で外部装置から入力するナビ
    側圧縮辞書データ入力手段を備え、 該ナビ側圧縮辞書データ入力手段を介して入力した前記
    圧縮辞書データを、前記圧縮辞書データ記憶手段に記憶
    しておくよう構成されていることを特徴とするナビゲー
    ションシステム。