(57)【特許請求の範囲】
【請求項１】
入力ストリングのハイフネーション位置を決定するハイフネーション位置決定装置であって、
前記入力ストリングから入力記号を読み取る入力手段と、
前記入力手段に連結され、初期状態、現行状態、及び状態遷移データ構造によって特徴付けられ、該現行状態が前記入力ストリングの少なくとも一つの入力記号及び該状態遷移データ構造の遷移によって決定され、該状態遷移データ構造は、単一レベルのハイフネーション規則を符号化し、該単一レベルのハイフネーション規則の各ハイフネーション規則は、パターンを規定する規則であり、かつ該パターンに関して、少なくとも一つの許されたハイフン位置または少なくとも一つの許されたハイフン位置及び少なくとも一つの禁止されたハイフン位置を規定する有限状態機械と、
前記有限状態記載に連結され、前記入力ストリングのハイフネーション位置を指示するハイフネーション指示手段とを備え、前記ハイフネーション位置は、前記状態遷移データ構造によって符号化された前記単一レベルのハイフネーション規則によって規定された前記パターンによって制御されることを特徴とするハイフネーション位置決定装置。
【請求項２】
前記単一レベルのハイフネーション規則は、無限の数のストリングに適用可能な少なくとも一つの規則を備えていることを特徴とする請求項１に記載のハイフネーション位置決定装置。
【請求項３】
前記単一レベルのハイフネーション規則は、その他の規則によって扱われない有限の数のストリングに適用可能な少なくとも一つの規則を更に備えていることを特徴とする請求項２に記載のハイフネーション位置決定装置。
【請求項４】
前記単一レベルのハイフネーション規則は、その他の規則によって扱われない有限の数のストリングに適用可能な少なくとも一つの規則を更に備え、否定規則は、当該否定規則を含んでいる該その他の規則が該有限の数のストリングのハイフネーションを扱わないように該その他の規則に追加されることを特徴とする請求項２に記載のハイフネーション位置決定装置。
【請求項５】
前記入力ストリングは、言語の単語であることを特徴とする請求項１に記載のハイフネーション位置決定装置。
【請求項６】
前記言語は、英語であることを特徴とする請求項５に記載のハイフネーション位置決定装置。
【請求項７】
前記言語は、フィンランド語であることを特徴とする請求項５に記載のハイフネーション位置決定装置。
【請求項８】
前記入力ストリングは、文書処理プログラムにより用いられる文書の単語であり、かつ前記ハイフネーション指示手段は、該文書処理プログラムのラインブレーク位置決定プロセッサに連結されることを特徴とする請求項１に記載のハイフネーション位置決定装置。
【請求項９】
前記ハイフネーション指示手段は、ハイフネーション位置にハイフンが散在する前記入力ストリングから記号を含んでいるストリングを出力することを特徴とする請求項１に記載のハイフネーション位置決定装置。
【請求項１０】
前記入力ストリングは、少なくとも一つの提案されたハイフネーション位置に少なくとも一つのハイフンを含み、かつ前記ハイフネーション指示手段は、該提案されたハイフネーション位置が前記単一レベルのハイフネーション規則に従うか否かを指示することを特徴とする請求項１に記載のハイフネーション位置決定装置。
【請求項１１】
前記状態遷移データ構造は、前記データ構造への前記単一のハイフネーション規則の自動コンパイルによって生成されたデータ構造であることを特徴とする請求項１に記載のハイフネーション位置決定装置。
【請求項１２】
前記状態遷移データ構造は、前記データ構造への前記単一のハイフネーション規則の手動コンパイルによって生成されたデータ構造であることを特徴とする請求項１に記載のハイフネーション位置決定装置。
【請求項１３】
入力ストリングにハイフンを付す方法であって、
単一のハイフネーション規則を状態遷移構造にコンパイルし、該単一のハイフネーション規則のそれぞれが、前記各ハイフネーション規則に関連付けられたパターンに対してハイフネーション位置を符号化し、前記ハイフネーション規則は、そのパターンにおける少なくとも一つの許されたハイフン位置または許されたハイフン位置及び禁止されたハイフン位置を指示し、前記単一レベルのハイフネーション規則の少なくとも一つは、入力ストリングの非束縛の組にマップするパターンに対して少なくとも一つのハイフン位置を符号化し、
前記状態遷移構造により有限状態機械をプログラミングし、
前記有限状態機械を初期状態にリセットし、
前記入力ストリングの記号及び前記状態遷移構造により前記有限状態機械の少なくとも一つの現行状態を変更し、かつ
前記変更段階で生じた一つの状態から別の状態への遷移によりハイフン位置指示を出力する段階を具備することを特徴とする方法。
【請求項１４】
前記ハイフン位置指示を出力する段階は、ハイフン位置にハイフンが散在する前記入力ストリングの前記記号を出力する段階を更に具備することを特徴とする請求項１３に記載の方法。
【請求項１５】
前記入力ストリングは、提案されたハイフン位置に少なくとも一つのハイフンを備え、
前記ハイフン位置指示を出力する段階は、該提案されたハイフン位置が該入力ストリングについてのハイフン位置に対応するかまたは該提案されたハイフン位置が該入力ストリングに対して該ハイフン位置に対応しないかのいずれかを示す対応指示を出力する段階を更に具備することを特徴とする請求項１３に記載の方法。
【請求項１６】
単一レベルのハイフネーション規則を生成し、該単一レベルのハイフネーション規則の少なくとも一つは、入力ストリングの非束縛の組にマップするパターンに対して少なくとも一つのハイフン位置を符号化し、該単一レベルのハイフネーション規則の各ハイフネーション規則は、各ハイフネーション規則によって動作される一つ組の可能な入力ストリングに対して有効出力ストリングを規定し、
前記単一のハイフネーション規則から前記パターンに対応している状態遷移構造を生成し、該状態遷移構造は、現行状態から次の状態への複数の遷移のどれが入力ストリングの特定の記号の入力に続いて行なわれるかを指示しているデータを備え、該データはまた前記入力ストリングのハイフン位置も指示し、かつ
有限状態プロセッサを前記状態遷移構造に連結し、それにより入力ストリングが前記一組の可能な入力ストリングのストリングである場合に前記有効出力ストリングから選択された出力ストリングだけを出力する有限状態機械を形成する段階を具備することを特徴とする、有限状態機械を生成する方法。
【請求項１７】
一組の入力ストリングから選択された入力ストリングにハイフンを付す方法であり、ストリングは記号の順序付けられた配列でありかつ該一組の入力ストリングは該組が入力ストリングの所定の固定リストに列挙することが実行可能であるよりも多くの入力ストリングを含むということで非束縛である、該方法であって、
単一レベルのハイフネーション規則を識別し、該単一レベルのハイフネーション規則のハイフネーション規則は、ハイフネーション規則に関連付けられた記号のパターンに対して少なくとも一つの許されたハイフン位置または少なくとも一つの許されたハイフン位置及び少なくとも一つの禁止されたハイフン位置を示す段階と、
前記単一レベルのハイフネーション規則を状態遷移構造にコンパイルする段階と、
前記状態遷移構造により有限状態機械をプログラミングする段階と、
前記有限状態機械を初期状態にリセットする段階と、
記号ポインタを前記入力ストリングの現行記号にセットする段階と、
マッチング遷移またはヌル遷移のいずれかにより前記有限状態機械の現行状態を変更し、かつマッチング遷移は前記入力ストリングの現行記号に等しい入力記号による遷移でありかつヌル遷移はヌル記号に等しい入力記号による遷移であり、それにより入力ストリングの記号へのハイフネーション規則の記号のパターンのマッピングに影響を与える段階と、
マッチング遷移が実行されるときに前記現行記号ポインタを増分する段階と、
終了状態に達するまで前記変更する段階及び前記増分する段階を繰り返す段階と、及び
前記変更する段階で実行された遷移により少なくとも一つのハイフン位置指示装置を出力する段階と
を具備することを特徴とする方法。
【請求項１８】
現行入力記号に対する有効遷移を有していない状態に達したときまたは有限状態機械が前記入力ストリングの最終記号に対して実行された遷移の後で非最終状態にあるときに前記現行記号ポインタを減少する段階を更に具備することを特徴とする請求項１７に記載の方法。
【請求項１９】
前記単一レベルのハイフネーション規則は、許されたハイフネーション位置を示している複数の規則及び禁止されたハイフネーション位置を示している複数の規則を含む状態遷移構造にコンパイルされることを特徴とする請求項１７に記載の方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、有限状態機械（ＦＳＭｓ）及び有限状態変換器（ＦＳＴｓ）の分野に関する。より特定的には、文字のハイフンが付いていないストリングからハイフンで結んだストリングを発生しかつ適当なハイフネーションについてハイフンで結んだストリングを試験する有限状態変換器に関する。
【０００２】
【従来の技術】
“Ｃｏｍｐａｃｔ  Ｈｙｐｈｅｎａｔｉｏｎ  Ｐｏｉｎｔ  Ｄａｔａ”と題する米国特許出願第０７／７３９，７９８号は、単語についてのハイフネーションの一覧表により単語にハイフンを付けるためのＦＳＴｓの使用を記載している。それには、ハイフネーションＦＳＴの動作を示す指向グラフが示されている。
外見上、ＦＳＭは、記号のストリングを包含している入力テープを読込み、かストリングがＦＳＭによって許容されるストリングの組であるかどうかを決定すす機械として考えることができる。例えば、ストリングの組は、辞書における単語であり得、その場合に入力ストリングは、適当な綴りについて検査される単語であり得、入力記号は、アルファベットの文字（ｌｅｔｔｅｒ）（語内句読点を可能的に含んでおり）、そしてＦＳＭは、辞書における単語のそれぞれを許容する。辞書の単語は、ＦＳＭの動作を規定するデータ構造に一般的に符号化される。単語の一覧表をそのようなＦＳＭデータ構造に変形する処理は、“Ｅｎｃｏｄｉｎｇ  ＦＳＭ  Ｄａｔａ  Ｓｔｒｕｃｔｕｒｅｓ”と題された米国特許出願第０７／７３９，７９８号及び米国特許出願第０７／８５５，１２９号に記載されている。
【０００３】
ＦＳＭは、有限状態機械なので、その動作は、その一つが初期状態である有限数の状態、及び現行状態から次の状態への遷移を記述しかつどの状態が最終状態であるかを示しているデータ構造によって記述されうる。ＦＳＭの動作は、しばしば有向グラフによって示される。この有向グラフは、円で表される状態、遷移の方向を示している矢頭を有するアーク（弧）で表される遷移、及び遷移アークとして区分される（それらの）遷移に導くテープ記号からなる。初期状態は、慣例により０または１に区分され、最終状態は、円内の円により示される。テープ記号は、通常、しかし必ずしもそうである必要はないが、読み取られる入力ストリングの英文等の文字（ｌｅｔｔｅｒ）または句読文字である。
次に、ＦＳＭの動作は、初期状態に等しい現行状態で始まり、入力ストリングの第１の記号を読み取り、その区分に第１の記号を含む遷移を用いて、もし可能ならば初期状態から新たな状態に移る機械として、有向グラフに関して記述しうる。続いて、ＦＳＭは、入力ストリングの次の記号に移り、入力ストリングの各後続の記号について処理を繰り返す。全ストリングを読み取った後、もしＦＳＭが初期状態であるならば、入力ストリングは、ＦＳＭによって許容されるストリングの組にあると言える。さもなくば、そうとは言えない。入力ストリングは、一度に一つの記号が読み取られるので、入力ストリングは、ＦＳＭに送り込まれたテープとして考えられうる。確定的ＦＳＭにおいて、各状態から所与の入力記号について多くて一つの遷移が存在する。非確定的ＦＳＭにおいて、ある状態は、所与の入力記号について一つ以上の遷移を有しうる。また、あるＦＳＭｓにおいて、空文字（ヌル文字）は、入力ストリングから読み取りうる。効果として、遷移は取られるが、入力テープを進めない；これは、標識“０”によって指定される。
【０００４】
有限状態変換器（ＦＳＴ）は、ＦＳＴがストリングの対を受け入れるかまたは拒否する点を除いて、ＦＳＭに類似している。当然のこととなる理由について、これらは、しばしば入力テープまたはストリング、及び出力テープまたはストリングと呼ばれている。ＦＳＴも有向グラフによって記述されうるが、各遷移が入力記号及び出力記号対によって区分されるもの（有向グラフ）による。
あるＦＳＴｓの使用は、Ｌ．  Ｋａｒｔｔｕｎｅｎ，  Ｆｉｎｉｔｅ−Ｓｔａｔｅ  Ｃｏｎｓｔｒａｉｎｔｓ，  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｕｒｒｅｎｔ  Ｉｓｓｕｅｓ  ｉｎ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｌｉｎｇｕｉｓｔｉｃｓ，  Ｊｕｎｅ  １０−１４，  １９９１  で論ぜられている。ＦＳＴは、受け入れられるべき入力−出力ストリング対の組を指定する規則の組を実行するために用いうる。これらの対は、例えば、互いに対になった単語の単数及び複数形でありうる。
米国特許出願第０７／７３９，７９８号に記述されたＦＳＴは、単語についてのハイフネーション点及びハイフンで結ばれた単語のハイフンの正当性を決定するために用いられる。上記で用いられた用語において、入力ストリングは、検査されるべき単語であり、出力ストリングは、適当なハイフネーション点に埋め込まれたハイフンを有する単語である。受け入れられたストリング対の組は、それぞれが基本語及びハイフンで結んだ単語からなるストリング対の組である。
【０００５】
一つの応用において、挿入されたハイフンを有する単語は、ＦＳＴによって検査される。入力テープは、ハイフンなしの単語であり、出力テープは、ハイフンを有する単語である。もしＦＳＴが、その単語及び単語のその特定のハイフネーションを受け入れるべく符号化されるならば、それは受け入れられる。別の応用において、単語は、ＦＳＴへの入力であり、そしてＦＳＴは、ハイフンによって示されたハイフネーション点を有する単語である出力ストリングを示す。もし一つ以上のハイフネーションが受け入れられるならば、一つ以上の出力ストリングが示される。
以下、ＦＳＴの一例を図１を参照して説明する。図１は、ハイフネーションＦＳＴの状態及び遷移を表している有向グラフ１０である。有向グラフ１０において、一つの状態から別の状態への各遷移は、指向性アークによって示される、そして遷移の原因となる入力−出力記号対によって区分される。例えば、もしＦＳＴが状態１であるならば、そして入力記号及び出力記号が両方とも“Ｄ”ならば、状態２への遷移が行われる。ＦＳＴにおいて、遷移の標識は、記号対であり、入力記号、コロン、及び出力記号として書かれる（即ち、“Ｄ：Ｄ”）。速記表記法において、もし入力及び出力記号が同じであれば、標識は、状態２及び３の間で“Ｒ”と区分された遷移のように、単一の記号として示される。標識“Ｄ：Ｄ”は、“Ｄ”に短縮されうるが、説明のために完全な表記で残された。ＦＳＴでは要求されないけれども、指向グラフ１０は、ほとんどの記号対が入力ストリングの特性を出力ストリングの同じ特性に適合させることを示す。単語がハイフンで結ばれる場合、単語の文字は変わらないので、これはハイフネーションＦＳＴにおいて一般に期待されることである。
【０００６】
ある記号及びある状態に関して、遷移が存在せず、指向グラフ１０を用いているＦＳＴのように、記号“Ｄ”以外に状態１からの遷移が存在しない。それゆえに、“Ｄ”で始まっていない単語は、ＦＳＴによって受け入れられない。表１は、指向グラフ１０によって表されるＦＳＴによって受け入れられた入力−出力対を示す。
【０００７】
【表１】
0003599775.tif 000002
最終状態及び遷移の配置により、上記対のみがＦＳＴによって受け入れられる。図１において、上述したように、記号“０”（空記号）は入力ストリングから読み込まれ、かつ“−”は出力ストリングから読み込まれることを示す“０：−”と区分された遷移のような、空記号（ヌル記号）を示すために用いられる。空記号は、記号を読み込まないこと及びテープを進行させないことに等しい。
【０００８】
ＦＳＴを用いる方法は、二つある。一つの応用において、出力ストリングは、知られており、入力及び出力ストリングは、一度に一つの記号を読み込み、入力及び出力テープを進行させ（空記号が読み込まれたときを除く）、そして受け入れられたあらゆる遷移を取る。別の応用において、出力ストリングは、知られておらず、入力ストリングは、読み込まれ、そして、取られた遷移の経路（ｐａｔｈ）に沿って出会った出力記号は、出力される。
【０００９】
【発明が解決しようとする課題】
しかしながら、図１に示す指向グラフから明らかなように、ハイフネーションＦＳＴは、表１の入力欄（ｃｏｌｕｍｎ）の単語の有限一覧表（ｆｉｎｉｔｅ  ｌｉｓｔ  ）についてのハイフンで結ばれた出力ストリングを提供するだけである。対（ｈｅｌｌｏ，  ｈｅｌｌ−ｏ  ）は、有向なハイフネーションを示しうるけれども、唯一の有効な遷移は、Ｄ：Ｄであり、ＦＳＴは、状態１でブロックされうるので、ＦＳＴによって受け入れられる対ではありえない。“ｈ”で始まっている入力ストリングについて、初期状態から最終状態まで有向グラフ１０を貫通する経路は、不可能なので、対（ｈｅｌｌｏ，  ｈｅｌｌ−ｏ  ）は、ＦＳＴによって拒否される。
表１の小さな一覧表は、実用的なハイフネーション機械について有用ではないけれども、単語の更に大きな一覧表が、ＦＳＴの状態遷移構造に符号化されうる。しかしながら、大きな数の単語及びハイフネーション対を受け入れているＦＳＴでも、ＦＳＭ構造を符号化することにより多数の問題が発生しうるので、ワードプロセッサ（文書処理装置）に組み込まれうるような、英単語をハイフンで結ぶハイフネーション機械を必要とする応用では受け入れられない。第１に、有効な単語の網羅的かつ決定的な一覧表が存在せず、新しい単語が毎日創作されている。第２に、基本の単語の連結を介して単語が使用者によって創作されるドイツ語やフィンランド語のような、他の言語における応用に関して、単語一覧表は、潜在的に無限であり、予め知られていない。
【００１０】
必要なのは、予め知られていることを必要としない潜在的に無限な単語の一覧表を、ハイフネーション検査及びハイフネーション生成のためのＦＳＴ構造の中に、符号化する手段である。
本発明の目的は、上記従来のハイフネーションＦＳＴにおける問題点に鑑み、ハイフネーション検査及びハイフネーション生成のためのＦＳＴ構造の中に予め知られていることを必要としない潜在的に無限な単語の一覧表を符号化する手段を備えるハイフネーション規則に関する有限状態符号化システムを提供することにある。
【００１１】
【課題を解決するための手段】
上述した本発明の目的は、入力ストリングから入力記号を読み取る入力手段と、入力手段に連結され、初期状態、現行状態、及び状態遷移データ構造によって特徴付けられ、現行状態が入力ストリングの少なくとも一つの入力記号及び状態遷移データ構造の遷移によって決定され、状態遷移データ構造がハイフネーション規則の組によって決定される有限状態機械と、有限状態機械に連結され、入力ストリングのハイフネーション位置を指示し、ハイフネーションが有限状態機械の状態遷移によって決定されるハイフネーション指示手段とを備え、ハイフネーション位置がハイフネーション規則の組に従うハイフネーション位置決定装置によって達成される。
本発明におけるハイフネーション規則の組は、無限数のストリングに適用可能な少なくとも一つの規則を備えることが好ましい。
本発明におけるハイフネーション規則の組は、更に、他の規則によって扱われない有限数のストリングに適用可能な少なくとも一つの規則を備えることが好ましい。
【００１２】
本発明におけるハイフネーション規則の組は、更に、他の規則によって扱われない有限数のストリングに適用可能な少なくとも一つの規則を備え、他の規則に否定規則が付け加えられ、否定規則を含んでいる他の規則は、有限数のストリングのハイフネーションを扱わないことが好ましい。
本発明における入力ストリングは、言語の単語であることが好ましい。
本発明における言語は、英語であることが好ましい。
本発明における言語は、フィンランド語であってもよい。
本発明における入力ストリングは、文書処理プログラムで用いられる文書の単語であり、ハイフネーション標識は、文書処理プログラムのラインブレーク位置決定プロセッサに連結されてもよい。
本発明におけるハイフネーション標識は、ハイフネーション位置にハイフンが散在する入力ストリングから記号を包含しているストリングを出力するように構成してもよい。
本発明における入力ストリングは、少なくとも一つの提案されたハイフネーション位置に少なくとも一つのハイフンを含み、ハイフネーション標識は、提案されたハイフネーション位置がハイフネーション規則の組に従うか否かを示すことが好ましい。
【００１３】
本発明における状態遷移データ構造は、データ構造へのハイフネーション規則の組の自動コンパイルによって生成されたデータ構造であることが好ましい。
本発明における状態遷移データ構造は、データ構造へのハイフネーション規則の組の手動コンパイルによって生成されたデータ構造であってもよい。
上述した本発明の目的は、状態遷移構造にハイフネーション規則の組をコンパイルし、ハイフネーション規則のそれぞれが、表現に対応付けられた基準の組に適合するストリングの少なくとも一つの許されたハイフン位置または禁止されたハイフン位置を示す表現によって特徴付けられ、少なくともハイフネーション規則の一つが入力ストリングの非束縛な組についての少なくとも一つのハイフン位置を符号化し、状態遷移構造により有限状態機械をプログラミングし、有限状態機械を初期状態にリセットし、入力ストリングの記号及び状態遷移構造により有限状態機械の少なくとも一つの現行状態を変更し、変更段階で生じた一つの状態から別の状態への遷移によりハイフン位置標識を出力する段階を具備する入力ストリングをハイフン付けする方法によっても達成される。
本発明におけるハイフン位置標識を出力する段階は、更に、ハイフン位置にハイフンが散在する入力ストリングの記号を出力する段階を具備することが好ましい。
【００１４】
本発明における入力ストリングは、提案されたハイフン位置に少なくとも一つのハイフンを備え、ハイフン位置標識を出力する段階は、更に、提案されたハイフン位置が入力ストリングについてのハイフン位置に対応するか否かの標識を出力する段階を具備することが好ましい。
上記方法によって出力ストリングが生成されてもよい。
上述した本発明の目的は、ハイフネーション規則の組を生成し、少なくともハイフネーション規則の一つが入力ストリングの非束縛な組についての少なくとも一つのハイフン位置を符号化し、ハイフネーション規則のリストに対応する状態遷移構造を発生し、状態遷移構造が、入力ストリングの特定の記号の入力に続いて現行状態から次に状態への複数の遷移のいずれが取られるかを示すデータを備えており、データが該入力ストリングのハイフン位置をも示し、状態遷移構造により該有限状態機械をプログラミングする段階を具備する方法によって発生した有限状態機械によっても達成される。
【００１５】
【作用】
本発明によるハイフネーションＦＳＴの一つの実施例において、単語は、制約のない単語の組についての状態遷移図符号化ハイフネーション規則を有するＦＳＴに入力され、ＦＳＴは、受け入れられたハイフンの位置を示す。ＦＳＴの状態遷移構造は、制約のない単語の組に適用される規則、及び一つ以上の単語の有限の組に適用される規則を含むハイフネーション規則の組を表わす。ＦＳＭ状態遷移構造は、サブストリングのどこにハイフンが入るかを示しているハイフネーション規則の組からコンパイルまたは生成される。一度、ハイフネーション規則の組が有向グラフに変換されたならば、有向グラフは、米国特許出願第０７／８５５，１２９号に教示されているように、コンパクト符号化形式でアクセスできる。コンパクト符号化形式は、その間の状態及び遷移で実施された多数の規則を符号化するための一つの手段を提供する。しかしながら、有向グラフの状態及び遷移を記憶するあらゆる手段が本願発明に作用するので、コンパクト符号化形式は本願の発明に必要ない。
ハイフネーション規則が無限に多くのストリングに適用できるので、対応するＦＳＴは、状態遷移の環状に囲んでいるパスを有する。
【００１６】
本願発明によるハイフネーションＦＳＭの一つの実施例において、有向グラフは、機械可読状態及び遷移データとしてメモリに記憶され、ストリングプロセッサは、入力ストリングを状態及び遷移データに適用する。入力ストリングの適用の結果は、入力ストリング及び受け入れ可能なハイフンポイントを反映している出力ストリングか或いは入力ストリングのハイフンが正確に配置されたかどうかを示す標識のいずれかである。
本願発明の性質及び利点の更なる理解は、他の明細書の部分及び添付された図面を参照することによって認識されうる。
【００１７】
【実施例】
以下、添付した図面を参照して、本発明のハイフネーション規則に関する有限状態符号化システムの実施例を説明する。
図２は、ハイフネーションＦＳＴ（図３参照）の有向グラフ２０を示す。有向グラフ２０は、この例について選択された、ハイフン配置の任意の規則について符号化する：ハイフンは、ハイフンが最初の二文字の前でないならば、サブストリング“ＰＥ”の前及びサブストリング“ＩＮＧ”の前でストリングに位置付けられる。正式に言うならば、ＦＳＴは、許された位置で出力ストリングに加えられたハイフンを除いて、出力ストリングが入力ストリングと同じであるような全ての入力−出力ストリング対を受け入れる。表２は、ハイフン配置の規則の形式的表現を示す。
【００１８】
【表２】
0003599775.tif 000003
この規則の形式的表現は、ゼロックスによって創作された、二段階規則コンパイラーにより用いられる。「アルファベット」部分は、ＦＳＴで用いられる入力：出力記号対を列挙する。アルファベットにおける最初の記号対は、“ａ：ａ”であり、“ａ”と短縮される。この記号対は、“ａ”の入力記号及び“ａ”の出力記号を示す。最後の対“０：％−”は、空（ヌル）入力及びハイフン出力文字の記号対である（“％”は、“−”が制御文字でないことを示すために用いれる）。
【００１９】
「組」部分は、組Ｌｔｒの全てのメンバー（これらは記号対でもある）を簡潔に参照すべく用いられる、組Ｌｔｒ  の構成要素を列挙する。「規則」部分は、二重引用符（“  ”）における規則名及び感嘆符（！）で先行された注釈を伴って、規則それ自体を列挙する。
規則は、英語についての適当なハイフネーション規則を反映していないが、しかし例の明晰さのため及び、本発明は、これら英語や他の言語だけでなく任意のハイフネーション規則のいずれの組に対しても適用可能であることを示すために選択された。例えば、規則２は、英語における“ｉｎｇ”の尾部についての適当な規則ではない。有向グラフ１０（図１参照）が“ｉｎｇ”の尾部を適当に符号化するが、それは、三つの単語：ｄｉｐｐｉｎｇ，  ｄｒｉｐｐｉｎｇ，及びｄｒｏｐｐｉｎｇだけについてである。例から明らかなように、有向グラフ２０は、入力ストリングの潜在的に無限の組を符号化する。有向グラフ２０を用いているＦＳＴへの入力ストリングは、後述の例で示すように、どの言語における有効な単語である必要さえない。規則に基づいたハイフネーションＦＳＴは、長い単語が基本単語を互いに連結することによって創作されるフィンランド語やドイツ語のような言語において特に有用である。基本単語を結合する全ての異なる方法の事前指定を要求する単語−一覧表指向ＦＳＴに対抗して、規則に基づいたシステムでは、基本単語についての規則のみが符号化される必要がある。
【００２０】
表３は、有向グラフ２０の代替え表現である、二段階規則コンパイラーによって生成された状態−遷移データ構造を示す。
【００２１】
【表３】
0003599775.tif 000004
表３において、現行状態は、最終状態に対して“：”及び非最終状態に対して“．”を伴って、左側のコラム（列）に列挙されている。コラム（列）は、記号対により見出し付けされ、所与の記号対についての所与の状態からの遷移は、記号コラム（列）及び状態ロー（行）の交差点での状態数によって示されている。例えば、表３は、状態４が最終状態であることを示し、かつもしＦＳＴが記号対“ｉ”（ｉ：ｉ）を読み込むならば、ＦＳＴの現行状態が状態４から状態９に変更すべきであることを示す。文字（ｃｈａｒａｃｔｅｒ  ）＃は、単語の開始の標識であり、コラム＃：０は、単語の開始での遷移を示す。：０なので、入力ストリングの＃は、出力ストリングに繰り越さない。
【００２２】
表３は、現行状態が知られており、かつ遷移された状態が、入力−出力記号対についてのコラム（列）のもとでその現行状態について列挙されているので、示された状態−遷移図により符号化されたＦＳＴの作用（ａｃｔｉｏｎ）を決定するのに用いることができる。この例の平易さから、記号対の多くは、同一挙動の原因となる。例えば、記号対ａ：ａ及びｂ：ｂは、規則に示されていないので、それらは、ことなるように取り扱われておらず、従って、これら二つの対のコラム（列）は、同等である。表３の表示を簡略化するために、同値クラスが用いられる。特定の同値クラスは、表３の下部に列挙してある。第１の同値クラスは、全てのしかしアルファベットの五つの文字を含んでおり、かつ同値クラスの最初の文字によって識別される−−それゆえに、“ａ”とレッテルを付けられたコラム（列）は、列挙された同値クラスにおける他の記号対のいずれか一つに対応付けられた遷移を決定するために用いられるべきである。所与の記号対についての状態から遷移が許されないならば、表３におけるそのエントリー（入力）は、空白のままに残しておく。例えば、現行の状態が状態５であるならば、記号対ｅ：ｅについて遷移は、許されない。
【００２３】
図２は、表３の状態−遷移図を反映している有向グラフ２０を示している。上記したように、レッテル“ａ”は、同値クラス“ａ”における各記号対についての遷移を網羅（カバー）する。
入力ストリング“ｄｉｐｐｅｄ”を有する有向グラフ２０を用いているＦＳＴの動作について説明する。ＦＳＴは、状態１で開始（スタート）し、そして“＃”単語マーカーの始まりである、入力ストリングの最初の文字を読み取る。入力記号“＃”についての唯一の可能な遷移は、状態１から状態２へである。出力ストリングは、もしそれが読み出されたならば、前に進められない、そしてもしそれがＦＳＴによって出力されるならば、状態１から状態２への遷移の“＃：０”レッテルによって示されているように、それ（出力ストリング）は、記号を含んでいない。
状態２において、ＦＳＴは、次の入力記号、“ｄ”（それは要求されてはいないけれども、この例では解釈不感性が想定されている）を読み込む。唯一の可能な遷移は、状態２から状態３へである。“ｄ”とレッテルを付けられた遷移は明白に示されていないが、“ｄ”は同値クラス“ａ”の中なので、“ａ”とレッテルを付けられた遷移（状態１から状態２ヘ）が取られる。
【００２４】
第２の文字、“ｉ”、を読み取るために、ＦＳＴは、状態３から状態４への遷移を取る。
第３の文字、“ｐ”、を読み取るために、ＦＳＴは、状態４から状態１０への遷移、または状態４から状態５への遷移、入力ストリングから“ｐ”を使い切らない、そして次に状態６へ、“ｐ”を使う、が可能である。有向グラフ２０は、確定的なＦＳＴであるけれども、二つの可能な経路（パス：ｐａｔｈｓ  ）が状態４で利用可能である。異なる可能な経路の記録を辿るために、許された経路は、それらが通過する「状態」（ｔｈｅ  ｓｔａｔｅｓ）によって識別される。それゆえに、第３の文字を読み取った後、入力ストリングについて許された経路は、１−２−３−４−１０、または１−２−３−４−５−６で始まらなければならない。
第４の文字、“ｐ”、を読み取るために、１−２−３−４−５−６の経路は、ブロックされる、それは状態６からの“ｐ”の遷移が存在しないからであり、それゆえに１−２−３−４−１０の経路が唯一の実行可能な選択である。状態１０から、状態５への遷移は、唯一の許された遷移であり、状態６への遷移を伴う。この時点において、唯一の許された経路は、１−２−３−４−１０−５−６で始まる。
【００２５】
現行状態が状態６である間に、第５の文字、“ｅ”は、読み取られ、そして
許される遷移は、状態４へである。
第６のかつ最後の文字、“ｄ”、を読み取るために、状態４からそれ自体への遷移及び状態５への遷移を取る。しかしながら、状態５への遷移は、文字を使い果たさず、かつ“ｄ”についての状態５からの遷移は存在しないので、その経路は許されない。それゆえに、入力ストリング“ｄｉｐｐｅｄ”についての唯一の許される最後の経路は、１−２−３−４−１０−５−６−４−４である。状態４は、最終状態なので、この経路は、ＦＳＴで受け入れられる経路である。出力は、もし知られていないならば、経路をもどりかつ各遷移のレッテルの出力記号部分を調べることによって見出すことができる。この場合、経路についての出力記号は、次のようである（出力記号は括弧内）：
１（０）２（ｄ）３（ｉ）４（ｐ）１０（−）５（ｐ）６（ｅ）４（ｄ）４
換言すれば、入力ストリング“ｄｉｐｐｅｄ”を包含している唯一の入力−出力ストリング対は、ストリング対（ｄｉｐｐｅｄ，ｄｉｐ−ｐｅｄ）である。
勿論、もし出力ストリングが予め知られているならば、可能な出力記号を読み取ることは、経路を延長することの追加の必要条件でありうる。例えば、入力−出力ストリング対（ｄｉｐｐｅｄ，ｄｉｐ−ｐｅｄ）は、ＦＳＴによって受け入れられるべきではない。ＦＳＴが状態３でブロックし、記号対“ｉ：ｅ”について遷移が存在せず、そして代替え経路が存在しなゆえに、この対の記号について経路が存在しないので、この対の非受入は、図２から自明である。
【００２６】
状態４から状態１０，５，６，そして状態４に戻っるような、有向グラフ２０におけるループのために、無限の数のストリング対が受け入れられる。例えば、（ｄｉｐｐｅｄ，ｄｉｐ−ｐｅｄ）は、経路１−２−３−４−１０−５−６−４−１０−５−６−４がそのストリング対について許され、そしてそれが最終状態で終わるので、明らかに受け入れられる。
多くの他の入力ストリングは、有向グラフ２０を用いているＦＳＴによって受け入れられる。それらの中には、例えば、任意の入力ストリング“ｃｌｅｐｅｌｉｎｇｓ”を含んでおり、これは、有向グラフ２０を用いているＦＳＴによって処理されうるストリングがいかに所定の単語に限定されていないかを示す。
ＦＳＴは、状態１で開始し、前回の例のように、状態１から状態２への遷移を取り、入力ストリングの最初の文字“ｃ”を読み込む。“ｃ”は、同類クラス“ａ”なので、唯一の許される経路は、状態２から状態３への“ａ”とレッテルを付された遷移を有するそれである。第２の文字、“ｌ”、これも同類クラス“ａ”である、を読み取るために、唯一の許される経路は、状態３から状態４への遷移を含む。
【００２７】
第３の文字、“ｅ”については、二つの経路が許される。状態４から、状態４自体への遷移が許され、そして状態５への遷移が許される。しかしながら、状態５への経路についての入力記号は、ヌル（ゼロ）であり、そして状態５は、入力記号“ｅ”についての遷移を有していないので、この経路は、ブロックされて、経路１−２−３−４−４だけを残す。
第４の文字は、“ｐ”なので、状態１０及び状態５への、二つの経路が許される。状態５への遷移の後、状態６への遷移が続き、許された経路は、部分経路
１−２−３−４−４−１０及び１−２−３−４−４−５−６のいずれかで始まる。第５の文字、“ｅ”、を読み取るために、第１の経路は、状態１０から状態５への遷移を許し、それは“ｅ”遷移を有していないので、次にブロックされる。第２の経路（１−２−３−４−４−５−６）は、状態６から状態４への許される経路を有しており、それは、その唯一許される遷移である。それゆえに、この点で許される経路は、１−２−３−４−４−５−６−４である。
第６の文字、“ｌ”、を読み取るために、状態５への他の許される遷移が“ｌ”遷移の欠落によってブロックされるので、遷移は、状態４からそれ自身へでなければならない。第７の文字、“ｉ”、を読み取るために、遷移は、状態４から状態９へ、或いは状態５そして状態７へでなければならない。それゆえに、この点への許される経路は、１−２−３−４−４−５−６−４−４−９、及び１−２−３−４−４−５−６−４−４−５−７である。
【００２８】
第８の文字、“ｎ”、を読み取るために、上記第１の許される経路は、状態９から状態１１へ或いは状態５（ブロックされる）への遷移を必要とし、第２の許される経路は、状態７から状態８への遷移を必要とする。
第９の文字、“ｇ”、を読み取るために、上記第１の経路（１−２−３−４−４−５−６−４−４−９−１１）は、失敗する。なぜならば、状態１１が“ｇ”遷移を有さず、状態８までの経路、及びそこから状態４への遷移だけを残すからである。この点で、許される経路は、１−２−３−４−４−５−６−４−４−５−７−８−４である。
第１０の文字、“ｓ”、を読み取るために、状態５への遷移及び状態５からの遷移がブロックされるので、唯一の許される経路は、状態４から状態４へである。それゆえに、入力ストリングについての最終経路は、１−２−３−４−４−５−６−４−４−５−７−８−４−４である。
状態４が最終状態なので、入力ストリングは、許されるストリング対の入力ストリングである。換言すると、ハイフネーションＦＳＴは、それが処理できるあるものとしてストリングを認識する。この許される経路についての出力ストリングは、“ｃｌｅ−ｐｅｌ−ｉｎｇｓ”であるべく容易に決定され、それは規則１及び２の両方により適当にハイフンで結ばれている。
【００２９】
図３は、ストリング対を処理するのに有向グラフ２０を用いる本願発明による有限状態変換器（ＦＳＴ）システム３０の一つの実施例のブロック図である。ＦＳＴシステム３０は、入力バッファ３２ａ、入力バッファ３２ｂ、ＦＳＴ３４、及び出力バッファ３６を備えている。ＦＳＴ３４は、中央処理装置３８、及びメモリ４０を備えている。メモリ４０は、現行状態記憶場所４２及び状態−遷移データ構造４４を備えている。
入力バッファ３２ａ、３２ｂは、ＣＰＵ３８の入力に連結されており、ＣＰＵ３８に、入力ストリング及び出力ストリングをそれぞれ供給する。出力バッファ３６は、ＣＰＵ３８の出力に連結れている。データバスも現行状態記憶場所４２及び状態−遷移データ構造４４をＣＰＵ３８に連結する。ある実施例において、ハイフネーションＦＳＴシステム３０は、入力バッファ３２ａに入力したストリングから全ての非要求ハイフンを取り除きかつ変更されたストリングを入力バッファ３２ａに挿入することによって、入力バッファ３２ｂの内容から入力バッファ３２ａの内容を生成する手段を備えている。
【００３０】
ＦＳＴ３４が動作するとき、それは、入力バッファ３２ａに記憶された入力テープ、及び出力バッファ３２ｂに記憶された出力テープを読み取る。現行状態は、現行状態記憶場所４２に記憶された値によって示され、ＣＰＵ３８は、新しい状態を決定すべくデータ構造４４の状態−遷移データを読み取る。もしＦＳＴ３４が非確定的ＦＳＴであるならば、記憶場所４２は、調査されているあらゆる多重経路を説明すべく、一つ以上の現行状態についての割り当てられた空間を有しうる。状態−遷移データの例は、表３に示されたデータである。入力及び出力テープを読み取ったあと、ＦＳＴ３４は、テープを読み取り終えたときの現行状態が最終状態がどうかを示している、従って入力−出力ストリング対がＦＳＴ３４によって受け入れられるかどうかを示している妥当性ビットを出力する。
図３から明らかなように、そのような規則を符号化する異なるデータ構造４４を用いることにより、ＦＳＴ３４は、図３のそれらとは異なる規則の組についてプログラムされうる。
図４は、本発明によるＦＳＴシステム３０’の別の実施例のブロック図である。ＦＳＴシステム３０’は、入力バッファ３２ａに類似の入力バッファ３２’、ＦＳＴ３４に類似のＦＳＴ３４’、及び出力バッファ３６’を備えている。ＦＳＴ３４’は、入力バッファ３２’からの入力ストリングを受け取るべく、かつ出力バッファ３６’に出力ストリングを出力すべく連結される。
【００３１】
ＦＳＴ３４’が出力記号に関する許容可能な経路についてのその探索を制限しないことを除いて、ＦＳＴ３４’の動作は、ＦＳＴ３４のそれに類似である。
その代わり、もし入力バッファ３２’から入力された入力ストリングについて妥当な経路が見出されたならば、その経路に対応付けられた出力ストリングは、出力バッファ３６’に出力される。もしＦＳＴが、所与の入力ストリングについての多重出力ストリングを許すべくプログラムされるならば、出力バッファ３６’は、多重出力ストリングに対する容量を有する。
上述した記載は、例示的なものであり、限定的なものではない。本発明の多くの変更は、この開示をリビューすることにより当業者にとって明らかになるであろう。従って、本発明の範囲は、上述した記載に関して決定されるべきではなく、その代わり、それの完全なる同等な範囲に沿って、添付のクレームに関して決定されるべきである。
【００３２】
【発明の効果】
本発明の入力ストリングのハイフネーション位置を決定するハイフネーション位置決定装置は、入力ストリングから入力記号を読み取る入力手段と、入力手段に連結され、初期状態、現行状態、及び状態遷移データ構造によって特徴付けられ、現行状態が該入力ストリングの少なくとも一つの入力記号及び状態遷移データ構造の遷移によって決定され、状態遷移データ構造がハイフネーション規則の組によって決定される有限状態機械と、有限状態機械に連結され、入力ストリングのハイフネーション位置を指示し、ハイフネーションが有限状態機械の状態遷移によって決定されるハイフネーション指示手段とを備え、ハイフネーション位置がハイフネーション規則の組に従うので、予め知られていることを必要としない潜在的に無限な単語の一覧表を、ハイフネーション検査及びハイフネーション生成のためのＦＳＴ構造の中に、符号化する。
本発明のハイフネーション位置決定装置は、ハイフネーション規則の組が、無限数のストリングに適用可能な少なくとも一つの規則を備える。
本発明のハイフネーション位置決定装置は、ハイフネーション規則の組が、更に、他の規則によって扱われない有限数のストリングに適用可能な少なくとも一つの規則を備える。
【００３３】
本発明のハイフネーション位置決定装置は、ハイフネーション規則の組が、更に、他の規則によって扱われない有限数のストリングに適用可能な少なくとも一つの規則を備え、他の規則に否定規則が付け加えられ、否定規則を含んでいる他の規則は、有限数のストリングのハイフネーションを扱わない。
本発明のハイフネーション位置決定装置は、入力ストリングが、言語の単語である。
本発明のハイフネーション位置決定装置は、言語が英語である。
本発明のハイフネーション位置決定装置は、言語がフィンランド語である。
本発明のハイフネーション位置決定装置は、入力ストリングが、文書処理プログラムで用いられる文書の単語であり、ハイフネーション標識が、文書処理プログラムのラインブレーク位置決定プロセッサに連結される。
本発明のハイフネーション位置決定装置は、ハイフネーション標識が、ハイフネーション位置にハイフンが散在する入力ストリングから記号を包含しているストリングを出力する。
本発明のハイフネーション位置決定装置は、入力ストリングが、少なくとも一つの提案されたハイフネーション位置に少なくとも一つのハイフンを含み、ハイフネーション標識が、提案されたハイフネーション位置が記ハイフネーション規則の組に従うか否かを示す。
【００３４】
本発明のハイフネーション位置決定装置は、状態遷移データ構造が、データ構造へのハイフネーション規則の組の自動コンパイルによって生成されたデータ構造である。
本発明のハイフネーション位置決定装置は、状態遷移データ構造は、データ構造へのハイフネーション規則の組の手動コンパイルによって生成されたデータ構造である。
本発明の入力ストリングにハイフンを付す方法は、状態遷移構造にハイフネーション規則の組をコンパイルし、ハイフネーション規則のそれぞれが、表現に対応付けられた基準の組に適合するストリングの少なくとも一つの許されたハイフン位置または禁止されたハイフン位置を示す表現によって特徴付けられ、少なくともハイフネーション規則の一つが入力ストリングの非束縛な組についての少なくとも一つのハイフン位置を符号化し、状態遷移構造により有限状態機械をプログラミングし、有限状態機械を初期状態にリセットし、入力ストリングの記号及び状態遷移構造により有限状態機械の少なくとも一つの現行状態を変更し、変更段階で生じた一つの状態から別の状態への遷移によりハイフン位置標識を出力する段階を具備するので、予め知られていることを必要としない潜在的に無限な単語の一覧表を、ハイフネーション検査及びハイフネーション生成のためのＦＳＴ構造の中に、符号化する。
【００３５】
本発明の入力ストリングにハイフンを付す方法は、ハイフン位置標識を出力する段階が、更に、ハイフン位置にハイフンが散在する入力ストリングの記号を出力する段階を具備する。
本発明の入力ストリングにハイフンを付す方法は、入力ストリングが、提案されたハイフン位置に少なくとも一つのハイフンを備え、ハイフン位置標識を出力する段階が、更に、提案されたハイフン位置が入力ストリングについてのハイフン位置に対応するか否かの標識を出力する段階を具備する。
本発明における出力ストリングは、本発明の入力ストリングにハイフンを付す方法によって生成される。
本発明の有限状態機械は、ハイフネーション規則の組を生成し、少なくとも該ハイフネーション規則の一つが入力ストリングの非束縛な組についての少なくとも一つのハイフン位置を符号化し、ハイフネーション規則のリストに対応する状態遷移構造を発生し、状態遷移構造が、入力ストリングの特定の記号の入力に続いて現行状態から次に状態への複数の遷移のいずれが取られるかを示すデータを備えており、データが該入力ストリングのハイフン位置をも示し、状態遷移構造により有限状態機械をプログラミングする段階を具備する方法によって発生されるので、予め知られていることを必要としない潜在的に無限な単語の一覧表を、ハイフネーション検査及びハイフネーション生成のためのＦＳＴ構造の中に、符号化する。
【図面の簡単な説明】
【図１】単語の有限の組についてのハイフネーションＦＳＴ符号化の有向グラフを示す概略図である。
【図２】単語の無限の組についてのハイフネーション規則の組及び符号化を表しているハイフネーションＦＳＴの有向グラフを示す概略図である。
【図３】適当なハイフネーションについてハイフンで結ばれた単語を検査すべく図２の有向グラフにより入力ストリングを処理するストリングプロセッサのブロック図である。
【図４】示されたハイフネーション位置を有する単語を生成すべく図２の有向グラフにより入力ストリングを処理するストリングプロセッサのブロック図である。
【符号の説明】
１０，２０  有向グラフ
３０，３０’  有限状態変換器（ＦＳＴ）システム
３２ａ，３２ｂ，３２’  入力バッファ
３４，３４’  ＦＳＴ
３６，３６’  出力バッファ
３８  中央処理装置（ＣＰＵ）
４０  メモリ
４２  現行状態記憶場所
４４  状態−遷移データ構造
【図１】
0003599775.tif 000005
【図２】
0003599775.tif 000006
【図３】
0003599775.tif 000007
【図４】
0003599775.tif 000008