JPH02293969A - テキストコーディング方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はデジタルコンピュータにおいてスコぶる高速の
テキスト処理を可能にするようにドキュメント内のテキ
ストを表現する方法に関する。殊に、テキストの各ワー
ドはそのワードの特性を記述する情報パケットを照会す
る数（もしくはトークン）として表わされる。その後は
種々の操作が各文字ではなくて各トークンを処理してテ
キスト処理機能を実行する。このように表示がコンパク
トであるという性質の他に、ＷＹＳ　ＴＷＹＧエディタ
中の殆んど全ての機能の実行が改善されている。殊に、
改行を決定しテキストを表示する速度はテキストを一度
に一文字でなく一トークン処理する場合の方が著しく大
きい。

〔従来の技術〕

典型的なワード・プロセッシング方式の場合、各段階は
内部で１つもしくはそれ以上の文字列をして存在するか
ら表示したり印字したりする前にそれらを行に分解する
必要がある。例えば、典型的な改行アルゴリズムは主内
部ループを有していて、同ループは先の文字群の幅の和
に現在の文字の幅を加算してその新たな合計を所望の行
幅と比較する。プログラムは当該行内の文字数が行中に
おさまる文字数を超えるまでこのループを実行すること
になる。この時点でプログラムはその行を最後の語全部
で終えるか、それとも現在語にハイフンを入れてそのハ
イフン後の部分を次行の初めにおくかすることができる
。

この過程に関連する２つの問題がそのプログラムの実行
を余りに緩慢にする原因となっている。

即ち、まづ第１に、上記内部ループは行内の文字の全て
について実行する必要がある。第２に、もしハイフンづ
けを行う場合とは、マージンを超過した文字の前後関係
は推論する必要がある。即ち、その文字がスペースであ
るか句読点であるか語の一部であるのかを判断する必要
がある。一般的について、付丁の如き各文字の処理やド
キュメント内のスクロールを必要とする操作は全て非常
に遅い。更に、ハイフネーション、スペルチェック、サ
ーチ、リプレースの如き、ドキュメントを一系列の語と
して解釈することに依存する操作も非常に遅い。

米国特許第４，　１８１．　９７２号（キャセイ）は単
語を自動的にハイフンづけする手段と方法に関するもの
で、文字ではなくて入力単語の長さに反応する手段を開
示している。然しなから、上記キャセイ特許は将来の使
用のために得られる語の長さを記憶せず、ハイフネーシ
ョンが必要とされる場合には、キャセイ特許の方法では
テキスト全体を一字毎に走査するようになっている。ま
た、同方法によれば、全体の語の長さによって区切り点
を計算することをせず、その代わりに子音／母音の組合
せ間で有効な区切り点に関するメモリーベーステーブル
を使用することを教示している。

米国特許第４，　０９２，　７２９号（ローゼンバウム
外）と第４，　０２８，　６７７号（ローゼンバウム）
は同様に区切り点のメモリテーブルによるハイフネーシ
ョン法に関する。

ローゼンバウムの特許は語長によってハイフン付けを実
行している。しかし、そこに開示された方法は本書に開
示する発明とは異なっている。即ち、ローゼンバウム特
許では単語はハイフネーションが必要とされる時に文字
から組立てて、その後で区切り点を有する語を含む辞書
と比較する。

本文中に開示した発明ではドキュメントを解読する時に
単語を組立て、ラインブレーク計算中に辞書を参照する
方法を使用することはない。

必要とされるのは文書を処理するためにテキストを表現
するための優れた方法である。作成機能の計算算数度を
少なくする自然な方法は一度に一文字ではなく一度に一
語を計算することのできるデータ構造をつくりだすこと
であろう。この場合のテキス．トの内部表現は次の対と
して定義されるトークンである。

く型、データ〉 但し、タイプはそれぞれのトークンクラスに対する一義
的な識別子であり、データは特定型のトークンに関連す
るデータである。１つのトークンは次の通りより簡潔な
形で表現することができる。

く型、ポインタ〉 但し、ポインタはそのトークンと関連するデータのアド
レスである。この形のトークンはエントリーの長さが同
一であるため操作がより容易である。一つのトークンを
更に簡潔に表現するにはトークン型をデータブロック内
に含めればよい。即ち、このことによって１つのポイン
タに対する基本トークン目的を減らすことができる。型
情報はデータブロック内に依然存在するから、この形の
ポインタは依然１つのトークンとして適切に照会できる
。過去において、一種のトークン形である内部テキスト
表示法を使用した方法が若干あったが、それらは全て迅
速なテキスト作成に通用できないという欠点をもってい
た。

従来方式の多くのものはトークンをコンピュータプログ
ラムを編集するために使用していた。例えば、コピロッ
ト「対話形式プログラミングシステムにおける多重処理
方法」　（ダニエルカール、１９７４年７月、博士論文
、スタンフォード大学）を参照されたい。スワインハー
トはコンペイラがプログラムを機械命令に翻訳するため
に使用する原始コード（テキスト）とそれに対応するパ
ーズ木との間の関係を維持するためにトークンを使用し
ている。編集操作が終るたびに、変化した原始コードの
行を再走査してトークン化し、パーズ木は再構築され、
最終的にパーズ木の正確さをチェックする。これらの方
式はＬｉｓｐの如き言語で書かれたプログラムを作り修
正したりするにはすこぶる人気があるが、かなり遅く骨
の折れるものとなりがちである。ユーザに対する利点は
プログラムに対して施こされた変更のためエラーが導入
されずに除去される公算が大きい点である。

第２の公知の方法では基本テキスト単位としてトークン
を使用してコンピュータプログラミング言語の要素でな
くて英単語を表現している。［辞書依存式テキスト処理
システム」と題するレキシコンテキスト（ジョン・フラ
ンシス・ハーヴエイ、１９７１年８月、修士論文、マサ
チュセッツエ科大学）では、一つのトークンが単語に対
するテキストを含む字句エントリーを指名しており、そ
の後、ハッシュ機能を使用して各トークンに対して一義
的に定義できるエントリーと関連するデータを検索する
ようになっている。このコーディング法は非常に一般的
であるが性能を犠牲にしている。

更に、ハーヴエイの方法は原則としてオペーレーティン
グシステムに対する自然言語インターフェースとして使
用されるため、文句はグローバルであって何らかの特定
の文書から独立している。

このアーキテクチャは情報が単一の中央処理装置で処理
されるような環境において、しかも、遭遇する単語の世
界全体が予め知られている場合に実際的である。たとい
数語をそのグローバルな辞書に追加することができても
、処理装置がネットワークやその他の通信装置に接続さ
れない分散型環境においては依然問題が存在することに
なろう。

この場合、辞書は急速に発散し、一つの機械でかかられ
た文書は他の何れの機械でも正確に解釈することはでき
ないであろう。この方法のもう一つの大きな欠点は主辞
書内にエラーが発見された場合、その欠陥辞書によって
コーディングされた文書は、たといその文書を再構築す
ることが可能であっても全て処理しなおさなければなら
ない点である。主辞書は非常に大きく設計する必要があ
るから、同辞書を主メモリ内に常駐したままにすること
は実行不能であろう。主メモリ内に常駐しない大辞書は
巨大な性能上の不利益を蒙ることになろう。

〔発明が解決しようとする課題〕

本発明はトークンを使用して、特にＷＹＳ　ＩＷＹＧエ
ディタに適用した場合にテキストを効率的に編集すべく
設計された方法でテキストを表現する方法である。本指
向構造をコンピュータプログラムエディタ内に使用する
代わりに、単純な連鎖リストを使用する。トークンポイ
ントはそのトークンと関連するデータを直接指示するこ
とによってハッシュ機能を除去することができ、また、
データブロックの長さは可変であるが、データブロック
は全トークンに対して均一に定義することができる。

辞書は各文書のみに限定されており、分散的環境に好適
なシステムを得ることができる。

上記手法は改行やページネーション、ストリングサーチ
、リプレーススペルコレクションの如きその他の可視的
な文書操作を高速化するために文書作成システムに使用
することができよう。また、本発明は印字文字の表示や
文書内のスクロール、マウスのつめを文書内の一位置に
合わせるといった対話用操作の性能を向上させるために
も使用することもできる。本方法はハイフンのついたテ
キストを希望する場合に特に効率的である。アルゴリズ
ムを拡大して連結線、対核（ｋｅｒｎｅｄ　ｐａｉｒｓ
）、外部テキストを支援する場合にも性能は低下しない
。この手法は長い単語、ハイフネーション、ハイフネー
ションによるスペルの変化を伴うドイツ語文や、何度も
ハイフンを付す必要のある単語にすこぶる好適である。

本方法は文書中のテキストを単語、句読点もしくは句読
スペースの一連の「アトム」に分解し、それぞれに番号
（「トークン」）を付与する段階より構成される。一例
として、もしプログラムがｏｆ″という語に最初に出会
った時そのアトムｏｆ”にトークン″３０１”を付与し
たとすると、同文書内の他の全ての″ｏｆ”に同一番号
“３０１”を付与しつづけるであろう。

同時に文書内のそれぞれの唯一のトークンに対して性質
のテーブルが構成される。以下はスペース以外のアトム
に対して維持される性質のリストである。

ｔｅｘｔ　：　　　　アトム内の文書 １ａｓｔＦｏｎｔ　：　　本テーブル内に納められるト
ークン性質を計算するために使用されるフ ォントの表示性質を示すコード ｄｉｓｐｌａｙＢｉｔＭａｐ：　　フォントＩａｓｔＦ
ｏｎｔ内のアトムテキストのビットマップ ｎｏｔＰｕｎｃｔｕａｔｉｏｎ：アトムが句読点である
かどうかを示すプール ａｔｏｍＭｅｔｒｉｃｓ：　　スクリーンとプリンタ装
置内のトークンの文字数と語幅を含むレコ ード、この情報はＩａｓｔＦｏｎｔが照会するフォント
から導出される。

ｂｒｅａｋＰａｉｎｔ：　　トークン内の各区切り点に
ついて工ントリーを一つ有するアレイ、もし エントリーがハイフン点であれば、 エントリーはハイフンの幅を含めハ イフネーション点に先立ちワード部 分に対する計測情報を含む。もしハ イフンがユーザにより挿入されたハ ードなハイフネーション点の場合に はハイフンの幅は含まれない。

スペースに相当するトークンは他のトークンとは異なる
風に取扱われる。上記トークンはそれを処理する規則が
他のトークンのそれとずっと異なっているためそれと関
連する属性の集合を有しない。

テキスト処理機能はそれぞれの継起的なトークンを用い
て現在のトークン属性をアクセスすることによって進め
ることができる。このため文書をアトム系列として解釈
するテキスト機能だけでなく文書を古典的な形で一度に
一文字処理するアルゴリズムも著しくスピードアップす
る。

改行アルゴリズムはそれぞれの継起トークンを用いてト
ークン属性中の計測情報にアクセスすることができる。

もし行幅を超えると、現在の行は先のトークンで終結す
るのが普通である。テキストが右端をジャスティファイ
される場合には、語間のスペースは拡大することができ
る。最後に、もし行を十分に拡張できない場合には、ス
ペースを詰めすぎたトークンに相当するトークンを調べ
てそれがハイフネーション可能かどうかを判断すること
になる。

トークン・パイ・トークン法によれば改行がより効率的
になるばかりでなく、文書が一連のアトム（例えば、単
語、スペース、句読点）として解釈されるに応じてその
他の編集機能もスピードアップすることができる。例え
ばスペルチェックの場合、一文書中に一単語がどれ程多
く使用されようとも、その単語のスペルは１回チェック
するだけでよい。何故ならば、その単語が出て来るたび
に同一のトークンが使用されるであろうからである。ア
ルゴリズムはフエーズで進行する。まず、アルゴリズム
はアトムテーブル内のエントリーを全てチェックした後
、文書の隣り合う単語どうしあるいは分割された単語を
走査する。

本方法によってコーディングされたテキストからトーク
ン全体だけでなく文字を挿入削除する作業は非常に効率
的に行える。個々の文字の場合には、迅速に修正可能な
特別のトークンが使用される。トークン全体を挿入削除
する作業は同作業がトークン系列を修正するだけである
から個々の文字の場合よりも更に高速である。タイプ・
イン中のスクリーン彩色も非常に高速である。何故なら
ば、それら操作の全ては文書のデータ構造を更新し、新
たな行終了点を判断し、スクリーン上のテキストを彩色
することを伴い全てこの手法により利益を受けるからで
ある。

サーチとリプレース機能もまたそれが一語だけをサーチ
している場合にもアトムテーブル内のテキストのみを処
理するだけで済むから好都合である。もし多数の語をサ
ーチしている場合には文字系列ではな《アトム系列につ
いては文書を走査するだけでよい。

また、このテキスト解読法によればすこぶるコンパクト
な外部フォーマットが可能になる。トークン属性を基本
的な属性とその基本的なトークン属性から算定できる派
生属性（即ち、トークン内の文字と区切り点の位置）に
分離することができる。ファイル上には基本トークン属
性のみを書出せば済む。新たなエディットセッションが
そのファイルについて開始されると、その基本属性を用
いて派生属性を追加する。

データ構造 本方法を使用してテキストをコーディングする作業は文
書をアトムに解析してそのアトムに相当するトークンの
アレイを構築する作業より成る。

アレイ内の少数のエントリーはトークンではない。

これらは頻度の少ない文字系列（連続したスペースの如
き）をコーディングして非常に大きな文書をコーディン
グするために必要な特殊エントリーである。

第１図のテキストはテキストをトークンにコーディング
するために必要とされるデータ構造の型の定義より構成
される。第１図内で使用されるコンピュータ言語はメサ
（ゼロックス開発環境メサ言語便覧、ゼロックス社、１
９８５年）である。

メサはパスカル（パスカルユーザ便覧・報告、キャサリ
ーン・ジャンスンならびにニコラスヮース、シュプリン
ガー出版社、１９７４年）とモジュラ■（モジュラＨに
よるプログラミング、ニコラスワーク、シュプリンガー
出版社、１９８２年）である。ディレクトリ節はインタ
ーフエーストークンからオフセットした型が改行メサで
使用されることを宣言する。次に、ファイルはファイル
の採能がデータ型式と手順を定義することであるからＤ
ＥＦＩＮＩＴＩＯＮＳファイルと宣言される。

コーディングされたトークンアレイを定義するデータ構
造はエンコーディッドテキスト（ＥｎｃｏｄｅｄＴｅｘ
ｔ）である。アレイ中の各要素はエントリーである。コ
ーディングされたテキスト内の各エントリーはメモリの
一ワード中におさまる。エントリーはトークンもしくは
拡張文字の２つのバリアントを有するレコードである。

