検索装置、プログラム及び方法
【課題】高速に類似する文字列の検索を行う。
【解決手段】本装置は、検索対象文字列の第1検索用データと、1以上第1所定文字数以下の整数Nの各々について各検索対象文字列におけるN文字以降の文字の順番を入れ替えた反転文字列についての第2検索用データを格納するデータ格納部と、第1検索用データに対して検索文字列の前方一致検索を行って、第2所定文字数以上前方一致する検索対象文字列を検出する第1検索部と、検索文字列における整数M文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、整数Mについての第2検索用データに対して行って、第2所定文字数以上前方一致する反転文字列を検出し、整数M-2文字一致した反転文字列が存在するか否かを判断する第2検索部と、第2検索部に対して、第2所定文字数から整数Mについての検索指示を、第2検索部により整数M-2文字一致した反転文字列が存在しないと判断された直後を除き出力する制御部とを有する。
【解決手段】本装置は、検索対象文字列の第1検索用データと、1以上第1所定文字数以下の整数Nの各々について各検索対象文字列におけるN文字以降の文字の順番を入れ替えた反転文字列についての第2検索用データを格納するデータ格納部と、第1検索用データに対して検索文字列の前方一致検索を行って、第2所定文字数以上前方一致する検索対象文字列を検出する第1検索部と、検索文字列における整数M文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、整数Mについての第2検索用データに対して行って、第2所定文字数以上前方一致する反転文字列を検出し、整数M-2文字一致した反転文字列が存在するか否かを判断する第2検索部と、第2検索部に対して、第2所定文字数から整数Mについての検索指示を、第2検索部により整数M-2文字一致した反転文字列が存在しないと判断された直後を除き出力する制御部とを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、文字列の検索技術に関する。
【背景技術】
【０００２】
名寄せとは、名称や住所、電話番号等の複数の属性で表現されるレコードについて、同一実体を表すレコードを収集する処理である。属性毎に、例えば文字列の類似性を評価して、同一実体か否かを判断することになる。同一実体を表すレコードの属性の値は、本来であれば同一の値となるべきであるが、様々な理由で類似した値となる場合がある。例えば、「渡辺商店」とすべきところ「渡邊商店」と異字体が入力される場合や、「ＡＡ研究所」とすべきところ「ＡＡ研」といったような省略がなされる場合、「ＡＡ研究所」とすべきところ「Ａっつ研究所」といったように入力ミスがある場合などが想定される。
【０００３】
名寄せでは、このような同一の値ではなく類似する値となっている場合でもレコードを抽出して、他の要素と共に評価して同一実体であると推定されるレコード群を特定する。
【０００４】
なお、入力ＵＲＬ（Uniform Resource Locator）で、有害Ｗｅｂ（ウェブ）サイトのＵＲＬを格納しているデータベースを検索する場合、ＵＲＬの特性を用いて文字列検索を行う技術が存在している。具体的には、ＵＲＬのホスト＋ドメイン部分については右から左方向に詳細になっており、ＵＲＬのホスト＋ドメイン部分のうちホスト部分を簡単に変更できること、ドメイン部分についてもサブドメインの定義が可能であるという特性がある。そこで、ホスト＋ドメイン部分については右からの一致を優先すべく、例えばホスト＋ドメイン部分がｗｗｗ．ａｂｃ．ｄｅｆ．ｃｏ．ｊｐであれば、ｐｊ．ｏｃ．ｆｅｄ．ｃｂａ．ｗｗｗといったホスト＋ドメイン名の区切りで文字の順番を反転させた形でデータベースに登録しておき、検索する際も入力ＵＲＬのホスト＋ドメイン部分をドット毎の区切りで文字の順番を反転させて文字列の前方一致検索を行うものである。しかしながら、この技術は、ＵＲＬの特性に基づき、ホスト＋ドメイン名の区切りで文字の順番を入れ替えているだけで、名寄せにそのまま適用できるようなものではない。すなわち、一般的には文字列間の異なり位置は不確定であり、スラッシュのように確定した区切り位置は存在していない。
【０００５】
一般的な検索文字列と一般的な検索対象文字列とを比較する際に、それらの間で相違が発生する文字位置は様々である。大量の検索対象文字列から、検索文字列に前方からだけではなく後方からも類似する検索対象文字列を抽出するには、相違する文字位置のバリエーションを考慮すると、相当の処理時間が掛ってしまう。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−２２１２９４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
従って、本技術の目的は、一側面において、高速に類似する文字列の検索を行うための技術を提供することである。
【課題を解決するための手段】
【０００８】
本検索装置は、（Ａ）検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部と、（Ｂ）第１のデータ格納部に格納されている第１の検索用データに対して検索文字列の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された検索対象文字列の識別子を第２のデータ格納部に格納する第１の検索部と、（Ｃ）検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、データ格納部に格納されている整数Ｍについての第２の検索用データに対して行って、第２の所定文字数以上前方一致する反転文字列を検出し、検出された反転文字列に対応する検索対象文字列の識別子を第２のデータ格納部に格納し、整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する第２の検索部と、（Ｄ）第２の検索部に対して、第２の所定文字数から１まで当該第２の所定文字数から１までのうち整数Ｍについての検索指示を、第２の検索部により整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き出力する制御部とを有する。
【発明の効果】
【０００９】
高速に類似する文字列の検索を行うことができるようになる。
【図面の簡単な説明】
【００１０】
【図１】図１は、文字列間の比較を説明するための図である。
【図２】図２は、本実施の形態における処理の具体的な例を示す図である。
【図３Ａ】図３Ａは、本実施の形態の概要を説明するための図である。
【図３Ｂ】図３Ｂは、本実施の形態の概要を説明するための図である。
【図３Ｃ】図３Ｃは、本実施の形態の概要を説明するための図である。
【図３Ｄ】図３Ｄは、本実施の形態の概要を説明するための図である。
【図４】図４は、本実施の形態に係る検索装置の機能ブロック図である。
【図５】図５は、検索用データ生成部の機能ブロック図である。
【図６】図６は、検索処理部の機能ブロック図である。
【図７】図７は、検索用データ生成処理の処理フローを示す図である。
【図８】図８は、検索対象文字列の一例を示す図である。
【図９】図９は、ソート後の検索対象文字列の一例を示す図である。
【図１０Ａ】図１０Ａは、第１のグループの例を示す図である。
【図１０Ｂ】図１０Ｂは、第２のグループの例を示す図である。
【図１１】図１１は、検索用データ生成処理の一例を示す図である。
【図１２】図１２は、グループについての処理の一例を示す図である。
【図１３】図１３は、末尾文字「ｅ」の検索用データの一例を示す図である。
【図１４】図１４は、末尾文字「ｇ」の検索用データの一例を示す図である。
【図１５】図１５は、検索処理の処理フローを示す図である。
【図１６】図１６は、検索処理を説明するための具体例を示す図である。
【図１７】図１７は、検索処理の処理フローを示す図である。
【図１８】図１８は、検索処理を説明するための具体例を示す図である。
【図１９】図１９は、検索処理を説明するための具体例を示す図である。
【図２０】図２０は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１１】
名寄せの目的となるデータベースへのデータ入力において、入力ミス等が同一レコードの同一属性で複数回起きる可能性は小さいので、属性毎の文字列において相違箇所は高々１カ所で、且つ相違箇所の長さは文字列全体と比べて小さいという仮定を導入しても、大きな問題はないと考えられる。
【００１２】
相違箇所が１カ所であるなら、相違箇所は、先頭から比較したとき最初に異なる文字が現れる位置から、末尾から比較したときに最初に異なる文字が現れる位置までの区間である。従って、単純な検索方法では、前方一致検索と後方一致検索とを組み合わせることになる。例えば、図１に示すように、文字列Ｓと文字列Ｔとを比較する場合には、前方から後方に向けて「ａ」「ｂ」が一致しており、後方から前方に向けて「ｇ」「ｆ」が一致しているということで、図１の例では、２文字ずつ一致しているでの合計４文字一致していると判断する。
【００１３】
本実施の形態では、条件「先頭からの文字の一致数＋末端からの文字の一致数≧最低一致文字数」を満たすような文字列を高速に抽出するために、以下のような処理を実施する。
【００１４】
具体的には、図２に示すように、（ａ）に示すような検索対象文字列に対して、（ｇ）に示すような検索文字列「ａｂｃｄｅ」が入力されて、４文字以上一致する文字列を抽出する場合の処理について説明する。
【００１５】
本実施の形態では、（ａ）をそのまま辞書順でソートした結果（ｂ）と、検索対象文字列の４文字目以降の文字の順番を反転させた反転文字列について辞書順にソートした結果（ｃ）と、検索対象文字列の３文字目以降の文字の順番を反転させた反転文字列について辞書順にソートした結果（ｄ）と、検索対象文字列の２文字目以降の文字の順番を反転させた反転文字列について辞書順にソートした結果（ｅ）と、検索対象文字列の１文字目以降の文字の順番を反転させた反転文字列について辞書順にソートした結果（ｆ）とを用意する。
【００１６】
そして、検索文字列の先頭４文字「ａｂｃｄ」で（ｂ）を検索して、４文字以上前方一致する検索対象文字列を抽出する。この例ではＩＤ「５」の「ａｂｃｄｇ」が特定される。
【００１７】
さらに、検索文字列の４文字目以降の文字の順番を反転させた反転文字列（ｉ）「ａｂｃｅｄ」の先頭４文字「ａｂｃｅ」で（ｃ）を検索して、４文字以上前方一致する反転文字列を検出する。この例ではＩＤ「４」の「ａｂｃｅｇ」が特定される。なお、本実施の形態では、反転位置（切断点とも呼ぶ）「４」−２＝２文字一致している反転文字列が存在するかを判断する。（ｃ）には存在しないことが分かる。存在しない場合には、以下で述べる理由で反転位置「３」についての検索処理をスキップする。一方、存在する場合には、反転位置「３」についての検索処理を実施する。
【００１８】
このように途中で検索処理をスキップする理由を図３Ａ乃至図３Ｄを用いて説明する。
【００１９】
例えば図３Ａの左側に示すように、切断点（反転位置）が４文字目であり、先頭５文字一致である場合、図３Ａの右側に示すように、切断点（反転位置）が３文字目になると、先頭４文字一致になってしまう。すなわち、一致数≧切断点−１の時には、切断点を先頭方向に１ずらすと一致数は必ず１減少してしまう。
【００２０】
また、図３Ｂの左側に示すように、切断点（反転位置）が４文字目であり、先頭１文字一致である場合、図３Ｂの右側に示すように、切断点（反転位置）が３文字目になると、先頭１文字一致は変わらない。すなわち、一致数＜切断点−２の時には、切断点を先頭方向に１ずらしても、一致数は変化しない。
【００２１】
さらに、図３Ｃの左側に示すように、切断点（反転位置）が４文字目であり、先頭２文字が一致する場合、図３Ｃの右側に示すように、切断点（反転位置）が３の時には、先頭２文字一致は変わらない。なお、上段の元々の文字列は「ａｂｃｄｅｆｇ」であり、下段の元々の文字列は「ａｂｈｅｆｋ」であり、末尾文字は不一致である。すなわち、一致数＝切断点−２の時であって、末尾文字が不一致である場合には、切断点を先頭方向に１ずらしても、一致数は変化しない。
【００２２】
一方、図３Ｄでは、上段の元々の文字列は「ａｂｃｄｅｆｇ」であり、下段の元々の文字列は「ａｂｈｅｆｇ」であり、末尾文字が一致している。このような場合、図３Ｄの左側に示すように、切断点（反転位置）が４文字目であり、先頭２文字が一致する場合、図３Ｄの右側に示すように、切断点（反転位置）が３の時には、先頭５文字一致になる。
【００２３】
このように、一致数＝切断点−２の時、元々の文字列の末尾文字が一致していれば、切断点を左にシフトした場合に一致数が増加し、末尾文字が一致していなければ、切断点を左にシフトした場合に一致数は変化しない、という特性があることが分かる。従って、末尾文字が一致しているか否かに拘わらず、末尾文字が一致している検索対象文字列に対して前方一致検索を行って、一致文字数が切断点−２となる検索対象文字列が存在していれば、切断点を左にシフトした場合において前方一致検索を実施すれば目的の検索対象文字列が得られる可能性がある。
【００２４】
なお、末尾文字が一致している検索対象文字列に対してのみ前方一致検索を行うことができるのであれば、より効率的に目的の検索対象文字列が得られるということになる。
【００２５】
図２の説明に戻って、上でも述べたように、（ｃ）には切断点「４」−２＝２文字一致の反転文字列は存在していないので、切断点「３」（＝現在の切断点「４」−１）についての前方一致検索はスキップできる。
【００２６】
次に、検索文字列の２文字目以降の文字の順番を反転させた反転文字列（ｋ）「ａｅｄｃｂ」の先頭４文字「ａｅｄｃ」で（ｅ）を検索して、４文字以上前方一致する反転文字列を検出する。ここでは該当する反転文字列は存在しない。また、切断点「２」−２＝０文字一致の反転文字列が存在するか判断する。図２の（ｅ）の反転文字列の中には「ｂｅｂｄｃ」が該当するので、切断点「１」の前方一致検索については実行することになる。
【００２７】
そして、検索文字列の１文字目以降の文字の順番を反転させた反転文字列（ｌ）「ｅｄｃｂａ」の先頭４文字「ｅｄｃｂ」で（ｆ）を検索して、４文字以上前方一致する反転文字列を検出する。ここでは該当する反転文字列は存在しない。
【００２８】
このようにして、最終的な検索結果としては、ＩＤ「４」及び「５」の検索対象文字列が得られることになる。
【００２９】
このような処理を実施すれば実施すべき前方一致検索が間引かれて、処理負荷が削減され、検索処理が高速化される。
【００３０】
なお、前方一致で最低一致文字数を満足する場合を除き、図１に示すように、文字列の中間部分で文字列の不一致が発生している場合に、最低一致文字数を満足するのは、検索対象文字列の末尾文字と検索文字列の末尾文字とが一致している場合のみである。図３Ａ乃至３Ｄの観点からも末尾文字が一致しているか否かが分かれば、処理負荷をさらに削減することができる。従って、予め検索対象文字列を、末尾文字の種類毎にグループ化しておけば、前方一致検索を行うべき検索対象文字列の数をさらに削減できる。
【００３１】
以上のような観点から、図４乃至図１９に示すような検索装置を導入するものとする。
【００３２】
図４に示すように、本実施の形態に係る検索装置１０００は、検索対象文字列格納部３０００に格納されている検索対象文字列から検索用データを生成する検索用データ生成部１１００と、検索用データ生成部１１００によって生成された検索用データを格納する検索用データ格納部１２００と、検索条件入力を受け付け且つ検索用データ格納部１２００に対して以下で述べる検索処理を実施する検索処理部１３００と、検索処理部１３００の検索結果を格納する検索結果格納部１４００と、検索結果格納部１４００に格納されている検索結果を検索用データ格納部１２００に基づき出力する出力部１５００とを有する。
【００３３】
図５に示すように、検索用データ生成部１１００は、データ読込部１１１０と、データ分割部１１２０と、文字列グループ格納部１１３０と、文字反転部１１４０と、反転文字列格納部１１５０と、ソート処理部１１６０とを有する。データ読込部１１１０は、検索対象文字列格納部３０００から検索対象文字列を読み出してデータ分割部１１２０とソート処理部１１６０に出力する。データ分割部１１２０は、データ読込部１１１０から得られた検索対象文字列をグループ化する処理を実施し、処理結果を文字列グループ格納部１１３０に格納する。文字列反転部１１４０は、文字列グループ格納部１１３０に格納されているデータに基づき、文字列グループ毎に、所属する検索対象文字列に対して以下で説明する文字反転処理を実施し、処理結果を反転文字列格納部１１５０に格納する。ソート処理部１１６０は、反転文字列格納部１１５０に格納されている反転文字列をグループ毎にソートして検索インデックスのデータを生成し、検索用データ格納部１２００に格納する。
【００３４】
また、図６に示すように、検索処理部１３００は、検索条件取得部１３１０と、検索部１３２０と、制御部１３４０とを有する。検索条件取得部１３１０は、検索条件入力を受け付け、検索部１３２０と制御部１３４０とに出力する。検索部１３２０は、第１検索部１３２１と、第２検索部１３２２とを有する。第１検索部１３２１は、検索文字列について、検索用データ格納部１２００に格納されている検索用データに対して前方一致検索を行い、検索結果を検索結果格納部１４００に格納する。第２検索部１３２２は、制御部１３４０からの指示に従って、検索用データ格納部１２００に格納されている検索用データに対して前方一致検索を行って、検索結果を検索結果格納部１４００に格納する。なお、検索結果のうち一部のデータについては制御部１３４０に出力する。
【００３５】
制御部１３４０は、検索キー生成部１３４１と、条件判定部１３４２とを有している。検索キー生成部１３４１は、検索文字列の一部の文字を反転させて検索キーを生成する。また、条件判定部１３４２は、検索キーの出力前に、以下で詳細に説明する条件を満たしているか否かを判断する。なお、第２検索部１３２２に前方一致検索を実施させるか否かを判断するための検索フラグについては、制御部１３４０及び第２検索部１３２２が参照可能なメモリの領域に用意されているものとする。
【００３６】
以下、検索装置１０００の処理内容を図７乃至図１９を用いて説明する。まず、検索用データ生成部１１００の処理を図７乃至図１４を用いて説明する。データ読込部１１１０は、検索対象文字列格納部３０００から、検索対象文字列を読み込み、データ分割部１１２０及びソート処理部１１６０に出力する（図７：ステップＳ１）。例えば、図８に示すような検索対象文字列が読み込まれたものとする。
【００３７】
そして、ソート処理部１１６０は、検索対象文字列をデータ読込部１１１０から取得し、当該検索対象文字列を辞書順でソートして、切断なしの前方一致検索用のインデックスデータを生成し、検索用データ格納部１２００に格納する（ステップＳ３）。図８のような検索対象文字列の場合には、図９に示すような形で通常の辞書順にソートされる。このようなソート後のデータからインデックスデータを生成する。
【００３８】
また、データ分割部１１２０は、検索対象文字列をデータ読込部１１１０から取得し、当該検索対象文字列を、その末尾の文字でグループ化する（ステップＳ５）。図８の例であれば、末尾文字が「ｇ」のグループ（図１０Ａ）と、「ｅ」のグループ（図１０Ｂ）とがあるので、２つのグループに分けられる。グループ分けについては、様々なバリエーションが可能である。例えば、異なる文字毎にグループを生成しても良いし、複数の種類の文字を纏めてグループ化するようにしてもよい。グループ化の結果については、グループ毎に検索対象文字列を文字列グループ格納部１１３０に格納する。
【００３９】
次に、文字反転部１１４０は、未処理のグループを１つ特定する（ステップＳ７）。そして、文字反転部１１４０は、特定されたグループ内の（最長文字列長−１）をＮに設定する（ステップＳ９）。端子Ａを介して図１１の処理に移行する。
【００４０】
図１１の処理の説明に移行して、文字反転部１１４０は、カウンタｉを１に初期化する（ステップＳ１１）。そして、文字反転部１１４０は、特定されたグループ内の各検索対象文字列について、ｉ文字目以降を反転させた反転文字列を生成し、反転文字列格納部１１５０に格納する（ステップＳ１３）。
【００４１】
例えば、末尾文字が「ｅ」であるグループを処理する場合、図１２の（ａ）に示すような検索文字列が処理の対象となる。そして、ｉ＝３であれば、３文字目以降の文字の順番を入れ替えて、（ｂ）に示すような反転文字列が生成される。
【００４２】
さらに、ソート処理部１１６０は、反転文字列格納部１１５０に格納されており且つ生成した反転文字列を辞書順でソートし、前方一致検索用のインデックスデータを生成して、検索用データ格納部１２００に格納する（ステップＳ１５）。図１２の例では、ソート結果が図１２（ｃ）のようになる。
【００４３】
以上まとめると、例えば、末尾文字が「ｅ」であるグループを処理する場合、図１３に示すように、ｉ＝１であれば（ａ）のようなデータが生成され、ｉ＝２であれば（ｂ）のようなデータが生成され、ｉ＝３であれば（ｃ）のようなデータが生成され、ｉ＝４であれば（ｄ）のようなデータが生成される。
【００４４】
また、末尾文字が「ｇ」であるグループを処理する場合、図１４に示すように、ｉ＝１であれば（ａ）のようなデータが生成され、ｉ＝２であれば（ｂ）のようなデータが生成され、ｉ＝３であれば（ｃ）のようなデータが生成され、ｉ＝４であれば（ｄ）のようなデータが生成される。
【００４５】
そして、文字反転部１１４０は、ｉがＮ以上となったか判断する（ステップＳ１７）。ｉがＮ未満であれば、文字反転部１１４０は、ｉを１インクリメントしてステップＳ１３に戻る（ステップＳ２０）。一方、ｉがＮ以上である場合、文字反転部１１４０は、未処理のグループが文字列グループ格納部１１３０にあるか判断する（ステップＳ１９）。未処理のグループが存在する場合には端子Ｂを介して図７のステップＳ７に戻る。一方、未処理のグループが存在しない場合には、処理を終了する。
【００４６】
以上のような処理を実施すれば、検索用データ格納部１２００には、図９と図１３及び図１４のような検索用データが格納されることになる。
【００４７】
なお、グループ化しない処理の場合には、全検索対象文字列を１つのグループとして設定して、上で述べた処理を実施すればよい。このような場合には、図２上段（ｂ）乃至（ｆ）のデータが、図１３及び図１４のデータの代わりに生成される。
【００４８】
次に、図１５乃至図１９を用いて、検索時の処理について説明する。まず、検索処理部１３００の検索条件取得部１３１０は、検索者からの検索条件（検索文字列及び最低一致文字数Ｌ）の入力を受け付ける（図１５：ステップＳ２１）。なお、検索装置１０００が、ネットワークに接続されており、当該ネットワークに接続されている他の端末から受信するような場合もある。検索条件取得部１３１０は、取得した検索条件のデータを、制御部１３４０と検索部１３２０に出力する。例えば、最小一致文字数Ｌ＝４で、検索文字列「ａｂｃｄｅ」が入力されたものとする。
【００４９】
そして、検索部１３２０の第１検索部１３２１は、検索用データ格納部１２００における、切断なしの検索用インデックスに対して、検索文字列についての前方一致検索を実施し、Ｌ文字以上一致する文字列の識別子を抽出して、検索結果格納部１４００に格納する（ステップＳ２３）。
【００５０】
例えば図１６において、（ａ）に示すような切断なしの検索用データに対して、検索文字列（ｆ）「ａｂｃｄｅ」について前方一致検索を実施する。より具体的には先頭Ｌ文字「ａｂｃｄ」で前方一致検索を実施する。この場合、ＩＤ「５」が得られる。
【００５１】
一方、制御部１３４０の条件判定部１３４２は、切断点Ｎに対して最小一致文字数Ｌを設定する（ステップＳ２５）。また、制御部１３４０は、初期的に、次回の前方一致検索を行うべきことを表す検索フラグをセットする（ステップＳ２７）。そして端子Ｃを介して図１７の処理に移行する。
【００５２】
そして、制御部１３４０の条件判定部１３４２は、Ｎ＝０であるか判断する（ステップＳ２９）。Ｎ＝０ではない場合には、条件判定部１３４２は、検索フラグがセットされているか判断する（ステップＳ３１）。初回は必ず検索フラグがセットされており、ステップＳ３３に移行する。
【００５３】
検索フラグがセットされている場合には、条件判定部１３４２は、検索フラグをオフにセットする（ステップＳ３２）。
【００５４】
その後、条件判定部１３４２は、検索キー生成部１３４１に対して指示を出力し、この指示に応じて検索キー生成部１３４１は、検索文字列におけるＮ文字目以降の文字の順番を反転させた検索キーを生成し、切断点Ｎ及び検索文字列の末尾文字と共に検索キーを第２検索部１３２２に出力する（ステップＳ３３）。そして、第２検索部１３２２は、切断点及び検索文字列の末尾文字と共に検索キーを制御部１３４０から受け取ると、検索用データ格納部１２００における、検索文字列の末尾文字についてのグループにおける切断点Ｎのインデックスに対して、検索キーについての前方一致検索を実施し、最低一致文字数Ｌ文字以上一致する反転文字列の識別子（本実施の形態では元の検索対象文字列と同じ）を抽出して、検索結果格納部１４００に格納する（ステップＳ３５）。末尾文字に応じたグループ分けを行っていない場合には、１つのグループのみが存在するものとして処理すればよい。
【００５５】
「ａｂｃｄｅ」が検索文字列であるから末尾が「ｅ」のグループにおいて、Ｎ＝４であれば、図１６（ｂ）に示す検索用データに対して前方一致検索を行う。この際４文字目以降の文字が反転されるので、図１６（ｇ）に示すように検索キーは「ａｂｃｅｄ」となる。従って、図１８に示すように、ＩＤ「２」の反転文字列についての一致数は「１」であり、ＩＤ「４」の反転文字列についての一致数は「４」であり、ＩＤ「３」の反転文字列についての一致数は「０」となる。従って、ＩＤ「４」が抽出されて、検索結果格納部１４００に格納する。
【００５６】
また、第２検索部１３２２は、一致数が（Ｎ−２）の反転文字列が存在しているか判断し、一致数が（Ｎ−２）の反転文字列が存在している場合には検索フラグをセットする（ステップＳ３７）。上でも述べたように、最低一致文字数Ｌの反転文字列が抽出できる可能性がある場合には検索フラグをセットし、そうでない場合には検索フラグをオフにしたままにする。
【００５７】
なお、図１８の例では、Ｎ＝４から２を引いた一致数２の反転文字列が存在していないので、検索フラグはオフのままになる。そして、ステップＳ４１に移行する。
【００５８】
ステップＳ４１では、条件判定部１３４２は、Ｎを１デクリメントする。その後処理はステップＳ２９に戻る。
【００５９】
上で述べている具体例ではＮ＝３については第２検索部１３２２が前方一致検索を行わないように検索フラグがオフにセットされている。従って、ステップＳ３１では、検索フラグはセットされていないと判断されて、条件判定部１３４２は、検索フラグをセットする（ステップＳ３９）。一度検索フラグがオフにセットされたからといって以降の前方一致検索を全てスキップできるわけではない。従って、ここで次のＮについては前方一致検索を実施すべく、検索フラグをセットする。そしてステップＳ４１に移行する。
【００６０】
図１６の例でもＮ＝３についての検索キー（ｈ）については生成されることなく、検索用データ（ｃ）に対する前方一致検索も行われない。
【００６１】
Ｎ＝２になると、検索フラグがオンになっているので、図１６の（ｉ）で示すような２文字目以降の文字の順番が反転された検索キーが生成される。そして、Ｎ＝２のための検索用データ（ｄ）に対して検索キーについての前方一致検索を実施する。４文字以上一致する反転文字列は存在しない。なお、この場合、図１９に示すように、Ｎ＝２から２を引いた「０」文字一致した反転文字列が存在している。従って、検索フラグがセットされる。
【００６２】
そうすると、Ｎ＝１になって、検索フラグがオンになっているので、図１６（ｊ）で示すような１文字目以降の文字の順番が反転された検索キーが生成される。そして、Ｎ＝１のための検索用データ（ｅ）に対して検索キーについての前方一致検索を実施する。４文字以上一致する反転文字列は存在しない。Ｎ＝１の場合には、ステップＳ３７の処理についてはスキップしても良い。
【００６３】
以上のような処理を実施すれば、検索結果格納部１４００には検索対象文字列の識別子｛４，５｝が格納されることになる。
【００６４】
ステップＳ２９で、Ｎ＝０と判断された場合には、出力部１５００は、検索用データ格納部１２００から、検索結果格納部１４００に格納されている検索対象文字列の識別子に対応する検索対象文字列を抽出して、出力する（ステップＳ４３）。
【００６５】
以上のような処理を実施すれば、文字列中高々１カ所しか不一致がないという前提において、前方からの一致文字数と後方からの一致文字数との和が一定以上、という条件を満足する類似文字列を高速に検索することができる。また、前方一致と後方一致の両方を併用することなく、処理も簡略化されている。
【００６６】
以上本技術の一実施の形態を説明したが、本技術はこれに限定されるものではない。
【００６７】
例えば図４乃至図６の機能ブロック図は一例であって、必ずしも実際のプログラムモジュールと一致しない場合もある。また、処理フローについても、同様の処理結果が得られる限り、ステップの順番を入れ替えたり、並列処理を行っても良い。例えば、第１検索部１３２１と第２検索部１３２２についての検索処理については、並列実施するようにしても良い。
【００６８】
同様に、１つの検索装置１０００に検索用データ生成部１１００と検索処理部１３００とを実施する場合を示しているが、異なる装置によって実施するようにしても良い。さらに、検索用データ生成部１１００の処理についても複数の装置によって実施するようにしても良いし、検索処理部１３００の処理についても複数の装置で処理するようにしても良い。
【００６９】
なお、上で述べた検索装置１０００は、コンピュータ装置であって、図２０に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【００７０】
以上述べた本実施の形態をまとめると以下のようになる。
【００７１】
本実施の形態に係る検索装置は、（Ａ）検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部と、（Ｂ）第１のデータ格納部に格納されている第１の検索用データに対して検索文字列（例えば検索文字列のうち先頭の第２の所定数部分）の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された検索対象文字列の識別子を第２のデータ格納部に格納する第１の検索部と、（Ｃ）検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キー（例えば検索キーのうち先頭の第２の所定数部分）の前方一致検索を、データ格納部に格納されている整数Ｍについての第２の検索用データに対して行って、第２の所定文字数以上前方一致する反転文字列を検出し、検出された反転文字列に対応する検索対象文字列の識別子を第２のデータ格納部に格納し、整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する第２の検索部と、（Ｄ）第２の検索部に対して、第２の所定文字数から１まで第２の所定文字数から１までのうち整数Ｍについての検索指示を、第２の検索部により整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き出力する制御部とを有する。
【００７２】
このようにすれば第２の検索部による前方一致検索の回数を削減することができるため、検索処理が高速化される。
【００７３】
また、上で述べた第２の検索用データが検索対象文字列の末尾文字の種類毎にグループ化されている場合もある。その場合、第２の検索部が、検索文字列の末尾文字と一致する末尾文字の種類のグループに属する第２の検索用データに対して前方一致検索を実施するようにしてもよい。このようにすれば、さらに検索対象文字列を絞り込むことができ、検索処理を高速化することができるようになる。
【００７４】
なお、上で述べた制御部が、第２の検索部に対して、第２の所定文字数を整数Ｍとして検索指示を出力し、第２の検索部により整数Ｍ−２文字一致した反転文字列が存在すると判断された場合には、整数Ｍ−１を新たな整数Ｍとして検索指示を第２の検索部に出力し、第２の検索部により整数Ｍ−２文字一致した反転文字列が存在しないと判断された場合には、整数Ｍ−２を新たな整数Ｍとして検索指示を第２の検索部に出力するようにしてもよい。
【００７５】
さらに、上で述べた検索装置が、１以上第１の所定文字数以下の整数Ｎの各々について各検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列を生成し、当該反転文字列をソートして第２の検索用データを生成する検索用データ生成部をさらに有するようにしてもよい。これによって、自動的に第２の検索用データが生成されるようになる。
【００７６】
また、検索装置が、検索対象文字列の末尾文字の種類毎に検索対象文字列をグループ化し、当該グループの各々について、１以上第１の所定文字数以下の整数Ｎの各々について当該グループに属する各検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列を生成し、当該反転文字列をソートして第２の検索用データを生成する検索用データ生成部をさらに有するようにしても良い。末尾文字でグループ化する場合においても第２の検索用データが自動的に生成されるようになる。
【００７７】
なお、上記処理をコンピュータに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【００７８】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００７９】
（付記１）
検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部と、
前記第１のデータ格納部に格納されている前記第１の検索用データに対して検索文字列の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された前記検索対象文字列の識別子を第２のデータ格納部に格納する第１の検索部と、
前記検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、前記第１のデータ格納部に格納されている前記整数Ｍについての前記第２の検索用データに対して行って、前記第２の所定文字数以上前方一致する反転文字列を検出し、検出された前記反転文字列に対応する前記検索対象文字列の識別子を前記第２のデータ格納部に格納し、前記整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する第２の検索部と、
前記第２の検索部に対して、前記第２の所定文字数から１まで前記第２の所定文字数から１までのうち整数Ｍについての検索指示を、前記第２の検索部により前記整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き出力する制御部と、
を有する検索装置。
【００８０】
（付記２）
前記第２の検索用データが前記検索対象文字列の末尾文字の種類毎にグループ化されており、
前記第２の検索部が、前記検索文字列の末尾文字と一致する末尾文字の種類のグループに属する前記第２の検索用データに対して前方一致検索を実施する
付記１記載の検索装置。
【００８１】
（付記３）
前記制御部が、
前記第２の検索部に対して、前記第２の所定文字数を前記整数Ｍとして検索指示を出力し、
前記第２の検索部により前記整数Ｍ−２文字一致した反転文字列が存在すると判断された場合には、前記整数Ｍ−１を新たな整数Ｍとして検索指示を前記第２の検索部に出力し、
前記第２の検索部により前記整数Ｍ−２文字一致した反転文字列が存在しないと判断された場合には、前記整数Ｍ−２を新たな整数Ｍとして検索指示を前記第２の検索部に出力する
付記１又は２記載の検索装置。
【００８２】
（付記４）
１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列を生成し、当該反転文字列をソートして前記第２の検索用データを生成する検索用データ生成部
をさらに有する付記１乃至３のいずれか１つ記載の検索装置。
【００８３】
（付記５）
前記検索対象文字列の末尾文字の種類毎に前記検索対象文字列をグループ化し、当該グループの各々について、１以上第１の所定文字数以下の整数Ｎの各々について当該グループに属する各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列を生成し、当該反転文字列をソートして前記第２の検索用データを生成する検索用データ生成部
をさらに有する付記２記載の検索装置。
【００８４】
（付記６）
検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部に格納されている前記第１の検索用データに対して検索文字列の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された前記検索対象文字列の識別子を第２のデータ格納部に格納するステップと、
前記第２の所定文字数から１まで前記第２の所定文字数から１までのうち整数Ｍについての検索処理を、当該検索処理において前記整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き実施するステップと、
を含み、
前記検索処理が、
前記検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、前記第１のデータ格納部に格納されている前記整数Ｍについての前記第２の検索用データに対して行って、前記第２の所定文字数以上前方一致する反転文字列を検出し、検出された前記反転文字列に対応する前記検索対象文字列の識別子を前記第２のデータ格納部に格納し、前記整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する処理
であり、コンピュータにより実行される検索処理方法。
【００８５】
（付記７）
検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部に格納されている前記第１の検索用データに対して検索文字列の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された前記検索対象文字列の識別子を第２のデータ格納部に格納するステップと、
前記第２の所定文字数から１まで前記第２の所定文字数から１までのうち整数Ｍについての検索処理を、当該検索処理において前記整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き実施するステップと、
をコンピュータに実行させ、
前記検索処理が、
前記検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、前記第１のデータ格納部に格納されている前記整数Ｍについての前記第２の検索用データに対して行って、前記第２の所定文字数以上前方一致する反転文字列を検出し、検出された前記反転文字列に対応する前記検索対象文字列の識別子を前記第２のデータ格納部に格納し、前記整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する処理
である検索処理プログラム。
【符号の説明】
【００８６】
１０００ 検索装置
３０００ 検索対象文字列格納部
１１００ 検索用データ生成部
１２００ 検索用データ格納部
１３００ 検索処理部
１４００ 検索結果格納部
１５００ 出力部
【技術分野】
【０００１】
本技術は、文字列の検索技術に関する。
【背景技術】
【０００２】
名寄せとは、名称や住所、電話番号等の複数の属性で表現されるレコードについて、同一実体を表すレコードを収集する処理である。属性毎に、例えば文字列の類似性を評価して、同一実体か否かを判断することになる。同一実体を表すレコードの属性の値は、本来であれば同一の値となるべきであるが、様々な理由で類似した値となる場合がある。例えば、「渡辺商店」とすべきところ「渡邊商店」と異字体が入力される場合や、「ＡＡ研究所」とすべきところ「ＡＡ研」といったような省略がなされる場合、「ＡＡ研究所」とすべきところ「Ａっつ研究所」といったように入力ミスがある場合などが想定される。
【０００３】
名寄せでは、このような同一の値ではなく類似する値となっている場合でもレコードを抽出して、他の要素と共に評価して同一実体であると推定されるレコード群を特定する。
【０００４】
なお、入力ＵＲＬ（Uniform Resource Locator）で、有害Ｗｅｂ（ウェブ）サイトのＵＲＬを格納しているデータベースを検索する場合、ＵＲＬの特性を用いて文字列検索を行う技術が存在している。具体的には、ＵＲＬのホスト＋ドメイン部分については右から左方向に詳細になっており、ＵＲＬのホスト＋ドメイン部分のうちホスト部分を簡単に変更できること、ドメイン部分についてもサブドメインの定義が可能であるという特性がある。そこで、ホスト＋ドメイン部分については右からの一致を優先すべく、例えばホスト＋ドメイン部分がｗｗｗ．ａｂｃ．ｄｅｆ．ｃｏ．ｊｐであれば、ｐｊ．ｏｃ．ｆｅｄ．ｃｂａ．ｗｗｗといったホスト＋ドメイン名の区切りで文字の順番を反転させた形でデータベースに登録しておき、検索する際も入力ＵＲＬのホスト＋ドメイン部分をドット毎の区切りで文字の順番を反転させて文字列の前方一致検索を行うものである。しかしながら、この技術は、ＵＲＬの特性に基づき、ホスト＋ドメイン名の区切りで文字の順番を入れ替えているだけで、名寄せにそのまま適用できるようなものではない。すなわち、一般的には文字列間の異なり位置は不確定であり、スラッシュのように確定した区切り位置は存在していない。
【０００５】
一般的な検索文字列と一般的な検索対象文字列とを比較する際に、それらの間で相違が発生する文字位置は様々である。大量の検索対象文字列から、検索文字列に前方からだけではなく後方からも類似する検索対象文字列を抽出するには、相違する文字位置のバリエーションを考慮すると、相当の処理時間が掛ってしまう。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−２２１２９４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
従って、本技術の目的は、一側面において、高速に類似する文字列の検索を行うための技術を提供することである。
【課題を解決するための手段】
【０００８】
本検索装置は、（Ａ）検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部と、（Ｂ）第１のデータ格納部に格納されている第１の検索用データに対して検索文字列の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された検索対象文字列の識別子を第２のデータ格納部に格納する第１の検索部と、（Ｃ）検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、データ格納部に格納されている整数Ｍについての第２の検索用データに対して行って、第２の所定文字数以上前方一致する反転文字列を検出し、検出された反転文字列に対応する検索対象文字列の識別子を第２のデータ格納部に格納し、整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する第２の検索部と、（Ｄ）第２の検索部に対して、第２の所定文字数から１まで当該第２の所定文字数から１までのうち整数Ｍについての検索指示を、第２の検索部により整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き出力する制御部とを有する。
【発明の効果】
【０００９】
高速に類似する文字列の検索を行うことができるようになる。
【図面の簡単な説明】
【００１０】
【図１】図１は、文字列間の比較を説明するための図である。
【図２】図２は、本実施の形態における処理の具体的な例を示す図である。
【図３Ａ】図３Ａは、本実施の形態の概要を説明するための図である。
【図３Ｂ】図３Ｂは、本実施の形態の概要を説明するための図である。
【図３Ｃ】図３Ｃは、本実施の形態の概要を説明するための図である。
【図３Ｄ】図３Ｄは、本実施の形態の概要を説明するための図である。
【図４】図４は、本実施の形態に係る検索装置の機能ブロック図である。
【図５】図５は、検索用データ生成部の機能ブロック図である。
【図６】図６は、検索処理部の機能ブロック図である。
【図７】図７は、検索用データ生成処理の処理フローを示す図である。
【図８】図８は、検索対象文字列の一例を示す図である。
【図９】図９は、ソート後の検索対象文字列の一例を示す図である。
【図１０Ａ】図１０Ａは、第１のグループの例を示す図である。
【図１０Ｂ】図１０Ｂは、第２のグループの例を示す図である。
【図１１】図１１は、検索用データ生成処理の一例を示す図である。
【図１２】図１２は、グループについての処理の一例を示す図である。
【図１３】図１３は、末尾文字「ｅ」の検索用データの一例を示す図である。
【図１４】図１４は、末尾文字「ｇ」の検索用データの一例を示す図である。
【図１５】図１５は、検索処理の処理フローを示す図である。
【図１６】図１６は、検索処理を説明するための具体例を示す図である。
【図１７】図１７は、検索処理の処理フローを示す図である。
【図１８】図１８は、検索処理を説明するための具体例を示す図である。
【図１９】図１９は、検索処理を説明するための具体例を示す図である。
【図２０】図２０は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１１】
名寄せの目的となるデータベースへのデータ入力において、入力ミス等が同一レコードの同一属性で複数回起きる可能性は小さいので、属性毎の文字列において相違箇所は高々１カ所で、且つ相違箇所の長さは文字列全体と比べて小さいという仮定を導入しても、大きな問題はないと考えられる。
【００１２】
相違箇所が１カ所であるなら、相違箇所は、先頭から比較したとき最初に異なる文字が現れる位置から、末尾から比較したときに最初に異なる文字が現れる位置までの区間である。従って、単純な検索方法では、前方一致検索と後方一致検索とを組み合わせることになる。例えば、図１に示すように、文字列Ｓと文字列Ｔとを比較する場合には、前方から後方に向けて「ａ」「ｂ」が一致しており、後方から前方に向けて「ｇ」「ｆ」が一致しているということで、図１の例では、２文字ずつ一致しているでの合計４文字一致していると判断する。
【００１３】
本実施の形態では、条件「先頭からの文字の一致数＋末端からの文字の一致数≧最低一致文字数」を満たすような文字列を高速に抽出するために、以下のような処理を実施する。
【００１４】
具体的には、図２に示すように、（ａ）に示すような検索対象文字列に対して、（ｇ）に示すような検索文字列「ａｂｃｄｅ」が入力されて、４文字以上一致する文字列を抽出する場合の処理について説明する。
【００１５】
本実施の形態では、（ａ）をそのまま辞書順でソートした結果（ｂ）と、検索対象文字列の４文字目以降の文字の順番を反転させた反転文字列について辞書順にソートした結果（ｃ）と、検索対象文字列の３文字目以降の文字の順番を反転させた反転文字列について辞書順にソートした結果（ｄ）と、検索対象文字列の２文字目以降の文字の順番を反転させた反転文字列について辞書順にソートした結果（ｅ）と、検索対象文字列の１文字目以降の文字の順番を反転させた反転文字列について辞書順にソートした結果（ｆ）とを用意する。
【００１６】
そして、検索文字列の先頭４文字「ａｂｃｄ」で（ｂ）を検索して、４文字以上前方一致する検索対象文字列を抽出する。この例ではＩＤ「５」の「ａｂｃｄｇ」が特定される。
【００１７】
さらに、検索文字列の４文字目以降の文字の順番を反転させた反転文字列（ｉ）「ａｂｃｅｄ」の先頭４文字「ａｂｃｅ」で（ｃ）を検索して、４文字以上前方一致する反転文字列を検出する。この例ではＩＤ「４」の「ａｂｃｅｇ」が特定される。なお、本実施の形態では、反転位置（切断点とも呼ぶ）「４」−２＝２文字一致している反転文字列が存在するかを判断する。（ｃ）には存在しないことが分かる。存在しない場合には、以下で述べる理由で反転位置「３」についての検索処理をスキップする。一方、存在する場合には、反転位置「３」についての検索処理を実施する。
【００１８】
このように途中で検索処理をスキップする理由を図３Ａ乃至図３Ｄを用いて説明する。
【００１９】
例えば図３Ａの左側に示すように、切断点（反転位置）が４文字目であり、先頭５文字一致である場合、図３Ａの右側に示すように、切断点（反転位置）が３文字目になると、先頭４文字一致になってしまう。すなわち、一致数≧切断点−１の時には、切断点を先頭方向に１ずらすと一致数は必ず１減少してしまう。
【００２０】
また、図３Ｂの左側に示すように、切断点（反転位置）が４文字目であり、先頭１文字一致である場合、図３Ｂの右側に示すように、切断点（反転位置）が３文字目になると、先頭１文字一致は変わらない。すなわち、一致数＜切断点−２の時には、切断点を先頭方向に１ずらしても、一致数は変化しない。
【００２１】
さらに、図３Ｃの左側に示すように、切断点（反転位置）が４文字目であり、先頭２文字が一致する場合、図３Ｃの右側に示すように、切断点（反転位置）が３の時には、先頭２文字一致は変わらない。なお、上段の元々の文字列は「ａｂｃｄｅｆｇ」であり、下段の元々の文字列は「ａｂｈｅｆｋ」であり、末尾文字は不一致である。すなわち、一致数＝切断点−２の時であって、末尾文字が不一致である場合には、切断点を先頭方向に１ずらしても、一致数は変化しない。
【００２２】
一方、図３Ｄでは、上段の元々の文字列は「ａｂｃｄｅｆｇ」であり、下段の元々の文字列は「ａｂｈｅｆｇ」であり、末尾文字が一致している。このような場合、図３Ｄの左側に示すように、切断点（反転位置）が４文字目であり、先頭２文字が一致する場合、図３Ｄの右側に示すように、切断点（反転位置）が３の時には、先頭５文字一致になる。
【００２３】
このように、一致数＝切断点−２の時、元々の文字列の末尾文字が一致していれば、切断点を左にシフトした場合に一致数が増加し、末尾文字が一致していなければ、切断点を左にシフトした場合に一致数は変化しない、という特性があることが分かる。従って、末尾文字が一致しているか否かに拘わらず、末尾文字が一致している検索対象文字列に対して前方一致検索を行って、一致文字数が切断点−２となる検索対象文字列が存在していれば、切断点を左にシフトした場合において前方一致検索を実施すれば目的の検索対象文字列が得られる可能性がある。
【００２４】
なお、末尾文字が一致している検索対象文字列に対してのみ前方一致検索を行うことができるのであれば、より効率的に目的の検索対象文字列が得られるということになる。
【００２５】
図２の説明に戻って、上でも述べたように、（ｃ）には切断点「４」−２＝２文字一致の反転文字列は存在していないので、切断点「３」（＝現在の切断点「４」−１）についての前方一致検索はスキップできる。
【００２６】
次に、検索文字列の２文字目以降の文字の順番を反転させた反転文字列（ｋ）「ａｅｄｃｂ」の先頭４文字「ａｅｄｃ」で（ｅ）を検索して、４文字以上前方一致する反転文字列を検出する。ここでは該当する反転文字列は存在しない。また、切断点「２」−２＝０文字一致の反転文字列が存在するか判断する。図２の（ｅ）の反転文字列の中には「ｂｅｂｄｃ」が該当するので、切断点「１」の前方一致検索については実行することになる。
【００２７】
そして、検索文字列の１文字目以降の文字の順番を反転させた反転文字列（ｌ）「ｅｄｃｂａ」の先頭４文字「ｅｄｃｂ」で（ｆ）を検索して、４文字以上前方一致する反転文字列を検出する。ここでは該当する反転文字列は存在しない。
【００２８】
このようにして、最終的な検索結果としては、ＩＤ「４」及び「５」の検索対象文字列が得られることになる。
【００２９】
このような処理を実施すれば実施すべき前方一致検索が間引かれて、処理負荷が削減され、検索処理が高速化される。
【００３０】
なお、前方一致で最低一致文字数を満足する場合を除き、図１に示すように、文字列の中間部分で文字列の不一致が発生している場合に、最低一致文字数を満足するのは、検索対象文字列の末尾文字と検索文字列の末尾文字とが一致している場合のみである。図３Ａ乃至３Ｄの観点からも末尾文字が一致しているか否かが分かれば、処理負荷をさらに削減することができる。従って、予め検索対象文字列を、末尾文字の種類毎にグループ化しておけば、前方一致検索を行うべき検索対象文字列の数をさらに削減できる。
【００３１】
以上のような観点から、図４乃至図１９に示すような検索装置を導入するものとする。
【００３２】
図４に示すように、本実施の形態に係る検索装置１０００は、検索対象文字列格納部３０００に格納されている検索対象文字列から検索用データを生成する検索用データ生成部１１００と、検索用データ生成部１１００によって生成された検索用データを格納する検索用データ格納部１２００と、検索条件入力を受け付け且つ検索用データ格納部１２００に対して以下で述べる検索処理を実施する検索処理部１３００と、検索処理部１３００の検索結果を格納する検索結果格納部１４００と、検索結果格納部１４００に格納されている検索結果を検索用データ格納部１２００に基づき出力する出力部１５００とを有する。
【００３３】
図５に示すように、検索用データ生成部１１００は、データ読込部１１１０と、データ分割部１１２０と、文字列グループ格納部１１３０と、文字反転部１１４０と、反転文字列格納部１１５０と、ソート処理部１１６０とを有する。データ読込部１１１０は、検索対象文字列格納部３０００から検索対象文字列を読み出してデータ分割部１１２０とソート処理部１１６０に出力する。データ分割部１１２０は、データ読込部１１１０から得られた検索対象文字列をグループ化する処理を実施し、処理結果を文字列グループ格納部１１３０に格納する。文字列反転部１１４０は、文字列グループ格納部１１３０に格納されているデータに基づき、文字列グループ毎に、所属する検索対象文字列に対して以下で説明する文字反転処理を実施し、処理結果を反転文字列格納部１１５０に格納する。ソート処理部１１６０は、反転文字列格納部１１５０に格納されている反転文字列をグループ毎にソートして検索インデックスのデータを生成し、検索用データ格納部１２００に格納する。
【００３４】
また、図６に示すように、検索処理部１３００は、検索条件取得部１３１０と、検索部１３２０と、制御部１３４０とを有する。検索条件取得部１３１０は、検索条件入力を受け付け、検索部１３２０と制御部１３４０とに出力する。検索部１３２０は、第１検索部１３２１と、第２検索部１３２２とを有する。第１検索部１３２１は、検索文字列について、検索用データ格納部１２００に格納されている検索用データに対して前方一致検索を行い、検索結果を検索結果格納部１４００に格納する。第２検索部１３２２は、制御部１３４０からの指示に従って、検索用データ格納部１２００に格納されている検索用データに対して前方一致検索を行って、検索結果を検索結果格納部１４００に格納する。なお、検索結果のうち一部のデータについては制御部１３４０に出力する。
【００３５】
制御部１３４０は、検索キー生成部１３４１と、条件判定部１３４２とを有している。検索キー生成部１３４１は、検索文字列の一部の文字を反転させて検索キーを生成する。また、条件判定部１３４２は、検索キーの出力前に、以下で詳細に説明する条件を満たしているか否かを判断する。なお、第２検索部１３２２に前方一致検索を実施させるか否かを判断するための検索フラグについては、制御部１３４０及び第２検索部１３２２が参照可能なメモリの領域に用意されているものとする。
【００３６】
以下、検索装置１０００の処理内容を図７乃至図１９を用いて説明する。まず、検索用データ生成部１１００の処理を図７乃至図１４を用いて説明する。データ読込部１１１０は、検索対象文字列格納部３０００から、検索対象文字列を読み込み、データ分割部１１２０及びソート処理部１１６０に出力する（図７：ステップＳ１）。例えば、図８に示すような検索対象文字列が読み込まれたものとする。
【００３７】
そして、ソート処理部１１６０は、検索対象文字列をデータ読込部１１１０から取得し、当該検索対象文字列を辞書順でソートして、切断なしの前方一致検索用のインデックスデータを生成し、検索用データ格納部１２００に格納する（ステップＳ３）。図８のような検索対象文字列の場合には、図９に示すような形で通常の辞書順にソートされる。このようなソート後のデータからインデックスデータを生成する。
【００３８】
また、データ分割部１１２０は、検索対象文字列をデータ読込部１１１０から取得し、当該検索対象文字列を、その末尾の文字でグループ化する（ステップＳ５）。図８の例であれば、末尾文字が「ｇ」のグループ（図１０Ａ）と、「ｅ」のグループ（図１０Ｂ）とがあるので、２つのグループに分けられる。グループ分けについては、様々なバリエーションが可能である。例えば、異なる文字毎にグループを生成しても良いし、複数の種類の文字を纏めてグループ化するようにしてもよい。グループ化の結果については、グループ毎に検索対象文字列を文字列グループ格納部１１３０に格納する。
【００３９】
次に、文字反転部１１４０は、未処理のグループを１つ特定する（ステップＳ７）。そして、文字反転部１１４０は、特定されたグループ内の（最長文字列長−１）をＮに設定する（ステップＳ９）。端子Ａを介して図１１の処理に移行する。
【００４０】
図１１の処理の説明に移行して、文字反転部１１４０は、カウンタｉを１に初期化する（ステップＳ１１）。そして、文字反転部１１４０は、特定されたグループ内の各検索対象文字列について、ｉ文字目以降を反転させた反転文字列を生成し、反転文字列格納部１１５０に格納する（ステップＳ１３）。
【００４１】
例えば、末尾文字が「ｅ」であるグループを処理する場合、図１２の（ａ）に示すような検索文字列が処理の対象となる。そして、ｉ＝３であれば、３文字目以降の文字の順番を入れ替えて、（ｂ）に示すような反転文字列が生成される。
【００４２】
さらに、ソート処理部１１６０は、反転文字列格納部１１５０に格納されており且つ生成した反転文字列を辞書順でソートし、前方一致検索用のインデックスデータを生成して、検索用データ格納部１２００に格納する（ステップＳ１５）。図１２の例では、ソート結果が図１２（ｃ）のようになる。
【００４３】
以上まとめると、例えば、末尾文字が「ｅ」であるグループを処理する場合、図１３に示すように、ｉ＝１であれば（ａ）のようなデータが生成され、ｉ＝２であれば（ｂ）のようなデータが生成され、ｉ＝３であれば（ｃ）のようなデータが生成され、ｉ＝４であれば（ｄ）のようなデータが生成される。
【００４４】
また、末尾文字が「ｇ」であるグループを処理する場合、図１４に示すように、ｉ＝１であれば（ａ）のようなデータが生成され、ｉ＝２であれば（ｂ）のようなデータが生成され、ｉ＝３であれば（ｃ）のようなデータが生成され、ｉ＝４であれば（ｄ）のようなデータが生成される。
【００４５】
そして、文字反転部１１４０は、ｉがＮ以上となったか判断する（ステップＳ１７）。ｉがＮ未満であれば、文字反転部１１４０は、ｉを１インクリメントしてステップＳ１３に戻る（ステップＳ２０）。一方、ｉがＮ以上である場合、文字反転部１１４０は、未処理のグループが文字列グループ格納部１１３０にあるか判断する（ステップＳ１９）。未処理のグループが存在する場合には端子Ｂを介して図７のステップＳ７に戻る。一方、未処理のグループが存在しない場合には、処理を終了する。
【００４６】
以上のような処理を実施すれば、検索用データ格納部１２００には、図９と図１３及び図１４のような検索用データが格納されることになる。
【００４７】
なお、グループ化しない処理の場合には、全検索対象文字列を１つのグループとして設定して、上で述べた処理を実施すればよい。このような場合には、図２上段（ｂ）乃至（ｆ）のデータが、図１３及び図１４のデータの代わりに生成される。
【００４８】
次に、図１５乃至図１９を用いて、検索時の処理について説明する。まず、検索処理部１３００の検索条件取得部１３１０は、検索者からの検索条件（検索文字列及び最低一致文字数Ｌ）の入力を受け付ける（図１５：ステップＳ２１）。なお、検索装置１０００が、ネットワークに接続されており、当該ネットワークに接続されている他の端末から受信するような場合もある。検索条件取得部１３１０は、取得した検索条件のデータを、制御部１３４０と検索部１３２０に出力する。例えば、最小一致文字数Ｌ＝４で、検索文字列「ａｂｃｄｅ」が入力されたものとする。
【００４９】
そして、検索部１３２０の第１検索部１３２１は、検索用データ格納部１２００における、切断なしの検索用インデックスに対して、検索文字列についての前方一致検索を実施し、Ｌ文字以上一致する文字列の識別子を抽出して、検索結果格納部１４００に格納する（ステップＳ２３）。
【００５０】
例えば図１６において、（ａ）に示すような切断なしの検索用データに対して、検索文字列（ｆ）「ａｂｃｄｅ」について前方一致検索を実施する。より具体的には先頭Ｌ文字「ａｂｃｄ」で前方一致検索を実施する。この場合、ＩＤ「５」が得られる。
【００５１】
一方、制御部１３４０の条件判定部１３４２は、切断点Ｎに対して最小一致文字数Ｌを設定する（ステップＳ２５）。また、制御部１３４０は、初期的に、次回の前方一致検索を行うべきことを表す検索フラグをセットする（ステップＳ２７）。そして端子Ｃを介して図１７の処理に移行する。
【００５２】
そして、制御部１３４０の条件判定部１３４２は、Ｎ＝０であるか判断する（ステップＳ２９）。Ｎ＝０ではない場合には、条件判定部１３４２は、検索フラグがセットされているか判断する（ステップＳ３１）。初回は必ず検索フラグがセットされており、ステップＳ３３に移行する。
【００５３】
検索フラグがセットされている場合には、条件判定部１３４２は、検索フラグをオフにセットする（ステップＳ３２）。
【００５４】
その後、条件判定部１３４２は、検索キー生成部１３４１に対して指示を出力し、この指示に応じて検索キー生成部１３４１は、検索文字列におけるＮ文字目以降の文字の順番を反転させた検索キーを生成し、切断点Ｎ及び検索文字列の末尾文字と共に検索キーを第２検索部１３２２に出力する（ステップＳ３３）。そして、第２検索部１３２２は、切断点及び検索文字列の末尾文字と共に検索キーを制御部１３４０から受け取ると、検索用データ格納部１２００における、検索文字列の末尾文字についてのグループにおける切断点Ｎのインデックスに対して、検索キーについての前方一致検索を実施し、最低一致文字数Ｌ文字以上一致する反転文字列の識別子（本実施の形態では元の検索対象文字列と同じ）を抽出して、検索結果格納部１４００に格納する（ステップＳ３５）。末尾文字に応じたグループ分けを行っていない場合には、１つのグループのみが存在するものとして処理すればよい。
【００５５】
「ａｂｃｄｅ」が検索文字列であるから末尾が「ｅ」のグループにおいて、Ｎ＝４であれば、図１６（ｂ）に示す検索用データに対して前方一致検索を行う。この際４文字目以降の文字が反転されるので、図１６（ｇ）に示すように検索キーは「ａｂｃｅｄ」となる。従って、図１８に示すように、ＩＤ「２」の反転文字列についての一致数は「１」であり、ＩＤ「４」の反転文字列についての一致数は「４」であり、ＩＤ「３」の反転文字列についての一致数は「０」となる。従って、ＩＤ「４」が抽出されて、検索結果格納部１４００に格納する。
【００５６】
また、第２検索部１３２２は、一致数が（Ｎ−２）の反転文字列が存在しているか判断し、一致数が（Ｎ−２）の反転文字列が存在している場合には検索フラグをセットする（ステップＳ３７）。上でも述べたように、最低一致文字数Ｌの反転文字列が抽出できる可能性がある場合には検索フラグをセットし、そうでない場合には検索フラグをオフにしたままにする。
【００５７】
なお、図１８の例では、Ｎ＝４から２を引いた一致数２の反転文字列が存在していないので、検索フラグはオフのままになる。そして、ステップＳ４１に移行する。
【００５８】
ステップＳ４１では、条件判定部１３４２は、Ｎを１デクリメントする。その後処理はステップＳ２９に戻る。
【００５９】
上で述べている具体例ではＮ＝３については第２検索部１３２２が前方一致検索を行わないように検索フラグがオフにセットされている。従って、ステップＳ３１では、検索フラグはセットされていないと判断されて、条件判定部１３４２は、検索フラグをセットする（ステップＳ３９）。一度検索フラグがオフにセットされたからといって以降の前方一致検索を全てスキップできるわけではない。従って、ここで次のＮについては前方一致検索を実施すべく、検索フラグをセットする。そしてステップＳ４１に移行する。
【００６０】
図１６の例でもＮ＝３についての検索キー（ｈ）については生成されることなく、検索用データ（ｃ）に対する前方一致検索も行われない。
【００６１】
Ｎ＝２になると、検索フラグがオンになっているので、図１６の（ｉ）で示すような２文字目以降の文字の順番が反転された検索キーが生成される。そして、Ｎ＝２のための検索用データ（ｄ）に対して検索キーについての前方一致検索を実施する。４文字以上一致する反転文字列は存在しない。なお、この場合、図１９に示すように、Ｎ＝２から２を引いた「０」文字一致した反転文字列が存在している。従って、検索フラグがセットされる。
【００６２】
そうすると、Ｎ＝１になって、検索フラグがオンになっているので、図１６（ｊ）で示すような１文字目以降の文字の順番が反転された検索キーが生成される。そして、Ｎ＝１のための検索用データ（ｅ）に対して検索キーについての前方一致検索を実施する。４文字以上一致する反転文字列は存在しない。Ｎ＝１の場合には、ステップＳ３７の処理についてはスキップしても良い。
【００６３】
以上のような処理を実施すれば、検索結果格納部１４００には検索対象文字列の識別子｛４，５｝が格納されることになる。
【００６４】
ステップＳ２９で、Ｎ＝０と判断された場合には、出力部１５００は、検索用データ格納部１２００から、検索結果格納部１４００に格納されている検索対象文字列の識別子に対応する検索対象文字列を抽出して、出力する（ステップＳ４３）。
【００６５】
以上のような処理を実施すれば、文字列中高々１カ所しか不一致がないという前提において、前方からの一致文字数と後方からの一致文字数との和が一定以上、という条件を満足する類似文字列を高速に検索することができる。また、前方一致と後方一致の両方を併用することなく、処理も簡略化されている。
【００６６】
以上本技術の一実施の形態を説明したが、本技術はこれに限定されるものではない。
【００６７】
例えば図４乃至図６の機能ブロック図は一例であって、必ずしも実際のプログラムモジュールと一致しない場合もある。また、処理フローについても、同様の処理結果が得られる限り、ステップの順番を入れ替えたり、並列処理を行っても良い。例えば、第１検索部１３２１と第２検索部１３２２についての検索処理については、並列実施するようにしても良い。
【００６８】
同様に、１つの検索装置１０００に検索用データ生成部１１００と検索処理部１３００とを実施する場合を示しているが、異なる装置によって実施するようにしても良い。さらに、検索用データ生成部１１００の処理についても複数の装置によって実施するようにしても良いし、検索処理部１３００の処理についても複数の装置で処理するようにしても良い。
【００６９】
なお、上で述べた検索装置１０００は、コンピュータ装置であって、図２０に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【００７０】
以上述べた本実施の形態をまとめると以下のようになる。
【００７１】
本実施の形態に係る検索装置は、（Ａ）検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部と、（Ｂ）第１のデータ格納部に格納されている第１の検索用データに対して検索文字列（例えば検索文字列のうち先頭の第２の所定数部分）の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された検索対象文字列の識別子を第２のデータ格納部に格納する第１の検索部と、（Ｃ）検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キー（例えば検索キーのうち先頭の第２の所定数部分）の前方一致検索を、データ格納部に格納されている整数Ｍについての第２の検索用データに対して行って、第２の所定文字数以上前方一致する反転文字列を検出し、検出された反転文字列に対応する検索対象文字列の識別子を第２のデータ格納部に格納し、整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する第２の検索部と、（Ｄ）第２の検索部に対して、第２の所定文字数から１まで第２の所定文字数から１までのうち整数Ｍについての検索指示を、第２の検索部により整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き出力する制御部とを有する。
【００７２】
このようにすれば第２の検索部による前方一致検索の回数を削減することができるため、検索処理が高速化される。
【００７３】
また、上で述べた第２の検索用データが検索対象文字列の末尾文字の種類毎にグループ化されている場合もある。その場合、第２の検索部が、検索文字列の末尾文字と一致する末尾文字の種類のグループに属する第２の検索用データに対して前方一致検索を実施するようにしてもよい。このようにすれば、さらに検索対象文字列を絞り込むことができ、検索処理を高速化することができるようになる。
【００７４】
なお、上で述べた制御部が、第２の検索部に対して、第２の所定文字数を整数Ｍとして検索指示を出力し、第２の検索部により整数Ｍ−２文字一致した反転文字列が存在すると判断された場合には、整数Ｍ−１を新たな整数Ｍとして検索指示を第２の検索部に出力し、第２の検索部により整数Ｍ−２文字一致した反転文字列が存在しないと判断された場合には、整数Ｍ−２を新たな整数Ｍとして検索指示を第２の検索部に出力するようにしてもよい。
【００７５】
さらに、上で述べた検索装置が、１以上第１の所定文字数以下の整数Ｎの各々について各検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列を生成し、当該反転文字列をソートして第２の検索用データを生成する検索用データ生成部をさらに有するようにしてもよい。これによって、自動的に第２の検索用データが生成されるようになる。
【００７６】
また、検索装置が、検索対象文字列の末尾文字の種類毎に検索対象文字列をグループ化し、当該グループの各々について、１以上第１の所定文字数以下の整数Ｎの各々について当該グループに属する各検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列を生成し、当該反転文字列をソートして第２の検索用データを生成する検索用データ生成部をさらに有するようにしても良い。末尾文字でグループ化する場合においても第２の検索用データが自動的に生成されるようになる。
【００７７】
なお、上記処理をコンピュータに行わせるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブルディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。尚、中間的な処理結果はメインメモリ等の記憶装置に一時保管される。
【００７８】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００７９】
（付記１）
検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部と、
前記第１のデータ格納部に格納されている前記第１の検索用データに対して検索文字列の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された前記検索対象文字列の識別子を第２のデータ格納部に格納する第１の検索部と、
前記検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、前記第１のデータ格納部に格納されている前記整数Ｍについての前記第２の検索用データに対して行って、前記第２の所定文字数以上前方一致する反転文字列を検出し、検出された前記反転文字列に対応する前記検索対象文字列の識別子を前記第２のデータ格納部に格納し、前記整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する第２の検索部と、
前記第２の検索部に対して、前記第２の所定文字数から１まで前記第２の所定文字数から１までのうち整数Ｍについての検索指示を、前記第２の検索部により前記整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き出力する制御部と、
を有する検索装置。
【００８０】
（付記２）
前記第２の検索用データが前記検索対象文字列の末尾文字の種類毎にグループ化されており、
前記第２の検索部が、前記検索文字列の末尾文字と一致する末尾文字の種類のグループに属する前記第２の検索用データに対して前方一致検索を実施する
付記１記載の検索装置。
【００８１】
（付記３）
前記制御部が、
前記第２の検索部に対して、前記第２の所定文字数を前記整数Ｍとして検索指示を出力し、
前記第２の検索部により前記整数Ｍ−２文字一致した反転文字列が存在すると判断された場合には、前記整数Ｍ−１を新たな整数Ｍとして検索指示を前記第２の検索部に出力し、
前記第２の検索部により前記整数Ｍ−２文字一致した反転文字列が存在しないと判断された場合には、前記整数Ｍ−２を新たな整数Ｍとして検索指示を前記第２の検索部に出力する
付記１又は２記載の検索装置。
【００８２】
（付記４）
１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列を生成し、当該反転文字列をソートして前記第２の検索用データを生成する検索用データ生成部
をさらに有する付記１乃至３のいずれか１つ記載の検索装置。
【００８３】
（付記５）
前記検索対象文字列の末尾文字の種類毎に前記検索対象文字列をグループ化し、当該グループの各々について、１以上第１の所定文字数以下の整数Ｎの各々について当該グループに属する各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列を生成し、当該反転文字列をソートして前記第２の検索用データを生成する検索用データ生成部
をさらに有する付記２記載の検索装置。
【００８４】
（付記６）
検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部に格納されている前記第１の検索用データに対して検索文字列の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された前記検索対象文字列の識別子を第２のデータ格納部に格納するステップと、
前記第２の所定文字数から１まで前記第２の所定文字数から１までのうち整数Ｍについての検索処理を、当該検索処理において前記整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き実施するステップと、
を含み、
前記検索処理が、
前記検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、前記第１のデータ格納部に格納されている前記整数Ｍについての前記第２の検索用データに対して行って、前記第２の所定文字数以上前方一致する反転文字列を検出し、検出された前記反転文字列に対応する前記検索対象文字列の識別子を前記第２のデータ格納部に格納し、前記整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する処理
であり、コンピュータにより実行される検索処理方法。
【００８５】
（付記７）
検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部に格納されている前記第１の検索用データに対して検索文字列の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された前記検索対象文字列の識別子を第２のデータ格納部に格納するステップと、
前記第２の所定文字数から１まで前記第２の所定文字数から１までのうち整数Ｍについての検索処理を、当該検索処理において前記整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き実施するステップと、
をコンピュータに実行させ、
前記検索処理が、
前記検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、前記第１のデータ格納部に格納されている前記整数Ｍについての前記第２の検索用データに対して行って、前記第２の所定文字数以上前方一致する反転文字列を検出し、検出された前記反転文字列に対応する前記検索対象文字列の識別子を前記第２のデータ格納部に格納し、前記整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する処理
である検索処理プログラム。
【符号の説明】
【００８６】
１０００ 検索装置
３０００ 検索対象文字列格納部
１１００ 検索用データ生成部
１２００ 検索用データ格納部
１３００ 検索処理部
１４００ 検索結果格納部
１５００ 出力部
【特許請求の範囲】
【請求項１】
検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部と、
前記第１のデータ格納部に格納されている前記第１の検索用データに対して検索文字列の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された前記検索対象文字列の識別子を第２のデータ格納部に格納する第１の検索部と、
前記検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、前記第１のデータ格納部に格納されている前記整数Ｍについての前記第２の検索用データに対して行って、前記第２の所定文字数以上前方一致する反転文字列を検出し、検出された前記反転文字列に対応する前記検索対象文字列の識別子を前記第２のデータ格納部に格納し、前記整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する第２の検索部と、
前記第２の検索部に対して、前記第２の所定文字数から１まで前記第２の所定文字数から１までのうち整数Ｍについての検索指示を、前記第２の検索部により前記整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き出力する制御部と、
を有する検索装置。
【請求項２】
前記第２の検索用データが前記検索対象文字列の末尾文字の種類毎にグループ化されており、
前記第２の検索部が、前記検索文字列の末尾文字と一致する末尾文字の種類のグループに属する前記第２の検索用データに対して前方一致検索を実施する
請求項１記載の検索装置。
【請求項３】
１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列を生成し、当該反転文字列をソートして前記第２の検索用データを生成する検索用データ生成部
をさらに有する請求項１又は２記載の検索装置。
【請求項４】
前記検索対象文字列の末尾文字の種類毎に前記検索対象文字列をグループ化し、当該グループの各々について、１以上第１の所定文字数以下の整数Ｎの各々について当該グループに属する各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列を生成し、当該反転文字列をソートして前記第２の検索用データを生成する検索用データ生成部
をさらに有する請求項２記載の検索装置。
【請求項５】
検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部に格納されている前記第１の検索用データに対して検索文字列の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された前記検索対象文字列の識別子を第２のデータ格納部に格納するステップと、
前記第２の所定文字数から１まで前記第２の所定文字数から１までのうち整数Ｍについての検索処理を、当該検索処理において前記整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き実施するステップと、
を含み、
前記検索処理が、
前記検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、前記第１のデータ格納部に格納されている前記整数Ｍについての前記第２の検索用データに対して行って、前記第２の所定文字数以上前方一致する反転文字列を検出し、検出された前記反転文字列に対応する前記検索対象文字列の識別子を前記第２のデータ格納部に格納し、前記整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する処理
であり、コンピュータにより実行される検索処理方法。
【請求項６】
検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部に格納されている前記第１の検索用データに対して検索文字列の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された前記検索対象文字列の識別子を第２のデータ格納部に格納するステップと、
前記第２の所定文字数から１まで前記第２の所定文字数から１までのうち整数Ｍについての検索処理を、当該検索処理において前記整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き実施するステップと、
をコンピュータに実行させ、
前記検索処理が、
前記検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、前記第１のデータ格納部に格納されている前記整数Ｍについての前記第２の検索用データに対して行って、前記第２の所定文字数以上前方一致する反転文字列を検出し、検出された前記反転文字列に対応する前記検索対象文字列の識別子を前記第２のデータ格納部に格納し、前記整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する処理
である検索処理プログラム。
【請求項１】
検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部と、
前記第１のデータ格納部に格納されている前記第１の検索用データに対して検索文字列の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された前記検索対象文字列の識別子を第２のデータ格納部に格納する第１の検索部と、
前記検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、前記第１のデータ格納部に格納されている前記整数Ｍについての前記第２の検索用データに対して行って、前記第２の所定文字数以上前方一致する反転文字列を検出し、検出された前記反転文字列に対応する前記検索対象文字列の識別子を前記第２のデータ格納部に格納し、前記整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する第２の検索部と、
前記第２の検索部に対して、前記第２の所定文字数から１まで前記第２の所定文字数から１までのうち整数Ｍについての検索指示を、前記第２の検索部により前記整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き出力する制御部と、
を有する検索装置。
【請求項２】
前記第２の検索用データが前記検索対象文字列の末尾文字の種類毎にグループ化されており、
前記第２の検索部が、前記検索文字列の末尾文字と一致する末尾文字の種類のグループに属する前記第２の検索用データに対して前方一致検索を実施する
請求項１記載の検索装置。
【請求項３】
１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列を生成し、当該反転文字列をソートして前記第２の検索用データを生成する検索用データ生成部
をさらに有する請求項１又は２記載の検索装置。
【請求項４】
前記検索対象文字列の末尾文字の種類毎に前記検索対象文字列をグループ化し、当該グループの各々について、１以上第１の所定文字数以下の整数Ｎの各々について当該グループに属する各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列を生成し、当該反転文字列をソートして前記第２の検索用データを生成する検索用データ生成部
をさらに有する請求項２記載の検索装置。
【請求項５】
検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部に格納されている前記第１の検索用データに対して検索文字列の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された前記検索対象文字列の識別子を第２のデータ格納部に格納するステップと、
前記第２の所定文字数から１まで前記第２の所定文字数から１までのうち整数Ｍについての検索処理を、当該検索処理において前記整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き実施するステップと、
を含み、
前記検索処理が、
前記検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、前記第１のデータ格納部に格納されている前記整数Ｍについての前記第２の検索用データに対して行って、前記第２の所定文字数以上前方一致する反転文字列を検出し、検出された前記反転文字列に対応する前記検索対象文字列の識別子を前記第２のデータ格納部に格納し、前記整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する処理
であり、コンピュータにより実行される検索処理方法。
【請求項６】
検索対象文字列の第１の検索用データと、１以上第１の所定文字数以下の整数Ｎの各々について各前記検索対象文字列におけるＮ文字以降の文字の順番を入れ替えた反転文字列についての第２の検索用データとを格納する第１のデータ格納部に格納されている前記第１の検索用データに対して検索文字列の前方一致検索を行って、第２の所定文字数以上前方一致する検索対象文字列を検出し、検出された前記検索対象文字列の識別子を第２のデータ格納部に格納するステップと、
前記第２の所定文字数から１まで前記第２の所定文字数から１までのうち整数Ｍについての検索処理を、当該検索処理において前記整数Ｍ−２文字一致した反転文字列が存在しないと判断された直後を除き実施するステップと、
をコンピュータに実行させ、
前記検索処理が、
前記検索文字列における整数Ｍ文字以降の文字の順番を入れ替えた検索キーの前方一致検索を、前記第１のデータ格納部に格納されている前記整数Ｍについての前記第２の検索用データに対して行って、前記第２の所定文字数以上前方一致する反転文字列を検出し、検出された前記反転文字列に対応する前記検索対象文字列の識別子を前記第２のデータ格納部に格納し、前記整数Ｍ−２文字一致した反転文字列が存在するか否かを判断する処理
である検索処理プログラム。
【図１】
【図２】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図３Ｄ】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０Ａ】
【図１０Ｂ】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図３Ｄ】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０Ａ】
【図１０Ｂ】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【公開番号】特開２０１２−１９０３７９（Ｐ２０１２−１９０３７９Ａ）
【公開日】平成２４年１０月４日（２０１２．１０．４）
【国際特許分類】
【出願番号】特願２０１１−５５０１９（Ｐ２０１１−５５０１９）
【出願日】平成２３年３月１４日（２０１１．３．１４）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年１０月４日（２０１２．１０．４）
【国際特許分類】
【出願日】平成２３年３月１４日（２０１１．３．１４）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]