JPH10198391A

JPH10198391A - ネットワーク作成装置およびそのネットワーク作成方法

Info

Publication number: JPH10198391A
Application number: JP9004613A
Authority: JP
Inventors: Riyuuichi Oka; 嶐一岡; Jun Toyoura; 潤豊浦
Original assignee: GIJUTSU KENKYU KUMIAI SHINJOHO SHIYORI KAIHATSU KIKO; Mitsubishi Electric Corp
Current assignee: GIJUTSU KENKYU KUMIAI SHINJOHO SHIYORI KAIHATSU KIKO; Mitsubishi Electric Corp
Priority date: 1997-01-14
Filing date: 1997-01-14
Publication date: 1998-07-31
Anticipated expiration: 2017-01-14
Also published as: JP3291501B2

Abstract

(57)【要約】【課題】記号系列のネットワークを自動作成する。【解決手段】キーボードから入力された記号系列の中
の記号系列を先頭から順次に所定個数ＣＰＵ１００によ
り取り出す。記憶領域１０１に記憶されているネットワ
ーク情報の示す記号接続構造を照合して、取り出した記
号系列の中の接続構造が不一致の部分をＣＰＵ１００に
より検出する。不一致の部分は新規な部分なので、この
部分のネットワークを上記ネットワークに派生させて増
設することにより初期状態のネットワークから記号系列
が入力される毎に新規部分をネットワークに増設して新
規ネットワークを構築する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、テキストや音声
や画像など記号系列で表現する場合に、その記号系列の
構造を示すネットワークを形成するネットワーク作成装
置およびそのネットワーク作成方法に関する。

【０００２】

【従来の技術】記号系列のデータのモデル化やその系列
の特徴を表現するために、従来多くの表示方法が考えら
れてきた。

【０００３】１．入力記号系列を、パージングして部分
記号列に分解し（例えば、自然言語の分を単語単位に分
割するように）各部分記号列の出現頻度を計算し、この
値をベクトルの要素とする「ベクトル表示」（後述の参
考文献４）２．時系列中に出現する連続するｎ項の記号列データの
出現頻度を対象の記号系列中から計算して得られる「n-
gram表示」（参考文献２，３）３．Hidden Markov Model （ＨＭＭ）のように、原理的
にはともかく通常、音素モデルのように３状態程度から
なるトポロジーの簡単なネットワークを与え、各ＶＱco
deのノード間の遷移確率を、入力単語や文の記述が与え
られた音声波形の分析データから計算して得られる「Ｈ
ＭＭ表示」（参考文献７）。

【０００４】４．ネットワークを人間の視察によって構
成するもので、いわゆる意味ネットワークを含む「ネッ
トワークモデル表示」（参考文献１）。

【０００５】５．上記４と類似しているが、より形式化
されたオートマンとして表現される場合の「オートマト
ン表示」（参考文献５，６）などがあった。

【０００６】（参考文献）１ M.R.Quillian. Semantic Information Processing,
chapter Semantic Memory. MIT Press,MA,1968. ２ J.Rissanen. A universal data compression syste
m. IEEE Trans. Inform.Theory,IT-29:656-664,1983. ３ J.Rissanen. Complexity of strings in the class
of markov sources.IEEE Trans. Inform. Theory, IT-
32:526-532,1986. ４ G.Salton and M.J.McGill. Introduction to moder
n information retrieval. McGraw-Hill, New York, 19
83. ５榎本肇，堂下修司，富田悦次，and 山口泰彦．句構
造サンプルパターンを識別するオートマトンの構成につ
いて．信学会オートマトン研資，A69-76, Mar.1970. ６榎本肇，堂下修司，富田悦次，and 長谷川和幸．サ
ンプルストリングによるオートマトンの構成と表現．信
学会オートマトン研資，A70-39,Oct.1970. ７中川聖一．確率モデルによる音声認識．電子情報通
信学会誌，1988．上記の記号系列のデータのモデル化の中で、「ネットワ
ークモデル表示」はその表現が直感的であること、また
その改変が比較的容易であることにより、意味ネットワ
ークも含めて、自然言語理解、画像理解、音声理解、Ex
pert-system 等、幅広く応用されている。しかし「ネッ
トワークモデル」の作成においては、そのトポロジーを
決定することも含めて、多くは人間の視察に基づいてな
されているといってよい。しかし、極めて大量の時系列
データを対象にしたり、また、そのノード数やトポロジ
ーを事前に決められないほど変動する場合や、ネットワ
ーク自体の規模が極めて大きくなる場合、その作成を人
間の視察に頼ることが実際上できなくなるという問題が
あった。

【０００７】この点をより具体的に説明する。たとえば
「ＡＢＣ」という記号列では記号「Ａ」と記号「Ｂ」が
隣接しており、かつ、記号「Ａ」から記号「Ｂ」に状態
遷移していることを示している。このような記号系列の
構造を表わすために、ネットワーク表現ではノードとリ
ンク（アークとも呼ばれる）を使用する。図１にネット
ワークの一例を示す。

【０００８】図１中符号１，２，３はノード、符号４，
５，６はリンクである。ノードの図形の中に示した番号
はノード番号である。上記記号系列「ＡＢＣ」ではノー
ド番号０が始点のノードとなる。ノード０からノード０
に戻るリンク文字「Ａ」が割当てられ、記号「Ｂ」はノ
ード０（符号１）とノード２（符号２）とを接続するリ
ンク５に割当てられる。同様に記号「Ｃ」はノード１
（符号２）とノード２（符号３）とを接続するリンク６
に割当てられる。記号系列「ＡＢＣ」のネットワーク構
造をコンピュータシステム上で記憶するために一般的に
次のような記号表現を行う。

【０００９】ノード番号ｉからノード番号ｊに向うリン
クをＡ_ijと表わす。図１の（１）のネットワークでは、
Ａ_0,0 ＝Ａ，Ａ_0,1 ＝Ｂ，Ａ_1,2 ＝Ｃとなる。このよう
なネットワーク表現を使用すると、文字列「ＡＢＣＢ
Ｅ」は図１の（２）のようにネットワーク表現できる。

【００１０】