トークンバリアントは２つのワイールドより成る。即ち
、トークンが照会するアトムに相当する番号と、トーク
ンの後にスペースが来るがどうかを示すプールとである
。性能を最大にするために、各アトムに付与されるトー
クンはそれを用いてそのトークンの属性のメモリ内のロ
ケーションを判断できるように選択する。

Ｅｎｔｒｙレコードの拡張文字バリアントはそれ自体パ
リアントレコードである。このバリアントはトークン見
出し語によって表現できない情報を解読するために使用
される。Ｃｈａｎｇｅ　Ｂａｓｅ拡張文字バリアントは
大きな文書を解読するために必要とされる。トークンバ
リアントのオフセットは１４ビットのみで構成されるた
め、直接アドレス指定可能なトークンの数は限られてい
る。Ｃｈａｎｇｅ　Ｂａｓｅ拡張文字はトークン属性の
アドレス空間を変更することを可能にし、従って非常に
多くのトークン属性をアドレス指定することが可能にな
る。

スペース拡張文字バリアントは連続スペースを表現する
ために使用される。これが必要なのはトークンエントリ
ーがアトムの後に１個のスペースが続くかどうかをコー
ディングすることしかできないためである。

Ｚｅｒｏ　Ｗｉｄｔｈ　Ｓｐａｃｅ拡張文字バリアント
はアトム内のハイフン化しない区切り点を表現するため
に使用される。これはＸＩＣＳマークアップ言語では滅
多に使用されない特長である（ゼロックス統辞文システ
ムユーザガイド、ゼロックス社、１９８７年）　Ｚｅｒ
ｏ　Ｗｉｄｔｈ　Ｓｐａｃｅバリアントはパラメータを
有しない。

第２図は、第４図のテキストから作り出されるトークン
のリストである。この図では、テープの列毎にエントリ
ーが１個あるようなコーディングテキストの各エントリ
ーの目録より構成される。

わかりやすくするために、各トークンのテキストは第２
図中の各トークンエントリーのすぐ右側に含まれる。第
２図の第１列はＣｈａｎｇｅＢａｓｅバリアントである
拡張文字見出語を含む。該第１列はトークン属性のアド
レス空間を第１のアドレス空間に設定する。トークン属
性のアドレスはＣｈａｎｇｅＢａｓｅエントリー中に定
義されたベースアドレスはトークンエントリー中のオフ
セットとを結合することによって計算される。第２図の
第２列はトークンバリアントエントリを含む。各アトム
については２個のアイテムがある。即ち、そのアトムを
識別する番号とアトムの後にスペースが存在するか否か
を示す１ビットである。このコーディング方式ではアト
ム間のスペースは先行するアトムの一部となる。例えば
、第１の単語“Ｔｈｅ″、は（ＳｐａｃｅＦｏｌｌｏｗ
ｓ：ＴＲｔｌＥ，　ｏｆｆｓｅｔ：１　］という値を付
与される。

同様にして、第２の語“ａｐｐｒｏａｃｈ”は（Ｓｐａ
ｃｅＦｏｌｌｏｗｓ：ＴＲＵＥ．　ｏｆｆｓｅｔ：　２
　０　）となる。

９番目のエントリーは再び“ｔｈｅ”という語となるが
小文字“ｔ”を備えている。このアトムは文字幅が普通
の場合同一でないために大文字“Ｔ”を有する本来の“
Ｔｈｅ”と同一のトークンを付与することはできない。

１７番目のエントリーは右括弧である。次のようにコー
ディングされる。

（ｓｐａｃｅＦｏｌｌｏｗｓ：ＦＡＬＳＥ，　　ｏｆｆ
ｓｅｔ：３２３］リスト上の２９番目のアイテム、　Ｏ
ｒ”という単語はリスト上の１８番目の語と同じ語であ
る。

それらは同一の属性を持つから同一のトークンを使用す
ることになろう。同様にして、エントリー２６と２８の
コンマは同じトークンを有することになろう。

各トークンは第１３図に示すように関連する属性のリス
トを備えている。属性の集合は２つのレコードより構成
される。即ち、ＴｏｋｅｎＰｒｏｐｓ．　Ｏｂ　ｊｅｃ
ｔとレコードＴｏｋｅｎＰｒｏｐの例である。これらレ
コードの両方ともＭＡＣＨＩＮＥ　ＤＢＰＥＮＤＥＮＴ
と宣言されメサコンパイラをしてフィールドを可能な限
り少ないメモリワード数内へ詰めこませる。値をアクセ
ス回数の少ない順に配列することによってトークン属性
にアクセスするために必要とされるメモリ照会の数は最
小限にすることができよう。メサプログラミング言語で
は不定長アレイはレコードの終りにしか配置できないた
め、最適順序を実現するためには２個のレコードが必要
になる。

Ｏｂｊｅｃｔレコード中の最初のレコードはアトムが句
読点であるかどうかを示すプールである。このフィール
ドはどこで適法の区切りが行われるかを判断するために
改行計算中に使用される。

次は文体、大きさ、アクセント、フォントの重さを識別
する番号である。この番号はそれからアトムＭｅｔｒｉ
ｃｓ，　ｂｒｅａｋＰｏｉｎｔアレイ（存在する場合）
およびディスプレイビットマップが計算された最終的な
フォントを表わす。従って、もしアトムが処理中の現在
のフォントが既にアトムが処理された最後のフォントと
同一であるならば、属性レコード中の値は依然正確であ
るため簡単にアクセスされ再計算されることはない。さ
もなければ、属性レコード中の値は現在トークン処理す
る前に再計算する必要がある。

第３のフィールドはＡｔｏｍＭｅｔｒｉｃｓと呼ばれ、
同様にＴｏｋｅｎＰｒｏｐｓインターフェース中で定義
される。このレコードはアトム全体についての計測情報
を含んでいる。ＡｔｏｍＭｅｔｒｉｃｓ内の値は、マイ
カ（１インチの１／２５４０と定義される機械独立単位
）とピクセル（スクリーン単位）のアトムの長さとアト
ムテキストの長さ（単位バイト表示）である。

英文字は各文字について１バイトを要するのが普通であ
るが、別の言語や特殊技術記号を表わすにはそれ以上の
バイトが１文字あたり必要となるかもしれない。１文字
あたり１バイト以上を要する国際文字や特殊記号をコー
ディングする方法についてはゼロックス文字コード基準
（ゼロックス文字コード基準、ゼロックス社、１９８６
年）を参照されたい。

ａｔｏｍＭｅｔｒｉｃｓに続くのはｂｒｅａｋＰｏｉｎ
ｔｃｏｕｎｔでアトムが行間に分解できる位置数に相当
する。区切り点は普通単語にハイフンをつけることによ
って判断される。一語は手で挿入されたゼロ幅スペース
を含むことができる。このコーディング技法ではアトム
“ｔｈｅ”は区切り点をもたない。Ｏｂｊｅｃｔ中の最
後のフィールドはｂｒｅａｋＰｏｉｎｔアレイである。

このアレイはアトム中に区切り点がなければ全く省略す
ることができる。第１１図はアトム“ｔｈｅ”の属性の
メモリレイアウトを示す。もしアトム中に区切り点が存
在すれば、ｂｒｅａｋＰｏｉｎｔアレイの各要素は最初
の単語をハイフン付けすることによって形成可能な分割
語の最初の部分より構成されることになろう。例えば、
３音節語の“ｄｏｃｕｍｅｎｔ”は″ｄｏｃ一“と“ｄ
ｏｃｕ−”を記述するための情報である２個の区切り点
を有することになろう。これは第１２図に示されている
。

各ｂｒｅａｋＰａ　ｉｎ　ｔアレイ中の最初の要素は区
切り点が如何に望ましいかを表わすパラメータである区
切り点形成式より構成される。これは改行アルゴリズム
によって使用される。バイトカウントは各々の選択肢の
バイトカウントである。長さは機械独立単位とピクセル
における各選択肢の長さである。

属性を記述する第２のレコードはＯｂ　ｊｅｃｔＴｒａ
ｉ　Ｉｅｒレコードである。トレイラーレコードはトー
クン属性中に常に存在する。ＯｂｊｅｃｔＴｒａｉｌｅ
ｒ中の最初のフィールドはｒｅｆｅｒｅｎｃｅｃｏｕｎ
ｔである。これは、一組の属性に対してスペースを開放
すべきかを何時に定めるかの為にエディタのダイナミッ
クメモリ管理プログラムによって使用される。典型的に
はこれは基準カウントがゼロに達する時に行われる。

次のフィールドはラスタであり、これはＲａｓｔｅｒＤ
ａｔａと呼ばれるレコードであってアトムの格納された
スクリーン解像を記述する情報である。第１のアイテム
であるｂｐｌは各水平走査線における総ピクセルである
。もし、例えば、ビットマップが１６のビットワードに
分割されれば、この数はたといアトムの画像が個々の文
字“ｉ”の場合と同様に小さな“幅．”を占めても１６
ビットの倍数であろう。ピクセル内の画像の実際の幅は
ａｔｏｍＭｅｔｒｉｃｓ中に記述される。第２のアイテ
ムはこのアトムについてビットマップ全体を格納するた
めに必要とされるメモリの全ワード数である。例えば、
ｌアトムのピクセル中の幅が３０ビットで１画像が１４
ピクセルの高さであれば、ビットマップは２８ワードを
要することになろう。この数は次のようにして導き出さ
れる。

ｈｅｉｇｈｔ”ｂｐｌ／ｂｉｔｓ−ｐｅｒ−ｗｏｒｄ但
し、ｂｐｌは規約により画像幅より大きいかそれに等し
いメモリの１ワード中のビットの最小倍数であると定義
される。高さは画像の高さである。

ペースラインは画像の上部からテキストが重る走査線へ
至る走査線数である。ビットは画像の最初のワードに対
する２ワードポインタであり，　ＲａｓｔｅｒＤａｔａ
レコード中のフィールドのグラフ表示については第１３
図を参照されたい。

トレイラーレコードの最終フィールドはテキストと呼ば
れる。これはトークン中に文字を含むアレイである。ア
レイの長さは先に定義したＡｔｏｍＭｅｔｒｉｃｓ中に
格納される。トークンのサーチを最適化するために、テ
キストフィールドに割当てられるバイトの数は実際には
トークン中の文字数を超えるかもしれない。割当てられ
る文字数は、アルゴリズムが実行される特定の機種に応
じて、通常２もしくは４の倍数であろう。

第５図はＭｅｓａ原始コードで改行を計算するためのデ
ータと手順を定義する。ファイルのディレクトリ一部分
はＬｉｎｅＢｒｅａｋ．　ｍｅｓａ中に参照される他の
インターフェースファイルの要素を定義する。

ＬｉｎｅＢｒｅａｋ．　ｍｅｓａはファイルの機能がデ
ータ型と手順を定義することであるからＤＥＦＩＮＩＴ
ＩＯＮＳファイルとして宣言される。

Ｓｕ　ｆ　ｆ　ｉｘＣｈａｒはテキストの一行の終りに
出現可能な最終文字を定義する型である。これはディス
プレイアルゴリズムに必要となる。ＳｕｆｆｉｘＣｈａ
ｒは列挙された型中の各エレメントに付与される値が連
続し０で始まるようにするために機械依存性として宣言
される。

Ｒｅａｓｏｎは改行アルゴリズムが復帰できる可能な理
由を列挙する列挙された型である。Ｒｅａｓｏｎは改行
アルゴリズムがコンパイラが列挙型中の各エレメントに
付与する特定値に依存するため機械依存性をもつ。以下
のテーブルはＲｅａｓｏｎの値をそれぞれ実行する。

ｍａｒｇｉｎ　　現在トークンが行幅を費消し改行決定
が行われた。このことはアルゴリズムに対して課される
制約の全てを充たす改行が識別されたことを意味する。

ｎｏｒｍａｌ　　現在のテキストブロックが改行決定を
行わずに費消された。

ｃｈａｎｇｅＢａｓｅ　　現在トークンはｃｈａｎｇｅ
Ｂａｓｅ拡張文字である。

ｉｎｖａｌｉｄＰｒｏｐｓ　　現在トークンの属性は時
代遅れで現在フォントで計算しなおす必要 がある。

ｃｏｎｔ　ｉｇｕｏｕｓＷｏｒｄｓ　　現在トークンの
前にはスペースや句読点はない。このこと は通常２個のトークンが１ワ ードの断片であることを意味 する。この結果、クライアン トコードがトークン断片の系 列をハイフン付けする場合断 片トークンの開始を追跡しつ づけると共に核化（ｋｅｒｎｉｎｇ） と文字間隔について計測情報 を調節することが可能になる。

ｕｎａｂ　ｌｅＴｏＢｒｅａｋ　　現在行幅に達しても
改行決定はできない。この結果を生じさせ る最も一般的な事象はマージン を超えるトークンが句読点であ る場合である。

ｓｐｅｃｉａｌＧｅｒｍａｎｃａｓｅ　　改行アルゴリ
ズムが所望のハイフネーション点で綴り 直しを必要とするトークン を破ろうとする時、この理 由は復帰する。

ＴｗｅｌｖｅＢｉｔｓは１２ビットの無符号整数を定義
する型である。以下に述べるＳｔａｔｅＲｅｃレコード
に使用される。

ＡｒｇＲｅｃは改行アルゴリズムに対する引き数である
機械依存レコードである。これが機械依存であるのはレ
コード内の数フィールドは可能な場合、メモリの１ワー
ド中に実装されるからである。

レコード中の最初のフィールドはテキストと呼ばれ、処
理されるトークンのアレイを表わす記述子である。記述
子はメモリの３ワードを占め、そのうち最初の２ワード
は第１のトークンに対するポインタより成り、最後のワ
ードはアレイの長さを定義する。

フィールドｐｒｏｐｓＢａｓｅはコード化Ｔｅｘｔアレ
イのトークンエントリー中に埋込まれたポインタの相互
関係を明らかにするために使用されるベースアドレスで
ある。コード化テキストの一節の一例としては第２図を
参照されたい。ｐｒｏｐｓＢａｓｅの後にはハイフネー
トと称されるプールが来る。もしハイフネートがＴＲＵ
Ｅであれば改行アルゴリズムは行幅を横切るトークンを
ハイフン付けしようと試みる。さもなければ、アルゴリ
ズムは行幅におさまる最後の完全なトークンにまで戻る
。次のフィールドは処理中のフォントの書体、大きさ、
アクセント、重みを表わす。もしＡｒｇＲｅｃ中のフォ
ントのフィールドがトークンＰｒｏｐｓ中のフォントフ
ィールドの一つにマッチしない場合にはアルゴリズムは
無効Ｐｒｏｐｓの理由で復帰する。フォント後のフィー
ルドはマージンで行幅（ｍｉｃａ）である。

