JPH1139344A - ２次元配列コードを用いた文字列検索方法 - Google Patents

Abstract

(57)【要約】 （修正有） 【課題】複数指定がある場合でも比較回数を減らし、検
索性能を高速化する文字検索方法を提供する。 【解決手段】条件種別を行方向と、文字種別を列方向の
添え字とする２次元配列を備え、列方向添字の先頭に
は、対応する条件文字種別コードが格納され、複数指定
の場合、列方向の添え字の次の要素に、順次、文字種別
の該当フラグによりコード化し、比較対象文字について
該比較対象文字種別の該当フラグによりコード値を前記
２次元配列の前記文字種別に対応する添字に格納された
コードと比較することにより、文字の検索を行う。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、文字列検索方法に
関し、特に、コンピュータを用いた文字列検索方法に関
する。

【０００２】

【従来の技術】ファイルに格納されている複数の文字列
データと条件文字列を比較する文字検索方法として、比
較対象文字列の先頭１文字と条件文字列の先頭１文字と
を比較し、合致した場合には、以降それぞれの文字列の
次の文字同士の比較を順次行い、条件文字列全体と一致
するか否かを判断する。条件文字列中の文字としては、
通常の文字のほかに、特殊な文字として、任意の１文字
を表すもの、任意の文字（または文字列）を表すもの、
さらに該当する文字の羅列や範囲を指定して複数の文字
を表すもの（この指定の仕方を「複数指定」という）な
どがある。

【０００３】この中で、複数指定による比較を行うため
には、その指定によって条件に該当する全ての文字
（「該当文字群」という）の情報を保持し、比較対象の
文字と個々に比較する必要がある。

【０００４】従来の文字検索方式について図１０を参照
して以下に説明する。従来の方式では、条件文字列１０
１に対してコード化処理１０２を行い、条件文字コード
１０３のように、該当文字群の情報を１文字ごとに配列
の１要素に格納しているため、比較対象文字列１０５と
の比較処理１０４では比較回数が増えてしまう。

【０００５】

【発明が解決しようとする課題】以上説明したように、
上記従来の文字検索方法は下記記載の問題点を有してい
る。

【０００６】第１の問題点は、複数指定をした際の性能
が著しく低下する、ということである。

【０００７】その理由は、複数指定部分での比較回数
は、指定該当文字数をｎとすると、比較対象となる文字
列データごとに、比較対象文字が該当文字列にない場合
には、ｎ回、該当文字列にある場合でも、平均して、
（（１＋ｎ）／２）回になり、比較回数は、該当文字数
や、特に文字列データが増えるにしたがって増大するか
らである。

【０００８】第２の問題点は、複数指定時の該当文字群
の情報を格納するために必要な個々の文字を保持する配
列の大きさ（要素の個数）を決めるための適当な方法が
ない、ということである。

【０００９】その理由は、上述の考え方では、複数指定
部分での該当文字群の情報を格納する配列の大ささは、
（条件文字数×許される文字数）個であるが、通常、複
数指定は、条件文字列中、せいぜい１〜２文字程度であ
り、また該当文字数も、平均すれば、使用可能な文字数
全体に比べ、かなりの割合であることが考えられるた
め、ほとんどが無駄な配列となる、可能性がある。

【００１０】しかし、この大きさよりも小さい配列を用
意すると、指定によっては、用意した配列の大きさ以上
の大きさが必要となり、いわゆる配列外参照を起こして
しまう可能性がある。

【００１１】したがって、本発明は、複数指定がある場
合でも比較回数を減らし、検索性能を高速化する文字検
索方法を提供することにある。

【００１２】また、本発明は、複数指定による該当文字
の情報を格納するために必要な配列の大きさについて、
さほど無駄にならず、かつ、一意に決まるようにする文
字検索方法を提供することにある。

【００１３】

【課題を解決するための手段】前記目的を達成するた
め、本発明は、その概要を述べれば、条件文字列を２次
元配列を用いてコード化するものである。本発明の文字
検索方法は、条件指定による文字列の検索において、条
件文字を文字種別と、該文字種別内該当文字フラグを表
す２次元の配列を用いてコード化し、前記コードと複数
指定条件文字を含む比較対象文字とを比較することを特
徴とする。