【発明が解決しようとする課題】このようなネットワー
ク表現では、重複的に使用される記号の他の記号との間
の接続関係がよく分かるという反面、図１の（２）のよ
うに重複的に使用される文字列（図１の場合「Ｂ」）が
多数発生すると、人間がその都度Ａ_0,0 ＝Ａ，Ａ_0,1 ＝
Ｂというようにネットワーク構造に関する情報を与える
ことが難しくなる。

【００１１】そこで、本発明の目的は、記号系列を入力
し、その文字列の接続構造を示すネットワークを自動作
成することができるネットワーク作成装置およびそのネ
ットワーク作成方法を提供することにある。

【００１２】

【課題を解決するための手段】このような目的を達成す
るために、請求項１の発明は、作成すべきネットワーク
を記憶しておく記憶手段と、前記作成すべきネットワー
クの初期状態を設定する初期化手段と、複数の記号が連
続的に結合された記号系列を入力する入力手段と、当該
入力された記号系列の中の各記号位置を先頭として所定
個数の記号系列を前記入力された記号系列から抽出する
第１の情報処理手段と、当該抽出された記号系列と同じ
接続構造が前記記憶手段のネットワークの中に存在する
か否かを判定する判定手段と、判定結果として否定判定
が得られた場合には、前記ネットワークに派生させて前
記抽出された記号系列のネットワークを増設する第２情
報処理手段とを具えたことを特徴とする。

【００１３】請求項２の発明は、請求項１に記載のネッ
トワーク作成装置において、前記ネットワークは複数の
ノードおよび該ノードの間を結合するリンクから構成さ
れ、前記記号系列の各記号を前記リンクに割り当てるこ
とにより該記号系列の接続構造をネットワーク表現する
ことを特徴とする。

【００１４】請求項３の発明は、請求項２に記載のネッ
トワーク作成装置において、前記初期状態はノードのみ
が存在し、リンクが存在しない状態であり、前記入力手
段から記号系列が入力されるごとに前記第２情報処理手
段は、リンクが未接続のノードとリンクが接続済みのノ
ードをリンクにより接続することにより前記抽出された
記号系列のネットワークを増設することを特徴とする。

【００１５】請求項４の発明は、請求項３に記載のネッ
トワーク作成装置において、前記第２情報処理手段は抽
出された記号系列の接続構造について、前記ネットワー
クの接続構造と合致しない部位を検出し、当該検出した
部位を新規ネットワークとして増設することを特徴とす
る。

【００１６】請求項５の発明は、請求項１に記載のネッ
トワーク作成装置において、前記ネットワークは複数の
ノードおよび該ノードの間を結合するリンクから構成さ
れ、記号系列の各記号を前記ノードに割り当て隣接する
記号をリンクで接続することにより該記号系列の接続構
造をネットワーク表現することを特徴とする。

【００１７】請求項６の発明は、請求項１に記載のネッ
トワーク作成装置において、前記入力手段は前記入力さ
れた記号系列の各記号にその記号位置を示す情報を付加
し、前記第２情報処理手段は該情報を付加した該記号系
列ネットワークを増設し、前記入力された記号系列の中
の前記記憶手段のネットワークの中の記号接続構造と前
記記号位置を示す情報が一致する記号系列を連想結果と
して抽出する第３情報処理手段をさらに具えたことを特
徴とする。

【００１８】請求項７の発明は、請求項６に記載のネッ
トワーク作成装置において、前記記号位置を示す情報は
時刻刻印であることを特徴とする。

【００１９】請求項８の発明は、記号系列の接続構造を
示すネットを作成するネットワーク作成装置の作成方法
において、初期状態のネットワークを予め記憶装置に記
憶しておき、複数の記号が連続的に結合された記号系列
を入力し、当該入力された記号系列の中の各記号位置を
先頭として所定個数の記号系列を前記入力された記号系
列から情報処理装置により抽出し、当該抽出された記号
系列と同じ接続構造が前記記憶手段のネットワークの中
に存在するか否かを前記情報処理装置により判定し、判
定結果として否定判定が得られた場合には、前記記憶装
置上のネットワークに派生させて前記抽出された記号系
列のネットワークを前記情報処理装置により増設するこ
とを特徴とする。

【００２０】請求項９の発明は、請求項８に記載のネッ
トワーク作成装置の作成方法において、前記ネットワー
クは複数のノードおよび該ノードの間を結合するリンク
から構成され、前記記号系列の各記号を前記リンクに割
り当てることにより該記号系列の接続構造をネットワー
ク表現することを特徴とする。

【００２１】請求項１０の発明は、請求項９に記載のネ
ットワーク作成装置の作成方法において、前記初期状態
のネットワークはノードのみが存在し、リンクが存在し
ない状態であり、前記記号系列が入力されるごとに前記
情報処理装置は、リンクが未接続のノードとリンクが接
続済みのノードをリンクにより接続することにより前記
抽出された記号系列のネットワークを増設することを特
徴とする。

【００２２】請求項１１の発明は、請求項１０に記載の
ネットワーク作成装置の作成方法において、前記情報処
理装置は前記抽出された記号系列の接続構造について、
前記ネットワークの接続構造と合致しない部位を検出
し、当該検出した部位を新規ネットワークとして増設す
ることを特徴とする。

【００２３】請求項１２の発明は、請求項８に記載のネ
ットワーク作成装置の作成方法において、前記ネットワ
ークは複数のノードおよび該ノードの間を結合するリン
クから構成され、記号系列の各記号を前記ノードに割り
当て隣接する記号をリンクで接続することにより該記号
系列の接続構造をネットワーク表現することを特徴とす
る。

【００２４】請求項１３の発明は、請求項８に記載のネ
ットワーク作成装置の作成方法において、前記情報処理
装置は、前記入力された記号系列の各記号にその記号位
置を示す情報を付加し、該情報を付加した該記号系列ネ
ットワークを増設し、前記入力された記号系列の中の、
前記記憶装置のネットワークの中の記号接続構造と前記
記号位置を示す情報が一致する記号系列を連想結果とし
て抽出することを特徴とする。

【００２５】請求項１４の発明は、請求項１３に記載の
ネットワーク作成装置の作成方法において、前記記号位
置を示す情報は時刻刻印であることを特徴とする。