ＡｒｇＲｅｃ中の次の２フィールドはｈｙｐｈｅｎＰｉ
ｘｅｌＬｅｎｇｔｈとｍｉｎｓｐａｃｅＰｉｘｅｌ　Ｌ
ｅｎｇｔｈである。これらはそれぞれハイフンの幅とス
クリーン装置（ピクセル）中に入ることのできるスペー
スの最小幅を定義する。次の２つのフィールドはハイフ
ンの幅とスペースの最小幅（ｍｉｃａｓ）である。

ｗｈｉｔｅＳｐａｃｅフィールドはスペースの最大寸法
（ｍｉｃａｓ）を定義する、改行判断を行う場合にはｍ
ｉｃａ尺度しか使用されないためにスペースの最大寸法
をピクセルで定義する必要もない。

ＡｒｇＲｅｃにおける最後の２つのフィールドはｆｉｎ
ａｌとｐｒｉｏｒと呼ばれる。これらは両方ともＬｉｎ
ｅＢｒｅａｋの例である。これらのフィールドはメサ記
法ではそれぞれａｒｇ．　ｆ　ｉｎａｌとａｒｇ，　ｐ
ｒｉｏｒと称されることになろう。これらレコード中の
値は一時的に記憶し改行判断を行う際の結果を記録する
ために改行アルゴリズムによって使用される。ａｒｇ．
　ｐｒｉｏｒ中の値は現在のテキストブロック中に通さ
れる最後の区切り点を表わす。同様にして、ａｒｇ．　
ｆｉｎａｌは現在の改行アルゴリズム出口前に処理され
た最終トークンについてのデータを含む。もし改行判断
が下されると、ａｒｇ，　ｐｒｉｏｒ中の値は現在行末
の値を含み、ａｒｇ．　ｆ　ｉｎａｌ中の値は次の行を
開始するための値となる。

ＬｉｎｅＢｒｅｃｋ．　Ｓｔａｔｅレコード中の最初の
フィールドは指標である。これはｅｎｃｏｄｅｄＴｅｘ
ｔの開始に対する現在トークンの指標である。ｍｉｃａ
ＬｅｎｇｔｈとｐｉｘｅｌＬｅｎｇｔｈは現在行に割当
てられたトークンのそれぞれｍｉｃａｓとピクセルの累
積幅である。これらは特に現在テキストブロックにおけ
るトークンの累積幅ではないことに注意されたい。次の
フィールドは現在行上で出会うブランクのカウントであ
る。ブランクの後はカウントはｎｏｔＰｕｎｃｔｕａｔ
ｉｏｎと呼ばれるプールである。このフィールドは最後
のトークンが句読点であるか否かを示す。このフィール
ドは一行内の適法な区切り点の位置を判断するために使
用される。ｓｕ　ｆ　ｆ　ｉｘＣｈａｒは改行決定が行
われた後に行上にある最後の文字を表わすコードである
。ｓｕｆ　ｆ　ｉｘＣｈａｒの可能な値は先に列挙され
た型ＳｕｆｆｉｘＣｈａｒ中に定義されている。ｂｙｔ
ｅＣｏｕｎｔフィールドは現在行に割当てられたトーク
ン中のバイトの総数である。最終フィールドＷｈｉｔｅ
Ｓｐａｃｅは改行判断を行なう時に改行アルゴリズムが
その行に割当てることのできる白地スペースの最大量で
ある。

ＡｒｇＨａｎｄｌｅ，　ＡｒｇＳｐａｃｅ，およびａｒ
ｇ　Ａｌｉｇｎｍｅｎｔはページ境界の横断を回避する
ようにＡｒｇＲｅｃをメモリ内に整合させるために必要
とされるデータ構造を規定する３つの型である。この不
変式はゼロックス６０８５ワークステーションにおける
マイクロコード実行によって使用される最適化である。

ＡｒｇＲｅｃは２３ワード長であるから、レコードはペ
ージ境界を横断しないようにするため、３２ワードの境
界からスタートする必要がある。ＡｒｇＳｐａｃｅは５
５ワード長のメモリブロックを定義する。そのためその
範囲に３２ワードの境界が存在し、境界の後に十分なス
ペースが残りレコード全体を含むことができる。Ｌｉｎ
ｅＢｒｅａｋ，　Ａｌｌｇｎ　Ａｒｇ　Ｒｅｃは引き数
として５５ワードのメモリブロックのうちの一に対する
ポインタをとり、ブロック内に含まれる３２ワード境界
に対するポインタを復帰させる。

ＬｉｎｅＩｌｒｅａｋ．ＳｏｆｔｗａｒｅＬｉｎｅＢｒ
ｅａｋとＬｉｎｅＢｒｅａｋ．ＬｉｎｅＢｒｅａｋは次
節で定義するＭｅｓａ　　改行アルゴリズムのマイクロ
コードバージョンを定義する。２つの手順は同一の結果
に復帰し、相異は後者が６０８５に対するカスタム機械
命令として実行される点である。これら手続の両方に対
する引き数はＡｒｇＲｅｃに対するポインタで双方とも
ＬｉｎｅＢｒｅａｋ．　Ｒｅａｓｏｎに復帰する。

第６図はファイルＬｉｎｅＢｒｅａｋｉｍｐｌ．　ｍｅ
ｓａの内容である。このファイルはインターフェースＬ
ｉｎｅＢｒｅａｋの実行を供給する。ファイルのＤＩＲ
ＥＣＴＯＲＹ部中の名称のリストはＬｉｎｅＢｒｅａｋ
ｉｍｐｌ中に照会されるインターフェースファイルの名
前を宣言する。次の原始文中ではＬｉｎｅＢｒｅａｋｉ
ｍｐｌは、インターフェースＰｒｏｍｅからのサブプロ
グラムを使用し（ＩＭＰＯＲＴＳ）、インターフェース
ＬｉｎｅＢｒｅａｋを介してプログラムを共有（Ｅ！Ｘ
ＰＯＲＴ３）するプログラム（以前のような定義ファイ
ルでない）として宣言する。一定のｎｕｌｌＤａｔａｆ
Ｊ＜　ＰＲＯＧＲＡＭ文の直後に宣言される。

改′−アルゴリズム ＳｏｆｔｗａｒｅＬｉｎｅＢｒｅａｋはａｒｇｕｍｅｎ
　ｔａｒｇ．中に格納されたマージンに基づく行末を計
算する。プログラムは同一行中に一つ以上のテキストブ
ロックを必要とする場合を取扱うように設計されている
。設計はそのプログラムを使用するアプリケーションが
テキストを格納するために使用する方法からも独立して
いる。主要手順は４個の入れ子形サブプログラムを含む
ように組織される。

ＷｈｏｌｅＷｏｒｄＢｒｅａｋはワード全体の終りもし
くはスペースで終行判断が行われるときに使用される論
理である。ＷｈｏｌｅＷｏｒｄＢｒｅａｋはａｒｇ．　
ｆｉｎａｌ中のデータを初期化して現在行を終了するも
のの後にトークンの開始を照会する。この手順はＩＮＬ
ＩＮＥ手順と宣言され、短い手順についてより良好な動
作を意味するマクロとして処理されることを示す。

ＳａｖｅＴｈｉｓＢｒｅａｋはａｒｇ．　ｆ　ｉｎａｌ
の内容をａｒｇ，　ｐｒｉｏｒへ転送する手段である。

もしトークンを現在行に追加することができない場合に
も論理はａｒｇ．　ｐｒｉｏｒ中の値に復帰する必要が
ある。この手続はまた動作上ＩＮＬＩＮＥと宣言される
。

ＰｒｏｃｅｓｓＳｐａｃｅは現在スペースが行上にフィ
ットするかどうかを見るためにチェックする。もし否で
あれば、処理は終了し、ルーチンはＴＲＵＥ値に復帰す
る。もし、現在スペースがフィットすれば、ａｒｇ．　
ｆ　ｉｎａｌ中のデータは現在点における値を反映する
ように修正され、この場合、ルーチンはＦＡＬＳＥ値に
復帰する。また、ＰｒｏｃｅｓｓＳｐａｃｅは動作を最
適化するためのマクロとしても取扱われる。

ＨｙｐｈｅｎａｔｅＷａｒｄはマージンがトークンニヨ
リ横断される時に実行される副手続である。もし処理さ
れた最後のトークンが句読点文字でない場合にはアルゴ
リズムはｕｎａｂｌｅＴｏＢｒｅａｋ出口節へ分岐する
。この出口のための理由はｕｎａｂ　ＩｅＴｏＢｒｅａ
ｋにセットされる。この前後関係によりスペースは句読
点文字と考えられる。同様にして、もし選択すべき区切
り点がなかったり現在のテキストブロックに対してハイ
フネーションが選択されない場合には、アルゴリズムは
分岐を経てｎｏｎｅＦｉｔｓＥｘｉｔ節へ退去する。も
し、この通路が実行されると、処理される最後のトーク
ンは区切り点として選ばれ、ｆｉｎａｌの値は手続Ｗｈ
ｏ　］ｅＷｏｒｄＢｒｅａｋにより初期化される。

この時点でアルゴリズムはハイフネーション点が退去し
、区切り点の一つを選ぶのが適当であることを判断した
。メインループ内に入る前に２個の変数が初期化される
。第１の変数は区切り点アレイのエレメントのポインタ
である。この変数は区切られるトークン中の区切り点ア
レイの第１のエレメントを指示するように初期化される
。第２の変数は最後のトークン部分を含むテキストが白
地スペースの制約を満足するためにとらねばならない最
小の幅である。

ＨｙｐｈｅｎａｔｅＷｏｒｄ中のメインルーブはリスト
内の区切り点から最良の区切り点を選択する。アルゴリ
ズムは区切り点を２つのキーからソートすることを要求
する。即ち、優先下降順（いいかえれば最も望ましい区
切りが最初に来る）で各優先階級内、トークン内の低下
位置順。この順序によってアルゴリズムは区切り点上を
一回パスしただけで最適の区切り点を発見することがで
きる。最適な区切り点は最高優先度を有するものであり
、その結果、行に対して最もきっちり納まることになる
。

３つの例外のためアルゴリズムは最高優先順位と最もき
っちり納まるという基準に基づいた区切り点を選択しな
くなる。第１の例外は区切り点が選択された場合にリス
ベリングを必要とするドイツ語の如き特殊事例の区切り
点についてのものである。第２の例外は手で挿入される
、即ち「ハードな」ハイフンが存在する場合である。そ
の場合には手で挿入されるハイフンはそれが最もぴった
りと納まるかどうかで選ばれる。第３の例外は区切り点
が全て大きすぎる場合、即ち、何れも少なくとも最小の
白地スペースをもたない場合であり、その場合にはアル
ゴリズムは区切り点を選択せずに終了し、先のトークン
の境界は行の終結用に使用される。

適当な区切り点が選択されると、ＨｙｐｈｅｎａｔｅＷ
ｏｒｄはｓｕｃｃｅｓｓＥｘｉｔ節を経て退去する。節
の４つの文はａｒｇ．　ｆ　ｉｎａｌとａｒｇ．　ｐｒ
ｉｏｒｆ　ｉｅｌｄをそれぞれ更新し、選択された区切
り点を反映するようになる。次にａｒｇ．　ｆ　ｉｎａ
ｌは新行を開始するトークン部分を表わすように更新さ
れる。ａｒｇ，　ｆｉｎａｌが更新される方法は選択さ
れたハイフネーション点のタイプに依存する。もし区切
り点が区切り点論理によって発生させられる合成ハイフ
ンである場合には、／Ｓイフンは実際にはトークンの一
部ではないから調節する必要がある。合成ハイフンでは
ない最も一般的なハイフンはハードハイフンである。

行を終らせるために任意の形の７１イフンを選んだ場合
、ｍｉｃａＬｅｕｇｔｈ，　ｐｉｘｅｌＬｅｎｇｔｈ，
　ｂｙｔｅｃｏｕｎｔは全て先の行を終らせるトークン
部分を表わす負数を付与される。索引の値は同一のトー
クンが次の行を開始するように変化しないまま留まる。

ａｒｇ．ｆｉｎａｌ中の負値がトークン全体に対する値
に追加される場合、結果は新しい行を開始するトークン
部分にとって適当な値となる。

Ｓｏｆ　ｔｗａｒｅＬｉｎｅＢｒｅａｋの主要部分はａ
ｒｇ．　ｆｉｎａｌとａｒｇ．ｐｒｉｏｒに対するポイ
ンタの初期化とともに開始される。メインループはａｒ
ｇ．　ｆ　ｉｎａｌ索引が現在テキストブロック、ａｒ
ｇ，　ｔｅｘｔの長さより短いか等しい限り実行される
。ａｒｇ．　ｔｅｙｔ中の各トークンエントリーに対し
て行われる処理はトークンエントリーの型に依存する。

もし型がトークンエントリーであれば、バリアント選択
文のトークン分岐内の最初の文は処理を加速化するため
に回り道レベルの幾つかを照会する。次に、このテキス
トブロックに対して希望されるフォントはアトム作成法
を計算するために最後に使用されたフォントと比較され
る。もしフォントが不正確であれば、メインループはｉ
ｎｖａｌｉｄＰｒｏｐｓ節を通って退去し、そのため今
度はｉｎｖａｌｉｄＰｒｏｐｓの理由で手順からの復帰
が惹起される。これは発呼者にトークン属性を計算しな
おし手続を再開する機会を与える。もし、属性が依然有
効であれば、トークン全体が現在の行上に納まるかどう
かの計算が行われる。もし、そうでなければループはｍ
ａｒｇ　ｉｎＥｘ　ｉ　ｔ節を経て退去し、ハイフネー
ションが試みられる。もしトークンが納まれば、スペー
スか句読点なくアルゴリズムが２の連続トークンに出会
ったかどうかについてのチェックが行われる。もしそう
であれば、ループはｃｏｎ　ｔ　ｉｇｕｏｕｓＥｘｉｔ
節を通って退去する。