【００１４】また、本発明は、条件種別を行方向と、文
字種別を列方向の添え字とする２次元配列を備え、列方
向添字の先頭には、対応する条件文字種別コードが格納
され、複数指定の場合、列方向の添え字の次の要素に、
順次、文字種別の該当フラグによりコード化し、比較対
象文字について該比較対象文字種別の該当フラグにより
コード値を前記２次元配列の前記文字種別に対応する添
字に格納されたコードと比較することにより、文字の検
索を行うことを特徴とする。

【００１５】本発明においては、条件コードは、条件文
字ごとに文字種別ごとの該当文字フラグの情報を格納す
る配列と、これらの配列を条件文字すべてについて管理
する配列からなっている。

【００１６】

【発明の実施の形態】次に、本発明の実施の形態につい
て図面を参照して説明する。

【００１７】図１は、本発明の実施の形態を説明するた
めの図であり、文字列データ４の中から与えられた条件
文字１を満たす文字列を検索し、一致データファイル６
に格納するシステムである。このシステムでの比較処理
５にあたっては、条件文字１をコード処理（図１の２）
により得た条件文字コード３を使って比較を行ってい
る。

【００１８】次に、本発明の実施の形態における条件文
字コード３の詳細について、図２を参照して説明する。

【００１９】コード化にあたっては、与えられた条件文
字列１を条件文字ごとに分け、配列の１次元目の格納番
号（「１次の添字」という）を与える。さらに、その文
字を条件種別にわけ、２次元目の格納番号（「２次の添
字」という）の先頭に種別番号を代入し、特に、複数指
定であった場合には、文字種別ごとに、該当データ群を
フラグとして、対応する２次の添字の要素に対応させて
格納し（図２の７）、条件文字コードコード３とする。

【００２０】図３は、本発明の実施の形態の動作を説明
するためのフローチャートである。本発明の実施の形態
の動作について、図３を参照して説明する。

【００２１】ある与えられた条件文字列について、その
文字列を分類処理し（ステップＳｌｌ）、文字列全体が
一意指定か前方一致であるかを判定する（ステップＳ１
２）。一意指定または前方一致の場合、処理が増えるた
め、標準関数等を用いて、比較する（ステップＳ１
４）。

【００２２】上記以外の場合には（ステップＳ１２のＮ
ｏ分岐）、構成する条件文字ごとに条件種別にわけ、複
数指定であった場合には文字種別ごとに該当データ群を
フラグ化し、各配列の要素に格納する（ステップＳ１
３）。

【００２３】次に、文字列データファイル４より比較対
象文字を取得し（ステップＳ１５）、文字列データが終
了しているか否かの判断を行う（ステップＳ１６）。

【００２４】文字列データが終了していなければ、文字
ごとの比較処理を行い（ステップＳ１７）、最終一致判
定処理を行い（ステップＳ１８）、文字列が一致するか
どうかを判定し（ステップＳ１９）、一致していれば、
一致文字列データを書き込んで（ステップＳ２０）、次
の文字列データを読み込む（ステップＳ１５）。ステッ
プＳ１５〜Ｓ２０の処理は、文字データファイル内のす
べての文字列データについて行われる。

【００２５】図４は、図３のステップＳ１７の文字ごと
の比較処理の処理フローを示すフローチャートである。
図４を参照して、比較対象文字列との比較処理について
説明する。

【００２６】比較対象文字列との比較おいては、対応す
る条件文字コードの２次の添え字について先頭の要素を
基に、複数指定文字かどうかを判断し（ステップＳ４
２）、複数指定文字以外の場合には、処理が増えるた
め、従来の条件種別に応じた比較処理を行う（ステップ
Ｓ４４）。

【００２７】一方、複数指定の場合には、比較文字デー
タの（ｉ＋１）文字目について文字種別を判断し、該当
する文字種別についてのみコード化する（ステップＳ４
３）。

【００２８】次に、上記比較対象文字コードと対応する
条件文字コードの文字種別の要素（フラグ）で論理積を
とることにより比較を行う（ステップＳ４５）。

【００２９】上記処理の比較結果からの文字が一致する
かどうかを判断する（ステップＳ４６）。具体的には、
ステップＳ４５での結果が０以外の場合には一致、０の
場合には不一致となる。