【００２６】上述の発明では図１３に示すようにネット
ワーク作成装置に作成対象の記号系列が入力されると
（ステップＳ１０）、その中の第１番目の記号位置から
所定個数、たとえば、２つの記号系列が抽出される（ス
テップＳ２０→Ｓ３０）。抽出された記号系列の接続構
造、すなわち、接続順と同じ接続順ががこれまでに作成
したネットワークにあるか照合され、不一致部分を検出
すると（Ｓ４０→Ｓ５０）、その接続順を示すネットワ
ークを増設する（Ｓ７０）。以下、２つの記号の読み出
し開始位置を１つずらして入力記号系列について上述の
処理を繰り返す（ステップＳ２０〜Ｓ７０のループ処
理）。これにより記号系列がない初期状態のネットワー
クから記号系列が入力されるごとに新規な記号系列を増
設してネットワークを構築する。

【００２７】

【発明の実施の形態】以下、図面を参照して本発明実施
の形態を説明する。最初にネットワーク作成方法を図２
を使用して説明する。

【００２８】予め所定個数のノードを用意する。この時
点では入力の文字列がないのでノード間にリンクは張ら
れていない（図２の（１）の状態）。入力記号系列が
「ＡＢＣＣＤＥ」とする。

【００２９】本実施の形態ではリンクが２つのノード間
で接続されることに着目し、文字の先頭から、各文字先
頭とし、先頭の文字とこの後に続く記号とで構成される
２文字の記号系列を順次に入力の記号系列から取り出
す。たとえば上記入力の記号系列では「ＡＢ」が取り出
される。初期処理として先頭の記号「Ａ」についてのリ
ンク１１（図２の（２）参照）が作成される。つぎの２
つの記号すなわち「ＢＣ」が取り出されると、前の「Ａ
Ｂ」の接続関係を示すリンク１２を作成する。このと
き、記号「Ａ」から記号「Ｂ」に向かうリンクがこれま
でに作成したネットワークの中にあるかが検索される。
同一のリンクがない場合に新しいノード（この場合、番
号１のノード１３）と、記号「Ａ」に関連するノード
（この場合番号０のノード１４）とを接続するリンク１
２が作成される。

【００３０】このようにして、連続する２つの記号を取
り出し、この２つの記号の接続関係と同じリンクがある
か否かの検索を行う。同じ接続関係があれば、取り出す
２つの記号を切り替える。同じ接続関係がない場合に
は、２つの記号の先頭記号に関連するノードをネットワ
ーク中で探し、そのノードを始点とする新規リンクを作
成する。このようなネットワーク作成方法で入力記号系
列「ＡＢＣＣＤＥ」についてのネットワークを作成する
と、そのネットワークは図２の（１）の状態から（５）
の状態に変化して行く。図２の（５）のネットワークに
新規に文字列「ＡＡＢＢＢ」が与えられた場合のネット
ワークの状態の遷移を図３に示す。最初に取り出す記号
列「ＡＡ」は図３の（１）に示すように同じリンク構造
があるので、ネットワークは変化しない。新規入力の記
号系列「ＡＡＢＢＢ」の中の「ＢＢ」が取り出されたと
きこのリンク構造がないことが確認されて番号１のノー
ドから番号０のノードに向うリンクが新設される（図３
の（８）参照）。

【００３１】以上、説明したネットワーク作成方法を適
用したネットワーク作成装置を次に説明する。

【００３２】図４はネットワーク作成装置のシステム構
成を示す。図１において、ＣＰＵ１００は内蔵のシステ
ムプログラムに従ってシステム制御を行う他、後述のプ
ログラムを実行してワークメモリ１０１上にネットワー
クを作成する。

【００３３】ワークメモリ１０１は専用の記憶領域１０
１Ａ，１０１Ｂ，１０１Ｃと、一般的な情報のための記
憶領域を有する。記憶領域１０１Ａは入力バッファとし
て使用し、キーボード１０２から入力された記号系列を
一時記憶する。

【００３４】記憶領域１０１Ｂには入力バッファ１０１
Ａの中から取り出した２つの記号を記憶する。記憶領域
１０１Ｃはこれまでに作成したネットワークを変数形態
で記憶する。ネットワークはリンクの始点となるノード
番号とリンクの終点となるノード番号を有する変数（Ａ
_ij）で構成され、この変数がリンクに割当てる記号を保
持する。記憶領域１０１Ｄは上述の情報以外の情報を記
憶する。

【００３５】キーボード１０２からは、ネットワーク作
成の起動の指示やネットワーク作成の対象となる文字列
を入力する。ＣＲＴ（陰極線管表示器）１０３はキーボ
ード１０２から入力された情報やＣＰＵ１００の演算処
理結果を表示する。

【００３６】このようなシステム構成で実行されるネッ
トワーク作成処理を説明する。

【００３７】（実施形態１）キーボード１０２から入力
される入力記号系列は、例えば、図５のようにｕ（０）
ｕ（１）ｕ（２）ｕ（３）ｕ（４）ｕ（５）…ｕ（ｔ）
…であるとする。ここで、ｕ（ｔ）が１個の記号で、ｔ
が入力順序および時間を表している。入力記号系列は入
力バッファ１０１Ａに入力され、先頭から順に各記号毎
に２個ずつ記憶領域１０１Ｂにｕ（０）ｕ（１），ｕ
（１）ｕ（２），ｕ（２）ｕ（３），ｕ（３）ｕ
（４），…，ｕ（ｔ−１）ｕ（ｔ），…というように出
力される。このための処理手順は周知の文字抽出手順を
使用すればよく、詳細な説明を要しないであろう。

【００３８】この取り出した２つの記号を使用してネッ
トワークを構築するための処理プログラムを以下に示
す。ここでｉ^k ：番号付ノード（ｉ^k ∈Ｎ）Ｎ：ノード集合Ｍ：ノード数，Ｍ＝｜Ｎ｜Ｌ：１つのノードに対して許容するリンク（アーク）の
数Ａ_ij：ノードｉからノードｊに向うリンクに割当てる記
号ラベルＫ：ラベル集合，Ａ_ij∈Ｋ，φ∈Ｋ φ：ヌルｕ（ｔ）：時刻ｔに入力されるラベル

【００３９】

【外１】

【００４０】処理プログラム１は以下の通りである。

【００４１】

【外２】

【００４２】この処理プログラムでは、全ノード数Ｍの
ネットワークを対象にし、１個のノードからのリンク数
は最大でＬ本に制限している。処理プログラム１では