この時点では現在のトークンが行上に納まり同行に追加
できるということが判断されたところである。次のメイ
ンループの４行はａｒｇ．ｆｉｎａｌを更新してこれを
反映させる。節中の最終行はこのトークンについてｓｐ
ａｃｅＦｏｌｌｏｗｓのプールがＴＲＵＥであるかどう
かをチェックする。もしそうであれば、Ｐｒｏｃｅｓｓ
Ｓｐａｃｅの副手段が実行される。もしスペースが行上
に納めらなければハイフネーションが不要であることは
明らかであるからメインループはｓｉｍｐｌｅＭａｒｇ
ｉｎＥｘｉｔを経て退去する。もしスペースが納まれば
、選択文のト．−クン分岐は退去して、ｆｉｎａｌ．　
ｉｎｄｅｘは増分され、テキストブロック内の次のエン
トリーが処理される。

テキストエントリーがＴｏｋｅｎ．　Ｅｎ　ｔｒｙレコ
ードの拡張文字バリアントであればメインルーブ内のパ
リアント選択分の他の分岐が実行される。第１図に記述
されている通り、拡張文字バリアント自体はパリアント
レコードである（Ｍｅｓａ中の匿名レコードと称される
）。

それ故、選択文の拡張文字アトムは選択文でもある。先
に述べた如く、このレコードの３つのバリアント（変数
）はスペースとＺｅｒｏＷｉｄｔｈＳｐａｓｅと、ｃｈ
ａｎｇｅＢａｓｅである。

スペースバリアントの処理はＰｒｏｃｅｓｓＳｐａｃｅ
サブルーチンを実行することから成る。もし、スペース
が行上に納まらない場合は、メインループはｓｉｍｐｌ
ｅＭａｒｇｉｎＥｘｉｔ節を経て退去する。ＺｅｒｏＷ
ｉｄｔｈＳｐａｓｅに出会うと、ｆｉｎａｌ．　ｓｕｆ
ｆｉｘＣｈａｒがこれを反映するために更新される。行
上の現在位置は次のトークンが納まらない場合は実行可
能な区切り点にされる。ｃｈａｎｇｅＢａｓｅ拡張文字
はｃｈａｎｇｅＢａｓｅ退去節を経てメインループから
の退去をひきおこす。

発呼者はａｒｇ．　ｐｒｏｐｓＢａｓｅを含む必要なデ
ータ構造の全てを更新するから他の処理は不要である。

もし拡張文字エントリーに対する処理が退去が実行され
ることなく完了すると、節は退去させられ、ｆｉｎａｌ
．　ｉｎｄｅｘは増分され、次のテキストエントリーの
処理が開始される。

もし、テキストブロック全体が終行判断を行わずに処理
されると、手続は主ループのＦＩＮＩＳＨＥＤ退去節を
経て退去する。

第８図は第４図中のテキストの処理の開始に先立つａｒ
ｇＲｅｃ中の値と、その後計算された最初の３行の各々
の後のａｒｇＲｅｃ中の値を示す。第１の事例では、テ
キストの値は第２図内のコーディングを表わす記述子で
ある。値は簡単にするために削除されたところである。

フォント、マージン、ハイフンＰｉｘｅｌＬｅｎｇｔ　
，　ｍｉｎｓｐａｃｅＰｉｘｅｌＬｅｎｇｔｈ，　ｈｙ
ｐｈｅｎＭｉｃａＬｅｎｇｔｈ，　ｍｉｎＳｐａｃｅＭ
ｉｃａＬｅｎｇｔｈ及びｗｈｉｔｅＳｐａｃｅの値は１
０ポイントセリフフォントについて全て認定される。ｆ
ｉｎａｌとｐｒｉｏｒの値はトークンが処理されていな
いため全て最初の零値にセットされる。

第８図中のａｒｇの第２の値は第１行が計算された後の
ａｒｇ値に担当する。ｆｉｎａｌとｐｒｉｏｒの値だけ
が変化したところである。ｆｉｎａｌ索引とｐｒｉｏｒ
索引は第１行上の最後のトークンがハイフン付けされて
いるため同一である。第２図中では１０番目のエントリ
ー（最初のエレメントを０番とじた場合）はトークン“
ｄｏｃｕｍｅｎｔ”に相当することに注意されたい。ａ
ｒｇ．　ｐｒｉｏｒ中の値は最初の１０個のトークンと
“ｄｏｃｕ”を通る第１１番目のトークン部分とをプラ
スしたものに等しい。ａｒｇ，　ｆ　ｉｎａｌ中の負数
はａｒｇ．ｐｒｉｏｒの値中に含まれる最終トークン部
分にのみ相当する。これらの値を次行の最初のトークン
に加えたばあい（それは、ワード“ｄｏｃｕｍｅｎｔ”
全体の値に等しくなろう）、ワードの適当な部分、“ｍ
ｅｎ　ｔ”が行値に加えられる結果となる。このことは
第１４図にグラフ表示してある。改行判断がｌトークン
を２行にわたって分割することを必要とするぱあい、同
一のトークンを２回処理することによって、Ｓｏｆｔｗ
ａｒｅＬｉｎｅＢｒｅａｋを呼ぶコードはハイフネーシ
ョンが起こったかどうかとは大部分独立な論理で書込む
ことができる。

この不変性のためすこぶる効率的なページネーションコ
ードが得られる。

第２行が計算された後、ａｒｇ中の値は第８図中の第３
のａｒｇ値における値となろう。このブロックではマー
ジンの値は変化して第２行が字下げされていないことを
反映することを注意されたい。

第２行はハイフン付けされないため、ａｒｇ．　ｆ　ｉ
ｎａｌ索引の値とａｒｇ，　ｐｒｉｏｒ索引中の値とは
異なる。このことがふさわしいのは第２行がトークン’
ｅａＣｈ″であるエントリー２１で終了するが第３行は
エントリー２２“ｕｎ　ｉｑｕｅ″で開始されるためで
ある。

第２行の最終トークンはハイフン付けされていないから
、第１行の場合に存在するような行間の繰越し値は存在
しない。それ故、この時点でのａｒｇ．ｆｉｎａｌの他
の値は全て零である。

第８図内のａｒｇの最終値は第４図の第３行に相当する
。この行は完全なトークンにより開始され完全なトーク
ンと共に終了した。

第１７図はＣプログラミング言語で書かれた第１図、第
３図、第５図、第６図におけるプログラムの等価図であ
る。このプログラムはモデル３／５０の如きサンマイク
ロシステムミニコンピュータ３、４ファミリーの何れの
メンバーも含めて、Ｃコンパイラを提供する任意のコン
ピュータで実行することができる。このコードもまたＤ
ＥＣ　Ｖａｘ７ｘｘファミリーとｍｉｃｒｏ　Ｖａｘコ
ンピュータで実行された。

表六アルゴリズム 改行アルゴリズムと表示アルゴリズム間には２つの主な
相異がある。先ず、どこに行末があるかを判断するため
にトークン作成法を蓄積するよりも、この情報は先に計
算して表示アルゴリズム内へ通さなければならない。ト
ークン数（も，シ＜はトークン部分の数）と累積計測情
報に関する情報は表示プロセスの初めに必要になる。こ
の情報はジャスティフィケーションが望まれる場合にト
ークンの配置について適当な調節を行うことができるた
めに必要なものである。同様に、一定のテキストフォー
マットモードが望まれる場合に、表示アルゴリズムは最
初のトークンが表示される以前に彩色されるトークンの
幅をそれに対して利用可能にしなければならない。例は
不調和な左モードと、テキストが欄、ページもしくは任
意の尺度上に集中したモードである。第２の相異は表示
アルゴリズムがＴｏｋｅｎＰｒｏｐｓ．Ｔｒａｉｌｅｒ
Ｏｂｊｅｃｔ　（第３図）中のＲａｓｔｅｒＤａｔａに
アクセスしてテキストの１行の表示ビットマップを蓄積
する点である。このことは大抵の機械のラス処理サポー
トに類似したゼロックス６０８５ワークステーションの
旧ｔＢｌｔ機械命令（パイロットプログラマー用便覧、
ゼロックス社、１９８５年）を用いて行う。この命令が
原始ビットマップについて使用するビットマップの記述
は幅とビットマップ内へのビットオフセ，ソトの両方を
含む。これらパラメータは、トークンが通常ハイフネー
ションによって２行間に分割される時、トークンビット
マップの一部のみを彩色することを可能にする。トーク
ンビットマップの幅が３０ビットで、トークンが区切り
点１７ビットでハイフン化された映像になる例を考えて
みよう。

区切り点に先立つ映像部分を彩色するためには、幅は１
７にセットされ、オフセットは０となろう。

区切り点後の部分を彩色するためには、幅は３２マイナ
ス１７もしくは１５ビットとなり、オフセットは１７ビ
ットとなろう。このことが何時重要となるかの例につい
ては第４図の第２行と第１４図を参照されたい。

さてテキストを１回に１トークン彩色することは１回に
１文字彩色する同じプロセスと比較することができよう
。両方の場合とも、フォント（あるいはテキスト映像）
情報の同じビット数がディスプレイに渡されるが、１回
にｌトークンの場合の方が動作は相当高速である。動作
の差異は（システム）ディスプレイビットマップを格納
するメモリの各ワードがアクセスされる必要されねばな
らない回数が少ない結果である。メモリ照会数はテキス
トが１回に１文字表示される場合にはずっと多い。典型
的な文字ビットマップの幅は文書本文テキスト（即ち、
見出しや脚注の如き特殊機能には使用されないテキスト
）に通常使用されるフォントサイズについては４〜６ビ
ットオーダである。このことは１６ビットのワード長を
有する機器の場合には、ディスプレイメモリの各語は３
〜４回アクセスされるが、隣接文字（テキストの１ワー
ドの場合のように）のビットマップはディスプレイビッ
トマップ中に書込まれることを意味する。もし機器が３
２ビットのメモリワード長を有する場合にはメモリの各
ワードは映像が組立てられる間６〜８回アクセスされる
ことになろう。

テキストを１回に１文字彩色する場合と１回に１トーク
ン彩色することとの性能の相異はテキストが幾つかの文
字もしくは文字部分を余分に打つ必要のある文字を含む
場合には更に重要になる。

このことが生ずる場合の例は普通フォント中には含まれ
ないアクセントをつけた文字や数学記号である。いった
ん、これら特殊文字や記号の映像が発生してトークン属
性中に挿入されると、それらはフォントが変化しない限
り再使用できる。

又１旦至正 さて出版業務に使用されるＷＹＳＩＷＹＧ文書エディタ
に本発明を適用した場合について説明する。本発明は他
のテキスト処理業務にも使用することができよう。本シ
ステムにより処理される文書はテキスト断片を点在させ
たフォーマット命令（組み指定）より成るエレメント系
列より成る。テキストの断片自体はトークン系列である
。文書中の各エレメントはピースと呼ばれ、データ構造
全体はピーステーブルと呼ばれる。Ｔｏｋｅｎ．　Ｂｎ
ｔｒｙベクトルを表わすピース（従ってテキストである
内容を備える）はテキストピースと称する。文書の修正
を容易にするために個々のピースはポインタと両方向に
リンクされる。

セレクション ユーザはテキストの一部分を識別しＷＹＳ　ＩＷＹＧエ
ディタもしくはテキスト処理システム中で通常実行され
る編集操作の一つを発動することによって文書を修正す
る。処理されるテキスト部分はセレクションと呼ばれる
。セレクションは１文字ぐらいの小ささの文字と、一連
の隣接文字もしくはワード、あるいは文書全体の規模か
ら構成することができる。セレクションは通常、テキス
トの外形を変化させることによって示される。高解像度
スクリーンを有するシステムで望ましい方法はセレクシ
ョンを逆ビデオで表示することである。

開始と終了を有する外に、セレクションは挿入点も有す
る。それは通常セレクションの終りにあるがその初めに
もってくることもできる。挿入点は明滅する挿入記号（
Δ）で識別される。挿入点を含むピーステーブルエント
リーは入力焦点と定義される。視覚的に入力焦点がテキ
ストのみにつけられているように見える場合でも、挿入
点を実際には命令を含むピーステーブルエントリーにつ
けることは全く可能である。

ユーザがセレクションに対して実行できる操作はそれを
削除したり、挿入点で開始される１つもしくはそれ以上
の文字もしくはワードだけバックスペースさせたり、挿
入点後に文字を追加することである。ワード単位でバッ
クアップすることはバックワード操作と称する。何れの
場合も、本発明により表示されるテキストを処理するア
ルゴリズムは一連の文字としてコーディングされた文書
を処理するための等価アルゴリズムよりも幾分異なって
いる。

いったん上記操作のうちの一つがセレクションについて
実行されると、そのセレクションは非活性化する。この
ことは操作後にセレクション中のテキストの強調を解除
することによってユーザに示される。

圀邂１」！ととλ汝 テキストの一部は座標情報をポインティング装置から文
書内の位置へ変換することによって選択される。このプ
ロセスは文書内の位置を分解すると呼ばれる。殆んど全
ての会話形式ＷＹＳ　ＩＷＹＧシステムがある形式のポ
インティング装置を備えている。最も普通にはポインテ
ィング装置はマウスである。それよりずっと少ないが一
組のカーソルキーがそれに次ぐ。

ポインティング装置は装置の活動中に規則的な間隔で座
標情報を提供する。座標情報を文書内の一位置へ変換す
るプロセスは本発明によって容易にすることができる。

解像アルゴリズムは３つのフエーズで進行する。

まづ、座標を含むテキストの行が位置指定される。

次に特定のトークンが識別される。そして最後に文字が
位置指定される。エディタはどのテキスト行が新たな座
標を含むかを判断するためにソフトウエアを分解する何
らかの方法を提供する必要がある。典型的にはこのこと
は行ボックスのテーブルによって行われる。行ボックス
を記述する情報は行の位置（もしくは向き）、行の寸法
、および行上の最初のトークンの開始オフセットである
。

いったん行が位置指定されると、分解アルゴリズムは行
内のトークンを列挙してどのトークンに座標が配置され
ているかを判断することができる。

この時点で個々の文字を点検してどの文字中に座標があ
るかを判定することができる。

行ボックスのテーブルはエディターの設計が多数行設定
モードをサポートする場合には不可欠である。もしテキ
ストが幅の変化するスペースで組まれているかテキスト
が欄の左側に沿って整列していないならば、スペースの
数と幅に関する情報もテーブル内に含める必要がある。

高速プロセッサの場合、行テーブルを適当なページをｎ
番目の行につけることによってｎ番目の行ボックス内の
情報を復帰させるページネーション論理に対する手続イ
ンターフェースを取替えることが可能である。

従来そうであったように１度に１文字ではなく１度に１
トークンだけ行全体を進むことによって、分解プロセス
はずっと高速に進行する。特に、１文字毎に１バイトで
表現できない国際テキストもしくは数学テキストの如き
複合テキストの場合には、ここで述べる方法は相当高速
であろう。