【００３０】比較の結果一致しない場合には、次の文字
列データを読み込む（図１のステップＳ１５）。

【００３１】一致する場合には、比較対象を次の条件文
字、比較対象文字に移すためにカウンタ（ｉ）を増やす
（ステップＳ４７）。ここで、比較文字列が終了してい
た場合には最終一致判定処理へ移る（図１のステップＳ
１８）。

【００３２】終了していない場合には、ステップＳ４２
からＳ４８までの処理を繰り返す。なお、上記各ステッ
プの処理は、コンピュータ上で実行されるプログラム制
御により実現することができる。

【００３３】

【実施例】次に、本発明の一実施例について説明する。
使用する文字は以下のものとし、それぞれ以下のような
文字種別とする。

【００３４】 ．（ピリオド） …文字種別１。

【００３５】 ０〜９ …文字種別２。

【００３６】 Ａ〜Ｚ …文字種別３。

【００３７】また、条件文字の指定方法として以下の４
種類があるものとし、それぞれ以下のような条件種別番
号に対応するものとする。

【００３８】 ・一意指定（条件種別０） …使用可能な文字の中
から１文字を指定する。

【００３９】 ・任意１文字指定（条件種別１）…使用可能な文字の中
の任意の１文字を表す。

【００４０】 ・任意文字指定（条件種別２） …使用可能な文字また
は文字列を表す。

【００４１】 ・複数指定（条件種別３） …複数個の使用可能な
文字を指定するもの（文字の羅列や範囲指定などがあ
る）。

【００４２】複数指定の例について簡単に説明する。

【００４３】 ［ＡＢＣ］→Ａ，Ｂ，Ｃのいずれかを表す。

【００４４】 ［Ｄ−Ｆ］→Ｄ，Ｅ，Ｆのいずれかを表す。

【００４５】 ［ＡＣ−Ｅ］→Ａ，Ｃ，Ｄ，Ｅのいずれかを表す。

【００４６】また、文字種別間の範囲指定についても文
字種別の１から３の順に連続しているものとして指定が
可能であるものとする。

【００４７】実際の条件文字の例として、条件文字列Ａ
？＊［５−ＣＸ］について考える。

【００４８】これは、先頭の文字がＡで、最後の文字
が、５，６，７，８，９，Ａ，Ｂ，Ｃ，Ｘである３文字
以上の文字列であることを表す。

【００４９】この場合の条件種別は、４種類、条件文字
数は４文字であるので、文字コードは５×５の行列とな
る。

【００５０】次に、本発明の一実施例の動作について、
図５を参照して詳細に説明する。

【００５１】条件文字列５１をコード化した際の条件コ
ードの配列の値は、条件コード５２のように、２次の添
え字の先頭には、対応する条件文字種別コードが入り、
複数指定（Ｄ［ｎ］［０］＝３）の場合、その１次の添
え字の次の要素（Ｄ［ｎ］［１］，Ｄ［ｎ］［２］，
…）に、順次、文字種別の該当フラグを格納する。な
お、条件コード５２の他の要素のデータは、条件文字列
５１に対しては使用しないが、Ｄ［０］［０］＝０は条
件種別０、Ｄ［１］［０］＝１は条件種別１、Ｄ［２］
［０］＝２は条件種別２を示している。

【００５２】次に、条件文字列５２中の複数条件文字
［５−ＣＸ］のコード化について、図６を参照して説明
する。

【００５３】複数条件文字のコード化では、対応する該
当文字について条件文字種別ごとの番号を付け、その番
号に対応する要素に文字があるかないかを０と１で表
す。以下各文字種別ごとに説明する。

【００５４】条件文字［５−ＣＸ］中には、文字種別１
であるピリオドは含まれていない。そこで、Ｄ［３］
［１］に０を格納する（図６の６１）。

【００５５】また、文字種別２の中では５から９が該当
するため、それらに該当する部分のフラグを１にし、こ
れを０から９まで順に並べたもの（図６の６２）を２進
数と見なし、Ｄ［３］［２］に格納する。なお、以降こ
の２進数を１０進化して説明する。