【００４３】

【外３】

【００４４】Loop以下で、Stopの条件が成立するまで繰
り返される。この処理プログラムでネットワークが形成
される様子を図６で具体的に説明する。ネットワークに
は０〜１２のノードが有る、つまりＮ＝０〜１２，Ｍ＝
１３とする。また、最初の状態は０だったとし、実線の
リンクは既に作成されていることを示す。さらにＬ＝５
とする。ここへ記号列：“ＡＢＣＤＥＦＧＨＩＪＫ…”
が入力された場合についての状態遷移を以下示す。

【００４５】最初に“ＡＢ”が入力バッファ１０１Ａか
ら記憶領域１０１Ｂにバッファリングされ、その１番目
の“Ａ”のラベルが貼られた番号０のノード（以下、ノ
ードを単に数字で表記する）からのリンクが有るかどう
かが最初に探される（Step-a-1-1) 。ここでは０→１の
リンクに“Ａ”が貼られており条件を満たすので、次に
バッファの２番目のラベル“Ｂ”が貼られたリンクが１
から張られているかＣＰＵ１００が記憶領域１０１上の
変数を探す。１→３のリンクと１→６のリンクに“Ｂ”
が貼られている（Step-a-1-2）。番号の若い３について
張られているリンクを数えると３→４，３→７の２本で
２≦（５−１）を満たしているのでｔに１を加え０→３
の状態遷移し（Step-b-1-2）、Loopへ戻る。

【００４６】次に“ＣＤ”がバッファリングされ、その
１番目の“Ｃ”が貼られた３からのリンクが有るかどう
かが最初に探される（Step-a-1-1) 。ここでは３→４，
３→７のリンクに“Ｃ”が貼られているので、バッファ
リンクされた２文字の中の２番目の“Ｄ”が貼られたリ
ンクが４，７に有るかを調べるが、そうしたリンクは存
在しない（Step-a-1-2）。そこで、番号の若い４につい
て張られているリンクを数えると４→ｃの１本で１≦
（５−１）を満たしているので３→４の状態遷移し（St
ep-b-1-1）、Loopへ戻る。

【００４７】次に“ＤＥ”がバッファリングされ、その
１番目の“Ｄ”が貼られた４からのリンクが有るかどう
かが最初に探されるが、そうしたリンクは存在しない
（Step-a-1-1）。そこで、４からリンクの張られないノ
ードの中で、バッファの２番目の“Ｅ”が貼られたリン
クが有るノードを探すと１，７が、１→５，７→９と
“Ｅ”の貼られたリンクを持ち、ノード１，７からのリ
ンク数には、４本より少ない（Step-a-2-1）。そこで、
番号の若い１のリンク先５について張られているリンク
を数えると５→７，５→９の２本、かつ４≠５で２＋０
≦（５−１）を満たしているので４→１に、“Ｄ”を貼
ったリンクを生成しｔに１を加え４→１→５の状態遷移
し（Step-b-2-1）、Loopへ戻る。

【００４８】次に“ＦＧ”がバッファリングされ、その
１番目の“Ｆ”が貼られた５からのリンクが有るかどう
かが最初に探されるが、そうしたリンクは存在しない
（Step-a-1-1）。そこで、５からリンクの張られていな
いノードの中で、バッファの２番目の“Ｇ”が貼られた
リンクが有るノードを探すと０が、０→２と“Ｇ”の貼
られたリンクを持ち、ノード０からのリンク数は、４本
より少ない（Step-a-2-1）。そこで、０のリンク先２に
ついて張られているリンクを数えると２→４，２→８，
４→１１の３本、かつ５≠１１で３≦（５−１）を満た
しているので５→０に、“Ｆ”を貼ったリンクを生成し
ｔに１を加え５→０→２の状態遷移し（Step-b-2-1）、
Loopへ戻る。

【００４９】次に“ＨＩ”がバッファリングされ、その
１番目の“Ｈ”が貼られた２からのリンクが有るかどう
かが最初に探される（Step-a-1-1）。ここでは２→ｔの
リンクに“Ｈ”が貼られているので、バッファの２番目
の“Ｉ”が貼られたリンクが１１に有るかを調べるが、
そうしたリンクは存在しない（Step-a-1-2）。そこで、
１１について張られているリンクを数えるとｔ→８の１
本で１≦（５−１）を満たしているので２→１１の状態
遷移し（Step-b-1-1）、Loopへ戻る。

【００５０】次に“ＩＪ”がバッファリングされ、その
１番目の“Ｉ”が貼られた１１からのリンクが有るかど
うかが最初に探されるが、そうしたリンクは存在しない
（Step-a-1-1）。そこで、１１からリンクの張られてい
ないノードの中で、バッファの２番目の“Ｊ”が貼られ
たリンクが有るノードを探すがそうしたノードは存在し
ないので（Step-a-2-1）、リンクを張っていないノード
を探すと、１２が見つかるので、１１→１２に、“Ｉ”
を貼ったリンクを生成し１１→１２の状態遷移し（Step
-a-3-1）、Loopへ戻る。

【００５１】次に“ＪＫ”がバッファリングされ、その
１番目の“Ｊ”が貼られた１２からのリンクが有るかど
うかが最初に探されるが、そうしたリンクは存在しない
（Step-a-1-1）。そこで、１２からのリンクの張られて
いないノードの中で、バッファの２番目の“Ｋ”が貼ら
れたリンクが有るノードを探すがそうしたノードは存在
しないので（Step-a-2-1）、リンクを張っていないノー
ドを探すが、空いているノードが存在しないのでStopし
（Step-a-3-1）アルゴリズムを終了する。

【００５２】上の操作により“ＡＢＣＤＥＦＧＨＩＪ”
の順で遷移するネットワークが形成されて、各ノードの
リンク数はＬ以下になっている。なお

【００５３】

【外４】

【００５４】例えば“ＤＥ”がバッファリングされたと
きには４→１にリンクが生成されるので、ノード４とノ
ード５が一致したときは、ノード５からのリンク数に１
を加える必要があるためである。