削７、アルゴリズム トークンの系列としてコーディングされた文書の一部を
削除するアルゴリズムはピーステーブル中に格納された
文字列として格納されたテキストを削除するアルゴリズ
ムに非常に似ている。一般的な場合、削除は、セレクシ
ョン内の最初と最後の文字が同一のビーステーブルエン
トリ中にないような１文字以上より成るセレクションに
対して行われる。最も簡単なケースはセレクションの開
始がスペース直後（トークンの開始）であったり、同様
に、セレクションの終りがスペースの直前にある場合で
ある。この場合、削除の結果として新たなトークンぱつ
くりだされないが、セレクションの開始と終了がテキス
トの同じピース内にあるかどうかに応じて２つほどのピ
ースがつくりだされる。セレクション直後のスペースの
コーディングはもしセレクションの最終トークン内のｓ
ｐａｃｅＦｏｌｌｏｗｓブールを使用してコーディング
される場合ニハ、Ｔｏｋｅｎ．　Ｅｎｔｒｙのスペース
拡張文字バリアントに対して変化される必要があろう。

もしセレクションの一端が最初もしくは最後のトークン
の内部文字の一つに該当するならば、新たなトークンが
削除より生ずることになろう。もしこの場合が起きると
、ｃｈａｎｇｅＢａｓｅ　ｅｓｐａｃｅ　Ｔｏｋｅｎ．
Ｅｎｔｒｙをその結果生ずるピースに追加して新たなト
ークンの各々のベースアドレスを反映させる必要がある
かもしれない。

第１５図中のテキストは先に第４図に示したものと同じ
テキストを含む。テキストのハイライト部分はセレクシ
ョンが削除された時に幾つかの新たなトークンがつくり
だされることになるセレクションを表わす。最も一般的
なケースを明らかにするために、新たなトートンは現存
するトークン（ベースアドレス番号ｌ）用に使用される
領域よりも異なるメモリ領域内に配置されるものと規定
する。削除の結果、１つはセレクションに先立つテキス
ト部分に対するもの、他はセレクション後の部分の別個
のピースの２つのピースが生ずることになろう。第２図
は削除前のパラグラフの残存部分に対するピーステーブ
ルエントリーを含む。

第９図はテキストの最初の断片の初めと終りを示す。（
ピースの紛失部分は第２図のピース部分に相当する。）
　ｃｈａｎｇｅＢａｓｅ　ｅｓｐａｃｅ　Ｔｏｋｅｎ．
Ｅｎｔｒｙが必要とされるのは新たなトークンが他のト
ークンが存在する同じトークン属性領域内にないためで
あることに注意されたい。第１０図は第２のピーステー
ブルエントリ内のトークンを示す。

新たなトークンの前には、ｃｈａｎｇｅＢａｓｅ　ｅｓ
ｐａｃｅＴｏｋｅｎ．　Ｅｎｔｒｙが来る。ベースアド
レスを残りのトークンのために使用される第１のアドレ
ス空間へ戻すためにこのピース内には第２のベースアド
レス変更が必要である。

正　　なＴｏｋｅｎ．　Ｅｎｔｒ　　アレイとトークン
　性ビーステーブルエントリー（およびエントリの内容
）は格納必要条件を最小にするために普通は固定長でし
る。バックスペースとバックワードは全て挿入点を含む
ピーステーブルエントリの内容を変化させる、修正され
た内容に対して新たなスペースを割当てたり、入力焦点
の内容を新しいスペースにコピーしたり、新たなピース
の内容を更新して変化を反映させたり、旧内容の配分を
解除したりすることは各操作の後には実際的ではない。

これらの操作を反復して行うとダイナミックメモリが断
片化して性能が不十分になる。この断片化を回避する道
は変更容易な過渡電源を識別することである。殊に任意
の長さの予め配分したＴｏｋｅｎ．Ｅｎｔｒｙアレイで
あればこれらの操作の一つが選択された時に実際のピー
スの内容と取替えることができよう。

さて、アレイの長さはその変化を反映するために各操作
の終りに簡単に調節する必要がある。修正可能なエント
リーアレイを必要とする第１の操作が発動されると、入
力焦点の内容は修正可能なエントリーアレイ中にコピー
され修正可能な内容に対する基準は入力焦点内に配置さ
れる。その後、編集アルゴリズムが発動される。入力焦
点の内容はある事象が修正可能ピースに対するそれ以上
の操作が起こり得ないということを告知するまで修正可
能スペース領域内にとどまる。この性質の事象はユーザ
が文書に対する編集セッションを終了したり、セレクシ
ョンを別の文書部分へ移動させたりすることを含む。最
後の編集が行われた後、入力焦点内に残存する内容は何
れも新たなスペースを配分し、修正可能スペースの内容
を新たなスペース内へコピーし、新スペースに対する基
準を入力焦点内に配置することによって永久的なものに
なる。

また、挿入とバックスペースも高速動作中にトークン属
性を繰返し配分し配分解除することにより生ずる同様な
性能上の問題を回避するために修正可能なトークン属性
を必要とする。修正可能トークン属性スペースに対する
基準は最初の挿入もしくはバックスペースが発動された
時に修正可能Ｔｏｋｅｎ．　Ｅｎｔｒｙアレイ中の最後
のトークンバリアントと取替えられる。その後、修正可
能トークン属性の内容は操作の順序に応じて永久属性ス
ペースへ廃棄されるか転送されるかする。このことは以
下に詳説する。

修正可能Ｔｏｋｅｎ．　Ｅｎｔｒｙアレイの長さは限定
することができる。一般的にいって、１０００個のトー
クンの長さは滅多に使い尽くされることはな《、この長
さは実施上殆んど制約を課すことはない。

修正可能トークン属性スペースは製作が可能な区切り点
の最大数を維持するに十分な長さであればよい。

規約により、修正可能なトークン属性スペースはベース
アドレス零において１だけずれているものと定義される
。この規約は以下の編集アルゴリズムにおいて使用され
ることになろう。

バックスペース バックスペース操作が発動されると、アルゴリズムは入
力焦点のどちら側の端に挿入点が位置するかをチェック
する。もし挿入点が入力焦点の右側にあれば、アルゴリ
ズムは次のステップへ進む。

挿入点が入力焦点の左側にあれば、入力焦点はテキスト
を含む次の前のピーステーブルエントリへ移動する。挿
入点は入力焦点の右側に移動する。

もし以前のテキストピースが存在しなければアルゴリズ
ムは終了する。

次に、入力焦点の内容が修正可能エントリーアレイ中に
コピーされたかどうかについてチェックを行う。もし入
力焦点の内容がコピーされると、最後の文字を削除する
アルゴリズム部分が発動される。さもなければ、入力焦
点の内容は修正可能Ｔｏｋｅｎ．　Ｅｎｔｒｙアレイ内
ヘコピーされる。このプロセスにおける最初のステップ
は入力焦点内のテキストのアドレスを修正可能エントリ
ーアレイのアドレスを取替えることである。さて、アル
ゴリズムは進行して文字を削除する。

いったん入力焦点の内容が修正可能Ｔｏｋｅｎ．　Ｅｎ
ｔｒｙアレイにコピーされると、アレイ内の最後の内容
を担うエントリを位置指定することによってバックスペ
ースアルゴリズムが開始される。内容を担うエントリー
は、ｃｈａｎｇｅＢａｓｅバリアントではないＴｏｋｅ
ｎ．　Ｅｎｔｒｙである。アルゴリズムは最後のアレイ
エレメントと共に開始されそれぞれの継起エレメントを
点検しながら後方へ進む。コノプロセスは最初の内容を
担うエントリーが位置指定されたとき終了する。そのエ
ントリーが、ｓｐａｃｅ　ｅｓｃａｐｅＴｏｋｅｎ．　
Ｅｎｔｒｙであれば、トークンアレイは一つだけ短くな
りスペースを削除する。その後、アルゴリズムは一文字
が削除されたために終了する。同様にして、内容を担う
エントリーを求めて走査によりつきとめられたエントリ
ーがｓｐａｃｅＦｏｌｌｏｗｓプールがＴＲＵＥにセッ
トされたＴｏｋｅｎ．　Ｅｎｔｒｙであれば、文字を削
除．する作業はプールをＰＡＬＳＨにセットすることよ
り成る。最後の内容を担うエントリーが除去されずに変
更されただけであるから、入力焦点の内容は同一のまま
である。

最後のケースは最後の内容を担うエントリーがＴＲＵＥ
にセットされたｓｐａｃｅＦｏ　Ｉ　ｔｏｗｓブールを
有しないＴｏｋｅｎ．　Ｅｎｔｒｙである場合である。

もし、最後のトークンに対する属性が既に修正可能なト
ークン属性エリア内になければ、内容はコピーされエン
トリーアレイは更新されてこれを反映する。全体として
、内容を担うエントリーは２つのエントリと取替えられ
る。第１のエントリーはｃｈａｎｇｅＢａｓｅｅｓｃａ
ｐｅ　Ｔｏｋｅｎ．Ｂｎｔｒｙでベースアドレスをゼロ
（修正可能トークン属性エリア）にセットし、第２エン
トリーはｌのオフセットを有するＴｏｋｅｎ．　Ｅｎｔ
ｒｙである。最後に、入力焦点の内容の長さは（通常長
さを１だけ増分することによって）更新される。

バックスペースアルゴリズムの最終部分は、修正可能エ
ントリーアレイの最終のエレメント修正可能トークン属
性エリアへ（先の操作から）既にコピーされたＴｏｋｅ
ｎ．　ＥｎｔｒｙであってｓｐａｃｅＦｏｌｌｏｗｓブ
ールが既にＦＡＬＳＥである場合に文字を削除するため
のプリシージャである。第１のステップは最後の論理文
字を除去するためにどれ位多くのバイトを削除する必要
があるかを判断することである。

アクセント付きの文字の如き国際文字は１バイトより長
いバイト順列で表現できる。もしその結果起こる削除が
トークン属性中のバイトを使い尽くさなければ、属性は
更新され、アルゴリズムは終了する。もし削除が区別さ
れたトークン属性エリア内でバイトを使い尽さなければ
、その区別されたトークンアレイの長さはｌだけ減り、
第１の先行する内容担持エントリアレイエレメントを求
めるプロシージャが実行される。

バックワード バックワードアルゴリズムの最初の２つのステップはバ
ックスペースアルゴリズムと同一である。

即ち、もし挿入点が入力焦点の左側にあると、次の先行
するピース含有テキストの内容が入力焦点としてセット
され、挿入点は新たな入力焦点の右側へ移動する。次に
、もし入力焦点の内容が修正可能エントリーアレイ中に
なければ、内容は修正可能アレイ中にコピーされ、修正
可能エントリーアレイに対する基準点は入力焦点中に配
置される。

一たび入力焦点の内容が修正可能エントリーアレイにコ
ピーされると、バックワードアルゴリズムはアレイ内の
最後の内容担持エントリーを配置する。このエントリー
はスペースであってはならない。次に、第２番目の走査
が開始され次の先行スペースもしくは句読点を位置指定
する。走査論理はーワードが２もしくはそれ以上の連続
するトークンに断片化されるか削除中のトークンが文書
内の最初のトークンである可能性を伴うべきである。

いったん逆方向の右境界が識別されると、続くトークン
の全ては修正可能トークンアレイの長さを調節すること
によって削除される。バックヮードアルゴリズムは常に
整数のトークンを除去するため新たなトークンぱつくり
だされない点に注意されたい。

挿ノ、 挿入アルゴリズムも修正可能エントリアレイを必要とす
るため、挿入アルゴリズムもまた入力焦点からどんな内
容が特別なエントリーアレイ中に移動されなければなら
ないかを判断することから開始される。もし挿入点が入
力焦点の左側にあれば、新たなピーステーブルエントリ
がつくりだされなければならず、入力焦点に先立ってテ
ーブル内へリンクされる必要がある。新たなビースは今
度は入力焦点とされ、挿入点はこめピースの右側へ移動
する。

もし挿入点が入力焦点の右側にあり、入力焦点の内容が
修正可能エントリアレイ内になければ、入力焦点の内容
はそこでコピーされ、修正可能エントリーアレイに対す
る基準点は入力焦点内に配置される。

さて、一文字を文書に追加することできる。実行される
論理は文字の種別による。基本的な類別はスペース、文
字、および句読点である。句読点はｌトークン中には決
して含まれない文字である。

これらはまた改行アルゴリズムに識別されてそれがどこ
に許される句切り点があるかを判断する上で助力する。

金融テキスト処理業務のように相当量の数値データが予
期されるような用途では、数値データを特殊な形で処理
する必要がある。数字は一義的、もしくは殆んど一義的
なものとなりがちであるから、このテキストをテキスト
にとって高度に効率的なものとする統計上の属性は実現
されないであろう。その結果、メモリが桁外れの実行時
間をもたなければならないすこぶる大きな文書となる可
能性が非常に高い。一つの選択肘肢は表データを正規の
テキスト連糸として取扱うか、数値データを含む特殊な
拡張文字バリアントをつくりだすことである。最初の文
字に出会った時、入力焦点中の最初のトークンが検査さ
れる。もしそれが修正可能トークン属性に対する基準点
でなければそれはピース末に追加される。これは通常、
入力焦点の内容を２だけ長くすることを伴う。修正可能
トークン属性を含むスペースを照会するｃｈａｎｇｅＢ
ａｓｅ拡散文字バリアントが追加されてその後に修正可
能属性を照会するＴｏｋｅｎ．　Ｅｎｔｒｙが続く。

作成法（ｍｅｔｒｉｃｓ）、区切り点データ、ディスプ
レイビットマップ、および文字アレイは全て零値に初期
化される。もし、アレイ中の最終エントリがｓｐａｃｅ
Ｆｏ　ｌ　ｔｏｗｓプールがＰＡＬＳＥにセットされた
トークンバリアントであれば、エントリーは修正可能ト
ークン属性に対する照会に必要とされる２つのエントリ
ーと取替えられる。この場合、修正可能属性の内容は初
期化されて取替えられたトークンの内容となる。

さて、文字が文字アレイに追加されて、フォント作成法
（ｍｅｔｒｉｃｓ）とビットマップの再計算を強制する
値にセットされる。全体として、新しいテキストのハイ
フネーションはハードウエアが非常に高速でない限り区
切り文字（即ち、スペースもしくは句読点）に出会うま
で遅らせることが望ましい。