【００５６】同様に、文字種別３についても同様の処理
を行い（図６の６３）、データをＤ［３］［３］に格納
する。

【００５７】次に実際の比較について、図７を参照して
詳細に説明する。なお、複数条件文字以外の比較処理に
ついては従来の処理で行うため、説明は複数条件文字と
の比較部分に絞って説明する（図４のステップＳ４３と
ステップＳ４５）。

【００５８】具体例の１として、上記条件文字［５−Ｃ
Ｘ］、比較の対象となる文字の例として”６”を考え
る。まず”６”の文字種別は２であり、”６”について
条件文字と同様の方法でコード化を行い、６４を得る
（図７の７１）。

【００５９】次に、このコードと条件文字コード７２内
の対応するコード（Ｄ［３］［２］）との論理積をと
る。その結果として６４となり、論理積が０でないこと
から一致するという結果を得る。

【００６０】また、同じ複数条件文字に対して”Ｅ”と
の比較を行うと”Ｅ”の文字種別と順番から（図７の７
３）のようになり、条件文字コード７２中の対応コード
（Ｄ［３］［３］）との論理積の結果である０、すなわ
ち不一致という結果を得る。

【００６１】次に、従来のコードとの違いについて図１
１を参照して詳細に説明する。

【００６２】図１１（Ａ）の条件文字列５１を、従来の
コードを使って表現すると、図１１（Ｂ）の１１１のよ
うになる。ここで、１次の添え字３と１３の括
弧（［，］）は複数条件の該当文字データの開始と終了
を表すものとする。

【００６３】配列の大きさでは、従来のコードは、１
４、本実施例によるコードでは２５と従来のコードの方
が少ないが、文字列データあたりの複数条件部分での比
較回数については、従来の９回（＝該当文字数）に比
べ、本実施例によるコードでは１回と少ない。

【００６４】さらに、図１２に示すよう、に条件文字列
としてＡ？−＊［５−Ｘ］を考えると、従来の条件コー
ドでは３６となり、本実施例によるコードの２５よりも
多くなる。また、文字列データあたりの複数指定部分の
比較回数は、従来のコードでの３１回に比べて１回とか
なり少ない。このように、本実施例によるコードでは条
件文字数が同じであればどのような指定をしても配列の
要素数は変わらず、また、複数指定部分の比較は常に１
回になる。

【００６５】なお、従来のコードにおいて使用する要素
数は条件文字列によって変わるものの、配列外参照が起
こらないようにするために必要な配列の要素数は、条件
文字を４文字とした場合には、４×｛（文字種別１の文
字数）＋（文字種別２の文字数）＋（文字種別３の文字
数）｝＝４×（１＋１０＋２６）＝１４８となる。

【００６６】本発明の別の実施の形態について図８を参
照して説明する。入力ファイル８１を記憶装置８３に格
納する際に、予めデータ内のキーワードを基に、上位索
引ファイル８７からデータ種別を分類し、そのキーワー
ドとデータファイル８７へのポインタに関するデータを
データ種別ごとに格納する索引ファイル８９で構成され
るシステムでの検索方式がある。

【００６７】従来は、指定したキーワードの数だけリス
トデータの検索を行っていたが、本発明の実施の形態で
は、上位索引ファイル８３内に、データ種別ごとに属す
るキーワードに番号を付けそれらを管理することで（図
９の９１）、検索の際に、検索データ８４を上位索引フ
ァイル８３の情報を基に、データ種別ごとにフラグ化す
る。なお、図９において、上位検索ファイル９１とデー
タ種別１との対応を９２で示す。データ種別ごとの索引
ファイルとの比較においては、ファイル内の各データを
同様にフラグ化して入力条件コードの該当データ種別と
の論理積をとりその値で一致するかどうかで判断でき
る。

【００６８】

【発明の効果】以上説明したように、本発明によれば下
記記載の効果を奏する。

【００６９】本発明の第１の効果は、従来方式で問題点
とされていた複数指定を使った際の検索性能の低下を解
消し、検索性能を高速化する、ということである。

【００７０】その理由は、本発明においては、コード化
は複数条件文字部分のデータ化を検索処理の先頭で行う
ため、比較回数が文字列データごとに１回となる、ため
である。