【００５５】（実施形態２）実施形態１では検索に使用
する記号数は２つであったが、この記号数を２以上とす
る実施形態２を説明する。入力記号系列は、例えば、図
７のようにｕ（０）ｕ（１）ｕ（２）…ｕ（ｎ−１）ｕ（ｎ）ｕ
（ｎ＋１）… であるとする。ここで、ｕ（ｔ）が１個の記号で、ｔが
入力順序＝時間を表している。入力記号系列は入力バッ
ファに入力され、先頭から順にｎ個ずつ記号照合器に出
力される。図７を例にすれば、 u(0)u(1), …u(n-1),u(1)u(2),…u(n),u(2)u(3),…u(n+
1), … の順に出力される。

【００５６】ネットワークは、実施形態１と同様にノー
ドとノード間を結ぶ記号が貼られたリンクから構成され
ている。ネットワーク上では各時刻に１個のノードが活
性化しており、記憶領域１０１Ｂに入力された記号とネ
ットワーク上のリンクの記号との照合結果に応じて、活
性ノードが他のノードへと移ることで状態遷移を表すも
のとする。

【００５７】入力記号列から取り出す記号数をｎとする
場合の処理プログラム２および取り出す記号数を３とす
る場合の処理プログラム３を以下に示す。

【００５８】

【外５】

【００５９】

【外６】

【００６０】

【外７】

【００６１】

【外８】

【００６２】

【外９】

【００６３】

【外１０】

【００６４】

【外１１】

【００６５】

【外１２】

【００６６】

【外１３】

【００６７】

【外１４】

【００６８】

【外１５】

【００６９】処理プログラム２および処理プログラム３
で使用している記号の定義は処理プログラム１の定義と
同一である。

【００７０】処理プログラム２および処理プログラム３
はInitializeの初期化で、

【００７１】

【外１６】

【００７２】Loop以下で、Stopの条件が成立するまで繰
り返される。

【００７３】ｎ＝３として処理プログラム３の場合につ
いて具体的に説明する。ネットワークには０〜１３のノ
ードが有る、つまりＮ＝ｉ〜ｕ，Ｍ＝１３とする。ま
た、最初の状態は０だったとし、図８の実線のリンクは
既に張られていたとする。さらにＬ＝５とする。ここへ
記号列：“ＡＢＣＤＥＦＧＨＩＪＫＬＭＮＯ…”が入力
された場合についての状態遷移を以下示す。

【００７４】最初に“ＡＢＣ”がバッファリングされ、
その１番目の“Ａ”が貼られた０からのリンクが有るか
どうかが最初に探される（Step-a-1-1) 。ここでは０→
１のリンクに“Ａ”が貼られており条件を満たすので、
次にバッファの２番目の“Ｂ”が貼られたリンクが１か
ら張られているかを探すと１→２のリンクと１→３のリ
ンクに“Ｂ”が貼られているので（Step-a-1-2）、次に
バッファの３番目の“Ｃ”が貼られたリンクが２，３か
ら張られているかを探すと３→４のリンクに“Ｃ”が貼
られているので（Step-a-1-3）、４について張られてい
るリンクを数えると４→５の１本で１≦（５−１）を満
たしているのでｔに２を加え０→１→３→４の状態遷移
し（Step-b-1-3）、Loopへ戻る。

【００７５】次に“ＤＥＦ”がバッファリングされ、そ
の１番目の“Ｄ”が貼られた４からのリンクが有るかど
うかが最初に探される（Step-a-1-1) 。ここでは４→５
のリンクに“Ｄ”が貼られており条件を満たすので、次
にバッファの２番目の“Ｅ”が貼られたリンクが５から
張られているかを探すと５→６のリンクに“Ｅ”が貼ら
れているので（Step-a-1-2）、次にバッファの３番目の
“Ｆ”が貼られたリンクが６から張られているかを探す
が、そうしたリンクは存在しない（Step-a-1-3）。そこ
で６について張られているリンクを数えると０本で０≦
（５−１）を満たしているのでｔに１を加え４→５→６
の状態遷移し（Step-b-1-2）、Loopへ戻る。

【００７６】次に“ＦＧＨ”がバッファリングされ、そ
の１番目の“Ｆ”が貼られた６からのリンクが有るかど
うかが最初に探されるが、そうしたリンクは存在しない
（Step-a-1-1) 。そこで、６からリンクの張られていな
いノードの中で、バッファの２番目の“Ｇ”が貼られた
リンクが有るノードを探すと２，７が２→１３，７→８
と“Ｇ”の貼られたリンクを持ち、ノード２，７からの
リンク数は、４本より少ない（Step-a-2-1）。次にバッ
ファの３番目の“Ｈ”が貼られたリンクが１３，８から
張られているかを探すと８→１０のリンクに“Ｈ”が貼
られている（Step-a-2-2）。そこで１０について張られ
ているリンクを数えると１本で、かつ６≠１０なので、
（０＋０）≦（５−１）を満たしているのでｔに２を加
え６→７→８→１０の状態遷移し（Step-b-2-2）、Loop
へ戻る。

【００７７】最初に“ＩＪＫ”がバッファリングされ、
その１番目の“Ｉ”が貼られた１０からのリンクが有る
かどうかが最初に探される（Step-a-1-1) 。ここでは１
０→１１のリンクに“Ｉ”が貼られており条件を満たす
ので、次にバッファの２番目の“Ｊ”が貼られたリンク
が１１から張られているかを探すが、そうしたリンクは
存在しない（Step-a-1-2）。そこで１１について張られ
ているリンクを数えると１１→７の１本で１≦（５−
１）を満たしているので１０→１１の状態遷移し（Step
-b-1-1）、Loopへ戻る。

【００７８】次に“ＪＫＬ”がバッファリングされ、そ
の１番目の“Ｊ”が貼られた１１からのリンクが有るか
どうかが最初に探されるが、そうしたリンクは存在しな
い（Step-a-1-1) 。そこで、１１からリンクの張られて
いないノードの中で、バッファの２番目の“Ｋ”が貼ら
れたリンクが有るノードを探すが、そうしたリンクは存
在しない（Step-a-2-1）。そこで、１１からリンクの張
られていないノードからリンクを張られていないノード
の中で、バッファの３番目の“Ｌ”が貼られたリンクが
有るノードを探すと５が、５→１２と“Ｌ”の貼られた
リンクを持つ（Step-a-3-1）。