第２とそれに続《（連続）文字の処理は第１の文字の処
理に必要とされるものの最終ステップだけから成る。即
ち、文字は文字アレイに追加され、トークン属性中のフ
ォントフィールドはｉｎｖａｌｉｄＰｒｏｐｓを改行ア
ルゴリズムから復帰させる特定値にセットされる。

文字（　ｌｅｔｔｅｒ）ではない文字（　ｃｈａｒａｃ
ｔｅｒ）が１つもしくはそれ以上の文字（　ｌｅｔｔｅ
ｒｓ）の後に入力されるか、入力操作が終了すると、修
正可能なトークン属性の内容は永久トークンに変換され
る。

新たなトークンは修正可能トークン属性前には最後のト
ークンと同じベースアドレスを有しないかもしれないか
ら、ｃｈａｎｇｅＢａｓｅ拡張文字は必要かもしれない
。

もし修正可能トークン属性に対する入力を終了させる事
象がスペースであれば、そのスペースは新トークン中の
ｓｐａｃｅＦｏ　Ｉ　ｌａｗｓプールと共にコーディン
グする必要がある。もしスペースが入力されても修正可
能トークン内に文字が存在しない場合には、スペース拡
張文字バリアントを使用する必要がある。同様にして、
もし１つもしくはそれ以上の文字が入力された後に句読
点が入力されると、修正可能トークン属性は句読点を処
理する前に永久属性へ変換する必要がある。

サーチアルゴリズム 全体として、ユーザは２つのストリングが同等であるか
どうかをアルゴリズムが判断するだろうという期待をも
ってテキストストリングをサーチする。同等であるとは
１ストリングに対するコーディングが情報を喪失せずに
他のストリングのコ−ディングへ変換できるということ
を意味するものと定義される。同様にして、テキストと
命令の組合せをサーチする場合、命令の順序とは無関係
に命令の意味を理解できるものと予期される。例えば、
もし太字体のテキストを開始する命令が＜ＢＤ＞ であって、イタリック体テキストの命令が＜ＩＴ＞ であると、命令の順序が ＜ＢＤ＞　　＜ＩＴ＞ である時のテキストに対する影響は ＜ＩＴ＞　　＜１３Ｉ）＞ と同じである。

それ故、２つはサーチによって同等であると解釈さるべ
きである。概念上はこのことは命令をバッファ内に集積
してそれらを各テキストピースの開始前に点検すること
と等しい。

トークンの同等性は直観的なものである。即ち多数の連
続トークン間で分割されたワードはｌトークンとして表
示された同じ内容とマッチしなければならない。次のア
ルゴリズムは等価トークンの形で提示されよう。同様に
、命令系列の等価なコーディングも当然である。かくし
て、フォーマント命令が有意義（即ちサーチ系列の外観
がサーチ基準内に含まれている）である場合のサーチ用
アルゴリズムは命令順序からは独立している。

サーチは３つの特殊類別を処理することから成る。即ち
、最初のデリミッタに先行する等価トークン、最後のデ
リミッタ後の等価トークン、および残りのトークンの３
つである。この前後関係において、デリミッタはスペー
スもしくは句読点と定義される。走査は第１のトークン
に正確に等しいトークンもしくはテキスト内の終りが識
別されるまで続行される。アルゴリズムは今度はそれぞ
れの継起デリミッタと内部トークンを処理する。

もし突合せが正確ならば、走査は続行される。最後に、
最後のトークンが比較される。もしサーチ系列内の最後
の等価トークンがサーチ中のテキストの一節内の対応す
るトークンと完全に一致していれば、整合が確認される
。同様にして、もし最後の等価トークンがテキスト内の
対応するトークンの開始とマッチすれば、そのサーチは
正確である。

ターゲット系列中のフォーマット命令が有意義であれば
サーチアルゴリズムを定義する必要がある。走査前に、
原始系列はトークンに変換され、有効命令が判断される
。各テキストピースの初めに、有効命令の状態は原始ス
トリング中の対応する命令と比較される。もし有効命令
がマッチしなければ比較は失敗である。

サーチとリプレース サーチとリプレース機能は先に定義した編集操作によっ
て定義される。まづ、原始ストリングとリプレーススト
リングはトークン系列に変換される。その後、文書の走
査が実行される。突合せが行われる時、文書の突合され
た部分は含意セレクションに変換される。セレクション
はその後、先に定義した操作を用いて削除される。コー
ディングされたリプレースストリングはその後、挿入点
で挿入される。その後走査が進められ次の突合せをつき
とめる。

スペルチェック この方法によってコーディングされた文書におけるテキ
ストのスペルをチェックするためのアルゴリズムはすこ
ぶる効率的である。文書全体がチェックされるのか、そ
れとも文書の選択部分のみがチェックされるのかに応じ
て考慮すべき２つの場合がある。文書を処理する前に、
２つの一時的データ構造がつくりだされる。第１のもの
はそれぞれの一意的トークンに対してエレメントを有す
るリストである。各エレメントは基準カウントとプール
フィールドを含む。エレメントはそれぞれの基準カウン
トとＦＡＬＳＥ値と共に初期化される。

第２のものは１つ以上のトークンより成るミススペル語
をそれぞれ保持するためのリストである。

このリストは最初は空白である。

文書の処理は文書トークン辞書中の各エントリーをスペ
リング辞書に照してチェックすることから始まる。次に
処理は一時リスト内の適当なプールフィールドをスペリ
ング辞書によってミススペルと識別されたトークンにつ
いてＴＲＵＥにセットする操作へ進む。文書は今度は幾
つかの連続トークンより成るワードについて走査される
。複合トークンの各例については複合中の各トークンに
対する一時的基準カウントが減分された後、ワードはス
ペリング辞書に照らしてチェックされる。もしワードの
綴りが不正確であれば、そのワードはミススペルリスト
へ追加される。（リスト中に既に存在しない場合）文書
末にはミススペルの複合語のリスト中のワードがユーザ
に報告される。同様にして、ミススペルとしてマーキン
グされ非常の一時的基準カウントを有するトークン辞典
エントリーもユーザに報告される。

テキストの一部をチェックする第２の場合にはミススペ
ルされたワードを含むリストだけしか必要でない。同処
理は各ワードをそれが幾つかの断片より構成されている
か否かを選択されたテキスト中より列挙して、その語を
スペリング辞書に照してチェックすることより成る、ミ
ススペルされたワードはミススペルリストに加えられる
。最後のトークンが確認された後そのミススペルリスト
はユーザに報告される。

外里又１ｌｊ ここに述べるテキスト表示はピーステーブルと相俟って
すこぶるコンパクトな機械読取可能な外部形式として使
用することができる。外部記憶の必要条件を最小限にす
ることはピーステーブルと、ピーステーブルが参照する
Ｔｏｋｅｎ．　ＥｎｔｒＹアレイを含むメモリと、トー
クン属性の副集合を節約することより成る。迅速に再計
算できないトークン属性部分のみをファイル中に書込む
必要がある。かくして文字、各区切り点の型と位置を記
すアレイ、および属性のベースアドレスとオフセットだ
けで十分である。区切り点アレイ、計測情報およびトー
クンビットマップ映像を格納しないことによって属性ス
ペースは少なくとも３／４だけ減らすことができる。

典型的な場合、大きな文書の場合、比較は文書中の平均
ワード長の逆元の２倍に収斂する要素であろう。標準的
な英語の場合、その比は３分の１よりも若干小さい。多
数の長いワードを含む技術文書の場合その比は大きくな
ろう。

以上、本発明を特定の実施例について説明してきたが、
当業者には各種の変更を施こし、本発明の真の精神と範
囲より逸脱せずにその諸要素と代替できることが理解で
きよう。更に、本発明の本質的思想から逸脱せずに多く
の変形を施こすことも可能である。

【図面の簡単な説明】

第１図は、メサプログラミング言語で書かれたトークン
データ構造を定義する原始ファイルを示す図、 第２図（ａ）〜（ｃ）は、第１図で定義されたデータ構
造を用いて第４図中のテキストのコーディングの過程を
示す図、 第３図は、メサプログラミング言語で書かれたトークン
属性を表わすためのデータ構造を規定する原始ファイル
を示す図、 第４図は、第１図〜第３図の例に使用したサンプルテキ
ストの一節を示す図、 第５図（ａ）及び（ｂ）は、メサプログラミング言語で
書かれ、トークンとしてコーディングされたテキストを
処理する改行アルゴリズムを定義する原始ファイルを示
す図、 第６図（ａ）〜ｆｄ）は、メサプログラミング言語で書
かれ、トークンとしてコーディングされたテキストの改
行について改行アルゴリズムを実行するための原始ファ
イルを示す図、 第７図（ａ）〜（ｈ）は、Ｃプログラミング言語で書か
れた、テーブル６のメサ原始コードの等価なものを示す
図、 第８図は、第４図のテキストの最初の３行について第６
図で定義されたアルゴリズムの結果を示す図、 第９図は、第１５図で選択されたテキストが削除された
後に残る第８図中のコーディングテキストの最初の断片
を示す図、 第ｌＯ図は、第１５図中で選択されたテキストが削除さ
れた後に残る第２図のコーディングテキストの最終の断
片部分を示す図、 第１１図は、区切り点を有しないトークンについて第３
図に規定されたトークン属性のメモリレイアウトを示す
図、 第１２図は、２つの区切り点を有するトークンについて
第３図に規定されたトークン属性のメモリレイアウトを
示す図、 第１３図は、第３図のデータ構造のディスプレイビット
マップ部分を規定するパラメータを示す図、 第１４図は、テキストが第４図のものである場合の、ハ
イフネーションが許可された時にトークンが処理される
手順を示す図、 第１５図は、セレクションを表示するためにテキストの
一部をハイライトさせた第４図中のテキストを示す図で
ある。 第１図 第２図（ａ） 第２図（ｃ） 第２図（ｂ） 第４図 第５図（ａ） 第５図（ｂ） 第７図（ａ） 第７図（ｂ） 第７図（ｄ） 第７図（ｆ） 第７図（ｅ） 第７図（９） 第７図（ｈ） 第９図 第８図 第１０図 第１１図 第１３図 第１２図 第１４図

Claims (1)

