JPS63153632A - 文字列検索方式 - Google Patents
文字列検索方式Info
- Publication number
- JPS63153632A JPS63153632A JP61302116A JP30211686A JPS63153632A JP S63153632 A JPS63153632 A JP S63153632A JP 61302116 A JP61302116 A JP 61302116A JP 30211686 A JP30211686 A JP 30211686A JP S63153632 A JPS63153632 A JP S63153632A
- Authority
- JP
- Japan
- Prior art keywords
- character
- character string
- unknown
- string
- characters
- 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.)
- Pending
Links
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔概要〕
未知文字列を文字列テーブルから読出した文字と一文字
ずつ比較する動作を繰り返し、一致したことで未知文字
列を認識する計算機において、未知文字列の先頭文字を
認識した後、この認識した先頭文字に対応する範囲外の
文字列テーブルに対する比較動作を省略し得るようにし
て、プロセ。
ずつ比較する動作を繰り返し、一致したことで未知文字
列を認識する計算機において、未知文字列の先頭文字を
認識した後、この認識した先頭文字に対応する範囲外の
文字列テーブルに対する比較動作を省略し得るようにし
て、プロセ。
すが文字比較を行う回数を減少させ、計算機の処理時間
の短縮を実現した。
の短縮を実現した。
本発明は計算機の文字列認識方式に係り、特に未知文字
列を、予め備えた文字列テーブルと順次比較して認識す
る際の、検索時間を短縮する文字列検索方式に関する。
列を、予め備えた文字列テーブルと順次比較して認識す
る際の、検索時間を短縮する文字列検索方式に関する。
情報処理の分野においては、成る未知文字列を認識する
ため、計算機のメモリ等に備えた文字列テーブルから、
順次文字列を読出して未知文字列と比較し、一致したこ
とでその成る未知文字列を認識している。この場合、一
般に文字列の先頭から一文字ずつを比較し、一致すると
次の文字を比較する動作を繰り返し、総ての文字の比較
結果が一致すると、未知文字列の認識が完了する。 ゛
従って、文字列テーブルは文字列を構成する文字数によ
り、語長が１からＮまでのものを夫々まとめたテーブル
の集合で構成されており、未知文字列の文字数と一致す
る語長のテーブルが選択されて、比較動作が行われてい
る。このため、文字列の文字数が多くなる程文字を比較
する回数が増加し、検索時間が増加することから、計算
機の処理時間が短い文字列検索方式の出現が望まれてい
る。
ため、計算機のメモリ等に備えた文字列テーブルから、
順次文字列を読出して未知文字列と比較し、一致したこ
とでその成る未知文字列を認識している。この場合、一
般に文字列の先頭から一文字ずつを比較し、一致すると
次の文字を比較する動作を繰り返し、総ての文字の比較
結果が一致すると、未知文字列の認識が完了する。 ゛
従って、文字列テーブルは文字列を構成する文字数によ
り、語長が１からＮまでのものを夫々まとめたテーブル
の集合で構成されており、未知文字列の文字数と一致す
る語長のテーブルが選択されて、比較動作が行われてい
る。このため、文字列の文字数が多くなる程文字を比較
する回数が増加し、検索時間が増加することから、計算
機の処理時間が短い文字列検索方式の出現が望まれてい
る。
第３図は従来の技術を説明するブロック図である。
語長側ポインタテーブル１１は未知文字列の文字数に応
じて、語長が１の文字列テーブル１２、語長が２の文字
列テーブル１３、語長が３の文字列テーブル１４、語長
が４の文字列テーブル１５、−・−１語長が１０の文字
列テーブル１６を夫々指示する。
じて、語長が１の文字列テーブル１２、語長が２の文字
列テーブル１３、語長が３の文字列テーブル１４、語長
が４の文字列テーブル１５、−・−１語長が１０の文字
列テーブル１６を夫々指示する。
例えば、未知文字列が３文字であると、語長側ポインタ
テーブル１１は文字列テーブル１４の最初の文字列１４
１を指示する。この指示により計算機のプロセッサ（図
示せず）は文字列１４１の先頭の文字を読出して、未知
文字列の先頭の文字と比較する。一致しなければ、文字
列１４２の先頭の文字を読出して、未知文字列の先頭の
文字と比較する。
テーブル１１は文字列テーブル１４の最初の文字列１４
１を指示する。この指示により計算機のプロセッサ（図
示せず）は文字列１４１の先頭の文字を読出して、未知
文字列の先頭の文字と比較する。一致しなければ、文字
列１４２の先頭の文字を読出して、未知文字列の先頭の
文字と比較する。
プロセッサはこの動作を比較結果が一敗するまで繰り返
すが、一致しない時はこの比較動作を文字列テーブル１
４の文字列の最後まで操り返した後玉一致を報告して比
較動作を停止する。
すが、一致しない時はこの比較動作を文字列テーブル１
４の文字列の最後まで操り返した後玉一致を報告して比
較動作を停止する。
若し、例えば文字列１４２で先頭文字が一致したとする
と、プロセッサはここで文字列１４２の二番目の文字と
、未知文字列の二番目の文字とを比較する。そして、上
記同様文字列テーブルの最後まで一致しなければ、不一
致を報告し、一致すれば未知文字列の三番目の文字と、
文字列テーブル１４から読出した先頭文字と二番目の文
字が一致した文字列の三番目の文字との比較を行う。
と、プロセッサはここで文字列１４２の二番目の文字と
、未知文字列の二番目の文字とを比較する。そして、上
記同様文字列テーブルの最後まで一致しなければ、不一
致を報告し、一致すれば未知文字列の三番目の文字と、
文字列テーブル１４から読出した先頭文字と二番目の文
字が一致した文字列の三番目の文字との比較を行う。
ここで、先頭文字と二番目及び三番目の文字が一致すれ
ば、その文字列テーブル１４から読出された文字列は未
知文字列と同一であるから、計算機の未知文字列の認識
が完了する。
ば、その文字列テーブル１４から読出された文字列は未
知文字列と同一であるから、計算機の未知文字列の認識
が完了する。
上記の如く、従来は計算機が語長側ポインタテーブル１
１の指示に従い、文字列テーブル１２〜１６から該当す
る文字列テーブルを選択し、この文字列テーブルから読
出した文字列の一文字ずつを、未知文字列の一文字と比
較する動作を、総ての文字が一致する文字列が見つかる
まで、文字列テーブル内の文字列に対して、文字列の配
列順に繰り返すため、文字の比較回数が多く、処理時間
が長いという問題がある。
１の指示に従い、文字列テーブル１２〜１６から該当す
る文字列テーブルを選択し、この文字列テーブルから読
出した文字列の一文字ずつを、未知文字列の一文字と比
較する動作を、総ての文字が一致する文字列が見つかる
まで、文字列テーブル内の文字列に対して、文字列の配
列順に繰り返すため、文字の比較回数が多く、処理時間
が長いという問題がある。
第１図は本発明の原理ブロック図である。
プロセッサ１７はメモリ１８に例えばディスク２２から
語長側ポインタテーブル１９と先頭文字順ポインタテー
ブル２０と文字列テーブル２１をロードする。そして、
インタフェース回路２３がら入る未知文字列をメモリ１
８に格納する。
語長側ポインタテーブル１９と先頭文字順ポインタテー
ブル２０と文字列テーブル２１をロードする。そして、
インタフェース回路２３がら入る未知文字列をメモリ１
８に格納する。
プロセッサ１７は文字列テーブル２１０語長側ポインタ
テーブル１９が指示する語長１の文字列テーブルから文
字コードを読出し、未知文字列の先頭の文字コードと比
較し、一致したことにより未知文字列の先頭の文字を認
識する。
テーブル１９が指示する語長１の文字列テーブルから文
字コードを読出し、未知文字列の先頭の文字コードと比
較し、一致したことにより未知文字列の先頭の文字を認
識する。
続いて、プロセッサ１７は未知文字列の文字数により、
語長側ポインタテーブル１９が指示する先頭文字順ポイ
ンタテーブル２０を参照する。
語長側ポインタテーブル１９が指示する先頭文字順ポイ
ンタテーブル２０を参照する。
先頭文字順ポインタテーブル２０は所定の順序で文字列
テーブル２１を索引するように構成されており、未知文
字列の先頭文字に対応して、文字列テーブル２１の索引
範囲内の文字列を配列順に指示する。
テーブル２１を索引するように構成されており、未知文
字列の先頭文字に対応して、文字列テーブル２１の索引
範囲内の文字列を配列順に指示する。
先頭文字順ポインタテーブル２０は未知文字列の先頭文
字に対応して、文字列テーブル２１の比較対象となる文
字列の範囲を指示するため、文字列テーブル２１の比較
する必要の無い文字列の比較動作を省略することが可能
となり、プロセッサ１７の比較処理時間を短縮すること
が出来る。
字に対応して、文字列テーブル２１の比較対象となる文
字列の範囲を指示するため、文字列テーブル２１の比較
する必要の無い文字列の比較動作を省略することが可能
となり、プロセッサ１７の比較処理時間を短縮すること
が出来る。
第２図は本発明の一実施例を説明する図である。
第２図は第１図の語長側ポインタテーブル１９と先頭文
字順ポインタテーブル２０と文字列テーブル２１の詳細
内容を示すもので、プロセッサ１７は未知文字列の先頭
文字を認識するため、語長側ポインタテーブル１９が指
示する文字列テーブル２１１から文字の配列順に順次文
字コードを読出し、比較する。
字順ポインタテーブル２０と文字列テーブル２１の詳細
内容を示すもので、プロセッサ１７は未知文字列の先頭
文字を認識するため、語長側ポインタテーブル１９が指
示する文字列テーブル２１１から文字の配列順に順次文
字コードを読出し、比較する。
文字列テーブル２１１は語長１の文字列テーブルであり
、例えばＡ〜Ｚまでアルファベット順に並んでおり、未
知文字列が例えばＥＮＤであるとすると、先頭文字Ｅが
プロセッサ１７に認識される。
、例えばＡ〜Ｚまでアルファベット順に並んでおり、未
知文字列が例えばＥＮＤであるとすると、先頭文字Ｅが
プロセッサ１７に認識される。
プロセッサ１７は未知文字列が３文字であることから、
語長側ポインタテーブル１９の指示する先頭文字順ポイ
ンタテーブル２０２を参照する。
語長側ポインタテーブル１９の指示する先頭文字順ポイ
ンタテーブル２０２を参照する。
先頭文字順ポインタテーブル２０２はＡ−Ｚまでアルフ
ァベット順に文字列テーブルを指示する構成となってお
り、プロセッサ１７は未知文字列の先頭がＥであるため
、先頭文字順ポインタテーブル２０２のＡ−Ｄまでを飛
び越して、Ｅが指示する文字列テーブル２１３の検索開
始を示す文字列の一番目の文字コードを読出し、未知文
字列の二番目の文字コードと比較する。
ァベット順に文字列テーブルを指示する構成となってお
り、プロセッサ１７は未知文字列の先頭がＥであるため
、先頭文字順ポインタテーブル２０２のＡ−Ｄまでを飛
び越して、Ｅが指示する文字列テーブル２１３の検索開
始を示す文字列の一番目の文字コードを読出し、未知文
字列の二番目の文字コードと比較する。
文字列テーブル２１３は例えばｒＡＤＤＪがら順次ｒＦ
ＯＲＪまで比較すべき文字列を用意しているものとする
と、先頭の一文字を除いて、二番目と三番目の文字をテ
ーブルにして備えており、図示する如く、ｒＡＤＤＪは
ＤＤのみを、ｒＢＩＴ」はＩＴ（７）みを、ｒＥＧＩＪ
はＧｒのみを、ｒＥＭＩＪはＭＩのみを、ｒＥＮＤＪは
ＮＤのみを、ｒＥＯＩ’ＪはＯＰのみを、ｒＦＯＲＪは
ＯＲのみを備えている。
ＯＲＪまで比較すべき文字列を用意しているものとする
と、先頭の一文字を除いて、二番目と三番目の文字をテ
ーブルにして備えており、図示する如く、ｒＡＤＤＪは
ＤＤのみを、ｒＢＩＴ」はＩＴ（７）みを、ｒＥＧＩＪ
はＧｒのみを、ｒＥＭＩＪはＭＩのみを、ｒＥＮＤＪは
ＮＤのみを、ｒＥＯＩ’ＪはＯＰのみを、ｒＦＯＲＪは
ＯＲのみを備えている。
先頭文字順ポインタテーブル２０２は、ｒＥＧ■」から
ｒＥＯＰＪまでの文字列群の先頭のＣＩを指示するため
、プロセッサ１７はＧの文字コードを読出し、未知文字
列のＮの文字コードと比較する。当然不一致となるため
、プロセッサ１７は次のＭの文字コードと比較し、不一
致のため次のＮの文字コードを続出して比較する。
ｒＥＯＰＪまでの文字列群の先頭のＣＩを指示するため
、プロセッサ１７はＧの文字コードを読出し、未知文字
列のＮの文字コードと比較する。当然不一致となるため
、プロセッサ１７は次のＭの文字コードと比較し、不一
致のため次のＮの文字コードを続出して比較する。
ここで−敗するため、プロセッサ１７は未知文字列の先
頭文字と二番目の文字が一敗したことから、この文字列
テーブル２１３の文字列ＮＤの二番目の文字であるＤの
文字コードを読出し、未知文字列の三番目の文字りの文
字コードと比較する。
頭文字と二番目の文字が一敗したことから、この文字列
テーブル２１３の文字列ＮＤの二番目の文字であるＤの
文字コードを読出し、未知文字列の三番目の文字りの文
字コードと比較する。
当然−敗となるため、プロセッサ１７は未知文字列はＥ
ＮＤであることを認識する。
ＮＤであることを認識する。
若し、未知文字列がＥＮＤで無く、ＥＮＱであるとする
と、不一致となるため、プロセッサ１７は次の文字列Ｏ
ＰのＯの文字コードと未知文字列の二番目の文字Ｎの文
字コードを比較する。
と、不一致となるため、プロセッサ１７は次の文字列Ｏ
ＰのＯの文字コードと未知文字列の二番目の文字Ｎの文
字コードを比較する。
この場合不一致となるが、先頭文字順ポインタテーブル
２０２は、ここまでしか比較範囲を指示しないため、プ
ロセ、す１７は未知文字列の検索が成功しなかったと判
定する。
２０２は、ここまでしか比較範囲を指示しないため、プ
ロセ、す１７は未知文字列の検索が成功しなかったと判
定する。
上記の如く動作するため、プロセッサ１７は文 。
字列テーブル２１３０文字列ＤＤからＧｌまでの文字列
の比較と、ＯＲ以降の文字列の比較をする必要が無く、
プロセッサ１７は処理時間を短縮することが出来る。
の比較と、ＯＲ以降の文字列の比較をする必要が無く、
プロセッサ１７は処理時間を短縮することが出来る。
未知文字列が２文字の場合、プロセッサ１７は先頭文字
順ポインタテーブル２０１を参照し、文字列テーブル２
１２から比較すべき文字コードを読出す。
順ポインタテーブル２０１を参照し、文字列テーブル２
１２から比較すべき文字コードを読出す。
以上説明した如く、本発明は先頭文字順ポインタテ−プ
ルが指示する範囲内の文字列テーブルの文字列から、未
知文字列の二番目以降の文字の比較を行えば良いため、
文字の比較回数を減らすことが可能となり、プロセッサ
の処理時間を短縮することが出来る。
ルが指示する範囲内の文字列テーブルの文字列から、未
知文字列の二番目以降の文字の比較を行えば良いため、
文字の比較回数を減らすことが可能となり、プロセッサ
の処理時間を短縮することが出来る。
第１図は本発明の原理ブロック図、
第２図は本発明の一実施例を説明する図、第３図は従来
の技術を説明するブロック図である。 図において、 １１．１９は語長側ポインタテーブル、１２〜１６．２
１は文字列テーブル、 １７はプロセッサ、１８はメモリ、 ２０は先頭文字順ポインタテーブル、 ２２はディスク、 ２３はインタフェース回路である。 本承あ日月のオＦチ１Ｐ−フツロ・ンフＥＪ＃１ 図
の技術を説明するブロック図である。 図において、 １１．１９は語長側ポインタテーブル、１２〜１６．２
１は文字列テーブル、 １７はプロセッサ、１８はメモリ、 ２０は先頭文字順ポインタテーブル、 ２２はディスク、 ２３はインタフェース回路である。 本承あ日月のオＦチ１Ｐ−フツロ・ンフＥＪ＃１ 図
Claims (1)
- 【特許請求の範囲】 プロセッサ（１７）により制御され、メモリ（１８）に
格納された未知文字列を認識する計算機において、未知
文字列を認識するための比較対象となる文字列の先頭文
字を除き、文字数に応じて所定の順序でまとめた文字列
テーブル（２１）と、 該文字列テーブル（２１）から除かれた先頭文字に対応
して、該文字列テーブル（２１）の検索範囲内の文字列
を指示する先頭文字順ポインタテーブル（２０）と、 該先頭文字順ポインタテーブル（２０）を未知文字列の
文字数に応じて指示する語長別ポインタテーブル（１９
）とを設け、 未知文字列の先頭の文字を一文字の文字列テーブルから
索引した後、前記語長別ポインタテーブル（１９）が指
示する前記先頭文字順ポインタテーブル（２０）を参照
し、未知文字列の先頭文字に対応した前記文字列テーブ
ル（２１）の指定された範囲内の文字列を比較すること
を特徴とする文字列検索方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61302116A JPS63153632A (ja) | 1986-12-17 | 1986-12-17 | 文字列検索方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP61302116A JPS63153632A (ja) | 1986-12-17 | 1986-12-17 | 文字列検索方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPS63153632A true JPS63153632A (ja) | 1988-06-27 |
Family
ID=17905122
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP61302116A Pending JPS63153632A (ja) | 1986-12-17 | 1986-12-17 | 文字列検索方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPS63153632A (ja) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS63204463A (ja) * | 1987-02-20 | 1988-08-24 | Sanyo Electric Co Ltd | 機械翻訳装置 |
| JPH04199466A (ja) * | 1990-11-29 | 1992-07-20 | Matsushita Electric Ind Co Ltd | 電子化辞書検索装置 |
| JP2013003644A (ja) * | 2011-06-13 | 2013-01-07 | Nippon Telegr & Teleph Corp <Ntt> | 一致判定装置、方法、およびプログラム |
-
1986
- 1986-12-17 JP JP61302116A patent/JPS63153632A/ja active Pending
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS63204463A (ja) * | 1987-02-20 | 1988-08-24 | Sanyo Electric Co Ltd | 機械翻訳装置 |
| JPH04199466A (ja) * | 1990-11-29 | 1992-07-20 | Matsushita Electric Ind Co Ltd | 電子化辞書検索装置 |
| JP2013003644A (ja) * | 2011-06-13 | 2013-01-07 | Nippon Telegr & Teleph Corp <Ntt> | 一致判定装置、方法、およびプログラム |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPS63153632A (ja) | 文字列検索方式 | |
| JPH0395672A (ja) | 文字列検索方法及び装置 | |
| KR100284777B1 (ko) | 지도 용어 사전을 위한 트라이 사전과 그 등록 및 검색 방법 | |
| JPH0227423A (ja) | 日本語文字データの並び換え方法 | |
| JP3722231B2 (ja) | コンパクトにエンコードされて記憶されたストリングの組を有する製品 | |
| JPS63253431A (ja) | インバ−テツド構造のデ−タベ−ス検索方式 | |
| SU342185A1 (ru) | УСТРОЙСТВО дл ПОИСКА ИНФОРМАЦИИ | |
| JPS6361345A (ja) | 外部記憶装置の制御装置 | |
| JPS63138479A (ja) | 文字認識装置 | |
| JPS6373422A (ja) | 情報検索装置 | |
| JPH07101382B2 (ja) | マ−ジ処理装置 | |
| JPS63187334A (ja) | 文字列パタ−ンマツチング装置 | |
| JPS63142423A (ja) | 文字列テ−ブル検索方式 | |
| JP2839515B2 (ja) | 文字読取システム | |
| JPH03127254A (ja) | 単語検索装置 | |
| JPS63103393A (ja) | 単語認識装置 | |
| JPH0268663A (ja) | 文字列検索装置 | |
| JPS59188783A (ja) | 文字判定処理方式 | |
| JPH07121665A (ja) | 文字認識辞書の構成方法及び検索方法 | |
| JPS62285189A (ja) | 文字認識後処理方式 | |
| JPS61278933A (ja) | デ−タのソ−ト方式 | |
| JPH0343832A (ja) | ラベル検索方式 | |
| JPH03282885A (ja) | 学習機能付テーブル検索装置 | |
| JP2000293635A (ja) | 文字認識装置及び方法並びに文字認識プログラム記録媒体 | |
| JPH04245375A (ja) | 記号列照合装置の制御方式 |