【００７９】１１からリンクの張られていないノードの
候補の中で一番番号の若いのは１で、１からのリンク数
は４以下で、１からのリンクの張られていないノードの
候補の中で一番番号の若いのは５で、５からのリンク数
は４以下である。そして、１２から張られているリンク
は０本で、かつ１１≠１２，１≠１２なので、（０＋
０）≦（５−１）を満たしており、かつ１１＝１＝５で
はないので、１１→１に、“Ｊ”を貼ったリンクを生成
し、１→５に、“Ｋ”を貼ったリンクを生成し、ｔに２
を加え１１→１→５→１２の状態遷移し（Step-b-3-
1）、Loopへ戻る。

【００８０】次に“ＭＮＯ”がバッファリングされ、そ
の１番目の“Ｍ”が貼られた１２からのリンクが有るか
どうかが最初に探されるが、そうしたリンクは存在しな
い（Step-a-1-1) 。そこで、１２からリンクの張られて
いないノードの中で、バッファの２番目の“Ｎ”が貼ら
れたリンクが有るノードを探すがそうしたリンクは存在
しないので（Step-a-2-1）、１２からリンクの張られて
いないノードからリンクを張られていないノードの中
で、バッファの３番目の“Ｏ”が貼られたリンクが有る
ノードを探すが、そうしたノードは存在しない（Step-a
-3-1）。そこでリンクを張っていないノードを探すが、
空いているノードが存在しないのでStopし（Step-a-4-
1）アルゴリズムを終了する。

【００８１】上の操作により“ＡＢＣＤＥＦＧＨＩＪＫ
Ｌ”の順で遷移するネットワークが形成されて、各ノー
ドのリンク数はＬ以下になっている。なおＬ−１との比
較の際に

【００８２】

【数１】

【００８３】が加えられているのは新しく生成されるリ
ンクを足し込むためである。また

【００８４】

【数２】

【００８５】の条件は、新しく複数のリンクを生成する
場合にノードｉからノードｊへ異なったラベルの張られ
た別のリンクが生成されないための条件である。

【００８６】（実施形態３）ネットワーク連想機構に本
発明を適用した実施形態３を次に説明する。

【００８７】この機構は図４に示すコンピュータシステ
ムを使用することができるがＣＰＵ１００が実行する処
理プログラムが異なる。この処理プログラムの機能構成
を図９に示す。ネットワーク連想機構のネットワークも
ノードとノード間を結ぶリンクから構成されているが、
このリンクには記号だけでなく時間刻印が貼られる。ネ
ットワーク上では各時刻に１個のノードが活性化してお
り、記号照合器に入力された記号とネットワーク上のリ
ンクの記号との照合結果に応じて、活性ノードが他のノ
ードへと移ることで状態遷移を表す。実施形態１，２で
は入力記号系列２００が入力バッファ２０１に取り込ま
れ、所定個数の記号列についてそのリンク構造を作成済
みのネットワーク２０３に対して照合２０２を行う。実
施形態４ではさらに、入力記号が既にあるリンクを通じ
て遷移を行う場合、そのリンクの時間刻印２０４が、過
去に入力された記号系列の時間刻印と照合され、一致し
た記号列が連想される。

【００８８】このための処理プログラムは上述した処理
プログラム１や処理プログラム２を使用できる。ただ
し、Ａ_i,j と同じ大きさのＴ_i,j を定義し、リンクを通
ってノード間をｉ→ｊのように状態遷移する部分で、Ｔ
_i,j に時間刻印を張り付ける。この時間刻印を具体的に
説明する。

【００８９】まずInitializeの段階でＴ_i,j ＝φ，for
∀i,j ∈Ｎと初期化される。ここで、図８と同様に “A(0)B(1)C(2)D(3)E(4)F(5)G(6)H(7)I(8)J(9)K(10)L(1
1)M(12)N(13)O(14) …” の記号列が入力されたとする、ここで括弧内の数字は時
間刻印を表す、図１０において例えばＡ（０）は、Ａの
時間刻印が０であることを表している。以下、図８と全
く同じ手順で０→１→３→４のように状態遷移し、その
際（Step-b-1-3）で０→１のリンクにはＡ（０）が対応
しているのでＴ_0,1 ＝０と、リンクに時間刻印を張り付
ける。同様にＴ_1,3 ＝１，Ｔ_3,4 ＝２とする。以下も４
→５→６の状態遷移に対応し（Step-b-1-2）Ｔ_4,5 ＝
３，Ｔ_5,6 ＝４と、リンクに時間刻印を張り付け、６→
７→８→１０の状態遷移に対応し（Step-b-2-2）Ｔ_6,7
＝５，Ｔ_7,8 ＝６，Ｔ_8,10＝７と、リンクに時間刻印を
張り付け、１０→１１の状態遷移に対応し（Step-b-1-
1）Ｔ_10,11 ＝８と、リンクに時間刻印を張り付け、１
１→１→５→１２の状態遷移に対応し（Step-b-3-1）Ｔ
_11,1＝９，Ｔ_1,5 ＝１０，Ｔ_5,12＝１１と、リンクに時
間刻印を張り付ける。

【００９０】このように作成したネットワークに別の文
字列が“ＡＣＦＧＩＪ”が入力した場合の連想機構の動
作を図１１に示す。ノード０から遷移が開始した場合、
０→１→６→７→８→１１→１の順に遷移する。このと
きの遷移のリンクを太線で示した、但し点線は新たに生
成したリンクである。このとき、例えば“ＦＧ”に対し
ては、既にあるリンクによる遷移６→７→８が起ってい
るが、これらに対しては５，６の時間刻印が貼られてい
る。この結果を、時刻照合処理で、既に入力された “A(0)B(1)C(2)D(3)E(4)F(5)G(6)H(7)I(8)J(9)K(10)L(1
1)M(12)N(13)O(14) …” の時刻部分と比較することにより、この中からＦ（５）
Ｇ（６）が連想される。

【００９１】（実施形態４）以下に実施形態４の処理プ
ログラムおよび変数定義を示す。なお、以下で示した変
数以外の変数は上述した処理プログラムの変数と同様で
ある。

【００９２】Ｋ_i ：Ｋのｉ番目のラベル，ｋ_i ∈ＫＰ：ノード集合Ｐ_i ：Ｐのｉ番目のラベルＱ：ノードの数，Ｑ＝｜Ｐ｜Ｂ_ij：ノードｉからノードｊに向うリンクが存在しなけ
ればＢ_ij＝φ

