(57)【要約】【課題】連続一致長を考慮したシーケンスの類似度算出を可能にする。【解決手段】本情報処理方法は、（Ａ）第１のシーケンスに含まれる複数のエレメントの各々と、第２のシーケンスに含まれる複数のエレメントの各々とを比較して、一致するエレメントの第１の部分及び連続一致するエレメントの第２の部分を特定し、（Ｂ）特定された第１の部分及び第２の部分の各々について、当該部分の長さに応じたスコアを設定し、（Ｃ）当該スコアに基づき、第１のシーケンスと第２のシーケンスとの類似度を算出する処理を含む。【選択図】図１
2015158744.tif 000002
【特許請求の範囲】
【請求項１】
第１のシーケンスに含まれる複数のエレメントの各々と、第２のシーケンスに含まれる複数のエレメントの各々とを比較して、一致するエレメントの第１の部分及び連続一致するエレメントの第２の部分を特定し、
特定された前記第１の部分及び前記第２の部分の各々について、当該部分の長さに応じたスコアを設定し、
当該スコアに基づき、前記第１のシーケンスと前記第２のシーケンスとの類似度を算出する
処理を、コンピュータに実行させるためのプログラム。
【請求項２】
前記第１のシーケンスの前記複数のエレメントの各々に応じた第１の方向の辺と前記第２のシーケンスの前記複数のエレメントの各々に応じた第２の方向の辺とを有する格子状の有向グラフを生成し、
特定された前記第１の部分に対応する辺を前記有向グラフにおいて前記第１の部分に対応する格子要素内に追加し、
特定された前記第２の部分に対応する短絡辺を前記有向グラフにおいて前記第２の部分に対応する部分に追加する
処理をさらに前記コンピュータに実行させ、
前記スコアを設定する処理において、
追加された前記辺及び前記短絡辺に、当該辺又は短絡辺の長さに応じたスコアを設定し、
前記類似度を算出する処理が、
前記有向グラフにおける最大スコア経路を決定する
処理を含む請求項１記載のプログラム。
【請求項３】
前記第１のエレメントの各々に応じた第１の方向の辺と前記第２のエレメントの各々に応じた第２の方向の辺とを有する格子状の有向グラフを生成し、
特定された前記第１の部分に対応する辺を前記有向グラフの前記第１の部分に対応する格子要素内に追加する
処理をさらに前記コンピュータに実行させ、
前記スコアを設定する処理において、
特定された前記第２の部分に含まれる前記第１の部分に対応する各辺に、特定された前記第２の部分の長さに応じたスコアを設定し、
特定された前記第２の部分に含まれない前記第１の部分に対応する各辺に、当該第１の部分の長さに応じたスコアを設定し、
前記類似度を算出する処理が、
前記有向グラフにおける最大スコア経路を決定する
処理を含む請求項１記載のプログラム。
【請求項４】
前記短絡辺を前記有向グラフに追加する処理において、
特定された前記第２の部分のうち所定の条件を満たす第２の部分について、前記短絡辺を前記有向グラフに追加する
請求項２記載のプログラム。
【請求項５】
前記所定の条件が、連続一致するエレメントの数についての条件である
請求項４記載のプログラム。
【請求項６】
前記有向グラフの格子において、第１の短絡辺が通過する第１の格子要素の前記第１の方向及び前記第２の方向のいずれかに、第２の短絡辺が通過する第２の格子要素が存在するか判断し、
前記第２の格子要素が存在していない場合、前記第１の短絡辺に対応する前記第２の部分に含まれる第１の部分に対応する辺及び前記第１の短絡辺に対応する前記第２の部分に含まれる他の第２の部分に対応する短絡辺を削除する
処理をさらに前記コンピュータに実行させるための請求項２記載のプログラム。
【請求項７】
前記第１のシーケンスと前記第２のシーケンスとのうち少なくともいずれかにおいて同一エレメントが連続する部分が存在し且つ当該同一エレメントが少なくとも１つ前記第１のシーケンス及び前記第２のシーケンスに含まれるという条件を満たす場合、前記有向グラフにおいて前記同一エレメントが連続する部分に対応する格子要素の領域を特定し、
前記有向グラフの格子において、特定された前記領域の前記第１の方向及び前記第２の方向のいずれかに、他の短絡辺が通過する第２の格子要素が存在するか判断し、
前記第２の格子要素が存在していないと判断された場合、前記領域内の辺を削除し、前記領域において前記有向グラフの開始点に最も近い頂点から終了点に最も近い頂点へ結ぶ短絡辺を追加する
処理をさらに前記コンピュータに実行させるための請求項２又は６記載のプログラム。
【請求項８】
前記第２の格子要素が存在すると判断された場合、前記領域内部の辺を削除し、
前記領域の辺のうち前記有向グラフにおける開始点側の辺に含まれる頂点から、前記領域の辺のうち前記有向グラフにおける終了点側の辺に含まれる頂点へ短絡辺を追加する
処理をさらに前記コンピュータに実行させるための請求項７記載のプログラム。
【請求項９】
前記有向グラフの格子において前記第１の方向に並ぶ格子要素のいずれかに存在する短絡辺の数を、前記第２の方向に並ぶ各格子要素について計数し、
前記有向グラフの格子において前記第２の方向に並ぶ格子要素のいずれかに存在する短絡辺の数を、前記第１の方向に並ぶ各格子要素について計数する
処理をさらに前記コンピュータに実行させるための請求項６乃至８のいずれか１つ記載のプログラム。
【請求項１０】
前記有向グラフの格子において前記第１の方向に並ぶ格子要素のいずれかに短絡辺が存在するか否かを、前記第２の方向に並ぶ各格子要素について判定し、
前記有向グラフの格子において前記第２の方向に並ぶ格子要素のいずれかに短絡辺が存在するか否かを、前記第１の方向に並ぶ各格子要素について判定する
処理をさらに前記コンピュータに実行させるための請求項９記載のプログラム。
【請求項１１】
第１のシーケンスに含まれる複数のエレメントの各々と、第２のシーケンスに含まれる複数のエレメントの各々とを比較して、一致するエレメントの第１の部分及び連続一致するエレメントの第２の部分を特定し、
特定された前記第１の部分及び前記第２の部分の各々について、当該部分の長さに応じたスコアを設定し、
当該スコアに基づき、前記第１のシーケンスと前記第２のシーケンスとの類似度を算出する
処理を含み、コンピュータにより実行される情報処理方法。
【請求項１２】
第１のシーケンスに含まれる複数のエレメントの各々と、第２のシーケンスに含まれる複数のエレメントの各々とを比較して、一致するエレメントの第１の部分及び連続一致するエレメントの第２の部分を特定する特定部と、
特定された前記第１の部分及び前記第２の部分の各々について、当該部分の長さに応じたスコアを設定する設定部と、
当該スコアに基づき、前記第１のシーケンスと前記第２のシーケンスとの類似度を算出する算出部と、
を有する情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、各々複数のエレメントを含むシーケンスの類似度算出技術に関する。
【背景技術】
【０００２】
シーケンスは、例えば文字を要素とする列である文字列の他、数値データの列、バイトデータの列、単語の列などを含む。以下、説明を分かりやすくするために、文字列について説明する。
【０００３】
文字列は、今日広く使われるデータ形式である。単語や文書、設定情報やプログラムソースコードなどの人間が読み書きするデータはもちろん、人間による読み書きを想定しないデータ（たとえば実験データや通信プロトコルのメタデータなど）もしばしば文字列として表現される。したがって、文字列を効率良く処理することは重要である。そうした文字列処理の基本的な命題のひとつに文字列同士の比較がある。
【０００４】
本願で検討する文字列の比較とは、単に２つの文字列が同じかどうかだけでなく、２つの文字列がどの程度似ているかを調べることを指す。このとき似ている度合を類似度と呼ぶことにする。何をもって類似している、または類似していないとみなすかは比較の目的にも依るが、基本的には共通の文字が共通の位置や順序で並んでいるほど似ているとみなし、文字が異なるか同じ文字でも位置や順序が異なっているほど似ていないとみなす方式が一般的である。このほか、文字の意味、あるいは英語や日本語などの自然言語の特性を取り入れ、文字の意味の近さ、発音の類似性、語形や発音の変化、語の意味の類似性、人間が筆記またはタイプした際の誤り易さなどを考慮する比較方法もある。しかしながら、本願ではこうした意味や自然言語特性を考慮せず、文字の一致と並び方だけを考慮した比較方法を考えるものとする。
【０００５】
このような文字列の類似度として良く知られているのが、最長共通部分系列（Longest Common Sequence、以下ＬＣＳと略記する）の長さである。ＬＣＳとは、比較対象の文字列Ｓ及び文字列Ｔについて、ＳとＴに共通に含まれる文字の列であって、順序を変えずに並べることのできる最長のものを指す。ＬＣＳは部分系列であって部分文字列ではないので、ＬＣＳに含まれる文字は必ずしも元の文字列内で連続していなくても構わない点に注意を要する。
【０００６】
たとえば、”ａｂｃ”と”ｂａｃ”のＬＣＳは”ａｃ”と”ｂｃ”であり、その長さは２である。”ａｂ”と”ｂａ”はどちらも共通に含まれる文字のみから成るが、文字の順序を入れ替えなければ一致しないので、ＬＣＳではない。一組の比較対象文字列に対し、ＬＣＳは複数あり得るが、ＬＣＳ長は一意に決めることができ、このＬＣＳ長を類似の度合とみなすものである。
【０００７】
なお、Levenshteinの編集距離と呼ばれる指標は、類似の度合ではなく相違の度合を測るものだが、実質的にはＬＣＳに含まれない文字を数えることに相当し、尺度として反転しているものの本質的にはＬＣＳ長と同等の意味をもつ。
【０００８】
ＬＣＳ長については、これを求めるための比較的効率の良い手法が知られている（例えば以下の文献を参照のこと。David Maier. “The Complexity of Some Problems on Subsequences and Supersequences”, J. ACM, Vol. 25, No. 2, pp. 322-336. 1978.）。この手法の基本的な手順は次のようなものである。
【０００９】
ステップ１：格子状の有向グラフを作成する。この手順は次のステップを含む。
ステップ１．１：比較対象の文字列をそれぞれ縦軸と横軸に対応させ、各文字の位置に縦（下向き）または横（右向き）の辺を設けた格子状の有向グラフを用意する。この縦及び横の辺にはすべてスコア０を与える。
ステップ１．２：異なる文字列の各文字同士を比較し、同じ文字であれば格子要素を斜めに（右下へ）横切る辺を設ける。この辺にはスコア１を与える。
ステップ２：グラフの左上の頂点から右下の頂点までたどり着く経路であり、且つその経路上のスコアの合計が最大になるものを少なくとも１つ見つける。このときその最大となる合計スコアがＬＣＳ長である。
【００１０】
ＬＣＳ長は、比較的効率良く求めることができ、２つの文字列の間の類似度スコアとして用いるには適している。しかし、連続一致部分の長さが考慮されないという問題がある。
【００１１】
ＬＣＳ長は、一致する文字が連続しているかどうかを考慮しないため、連続して一致している部分がより長い文字列同士をより似たものと判断することができない。たとえば、”ａｂｃｄｅｆ”との比較において、”ａｂｃｘｙｚ”と”ａｘｂｙｃｚ”では、ＬＣＳはどちらも”ａｂｃ”で、ＬＣＳ長は同じ３だが、”ａｂｃ”が連続して一致している前者のほうがより似ているとみなした方が都合の良い場合が多い。ＬＣＳ長はこうした場合に適した類似度指標とはいえない。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２００７−３１０７４６号公報
【特許文献２】特開平８−１６１３５７号公報
【非特許文献】
【００１３】
【非特許文献１】David Maier. “The Complexity of Some Problems on Subsequences and Supersequences”, J. ACM, Vol. 25, No. 2, pp. 322-336. 1978.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
従って、本発明の目的は、一側面によれば、連続一致長を考慮したシーケンスの類似度算出を可能にするための技術を提供することである。
【課題を解決するための手段】
【００１５】
本情報処理方法は、（Ａ）第１のシーケンスに含まれる複数のエレメントの各々と、第２のシーケンスに含まれる複数のエレメントの各々とを比較して、一致するエレメントの第１の部分及び連続一致するエレメントの第２の部分を特定し、（Ｂ）特定された第１の部分及び第２の部分の各々について、当該部分の長さに応じたスコアを設定し、（Ｃ）当該スコアに基づき、第１のシーケンスと第２のシーケンスとの類似度を算出する処理を含む。
【発明の効果】
【００１６】
一側面によれば、連続一致長を考慮したシーケンスの類似度算出が可能となる。
【図面の簡単な説明】
【００１７】
【図１】図１は、第１の実施の形態に係る情報処理装置の機能ブロック図である。
【図２】図２は、第１の実施の形態に係るメインの処理フローを示す図である。
【図３】図３は、グラフ生成処理の処理フローを示す図である。
【図４】図４は、初期グラフの生成処理の処理フローを示す図である。
【図５】図５は、初期的な有向グラフの一例を示す図である。
【図６】図６は、一致文字に基づく辺の追加処理の処理フローを示す図である。
【図７】図７は、有向グラフの第２の状態を示す図である。
【図８】図８は、連続一致文字に基づく短絡辺の追加処理の処理フローを示す図である。
【図９】図９は、有向グラフの第３の状態を示す図である。
【図１０】図１０は、有向グラフの第４の状態を示す図である。
【図１１】図１１は、第２の実施の形態に係るグラフ生成処理の処理フローを示す図である。
【図１２】図１２は、斜め辺スコア調整処理の処理フローを示す図である。
【図１３】図１３は、第２の実施の形態を説明するための図である。
【図１４】図１４は、第１の実施の形態の例を示す図である。
【図１５】図１５は、第２の実施の形態を説明するための図である。
【図１６】図１６は、短絡辺の干渉を説明するための図である。
【図１７Ａ】図１７Ａは、短絡辺の干渉を説明するための図である。
【図１７Ｂ】図１７Ｂは、短絡辺の干渉を説明するための図である。
【図１７Ｃ】図１７Ｃは、短絡辺の干渉を説明するための図である。
【図１８】図１８は、第４の実施の形態に係る情報処理装置の機能ブロック図である。
【図１９】図１９は、第４の実施の形態に係るグラフ生成処理の処理フローを示す図である。
【図２０】図２０は、短絡辺の削除処理の処理フローを示す図である。
【図２１】図２１は、グラフ変形処理を説明するための図である。
【図２２】図２２は、グラフ変形処理を説明するための図である。
【図２３】図２３は、グラフ変形処理を説明するための図である。
【図２４】図２４は、グラフ変形処理の処理フローを示す図である。
【図２５】図２５は、矩形領域取得処理の処理フローを示す図である。
【図２６】図２６は、矩形領域内処理の処理フローを示す図である。
【図２７】図２７は、干渉なしの場合の変更処理の処理フローを示す図である。
【図２８】図２８は、干渉ありの場合の変更処理の処理フローを示す図である。
【図２９】図２９は、干渉ありの場合の変更処理の処理フローを示す図である。
【図３０】図３０は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１８】
［実施の形態１］
本実施の形態に係る情報処理装置１００の構成例を図１に示す。情報処理装置１００は、入力データ格納部１０１と、グラフ生成部１０２と、第１データ格納部１０３と、探索部１０４と、第２データ格納部１０５と、類似度算出部１０６と、出力データ格納部１０７とを有する。
【００１９】
入力データ格納部１０１は、比較対象の文字列のデータを格納する。
【００２０】
グラフ生成部１０２は、初期グラフ生成部１０２１と、辺追加部１０２２と、スコア調整部１０２３とを有する。初期グラフ生成部１０２１は、比較対象の文字列に応じて、初期的な格子状の有向フラグを生成する。辺追加部１０２２は、初期的な有向グラフに対して、比較対象の文字列のうち一致する文字又は文字列について辺を追加する処理を実行する。スコア調整部１０２３は、有向グラフの辺に設定されているスコアを、一致する文字又は文字列の長さに応じたスコアに調整し、スコアが設定された有向グラフのデータを第１データ格納部１０３に格納する。
【００２１】
探索部１０４は、第１データ格納部１０３に格納されている有向グラフのデータを用いて、有向グラフにおいて最大スコア経路を決定し、当該最大スコア経路のデータを第２データ格納部１０５に格納する。
【００２２】
類似度算出部１０６は、第２データ格納部１０５に格納されているデータから、比較対象の文字列の類似度を算出し、出力データ格納部１０７に格納する。
【００２３】
なお、本実施の形態では、一例として、「ｓｉｔｔｉｎｇ」と「ｋｉｔｔｅｎ」とを比較する場合を一例として説明する。
【００２４】
次に、図２乃至図１０を用いて、情報処理装置１００の処理内容を説明する。
【００２５】
まず、グラフ生成部１０２は、グラフ生成処理を実行し、生成されたスコア付き有向グラフのデータを、第１データ格納部１０３に格納する（図２：ステップＳ１）。本実施の形態に係るグラフ生成処理については図３乃至図１０を用いて説明する。
【００２６】
次に、探索部１０４は、最大スコア経路の探索処理を実行し、処理結果を第２データ格納部１０５に格納する（ステップＳ３）。
【００２７】
本実施の形態では、この処理は、スコア付きの有向グラフＧ＝（Ｖ，Ｅ，ｗ）に対して、その開始点ｖ（１，１）から終了点ｖ（ｍ＋１，ｎ＋１）までの経路のうちスコア合計値が最大となる経路（最大スコア経路）及びそのスコア合計値を決定するものである。このステップは、以下のいずれかの方法を用いることで、効率良く実施できる。なお、ｗは辺の集合Ｅに属する任意の辺ｅに対するスコアｗ（ｅ）を表す。なお、頂点の集合はＶである。
【００２８】
（Ａ）スコアをコストに反転したグラフＧ’＝（Ｖ，Ｅ，ｃ）（但し、ｃ（ｅ）＝−ｗ（ｅ）。）に対して最小コスト経路探索を行う。これはベルマン・フォードのアルゴリズムなどよく知られた方法で求めることができる。ｗｍａｘは最小の合計コストｃｍｉｎからｗｍａｘ＝−ｃｍｉｎと求められる。
（Ｂ）動的計画法により最大スコアを求める。有向グラフＧの辺は右、下、又は右下を向いており（すなわち半順序性をもち）、またすべての頂点へ到達可能な頂点及びすべての頂点から到達可能な頂点がそれぞれ開始点と終了点のみに限られることから、Ｇは束である。開始点からある任意の頂点までの最大スコアは、その頂点に達する高々２＋ｎ個の辺のスコアとそれらの始点までの最大スコア（すなわち副問題の解）のみから求められる。しかし、有向グラフＧは束であるから副問題間の依存関係が閉路を形成することはなく、ゆえに高々（ｍ＋１）×（ｎ＋１）個の頂点について１度ずつ漸次的に副問題を解けば最終的に終了点までの最大スコアを求めることができる。したがって、動的計画法を用いて問題を解くことができる。
【００２９】
これらの最小コスト経路探索や動的計画法については、従来技術としてよく知られているので、ここでは詳細な説明を省略する。
【００３０】
さらに、類似度算出部１０６は、第２データ格納部１０５に格納されている最大スコアを用いて類似度算出処理を実行し、算出された類似度のデータを出力データ格納部１０７に格納する（ステップＳ５）。
【００３１】
類似度ｒは、一般的にはｗｍａｘを文字列の長さに応じて正規化したものであることが望まれている。例えば、ｒ＝ｗｍａｘ／ａｖｇ（ｍ，ｎ）とする。ここでａｖｇ（ｍ，ｎ）は、第１の文字列（ｓｉｔｔｉｎｇ）の長さｍと第２の文字列（ｋｉｔｔｅｎ）の長さｎの相加平均（ｍ＋ｎ）／２とする。これにより、類似度ｒは０から１までの実数値になり、１文字も一致しなければ０、文字列が完全に同じであれば１となる。このステップについても、従来と同様であって、このほかの手法を採用しても良く、これ以上述べない。
【００３２】
このようにグラフ生成処理を適切に実行することで、２つの文字列の類似度ｒを、連続一致長を加味した上で算出できるようになる。
【００３３】
次に、図３乃至図１０を用いて本実施の形態に係るグラフ生成処理について詳細に述べる。
【００３４】
まず、初期グラフ生成部１０２１は、初期グラフの生成処理を実行する（図３：ステップＳ１１）。初期グラフの生成処理については、図４及び図５を用いて説明する。
【００３５】
まず、初期グラフ生成部１０２１は、空のグラフＧ＝（Ｖ，Ｅ，ｗ）を生成する（図４：ステップＳ２１）。Ｖは頂点集合を表し、Ｅは辺集合を表し、ｗはスコアを表す。
【００３６】
そして、初期グラフ生成部１０２１は、（ｍ＋１）×（ｎ＋１）個の頂点ｖ（ｉ，ｊ）をＶに追加する（ステップＳ２３）。ここでｉは１以上ｍ＋１以下の整数であり、ｊは１以上ｎ＋１以下の整数である。
【００３７】
また、初期グラフ生成部１０２１は、変数ｉを１に初期化し（ステップＳ２５）、変数ｊを１に初期化する（ステップＳ２７）。
【００３８】
そして、初期グラフ生成部１０２１は、ｖ（ｉ，ｊ）からｖ（ｉ＋１，ｊ）へ向かう横方向の辺ｅｈ（ｉ，ｊ）をＥに追加し、そのスコアｗ（ｅｈ（ｉ，ｊ））を０に設定する（ステップＳ２９）。
【００３９】
さらに、初期グラフ生成部１０２１は、ｖ（ｉ，ｊ）からｖ（ｉ，ｊ＋１）へ向かう縦方向の辺ｅｖ（ｉ，ｊ）をＥに追加し、そのスコアｗ（ｅｖ（ｉ，ｊ））を０に設定する（ステップＳ３１）。
【００４０】
そして、初期グラフ生成部１０２１は、ｊがｎ＋１より小さいか否かを判断する（ステップＳ３３）。この条件を満たす場合、初期グラフ生成部１０２１は、ｊを１インクリメントし（ステップＳ３５）、処理はステップＳ２９に戻る。
【００４１】
一方、ステップＳ３３の条件を満たさない場合には、初期グラフ生成部１０２１は、ｉがｍ＋１より小さいか否かを判断する（ステップＳ３７）。この条件を満たす場合には、初期グラフ生成部１０２１は、ｉを１インクリメントして（ステップＳ３９）、処理はステップＳ２７に戻る。一方、ステップＳ３７の条件を満たさない場合、処理は呼び出し元の処理に戻る。
【００４２】
図５に初期的な格子状の有向グラフの一例を示す。このように左上端部の頂点を開始点とし、右下端部の頂点を終了点とし、横方向には第１の文字列「ｓｉｔｔｉｎｇ」という７文字に対応する７辺が設けられ、縦方向には第２の文字列「ｋｉｔｔｅｎ」という６文字に対応する６辺が設けられている。すなわち、横方向には７＋１＝８つの頂点が設けられ、縦方向には６＋１＝７つの頂点が設けられている。各辺には左から右、又は上から下への方向が設定されており、この段階で生成された辺のスコアは０となっている。
【００４３】
図３の処理の説明に戻って、辺追加部１０２２は、初期グラフに対する、一致文字に基づく辺の追加処理を実行する（ステップＳ１３）。本追加処理については、図６及び図７を用いて説明する。
【００４４】
まず、辺追加部１０２２は、空の斜め辺集合Ｅｄを生成する（図６：ステップＳ４１）。また、辺追加部１０２２は、変数ｉを１に初期化し（ステップＳ４３）、変数ｊを１に初期化する（ステップＳ４５）。
【００４５】
そして、辺追加部１０２２は、第１の文字列ｓのｉ番目の文字ｓ（ｉ）と第２の文字列ｔのｊ番目の文字ｔ（ｊ）とが同じ文字であるか否かを判断する（ステップＳ４７）。同じ文字ではない場合には、処理はステップＳ５１に移行する。
【００４６】
一方、同じ文字である場合には、辺追加部１０２２は、ｖ（ｉ，ｊ）からｖ（ｉ＋１，ｊ＋１）への辺ｅｄ（ｉ，ｊ）をＥとＥｄに追加し、そのスコアｗ（ｅｄ（ｉ，ｊ））を１に設定する（ステップＳ４９）。
【００４７】
そして、辺追加部１０２２は、ｊがｎ＋１より小さいか否かを判断する（ステップＳ５１）。ｊがｎ＋１より小さい場合には、辺追加部１０２２は、ｊを１インクリメントして（ステップＳ５３）、処理はステップＳ４７に戻る。
【００４８】
一方、ｊがｎ＋１以上である場合には、辺追加部１０２２は、ｉがｍ＋１より小さいか否かを判断する（ステップＳ５５）。ｉがｍ＋１より小さい場合には、辺追加部１０２２は、ｉを１インクリメントして（ステップＳ５７）、処理はステップＳ４５に戻る。一方、ｉがｍ＋１以上となった場合には、処理は呼び出し元の処理に戻る。
【００４９】
このような処理を実行すれば、例えば図７に示すような有向グラフが得られる。図７は、図５に対して図６の処理を行った後の状態を表しており、第１の文字列の文字と第２の文字列の文字とが一致する部分、例えば文字「ｉ」「ｔ」「ｎ」に対応する格子要素（枡目とも呼ぶ）に斜め辺が追加され、この斜め辺のスコアは「１」となっている。この段階では、連続一致については考慮されていない。
【００５０】
図３の処理の説明に戻って、辺追加部１０２２は、連続一致文字に基づく短絡辺の追加処理を実行する（ステップＳ１５）。この追加処理については、図８及び図９を用いて説明する。
【００５１】
まず、辺追加部１０２２は、空の短絡辺集合Ｅｓを生成する（図８：ステップＳ６１）。また、辺追加部１０２２は、変数ｉを１に初期化し（ステップＳ６３）、変数ｊを１に初期化する（ステップＳ６５）。
【００５２】
その後、辺追加部１０２２は、斜め辺集合Ｅｄに斜め辺ｅｄ（ｉ，ｊ）が含まれているか判断する（ステップＳ６７）。この条件を満たさない場合には、処理はステップＳ７７に移行する。
【００５３】
一方、ステップＳ６７の条件を満たす場合には、辺追加部１０２２は、連続一致文字のカウンタｋを１に初期化する（ステップＳ４９）。そして、辺追加部１０２２は、斜め辺集合Ｅｄに斜め辺ｅｄ（ｉ＋ｋ，ｊ＋ｋ）が含まれているか判断する（ステップＳ７１）。すなわち、１つの斜め辺の先にさらなる斜め辺が形成されているか判断する。ステップＳ７１の条件を満たさない場合には、処理はステップＳ７７へ移行する。
【００５４】
一方、ステップＳ７１の条件を満たす場合には、辺追加部１０２２は、ｖ（ｉ，ｊ）からｖ（ｉ＋ｋ，ｊ＋ｋ）への短絡辺ｅｓ（ｉ，ｊ，ｋ）を辺集合Ｅと短絡辺集合Ｅｓに追加し、そのスコアｗ（ｅｓ（ｉ，ｊ，ｋ））をｋ＋１に設定する（ステップＳ７３）。そして、辺追加部１０２２は、ｋを１インクリメントして（ステップＳ７５）、処理はステップＳ７１へ戻る。
【００５５】
例えば、ｋ＝１の場合に、さらなる斜め辺が検出されると、２本の斜め辺が連続して検出されたことになるので、その長さに応じたスコア「２」（＝ｋ＋１＝１＋１）が設定された短絡辺が生成される。
【００５６】
また、ｋ＝２の場合に、さらなる斜め辺が検出されると、３本の斜め辺が連続して検出されたことになるので、その長さに応じたスコア「３」（＝ｋ＋１＝２＋１）が設定された短絡辺が生成される。
【００５７】
そして、ステップＳ６７又はＳ７１で条件を満たさないと判断された場合、辺追加部１０２２は、ｊがｎ＋１より小さいか否かを判断する（ステップＳ７７）。この条件を満たす場合には、辺追加部１０２２は、ｊを１インクリメントして（ステップＳ７９）、処理はステップＳ６７に移行する。
【００５８】
一方、ステップＳ７７の条件を満たさない場合には、辺追加部１０２２は、ｉがｍ＋１より小さいか否かを判断する（ステップＳ８１）。ｉがｍ＋１より小さい場合には、辺追加部１０２２は、ｉを１インクリメントして（ステップＳ８３）、処理はステップＳ６５に移行する。一方、ステップＳ８１の条件を満たさない場合には、処理は呼び出し元の処理に戻る。
【００５９】
以上の処理を実行することで、例えば図９に示すような有向グラフが生成される。なお、図９以降は、縦及び横の辺については矢印を省略している。図９は、図７に対して図８の処理を行った後の状態を表しており、「ｉｔｔ」という３つの連続一致部分について、短絡辺が追加されている。この場合、最も長い「ｉｔｔ」に対応する短絡辺だけではなく、「ｉｔ」に対応する短絡辺及び「ｔｔ」に対応する短絡辺も追加される。この状態では、３文字連続一致であれば「３」、２文字連続一致であれば「２」というスコアが設定される。
【００６０】
図３の処理の説明に戻って、スコア調整部１０２３は、斜め辺集合Ｅｄ及び短絡辺集合Ｅｓに含まれる各辺ｅについて、スコアを更新する処理を実行し、処理結果を第１データ格納部１０３に格納する（ステップＳ１７）。本ステップでは、長さが短いほどより小さくなるようにスコアを更新する。
【００６１】
ここでは、連続一致長ｄに対するスコアの関数ｗｌｅｎ（ｄ）を導入し、ｗｎｅｗ（ｅ）＝ｗｌｅｎ（ｌｅｎ（ｅ））をｗ（ｅ）の新しい値に設定する。なお、ｌｅｎ（ｅ）は辺ｅの斜め方向の長さである。ｗｌｅｎ（ｄ）は、例えば重み関数ｆ（ｄ）を用いて、ｗｌｅｎ（ｄ）＝ｄ×ｆ（ｄ）と定義される。なお、ｆ（ｄ）は０乃至１の範囲の実数値を出力する関数であり、長さｄが短いほど小さい値を返す関数とする。例えば、ｆ（ｄ）＝ａ＋（１−ａ）×ｄ／ｎと定義できる。ここで、ａは０より大きく１未満の実数で、ａ＝０．５とする。そうすると、例えばｎ＝６の時、ｗｌｅｎ（ｄ）の値は、ｄ＝６であれば６、ｄ＝５であれば４．５８３、ｄ＝４であれば３．３３３、ｄ＝３のとき２．２５０、ｄ＝２のとき１．３３３、ｄ＝１のとき０．５８３となる。数値は小数点第４位で四捨五入した値となる。
【００６２】
そうすると、図９に示すような有向グラフは、図１０に示すような有向グラフになる。図９ではスコアの値は「１」「２」「３」のいずれかが設定されていたが、図１０では、上で述べた数値に調整されている。
【００６３】
以降、上で述べたように最大スコア探索処理等を行った後、最大スコアから類似度を算出する処理が行われる。
【００６４】
以上のような処理を行えば、連続一致長に応じたスコアが設定された短絡辺により、連続一致を考慮した最大スコア探索等が行われるようになり、結果として連続一致長を考慮した類似度が算出されるようになる。
【００６５】
［実施の形態２］
第１の実施の形態では、短絡辺が追加されるので、探索経路等が多くなり演算量が多くなる場合がある。本実施の形態では、連続一致部分に短絡辺を追加する代わりに、連続一致部分に含まれる斜め辺それぞれのスコアに対しその連続一致部分の長さを反映させた調整を行う。これにより、第１の実施の形態よりも精度が落ちる場合があるものの、より少ない演算量で連続一致長を考慮した類似度が算出されるようになる。
【００６６】
具体的には、図１１乃至図１４を用いて本実施の形態に係る第２のグラフ生成処理を実行する。
【００６７】
まず、初期グラフ生成部１０２１は、初期グラフの生成処理を実行する（図１１：ステップＳ１０１）。この処理は第１の実施の形態と同様であり、詳細な説明については省略する。
【００６８】
次に、辺追加部１０２２は、一致文字に基づく辺の追加処理を実行する（ステップＳ１０３）。この処理も第１の実施の形態と同様であり、詳細な説明については省略する。
【００６９】
その後、「連続一致文字に基づく短絡辺の追加処理」を行うことなく、スコア調整部１０２３は、斜め辺スコア調整処理を実行する（ステップＳ１０５）。この斜め辺スコア調整処理については、図１２乃至図１４を用いて説明する。
【００７０】
まず、スコア調整部１０２３は、空の斜め辺集合Ｅｒを生成し、斜め辺集合Ｅｄの要素を追加する（図１２：ステップＳ１１１）。
【００７１】
また、スコア調整部１０２３は、変数ｉを１に初期化し（ステップＳ１１３）、さらに変数ｊを１に初期化する（ステップＳ１１５）。
【００７２】
そして、スコア調整部１０２３は、斜め辺集合Ｅｒが空になったか判断する（ステップＳ１１７）。斜め辺集合Ｅｒが空になった場合には、処理は呼び出し元の処理に戻る。
【００７３】
一方、斜め辺集合Ｅｒが空ではない場合、斜め辺集合Ｅｒに斜め辺ｅｄ（ｉ，ｊ）が含まれているか否かを判断する（ステップＳ１１９）。斜め辺集合Ｅｒに斜め辺ｅｄ（ｉ，ｊ）が含まれていない場合には、処理はステップＳ１２５に移行する。
【００７４】
一方、斜め辺集合Ｅｒに斜め辺ｅｄ（ｉ，ｊ）が含まれている場合には、スコア調整部１０２３は、斜め辺集合Ｅｒにｅｄ（ｉ＋ｋ，ｊ＋ｋ）が含まれるｋの最大値ｋｍを探索する（ステップＳ１２１）。すなわち、斜め辺の先にさらに斜め辺が存在するか否かを、ｋを１ずつ増加させつつ判断する。すなわち、一致する文字が何個連続するのかを判断するものである。
【００７５】
そして、スコア調整部１０２３は、ｅ＝ｅｄ（ｉ＋ｋ，ｊ＋ｋ）（ｋは０からｋｍまでの整数）の各々をＥｒから除去し、各スコアｗ（ｅ）を最大連続一致長に基づき更新する（ステップＳ１２３）。具体的には、例えばｗ（ｅ）＝ｗｌｅｎ（ｋｍ＋１）／（ｋｍ＋１）というように更新する。Ｅｒから除去されるので、例えば３文字連続一致の場合、１文字目及び２文字目の２文字連続一致と、２文字目及び３文字目の２文字連続一致については、スコア調整は行われない。最も長い連続一致部分のみ、スコアの調整がなされる。
【００７６】
そして、スコア調整部１０２３は、ｊがｎ＋１より小さいか否かを判断する（ステップＳ１２５）。この条件を満たす場合には、スコア調整部１０２３は、ｊを１インクリメントして（ステップＳ１２７）、処理はステップＳ１１７に戻る。
【００７７】
一方、ステップＳ１２５の条件を満たさない場合には、スコア調整部１０２３は、ｉがｍ＋１より小さいか否かを判断する（ステップＳ１２９）。ｉがｍ＋１より小さい場合には、スコア調整部１０２３は、ｉを１インクリメントして（ステップＳ１３１）、処理はステップＳ１１５に戻る。一方、ｉがｍ＋１以上となると、処理は終了する。
【００７８】
例えば、第１の実施の形態の例のように３文字連続一致が存在する場合、図１３に示すように、斜め辺が３つ連続して配置される。各斜め辺にはスコア「１」が設定されている。図１０でも示したが、第１の実施の形態では、図１４に示すように、２文字連続一致についての短絡辺と３文字連続一致についての短絡辺とが追加された上に、１文字一致の斜め辺を含めて、辺の長さに応じたスコアが設定されていた。これに対して、本実施の形態では、図１５に示すように、３文字連続一致でｋｍ＝２となるので、スコアは、ｗｌｅｎ（３）／３＝２．２５０／２＝０．７５と計算されるようになる。図１５でも示すように、３文字連続一致ということを表すスコアを、均等に各斜め辺に配分している。
【００７９】
このような処理を行うことで、短絡辺を追加することなく、各斜め辺に、連続一致する文字の長さに応じたスコアを設定する。連続一致部分が長くなったり、多数存在するような文字列の比較の場合には、その分短絡辺の数が増加して、演算量が増加するが、このように斜め辺のみが追加される場合には、演算量を削減できる。但し、精度については若干下がる場合もある。
【００８０】
［実施の形態３］
第１の実施の形態では、３文字連続一致の場合、３文字連続一致に対応する短絡辺、３文字中の２文字連続一致に対応する２つの短絡辺を追加するような処理を行っていた。このような処理を行うと、長い連続一致部分が存在すると、多数の短絡辺が追加されることになる。
【００８１】
本実施の形態では、演算量削減を目的として、一定の条件を満たす場合にのみ短絡辺を追加するように変形する。
【００８２】
この一定の条件とは、主に連続している一致する文字数に関するもので、その文字数が所定のｘ文字以下なら追加する、ｘ文字以上なら追加する、奇数なら（または偶数なら）追加する、といったものが挙げられる。具体的にはステップＳ７１において、このような条件が満たされた場合にのみ短絡辺を追加する。
【００８３】
また連続一致部分全体の文字数に関して、その文字数が所定のｙ文字以下ならすべての短絡辺を追加するが、ｙ文字を超えたらｙ文字より大きいｚ文字までは追加を省略し、ｚ文字を超えたら短絡辺は追加する、若しくはｙ文字を超えたら各短絡辺をより少ない頻度や確率でしか追加しない、といった方法も採用可能である。
【００８４】
一般に、長い短絡辺のみ追加する方が精度は下がるが計算時間は短くなる可能性が高い。一方、短い短絡辺のみ追加するほうが精度は下がりにくい又はほとんど下がらないが、計算時間はあまり短くならない可能性が高い。そこで、上で述べたようなバリエーションが効果的な場合がある。
【００８５】
［実施の形態４］
また、辺のうち不要なものを削除して、全体として辺の数を減らす工夫を取り入れることも考えられる。辺が不要かどうかは、その辺が通過又は隣接する格子要素と干渉する短絡辺が存在するかどうかによって判断される。
【００８６】
ある格子要素と干渉する短絡辺とは、端的には、その格子要素の上下左右方向のいずれかの格子要素を通過する短絡辺のことである。干渉する短絡辺の有無を調べるのは単に格子要素の縦及び横方向を走査するだけなので簡単だが、複数の格子要素について干渉する短絡辺を探すと効率が悪く、処理コストが増えてしまう。そこで、以下ではまず、干渉する短絡辺を効率良く探す方法を述べ、その後その方法を利用して辺を削除する方法を述べる。
【００８７】
各格子要素について上下左右の格子要素を走査せずに干渉する短絡辺を探すには、各行（横方向の格子要素の並び）及び各列（縦方向の格子要素の並び）に短絡辺のある格子要素がいくつあるかをあらかじめ調べておけばよい。
【００８８】
そのためには、まず各格子要素ｑ（ｉ，ｊ）を通過する短絡辺の有無を値（０なら無し、１なら有り）で表した２次元行列ｕ（ｉ，ｊ）を求める。これは、短絡辺を追加する際にｕ（ｉ，ｊ）を更新していっても良いし、最後にまとめて各格子要素を短絡辺が通過しているか調べて更新してもよい。
【００８９】
その後、ｕ（ｉ，ｊ）を行方向（横方向）と列方向（縦方向）に走査して、ｕ（ｉ，ｊ）＝１である格子要素の数を数え、それぞれｕｒｏｗ（ｊ）及びｕｃｏｌ（ｉ）として記録しておく。
【００９０】
例えば、図１６を用いて説明する。なお、第１の文字列については「ｓｉｔｔｉｎｇ」ではなく「ｓｉｔｔｉｔｇ」を採用し、「ｉｔ」が２回出現するようにした例である。図１６では、短絡辺が通過する格子要素についてはハッチングを付しており、ｕ（ｉ，ｊ）＝１となっている格子要素である。すなわち、ａ乃至ｅの格子要素がこれに該当する。ハッチング無しの格子要素については、ｕ（ｉ，ｊ）＝０となっている。
【００９１】
このようなｕ（ｉ，ｊ）が得られれば、ｊ（＝１）を固定してｉを変化させてｕ（ｉ，１）＝１となる格子要素の数を計数すれば、ｕｒｏｗ（１）が得られる。その後、ｊを２に変化させた上で、ｉを再度変化させてｕ（ｉ，２）＝１となる格子要素の数を計数すれば、ｕｒｏｗ（２）が得られる。このような処理を繰り返せばよい。
【００９２】
一方、ｉ（＝１）を固定してｊを変化させてｕ（１，ｊ）＝１となる格子要素の数を計数すれば、ｕｃｏｌ（１）が得られる。その後、ｉを２に変化させた上で、ｊを変化させてｕ（２，ｊ）＝１となる格子要素の数を計数すれば、ｕｃｏｌ（２）が得られる。このような処理を繰り返せばよい。図１６では、ｕｒｏｗ（ｊ）及びｕｃｏｌ（ｉ）を具体的に示している。
【００９３】
そして、ある格子要素ｑ（ｉ，ｊ）と干渉する短絡辺があるかどうかは、ｕｒｏｗ（ｊ）＞ｕ（ｉ，ｊ）とｕｃｏｌ（ｉ）＞ｕ（ｉ，ｊ）のいずれかが満たされるかどうかによって判断される。例えば、図１６において格子要素ａに着目すると、ｕｒｏｗ（２）＝２＞ｕ（２，２）＝１なので干渉する短絡辺があることが分かる。一方、格子要素ｃに着目するとｕｃｏｌ（４）＝ｕｒｏｗ（４）＝ｕ（４，４）＝１であるから、干渉する短絡辺はないと分かる。
【００９４】
このような前提の下、ある短絡辺が他の短絡辺と干渉していなければ、その短絡辺の一部をなすような斜め辺及びその短絡辺より短い短絡辺を辿ってもより低いスコアしか得られないので、そのような斜め辺及び短絡辺を削除する。短絡辺と干渉する他の短絡辺とは、その短絡辺が通過している格子要素の上下左右にある他の格子要素のいずれかを通過している短絡辺のこととする。
【００９５】
この処理を、図１７Ａ及び図１７Ｂを用いて説明する。他の短絡辺との干渉を検討する際には、長い短絡辺から検討していく。図１７Ａで最も長いのは短絡辺ａである。短絡辺ａと干渉する短絡辺は、短絡辺ａが通過している格子要素（斜め辺ｄ、ｅ及びｆが設けられた格子要素）の上下左右の格子要素、すなわち図１７Ａにおいてハッチング付きの格子要素を通過する短絡辺である。
【００９６】
図１７Ａに示すように、上で述べた条件を満たす短絡辺が１つもなければ、短絡辺ａの部分を成す辺ｂ、ｃ、ｄ、ｅ及びｆをすべて削除する。そうすると、図１７Ｂに示すような状態になる。すなわち、短絡辺ａのみが残るようになる。そうすると、最大スコア経路に必ず短絡辺ａが含まれるようになる。
【００９７】
もし仮に干渉する短絡辺がｇ及びｈの格子要素にあった場合は、短絡辺ａの部分を成す辺を削除せず、短絡辺ａの部分を成す辺のうち長い短絡辺（図１７Ａではｂ及びｃ）について同様に干渉する辺の有無を検討することになる。すなわち、もし格子要素ｇおよびｈに短絡辺があった場合、短絡辺ｃには干渉するが短絡辺ｂには干渉しないので、図１７Ｃに示すように短絡辺ｂの部分を成す辺ｄ及びｅだけを削除する。
【００９８】
以上の前提に基づき、不要な短絡辺などを削除する処理を行う場合における情報処理装置２００の構成例を、図１８に示す。第１の実施の形態に係る情報処理装置１００との差異は、グラフ生成部２０２であり、辺削除部２０２１が加えられている点が異なる。
【００９９】
次に、本実施の形態に係る第３のグラフ生成処理を図１９乃至図２９を用いて説明する。
【０１００】
まず、初期グラフ生成部１０２１は、初期グラフの生成処理を実行する（図１９：ステップＳ２０１）。この処理は第１の実施の形態における処理と同様であり、説明を省略する。
【０１０１】
また、辺追加部１０２２は、一致文字に基づく辺の追加処理を実行する（ステップＳ２０３）。この処理も第１の実施の形態における処理と同様であり、説明を省略する。
【０１０２】
さらに、辺追加部１０２２は、連続一致文字に基づく短絡辺の追加処理を実行する（ステップＳ２０５）。この処理も第１の実施の形態における処理と同様であり、説明を省略する。
【０１０３】
その後、辺削除部２０２１は、図１６を用いて説明したように、ｕ（ｉ，ｊ）、ｕｃｏｌ（ｉ）及びｕｒｏｗ（ｊ）を生成する（ステップＳ２０７）。これによって、簡単に短絡辺が干渉しているか否かを判定できる。
【０１０４】
そして、辺削除部２０２１は、短絡辺の削除処理を実行する（ステップＳ２０８）。この処理については、図２０乃至図２３を用いて説明する。
【０１０５】
まず、辺削除部２０２１は、空の短絡辺リストＥｒを生成し、辺集合Ｇに含まれる短絡辺を短絡辺リストＥｒに追加し、短絡辺を長さ順にソートする（図２０：ステップＳ２２１）。
【０１０６】
そして、辺削除部２０２１は、短絡辺リストＥｒが空であるか否かを判断する（ステップＳ２２３）。空であれば、処理は呼び出し元の処理に戻る。
【０１０７】
一方、短絡辺リストＥｒが空ではない場合には、辺削除部２０２１は、短絡辺リストＥｒの最長短絡辺の１つｅ＝ｅｓ（ｉ，ｊ，ｋ）を短絡辺リストＥｒから取り除く（ステップＳ２２５）。
【０１０８】
その後、辺削除部２０２１は、カウンタｚを０に初期化する（ステップＳ２２７）。そして、辺削除部２０２１は、ｕｒｏｗ（ｊ＋ｚ）＞ｕ（ｉ＋ｚ，ｊ＋ｚ）又はｕｃｏｌ（ｉ＋ｚ）＞ｕ（ｉ＋ｚ，ｊ＋ｚ）のいずれかが成り立つか否を判断する（ステップＳ２２９）。このステップは、ｅｓ（ｉ，ｊ，ｋ）の横方向又は縦方向に干渉する短絡辺が存在するか否かを、ｅｓ（ｉ，ｊ，ｋ）が横切る各格子要素について判断するものである。
【０１０９】
ステップＳ２２９の条件を満たす場合には、干渉があるので、処理はステップＳ２２３に戻る。一方、ステップＳ２２９の条件を満たさない場合には、辺削除部２０２１は、ｚがｋより小さいか否かを判断する（ステップＳ２３１）。ｋは、処理対象の短絡辺の長さに相当する。この条件を満たさない場合、辺削除部２０２１は、ｚを１インクリメントして（ステップＳ２３３）、処理はステップＳ２２９に戻る。
【０１１０】
一方、ｚがｋ以上となると、処理対象の短絡辺には完全に干渉がないことが確認されたことになる。従って、辺削除部２０２１は、ｅを成す短絡辺ｅｓ（ｉ＋ｚ，ｊ＋ｚ，ｈ）と斜め辺ｅｄ（ｉ＋ｚ，ｊ＋ｚ）を、辺集合Ｇ及び斜め辺集合Ｅｒから除去する（ステップＳ２３５）。このようにして、有向グラフにおける辺が削減されるようになる。処理は、ステップＳ２２３に戻る。
【０１１１】
以上のように、他の短絡辺との干渉がなければ、処理対象の短絡辺のみを後続処理で考慮すればよくなるので、削除によって演算量を削減できる。
【０１１２】
図１９の説明に戻って、次に、辺削除部２０２１は、グラフ変形処理を実行する（ステップＳ２０９）。この処理については、行わなくても良いが、行うと処理が効率化される場合がある。グラフ変形処理については、図２１乃至図２９を用いて説明する。
【０１１３】
グラフ変形処理は、斜め辺が上下及び左右の格子要素に複数並んで矩形状に存在するとき、すなわち文字列Ｓと文字列Ｔに特定の文字の連続部分が存在するとき、その矩形領域の入り口（すなわち左上端部）の頂点と出口（すなわち右下端部）の頂点のそれぞれの組を直接つなぐ辺を設け、その代わりに矩形内の従来の辺をすべて削除する、というものである。
【０１１４】
例えば、図２１では、左上端部の頂点ｖ（２，２）と右下端部の頂点ｖ（６，５）で特定される矩形領域が、条件に合致することになる。このとき、まず矩形領域の上下左右にある格子要素（図２１でハッチング付きの格子要素）に短絡辺が１つもなければ、矩形領域内の辺はすべて取り除いて、頂点ｖ（２，２）と頂点ｖ（６，５）を短絡するだけでよい。すなわち、図２２に示すような有向グラフとなる。
【０１１５】
一方、もし干渉する短絡辺があれば、矩形領域内の辺はすべて取り除いた上で、矩形領域内は、入口の頂点（矩形左上端部のｖ（２，２）を含む点線枠Ａ内の６頂点）と出口の頂点（矩形右下端部のｖ（６，５）を含む点線枠Ｂ内の６頂点）の任意の組み合わせ（ただし、出口が右、下、または右下にある組のみ。すなわち、終了点から遠くなるような出口点は選択しない。）をつなぐ短絡辺を追加する。そうすると、図２３に示すような有向グラフとなる。
【０１１６】
新たな短絡辺のスコアは、横方向及び縦方向の格子要素の数のうち小さい方の値から算出される。すなわち、その数だけ連続した斜めの辺といくつかの縦又は横の辺を辿ればスコア最大であることは明らかであり、縦及び横の辺のスコアは０であるから、連続した斜め辺のスコアが短絡辺のスコアである。
【０１１７】
以下、具体的な処理内容を、図２４乃至図２９を用いて説明する。
【０１１８】
まず、辺削除部２０２１は、空の頂点候補リストＶcを生成する（図２４：ステップＳ２４１）。そして、辺削除部２０２１は、ｉ＝１からｍの順番で各ｉについて、ｊ＝１からｎの順番で各ｊについて頂点ｖ（ｉ，ｊ）を頂点候補リストＶcに追加する（ステップＳ２４３）。
【０１１９】
その後、辺削除部２０２１は、頂点候補リストＶcが空になったか否かを判断する（ステップＳ２４５）。頂点候補リストＶcが空になった場合には、処理は呼び出し元の処理に戻る。
【０１２０】
一方、頂点候補リストＶcが空でなければ、辺削除部２０２１は、頂点候補リストＶcの先頭から頂点ｖ（ｉ，ｊ）を取り出す（ステップＳ２４７）。この頂点ｖ（ｉ、ｊ）が処理対象であり、頂点候補リストＶcからこの頂点ｖ（ｉ，ｊ）を除去する。
【０１２１】
その後、辺削除部２０２１は、図２１に示すような矩形領域を特定するための矩形領域取得処理を実行する（ステップＳ２４９）。この矩形領域取得処理については、図２５を用いて説明する。
【０１２２】
まず、辺削除部２０２１は、ｗ＝ｈ＝０に初期化する（図２５：ステップＳ２６０）。さらに、辺削除部２０２１は、第１の文字列のｉ番目の文字ｓ（ｉ）と第２の文字列のｊ番目の文字ｔ（ｊ）とが一致しているか否かを判断する（ステップＳ２６１）。この条件が満たされない場合には、処理は、呼び出し元の処理に戻る。
【０１２３】
一方、ステップＳ２６１の条件が満たされた場合には、辺削除部２０２１は、ｗを１に設定する（ステップＳ２６３）。そして、辺削除部２０２１は、ｉ＋ｗが第１の文字列の長さｍ以下であって且つｓ（ｉ＋ｗ）＝ｓ（ｉ）であるか否かを判断する（ステップＳ２６５）。同じ文字が連続しているか否かを判断している。この条件を満たす場合には、辺削除部２０２１は、ｗを１インクリメントして（ステップＳ２６７）、処理はステップＳ２６５に移行する。
【０１２４】
一方、ステップＳ２６５の条件を満たさない場合には、辺削除部２０２１は、ｈを１に設定する（ステップＳ２６８）。その後、辺削除部２０２１は、ｊ＋ｈが第２の文字列の長さｎ以下であって且つｔ（ｊ＋ｈ）＝ｔ（ｊ）であるか否かを判断する（ステップＳ２６９）。この条件を満たす場合には、辺削除部２０２１は、ｈを１インクリメントして（ステップＳ２７０）、処理はステップＳ２６９に戻る。
【０１２５】
一方、ステップＳ２６９の条件を満たさない場合には、処理は呼び出し元の処理に戻る。
【０１２６】
このようにすれば、頂点ｖ（ｉ，ｊ）から（ｗ−１）×（ｈ−１）のサイズの矩形領域ｒ（ｉ，ｊ，ｗ−１，ｈ−１）が得られたことになる。
【０１２７】
図２４の処理の説明に戻って、辺削除部２０２１は、ｗ＝２以下且つｈ＝２以下であるか否かを判断する（ステップＳ２５１）。すなわち、１×１サイズの矩形領域しかない又は矩形領域が特定されなかったか否かを判断する。この条件を満たす場合には、処理はステップＳ２４５に戻る。
【０１２８】
一方、ステップＳ２５１の条件を満たさない場合には、１×１より大きい矩形領域が得られたことになるので、辺削除部２０２１は、矩形領域内部の頂点ｖ（ｘ，ｙ）を頂点候補リストＶcから削除する（ステップＳ２５３）。そして、辺削除部２０２１は、矩形領域内処理を実行する（ステップＳ２５５）。この矩形領域内処理については、図２６乃至図２９を用いて説明する。
【０１２９】
まず、辺削除部２０２１は、干渉についての条件が満たされているか判断する（図２６：ステップＳ２７１）。具体的には、以下の数式が成り立つのか否かを判断する。この数式は、矩形領域全体について干渉がない場合に成り立つが、矩形領域の一部でも干渉があれば成り立たない。
【０１３０】
【数１】
2015158744.tif 000003
【０１３１】
ステップＳ２７１の条件を満たす場合には、干渉無しと判断されるので、辺削除部２０２１は、干渉なしの場合の変形処理を実行する（ステップＳ２７２）。そして処理は呼び出し元の処理に戻る。一方、ステップＳ２７１の条件を満たさない場合には、干渉有りと判断されるので、辺削除部２０２１は、干渉ありの場合の変形処理を実行する（ステップＳ２７３）。そして処理は呼び出し元の処理に戻る。
【０１３２】
次に、図２７を用いて干渉なしの場合の変形処理を説明する。
【０１３３】
辺削除部２０２１は、矩形領域内に未処理の頂点が存在するか否かを判断する（図２７：ステップＳ２７４）。未処理の頂点が存在する場合には、辺削除部２０２１は、矩形領域内における未処理の１つの頂点ｖ（ｘ，ｙ）を始点又は終点とする辺を、辺集合Ｇから削除する（ステップＳ２７５）。なお、ｘは、ｉ＋１からｉ＋ｗ−１まで変化させ、ｙは、ｊ＋１からｊ＋ｈ−１まで変化させる。そして、処理はステップＳ２７４に戻る。
【０１３４】
一方、矩形領域内に未処理の頂点が存在していない場合には、辺削除部２０２１は、頂点ｖ（ｉ，ｊ）からｖ（ｉ＋ｗ−１，ｊ＋ｈ−１）への短絡辺ｅを、辺集合Ｇに追加する（ステップＳ２７６）。さらに、辺削除部２０２１は、辺ｅのスコアｗ（ｅ）を、辺ｅの長さに応じた値に設定する（ステップＳ２７７）。具体的には、ｗｌｅｎ（ｍｉｎ（ｗ−１，ｈ−１））で算出する。ｍｉｎ（Ａ，Ｂ）は、ＡとＢとのうち小さい値を出力する関数である。
【０１３５】
このような処理によって図２３に示すような有向グラフが得られる。
【０１３６】
次に、干渉ありの場合の変形処理について、図２８及び図２９を用いて説明する。まず、辺削除部２０２１は、矩形領域内に未処理の頂点が存在するか否かを判断する（図２８：ステップＳ２８１）。未処理の頂点が存在する場合には、辺削除部２０２１は、矩形領域内における未処理の１つの頂点ｖ（ｘ，ｙ）を始点又は終点とする辺を、辺集合Ｇから削除する（ステップＳ２８３）。なお、ｘは、ｉ＋１からｉ＋ｗ−１まで変化させ、ｙは、ｊ＋１からｊ＋ｈ−１まで変化させる。そして、処理はステップＳ２８１に戻る。
【０１３７】
一方、矩形領域内に未処理の頂点が存在していない場合には、辺削除部２０２１は、空の入口点集合Ｖinを生成し（ステップＳ２８５）、頂点ｖ（ｘ，ｊ）（ｘはｉからｉ＋ｗ−１）を入口点集合Ｖinに追加する（ステップＳ２８７）。また、辺削除部２０２１は、頂点ｖ（ｉ，ｙ）（ｙはｊからｊ＋ｈ−１）を入口点集合Ｖinに追加する（ステップＳ２８９）。
【０１３８】
その後、辺削除部２０２１は、空の出口点集合Ｖoutを生成し（ステップＳ２９１）、頂点ｖ（ｘ、ｊ＋ｈ）（ｘはｉ＋１からｉ＋ｗ）を出口点集合Ｖoutに追加する（ステップＳ２９３）。さらに、辺削除部２０２１は、頂点ｖ（ｉ＋ｗ，ｙ）（ｙはｊ＋１からｊ＋ｈ−１）を出口点集合Ｖoutに追加する（ステップＳ２９５）。その後、処理は端子Ａを介して図２９の処理に移行する。
【０１３９】
図２９の処理の説明に移行して、辺削除部２０２１は、入口点集合Ｖinの未処理の頂点vin＝ｖ（ｘ，ｙ）を１つ特定する（ステップＳ２９７）。また、辺削除部２０２１は、Ｖoutにおいて頂点ｖout＝ｖ（ｘ＋ｄｘ，ｙ＋ｄｙ）（ｄｘ，ｄｙは自然数）のうち未処理頂点ｖoutを１つ特定する（ステップＳ２９９）。より特定された入口点から終了点に近い出口点のみに着目するものである。
【０１４０】
そして、辺削除部２０２１は、特定されたｖinから特定されたｖoutへの短絡辺ｅを辺集合Ｇに追加する（ステップＳ３０１）。また、辺削除部２０２１は、辺ｅのスコアｗ（ｅ）を、辺ｅの長さに応じた値に設定する（ステップＳ３１１）。具体的には、ｗｌｅｎ（ｍｉｎ（ｄｘ，ｄｙ））で算出する。
【０１４１】
その後、辺削除部２０２１は、未処理の頂点ｖoutが存在しているか否かを判断する（ステップＳ３１３）。未処理の頂点ｖoutが存在している場合には、処理はステップＳ２９９に戻る。一方、未処理の頂点ｖoutが存在していない場合には、ここまで処理したｖoutを未処理に設定する。その後、辺削除部２０２１は、未処理の頂点ｖinが存在しているか否かを判断する（ステップＳ３１５）。未処理の頂点ｖinが存在する場合には、処理はステップＳ２９７に戻る。一方、未処理の頂点ｖinが存在しない場合には、処理は呼び出し元の処理に戻る。
【０１４２】
以上のような処理を実行することで、図２３に示すような有向グラフが生成されるようになる。
【０１４３】
図１９の処理の説明に戻って、スコア調整部１０２３は、ステップＳ２０９でスコアの調整がなされていない斜め辺及び短絡辺について、スコアを更新する（ステップＳ２１１）。この処理は、基本的にステップＳ１７と同様の処理である。スコア未調整の斜め辺及び短絡辺については、ステップＳ２０３で追加された斜め辺の集合とステップＳ２０５で追加された短絡辺の集合とを管理しておき、ステップＳ２０８及びＳ２０９で削除された斜め辺及び短絡辺を、それぞれの集合から削除するようにすれば、把握される。
【０１４４】
以上のような処理を実行することで、グラフ生成処理より後の処理の演算量が削減できる。
【０１４５】
以上本発明の実施の形態を説明したが、本発明はこれに限定されるものではない。上でも述べたように、文字列は一例であって、数値データの列、バイトデータの列、単語の列などであっても良い。
【０１４６】
また、上で述べた機能ブロック構成は一例であって、プログラムモジュール構成やファイル構成とは一致しない場合もある。さらに、処理フローについても、処理結果が変わらない限り処理順番を入れ替えたり、複数ステップを並列実行するようにしてもよい。
【０１４７】
なお、上で述べた情報処理装置１００及び２００は、コンピュータ装置であって、図３０に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１４８】
以上述べた本実施の形態をまとめると、以下のようになる。
【０１４９】
本実施の形態に係る情報処理方法は、（Ａ）第１のシーケンスに含まれる複数のエレメントの各々と、第２のシーケンスに含まれる複数のエレメントの各々とを比較して、一致するエレメントの第１の部分及び連続一致するエレメントの第２の部分を特定し、（Ｂ）特定された第１の部分及び第２の部分の各々について、当該部分の長さに応じたスコアを設定し、（Ｃ）当該スコアに基づき、第１のシーケンスと第２のシーケンスとの類似度を算出する処理を含む。
【０１５０】
このように連続一致するエレメントの長さに応じたスコアを設定することで、連続一致を加味した類似度を算出できるようになる。
【０１５１】
また、本情報処理方法は、（Ｄ）第１のエレメントの各々に応じた第１の方向の辺と第２のエレメントの各々に応じた第２の方向の辺とを有する格子状の有向グラフを生成し、（Ｅ）特定された第１の部分に対応する辺を有向グラフに追加し、（Ｆ）特定された第２の部分に対応し、連続一致するエレメントのうち開始エレメントから終了エレメントをつなぐ短絡辺を有向グラフに追加する処理をさらに含むようにしても良い。この場合、上で述べたスコアを設定する処理において、（ｂ１）追加された辺及び短絡辺に、当該辺又は短絡辺の長さに応じたスコアを設定するようにしても良い。また、上で述べた類似度を算出する処理が、（ｃ１）有向グラフにおける最大スコア経路を決定する処理を含むようにしても良い。
【０１５２】
このように短絡辺を有向グラフに追加することで、連続一致するエレメントの寄与を直接的に反映させることができるようになる。
【０１５３】
また、本情報処理方法は、（Ｄ）第１のエレメントの各々に応じた第１の方向の辺と第２のエレメントの各々に応じた第２の方向の辺とを有する格子状の有向グラフを生成し、（Ｅ）特定された第１の部分に対応する辺を有向グラフに追加する処理をさらに含むようにしても良い。この場合、上で述べたスコアを設定する処理において、（ｂ２）特定された第２の部分に含まれる第１の部分について追加された各辺に、特定された第２の部分の長さに応じたスコアを設定し、（ｂ３）特定された第２の部分に含まれない第１の部分について追加された各辺に、当該第１の部分の長さに応じたスコアを設定するようにしても良い。さらに、上で述べた類似度を算出する処理が、（ｃ１）有向グラフにおける最大スコア経路を決定する処理を含むようにしても良い。
【０１５４】
このようにすれば、多少精度が落ちる可能性があるが、類似度を算出する処理の処理負荷を下げることができるようになる。
【０１５５】
また、上で述べた短絡辺を有向グラフに追加する処理（Ｆ）において、（ｆ１）特定された第２の部分のうち所定の条件を満たす第２の部分について、短絡辺を有向グラフに追加するようにしても良い。このようにすれば、精度が落ちるかもしれないが、処理負荷を削減できるようになる。
【０１５６】
なお、上で述べた所定の条件が、連続一致するエレメントの数についての条件である場合もある。例えば、長さが短いもののみ、長いもののみ、連続一致するエレメントの数の偶数奇数、長さが短いもの及び長いは全て且つ中間長の辺は省略又は確率的にといったバリエーションが考えられる。
【０１５７】
さらに、本情報処理方法は、（Ｇ）有向グラフの格子において、第１の短絡辺が通過する第１の格子要素の第１の方向及び第２の方向のいずれかに、第２の短絡辺が通過する第２の格子要素が存在するか判断し、（Ｈ）第２の格子要素が存在していない場合、第１の短絡辺に対応する第２の部分に含まれる第１の部分に対応する辺及び第１の短絡辺に対応する第２の部分に含まれる他の第２の部分に対応する短絡辺を削除する処理をさらに含むようにしても良い。このようにすれば、類似度算出処理において用いられない辺が削除され、処理負荷が軽減されるようになる。
【０１５８】
また、本情報処理方法は、（Ｉ）第１のシーケンスと第２のシーケンスとのうち少なくともいずれかにおいて同一エレメントが連続する部分が存在し且つ当該同一エレメントが少なくとも１つ第１のシーケンス及び第２のシーケンスに含まれるという条件を満たす場合、有向グラフにおいて同一エレメントが連続する部分に対応する格子要素の領域を特定し、（Ｊ）有向グラフの格子において、特定された領域の第１の方向及び第２の方向のいずれかに、他の短絡辺が通過する第２の格子要素が存在するか判断し、（Ｋ）第２の格子要素が存在していないと判断された場合、領域内の辺を削除し、領域において有向グラフの開始点に最も近い頂点から終了点に最も近い頂点へ結ぶ短絡辺を追加する処理をさらに含むようにしても良い。このような処理を行っても、類似度算出処理において用いられない辺が削除され、処理負荷が軽減される。
【０１５９】
また、本情報処理方法は、（Ｌ）第２の格子要素が存在すると判断された場合、領域内部の辺を削除し、（Ｍ）領域の辺のうち有向グラフにおける開始点側の辺に含まれる頂点から、領域の辺のうち有向グラフにおける終了点側の辺に含まれる頂点へ短絡辺を追加する処理をさらに含むようにしても良い。このような処理を行っても、類似度算出処理において用いられない辺が削除され、処理負荷が軽減される可能性がある。
【０１６０】
さらに、本情報処理方法は、（Ｎ）有向グラフの格子において第１の方向に並ぶ格子要素のいずれかに存在する短絡辺の数を、第２の方向に並ぶ各格子要素について計数し、（Ｏ）有向グラフの格子において第２の方向に並ぶ格子要素のいずれかに存在する短絡辺の数を、第１の方向に並ぶ各格子要素について計数する処理をさらに含むようにしても良い。これによって、第２の格子要素の有無を高速に判断できるようになる。
【０１６１】
また、本情報処理方法は、（Ｐ）有向グラフの格子において第１の方向に並ぶ格子要素のいずれかに短絡辺が存在するか否かを、第２の方向に並ぶ各格子要素について判定し、（Ｑ）有向グラフの格子において第２の方向に並ぶ格子要素のいずれかに短絡辺が存在するか否かを、第１の方向に並ぶ各格子要素について判定する処理をさらに含むようにしても良い。これによって、第２の格子要素の有無を高速に判断できるようになる。
【０１６２】
なお、上で述べたような処理をコンピュータに実行させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭなどの光ディスク、光磁気ディスク、半導体メモリ（例えばＲＯＭ）、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、ＲＡＭ等の記憶装置に一時保管される。
【０１６３】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１６４】
（付記１）
第１のシーケンスに含まれる複数のエレメントの各々と、第２のシーケンスに含まれる複数のエレメントの各々とを比較して、一致するエレメントの第１の部分及び連続一致するエレメントの第２の部分を特定し、
特定された前記第１の部分及び前記第２の部分の各々について、当該部分の長さに応じたスコアを設定し、
当該スコアに基づき、前記第１のシーケンスと前記第２のシーケンスとの類似度を算出する
処理を、コンピュータに実行させるためのプログラム。
【０１６５】
（付記２）
前記第１のシーケンスの前記複数のエレメントの各々に応じた第１の方向の辺と前記第２のシーケンスの前記複数のエレメントの各々に応じた第２の方向の辺とを有する格子状の有向グラフを生成し、
特定された前記第１の部分に対応する辺を前記有向グラフにおいて前記第１の部分に対応する格子要素内に追加し、
特定された前記第２の部分に対応する短絡辺を前記有向グラフにおいて前記第２の部分に対応する部分に追加する
処理をさらに前記コンピュータに実行させ、
前記スコアを設定する処理において、
追加された前記辺及び前記短絡辺に、当該辺又は短絡辺の長さに応じたスコアを設定し、
前記類似度を算出する処理が、
前記有向グラフにおける最大スコア経路を決定する
処理を含む付記１記載のプログラム。
【０１６６】
（付記３）
前記第１のエレメントの各々に応じた第１の方向の辺と前記第２のエレメントの各々に応じた第２の方向の辺とを有する格子状の有向グラフを生成し、
特定された前記第１の部分に対応する辺を前記有向グラフの前記第１の部分に対応する格子要素内に追加する
処理をさらに前記コンピュータに実行させ、
前記スコアを設定する処理において、
特定された前記第２の部分に含まれる前記第１の部分に対応する各辺に、特定された前記第２の部分の長さに応じたスコアを設定し、
特定された前記第２の部分に含まれない前記第１の部分に対応する各辺に、当該第１の部分の長さに応じたスコアを設定し、
前記類似度を算出する処理が、
前記有向グラフにおける最大スコア経路を決定する
処理を含む付記１記載のプログラム。
【０１６７】
（付記４）
前記短絡辺を前記有向グラフに追加する処理において、
特定された前記第２の部分のうち所定の条件を満たす第２の部分について、前記短絡辺を前記有向グラフに追加する
付記２記載のプログラム。
【０１６８】
（付記５）
前記所定の条件が、連続一致するエレメントの数についての条件である
付記４記載のプログラム。
【０１６９】
（付記６）
前記有向グラフの格子において、第１の短絡辺が通過する第１の格子要素の前記第１の方向及び前記第２の方向のいずれかに、第２の短絡辺が通過する第２の格子要素が存在するか判断し、
前記第２の格子要素が存在していない場合、前記第１の短絡辺に対応する前記第２の部分に含まれる第１の部分に対応する辺及び前記第１の短絡辺に対応する前記第２の部分に含まれる他の第２の部分に対応する短絡辺を削除する
処理をさらに前記コンピュータに実行させるための付記２記載のプログラム。
【０１７０】
（付記７）
前記第１のシーケンスと前記第２のシーケンスとのうち少なくともいずれかにおいて同一エレメントが連続する部分が存在し且つ当該同一エレメントが少なくとも１つ前記第１のシーケンス及び前記第２のシーケンスに含まれるという条件を満たす場合、前記有向グラフにおいて前記同一エレメントが連続する部分に対応する格子要素の領域を特定し、
前記有向グラフの格子において、特定された前記領域の前記第１の方向及び前記第２の方向のいずれかに、他の短絡辺が通過する第２の格子要素が存在するか判断し、
前記第２の格子要素が存在していないと判断された場合、前記領域内の辺を削除し、前記領域において前記有向グラフの開始点に最も近い頂点から終了点に最も近い頂点へ結ぶ短絡辺を追加する
処理をさらに前記コンピュータに実行させるための付記２又は６記載のプログラム。
【０１７１】
（付記８）
前記第２の格子要素が存在すると判断された場合、前記領域内部の辺を削除し、
前記領域の辺のうち前記有向グラフにおける開始点側の辺に含まれる頂点から、前記領域の辺のうち前記有向グラフにおける終了点側の辺に含まれる頂点へ短絡辺を追加する
処理をさらに前記コンピュータに実行させるための付記７記載のプログラム。
【０１７２】
（付記９）
前記有向グラフの格子において前記第１の方向に並ぶ格子要素のいずれかに存在する短絡辺の数を、前記第２の方向に並ぶ各格子要素について計数し、
前記有向グラフの格子において前記第２の方向に並ぶ格子要素のいずれかに存在する短絡辺の数を、前記第１の方向に並ぶ各格子要素について計数する
処理をさらに前記コンピュータに実行させるための付記６乃至８のいずれか１つ記載のプログラム。
【０１７３】
（付記１０）
前記有向グラフの格子において前記第１の方向に並ぶ格子要素のいずれかに短絡辺が存在するか否かを、前記第２の方向に並ぶ各格子要素について判定し、
前記有向グラフの格子において前記第２の方向に並ぶ格子要素のいずれかに短絡辺が存在するか否かを、前記第１の方向に並ぶ各格子要素について判定する
処理をさらに前記コンピュータに実行させるための付記９記載のプログラム。
【０１７４】
（付記１１）
前記シーケンスは文字列である付記２乃至９のいずれか１つに記載のプログラム。
【０１７５】
（付記１２）
第１のシーケンスに含まれる複数のエレメントの各々と、第２のシーケンスに含まれる複数のエレメントの各々とを比較して、一致するエレメントの第１の部分及び連続一致するエレメントの第２の部分を特定し、
特定された前記第１の部分及び前記第２の部分の各々について、当該部分の長さに応じたスコアを設定し、
当該スコアに基づき、前記第１のシーケンスと前記第２のシーケンスとの類似度を算出する
処理を含み、コンピュータにより実行される情報処理方法。
【０１７６】
（付記１３）
前記シーケンスは文字列である付記１２記載の情報処理方法。
【０１７７】
（付記１４）
第１のシーケンスに含まれる複数のエレメントの各々と、第２のシーケンスに含まれる複数のエレメントの各々とを比較して、一致するエレメントの第１の部分及び連続一致するエレメントの第２の部分を特定する特定部と、
特定された前記第１の部分及び前記第２の部分の各々について、当該部分の長さに応じたスコアを設定する設定部と、
当該スコアに基づき、前記第１のシーケンスと前記第２のシーケンスとの類似度を算出する算出部と、
を有する情報処理装置。
【０１７８】
（付記１５）
前記シーケンスは文字列である付記１４記載の情報処理装置。
【符号の説明】
【０１７９】
１００  情報処理装置
１０１  入力データ格納部
１０２，２０２  グラフ生成部
１０３  第１データ格納部
１０４  探索部
１０５  第２データ格納部
１０６  類似度算出部
１０７  出力データ格納部
１０２１  初期グラフ生成部
１０２２  辺追加部
１０２３  スコア調整部
２０２１  辺削除部
【図１】
2015158744.tif 000004
【図２】
2015158744.tif 000005
【図３】
2015158744.tif 000006
【図４】
2015158744.tif 000007
【図５】
2015158744.tif 000008
【図６】
2015158744.tif 000009
【図７】
2015158744.tif 000010
【図８】
2015158744.tif 000011
【図９】
2015158744.tif 000012
【図１０】
2015158744.tif 000013
【図１１】
2015158744.tif 000014
【図１２】
2015158744.tif 000015
【図１３】
2015158744.tif 000016
【図１４】
2015158744.tif 000017
【図１５】
2015158744.tif 000018
【図１６】
2015158744.tif 000019
【図１７Ａ】
2015158744.tif 000020
【図１７Ｂ】
2015158744.tif 000021
【図１７Ｃ】
2015158744.tif 000022
【図１８】
2015158744.tif 000023
【図１９】
2015158744.tif 000024
【図２０】
2015158744.tif 000025
【図２１】
2015158744.tif 000026
【図２２】
2015158744.tif 000027
【図２３】
2015158744.tif 000028
【図２４】
2015158744.tif 000029
【図２５】
2015158744.tif 000030
【図２６】
2015158744.tif 000031
【図２７】
2015158744.tif 000032
【図２８】
2015158744.tif 000033
【図２９】
2015158744.tif 000034
【図３０】
2015158744.tif 000035