【００７１】本発明の第２の効果は、該当文字群の情報
を格納する配列についての無駄や配列外参照の発生の可
能性を回避することができる、ということである。

【００７２】その理由は、本発明においては、該当文字
群の情報を格納するために必要な配列の大きさを使用可
能文字数から文字種別数にすることで、各条件文字コー
ドごとに全情報を持たせても、さほど大きくならないか
らである。

【図面の簡単な説明】

【図１】本発明の実施の形態を説明するための図であ
る。

【図２】本発明の実施の形態における２次元コードを説
明するための図である。

【図３】本発明の実施の形態の処理フローを示すフロー
チャートである。

【図４】本発明の実施の形態における文字ごとの比較の
処理フローを示すフローチャートである。

【図５】本発明の一実施例を説明するための図であり、
条件文字全体のコードの例を示す図である。

【図６】本発明の一実施例を説明するための図であり、
複数指定文字部分についてのコードの例を示す図であ
る。

【図７】本発明の一実施例を説明するための図であり、
複数指定文字と比較対象文字との比較方法についての例
を示す図である

【図８】本発明の別の実施の形態の構成を示す図であ
る。

【図９】本発明の別の実施の形態のコード化の適用例を
示す図である。

【図１０】従来の文字検索方式を説明するための図であ
る。

【図１１】従来のコードによる条件文字列５１のコード
である。

【図１２】条件文字列の他の例での従来と本実施例のコ
ードである。

【符号の説明】

１ 条件文字列 ２ コード化処理 ３ 条件文字コード ４ 文字列データ ５ 条件文字列との比較処理 ６ 一致文字列データ ７ 条件文字ごとの情報 ５１ 条件文字列の例 ５２ 条件文字列５１に対応する条件コード ６１ 条件文字列５１の文字種別１に関するコード表 ６２ 条件文字列５１の文字種別２に関するコード表 ６３ 条件文字列５１の文字種別３に関するコード表 ７１ 比較対象文字”６”の文字種別２に関するコード
表 ７２ 条件文字列５１の条件コード中の複数指定データ
部 ７３ 比較対象文字”Ｅ”の文字種別３に関するコード
表 ８１ 入力ファイル ８２ 入力装置 ８３ 記憶装置 ８４ 検索データ ８５ 検索装置 ８６ 一致データ格納ファイル ８７ データファイル ８８ 上位検索ファイル ８９ データ種別ごとの検索ファイル ９１ 上位検索ファイル８８の一例 ９２ データ種別１に関するコード表の例 １０１ 従来のコードによる条件文字列５１のコード １１１ 条件文字列の例 １１２ 従来のコードによる条件文字列１１１のコード １１３ 本発明のコードによる条件文字列１１１のコー
ド

Claims (3)

【特許請求の範囲】
1. 【請求項１】条件指定による文字列の検索において、 条件文字を文字種別と、該文字種別内該当文字フラグを
   表す２次元の配列を用いてコード化し、 前記コードと複数指定条件文字を含む比較対象文字とを
   比較することを特徴とする文字列検索方法。
2. 【請求項２】条件種別を行方向と、文字種別を列方向の
   添え字とする２次元配列を備え、 列方向添字の先頭には、対応する条件文字種別コードが
   格納され、 複数指定の場合、列方向の添え字の次の要素に、順次、
   文字種別の該当フラグによりコード化し、 比較対象文字について該比較対象文字種別の該当フラグ
   によりコード値を前記２次元配列の前記文字種別に対応
   する添字に格納されたコードと比較することにより、文
   字の検索を行うことを特徴とする文字列検索方法。
3. 【請求項３】条件種別を行方向、文字種別を列方向の添
   え字とする２次元配列の列方向添字の先頭には、対応す
   る条件文字種別コードが格納され、複数指定の場合、列
   方向の添え字の次の要素に、順次、文字種別の該当フラ
   グによりコード化してなる前記２次元配列を参照して、
   比較対象文字について該比較対象文字種別の該当フラグ
   によりコード値を前記２次元配列の前記文字種別に対応
   する添字に格納されたコードと比較することにより、文
   字の検索を行う、処理をコンピュータ上で行うプログラ
   ムを記録した記録媒体。