【００９３】

【外１７】

【００９４】図１２は、図８のネットワークから作成し
たネットワークである。まず、処理プログラム４のInit
ializeで全てのリンクが初期化、クリアーされる。次
に、Set Nodes で、ネットワークのリンクに貼られてい
た記号１個に１個ずつ、１対１でノードが割り当てられ
る、図８のネットワークに対しては“ＡＢＣ…Ｌ”の１
２の記号が貼られた１２個のノードが生成される。

【００９５】以下、Make Linksで、各ノードについて、
入力リンクと出力リンクが調べられる。同一のノードに
張られた入力リンクに貼られた記号と出力リンクに貼ら
れた記号は、入力された記号系列の中で「入力リンクに
貼られた記号」→「出力リンクに貼られた記号」の順序
で実際に表れているか、またはその順序で表れる可能性
が高いと考えられるので、「入力リンクに貼られた記号
に対応するノード」→「出力リンクに貼られた記号に対
応するノード」にリンクを張る。

【００９６】例えば、図８のノード０は、入力リンクが
存在しないのでリンクを生成しない。次にノード１の
「入力リンクに貼られた記号」＝Ａ、「出力リンクに貼
られた記号」＝Ｂ，Ｋなので、Ａ→Ｂ，Ａ→Ｋに、１を
貼ったリンクを張る。次にノード２の「入力リンクに貼
られた記号」＝Ｂ、「出力リンクに貼られた記号」＝Ｇ
なので、Ｂ→Ｇに、２を貼ったリンクを張る。次にノー
ド３の「入力リンクに貼られた記号」＝Ｂ、「出力リン
クに貼られた記号」＝Ｃなので、Ｂ→Ｃに、３を貼った
リンクを張る。次にノード４の「入力リンクに貼られた
記号」＝Ｃ，Ｈ、「出力リンクに貼られた記号」＝Ｄな
ので、Ｃ→Ｄ，Ｈ→Ｄに、４を貼ったリンクを張る。

【００９７】次にノード５の「入力リンクに貼られた記
号」＝Ｄ，Ｋ、「出力リンクに貼られた記号」＝Ｅ，Ｌ
なので、Ｄ→Ｅ，Ｄ→Ｌ，Ｋ→Ｅ，Ｋ→Ｌに、５を貼っ
たリンクを張る。次にノード６の「入力リンクに貼られ
た記号」＝Ｅ、「出力リンクに貼られた記号」＝Ｆなの
で、Ｅ→Ｆに、６を貼ったリンクを張る。次にノード７
の「入力リンクに貼られた記号」＝Ｃ，Ｆ、「出力リン
クに貼られた記号」＝Ｇなので、Ｃ→Ｇ，Ｆ→Ｇに、５
を貼ったリンクを張る。次にノード８の「入力リンクに
貼られた記号」＝Ｇ、「出力リンクに貼られた記号」＝
Ｆ，Ｈなので、Ｇ→Ｆ，Ｇ→Ｈに、８を貼ったリンクを
張る。ノード９は出力リンクが存在しないのでリンクを
生成しない。次にノード１０の「入力リンクに貼られた
記号」＝Ｈ、「出力リンクに貼られた記号」＝Ｉなの
で、Ｈ→Ｉに、１０を貼ったリンクを張る。次にノード
１１の「入力リンクに貼られた記号」＝Ｉ、「出力リン
クに貼られた記号」＝Ｃ，Ｊなので、Ｉ→Ｃ，Ｉ→Ｊ
に、１１を貼ったリンクを張る。

【００９８】以上により、記号をノードとするネットワ
ークが新たに生成される。

【００９９】上述した実施形態の他に以下の形態を実施
できる。

【０１００】１）上述の実施形態ではキーボードから記
号系列を入力したが、フロッピーディスクなどの記録媒
体や通信インタフェースを介して通信により記号系列を
入力してもよい。

【０１０１】２）上述の実施形態では情報処理装置とし
てパーソナルコンピュータを使用したが、検索機能を持
ちおよび記憶装置に読み／書きできる演算処理装置を使
用することができる。ネットワークを記憶する記憶装置
とメモリに限らず、ハードディスク等周知の記憶装置を
使用できる。

【０１０２】

【発明の効果】請求項１、３、８、１０の発明によれ
ば、新規な記号系列を含む記号系列が入力されると、入
力された記号系列の中の新規な記号系列の接続構造が検
出され、既存のネットワークに増設される。この増設処
理はネットワークの初期状態から行われるので、ユーザ
は手動操作による初期設定を必要とせず、完全自動でネ
ットワーク作成が行われる。加えて、所定個数単位で新
規なネットワークの増設を行うので、上記所定個数以上
であれば入力の記号系列は個数の制限を受けない。

【０１０３】請求項２、９の発明では、記号をリンクに
割り当てたネットワークが作成されるので、リンクをノ
ード順にたどることで、入力の記号系列を復元できる。

【０１０４】請求項４、１１の発明では、既存のネット
ワークの接続構造と一致する接続構造を持つ記号系列が
入力された記号系列の中から除かれて新規な接続構造を
持つ記号系列のネットワークが増設される。

【０１０５】請求項５、１２の発明ではノードに記号を
割り当てることによりノードの順に割り当てられた記号
をたどることにより入力された記号系列を復元できる。

【０１０６】請求項６、１３の発明では記号にその記号
位置を付加したネットワークを構築し、記号の接続順だ
けでなく、記号位置による想起を行うことにより高精度
な連想機能を付加することができる。

【０１０７】請求項７、１４の発明では、記号位置に時
刻刻印を使用することで、タイマー等の簡単な装置で、
記号位置を測定できる。

【図面の簡単な説明】

【図１】ネットワーク作成方法を説明するための説明図
である。

【図２】ネットワーク作成方法を説明するための説明図
である。

【図３】ネットワーク作成方法を説明するための説明図
である。

【図４】本発明実施の形態のシステム構成を示すブロッ
ク図である。

【図５】実施の形態１の入力記号系列および抽出した記
号系列を示す説明図である。

【図６】作成されたネットワークを図形形態で示す説明
図である。

【図７】実施の形態２の入力記号系列および抽出した記
号系列を示す説明図である。