1. 【特許請求の範囲】 （１）ワード、数字、句読点、スペースより成るアトム
   のストリングから構成されるテキストをトークンのリス
   トとそれに対応するデータブロックのアレイにコーディ
   ングする方法において、上記ストリング内の現在アトム
   が上記ストリングにおいて先に出会った以前のアトムと
   同一であるか否かを判断し、 もし同一であれば上記以前のアトムのトークンを上記ト
   ークンリストへ追加して次のアトムへ進み、 もし否であれば新たな独特のトークンを上記トークンリ
   ストへ追加して上記現在アトム内の文字のストリングよ
   り成る上記新たなトークンに対応する新たなデータブロ
   ックをつくりだし、次のアトムへ進む、 段階より成る前記方法。 （２）更に、アトム幅を上記データブロックへ追加する
   ことによって上記データブロックが何処で現在行を区切
   ることができるかを判断するために使用できるようにす
   る段階より成る請求項１記載の方法。 （３）請求項２の方法により発生させられた上記トーク
   ンリストとデータブロックアレイを使用してテキスト行
   を句切る方法において、 （ａ）現在トークンを使用して相当するデータブロック
   にアクセスし、 （ｂ）データブロック内の現在アトムの幅を現在行止め
   の幅の現在の合計に追加して現在行上の全アトムの全体
   幅を判断し、 （ｃ）もし上記全体幅が行を満たすに十分であれば、 ａ、もし先のトークンがスペースであれば、現在アトム
   の終りで改行し、 ｂ、スペースの続く行上の最後のトークンの終りで改行
   し、 （ｄ）もし上記全体幅が行を満たすに不十分であれば、
   次の行に進む、 段階より成る前記方法。 （４）同一の文字、文体、大きさ、重み、アクセント、
   大文字化を有する時にその２個のアトムが同一であると
   識別される請求項１記載の方法。 （５）更に、１ワードを含む各データブロックについて
   同ワードのハイフネーション点とかく上記ハイフネーシ
   ョン点によりつくりだされた各部分ワードの幅とを上記
   データブロックに追加することより成る請求項２記載の
   方法。 （６）請求項５の方法により発生させられたトークンリ
   スト内の各継起トークンを使用して改行点を判断する方
   法において、現在トークンを使用して担当するデータブ
   ロックにアクセスし、データブロック内の現在アトムの
   幅を現在行上のアトム幅の現在合計に加えて現在行上の
   全アトムの全体幅を判断し、 もしその幅の合計が現在行を満たすに十分でなければ、
   次のトークンに進み、 もし幅の合計が行を満たすに十分であれば、行を現在ア
   トムの終りで改行し次の行に進み、もし幅の合計が大き
   すぎて現在行上に納まらない場合は現在ワードをハイフ
   ネーション点が分割して、そのハイフン付けされたワー
   ドの始めを現在行の終りに追加して次の行を現在ワード
   の終り部分より開始する前記方法。 （７）ワード、数字、句読点、スペースより成るアトム
   のストリングから構成されるテキストをトークンのリス
   トとそれに対応するデータブロックのアレイにコーディ
   ングする方法において、上記ストリング中の現在アトム
   が上記ストリング内に先に出会った以前のアトムと同一
   であるかどうかを判断し、 もし同一であれば上記先のアトムのトークンを上記トー
   クンのリストに追加して次のアトムに進み、 もし否であれば新たな独特のトークンを上記トークンリ
   ストに追加して上記現在アトム中の文字ストリングより
   成る現在トークンに対応する新たなデータブロックをつ
   くりだし、次のアトムへ進み、 アトムの幅を上記データブロックに加えて上記データブ
   ロックが何処で現在行が改行可能かを判断するために使
   用できるようにし、 １ワードを含む各データブロックにつき、同ワードのハ
   イフネーション点と、かく同ハイフネーション点により
   つくりだされた各部分ワードの幅とを上記データブロッ
   クへ加え、 上記創造段階中にアトムビットマップを上記データブロ
   ックへ追加し、各現在行につき、上記アトムビットマッ
   プを行バッファ内へ格納して行ビットマップをつくりだ
   しラスタ映像化する、 段階より成る前記方法。 （８）ワード、数字、句読点、スペースより成るアトム
   のストリングから構成されるテキストの行をトークンの
   リストとそれに対応するデータブロックのアレイに分解
   した後そこからアトムを削除する方法において、 上記ストリング中の現在アトムが上記ストリング内に先
   に出会った以前のアトムと同一であるかどうかを判断し
   、 ａ、もし同一であれば上記先のアトムのトークンを上記
   トークンリストに追加して次のアトムへ進み、 ｂ、もし否であれば、新たな独特のトークンを上記トー
   クンリストに追加して上記現在アトム中の文字ストリン
   グより成る上記新たなトークンに対応する新たなデータ
   ブロックをつくりだして次のアトムに進み、 アトムの幅を上記データブロックに加えて上記データブ
   ロックが何処で現在行が改行可能であるかどうかを判断
   するために使用できるようにし、 現在トークンを使用して対応するデータブロックにアク
   セスし、 データブロック内の現在アトムの幅を現在行上の幅の現
   在合計に加えて現在行上の全アトムの全体幅を判断し、 もし上記全体幅が行を満たすに十分であれば、ａ、先の
   トークンがスペースであった場合、現在アトムの終りで
   行を改行し、 ｂ、さもなければ、スペースが続く行上の最後のトーク
   ンの終りで改行し、 もし、上記全体幅が行を満たすに不十分であれば、次の
   トークンに進み、その後そのアトムを削除し、 その削除の段階が、アトムと関連するトークンを削除し
   、データブロックにそれ以上の照会がなければ削除され
   たトークンと関連するデータブロックを削除し、 行上の最初のトークンより開始して請求項３の方法に従
   って改行する、 段階より成る前記方法。 （９）ワード、数字、句読点、スペースより成るアトム
   のストリングより構成されるテキストをトークンのリス
   トとそれに対応するデータブロックのアレイにコーディ
   ングしてトークンリスト中の各継起トークンを使用して
   改行点を判断した後、かくして形成された行中のアトム
   を削除する方法において、 上記ストリング中の現在アトムが上記ストリング中で先
   に出会った以前のアトムと同一であるかどうかを判断し
   、 もし同一であれば上記先のアトムのトークンを上記トー
   クンリストへ追加して次のアトムに進み、 もし否であれば、新たな独特のトークンを上記トークン
   のリストに追加して上記現在アトム中の文字のストリン
   グより成る上記新たなトークンに対応する新たなデータ
   ブロックをつりだして次のアトムへ進み、 アトムの幅を上記データブロックへ追加することによっ
   て上記データブロックが何処で現在行が改行可能である
   かを判断するために使用できるようにし、 １ワードを含む各データブロックにつき、上記ワードの
   ハイフネーション点と同ハイフネーション点により作り
   だされた各部分ワードの幅とを上記データブロックへ追
   加し、 現在トークンを使用して対応するデータブロックにアク
   セスし、データブロック内の現在アトムの幅を現在行上
   のアトム幅の現在合計に加えて現在行上の全アトムの全
   体幅を判断し、もし幅の合計が現在行を満たすに不十分
   であれば、次のトークンに進み、 もし幅の合計が行を満たすに十分であれば、現在アトム
   の終りで改行して次の行に進み もし幅の合計が大きすぎて現在行上に納まりきれない場
   合には、現在ワードをハイフネーション点で分割して、
   そのハイフン付けされたワードの初める現在行の終りに
   追加して次の行を現在ワードの終り部分より開始する段
   階より成り、 アトムを削除する方法が、次の段階、即ち、そのアトム
   と関連するトークンを削除し、 データブロックにそれ以上の照会がなければ削除された
   トークンと関連するデータブロックを削除し、 改行プロセスを繰返し、 同一の文字、書体、大きさ、重み、アクセント、大文字
   化を有する場合には２個のアトムが同一であると規定さ
   れる前記方法。 （１０）ワード、数字、句読点、スペースより成るアト
   ムのストリングより構成されるテキストを行をトークン
   のリストとそれに対応するデータブロックのアレイに分
   解する方法において、 上記ストリング内の現在アトムが先に上記ストリング内
   に出会った以前のアトムと同一であるかどうかを判断し
   、 もし同一であれば、上記先のアトムのトークンを上記ト
   ークンリストに追加して次のアトムに進み、 もし否であれば、新たな独特のトークンを上記トークン
   リストに追加して上記現在アトム中の文字ストリングよ
   り成る上記新たなトークンに対応する新たなデータブロ
   ックをつくりだして次のアトムへ進み、 アトムの幅を上記データブロックに追加して現在行が何
   処で改行可能かを判断するために上記データブロックを
   使用できるようにし、 現在トークンを使用して対応するデータブロックにアク
   セスし、 データブロック内の現在アトムの幅を現在行上の幅の現
   在合計に加えて現在行上の全アトムの全体幅を判断し、 もし上記全体幅が行を満たすに十分であれば、ａ、先の
   トークンがスペースであった場合、行を現在アトムの終
   りで改行し、 ｂ、さもなければ、行をスペースが続く行上の最終のト
   ークンの終りで改行し、 もし上記全体幅が行を満たすに不十分であれば、次のト
   ークンに進み、その後文字を以下の如く、即ち、 変更すべきアトムと関連するトークンを削除し、 その代わりに第１のトークンとデータブロックを削除さ
   れた文字に先立ってるアトムの断片の代わりに、また第
   ２のトークンとデータブロックを削除された文字の後に
   アトムの断片に代えて代入し、 もしデータブロックに対するそれ以上の照会がなければ
   削除されたトークンと関連するデータブロックを削除し
   、 行上の第１トークンより初めて改行プロセスを反復する
   ことにって削除する前記方法。 （１１）ワード、数字、句読点、スペースより成るアト
   ムのストリングを備えるテキストをトークンのリストと
   それに対応するデータブロックのアレイにコーディング
   してトークンリスト中の各継起トークンを使用して改行
   点を判断する方法において、 上記ストリング中の現在アトムが上記ストリング中で先
   に出会った以前のアトムと同一であるかどうかを判断し
   、 もし同一であれば、上記先のアトムのトークンを上記ト
   ークンリストに追加して次のアトムに進み、 もし否であれば、新たな独特のトークンを上記トークン
   リストに追加して上記現在アトム中の文字ストリングよ
   り成る上記新たなトークンに対応する新たなデータブロ
   ックをつくりだして次のアトムに進み、 アトムの幅を上記データブロックに追加して現在行が何
   処で改行可能であるかを判断するために上記データブロ
   ックを使用することができるようにし、 現在トークンを使用して対応するデータブロックにアク
   セスし、 データブロック内の現在アトムの幅を現在行上のアトム
   幅の現在合計に加えて現在行上の全アトムの全体幅を判
   断し、 もし幅の合計が現在行を満たすに不十分であれば、次の
   トークンに進み、 もし幅の合計が行を満たすに十分であれば、現在アトム
   の終りで行を改行して次の行に進み、もし幅の合計が大
   きすぎて現在行上に納まりきれない場合には、現在ワー
   ドをハイフネーション点で分割してハイフン付けされた
   ワードの初めを現在行の終りに追加して新しい行を現在
   ワードの終り部分から開始し、 同一の文字、書体、大きさ、重み、アクセント、大文字
   化を有する場合に２個のアトムが同一であると定義され
   、その後かくして形成されたテキストの行中のアトムか
   ら文字を削除し、その削除段階が、変更さるべきアトム
   と関連するトークンを削除し、 その代わりに削除された文字に先立って第１のトークン
   とデータブロックをアトム断片の代わりに代入し、削除
   された文字の後に第２のトークンとデータブロックをア
   トム断片の代わりに代入し、 データブロックに対するそれ以上の照会がない場合に削
   除されたトークンと関連するデータブロックを削除し、 行上の第１のトークンより開始して改行プロセスに従っ
   て改行する、 段階より成る前記方法。 （１２）ワード、数字、句読点、スペースより成るアト
   ムのストリングより構成されるテキストの行をトークン
   のリストとそれに対応するデータブロックのアレイに分
   解する方法において、 上記ストリング内の現在アトムが上記ストリング中で先
   に出会った以前のアトムと同一であるかどうかを判断し
   、 もし同一であれば、上記先のアトムのトークンを上記ト
   ークンのリストに追加して次のアトムに進み、 もし否であれば、新たな独特のトークンを上記トークン
   リストに追加して上記現在アトム中の文字のストリング
   より成る上記新たなトークンに対応する新たなデータブ
   ロックをつくりだして次のアトムに進み、 アトム幅を上記データブロックに追加することによって
   現在行が何処で改行可能であるかを判断するために上記
   データブロックを使用できるようにし、 現在トークンを使用して対応するデータブロックにアク
   セスし、 データブロック内の現在アトムの幅を現在行上の幅の現
   在合計に追加して現在行上の全アトムの全体幅を判断し
   、 もし上記全体幅が行を満たすに十分であれば、ａ、先の
   トークンがスペースであった場合、現在アトムの終りで
   改行し、 ｂ、スペースが続く行上の最後のトークンの終りで行を
   改行し、 もし上記全体幅が行を満たすに不十分であれば、次のト
   ークンに進み、その後、テキストの１行中の１アトムに
   一文字を追加し、 変更さるべきアトムと関連するトークンを削除し、 その代わりに、 ［１］挿入された文字に先立ってアトムの断片の代わり
   に第１のトークンとデータブロックを代入し、 ［２］（ａ）文字がスペースもしくは句読点である場合
   、請求項７の方法からつくりだしたデー タブロックと、 （ｂ）文字（ｃｈａｒａｃｔｅｒ）が文字（ｌｅｔｔｅ
   ｒ）もしくは番号である場合、特殊データブロック と、 に対応する第２のトークンを代入し、 ［３］挿入された文字の後にアトムの断片に代えて第３
   のトークンとデータブロックを代入し、行上の第１のト
   ークンより開始して改行プロセスに従って行を改行する
   、 段階より成る前記方法。 （１３）ワード、数字、句読点、スペースより成るアト
   ムのストリングより構成されるテキストの行をトークン
   のリストとそれに対応するデータブロックのアレイに分
   解する方法において、 上記ストリング中の現在アトムが上記ストリング中で先
   に出会った以前のアトムと同一であるかどうかを判断し
   、 もし同一であれば、上記先のアトムのトークンを上記ト
   ークンリストに追加して次のアトムに進み、 もし否であれば、新たな独特のトークンを上記トークン
   リストに追加して上記現在アトム中の文字ストリングよ
   り成る上記新たなトークンに対応する新たなデータブロ
   ックをつくり出し、次のアトムに進み、 アトムの幅を上記データブロックに追加することによっ
   て現在行が何処で改行可能かを判断するために上記デー
   タブロックを使用できるようにし、 現在トークンを使用して対応するデータブロックにアク
   セスし、 データブロック内の現在アトムの幅を現在行上の幅の現
   在合計に加えて現在行上の全アトムの全体幅を判断し、 もし上記全体幅が行を満たすに十分であれば、ａ、先の
   トークンがスペースであった場合、現在アトムの終りで
   改行し、 ｂ、さもなければ、スペースが続く行上の最後のトーク
   ンの終りで改行し、 もし上記全体幅が行を満たすに十分でなければ、次のト
   ークンに進み、その後１文字をテキストの１行中のアト
   ムに追加し、 変更さるべきアトムと関連するトークンを削除し、 その代わりに、 ［１］挿入された文字に先立ってアトム断片の代りに第
   １のトークンとデータブロックを代入し、 ［２］（ａ）文字がスペースもしくは句読点である場合
   、請求項７の方法によりつくりだされた データブロックと、 （ｂ）文字（ｃｈａｒａｃｔｅｒ）が文字（ｌｅｔｔｅ
   ｒ）もしくは番号である場合、特殊なデータブロッ ク、に対応する第２のトークンと、 ［３］挿入された文字の後にアトムの断片に代えて第３
   のトークンとデータブロックを、代入し、 行上の第１のトークンから開始して改行プロセスに従っ
   て改行し、その後かくして形成されたテキストの１行内
   の１アトムに第２の文字を追加し、その段階が、 ［１］文字（ｃｈａｒａｃｔｅｒ）が文字（ｌｅｔｔｅ
   ｒ）であるか番号であれば、新たな文字を請求項１２で
   つくりだされた特殊データブロックに追加し、［２］新
   たな文字がスペースもしくは句読点であれば、 （ａ）請求項２の方法によって特殊データブロック内の
   文字を使用して新たなアトム用の トークンを判断し、 （ｂ）特殊データブロックに対応するトークンを削除し
   、 （ｃ）（ａ）で判断されたトークンに対する照会を代替
   し、 （ｄ）もしそれがスペースもしくは句読点である場合に
   はその文字について請求項７の方 法からつくりだされたデータブロックに対 応する第２のトークンを挿入し、 （ｅ）次の文字を請求項１２の方法により処理し、 行上の第１のトークンから開始して同行を改行プロセス
   に従って改行する前記方法。 （１４）ワード、数字、句読点、スペースより成るアト
   ムのストリングより構成されるテキストをトークンのリ
   ストとそれに対応するデータブロックのアレイにコーデ
   ィングしてトークンリスト中の各継起トークンを使用し
   て改行点を判断する方法において、 上記ストリング中の現在アトムが上記ストリング中で先
   に出会った以前のアトムと同一であるかどうかを判断し
   、 もし同一であれば、上記先のアトムのトークンを上記ト
   ークンリストに追加して次のアトムに進み、 もし否であれば、新たな独特のトークンを上記トークン
   リストに追加して上記現在アトム中の文字のストリング
   より成る上記新たなトークンに対応する新たなデータブ
   ロックをつくりだして次のアトムに進み、 アトムの幅を上記データブロックに追加することによっ
   て現在行が何処で改行可能かを判断するために上記デー
   タブロックを使用できるようにし、 現在トークンを使用して対応するデータブロックにアク
   セスし、 データブロック内の現在アトムの幅を現在行上のアトム
   幅の現在合計に加えて現在行上の全アトムの全体幅を判
   断し、 もし幅の合計が現在行を満たすに不十分であれば、次の
   トークンに進み、 もし幅の合計が行を満たすに十分であれば、現在アトム
   の終りで行を改行して次の行に進み、もし幅の合計が大
   きすぎて現在行上に納まりきれない場合には現在ワード
   をハイフネーション点で分割してそのハイフン付けされ
   たワードの初めを現在行の終りに追加して現在ワードの
   終りの部分から新しい行を開始し、その後、かくして形
   成されたテキストの１行中の１アトムに下記の如く削除
   することによって追加し、その削除段階が、 変更さるべきアトムと関連するトークンを削除し、 その代わりに、 ［１］挿入された文字に先立ってアトム断片に代えて第
   １のトークンとデータブロックと、 ［２］（ａ）文字がスペースもしくは句読点である場合
   、請求項７中の方法からつくりだされた データブロックと、 （ｂ）文字（ｃｈａｒａｃｔｅｒ）が文字（ｌｅｔｔｅ
   ｒ）もしくは番号である場合、特殊データブロック と、 ［３］挿入文字後にアトム断片に代えて第３のトークン
   とデータブロックと、を代入し、 行上の第１のトークンより開始して請求項９の方法によ
   り改行し、２個のアトムが同一の文字、書体、大きさ、
   重み、アクセント、大文字を有する場合に同一であると
   定義される前記方法。 （１５）ワード、数字、句読点、スペースより成るアト
   ムのストリングより構成されるテキストをトークンのリ
   ストとそれに対応するデータブロックのアレイにコーデ
   ィングしトークンリスト中の各継起トークンを使用して
   改行点を判断する方法において、 上記ストリング中の現在アトムが上記ストリング内で先
   に出会った以前のアトムと同一であるかどうかを判断し
   、 もし同一であれば、上記先のアトムのトークンリストに
   追加して次のアトムに進み、 もし否であれば新たな独特のトークンを上記トークンリ
   ストに追加して上記現在アトム中の文字ストリングより
   成る上記新たなトークンに対応する新たなデータブロッ
   クをつくりだして次のアトムに進み、アトムの幅を上記
   データブロックに追加して現在の行が何処で改行可能で
   あるかを判断するために上記データブロックを使用でき
   るようにし、 現在トークンを使用して対応するデータブロックにアク
   セスし、データブロック内の現在アトムの幅を現在行上
   の全アトムの全体幅を判断するために現在行上のアトム
   幅の現在合計に追加し、もし幅合計が現在行を満たすに
   不十分な場合には次のトークンに進み、 もし幅合計が行を満たすに十分であれば現在アトムの終
   わりで行を改行して次の行に進み、幅の合計が大き過ぎ
   て現在行上に納まりきれない場合は、現在ワードをハイ
   フネーション点で分割してそのハイフン付けされたワー
   ドの初めを現在行の終わりに追加して新たな行を現在ワ
   ードの終わりの部分から開始し、その後かくして形成さ
   れたテキストの１行中の１アトムに１文字を以下の手順
   で追加し、同手順が、変更さるべきアトムと関連するト
   ークンを削除し、それに代えて、 ［１］挿入文字に先行するアトムの断片に代えて第１の
   トークンとデータブロックと、 ［２］（ａ）文字がスペースもしくは句読点である場合
   には請求項７中の方法によりつ くりだされたデータブロックと、 （ｂ）文字（ｃｈａｒａｃｔｅｒ）文字（ｌｅｔｔｅｒ
   ）もしくは番号である場合には特殊データブ ロックに相当する第２のトークンと、 ［３］あるいは挿入文字後のアトム断片に代えて第３の
   トークンとデータブロックを代入 し、 かくして形成されたテキストの１行中の１アトムに対し
   て以下の手順で第２の文字を追加し、その手順が、 ［１］文字（ｃｈａｒａｃｔｅｒ）が文字（ｌｅｔｔｅ
   ｒ）もしくは番号である場合、新しい文字を請求項１４
   でつくりだされた特殊データブロックに追 加し、 ［２］新文字がスペースもしくは句読点である場合には
   、 （ａ）請求項７の方法における特殊データ ブロック中の文字を使用して新アトム のトークンを判断し、 （ｂ）特殊データブロックに対応するトー クンを削除し、 （ｃ）（ａ）で判断されたトークンに対する照会を代替
   し、 （ｄ）もしそれがスペースもしくは句読点 である場合にはその文字につき請求項 ７の方法によりつくりだされたデータ ブロックに対応する第２のトークンを 挿入し、 （ｅ）次の文字を請求項１４の方法により 処理し、 行上の第１トークンから開始して改行プロセスに従い同
   行を改行し、 同一文字、書体、大きさ、重み、アクセント、大文字を
   有する場合に２個のアトムが同一であると定義される前
   記方法。 （１６）ワード、数字、句読点、スペースより成るアト
   ムのストリングから構成されるテキストの行をトークン
   のリストとそれに対応するデータブロックのアレイに分
   解する方法において、上記ストリング中の現在アトムが
   上記ストリング中で先に出会った以前のアトムと同一で
   あるかどうかを判断し、もし同一であれば、上記先のア
   トムのトークンを上記トークンリストに追加してつぎの
   アトムに進み、もし否であれば、新たな独特のトークン
   を上記トークンリストに追加し、上記現在アトム中の文
   字のストリングより成る上記新たなトークンに対応する
   新たなデータブロックをつくりだし、次のアトムに進み
   、アトムの幅を上記データブロックに追加することによ
   って現在行が何処で改行可能であるかを判断するために
   上記データブロックを使用することができるようにし、
   現在トークンを使用して対応するデータブロックにアク
   セスし、データブロック内の現在アトムの幅を現在行上
   の幅の現在合計に追加して現在行上の全アトムの全体幅
   を判断し、もし上記全体幅が行を満たすに十分であれば
   、 （ａ）先のトークンがスペースであった場合、行を現在
   アトムの終わりで改行し、 （ｂ）さもなければ、スペースが続く行上の最後のトー
   クンの終わりで行を改行し、 もし、全体幅が行を満たすに不十分であれば、次のトー
   クンに進み、その後かくして形成された行中の文字をカ
   ーソルで同定することによって識別し、その際、何れの
   行にカーソルが現れるかを判断し、同行の左端から開始
   して現在アトムの幅を現在合計の幅がカーソルの行の左
   端からの距離を越えるまで行中のアトムの幅の現在合計
   に加え、現在合計の幅が行の左端からのカーソルの距離
   を等しくなるまで１回に一文字左へ進む段階より成る前
   記方法。 （１７）ワード、数字、句読点、スペースより成るアト
   ムのストリングより構成されるテキストをトークンのリ
   ストとそれに対応するデータブロックのアレイにコーデ
   ィングしトークンリスト中の各継起トークンを使用して
   改行点を判断する方法において、上記ストリング中の現
   在アトムが上記ストリング中で先に出会った以前のアト
   ムと同一であるかどうかを判断し、もし同一であれば、
   上記先のアトムのトークンを上記トークンリストに追加
   して次のアトムに進み、もし否であれば、新たな独特の
   トークンを上記トークンリストに追加して上記現在アト
   ム中の文字ストリングより成る上記新たなトークンに対
   応する新たなデータブロックをつくりだし、次のアトム
   へ進み、アトムの幅を上記データブロックに追加するこ
   とによって現在行が何処で改行可能であるかを判断する
   ために上記データブロックが使用できるようにし、現在
   トークンを使用して対応するデータブロックにアクセス
   し、データブロック中の現在アトムの幅を現在行上のア
   トム幅の現在合計に追加して現在行上の全アトムの全体
   幅を判断し、もし幅の合計が現在行を満たすに不十分で
   あれば、次のトークンに進み、もし幅の合計が行を満た
   すに十分であれば、行を現在アトムの終わりで改行して
   次の行に進み、もし幅の合計が大きすぎて現在行上に納
   まりきれない場合には現在ワードをハイフネーション点
   で分割し、次の行を現在ワードの終わりの部分より開始
   し、かく形成された行中のカーソルで同定された点の文
   字を識別し、その際、行の左端から開始し、現在アトム
   の幅を現在行の幅が行の左端からのカーソルの距離を越
   えるまで行中のアトム幅の現在合計に追加し、現在合計
   の幅がカーソルの行左端からの距離に等しくなるまで１
   回に一文字左へ進め、 ２個のアトムが同一の文字、書体、大きさ、重み、アク
   セント、大文字を有する場合に同一であると定義される
   段階より成る前記方法。 （１８）ワード、数字、句読点、スペースより成るアト
   ムのストリングより構成されるテキストをトークンのリ
   ストとそれに対応するデータブロックのアトムにコーデ
   ィングする方法において、上記ストリング中の現在アト
   ムが上記ストリング中で先に出会った以前のアトムと同
   一であるかどうかを判断し、もし同一であれば、上記以
   前のアトムのトークンを上記トークンリストに追加して
   次のアトムへ進み、もし否であれば、新たな独特のトー
   クンを上記トークンリストに追加して上記現在アトム中
   の文字ストリングより成る上記新たなトークンに対応す
   る新たなデータブロックをつくりだし、次のアトムに進
   み、その後かくコーディングされたテキスト中でアトム
   を探索しそれを一個もしくはそれ以上のアトムと取替え
   、その際、 ［１］そのコーディング法を使用して探索さるべきアト
   ムを表すトークン順序を判断し、 （２）テキスト中の現在アトムより開始してそれがコー
   ディングされたサーチストリング 中の第１のアトムと等しいかどうかを判断 し、もし否であれば、テキスト中の次のト ークンに進み、さもなければ［３］を続行し、［３］コ
   ーディングされたサーチストリング中の各継起トークン
   について、テキスト中の 各継起トークンを比較し、もしそのトーク ンの一つがマッチしない場合には［２］に戻り［２］の
   段階で処理された最後のトークンの後に第１のトークン
   と共にし続行し、 ［４］代替トークン用のコーディングを決定し、［５］
   ［３］の段階でつきとめられたコード化されたサーチス
   トリングを［４］より導出されるトークンと取替える、
   段階より成る前記方法。 （１９）ワード、数字、句読点、スペースより成るアト
   ムのストリングより構成されるテキストをトークンのリ
   ストとそれに対応するデータブロックのアトムにコーデ
   ィングする方法において、上記ストリング中の現在アト
   ムが上記ストリング中で先に出会った以前のアトムと同
   一であるかどうかを判断し、もし同一であれば、上記先
   のアトムのトークンを上記トークンリストに追加して次
   のアトムに進み、もし否であれば、新たな独特のトーク
   ンを上記トークンリストに追加し、上記現在アトム中の
   文字ストリングより成る上記新たなトークンに対応する
   新たなデータブロックをつくりだし、次のアトムに進み
   、アトムの幅を上記データブロックに追加することによ
   って現在行が何処で改行可能であるかを判断するために
   上記データブロックを使用できるようにし、１ワードを
   含む各データブロックにつき、上記ワードのハイフネー
   ション点と同ハイフネーション点によりつくりだされた
   各部分ワードの幅を上記データブロックに追加し、その
   後、かくコーディングされたテキスト中の一個もしくは
   それ以上のアトムを探索してそれを一個もしくはそれ以
   上のアトムと取替え、その際、 ［１］上記コーディング法を使用して探索さるべきアト
   ムを表すトークン順序を判断し、 ［２］テキスト中の現在アトムより開始してそれがコー
   ディングされたサーチストリング 中の第１のアトムと等しいかどうかを判断 し、もし等しくなければテキスト中の次の トークンへ進み、さもなければ［３］を続行し、［３］
   コード化されたサーチストリング中の各継起トークンに
   つき、テキスト中のそれぞ れの継起トークンを比較し、もしそのトー クンの一つがマッチしない場合には［２］に戻り、段階
   ［２］で処理された最後のトークン後に第１のトークン
   を継続し、 ［４］代替トークン用のコーディングを決定し、［５］
   段階［３］でつきとめられたコード化されたサーチスト
   リングを段階［４］から導出されたトークンと取替える
   、 段階より成る前記方法。 （２０）ワード、数字、句読点、スペースより成るアト
   ムのストリングから構成されるテキストをトークンのリ
   ストとそれに対応するデータブロックのアレイにコーデ
   ィングする方法において、上記ストリング内の現在アト
   ムが上記ストリング中で先に出会ったアトムと同一であ
   るかどうかを判断し、もし同一であれば、上記先のアト
   ムのトークンを上記トークンリストに追加して次のアト
   ムに進み、もし否であれば、新たな独特のトークンを上
   記トークンリストに追加し、上記現在アトム中の文字ス
   トリングより成る上記新たなトークンに対応する新たな
   データブロックをつくりだし、次のアトムに進み、アト
   ムの幅を上記データブロックに追加することによって現
   在行が何処で改行可能であるかを判断するために上記デ
   ータブロックが使用できるようにし、その後、各データ
   ブロック中のストリングの綴りをチェック刷ることによ
   ってコーディングされたテキスト中のワードの綴りをチ
   ェックする段階より成る前記方法。 （２１）ワード、数字、句読点、スペースより成るアト
   ムのストリングより構成されるテキストをトークンのリ
   ストとそれに対応するデータブロックのアレイにコーデ
   ィングする方法において、上記ストリング中の現在アト
   ムが上記ストリング中で先に出会ったアトムと同一であ
   るかどうかを判断し、もし同一であれば、上記先のアト
   ムのトークンを上記トークンリストに追加して次のアト
   ムに進み、もし否であれば、新たな独特のトークンを上
   記トークンリストに追加して上記現在アトム中の文字の
   ストリングより成る上記新たなトークンに対応する新た
   なデータブロックをつくりだし、次のアトムに進み、ア
   トムの幅を上記データブロックに追加することによって
   現在行が何処で改行可能であるかどうかを判断するため
   に上記データブロックガイド使用できるようにし、１ワ
   ードを含む各データブロックについて、上記ワードのハ
   イフネーション点と同ハイフネーション点によりつくり
   だされた各部分ワードの幅を上記データブロックに追加
   し、その後、スペースもしくは句読点が前後する各トー
   クンについて各データブロック中のストリングのスペル
   をチェック刷ることによってコーディングされたテキス
   ト中のワードのスペルをチェックする段階より成る前記
   方法。 （２２）ワード、数字、句読点、スペースより成るアト
   ムのストリングより構成されるテキストをトークンのリ
   ストとそれに対応するデータブロックのアトムにコーデ
   ィングする方法において、上記ストリング内の現在アト
   ムが上記ストリング内で先に出会ったアトムと同一であ
   るかどうかを判断し、もし同一であれば、上記先のアト
   ムのトークンを上記トークンリストに追加して次のアト
   ムへ進み、もし否であれば、新たな独特のトークンを上
   記トークンのリストに追加して、上記現在アトム中の文
   字ストリングより成る上記新たなトークンに対応する新
   たなデータブロックをつくりだし、次のアトムへ進み、
   アトムの幅を上記データブロックに追加することによっ
   て現在行が何処で改行可能であるかを判断するために上
   記データブロックが使用できるようにし、１ワードを含
   む各データブロックにつき、上記ワードのハイフネーシ
   ョン点と同ハイフネーション点によりつくりだされた各
   部分ワードの幅を上記データブロックに追加し、その後
   、メモリ内に格納された各データブロックについてエン
   トリを有する新たなテーブルをつくりだし、その新たな
   テーブルの各エレメント中に最初のデータブロックの文
   字、区切り点位置、大きさを含め、コーディング段階で
   つくりだされた各データブロックのメモリ中のアドレス
   を新たなテーブルに追加することによってコーディング
   されたテキストを簡潔化する、段階より成る前記方法。