[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

JPS63292365A - 文字処理装置 - Google Patents

文字処理装置

Info

Publication number
JPS63292365A
JPS63292365A JP62128687A JP12868787A JPS63292365A JP S63292365 A JPS63292365 A JP S63292365A JP 62128687 A JP62128687 A JP 62128687A JP 12868787 A JP12868787 A JP 12868787A JP S63292365 A JPS63292365 A JP S63292365A
Authority
JP
Japan
Prior art keywords
dictionary
word
block
code
index
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP62128687A
Other languages
English (en)
Other versions
JPH0682370B2 (ja
Inventor
Yasushi Yamamoto
康 山本
Yoshizo Saito
齋藤　佳三
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Sharp Corp
Original Assignee
Sharp Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Sharp Corp filed Critical Sharp Corp
Priority to JP62128687A priority Critical patent/JPH0682370B2/ja
Priority to DE3852341T priority patent/DE3852341T2/de
Priority to EP88304675A priority patent/EP0293161B1/en
Priority to US07/198,503 priority patent/US4959785A/en
Publication of JPS63292365A publication Critical patent/JPS63292365A/ja
Publication of JPH0682370B2 publication Critical patent/JPH0682370B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F40/00—Handling natural language data
    • G06F40/20—Natural language analysis
    • G06F40/232—Orthographic correction, e.g. spell checking or vowelisation

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Audiology, Speech & Language Pathology (AREA)
  • Health & Medical Sciences (AREA)
  • Computational Linguistics (AREA)
  • General Health & Medical Sciences (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Artificial Intelligence (AREA)
  • Document Processing Apparatus (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Machine Translation (AREA)

Abstract

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

Description

【発明の詳細な説明】 （イ）産業上の利用分野 本発明は、スペルチェックを行うことができろ文字処理
装置に関する。
（ロ）従来の技術 従来、この種の文字処理装置におけるスペルチェックに
おいては、スペルチェックする欧文用単語辞書内の単語
をその頭文字層、単語を構成する文字数類というように
２次元テーブルで作成し、その２次元テーブルから該当
する単語を検索する方法が取られている。この検索方法
は、第５表＆及び第５表すに示すように“Ｃｏから始ま
る単語を例に取ると、“Ｃ”が先頭で７文字から構成さ
れる単語が１００６１１あり、同じく“Ｃｏが先頭で８
文字から構成される単語では１１５４種、さらに、“Ｃ
”が先頭で９文字から構成されろ単語に至っては１０９
２種らあり、例えば“ＣＯＭＰＡＮＹ”という単語を検
索する場合、少なくとも１００６回（２文法であれば５
０３回）比較参照していた。そして、単に頭文字類のみ
で分類されている欧文用単語辞書にあっては、さらに多
くの比較参照を行っていた。
（ハ）発明が解決しようとする問題点 しかし、上記の文字処理装置の欧文用単語辞書のスペル
チェックでは、検索のための処理速度が非常に遅くなり
、タイプライタ−等でリアルタイム処理をするには到底
耐えられないものであった。
また、単語をハツシュコードに直して処理速度を°速め
る方法もあるが、スペルチェック機能実現の次に要求さ
れるコレクト機能（誤綴り訂正）を考慮した場合、ハブ
シュコード採用辞書は元の文字配列を再生できないため
、精度が低いという問題を有している。
本発明は以上の事情に鑑みてなされたらので、その目的
は単語の文字発生頻度をハフマンコードに編集し直し、
かつ単語をブロック単位に分けろことによって辞書の記
憶容量の削減を図り、単語をスペルチェックするための
処理速度を速めろことにある。
（ニ）問題点を解決するための手段 第１図は、この発明の構成を示すブロック図であり、１
は文字情報および各種の指示を入力する入力手段、２は
入力手段から入力された文字情報を記憶する記憶手段、
３は文字情報を表示する表示手段、４は入力手段の指示
に基づき記憶手段に記憶されている文字情報を表示手段
に出力する制御手段、５はｎバイト毎に分割されたブロ
ックを一単位として構成され、１つのブロックにそのブ
ロックの先頭第１１１語が所定コードに変換された非圧
縮なバイト単位の文字列として格納され、かつ、先頭第
１単語と関連のある第２単語を含むそれ以降の単語が、
目的の単語の１つ前に格納された単語との共通部分を表
わす相対圧縮コードおよび相対圧縮ができなかった非圧
縮コードを出現頻度を考慮して割り付けだハフマンコー
ドに置換された情報として格納される辞書本体部と、辞
書本体部からのオフセットと、そのオフセットで示され
ろ１群のブロックの数とで構成されろインデックス部と
からなる情報が記憶される圧縮辞書記憶手段、６はキー
ワードの先頭２文字より圧縮辞書記憶手段のインデック
ス情報の格納されるアドレスを計算し、そのインデック
スのオフセットおよびブロック数を取出し、ブロックの
先頭第１単語についてブロック単位で２分検索を行うス
ペルチェック手段である。
（ホ）作用 この発明によれば、スペルチェックを行うと、キーワー
ドの先頭２文字よりインデックス情報の格納されるアド
レスが計算され、インデックスのオフセットおよびブロ
ック数を取出し、次に辞書本体のブロック先頭の先頭第
１単語がブロック単位で２分検索され、キーワードが辞
書本体のどこのブロックに格納されているかを調べて選
択し、選択されたブロックの先頭から順次ハフマンコー
ドを復号し、キーワードを検索するよう作用する。
（へ）実施例 以下、図に基づいてこの発明の実施例を詳述する。なお
、これによってこの発明は限定されろものではない。第
２図は、この発明の一実施例の構成を示すブロック図で
ある。同図において、ｌＯは文字、単語情報を入力する
ための人力装置で、例えばキーボード、タブレット装置
、光学式文字読み取り装置、磁気テープ装置等からなる
。１１は入力装置１０から入力された文字情報を記憶す
る記憶装置で、例えばコアメモリ、ＩＣメモリ。
磁気ディスク等からなる。１２は記憶装置ｉｔにおいて
記憶１編集された情報を出力する出力装置で、例えばプ
リンタ、ディスプレイ装置、＠気テープ、磁気ディスク
装置等からなる。！３は記憶装置２に記憶されている文
字、単語データの綴り情報の間合せに対して適時有効な
情報を供給するスペルチェック辞書装置で、例えばコア
メモリ。
ＩＣメモリ、ＲＡＭ、磁気ディスク等からなる。
１４は上記構成の各装置間の信号のやりとりを制御する
制御装置で、例えばコンピュータからなる。
次に、この発明の実施例の特徴部分であるスペルチェッ
ク辞書装置について詳述する。第３図は、スペルチェッ
ク辞書手段としての、辞書容量を圧縮した圧縮辞書の基
本構造である。同図において、圧縮辞書はインデックス
部と辞書本体とによって構成されている。インデックス
部は、先頭２文字が××で始まる単語列が格納されてい
る辞書本体の先頭からのオフセットとそのインデックス
内に収容されろ後述するブロック数から構成されており
、辞書本体はｎバイト毎に分割されたブロックを単位に
構成され、各ブロックの先頭第１単語は内部コードに変
換された非圧縮なバイト単位の文字列か格納される。
第２単語以降は相対圧縮コード（１つ前の単語との共通
部分を表わすコード）および相対圧縮ができなかった非
圧縮文字コードを出現頻度より割り付けたハフマンコー
ドに置き換えて格納されろ。
従ってＸＸで始まる単語列がブロック長であるｎバイト
を超えたならば、同一のインデックス内に複数のブロッ
クが存在するのでスペルチェックを行なう場合は、キー
ワードの先頭２文字よりインデックス情報の格納される
アドレスを計算し、そのインデックスのオフセットおよ
びブロック数を取出す。次にオフセット、ブロック数、
ブロック長ｎが既知であるため、先程のブロック先端の
非圧縮単語についてブロック単位で２分探索を行なう。
この段階でキーワードがどこのブロックに格納されてい
るかを知ることができるので対象となったブロックの先
頭から順次ハフマンコードを復号しキーワードを検索す
るものである。
取扱う文字種 ＆、’　、０〜９．Ａ−Ｚ、ａ−ｚの６４種但し。
はハイフォネート時に特別の意味をもつ。
辞書 圧縮を行う原辞書は、複数形や動詞の活用形などの変化
形を、原形に対して全く別の単語とみなして登録された
英単語辞書である。また単語長ｌの英文字は存在するの
で、同様に単語長ｌの＆および°そして数字ら無条件に
存在するものとして辞書には２文字以上の単語を登録す
る。
圧縮の基本アルゴリズム 英単語辞書は、アスキーコード順（文字コード順）にリ
ートを行わせろと、隣接する単語の相関関係が非常に密
となる。即ち、単語の先頭部分より重複する文字が多数
現れているので、この性質に着目し重複する文字列を特
殊なコードに置き換えろという方法で辞書の圧縮を行う
ことが出来ろ（第４図参照）。
しかしこの方法で圧縮を行なうと、辞書検索を行なう際
、辞書の先頭から順次探索を行なわなければならないの
で、最悪の場合、辞書に登録されていない単語について
スペルチェックを行う際にも、辞書の先頭より末尾まで
辞書全体にわたって探索が行なわれてしまう。そこで辞
書をある値（ブロック長）ｎバイトのブロックに分割し
、各ブロックの先頭第１単語は相対圧縮しないとすれば
、この非相対圧縮文字列に対してブロック単位で２分探
索法を利用することは可能である（第５図参照）。従っ
て辞書検索は次の３つのステップによって行う。
ｉ）キーワードのインデックス値よりオフセット、ブロ
ック数等のインデックス情報をインデックステーブルよ
り得る。
１ｉ）ｉ）で得たオフセット、ブロック数そしてブロッ
ク長ｎによりブロック単位で２分検索を行ないキーワー
ドの格納されていると考えられろブロックを特定する。
ｉｉｉ　）　ｉｉ　）で特定されたブロックについての
み、そのブロックの先頭から順次探索を行なう。
以上の方法による辞書探索を行えば、シーケンシャルに
探索を行なわなければならない範囲は、最悪の場合でも
ブロック長ｎとすることができるのでスペルチェック時
の検索時間の高速化を図ることができる。
このような方法を辞書の圧縮と辞書探索の基本的な骨組
とし、さらに圧縮を行なわせるために各ブロック第２単
語以降のコードに対して後述するハフマン符号化技法を
用いて圧縮を行なわせた。
従って、以上の手順で圧縮された辞書の容量およびスペ
ルチェックのための平均探索時間は、ブロック長ｎと後
述するインデックスの構成即ち先頭何文字をインデック
スとするかによって変化する。そこで、この２つのパラ
メータをいくつか選び、そのパラメータにより実際に辞
書圧縮および辞書探索を行なわせ、圧縮辞書の容量と平
均辞書探索速度の関係を調べて目的にあった容量、速度
を得ろパラメータを決定する。
インデックス部 前述の通り、この辞書で取扱う文字種は６４種である。
従って先頭１文字をインデックスとすれば６４’＝６４
個、先頭２文字をインデックスとすれば６４　”＝４．
０９６個、先頭３文字をインデックスとすれば６４３＝
２６２．１４４１１１というように先頭ｍの文字をイン
デックスとした場合６４′″個のインデックステーブル
を容易しなければならない。
しかしながら、辞書には２文字長の単語が登録されてい
るので、またインデックスを先頭３文字以上にすると辞
書の構造が複雑になり、ｍを大きくとると指数関数的に
インデックス部容量が増大するので、ｍは２以下に抑え
るしのとする。また、ｍは大なる方がインデックスを絞
り込めるのでスペルチェック速度が高速となる。この様
なことを念頭におき、ｍ＝１およびｍ＝２の場合につい
て、実験を行った結果、圧縮辞書容量とスペルチェック
速度の関係上ｍ＝２を採用することにした。
インデックステーブル参照の方法は、キーワードを第１
表に示す内部コード変換表に基づいて内部コードに変換
し、第１文字目に６４の重みを与えたＯ〜４０９５のイ
ンデックス値を作る。
（＆＆＝０．　＆’　＝１．・・・・・・、　ＡＡ＝８
０）この値よりインデックステーブルのアドレスを計算
して必要なインデックス情報を得る。
インデックス情報は３つあり、第１はそのインデックス
に属する単語列の格納される辞書本体の先頭からのオフ
セット値で、第２はそのインデックスに収容されるブロ
ック数、そして第３は前述の通り辞書には２文字長の単
語が存在するので、そのインデックスに２文字長の単語
があるかどうかを示すフラグである（例えばＡＢのイン
デックスにＡＢという２文字長の単語が存在するならば
フラッグは“ｏｎ”となる）。実際には、インデックス
情報部は第４図の構成であり、インデックステーブルは
この様な情報が４０９６個で成り立っており、その１つ
１つが０〜４０９６のインデックス（値）に対応してい
る。
第６図について、説明を加えろとオフセットは１８ビツ
トであるため、最大２　”−１＝２６２，１４３まで表
わすことができるが、今回の圧縮法ではオフセット値が
この値を超えろことはない。また、ブロック数は５ビツ
トで最大２’−１＝３１までであるか、実際に圧縮を行
った結果、現在の辞書ではブロック長ｎが約２５６バイ
ト以上あればブロック数が３１を超えることはない。従
って原辞書に変更があった場合や、ブロック長ｎを２５
６よりも小さくとった場合、また、辞書構造を変更した
場合などには、注意が必要である。
このようにして、インデックス部を構成するとインデッ
クス部容量は、４，０９６ｘ　３＝　１２．２８８バイ
トとなる。このような構成のインデックス部を所有する
辞書では、辞書検索を行う際、次の２つの特別な場合の
み、辞書本体を探索せずに速やかに該当単語の有無を判
別することができる。
ｉ）キーワードのインデックス値が示すインデックス情
報のブロック数が０ならば、そのインデックスに登録さ
れている単語はない。即ち、キーワードは辞書に登録さ
れていない。
ｉｉ）キーワードが２文字長の単語であったならば、イ
ンデックス値が示すインデックス情報のフラグを調べて
フラグが°ｏｎ”ならば該当する単語は辞書に登録され
ている。また、フラグが“ｏｆＴ”ならば登録されてい
ない。
辞書本体部 辞書本体部は、インデックスに使用されろ先頭２文字を
除いた単語の集合で、ブロックを基本単位とした構成で
あり、各ブロックの先頭は必らずバイト境界である。ま
た、各ブロックの先頭第１単語は、ブロック単語の２分
探索を行なうため第７図で示される内部コード（第１表
参照）にフラグを付加したバイト単位の符号列である。
従ってブロー７りの先頭第１単語はＥ　ＯＷ（Ｅｎｄ　
ｏｒ　Ｗｏｒｄ）あるいはＥ　ＯＢ　（Ｅｎｄ　ｏｒＢ
Ｌｏｃｋ）のフラグが立つまでの符号例で、らしＥＯＢ
のフラグが“ｏｎ”ならば、そのブロックにはそれ以上
単語が登録されていないということである。それゆえこ
の様な符号列に対して上位２　ｂｉｔをマスクすること
で容易に内部コードに復元できる。また、内部コードは
対応するアスキーコードの値を正順に配置しているので
、キーワードとの比較ら単純な減算のみで行うことがで
きる。
ブロックの第２単語以降は、府述の６４種類の文字と相
対圧縮符号及びＥＯＷ、ＥＯＢに対応するハフマンコー
ドで構成される。相対圧縮符号とは、１つ前の単語との
先頭文字からの共通部分の長さを示すコードで、インデ
ックスのための先頭２文字を削除した後の共通部分が１
文字ならば相対圧縮符号を用いる必要はないので２文字
以上共通部分があった場合に適用する（第８図参照）。
第８図では、便宜上凸符号を＊４やＥＯＷという形で表
わしていたが、実際にこれらの符号はハフマンコードと
して記録されている。このような方法で単語列の符号化
圧縮を行なうが、１つのインデックスに属する単語列（
例えばインデックスＡＡならばＡＡで始まる単語）が符
号化されていく過程でその容量がブロック長ｎを超える
可能性がある。この場合、インデックス内で２分探索を
行わせるためにブロック長ｎを超えて格納されている単
語は、次のブロックの先頭第１単語として扱い（即ち相
対圧縮らハフマン符号化も行わない）そのブロックの終
了としてのＥＯＢ符号を格納する。そして次のブロック
の先頭は必らずそのインデックスのオフセットの値にブ
ロック長ｎの整数倍を加えた値になるようにする。従っ
てこのようなインデックスには複数のブロックが存在す
ることになるので、オフセット、ブロック数、ブロック
長ｎが既知であるから、インデックス中の各ブロックの
先頭第１単語に対してブロック単位で２分探索法を試み
ることができる。２分探索法を行なうことでキーワード
か登録されていると考えられるブロックを特定すること
ができるので、そのブロックについてのみハフマンコー
ドを復号し、順次探索を行えばよい。ただしスペルチェ
ックを行なうキーワードが辞書に登録されていないもの
であれば、探索の過程で間違ったハフマンコード展開を
する可能性があるので、各ブロックの最後には、ＥＯＷ
のかわりにＥＯＢを必ず記録する。
このことにより、ハフマンコード展開時（フロック内探
索時）ＥＯＢ符号を検出しても尚キーワードが見い出せ
なかったならばキーワードは辞書に登録されていないの
で探索を打ち切る。
以上述べた辞書の構造を第９図に示す。
ハフマンコードの生成 ハフマンコードの使用については、圧縮を行なうデータ
である英単語辞書が既知であるためハフマン符号化法に
よる圧縮が効果的である。
ハフマンコードを割当てるにあたって各コードの出現頻
度を求めなければならないが、そのためのデータを作る
にはハフマンコードが決定して始めて完全な圧縮ができ
るので（何故ならハフマンコードは可変長ビット列であ
り辞書の圧縮に相対圧縮を利用しているので）、その上
で出現頻度がわかるという矛盾が生じるので、符号化に
対応するハフマンコードのコード長か全て８　ｂｉｔで
あるものとして実際に圧縮を行い、相対圧縮コードや相
対圧縮できなかった非圧縮文字そして単語間のセパレー
タコードであろＥＯＷと、ブロック終了コードであるＥ
ＯＢとの各コードの出現頻度をらとにした（第２表及び
第３表参照）。
従って、第２表に示す出現頻度及び出現確率は正確なも
のでないが、統計的には真値がらかけ離れた値になるこ
とはないので、このデータをらとにしてハフマンコード
を生成した。但し、ハフマンコードのコード長が８　ｂ
ｉｔを超えた場合、ハフマンコードの復号の処理が複雑
になる（後述する復号方法による変換テーブルの容量が
膨大になるのを防ぐため）ので、出現細度の比較的少な
いコ−ドについて全てをまとめて“ｏｔｈｅｒ”という
特別なハフマンコードを割当ることにより生成するハフ
マンコードの最大コード長を８　ｂｉｔに押さえた。こ
のｏｔｈｅｒコードは、“ｏｔｈｅｒ”に対応するハフ
マンコードに続けて６　ｂｉｔの文字コードを付加する
という形で拡張する。従って、このコード系は純粋のハ
フマンコードではなく修正ハフマンコードである。ハフ
マンコード変換表を第４表に示す。
ハフマンコード復号化のアルゴリズム 実際にスペルチェックを行う場合には、圧縮された辞書
を復号するという処理が必要となるが、ハフマンコード
は可変長ビット列であるｆ；め、復号の処理は＊ｍであ
る。例えば辞書中のデータを１ビツトづつ取り出してハ
フマンコードとパターンマツチングを行ない一致しなけ
れば更に１ビツト取出して１ビツトシフトを行ない、キ
ーを詰めて再度パターンマツチングを行なうということ
を、キーかハフマンコードにマツチするまで操り返すと
いうような方法で復号を行っていたので復号処理に要す
る時間的ロスが大きくスペルチェックとして役にたたな
い。
そこで辞書中のデータを８　ｂｉｔ単位で取出し、この
８　ｂｉｔのデータをＯ〜２５５の値とみなし、テーブ
ル参照より取込んだ１６ｂｉｔのデータ中実際にハフマ
ンコードとして有効なビット長、およびそのハフマンコ
ードに割り付けられた内部コードを得る。そして有効ビ
ット長だけ辞書の読み込みポインターを進め、次の復号
処理に備えるという手順によってハフマンコードを復号
する。このような復号処理では、ハフマンコード展開に
要する処理速度は、高速となる反面、参照テーブルのた
めのエリアが必要となる。今回の修正ハフマンコードで
は、ハフマンコードの最大ビット長が８ビツトになるよ
うに設けているので参照テーブルの容量は、２＠×２バ
イト−５１２バイトとなる（２バイトとは、有効ビット
長［３ｂｉｔ］および対応する内部コード［８ｂｉｔＦ
の情報を格納するエリアである）。
ところがｏｔｈｅｒコードに対応するハフマンコードを
１１Ｍした場合、辞書中よりさらに６　ｂｉｔの拡張コ
ードを得て、この拡張コードを変換テーブルにより内部
コードに変換しなければならない。このための変換テー
ブルの容量は拡張コードに割当てられたコード敗である
４９バイトである。
次にこの実施例における辞書検索機能を第１０図ａ１及
び第１０図すに示すフローチャートに従って説明する。
まず、ファイルあるいは入力装置より入力された文字列
から単語を切り出すことにより単語を抽出する（ステッ
プ２Ｇ）。単語に付随する不要な文字を削減する（ｘｘ
ｘ’はｘｘｘに、ｘｘｘ’　ｓはＸＸＸにする）（ステ
ップ２１）。探索する単語（以後キーワードと称す）の
長さを判断しくステップ２２）、単語の長さが１文字な
らば辞書探索を行わず、検索を終了する（ステップ２３
）。単語の長さが１文字でない場合、辞書探索が開始さ
れ（ステップ２４）、キーワードが辞書に登録されてい
るかを判断しくステップ２５）、登録されていなければ
原単語の全ての変化形について探索が行われ、検索を行
う単語がなければ探索を終了する（ステップ２８．２３
）。ステップ２６で、全ての変化形についての探索が行
われていない場合、変化形（ＡＢＣの場合Ａ　ｂ　ｃ　
ｓまたはａｂｃなどの変化形）生成が行われ（ステップ
２７）再び辞書検索が行われる。
次に辞書検索の過程について説明する。まず、キーワー
ドの先ｉＪ２文字よりインデックスの値を算出する（ス
テップ２８）。そして、キーワードより先頭２文字を削
除する。単語長が２文字であるか判断され（ステップ２
９）、単語長が２文字の場合は、該当するインデックス
の２文字単語登録フラグをチェックすることにより（ス
テップ３０）、登録の有無が判別できる。該当するイン
デックスの格納ブロック数が“Ｏ”とは、そのインデッ
クスに格納されている単語が無いということであるから
（ステップ３１）探索を終了する。ブロック数が“０°
でない場合は、辞書本体での探索を行うため、キーワー
ドを内部コードに変換しくステップ３２）、探索の第１
段階としてブロック単位での２分探索を行う（ステップ
′３３）。２分探索を行うた段階で、キーワードを発見
できたかを判断し、すなわちキーワードが登録されてい
たかを判断しくステップ３４）、登録されていなければ
、キーワードの未登録が判断される（ステップ３５）。
探索中に、キーワードと辞書の単語の大きさを比較する
ことにより以後の探索を行っても登録されていないこと
が判別できる（辞書はアスキー類に登録されているため
）。以後、圧縮辞書の逐次探索としての第２段階の探索
を行う。圧縮された辞書本体（修正ハフマンコード）よ
り１単語ずつ単語を取り出し、キーワードと比較するた
めに、取り出した単語を内部コードに変換する（ステッ
プ３６）。
ＥＯＢを検出した場合（ステップ３７）、それ以上単語
が登録されていないため探索を終了し、また、ＥＯＢが
検出されていない場合は、キーワードが登録されていた
かを判断しくステップ３８）、登録されていなければ、
キーワードの未登録が判断され（ステップ３９）、未登
録であれば探索を終了し、未登録と判断されなければス
テップ３６に戻る。
結果 ７７．２４０の単語が登録されている辞書を用いてスペ
ルチェックを行ったところ、ブロック長ｎ＝２５６バイ
トで１単語当りの平均スペルチェック速度は６９＋ａｓ
ｅｃ／ｗｏｒｄとなった。また、辞書圧縮の容量は辞書
本体で約１８２ＫＢ、インデックスと変換テーブルを含
めると約１９５１［Ｂとなりスペルチェックのプログラ
ムも含めて２Ｍｂｉｔ以内が可能となった。
また、この処理速度をより早くするためにはハフマンコ
ード復号にともなうビット演算処理をやめ、バイト単位
で圧縮を行えばブロック長ｎ＝２５６バイトで約２７ｓ
＋ｓｅｃ／ｗｏｒｄとなる。
与えられた環境で前者を選ぶか後者をえらぶかを判断す
る。
（ト）発明の効巣 この発明によれば、単語の文字発生頻度をハフマンコー
ドに編集し、かつ単語をブロック単位に分けて記憶して
いるため、スペルチェックとして使われる欧文用単語辞
書の記憶容量の削減を図ることができ、スペルチェック
の際の処理速度を速めることができる。
ＡＢＣＤＩ！ ００８　０５Ｂ３　０６２４　１１５４　０７２４　０
４７０ＴＯＴ　　３８７９　３５８６　　フ３０９　４
６７１　３０６４１１５表亀 ＦＧＨｒ、７ＫＬＭ ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏ
ｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏ。
ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏ
ｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏ。
ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏ
ｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏ。
ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏ
ｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏ。
ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏ
ｏｏｏ　ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏ。
ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏ
ｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏ。
ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏ
ｏｏｏ　　ｏｏｏｏ　　ｏｏｏｏ　　ｏｏｏ。
第Ｓ表ｂ ６７００　２８９２　１３４３　０９２５　１５６３　
００１９　０１８４　０１４２　００上上
【図面の簡単な説明】
第１図はこの発明の構成を示すブロック図、第２図はこ
の発明の一実施例の構成を示すブロック図、第３図は同
じく圧縮辞書の構造を示す″“″−第４図は同じく単語
の相対圧縮を示す説明１５図は同じく辞書のブロック化
を示す説明１６図は同じくインデッ、クス情報部の構成
図、図は同じく先頭第１単語の符号列を示す説：第８図
は同じく相対圧縮符号を示す説明図−図は同じく辞書構
造を示す説明図、第１０１′びに第１Ｏ図すは実施例の
作動を示すフロートである。 ！・・・・・・入力手段、　　　　２・・・・・・記憶
手；３・・・・・・出力手段、　　　　４・・・・・・
制御手１５・・・・・・圧縮辞書記憶手段、 ６・・・・・・スペルチェック手段。 第１　図 第２図 払 第３図 イ）デ゛、Ｊクス音β　　　　　　　　　　名串書本イ
ネＦＬ＃１特書の甚本槙追　　。 第４図 算話　　　　　　　心獣柾暢 第５図 特　蓄　４シ　イ」ミ 古辛書のアロツク花 抱６図 フラグ（１ビツト） イ）デックス情報郁の１１Ｋ成 第７図 ８ビツト（１ｔｃイト） 第８図 虎ｌｉｋ話　　　　先顛２刻清眸　　絽対ｉ鴫第９図 辞倉本体 繭１０図　ａ

Claims (1)

    【特許請求の範囲】
  1. １、文字情報および各種の指示を入力する入力手段と、
    入力手段から入力された文字情報を記憶する記憶手段と
    、文字情報を表示する表示手段と、入力手段の指示に基
    づき記憶手段に記憶されている文字情報を表示手段に出
    力する制御手段と、ｎバイト毎に分割されたブロックを
    一単位として構成され、１つのブロックにそのブロック
    の先頭第１単語が所定コードに変換された非圧縮なバイ
    ト単位の文字列として格納され、かつ、先頭第１単語と
    関連のある第２単語を含むそれ以降の単語が、目的の単
    語の１つ前に格納された単語との共通部分を表わす相対
    圧縮コードおよび相対圧縮ができなかった非圧縮コード
    を出現頻度を考慮して割り付けたハフマンコードに置換
    された情報として格納される辞書本体部と、辞書本体部
    からのオフセットと、そのオフセットで示される１群の
    ブロックの数とで構成されるインデックス部とからなる
    情報が記憶される圧縮辞書記憶手段と、キーワードの先
    頭２文字より圧縮辞書記憶手段のインデックス情報の格
    納されるアドレスを計算し、そのインデックスのオフセ
    ットおよびブロック数を取出し、ブロックの先頭第１単
    語についてブロック単位で２分検索を行うスペルチェッ
    ク手段とを具備することにより、辞書容量の削減および
    スペルチェックの処理速度を高めたことを特徴とする文
    字処理装置。
JP62128687A 1987-05-26 1987-05-26 文字処理装置 Expired - Lifetime JPH0682370B2 (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
JP62128687A JPH0682370B2 (ja) 1987-05-26 1987-05-26 文字処理装置
DE3852341T DE3852341T2 (de) 1987-05-26 1988-05-24 Zeichenverarbeitungssystem mit Funktion zur Prüfung von Rechtschreibung.
EP88304675A EP0293161B1 (en) 1987-05-26 1988-05-24 Character processing system with spelling check function
US07/198,503 US4959785A (en) 1987-05-26 1988-05-25 Character processing system with spelling check function that utilizes condensed word storage and indexed retrieval

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
JP62128687A JPH0682370B2 (ja) 1987-05-26 1987-05-26 文字処理装置

Publications (2)

Publication Number Publication Date
JPS63292365A true JPS63292365A (ja) 1988-11-29
JPH0682370B2 JPH0682370B2 (ja) 1994-10-19

Family

ID=14990940

Family Applications (1)

Application Number Title Priority Date Filing Date
JP62128687A Expired - Lifetime JPH0682370B2 (ja) 1987-05-26 1987-05-26 文字処理装置

Country Status (4)

Country Link
US (1) US4959785A (ja)
EP (1) EP0293161B1 (ja)
JP (1) JPH0682370B2 (ja)
DE (1) DE3852341T2 (ja)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0554077A (ja) * 1991-08-29 1993-03-05 Nec Corp 単語辞書検索装置
JPH0785047A (ja) * 1993-08-02 1995-03-31 Xerox Corp コンパクトにエンコードされて記憶されたストリングの組を有する製品
US6502064B1 (en) 1997-10-22 2002-12-31 International Business Machines Corporation Compression method, method for compressing entry word index data for a dictionary, and machine translation system

Families Citing this family (34)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5297038A (en) * 1985-09-27 1994-03-22 Sharp Kabushiki Kaisha Electronic dictionary and method of codifying words therefor
US5258910A (en) * 1988-07-29 1993-11-02 Sharp Kabushiki Kaisha Text editor with memory for eliminating duplicate sentences
JPH0833806B2 (ja) * 1989-03-13 1996-03-29 富士通株式会社 データ処理装置における多国語変換処理方式
US5333313A (en) * 1990-10-22 1994-07-26 Franklin Electronic Publishers, Incorporated Method and apparatus for compressing a dictionary database by partitioning a master dictionary database into a plurality of functional parts and applying an optimum compression technique to each part
US5229936A (en) * 1991-01-04 1993-07-20 Franklin Electronic Publishers, Incorporated Device and method for the storage and retrieval of inflection information for electronic reference products
CA2051135C (en) * 1991-09-11 1996-05-07 Kim D. Letkeman Compressed language dictionary
US5357431A (en) * 1992-01-27 1994-10-18 Fujitsu Limited Character string retrieval system using index and unit for making the index
JP3189186B2 (ja) * 1992-03-23 2001-07-16 インターナショナル・ビジネス・マシーンズ・コーポレ−ション パターンに基づく翻訳装置
GB9311580D0 (en) * 1993-06-04 1993-07-21 Phonelink Data Limited Data retrieval system
US5724594A (en) * 1994-02-10 1998-03-03 Microsoft Corporation Method and system for automatically identifying morphological information from a machine-readable dictionary
JP2809341B2 (ja) 1994-11-18 1998-10-08 松下電器産業株式会社 情報要約方法、情報要約装置、重み付け方法、および文字放送受信装置。
JP3003915B2 (ja) * 1994-12-26 2000-01-31 シャープ株式会社 単語辞書検索装置
US5809494A (en) * 1995-11-16 1998-09-15 Applied Language Technologies, Inc. Method for rapidly and efficiently hashing records of large databases
GB9704951D0 (en) * 1997-03-11 1997-04-30 Philips Electronics Nv Message transmission system, a method of operating the message transmission system and a primary station therefor
US6298321B1 (en) * 1998-11-23 2001-10-02 Microsoft Corporation Trie compression using substates and utilizing pointers to replace or merge identical, reordered states
US6304878B1 (en) 1998-11-23 2001-10-16 Microsoft Corporation Method and system for improved enumeration of tries
US6473621B1 (en) * 1999-05-28 2002-10-29 Nokia Inc. Method and apparatus for entering shortcut messages
US6675169B1 (en) 1999-09-07 2004-01-06 Microsoft Corporation Method and system for attaching information to words of a trie
EP1385640B1 (en) * 2000-12-11 2006-02-22 United Parcel Service Of America, Inc. Compression utility for use with smart label printing and pre-loading
US7667630B2 (en) * 2004-12-07 2010-02-23 Nippon Telegraph And Telephone Corporation Information compression-encoding device, its decoding device, method thereof, program thereof, and recording medium storing the program
US8509826B2 (en) * 2005-09-21 2013-08-13 Buckyball Mobile Inc Biosensor measurements included in the association of context data with a text message
US8275399B2 (en) * 2005-09-21 2012-09-25 Buckyball Mobile Inc. Dynamic context-data tag cloud
US7580719B2 (en) * 2005-09-21 2009-08-25 U Owe Me, Inc SMS+: short message service plus context support for social obligations
US8515468B2 (en) 2005-09-21 2013-08-20 Buckyball Mobile Inc Calculation of higher-order data from context data
US8489132B2 (en) * 2005-09-21 2013-07-16 Buckyball Mobile Inc. Context-enriched microblog posting
US8509827B2 (en) * 2005-09-21 2013-08-13 Buckyball Mobile Inc. Methods and apparatus of context-data acquisition and ranking
US7551935B2 (en) 2005-09-21 2009-06-23 U Owe Me, Inc. SMS+4D: short message service plus 4-dimensional context
US9166823B2 (en) * 2005-09-21 2015-10-20 U Owe Me, Inc. Generation of a context-enriched message including a message component and a contextual attribute
US9042921B2 (en) * 2005-09-21 2015-05-26 Buckyball Mobile Inc. Association of context data with a voice-message component
JP4398988B2 (ja) * 2007-03-26 2010-01-13 株式会社東芝 構造化文書を管理する装置、方法およびプログラム
CN101697116B (zh) * 2009-10-27 2011-11-09 飞天诚信科技股份有限公司 数据变换方法及装置
US8489131B2 (en) * 2009-12-21 2013-07-16 Buckyball Mobile Inc. Smart device configured to determine higher-order context data
US10127219B2 (en) * 2016-12-09 2018-11-13 Hong Kong Applied Science and Technoloy Research Institute Company Limited System and method for organizing and processing feature based data structures
CN112527949B (zh) * 2020-12-15 2023-01-13 建信金融科技有限责任公司 数据存储与检索方法、装置、计算机设备及存储介质

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4748589A (en) * 1979-09-06 1988-05-31 Sharp Kabushiki Kaisha Electronic translator
US4381551A (en) * 1979-09-13 1983-04-26 Sharp Kabushiki Kaisha Electronic translator
US4393462A (en) * 1979-10-24 1983-07-12 Sharp Kabushiki Kaisha Electronic translator with means for pronouncing input words and translated words
JPS59868B2 (ja) * 1979-10-24 1984-01-09 シャープ株式会社 単語の基本形認識装置およびこれを用いた翻訳装置
JPS6017564A (ja) * 1983-07-08 1985-01-29 Brother Ind Ltd 電子辞書
US4747053A (en) * 1985-05-20 1988-05-24 Brother Kogyo Kabushiki Kaisha Electronic dictionary
US4758955A (en) * 1985-07-19 1988-07-19 Carson Chen Hand-held spelling checker and method for reducing redundant information in the storage of textural material
US4782464A (en) * 1985-12-26 1988-11-01 Smith Corona Corporation Compact spelling-check dictionary

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0554077A (ja) * 1991-08-29 1993-03-05 Nec Corp 単語辞書検索装置
JPH0785047A (ja) * 1993-08-02 1995-03-31 Xerox Corp コンパクトにエンコードされて記憶されたストリングの組を有する製品
US6502064B1 (en) 1997-10-22 2002-12-31 International Business Machines Corporation Compression method, method for compressing entry word index data for a dictionary, and machine translation system

Also Published As

Publication number Publication date
EP0293161A3 (en) 1990-06-27
EP0293161A2 (en) 1988-11-30
DE3852341T2 (de) 1995-06-01
DE3852341D1 (de) 1995-01-19
EP0293161B1 (en) 1994-12-07
JPH0682370B2 (ja) 1994-10-19
US4959785A (en) 1990-09-25

Similar Documents

Publication Publication Date Title
JPS63292365A (ja) 文字処理装置
Adjeroh et al. The Burrows-Wheeler Transform:: Data Compression, Suffix Arrays, and Pattern Matching
US6047298A (en) Text compression dictionary generation apparatus
JP3889762B2 (ja) データ圧縮方法、プログラム及び装置
KR101157693B1 (ko) 토큰스페이스 저장소와 함께 사용하기 위한 멀티-스테이지질의 처리 시스템 및 방법
US8095526B2 (en) Efficient retrieval of variable-length character string data
US5333313A (en) Method and apparatus for compressing a dictionary database by partitioning a master dictionary database into a plurality of functional parts and applying an optimum compression technique to each part
JP2979106B2 (ja) データ圧縮
JP2000516058A (ja) 頻度の高いキャラクタの組み合わせ、ワード及び／又はフレーズでプレフィルした辞書を用いるＬｅｍｐｅｌ―Ｚｉｖデータ圧縮技術
JP4003854B2 (ja) データ圧縮装置及び復元装置並びにその方法
Mayne et al. Information compression by factorising common strings
CN114491597A (zh) 一种基于汉字部件组合的文本无载体信息隐藏方法
JPH10261969A (ja) データ圧縮方法および装置
JP2729416B2 (ja) テキストデータの復元方法
JP3241787B2 (ja) データ圧縮方式
JPH0554077A (ja) 単語辞書検索装置
JPH056398A (ja) 文書登録装置及び文書検索装置
JPH0546358A (ja) テキストデータの圧縮方法
Zhang Transform based and search aware text compression schemes and compressed domain text retrieval
JP2774350B2 (ja) データ圧縮方法および圧縮データのデータ復元方法
JPH07182354A (ja) 電子文書の作成方法
WO1991013395A1 (en) Data compression and restoration method and device therefor
JPH05152971A (ja) データ圧縮・復元方法
JP3384844B2 (ja) データ圧縮方法および装置並びにデータ復元方法および装置
JP3053656B2 (ja) データ圧縮における辞書登録方式