【図８】実施の形態２の作成ネットワークを示す説明図
である。

【図９】実施の形態３の処理内容を示すブロック図であ
る。

【図１０】実施の形態３の作成ネットワークを示す説明
図である。

【図１１】実施の形態３の作成ネットワークを示す説明
図である。

【図１２】実施の形態４の作成ネットワークを示す説明
図である。

【図１３】本発明の処理手順を示すフローチャートであ
る。

【符号の説明】

１００ＣＰＵ１０１ワークメモリ１０２キーボード１０３ＣＲＴ

───────────────────────────────────────────────────── フロントページの続き (72)発明者豊浦潤東京都千代田区丸の内二丁目２番３号三菱電機株式会社内

Claims

【特許請求の範囲】

【請求項１】作成すべきネットワークを記憶しておく
記憶手段と、前記作成すべきネットワークの初期状態を設定する初期
化手段と、複数の記号が連続的に結合された記号系列を入力する入
力手段と、当該入力された記号系列の中の各記号位置を先頭として
所定個数の記号系列を前記入力された記号系列から抽出
する第１の情報処理手段と、当該抽出された記号系列と同じ接続構造が前記記憶手段
のネットワークの中に存在するか否かを判定する判定手
段と、判定結果として否定判定が得られた場合には、前記ネッ
トワークに派生させて前記抽出された記号系列のネット
ワークを増設する第２情報処理手段とを具えたことを特
徴とするネットワーク作成装置。
【請求項２】請求項１に記載のネットワーク作成装置
において、前記ネットワークは複数のノードおよび該ノ
ードの間を結合するリンクから構成され、前記記号系列
の各記号を前記リンクに割り当てることにより該記号系
列の接続構造をネットワーク表現することを特徴とする
ネットワーク作成装置。
【請求項３】請求項２に記載のネットワーク作成装置
において、前記初期状態はノードのみが存在し、リンク
が存在しない状態であり、前記入力手段から記号系列が
入力されるごとに前記第２情報処理手段は、リンクが未
接続のノードとリンクが接続済みのノードをリンクによ
り接続することにより前記抽出された記号系列のネット
ワークを増設することを特徴とするネットワーク作成装
置。
【請求項４】請求項３に記載のネットワーク作成装置
において、前記第２情報処理手段は抽出された記号系列
の接続構造について、前記ネットワークの接続構造と合
致しない部位を検出し、当該検出した部位を新規ネット
ワークとして増設することを特徴とするネットワーク作
成装置。
【請求項５】請求項１に記載のネットワーク作成装置
において、前記ネットワークは複数のノードおよび該ノ
ードの間を結合するリンクから構成され、記号系列の各
記号を前記ノードに割り当て隣接する記号をリンクで接
続することにより該記号系列の接続構造をネットワーク
表現することを特徴とするネットワーク作成装置。
【請求項６】請求項１に記載のネットワーク作成装置
において、前記入力手段は前記入力された記号系列の各
記号にその記号位置を示す情報を付加し、前記第２情報
処理手段は該情報を付加した該記号系列ネットワークを
増設し、前記入力された記号系列の中の前記記憶手段の
ネットワークの中の記号接続構造と前記記号位置を示す
情報が一致する記号系列を連想結果として抽出する第３
情報処理手段をさらに具えたことを特徴とするネットワ
ーク作成装置。
【請求項７】請求項６に記載のネットワーク作成装置
において、前記記号位置を示す情報は時刻刻印であるこ
とを特徴とするネットワーク作成装置。
【請求項８】記号系列の接続構造を示すネットを作成
するネットワーク作成装置の作成方法において、初期状態のネットワークを予め記憶装置に記憶してお
き、複数の記号が連続的に結合された記号系列を入力し、当該入力された記号系列の中の各記号位置を先頭として
所定個数の記号系列を前記入力された記号系列から情報
処理装置により抽出し、当該抽出された記号系列と同じ接続構造が前記記憶手段
のネットワークの中に存在するか否かを前記情報処理装
置により判定し、判定結果として否定判定が得られた場合には、前記記憶
装置上のネットワークに派生させて前記抽出された記号
系列のネットワークを前記情報処理装置により増設する
ことを特徴とするネットワーク作成装置の作成方法。
【請求項９】請求項８に記載のネットワーク作成装置
の作成方法において、前記ネットワークは複数のノード
および該ノードの間を結合するリンクから構成され、前
記記号系列の各記号を前記リンクに割り当てることによ
り該記号系列の接続構造をネットワーク表現することを
特徴とするネットワーク作成装置の作成方法。
【請求項１０】請求項９に記載のネットワーク作成装
置の作成方法において、前記初期状態のネットワークは
ノードのみが存在し、リンクが存在しない状態であり、
前記記号系列が入力されるごとに前記情報処理装置は、
リンクが未接続のノードとリンクが接続済みのノードを
リンクにより接続することにより前記抽出された記号系
列のネットワークを増設することを特徴とするネットワ
ーク作成装置の作成方法。
【請求項１１】請求項１０に記載のネットワーク作成
装置の作成方法において、前記情報処理装置は前記抽出
された記号系列の接続構造について、前記ネットワーク
の接続構造と合致しない部位を検出し、当該検出した部
位を新規ネットワークとして増設することを特徴とする
ネットワーク作成装置の作成方法。
【請求項１２】請求項８に記載のネットワーク作成装
置の作成方法において、前記ネットワークは複数のノー
ドおよび該ノードの間を結合するリンクから構成され、
記号系列の各記号を前記ノードに割り当て隣接する記号
をリンクで接続することにより該記号系列の接続構造を
ネットワーク表現することを特徴とするネットワーク作
成装置の作成方法。
【請求項１３】請求項８に記載のネットワーク作成装
置の作成方法において、前記情報処理装置は、前記入力
された記号系列の各記号にその記号位置を示す情報を付
加し、該情報を付加した該記号系列ネットワークを増設
し、前記入力された記号系列の中の、前記記憶装置のネ
ットワークの中の記号接続構造と前記記号位置を示す情
報が一致する記号系列を連想結果として抽出することを
特徴とするネットワーク作成装置の作成方法。
【請求項１４】請求項１３に記載のネットワーク作成
装置の作成方法において、前記記号位置を示す情報は時
刻刻印であることを特徴とするネットワーク作成装置の
作成方法。