(57)【要約】【課題】複数の数値の中からひとつが選択されることを意味するメタ文字表現を含んだデータを抽出することができるデータ処理装置を提供する。【解決手段】データ処理装置１００は、メタ文字表現を含んだ文字列のうち、メタ文字表現以外の数値をメタ文字表現とし、メタ文字表現ごとに一単位文字として扱うとともに、ひとつの数値および該数値以外の文字を一単位文字として分割し、分割された単位文字の数を単位文字数として算出する単位文字分割部２１と、単位文字数ごとのＶＰ木を作成するＶＰ木作成部６０と、単位文字数が所定範囲に該当するＶＰ木を、候補データとして抽出するＶＰ木抽出部３２と、対象データとデータベースのデータとの間の距離を算出する距離算出部３３と、ＶＰ木抽出部で抽出された候補データのうち、算出された距離が所定値以下のデータを、候補データとして抽出する候補データ抽出部３４と、を有する。【選択図】図１
2015079380.tif 000002
【特許請求の範囲】
【請求項１】
入力された対象データに類似する候補データをデータベースから抽出するデータ処理装置であって、
前記データベースには、複数の数値の中からひとつの数値が選択されることを意味するメタ文字表現を含むデータおよびメタ文字表現を含まないデータが格納されており、
前記対象データに類似する候補データの抽出先がメタ文字表現を含むデータの場合、前記メタ文字表現を含んだ文字列のうち、メタ文字表現以外の数値をメタ文字表現とし、メタ文字表現ごとに一単位文字として扱うとともに、前記対象データおよび前記データベースのデータに含まれる、ひとつの数値および該数値以外の文字を一単位文字として分割し、前記対象データに類似する候補データの抽出先がメタ文字表現を含まないデータの場合、前記対象データおよび前記データベースのデータに含まれる文字列の文字ごとに一単位文字として分割し、前記分割された単位文字の数を単位文字数として算出する単位文字分割部と、
前記データベースのデータからメタ文字表現を含むデータと、メタ文字表現を含まないデータとに分類し、前記分類されてデータに基づく前記単位文字数ごとの２分探索木を作成する２分探索木作成部と、
前記対象データの単位文字数に基づき所定範囲に該当する２分探索木を、前記候補データとして抽出する２分探索木抽出部と、
前記対象データと前記データベースのデータとの間の距離を算出する距離算出部と、
前記２分探索木抽出部で抽出された候補データのうち、前記算出された距離が所定値以下のデータを、前記候補データとして抽出する候補データ抽出部と、を有する
ことを特徴とするデータ処理装置。
【請求項２】
前記候補データ抽出部は、前記メタ文字表現を含む２分探索木の場合、
前記対象データと前記候補データとの距離Ｄ、前記２分探索木の距離の中間値Ｍ、前記対象データと前記２分探索木のルートノードとの距離ｄとすると、
ｄ≦Ｍ−Ｄ
の条件を満たす場合であっても、前記２分探索木の検索をする
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項３】
前記候補データ抽出部は、前記対象データと前記候補データとの距離Ｄ、前記２分探索木の距離の中間値Ｍ、前記対象データと前記２分探索木のルートノードとの距離ｄとすると、
Ｄ＋Ｍ＜ｄ
の条件を満たすとき、前記２分探索木の検索をしない
ことを特徴とする請求項１に記載のデータ処理装置。
【請求項４】
データ処理装置は、データベースと、処理部とを有し、
前記データベースには、複数の数値の中からひとつの数値が選択されることを意味するメタ文字表現を含むデータが格納されており、
前記処理部は、
入力された対象データが前記データベースに格納されているか否かを検索し、前記対象データが前記データベースに格納されていなかった場合に、
前記メタ文字表現を含んだ文字列のうち、メタ文字表現以外の数値をメタ文字表現とし、メタ文字表現ごとに一単位文字として扱うとともに、前記対象データおよび前記データベースのデータに含まれる、ひとつの数値および該数値以外の文字を一単位文字として分割し、前記分割された単位文字の数を単位文字数として算出する処理と、
前記データベースのデータから前記単位文字数ごとの２分探索木を作成する処理と、
前記単位文字数が所定範囲に該当する２分探索木を、前記候補データとして抽出する処理と、
前記対象データと前記データベースのデータとの間の距離を算出する処理と、
前記抽出された候補データのうち、前記算出された距離が所定値以下のデータを、前記候補データとして抽出する処理と、を含んで実行する
ことを特徴とするデータ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置に関し、特に複数の数値の中からひとつの数値が選択されることを意味するメタ文字表現を含んだデータを抽出する技術に関する。
【背景技術】
【０００２】
一般に、顧客が商品カタログを参照して、商品を発注する際に商品の型番で発注することが多い。発注を受けた受注サーバは、注文で誤入力（例えば、カタログにない商品が指定されること）があった場合、文字列類似度を用いた検索でカタログのデータベースから正しい商品名の候補を抽出することができる（例えば、特許文献１参照）。
【０００３】
産業部品の商品カタログにおいては、商品の型番の一部が加工仕様を表しているものがあり、加工可能な条件の幅に合わせて商品の型番の一部が「加工仕様の幅が表記されておりその範囲で加工条件をひとつの数値が選択される」という「メタ文字表現」で表されているものがある。
【０００４】
「メタ文字表現」を持つ商品の型番の例として、Ａ｛１，１．５，２，２．５，３｝Ｂとあれば、｛１，１．５，２，２．５，３｝は５つの数値１、１．５、２、２．５、３の中からひとつの数値が選択されることを意味する。顧客は発注の際に、例えばＡ１．５Ｂと入力する。
【０００５】
また、他の「メタ文字表現」を持つ商品の型番の例として、Ａ｛１．．３（０．５）｝Ｂとあれば、｛１．．３（０．５）｝は１から３まで０．５刻みの数値の中から一つを選ぶことを意味する。この場合は｛１．．３（０．５）｝は、｛１，１．５，２，２．５，３｝と同じ意味となる。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】国際公開ＷＯ２００７／１３２５６４号
【発明の概要】
【発明が解決しようとする課題】
【０００７】
一般に、文字列の類似度の算出は、単一商品を表す文字列に対して行なうものである。このため、データベースにメタ文字表現を含んでいるデータがある場合、メタ文字表現で表された文字列に対しては類似度算出が非常に困難である。
【０００８】
したがって、メタ文字表現を持つ商品の型番に対して文字列類似度を計算する場合、メタ文字表現を持つ商品の型番を単一の商品を表す文字列に分解して計算しなければならなかった。すなわち、「メタ文字表現」を持つ商品の型番がＡ｛１．．３（０．５）｝Ｂの場合、Ａ１Ｂ、Ａ１．５Ｂ、Ａ２Ｂ、Ａ２．５Ｂ、Ａ３Ｂと分解する必要がでてくる。
【０００９】
しかしながら、メタ文字表現を持つ商品の型番を単一の商品の型番の文字列に分解すると、商品点数が爆発的に増加するため、計算資源や計算時間の観点からこの分解は現実的ではなかった。
【００１０】
また、類似の文字列を検索する場合に、ＶＰ（Vantage-Point）木などの距離をインデックスとする２分探索木を用いると、全件検索よりも高速に検索できる場合がある。しかしながら、メタ文字表現を有する文字列で、ＶＰ木が使用できるか否かはいまだ検討されていないのが実情である。
【００１１】
本発明は、前記した課題を解決するためになされたものであり、複数の数値の中からひとつの数値が選択されることを意味するメタ文字表現を含んだデータを抽出することができるデータ処理装置およびデータ処理方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
前記目的を達成するため、本発明のデータ処理装置は、入力された対象データに類似する候補データをデータベースから抽出するデータ処理装置であって、データベースには、複数の数値の中からひとつの数値が選択されることを意味するメタ文字表現を含むデータおよびメタ文字表現を含まないデータが格納されており、対象データに類似する候補データの抽出先がメタ文字表現を含むデータの場合（例えば、図４のメタ文字表現を含むデータ７４Ｂ）、メタ文字表現を含んだ文字列のうち、メタ文字表現以外の数値をメタ文字表現とし（すなわち、選択肢がひとつの数値選択表現とし）、メタ文字表現ごとに一単位文字として扱うとともに、対象データおよびデータベースのデータに含まれる、ひとつの数値および該数値以外の文字を一単位文字として分割し、対象データに類似する候補データの抽出先がメタ文字表現を含まないデータの場合（例えば、図４のメタ文字表現を含むデータ７４Ａの場合）、対象データおよびデータベースのデータに含まれる文字列の文字ごとに一単位文字として分割し、分割された単位文字の数を単位文字数として算出する単位文字分割部と、データベースのデータからメタ文字表現を含むデータと、メタ文字表現を含まないデータとに分類し、分類されてデータに基づく単位文字数ごとの２分探索木（例えば、ＶＰ木）を作成する２分探索木作成部（例えば、ＶＰ木作成部６０）と、対象データの単位文字数に基づき所定範囲に該当する２分探索木を、候補データとして抽出する２分探索木抽出部（例えば、ＶＰ木抽出部３２）と、対象データとデータベースのデータとの間の距離を算出する距離算出部と、２分探索木抽出部で抽出された候補データのうち、算出された距離が所定値以下のデータを、候補データとして抽出する候補データ抽出部と、を有することを特徴とする。
【発明の効果】
【００１３】
本発明によれば、複数の数値の中からひとつの数値が選択されることを意味するメタ文字表現を含んだデータを抽出することができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施形態に係るデータ処理装置を示す図である。
【図２】カタログ型番ＤＢの一例を示す図である。
【図３】誤入力修正履歴ＤＢの一例を示す図である。
【図４】単位文字数順カタログ型番ＤＢの一例を示す図である。
【図５】入力判定処理を示すフローチャートである。
【図６】入力判定処理の一例を示す図である。
【図７】ＶＰ木の作成例を示す図である。
【図８】ＶＰ木の編集距離の中間値を示す図である。
【図９】文字列ｑ、ｐ、ｌの編集距離の関係を示す図である。
【図１０】文字列ｑ、ｐ、ｒの編集距離の関係を示す図である。
【図１１】左側の枝刈り条件が成立する場合における枝刈りができない例を示す図である。
【図１２】右側の枝刈り条件が成立する場合における枝刈りができない例を示す図である。
【図１３】誤入力処理を示すフローチャートである。
【図１４】ＶＰ木の抽出例を示す図である。
【図１５】ＶＰ木検索処理を示すフローチャートである。
【図１６】ＶＰ木の検索例を示す図である。
【図１７】クライアントの表示画面の一例を示す図である。
【発明を実施するための形態】
【００１５】
以下、本発明の実施形態について図面を参照して詳細に説明する。
図１は、本発明の実施形態に係るデータ処理装置を示す図である。クライアント２００から入力された商品の型番を認証するためのデータ処理装置１００は、商品カタログのデータベース７０と、入力された対象データがデータベース７０に格納されているか否か検索し、対象データがデータベース７０に格納されていなかった場合に、対象データに類似する候補データをデータベース７０から抽出する処理部１０と、抽出する際に使用される閾値などを入力する入力部８１、処理結果を表示する表示部８２、およびネットワーク３００を介してクライアント２００などと通信を行う通信部８５から構成される。
【００１６】
データベース７０は、ＨＤＤ（Hard disk drive）装置などにより構成される。処理部１０は、ＣＰＵ（Central Processing Unit）によって、ＲＡＭ（Random Access Memory）やＨＤＤ上のプログラムを実行することで実現される。入力部８１は、キーボードやマウスなどのコンピュータに指示を入力するための装置であり、プログラム起動などの指示を入力する。表示部８２は、ディスプレイなどであり、データ処理装置１００による処理の実行状況や実行結果などを表示する。通信部８５は、ネットワーク３００を介して、他のサーバなどと各種データやコマンドを交換する。
【００１７】
データベース７０には、商品カタログの詳細情報である商品名、商品の型番、メーカ名、価格、納期、製品の特徴などの情報であるカタログＤＢ７１、カタログＤＢ７１のうち所定の分類ごとに商品の型番を分類した情報であるカタログ型番ＤＢ７２（図２参照）、誤入力があった際に修正された入力回数の履歴を記録した情報である誤入力修正履歴ＤＢ７３（図３参照）、カタログ型番ＤＢ７２を、単位文字数順に並べ替えた情報である単位文字数順カタログ型番ＤＢ７４（図４参照）、対象データに類似する候補データをデータベース７０から抽出する際に使用する情報（例えば、閾値）である抽出条件情報７５、単位文字数順カタログ型番ＤＢ７４から作成されたカタログ型番ＶＰ木ＤＢ７６（カタログ型番２分探索木ＤＢ）などが格納されている。なお、ＶＰ木は、２分探索木（Binary search tree）のひとつであり、探索木のうちで最も基本的な木構造である。
【００１８】
処理部１０は、入力された対象データがデータベース７０に格納されているか否かを検索する検索部２０（入力判定処理部）と、対象データがデータベース７０に格納されていなかった場合に、対象データに類似する候補データをデータベース７０から抽出する抽出部３０（誤入力処理部）と、抽出された候補データを提示する候補提示部４０と、誤入力修正履歴ＤＢ７３の履歴を更新する履歴更新部５０と、単位文字数別のカタログ型番ＶＰ木ＤＢ７６を作成するＶＰ木作成部６０（２分探索木作成部）の複数のプログラムを有する。
【００１９】
検索部２０は、対象データに類似する候補データの抽出先がメタ文字表現を含むデータの場合、メタ文字表現を含んだ文字列のうち、メタ文字表現以外の数値をメタ文字表現とし（すなわち、選択肢がひとつの数値選択表現とし）、メタ文字表現ごとに一単位文字として扱うとともに、対象データおよびデータベースのデータに含まれる、ひとつの数値および該数値以外の文字を一単位文字として分割し、対象データに類似する候補データの抽出先がメタ文字表現を含まないデータの場合、対象データおよびデータベースのデータに含まれる文字列の文字ごとに一単位文字として分割し、分割された単位文字の数を単位文字数として算出する単位文字分割部２１と、対象データの単位文字と、比較対象データの単位文字とが合致しているか否かを比較する単位文字比較部２２を有している。
【００２０】
抽出部３０は、前記した単位文字分割部２１、単位文字数が所定範囲に該当するＶＰ木を抽出するＶＰ木抽出部３２（２分探索木抽出部）と、対象データと比較対象データとの間の距離を算出する距離算出部３３と、ＶＰ木抽出部３２で抽出された候補データのうち、算出された距離が所定値以下のデータを、候補データとして抽出する候補データ抽出部３４を有している。
【００２１】
本実施形態のデータ処理装置１００は、詳細は後記するが、下記の特徴を有する。
（１）ＶＰ木作成部６０は、データベース７０のデータを、メタ文字表現を含むデータと、メタ文字表現を含まないデータとに分類し、該分類されたデータごとにＶＰ木を作成する。
（２）メタ文字表現を含むデータのＶＰ木構築時は、数値を一単位文字扱いとしてハウスドルフ距離となる編集距離を用いる。この場合に、単位文字分割部２１は、メタ文字表現を含んだ文字列のうち、メタ文字表現以外の数値をメタ文字表現とし（すなわち、選択肢がひとつの数値選択表現とし）一単位文字として扱うとともに、文字列の文字ごとに一単位文字として扱う。
【００２２】
図２は、カタログ型番ＤＢの一例を示す図である。カタログ型番ＤＢ７２には、多数の商品の型番であるデータが登録されている。例えば、メタ文字表現を含まないデータとして、１２３３４５、Ｐ１０−５、・・・があり、メタ文字表現を含むデータとして、Ｃ｛１０，１１｝−Ｄ３、Ｃ｛１，１０｝−Ｂ｛２，３｝、・・・がある。商品の型番には、既に説明したメタ文字表現で記載されているものが多数ある。
【００２３】
具体的に説明すると、商品の型番がＤ５１−Ｍ｛０．１．．１００（０．０１）｝−ＬＳ｛１０，２０，４５，５０，９０｝のデータの場合、メタ文字表現を含んだ文字列のうち、メタ文字表現以外の数値（例えば、５１）をメタ文字表現以外の数値をメタ文字表現とし（すなわち選択肢がひとつの数値選択表現とし）一単位文字として扱うとともに、文字列の文字ごとに一単位文字として扱う。すなわち、前記データの場合、Ｄ｛５１｝−Ｍ｛０．１．．１００（０．０１）｝−ＬＳ｛１０，２０，４５，５０，９０｝となり、文字「Ｄ」、メタ文字表現「｛５１｝」、文字「−」、文字「Ｍ」、メタ文字表現「｛０．１．．１００（０．０１）｝」、文字「−」、文字「Ｌ」、文字「Ｓ」、メタ文字表現「｛１０，２０，４５，５０，９０｝」から構成されており、単位文字数としては、「９」となる。なお、メタ文字表現の部分は、数値１個を表すため、ひとつの単位文字である。
【００２４】
前記のメタ文字表現部分である｛０．１．．１００（０．０１）｝は、０．１から１００まで、０．０１刻みの数値の中からひとつが指定されることを意味する。また、メタ文字表現部分である｛１０，２０，４５，５０，９０｝は、列挙された数値の中からひとつが指定されることを意味する。
【００２５】
図３は、誤入力修正履歴ＤＢの一例を示す図である。誤入力修正履歴ＤＢ７３には、誤入力があった際に修正された入力回数の履歴を記録した修正履歴の情報であり、型番と誤入力回数を含んで構成されている。具体的に説明すると、型番がＣ｛１０，１１｝−３Ｄの場合、誤入力回数は５０回あり、型番がＣ｛１，１０｝−Ｂ｛２，３｝の場合、誤入力回数は１００回あったことがわかる。
【００２６】
図４は、単位文字数順カタログ型番ＤＢの一例を示す図である。単位文字分割部２１は、（図１参照）は、データベースのデータを、メタ文字表現を含まないデータ７４Ａと、メタ文字表現を含むデータ７４Ｂとに分類するとともに、分類されたデータごとに予めカタログ型番ＤＢ７２を単位文字数順に分類している。単位文字数順カタログ型番ＤＢ７４には、単位文字数、単位文字分割後の型番（単位文字ごとにコンマ（，）で区切られている）、元の型番から構成されている。
【００２７】
メタ文字表現を含まないデータ７４Ａの場合、文字列の文字ごとに一単位文字とする。例えば、型番がＰ１０−５の場合、Ｐ，１，０，−，５に分割され、単位文字数は「５」である。また、型番が１２３３４５の場合、１，２，３，３，４，５に分割され単位文字数は「６」である。
【００２８】
メタ文字表現を含むデータ７４Ｂの場合、メタ文字表現を含んだ文字列のうち、メタ文字表現以外の数値をメタ文字表現とし（すなわち、選択肢がひとつの数値選択表現とし）、メタ文字表現ごとに一単位文字として扱うとともに、対象データおよびデータベースのデータに含まれる、ひとつの数値および該数値以外の文字を一単位文字として分割する。例えば、単位文字分割後の型番がＡ，Ｂ，Ｃ，−，Ｌ，｛１．．１０（０．１）｝，−，Ｗ，｛２．．５（０．５）｝，−，Ｈ，｛１，２，３｝の場合、単位文字数は「１２」である。また、単位文字分割後の型番がＣ，｛１０，１１｝，−，Ｄ，３の場合、単位文字数は「５」である。
【００２９】
ここで、図４において、型番がＣ｛１０，１１｝−Ｄ３の場合、単位文字分割後の型番が、Ｃ，｛１０，１１｝，−，Ｄ，｛３｝となり、メタ文字表現を含んだ文字列のうち、メタ文字表現以外の数値「３」がメタ文字表現である「｛３｝」に修正されている。
【００３０】
（入力判定処理）
図５は、入力判定処理を示すフローチャートである。図６は、入力判定処理の一例を示す図である。適宜図１を参照して説明する。入力判定処理Ｓ１１０は、検索部２０がクライアント２００から発注データを受理すると、発注データに含まれる型番を対象データとして、データベース７０に格納されているか否かを検索する処理である。対象データは、例えば、図６（ａ）に示す「Ａ１０−Ｂ２」である。
【００３１】
単位文字分割部２１は、対象データを下記に基づき単位文字に分割する（処理Ｓ１１１）。
（１）検索先がメタ文字表現を含まない場合（例えば、メタ文字表現を含まないデータ７４Ａの場合）：対象データを文字列の文字ごとに一単位文字として分割
（２）検索先がメタ文字表現を含む場合（例えば、メタ文字表現を含むデータ７４Ｂの場合）：対象データの数値は一単位文字として分割
すなわち、図６（ｂ）に示すように、（１）の場合、「Ａ，１，０，−，Ｂ，２」となり、（２）の場合、「Ａ，１０，−，Ｂ，２」となる。
【００３２】
単位文字分割部２１は、該当するカタログ型番ＤＢ７２をメモリに読込み、作業用のリストに格納する（処理Ｓ１１２）。
【００３３】
単位文字比較部２２は、対象データの先頭から単位文字ごとに（処理Ｓ１１３）、処理Ｓ１１４〜処理Ｓ１１６を繰り返す。まず、対象データの単位文字に該当する単位文字がリストにあるか否かを判定し（処理Ｓ１１４）、該当する単位文字がある場合（処理Ｓ１１４，Ｙｅｓ）、リストを絞り込み（処理Ｓ１１５）、次の単位文字へ進む（処理Ｓ１１６）。該当する単位文字がない場合（処理Ｓ１１４，Ｎｏ）、誤入力処理に進む（処理Ｓ１１８）。
【００３４】
図６を参照して具体的に説明すると、１単位文字目で絞り込むと、図６（ｃ）に示すようになる。対象データの「Ａ」に該当するデータが絞り込まれ、例えば、Ａ１０−ＸＹ、Ａ｛１０，１３｝−Ｄ｛２，３｝、ＡＢＣ−Ｌ｛１．．１０（０．１）｝−Ｗ｛２．．５（０．５）｝−Ｈ｛１，２，３｝となる。次に、２単位文字目で絞り込むと、図６（ｄ）に示すようになる。処理Ｓ１１１の（１）の場合、「１」に該当するデータが絞り込まれ、例えば、Ａ１−ＸＹとなる。処理Ｓ１１１の（２）の場合、「１０」に該当するデータが絞り込まれ、例えば、Ａ｛１０，１３｝−Ｄ｛２，３｝となる。なお、メタ文字表現の｛１０，１３｝には、「１０」が含まれている。
【００３５】
さらに、３単位文字目で絞り込むと、図６（ｅ）に示すようになる。処理Ｓ１１１の（１）の場合「０」、処理Ｓ１１１の（２）の場合「−」に該当するデータが絞り込まれるが、図６（ｄ）にくらべて変更のないＡ１０−ＸＹ、Ａ｛１０，１３｝−Ｄ｛２，３｝となる。さらに、４単位文字目で絞り込むと、図６（ｆ）に示すように、Ａ１０−ＸＹとなり、さらに、５単位文字目で絞りこむと、図６（ｇ）に示すように、リストには、該当するデータがない状態になる。図６に示す例の場合、５単位文字目の絞りこみで対象データである「Ａ１０−Ｂ２」が、誤入力と判定される。
【００３６】
一方、対象データである「Ａ１０−Ｂ２」があった場合、型番は正しいので、受注処理に進む（処理Ｓ１１７）。なお、受注処理は、受注処理を担当する受注サーバ（不図示）が担当するが、説明は省略する。
【００３７】
（ＶＰ木作成処理）
本実施形態の基本となる、メタ文字表現を含まないデータのＶＰ木の作成について説明する。図７は、ＶＰ木の作成例を示す図である。図８は、ＶＰ木の編集距離の中間値を示す図である。ＶＰ木は編集距離をインデックスとする２分探索木のひとつである。なお、文字列を、ここではノードと称する。
【００３８】
図７には、７つのノード「ＡＢＣＤＥＦＧ」、「ＡＢＣ４ＥＦＧ」、「ＡＢＣ４５ＦＧ」、「ＡＢ３４５ＦＧ」、「Ａ２３４５６Ｇ」、「Ａ２３４５６７」、「１２３４５６７」からなるＶＰ木の例を示す。図７のＶＰ木は、７つのノードの中から基準型番を「ＡＢＣＤＥＦＧ」として、ＶＰ木が作成されている。
【００３９】
ノード「ＡＢＣＤＥＦＧ」とすべての６つの子ノードの編集距離の中間値Ｍを求めると４であり、左側に編集距離４未満のものを配置し、右側に編集距離４以上のものを配置する。そして、ノード「ＡＢＣ４ＥＦＧ」とその２つの子ノードの編集距離の中間値Ｍを求めると１．５であり、左側に編集距離１．５未満のものを配置し、右側に編集距離１．５以上のものを配置する。さらに、ノード「Ａ２３４５６Ｇ」とその２つの子ノードの編集距離の中間値Ｍを求めると１．５であり、左側に編集距離１．５未満のものを配置し、右側に編集距離１．５以上のものを配置する。図８には、各ノードと編集距離の中間値Ｍとの関係を図示している。なお、データ間の距離を算出する際に、例えば、ハミング距離（信号距離）、レーベンシュタイン距離（編集距離）など、既存の技術を利用可能である。
【００４０】
一般的な編集距離の定義として、
（１）編集距離が０となるのは、２つの文字列が等しいときだけであり、かつそのときに限られる。
（２）対称である。すなわち、２つの文字列ｓ、ｔの編集距離ｄには、
ｄ（ｓ，ｔ）＝ｄ（ｔ，ｓ）が成り立つ。
（３）編集距離の三角不等式が成り立つ。任意の文字列をｕとするとき、
ｄ（ｓ，ｔ）≦ｄ（ｓ，ｕ）＋ｄ（ｕ，ｔ）を満たす。
【００４１】
前記で作成されたＶＰ木の子ノードを持つすべてのノードについて成り立つ。以降、子ノードと述べる際には孫以下のノードも含むものとする。
（ａ）ノードはそのノードの子ノードすべてとの間の編集距離の中間値Ｍを持つ。
（ｂ）ノードとそのノードの左側子ノードとの編集距離は、ノードが持つ中央値Ｍ未満である。
（ｃ）ノードとそのノードの右側子ノードとの編集距離は、ノードが持つ中央値Ｍ以上である。
【００４２】
図９は、文字列ｑ、ｐ、ｌの編集距離の関係を示す図である。今、対象データである検索文字列をｑ、ＶＰ木のあるノードの文字列をｐ、文字列ｐのノードの任意の左側子ノード文字列をｌとする。検索文字列との編集距離がＤ以下の文字列をＶＰ木で検索する場合、Ｄ＋Ｍ＜ｄ（ｑ，ｐ）が成り立てば、そのノードの左側の枝は検索しなくてよい（以降、左側の枝刈りと呼ぶ。）
【００４３】
Ｄ＋Ｍ＜ｄ（ｑ，ｐ）が成り立つとき、文字列ｐのノードの左側のノード文字列で、検索文字列ｑとの間の編集距離がＤ以下になるものは存在しない。図９において、文字列ｐのノードの左側すべての子ノードは文字列ｐのノードから半径Ｍの内側にある。このため、Ｄ＋Ｍ＜ｄ（ｑ，ｐ）が成り立つときは文字列ｐの左側のどの文字列も文字列ｑからの編集距離はＤよりも大きく（遠く）なる。
【００４４】
図１０は、文字列ｑ、ｐ、ｒの編集距離の関係を示す図である。今、対象データである検索文字列をｑ、ＶＰ木のあるノードの文字列をｐ、文字列ｐのノードの任意の右側子ノード文字列をｒとする。検索文字列との編集距離がＤ以下の文字列をＶＰ木で検索する場合、Ｄ＋ｄ（ｑ，ｐ）≦Ｍが成り立てば、そのノードの右側の枝は検索しなくてよい（以降、右側の枝刈りと呼ぶ）
【００４５】
Ｄ＋ｄ（ｑ，ｐ）≦Ｍが成り立つとき、文字列ｐのノードの右側ノード文字列で検索文字列ｑとの間の編集距離がＤ以下になるものは存在しない。図１０に示すように、文字列ｐのノードの右側のすべての子ノードは文字列ｐのノードから半径Ｍの外側にあるので、Ｄ＋ｄ（ｑ，ｐ）≦Ｍが成り立つときは文字列ｐの右側のどの文字列も文字列ｑからの編集距離はＤよりも大きく（遠く）なる。
【００４６】
図９に示す左側の枝刈り条件および図１０に示す右側の枝刈条件が成り立つ場合には、ＶＰ木での検索の編集距離計算回数は全件検索での編集距離計算回数よりも少なくなり、そのためＶＰ木による検索は全件検索と比べて高速になる。なお、ＶＰ木で枝刈りがまったくできない場合は全件検索となる。
【００４７】
前記で示した枝刈り方法は、メタ文字表現を含まないデータ７４Ａ（図４参照）の場合には適用可能である。しかし、メタ文字表現を含むデータの場合７４Ｂ（図４参照）に適用可能であるかの検討事例がなく、本実施形態において、編集距離の検討を含め詳細に検討した。
【００４８】
（編集距離）
本実施形態における、距離算出部３３が算出する編集距離について説明する。編集距離には、ある文字列と別の文字列の類似度を測る手法のひとつであるレーベンシュタイン（Levenshtein）距離、Damerau-Levenshtein距離などを利用する。但し、本実施形態のメタ文字表現について編集距離を取り扱った例はこれまでない。メタ文字表現の部分は、複数の数値の集合とみなすこともできるため、本実施形態でその取り合い方法について検討した。
【００４９】
編集距離は、編集距離が大きいほど２つの文字列が異なることを表す。編集距離は、対象データである文字列を単位文字ごとに分割し、一方の文字列の単位文字を挿入・削除・置換（場合によっては転置も考慮）して他方の文字列を生成するときの最小操作回数で定義される。メタ文字表現の部分は、数値１個を表すため、メタ文字表現の部分列はどれも単位文字として編集距離を計算する。既に説明したように、検索先がメタ文字表現を含む場合、対象データであるカタログの商品の型番中の数値部分は、１単位文字として編集距離を計算する。
【００５０】
メタ選択表現の部分に関する編集距離の計算ルールを以下のようにする。
（１）メタ選択表現の部分｛ｍ１，ｍ２，ｍ３｝と文字ｎとの比較：ｎがｍ１，ｍ２，ｍ３のいずれかと一致すれば同じ単位文字，一致しなければ異なる単位文字とする。
（２）メタ選択表現の部分どうしである｛ｍ１，ｍ２，ｍ３｝と｛ｎ１，ｎ２，ｎ３，ｎ４｝との比較：メタ選択表現同士がまったく同じ中身であれば同じ単位文字、異なる中身であれば異なる単位文字とする。
【００５１】
例えば、Ａ１−Ｂ２と、Ｃ｛１０，１１｝−Ｄ３との編集距離の算出の場合、文字「Ａ」を文字「Ｃ」に置換し、数値「１」をメタ文字表現の部分「｛１０，１１｝」に置換し、文字「−」は同一であり、文字「Ｂ」を文字「Ｄ」に置換し、数値「２」を数値「３」に置換している、よって、編集距離が「４」となる。
【００５２】
同様に、Ａ１−Ｂ２と、Ｃ｛１，１０｝−Ｂ｛２，３｝との編集距離の算出の場合、文字「Ａ」を文字「Ｃ」に置換し、数値「１」は、メタ文字表現の部分「｛１，１０｝」に含まれており、文字「−」および文字「Ｂ」の両者については同一であり、数値「２」は、メタ文字表現の部分「｛２，３｝」に含まれている。よって、編集距離が「１」となる。
【００５３】
言い換えると、単位文字の比較のルールとしては、下記となる。
（ａ）数値の単位文字同士の比較：
同じ数値であれば、編集距離を＋０（何も加算しないこと）とする。
異なる数値であれば、編集距離を＋１（１を加算すること）とする。
（ｂ）数値の単位文字と、メタ文字表現の部分の比較：
数値がメタ文字表現の部分の範囲に入っていれば編集距離を＋０とする。
数値がメタ文字表現の部分の範囲に入っていなければ編集距離を＋１とする。
（ｃ）メタ文字表現部分同士の比較：
メタ選択表現の部分同士である｛ｍ１，…，ｍＭ｝と｛ｎ１，…，ｎＮ｝とが完全一致の数値であれは、編集距離を＋０とする。
メタ選択表現の部分同士である｛ｍ１，…，ｍＭ｝と｛ｎ１，…，ｎＮ｝とが完全一致の数値でなければ、編集距離を＋１とする。
【００５４】
前記計算ルールに基づいて枝刈り条件について検討した。
図１１は、左側の枝刈り条件を成立する場合における枝刈りができない例を示す図である。ここで、メタ文字表現の文字列は大文字とする。図１１を参照して、左側の枝刈りが可能な条件「Ｄ（＝１）＋Ｍ（＝２）＜ｄ（ｑ，Ｐ）（＝４）」が成立っているが、枝刈りすると、ｑから距離１にあるＬを逃してしまうことを説明する。
【００５５】
メタ文字表現を含む文字列（以下、メタ文字列という）Ｐ「Ｃ｛１０，１１｝−Ｄ３」は、メタ文字を含まない文字列「Ｃ１０−Ｄ３」と「Ｃ１１−Ｄ３」（以下、要素非メタ文字列という）との集合と見ることができる。
【００５６】
非メタ文字列とメタ文字列との間の距離は、計算ルールの定義から、非メタ文字列とメタ文字列を構成する要素非メタ文字列との間の距離の最小値になる。
ｄ（Ａ１−Ｂ２，Ｃ１０−Ｄ３）＝４、
ｄ（Ａ１−Ｂ２，Ｃ１１−Ｄ３）＝４
よりｄ（Ａ１−Ｂ２，Ｃ｛１０，１１｝−Ｄ３）＝４となる。
【００５７】
同様に、メタ文字列Ｌ「Ｃ｛１，１０｝−Ｂ｛２，３｝」は、要素非メタ文字列「Ｃ１−Ｂ２」，「Ｃ１−Ｂ３」，「Ｃ１０−Ｂ２」，「Ｃ１０−Ｂ３」の集合と見ることができる。
ｄ（Ａ１−Ｂ２，Ｃ１−Ｂ２）  ＝１、
ｄ（Ａ１−Ｂ２，Ｃ１−Ｂ３）  ＝２、
ｄ（Ａ１−Ｂ２，Ｃ１０−Ｂ２）＝２、
ｄ（Ａ１−Ｂ２，Ｃ１０−Ｂ３）＝３
より、ｄ（Ａ１−Ｂ２，Ｃ｛１，１０｝−Ｂ｛２，３｝）＝１となる。
【００５８】
一方、メタ文字列Ｐとメタ文字列Ｌとの間の距離は、メタ文字表現部分（｛  ｝部分）同士の比較は完全一致か否かでみるので、ｄ（Ｐ，Ｌ）は、
メタ文字列Ｌを「Ｃ｛１，１０｝−Ｂ２」と「Ｃ｛１，１０｝−Ｂ３」の集合と見て、
ｄ（Ｃ｛１０，１１｝−Ｄ３，Ｃ｛１，１０｝−Ｂ２）＝３、
ｄ（Ｃ｛１０，１１｝−Ｄ３，Ｃ｛１，１０｝−Ｂ３）＝２
より、ｄ（Ｐ，Ｌ）＝２である。
【００５９】
これは、枝刈り条件を考える前提となる三角不等式「ｄ（ｑ，Ｐ）≦ｄ（ｑ，Ｌ）＋ｄ（Ｌ，Ｐ）」が成り立っていない。つまり、今の計算ルールではメタ文字列同士の間で距離が定義できないことになる。
【００６０】
なお、非メタ文字列ａ，ｂとメタ文字列Ｃの間は距離が定義でき、その時に成立っている三角不等式は、
ｄ（ａ，Ｃ）≦ｄ（ａ，ｂ）＋ｄ（ｂ，Ｃ）
である。ただし、メタ文字列をＤとするとき
ｄ（ａ，Ｃ）≦ｄ（ａ，Ｄ）＋ｄ（Ｄ，Ｃ）
は成り立たないことを意味する。
【００６１】
以上から、前記編集ルールに基づくＶＰ木では枝刈りしてはいけないことになってしまい、このままではＶＰ木を利用するメリットが失われる。そこで、ＶＰ木構築時には以下のルールに従うように改善した。
ＶＰ木構築ルール（１）：メタ文字表現を含む文字列と、メタ文字表現を含まない文字列とは分けて別々にＶＰ木を構築する。対象データである検索文字列は、メタ文字表現を含まないので、このルールによって、メタ文字表現を含まないＶＰ木には、通常の編集距離での計算と枝刈り条件が適用できる。
【００６２】
ところで、文字列ｓ（文字列長をＬＬｓとする）と文字列ｔ（文字列長をＬＬｔとする）との間の編集距離ｄ（ｓ，ｔ）については、その定義から、
｜ＬＬｓ−ＬＬｔ｜≦ｄ（ｓ，ｔ）≦ＬＬｓ＋ＬＬｔとなる。
これより｜ＬＬｓ−ｄ（ｓ，ｔ）｜≦ＬＬｔ≦ＬＬｓ＋ｄ（ｓ，ｔ）が得られる。
【００６３】
したがって、検索対象文字列をその長さでグルーピングしておけば、文字列ｑ（文字列長をＬＬｑとする）に対して編集距離Ｄ以下の文字列を抽出する際には文字列長さＬＬが、｜ＬＬｑ−Ｄ｜≦ＬＬ≦ＬＬｓ＋Ｄを満たす文字列についてだけ編集距離を計算すればよい。（以降、これを文字列長グループ検索と呼ぶ。）
【００６４】
そこで、ＶＰ木の構築では以下のルールも設定する。
ＶＰ木構築ルール（２）：メタ文字表現を含む文字列と含まない文字列それぞれで、文字列長ごとにグルーピングし、そのグループ（文字列長）ごとにＶＰ木を作る。
【００６５】
ＶＰ木構築ルール（３）：メタ文字表現を含む文字列のＶＰ木については、メタ文字表現以外の数値部分をメタ文字記号「｛」・「｝」で囲む。
【００６６】
このルールによって、メタ文字列間の編集距離の計算時には、前記（ｃ）メタ文字表現部分同士の比較が適用され、メタ文字列間の編集距離はハウスドルフ距離となる。その結果メタ文字表現を含まない文字列ｑとメタ文字列Ｕ，Ｖとの間の距離の三角不等式として、ｄ（ｑ，Ｕ）≦ｄ（ｑ，Ｖ）＋ｄ（Ｖ，Ｕ）が成り立つようになる。このため、ＶＰ木の左側の枝刈り前提条件となる三角不等式が成り立つようになる。したがって、メタ文字列のＶＰ木でも左側の枝刈り条件が成り立つ場合には左側は枝刈りができる。
【００６７】
図１２は、右側の枝刈り条件を成立する場合における枝刈りができない例を示す図である。右側の枝刈りが可能な条件「Ｄ（＝１）＋ｄ（ｑ，Ｐ）（＝１）≦Ｍ（＝２）」が成立っているが、枝刈りすると、ｑから距離１にあるＲを逃してしまうことを説明する。
【００６８】
メタ文字列Ｐ「Ａ｛１，３｝−Ｄ｛２，３｝」は要素非メタ文字列「Ａ１−Ｄ２」，「Ａ１−Ｄ３」，「Ａ３−Ｄ２」，「Ａ３−Ｄ３」の集合と見ることができる。
ｄ（Ａ１−Ｂ２，Ａ１−Ｄ２）＝１、
ｄ（Ａ１−Ｂ２，Ａ１−Ｄ３）＝２、
ｄ（Ａ１−Ｂ２，Ａ３−Ｄ２）＝２、
ｄ（Ａ１−Ｂ２，Ａ３−Ｄ３）＝３
なので、ｄ（Ａ１−Ｂ２，Ａ｛１，３｝−Ｄ｛２，３｝）＝１となる。
【００６９】
同様に、メタ文字列Ｒ「Ｃ｛１，１０｝−Ｂ｛２，３｝」は、要素非メタ文字列「Ｃ１−Ｂ２」，「Ｃ１−Ｂ３」，「Ｃ１０−Ｂ２」，「Ｃ１０−Ｂ３」の集合と見ることができる。
ｄ（Ａ１−Ｂ２，Ｃ１−Ｂ２）  ＝１、
ｄ（Ａ１−Ｂ２，Ｃ１−Ｂ３）  ＝２、
ｄ（Ａ１−Ｂ２，Ｃ１０−Ｂ２）＝２、
ｄ（Ａ１−Ｂ２，Ｃ１０−Ｂ３）＝３
より、ｄ（Ａ１−Ｂ２，Ｃ｛１，１０｝−Ｂ｛２，３｝）＝１となる。
【００７０】
一方、メタ文字列Ｐとメタ文字列Ｒとの間の距離は、メタ文字表現部分（｛  ｝部分）同士の比較は完全一致か否かでみるので、ｄ（Ｐ，Ｒ）＝３である。
【００７１】
これは、枝刈り条件を考える前提となる三角不等式「ｄ（Ｐ，Ｒ）≦ｄ（Ｐ，ｑ）＋ｄ（ｑ，Ｒ）」が成り立っていない。つまり、今の計算ルールではメタ文字列同士の間で距離が定義できないことになる。
【００７２】
なお、メタ文字列ａ，ｂとメタ文字列Ｃの間は距離が定義でき、その時に成立っている三角不等式は、
ｄ（ａ，Ｃ）≦ｄ（ａ，ｂ）＋ｄ（ｂ，Ｃ）
である。ただし、メタ文字列をＤとするとき、
ｄ（Ｃ，Ｄ）≦ｄ（Ｃ，ａ）＋ｄ（ａ，Ｄ）は成り立たないことを意味する。
【００７３】
そこでＶＰ木検索時には以下のルールを設定する。
ＶＰ木検索ルール（４）：メタ文字表現を含むメタ文字列ＶＰ木の検索では、左側の枝刈り条件が成り立てば左側は枝刈りするが、右側については枝刈り条件が成立するか否かを問わず常に検索する。
【００７４】
このルールによってＶＰ木全体の右側が枝刈りしてはいけないことになるのではなく、各ノードの右側を枝刈りしてはいけないだけである。
【００７５】
また、ＶＰ木構築ルール（２）があるので、ＶＰ木でまったく枝刈りができない場合でも全件検索になることはない。今回のＶＰ木利用による探索時間は最悪で文字列長グループ検索と同じで、枝刈りができればその分だけ高速化する。枝刈りが発生する割合はデータとそのときのＶＰ木の構成に依存する。
【００７６】
なお、ＶＰ木は検索のたびに作る必要はなく、ＶＰ木の元となるデータベースの変更がない限りは一度作ったＶＰ木は使い続けることができる。また、ＶＰ木の構築に要する時間の関数をＯ、ＶＰ木作成に用いるデータ数をｎとすると、Ｏ（ｎｌｏｇｎ）である。したがって、データベースに変更が生じた場合は夜間バッチでＶＰ木を再構築することが可能である。さらに、ＶＰ木構築ルール（１）およびＶＰ木構築ルール（２）のようにデータを分割できるため、ＶＰ木の構築と検索もこの単位で並列化が可能である。この単位での並列化を行えばさらに高速化できる。
【００７７】
（誤入力処理）
図１３は、誤入力処理を示すフローチャートである。図１４は、ＶＰ木の抽出例を示す図である。適宜図１を参照して説明する。誤入力処理Ｓ１３０は、対象データがデータベース７０に格納されていなかった場合に、対象データに類似する候補データをデータベース７０から抽出する処理である。
【００７８】
候補データ抽出部３４は、対象データを受付けると（処理Ｓ１３１）、修正候補リストを初期化する（処理Ｓ１３２）。
【００７９】
ＶＰ木抽出部３２は、抽出条件情報７５に格納されている閾値を読込む（処理Ｓ１３３）。
【００８０】
なお、ＶＰ木抽出部３２が、ＶＰ木検索処理を行う前に、ＶＰ木作成部６０は、予め単位文字数順カタログ型番ＤＢ７４（図４参照）から、メタ文字表現を含まないデータ７４Ａ（メタ文字なし）と、メタ文字表現を含むデータ７４Ｂ（メタ文字あり）とに基づき、単位文字数ごとに分類し（図１４（ａ）参照）、分類された単位文字数ごとに、ＶＰ木を作成している（図１４（ｂ）参照）。
【００８１】
候補データ抽出部３４は、メタ文字表現を含まないＶＰ木検索処理（処理Ｓ１３４）およびメタ文字表現を含むＶＰ木検索処理（処理Ｓ１３５）で、修正候補を抽出する。処理Ｓ１３４および処理Ｓ１３５について、図１５を参照して説明する。
【００８２】
図１５は、ＶＰ木検索処理を示すフローチャートであり、（ａ）はメタ文字表現を含まないＶＰ木検索処理であり、（ｂ）はメタ文字表現を含むＶＰ木検索処理である。
【００８３】
図１５（ａ）に示すメタ文字表現を含まないＶＰ木検索処理Ｓ１３４において、単位文字分割部２１は、対象データを単位文字に分割する（処理Ｓ１５１）。この際、文字列の文字ごとに一単位文字とする。例えば、対象データが「Ａ１０−Ｂ２」の場合、「Ａ，１，０，−，Ｂ，２」と分割され、単位文字数は６となる。ＶＰ木抽出部３２は、単位文字数および閾値に基づき、式（１）による絞込み単位文字数でＶＰ木を絞り込む（処理Ｓ１５２、図１４（ｃ）参照）。なお、処理Ｓ１５１は、入力判定処理Ｓ１１０で既に実行している場合は、省略することができる。
【００８４】
（対象データの単位文字数−閾値）の絶対値
≦絞り込み単位文字数
≦（対象データの単位文字数＋閾値）                ・・・式（１）
具体的には、対象データの単位文字数の「６」および閾値の「１」の場合、式（１）により、５≦絞り込み単位文字数≦７となる。
【００８５】
候補データ抽出部３４は、絞りこまれた単位文字ごとに（処理Ｓ１５３）、処理Ｓ１５４〜処理Ｓ１５６を繰り返す。候補データ抽出部３４は、処理Ｓ１５４で、深さ優先探索を実施し、左側の枝刈り条件を満たすときは、ノードの左側の枝刈りをし、また、右側の枝刈り条件を満たすときは、ノードの右側の枝刈りをする。そして、候補データ抽出部３４は、処理Ｓ１５５で、修正候補データを修正候補リストに登録する。
【００８６】
図１５（ｂ）に示すメタ文字表現を含むＶＰ木検索処理Ｓ１３５において、単位文字分割部２１は、対象データを単位文字に分割する（処理Ｓ１６１）。この際、数値は一単位文字とする。例えば、対象データが「Ａ１０−Ｂ２」の場合、「Ａ，１０，−，Ｂ，２」と分割され、単位文字数は５となる。具体的には、対象データの単位文字数の「５」および閾値の「１」の場合、式（１）により、４≦絞り込み単位文字数≦６となる。ＶＰ木抽出部３２は、単位文字数および閾値に基づき、前記式（１）による絞込み単位文字数でＶＰ木を絞り込む（処理Ｓ１６２、図１４（ｃ）参照）。なお、処理Ｓ１６１は、入力判定処理Ｓ１１０で既に実行している場合は、省略することができる。
【００８７】
候補データ抽出部３４は、絞りこまれた単位文字ごとに（処理Ｓ１６３）、処理Ｓ１６４〜処理Ｓ１６６を繰り返す。候補データ抽出部３４は、処理Ｓ１６４で、深さ優先探索を実施し、左側の枝刈り条件を満たすときは、ノードの左側の枝刈りをするが、右側の枝刈りの条件を満たすか否かを判定せず、検索の対象とすることが本実施形態の特徴のひとつである（図１６参照）。そして、候補データ抽出部３４は、処理Ｓ１６５で、修正候補データを修正候補リストに登録する。
【００８８】
なお、処理Ｓ１５４および処理Ｓ１６４において、深さ優先探索で実施するとしたがこれに限定されるものではない。例えば、幅優先探索で実施してもよい。
【００８９】
図１６は、ＶＰ木の検索例を示す図である。処理Ｓ１６４の内容に具体的に説明する。ノードＡにおいて、左側の枝刈り条件を満たすときは、ノードＢ以下の枝刈りができる。ノードＡにおいて、右側の枝刈り条件を満たすか否かを判定せず、ノードＣに進む。そして、ノードＣにおいて、左側の枝刈り条件を満たすときは、ノードＤ以下の枝刈りができる。ノードＣにおいて、右側の枝刈り条件を満たすか否かを判定せず、ノードＥに進む。さらに、ノードＥにおいて、左側の枝刈り条件を満たさないときは、ノードＦ以下のノードを検索対象とする。また、ノードＥにおいて、右側の枝刈り条件を満たすか否かは判定せず、ノードＧ以下を検索対象とする。
【００９０】
図１３に戻り、候補データ抽出部３４は、修正候補リストに対象データに対する修正候補があるか否かを判定し（処理Ｓ１３６）、修正候補がない場合（処理Ｓ１３６，Ｎｏ）、閾値が大きくなるように変更し（処理Ｓ１３７）、処理Ｓ１３４に戻る。
【００９１】
修正候補がある場合（処理Ｓ１３６，Ｙｅｓ）、候補提示部４０は、誤入力修正履歴ＤＢ７３を参照して、誤入力回数の多い順に並べ替え（処理Ｓ１４０）、並べ替えした修正候補データを、クライアント２００に出力する（処理Ｓ１４１）。出力例は、図１７を参照して後記する。
【００９２】
そして、候補提示部４０は、修正候補データがクライアント２００で選択されたか否かを判定し（処理Ｓ１４２）、選択された場合（処理Ｓ１４２，Ｙｅｓ）、選択された修正候補データの誤入力回数を１加算することによって誤入力修正履歴ＤＢ７３を更新し（処理Ｓ１４３）、一連の処理を終了する。一方、修正候補データが選択されない場合（処理Ｓ１４２，Ｎｏ）、入力判定処理Ｓ１１０に戻り（処理Ｓ１４４、図５参照）、処理を終了する。
【００９３】
図１７は、クライアントの表示画面の一例を示す図である。図１７には、候補提示部４０（図１参照）が提示するクライアント２００の表示画面を示す。表示画面には、例えば、図１７（ａ）に示す例では、「Ａ１０−Ｂ２という型番は存在しません。もしかしてこちらではないでしょうか？Ｃ｛１，１０｝−Ｂ｛２，３｝、Ａ｛１０，１３｝−Ｄ｛２，３｝」という表示がされる。顧客は、発注の入力間違いがあるとすばやく気づくことができ、例えば、Ｃ１０−Ｂ２が入力される。
【００９４】
図１７（ｂ）は、候補提示部４０が、図１７（ａ）のメタ文字表現を含む型番を、メタ文字表現を含まない型番に分解した例である。図１７（ｂ）に示す例では、「Ａ１０−Ｂ２という型番は存在しません。もしかしてこちらではないでしょうか？Ａ１０−Ｄ２、Ｃ１０−Ｂ２、Ｃ１０−Ｂ３、Ａ１０−Ｄ３、Ａ１３−Ｄ２、Ａ１３−Ｄ３、Ｃ１−Ｂ２、Ｃ１−Ｂ３」という表示がされる。顧客は、図１７（ａ）と同様に、発注の入力間違いがあるとすばやく気づくことができる。なお、前記の例は、基本的に距離が小さい順、かつ、アルファベット順に出力している。
【００９５】
本実施形態では、クライアント２００からの入力について説明したが、管理者が入力部８１を介して、対象データを入力してもよい。
【００９６】
対象データに対する比較対象データとして数百万件を対象とすることがある。本実施形態のデータ処理装置を適用することにより、入力誤りを早期に発見できるとともに、類似する型番を提示することができるため、インターネットビジネスの向上に有効な手段となる。また、本実施形態では、カタログの型番を対象データとして示したがこれに限定されるのではなく、メタ文字表現の数値を含む文字列であれば、データ処理方法を適用することができる。
【符号の説明】
【００９７】
１０    処理部
２０    検索部
２１    単位文字分割部
２２    単位文字比較部
３０    抽出部
３２    ＶＰ木抽出部（２分探索木抽出部）
３３    距離算出部
３４    候補データ抽出部
４０    候補提示部
５０    履歴更新部
６０    ＶＰ木作成部（２分探索木作成部）
７０    データベース
７１    カタログＤＢ
７２    カタログ型番ＤＢ
７３    誤入力修正履歴ＤＢ
７４    単位文字数順カタログ型番ＤＢ
７５    抽出条件情報
７６    カタログ型番ＶＰ木ＤＢ（カタログ型番２分探索木ＤＢ）
１００    データ処理装置
２００    クライアント
３００    ネットワーク
Ｓ１１０    入力判定処理
Ｓ１３０    誤入力処理
Ｓ１３４    メタ文字表現を含まないＶＰ木検索処理
Ｓ１３５    メタ文字表現を含むＶＰ木検索処理
【図１】
2015079380.tif 000003
【図２】
2015079380.tif 000004
【図３】
2015079380.tif 000005
【図４】
2015079380.tif 000006
【図５】
2015079380.tif 000007
【図６】
2015079380.tif 000008
【図７】
2015079380.tif 000009
【図８】
2015079380.tif 000010
【図９】
2015079380.tif 000011
【図１０】
2015079380.tif 000012
【図１１】
2015079380.tif 000013
【図１２】
2015079380.tif 000014
【図１３】
2015079380.tif 000015
【図１４】
2015079380.tif 000016
【図１５】
2015079380.tif 000017
【図１６】
2015079380.tif 000018
【図１７】
2015079380.tif 000019