JP2016177327A - Method of associating two element strings having feature in configuration of directed acyclic graph and cost of lattice point for applying dynamic programming - Google Patents
Method of associating two element strings having feature in configuration of directed acyclic graph and cost of lattice point for applying dynamic programming Download PDFInfo
- Publication number
- JP2016177327A JP2016177327A JP2015054744A JP2015054744A JP2016177327A JP 2016177327 A JP2016177327 A JP 2016177327A JP 2015054744 A JP2015054744 A JP 2015054744A JP 2015054744 A JP2015054744 A JP 2015054744A JP 2016177327 A JP2016177327 A JP 2016177327A
- Authority
- JP
- Japan
- Prior art keywords
- cost
- point
- lattice
- elements
- directed
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
Description
本発明は、順序を持つ要素の集合である要素列について、2つの要素列を比較して、一方の要素列の要素と他方の要素列の要素との対応を決定する、対応付け方法、対応付け装置ならびに対応付けプログラムに関する。 The present invention relates to an element method that is a set of elements having an order by comparing two element strings and determining a correspondence between an element in one element string and an element in the other element string. The present invention relates to an attaching device and an association program.
第1の要素列と第2の要素列のそれぞれの要素を対応付ける技術は、音声などの時系列パターンの認識や、文字や指紋などの画像パターンの認識など、様々な分野での応用がある。ここでいう要素とは、2つの要素列のそれぞれの要素間で対応付けの指標となる数値を定義できるものであれば良い。例えばN次元空間上の点の列であれば、2つの点の間の距離を対応付けの指標と定義することが出来る。 The technique for associating each element of the first element string and the second element string has applications in various fields such as recognition of time-series patterns such as speech and recognition of image patterns such as characters and fingerprints. The element here may be any element that can define a numerical value as an index of association between the elements of the two element strings. For example, in the case of a sequence of points on an N-dimensional space, the distance between two points can be defined as an association index.
要素列に歪みがあると対応付けは難しくなり、要素列を伸縮させてもっとも整合した対応付けを得る技術は、弾性マッチングと呼ばれる。弾性マッチングには動的計画法(Dynamic Programming)を利用したDPマッチングが広く用いられている。 If the element sequence is distorted, the association becomes difficult, and a technique for obtaining the most consistent association by expanding and contracting the element sequence is called elastic matching. DP matching using dynamic programming is widely used for elastic matching.
例えば類似画像の検索においてもDPマッチングが用いられている。特許文献1に記載された類似画像検索においては、ブロックに分割した画像データごとに特徴量行列を生成し、特徴量行列を構成する各特徴列間の距離をDPマッチングにより求める過程を含んでいる。 For example, DP matching is also used in searching for similar images. The similar image search described in Patent Document 1 includes a process of generating a feature quantity matrix for each image data divided into blocks and obtaining a distance between each feature column constituting the feature quantity matrix by DP matching. .
あるいは、画像情報であるジェスチャの認識においてもDPマッチングが用いられている。特許文献2に記載されたジェスチャ認識装置においては、要素列として特徴パラメータ系列を取り、連続DPマッチングと呼ぶ手法の中で特徴パラメータ間の距離計算の順序の逆行を許すことで、標準パターンとして用いられる要素列の情報量を減らす工夫を行っている。 Alternatively, DP matching is also used in the recognition of gestures that are image information. In the gesture recognition apparatus described in Patent Document 2, a feature parameter series is taken as an element sequence, and used as a standard pattern by allowing reversal of the order of distance calculation between feature parameters in a technique called continuous DP matching. To reduce the amount of information in the element sequence.
非特許文献1中第2節に記された単調連続性制約を持つDPマッチングを例に、従来技術としてDPマッチングの原理を説明する。このDPマッチングでは、次の式(1)に示す2つの要素列、XとYとを対応付けの対象とする。 The principle of DP matching will be described as a conventional technique by taking DP matching having a monotonic continuity constraint described in Section 2 of Non-Patent Document 1 as an example. In this DP matching, two element strings, X and Y shown in the following formula (1), are to be matched.
非特許文献1に記されたDPマッチングでは、次の式(2)に示す、Xの第i番目の要素xiとYの第j番目の要素yjとの対応付けを最適化する。式(2)は、iの値がひとつずつ増えることを意味しており、これを連続性制約と呼ぶこととする。なお、この連続性制約はDPマッチング一般に課される制約ではない。 In the DP matching described in Non-Patent Document 1, the correspondence between the i-th element x i of X and the j-th element y j of Y shown in the following equation (2) is optimized. Equation (2) means that the value of i increases by one, and this is called a continuity constraint. This continuity constraint is not a constraint imposed on DP matching in general.
つぎに、要素間の対応付けのコストを、式(3)のように表す。なお、DPマッチングにおいては、2つの要素列中のそれぞれの要素間の対応付けでの指標とする値を、コスト、距離、類似度などと呼ぶ。コストや距離と呼ぶ場合は、指標値の合計を最小化することを要素列の対応付けの目的とする定式化を行うのに対し、類似度と呼ぶ場合は指標値の合計を最大化するように定式化する場合もある(例えば非特許文献2)。適当な変換を行えば両者は同じ意味となり、本出願においてはコストの用語を用いることにする。 Next, the cost of association between elements is expressed as shown in Equation (3). In DP matching, values used as indices in association between elements in two element strings are referred to as cost, distance, similarity, and the like. When it is called cost or distance, the formulation is aimed at minimizing the sum of index values for the purpose of associating element strings, whereas when it is called similarity, the sum of index values is maximized. (For example, nonpatent literature 2). If appropriate conversions are made, they have the same meaning, and the term cost will be used in this application.
非特許文献1では、式(3)のようにコストをノルムの形式で記しており、局所距離とも呼んでいる。距離の一般化として捉えられるノルムは正定値性を備えており、すなわち非負である。 In Non-Patent Document 1, the cost is described in the form of a norm as shown in Equation (3), which is also called a local distance. The norm, which is regarded as a generalization of distance, has positive definiteness, that is, non-negative.
式(1)(2)(3)のように定めた際、最適化問題は次の式(4)のように定式化される。式(4)中に示すように、この例では単調性制約を課し、その他、傾斜制限、始端、終端に関する条件を課している。これらのうち、単調性制約については条件として課す場合が一般的であるが、そうでない場合も報告されている。傾斜制限については、図1を用いて後述するようにさまざまな種類がある。始端と終端とについても式(4)に示す条件を課す場合が一般的であるが、始端終端フリー化を図る方法も報告されている。 When the equations (1), (2), and (3) are determined, the optimization problem is formulated as the following equation (4). As shown in the equation (4), in this example, a monotonic constraint is imposed, and other conditions regarding inclination limitation, a start end, and an end are imposed. Of these, the monotonic constraint is generally imposed as a condition, but other cases have been reported. There are various types of tilt limitation as described later with reference to FIG. In general, the condition shown in the equation (4) is imposed on the start end and the end, but a method for making the start end free is also reported.
式(4)の最適解を求める際、DPマッチングの手法では、コストの総和であり累積距離とも呼ばれる値(式(5)中ではgi(ui))を、次の式(5)に示す漸化式により始端から順次求める。式(5)はDP漸化式と呼ばれる。式(5)のDP漸化式の始端以外の場合での最小値選択範囲は、式(4)中の単調性制約と傾斜制限とにより決められている。 When obtaining the optimal solution of equation (4), the DP matching method uses a value that is the sum of costs and is also called the cumulative distance (g i (u i ) in equation (5)) in the following equation (5): The recursion formula shown below is used in order from the beginning. Equation (5) is called the DP recurrence equation. The minimum value selection range in cases other than the starting point of the DP recurrence formula of Formula (5) is determined by the monotonicity constraint and the tilt limit in Formula (4).
DP漸化式中の最小値選択範囲は、さまざまな種類がある傾斜制限によって異なってくる。図1に、非特許文献1(2.2項)に示された傾斜制限、すなわち、最小値選択範囲の種類を示す。式(4)の場合、図1中101の破線で示した格子でのiとjとによる座標にて、黒丸で記した点のgi(ui)の値を決める際に比較を行うgi-1(ui-1)の値の点を白丸で示している。図1中104は、単調性制約の無い傾斜制限を表す。 The minimum value selection range in the DP recurrence formula varies depending on various types of tilt restrictions. FIG. 1 shows the tilt limit shown in Non-Patent Document 1 (Section 2.2), that is, the type of the minimum value selection range. In the case of equation (4), a comparison is made when determining the value of g i (u i ) of a point marked with a black circle with the coordinates of i and j in the lattice shown by the broken line 101 in FIG. The point of the value of i-1 (u i-1 ) is indicated by a white circle. In FIG. 1, reference numeral 104 denotes a tilt limit without a monotonic constraint.
DP漸化式を用いて求めたgi(ui)の終端での値gI(J)が、式(4)の目的関数Fの最小値となる。この最適解の際の対応付けu1,...,ui,...,uIは、式(5)のDP漸化式で最小値をいずれのgi-1(ui-1)より選んだかを終端より逆に辿ることにより、すなわち、バックトラックにより得られる。 The value g I (J) at the end of g i (u i ) obtained using the DP recurrence formula is the minimum value of the objective function F in formula (4). The correspondences u 1 ,..., U i ,..., U I in this optimal solution are the DP recurrence formulas of Equation (5), and the minimum value is any g i-1 (u i-1 ) Is obtained by tracing back from the end, that is, by backtracking.
DPマッチングの定式化においては、{1,...,i,...,I}と{1,...,j,...,J}との直積集合であるDP平面上の格子点ではなく、格子点を結ぶ有向辺にコストを割り当てているものもある。これを含む異なる定式化は、格子点にコストが割り当てる定式化に置き換え可能である。本出願においては、格子点へのコストを割り当てる定式化を基本的に用いるが、より簡明な説明が行える場合には有向辺にコストを割り当てる例(図5)も用いる。 In the DP matching formulation, the lattice on the DP plane is the Cartesian product set of {1, ..., i, ..., I} and {1, ..., j, ..., J}. Some assign costs to directed edges that connect grid points instead of points. A different formulation including this can be replaced by a formulation in which costs are assigned to grid points. In the present application, a formulation for assigning costs to lattice points is basically used, but an example of assigning costs to directed edges (FIG. 5) is also used when a simpler explanation can be made.
以上、非特許文献1での記述による例を基にして、DPマッチングの原理を説明した。DPマッチングは弾性マッチングにてDP(Dynamic Programming、動的計画法)を利用した手法であり、上述の式(1)〜(5)によるDPマッチングの例は、図2に示すDP平面上に構成された有向無閉路グラフ(DAG、Directed Acyclic Graph)での最小コスト経路を動的計画法にて求めたことに相当する。すなわち、図2は、要素列X中の要素の集合と要素列Y中の要素の集合との直積集合である格子空間上で、格子点間を式(2)および、式(4)中の単調性制約と傾斜制限とにより制限された有向辺で結んだ有向無閉路グラフを矢印で示したものである。上述の例でのDPマッチングは、201の始端から、202の終端へのコスト最小経路を動的計画法によって求め、その経路に含まれる格子点の集合を対応付け結果とするものである。 The principle of DP matching has been described above based on the example described in Non-Patent Document 1. DP matching is a technique using DP (Dynamic Programming) in elastic matching, and examples of DP matching according to the above formulas (1) to (5) are configured on the DP plane shown in FIG. This is equivalent to obtaining the minimum cost path in the directed acyclic graph (DAG) by dynamic programming. That is, FIG. 2 shows that in the lattice space, which is a Cartesian product set of the element set in the element sequence X and the element set in the element sequence Y, the distance between the lattice points is expressed by Equations (2) and (4). A directed acyclic graph connected by directed edges restricted by monotonicity restrictions and slope restrictions is indicated by an arrow. The DP matching in the above-mentioned example is to obtain a minimum cost route from the start end of 201 to the end of 202 by dynamic programming, and a set of lattice points included in the route is used as an association result.
なお、以上の説明においては、対応付け手法であるDPマッチングと、DPマッチングで用いられている動的計画法(DP)とを区別している。以下での説明においても、両者を区別して記す。 In the above description, DP matching, which is a matching method, is distinguished from dynamic programming (DP) used in DP matching. In the following description, the two are also distinguished.
DPマッチングで利用する動的計画法は、図2のように直積集合である格子空間上で有向無閉路グラフが構成されていれば適用できる。すなわち、有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を処理することにより最小コスト経路を求めることが、DPマッチングの基本的な考え方である。式(1)〜(5)に示す定式化は例であり、DPマッチングを適用するために必要な条件ではない。 The dynamic programming method used in DP matching can be applied if a directed acyclic graph is configured on a lattice space that is a Cartesian product set as shown in FIG. That is, the basic idea of DP matching is to obtain a minimum cost path by processing lattice points in a topologically sorted order according to a semi-order defined by a directed acyclic graph. Formulations shown in equations (1) to (5) are examples and are not necessary conditions for applying DP matching.
逆に、対応付けの対象となる2つの要素列の順序に従って、最適化問題の制約条件として単調性制約を課せば、明らかに格子空間上で有向無閉路グラフが構成されるため、DPマッチングが適用できる。 Conversely, if a monotonic constraint is imposed as a constraint condition of the optimization problem according to the order of the two element sequences to be matched, a directed acyclic graph is clearly constructed in the lattice space, so DP matching Is applicable.
以上、非特許文献1での記述を基にして、DPマッチングの原理を式(1)〜(5)による例で説明したが、コストの観点からは、式(3)とは異なる捉え方を行っているDPマッチングもある。例えば非特許文献2に見えるDNA塩基配列の比較方法、すなわち、塩基配列同士の対応付けへのDPマッチングの適用においては、類似度と呼ぶコスト相当の値に、ノルムのような非負の値ばかりでなく、正負の両方の値が用いられている。また、特許文献3は、DNA塩基配列ではなく、これを組み合わせたアミノ酸配列へ翻訳を行った後に比較を行っているが、やはりコストにあたるスコアにおいて正負の両方の値を用いている。 As described above, based on the description in Non-Patent Document 1, the principle of DP matching has been described in the examples using the formulas (1) to (5). However, from the viewpoint of cost, a different view from the formula (3) is used. Some DP matching is done. For example, in the comparison method of DNA base sequences that can be seen in Non-Patent Document 2, that is, the application of DP matching to the correspondence between base sequences, the value corresponding to the cost called similarity is only a non-negative value such as a norm. Instead, both positive and negative values are used. In Patent Document 3, comparison is made after translation into an amino acid sequence that is not a DNA base sequence but a combination thereof, but both positive and negative values are used in the cost score.
なお、非特許文献2、および、特許文献3では、最適化問題において目的関数最大化の定式化を行っており、式(4)での最小化の定式化と比べると、コストに当たる指標の正負の意味付けは逆になっている。以下では、目的関数最小化の定式に基づく指標としてのコストにおける正負の意味付けを前提に説明を行う。 In Non-Patent Document 2 and Patent Document 3, the objective function maximization formulation is performed in the optimization problem. Compared with the minimization formulation in Equation (4), the sign of the index corresponding to the cost is positive or negative. The meaning of is reversed. In the following, the description will be made on the premise of the significance of the cost as an index based on the objective function minimization formula.
有向無閉路グラフに対して動的計画法を適用してコスト最小の経路を求める際、そのコストは非負である必要は無い。よって、負のコストにあたる指標が用いられている非特許文献2および特許文献3における対応付けにおいても、問題無くDPマッチングは動作する。なお、非特許文献2、および、特許文献3でのいずれのDPマッチングの例でも、単調性制約を課していることより、コスト最小の経路を求めるグラフは有向無閉路グラフとなっている。 When dynamic programming is applied to a directed acyclic graph to find a path with the lowest cost, the cost need not be non-negative. Therefore, DP matching operates without any problem even in association in Non-Patent Document 2 and Patent Document 3 where an index corresponding to a negative cost is used. Note that in any of the DP matching examples in Non-Patent Document 2 and Patent Document 3, since the monotonic constraint is imposed, the graph for obtaining the path with the minimum cost is a directed acyclic graph. .
また、非特許文献2では、図1中102に当たる傾斜制限を課している。特許文献3の傾斜制限は、塩基列の3つごとにアミノ酸列を考えることなどにより複雑化しているが、固定的な範囲を最小値選択範囲(請求項2では7つの格子点)としていることは変わりがない。DPの計算量はO(IJ)であるが、これは最小値選択範囲が固定的であることに拠る。 In Non-Patent Document 2, an inclination restriction corresponding to 102 in FIG. 1 is imposed. The tilt restriction of Patent Document 3 is complicated by considering amino acid sequences for every three base sequences, but the fixed range is the minimum value selection range (7 lattice points in claim 2). Is unchanged. The calculation amount of DP is O (IJ), which is based on the fact that the minimum value selection range is fixed.
特許文献1〜3、非特許文献1〜2に記されたDPマッチングの手法を含む従来技術においては、いずれもDP漸化式において固定的な最小値選択範囲を採っている。これは前述のとおりO(IJ)という小さい計算量であるDPマッチングの利点の裏付けとなっているが、傾斜制限により実現されている固定的な最小値選択範囲は、「類似するように2つの集合の要素を対応付ける」という弾性マッチングの原義とは直接関係がない。すなわち、固定的な最小値選択範囲は、対応付けを素早く計算するための手段であり、“類似させる”ことへは制限となっている。 In the related arts including the DP matching methods described in Patent Documents 1 to 3 and Non-Patent Documents 1 and 2, all adopt a fixed minimum value selection range in the DP recurrence formula. This supports the advantage of DP matching, which is a small calculation amount of O (IJ), as described above. However, the fixed minimum value selection range realized by the tilt restriction is “two to be similar. There is no direct relationship with the original meaning of elastic matching, which refers to associating elements of a set. That is, the fixed minimum value selection range is a means for quickly calculating the association, and is limited to “similar”.
また、特許文献3、および、非特許文献2に記された正負の値を持つコストは、コスト0を境にして“類似する”ことの定義と尺度を与えるものであると考えられる。すなわち、負の値であれば対応付けることが好ましく、正の値であれば対応付けないことが好ましいという基準を、弾性マッピングに与えるコストの設定の仕方と捉えることが出来る。しかしながら、上述のように固定的な最小値選択範囲と併用されているため、正負の値を持つコストの効果は対応付け結果に対して限定的である。 The costs having positive and negative values described in Patent Document 3 and Non-Patent Document 2 are considered to give a definition and scale of “similar” with cost 0 as a boundary. That is, it can be considered as a method of setting the cost given to the elastic mapping that a negative value is preferably associated and a positive value is preferably not associated. However, since the fixed minimum value selection range is used together as described above, the effect of the cost having positive and negative values is limited with respect to the association result.
本発明は、「類似するように2つの集合の要素を対応付ける」という弾性マッチングの原義に沿った対応付けを得ることを目的とする。すなわち、類似するように対応させることへの障害となっていた制限を無くした柔軟な対応付け、類似することの基準を明確に設定できる対応付けを実現することが目的である。制限を無くすには、制限を無くしたことにより意図しない対応付けが最適解となることを防ぐことが必要となる。 An object of the present invention is to obtain a correspondence in accordance with the original principle of elastic matching, “to associate elements of two sets so as to be similar”. That is, it is an object to realize a flexible association that eliminates the restriction that has been an obstacle to making it correspond to be similar, and an association that can clearly set a similarity criterion. In order to eliminate the restriction, it is necessary to prevent an unintended association from becoming an optimal solution by eliminating the restriction.
本発明に係る2つの要素列の対応付け方法の第1の構成は、
第1の要素列と第2の要素列とを比較して、第1の要素列の要素と第2の要素列の要素との組を1つ以上含む対応付けを得る際に、
第1の要素列の要素による集合と第2の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第1のステップと、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第1の要素列の要素と第2の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第2のステップと、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで2つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第3のステップと、
求めた最小コスト経路に含まれる格子点の第1の要素列の要素と第2の要素列の要素との組の集合を第1の要素列と第2の要素列との対応付けの結果とする第4のステップと、
を有する、要素列間対応付け方法において、
前記第1のステップでは、
前記有向無閉路グラフにより定義される半順序での、有向辺の始点側を上位、終点側を下位とした順序関係にて、
すべての該順序関係にある上位の格子点と下位の格子点について、該上位の格子点から該下位の格子点への有向辺を設けるように、前記有向無閉路グラフを構成することと、
前記第2のステップでは、
前記要素列の対応付けの目的において、前記格子点を構成する第1の要素列の要素と第2の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値0のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする。
The first configuration of the method for associating two element sequences according to the present invention is as follows:
When the first element sequence is compared with the second element sequence to obtain an association including one or more pairs of elements of the first element sequence and elements of the second element sequence,
On a lattice space that is a Cartesian product set of a set of elements of the first element sequence and a set of elements of the second element sequence,
A first directed acyclic graph is formed by providing a plurality of directed edges with a point in the lattice space as a lattice point, one lattice point as a start point, and another lattice point as an end point so as not to cause a cycle. And the steps
For all the grid points included as vertices in the directed acyclic graph, the cost is determined for each combination of the elements of the first element sequence and the elements of the second element sequence constituting each grid point. A second step for the cost of the grid points;
A route that connects two or more directed edges in succession by repeating the connection of two directed edges by matching the end point of the directed edge on the directed acyclic graph with the start point of another directed edge. age,
The total cost of the grid points included as the start point or end point of the directed side in the route is defined as the route cost.
The lattice points are sequentially processed in a topologically sorted order according to the semi-order defined by the directed acyclic graph, and the route that minimizes the route cost to the lattice point and the minimum route cost are obtained. A third step of determining a minimum cost path in the directed acyclic graph by dynamic programming;
A set of sets of elements of the first element sequence and elements of the second element sequence of the grid points included in the determined minimum cost path, and a result of associating the first element sequence with the second element sequence A fourth step to:
In the element string matching method having
In the first step,
In a partial order defined by the directed acyclic graph, in an order relationship in which the start point side of the directed edge is higher and the end point side is lower,
Configuring the directed acyclic graph so as to provide directed edges from the upper grid point to the lower grid point for all the upper grid points and the lower grid points in the order relationship; ,
In the second step,
For the purpose of associating the element strings, associating the elements of the first element string and the elements of the second element string constituting the lattice points is a negative cost when the object is met. If the cost is not positive, the cost of the positive value, if not, the value 0 is the cost of the grid point.
Mixing lattice points with negative cost and non-negative cost points,
It is characterized by.
この構成によれば、有向無閉路グラフ上の各格子点を終端とする経路コストの最小値は、有向無閉路グラフの半順序において上位に位置するすべての格子点を最小値選択範囲として持つことになり、DP平面である有向無閉路グラフ上で多くの第1の集合の要素、および、第2の集合の要素を対応付けせずに柔軟にスキップすることに相当する、多様な経路が最小コスト経路となり得る。このようにDP平面上で多様な経路を許容すると、コストの増加を避けて好ましい対応付けもスキップされて想定外に小さい対応づけの集合となることが従来技術では懸念されるが、負のコストを格子点に設定することにより、好ましい対応付けは目的関数の最小化に有利な負のコストの格子点としてスキップされにくくなり、従来技術で懸念される事態が起こることが無い。 According to this configuration, the minimum value of the path cost that ends each grid point on the directed acyclic graph is determined by setting all grid points positioned higher in the partial order of the directed acyclic graph as the minimum value selection range. A number of elements corresponding to the first set and many elements of the second set on the directed acyclic graph that is the DP plane can be flexibly skipped without being associated with each other. The route can be the least cost route. In this way, if various routes are allowed on the DP plane, it is feared in the prior art that a preferable association is skipped by avoiding an increase in cost, resulting in an unexpectedly small set of associations. Is set as a grid point, and the preferred correspondence is less likely to be skipped as a negative cost grid point that is advantageous for minimizing the objective function, and there is no possibility of concern in the prior art.
本発明に係る2つの要素列の対応付け方法の第2の構成は、
第1の要素列と第2の要素列とを比較して、第1の要素列の要素と第2の要素列の要素との組を1つ以上含む対応付けを得る際に、
第1の要素列の要素による集合と第2の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第1のステップと、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第1の要素列の要素と第2の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第2のステップと、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで2つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第3のステップと、
求めた最小コスト経路に含まれる格子点の第1の要素列の要素と第2の要素列の要素との組の集合を第1の要素列と第2の要素列との対応付けの結果とする第4のステップと、
を有する、要素列間対応付け方法において、
前記第1のステップでは、
前記第1の要素列の要素数をIとし、前記第2の要素列の要素数をJとし、前記Iと前記Jとの2つの値に応じて、I2J2に比例する数の有向辺を設けて、前記有向無閉路グラフを構成することと、
前記第2のステップでは、
前記要素列の対応付けの目的において、前記格子点を構成する第1の要素列の要素と第2の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値0のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする。
The second configuration of the method for associating two element sequences according to the present invention is as follows:
When the first element sequence is compared with the second element sequence to obtain an association including one or more pairs of elements of the first element sequence and elements of the second element sequence,
On a lattice space that is a Cartesian product set of a set of elements of the first element sequence and a set of elements of the second element sequence,
A first directed acyclic graph is formed by providing a plurality of directed edges with a point in the lattice space as a lattice point, one lattice point as a start point, and another lattice point as an end point so as not to cause a cycle. And the steps
For all the grid points included as vertices in the directed acyclic graph, the cost is determined for each combination of the elements of the first element sequence and the elements of the second element sequence constituting each grid point. A second step for the cost of the grid points;
A route that connects two or more directed edges in succession by repeating the connection of two directed edges by matching the end point of the directed edge on the directed acyclic graph with the start point of another directed edge. age,
The total cost of the grid points included as the start point or end point of the directed side in the route is defined as the route cost.
The lattice points are sequentially processed in a topologically sorted order according to the semi-order defined by the directed acyclic graph, and the route that minimizes the route cost to the lattice point and the minimum route cost are obtained. A third step of determining a minimum cost path in the directed acyclic graph by dynamic programming;
A set of sets of elements of the first element sequence and elements of the second element sequence of the grid points included in the determined minimum cost path, and a result of associating the first element sequence with the second element sequence A fourth step to:
In the element string matching method having
In the first step,
The number of elements in the first element row is I, the number of elements in the second element row is J, and there are a number proportional to I 2 J 2 according to the two values I and J. Providing a directed edge to construct the directed acyclic graph;
In the second step,
For the purpose of associating the element strings, associating the elements of the first element string and the elements of the second element string constituting the lattice points is a negative cost when the object is met. If the cost is not positive, the cost of the positive value, if not, the value 0 is the cost of the grid point.
Mixing lattice points with negative cost and non-negative cost points,
It is characterized by.
この構成によれば、多様な経路が最小コスト経路となり得ることと、好ましい対応付けが負のコストの格子点としてスキップされにくいことと、の2つの特徴を維持しながら、2つの要素列を対応付ける処理の対象となる事象の固有の性質に基づき、対応付けとなるコスト最短経路に制約を加えることが出来る。 According to this configuration, two element sequences are associated with each other while maintaining the two features that various routes can be the least cost route and that the preferable association is difficult to be skipped as a negative cost lattice point. Based on the unique property of the event to be processed, it is possible to constrain the cost shortest path to be associated.
本発明に係る2つの要素列の対応付け方法の第3の構成は、
前記第1の構成、または前記第2の構成において、
前記最小コスト経路を求める第3のステップでは、
前記有向無閉路グラフにより定義される半順序によりトポロジカルソートした順序で前記格子点ごとに該格子点に至る経路の最小経路コストを順次計算する際に、
最小経路コストを求める対象である第1の格子点を終点とする有向辺の始点となる第2の格子点のすべてについて、
該第2の格子点の計算済みの最小経路コストに負または0の値を持つものがある場合には、その負または0の値の中での最小値に第1の格子点のコストを足した値を、第1の格子点へ至る経路の最小経路コストとし、さらに、該最小値の最小経路コストを有する第2の格子点を第1の格子点の親の格子点として記憶し、
該第2の格子点の計算済みの最小経路コストが例外なく正の値である場合には、第1の格子点のコストを第1の格子点の最小経路コストとするとともに、第1の格子点を始端候補として記憶し、
すべての前記格子点にて最小経路コストを計算したのちに、その中で最小の値を持つ格子点を終端と定め、
該終端である格子点を始まりとして、格子点から上記親の格子点を繰り返し求めるバックトラック手順を行い、
該バックトラック手順にて前記始端候補と記憶された格子点が前記親の格子点となった際には該格子点を始端と定めて繰り返しを終了し、
得られた終端と始端とを両端としてバックトラック手順で現れた格子点を前記有向辺でつないだ経路を最小コスト経路とすることを特徴とする。
The third configuration of the method for associating two element sequences according to the present invention is as follows:
In the first configuration or the second configuration,
In the third step of obtaining the minimum cost path,
When sequentially calculating the minimum path cost of the path to the grid point for each grid point in the order topologically sorted by the semi-order defined by the directed acyclic graph,
For all of the second grid points that are the starting points of the directed sides that end at the first grid point that is the target for which the minimum path cost is to be calculated,
When there is a negative or zero value in the calculated minimum path cost of the second grid point, the cost of the first grid point is added to the minimum value among the negative or zero values. The obtained value is set as the minimum path cost of the path to the first grid point, and the second grid point having the minimum path cost of the minimum value is stored as the parent grid point of the first grid point;
If the calculated minimum path cost of the second grid point is a positive value without exception, the cost of the first grid point is set as the minimum path cost of the first grid point, and the first grid point Remember the point as a starting point candidate,
After calculating the minimum path cost at all the lattice points, the lattice point having the smallest value among them is defined as the end point,
Starting from the lattice point that is the end, a backtrack procedure for repeatedly obtaining the parent lattice point from the lattice point is performed,
When the lattice point stored as the starting edge candidate in the backtrack procedure becomes the parent lattice point, the lattice point is determined as the starting edge, and the repetition is ended.
A path obtained by connecting the obtained lattice points appearing in the backtrack procedure with the end and the start as both ends and the directed side is defined as a minimum cost path.
この構成によれば、コストが最小となる経路の始端と終端とが固定されず、第1および第2の要素列の中で対応付けに最初に含まれる始点、および、最後に含まれる終点が固定されないようになる。この性質は、始端終端フリー化として、非特許文献1(2.5項)にも記されており、始点終点付近の不安定部分をスキップすることなどを行うことが出来る。本発明による本発明による始端終端フリー化は、始端終端に全く制限を設けないという意味で、完全な一般化となる。 According to this configuration, the start and end of the path with the lowest cost are not fixed, and the first and second end points included in the association in the first and second element sequences are It will not be fixed. This property is also described in Non-Patent Document 1 (Section 2.5) as making the start / end free, and it is possible to skip an unstable portion near the start / end. The free end-to-end according to the present invention according to the present invention is a complete generalization in the sense that there is no restriction on the start-end end.
本発明に係る2つの要素列の対応付け方法の第4の構成は、
前記第3の構成において、
前記始端候補および前記終端の少なくとも1つについて、前記第3のステップにて決定する際に、あらかじめ定めた条件を満たす格子点のみを、前記始端候補および前記終端と決定する対象とすることを特徴とする。
A fourth configuration of the method for associating two element sequences according to the present invention is as follows.
In the third configuration,
When at least one of the starting edge candidate and the terminal end is determined in the third step, only lattice points that satisfy a predetermined condition are set as objects to be determined as the starting edge candidate and the terminal end. And
この構成によれば、始端終端フリー化により決まる始端終端の位置を、2つの要素列を対応付ける処理の対象となる事象の固有の性質に基づき、適当な範囲内とすることが出来る。 According to this configuration, the position of the start end / end determined by making the start / end end free can be set within an appropriate range based on the inherent property of the event that is the target of the process of associating the two element strings.
本発明に係る2つの要素列の対応付け装置の第1の構成は、
第1の要素列と第2の要素列とを比較して、第1の要素列の要素と第2の要素列の要素との組を1つ以上含む対応付けを得る際に、
第1の要素列の要素による集合と第2の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第1の手段と、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第1の要素列の要素と第2の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第2の手段と、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで2つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第3の手段と、
求めた最小コスト経路に含まれる格子点の第1の要素列の要素と第2の要素列の要素との組の集合を第1の要素列と第2の要素列との対応付けの結果とする第4の手段と、
を有する、要素列間対応付け装置において、
前記第1の手段では、
前記有向無閉路グラフにより定義される半順序での、有向辺の始点側を上位、終点側を下位とした順序関係にて、
すべての該順序関係にある上位の格子点と下位の格子点について、該上位の格子点から該下位の格子点への有向辺を設けるように、前記有向無閉路グラフを構成することと、
前記第2の手段では、
前記要素列の対応付けの目的において、前記格子点を構成する第1の要素列の要素と第2の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値0のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする。
The first configuration of the device for associating two element sequences according to the present invention is as follows:
When the first element sequence is compared with the second element sequence to obtain an association including one or more pairs of elements of the first element sequence and elements of the second element sequence,
On a lattice space that is a Cartesian product set of a set of elements of the first element sequence and a set of elements of the second element sequence,
A first directed acyclic graph is formed by providing a plurality of directed edges with a point in the lattice space as a lattice point, one lattice point as a start point, and another lattice point as an end point so as not to cause a cycle. Means of
For all the grid points included as vertices in the directed acyclic graph, the cost is determined for each combination of the elements of the first element sequence and the elements of the second element sequence constituting each grid point. A second means for the cost of the grid points;
A route that connects two or more directed edges in succession by repeating the connection of two directed edges by matching the end point of the directed edge on the directed acyclic graph with the start point of another directed edge. age,
The total cost of the grid points included as the start point or end point of the directed side in the route is defined as the route cost.
The lattice points are sequentially processed in a topologically sorted order according to the semi-order defined by the directed acyclic graph, and the route that minimizes the route cost to the lattice point and the minimum route cost are obtained. A third means for determining a minimum cost path in the directed acyclic graph by dynamic programming;
A set of sets of elements of the first element sequence and elements of the second element sequence of the grid points included in the determined minimum cost path, and a result of associating the first element sequence with the second element sequence A fourth means to:
In the inter-element string association device having
In the first means,
In a partial order defined by the directed acyclic graph, in an order relationship in which the start point side of the directed edge is higher and the end point side is lower,
Configuring the directed acyclic graph so as to provide directed edges from the upper grid point to the lower grid point for all the upper grid points and the lower grid points in the order relationship; ,
In the second means,
For the purpose of associating the element strings, associating the elements of the first element string and the elements of the second element string constituting the lattice points is a negative cost when the object is met. If the cost is not positive, the cost of the positive value, if not, the value 0 is the cost of the grid point.
Mixing lattice points with negative cost and non-negative cost points,
It is characterized by.
本発明に係る2つの要素列の対応付け装置の第2の構成は、
第1の要素列と第2の要素列とを比較して、第1の要素列の要素と第2の要素列の要素との組を1つ以上含む対応付けを得る際に、
第1の要素列の要素による集合と第2の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第1の手段と、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第1の要素列の要素と第2の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第2の手段と、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで2つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第3の手段と、
求めた最小コスト経路に含まれる格子点の第1の要素列の要素と第2の要素列の要素との組の集合を第1の要素列と第2の要素列との対応付けの結果とする第4の手段と、
を有する、要素列間対応付け装置において、
前記第1の手段では、
前記第1の要素列の要素数をIとし、前記第2の要素列の要素数をJとし、前記Iと前記Jとの2つの値に応じて、I2J2に比例する数の有向辺を設けて、前記有向無閉路グラフを構成することと、
前記第2の手段では、
前記要素列の対応付けの目的において、前記格子点を構成する第1の要素列の要素と第2の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値0のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする。
The second configuration of the device for associating two element sequences according to the present invention is as follows:
When the first element sequence is compared with the second element sequence to obtain an association including one or more pairs of elements of the first element sequence and elements of the second element sequence,
On a lattice space that is a Cartesian product set of a set of elements of the first element sequence and a set of elements of the second element sequence,
A first directed acyclic graph is formed by providing a plurality of directed edges with a point in the lattice space as a lattice point, one lattice point as a start point, and another lattice point as an end point so as not to cause a cycle. Means of
For all the grid points included as vertices in the directed acyclic graph, the cost is determined for each combination of the elements of the first element sequence and the elements of the second element sequence constituting each grid point. A second means for the cost of the grid points;
A route that connects two or more directed edges in succession by repeating the connection of two directed edges by matching the end point of the directed edge on the directed acyclic graph with the start point of another directed edge. age,
The total cost of the grid points included as the start point or end point of the directed side in the route is defined as the route cost.
The lattice points are sequentially processed in a topologically sorted order according to the semi-order defined by the directed acyclic graph, and the route that minimizes the route cost to the lattice point and the minimum route cost are obtained. A third means for determining a minimum cost path in the directed acyclic graph by dynamic programming;
A set of sets of elements of the first element sequence and elements of the second element sequence of the grid points included in the determined minimum cost path, and a result of associating the first element sequence with the second element sequence A fourth means to:
In the inter-element string association device having
In the first means,
The number of elements in the first element row is I, the number of elements in the second element row is J, and there are a number proportional to I 2 J 2 according to the two values I and J. Providing a directed edge to construct the directed acyclic graph;
In the second means,
For the purpose of associating the element strings, associating the elements of the first element string and the elements of the second element string constituting the lattice points is a negative cost when the object is met. If the cost is not positive, the cost of the positive value, if not, the value 0 is the cost of the grid point.
Mixing lattice points with negative cost and non-negative cost points,
It is characterized by.
本発明に係る2つの要素列の対応付け装置の第3の構成は、
装置の前記第1の構成、または装置の前記第2の構成において、
前記最小コスト経路を求める第3の手段では、
前記有向無閉路グラフにより定義される半順序によりトポロジカルソートした順序で前記格子点ごとに該格子点に至る経路の最小経路コストを順次計算する際に、
最小経路コストを求める対象である第1の格子点を終点とする有向辺の始点となる第2の格子点のすべてについて、
該第2の格子点の計算済みの最小経路コストに負または0の値を持つものがある場合には、その負または0の値の中での最小値に第1の格子点のコストを足した値を、第1の格子点へ至る経路の最小経路コストとし、さらに、該最小値の最小経路コストを有する第2の格子点を第1の格子点の親の格子点として記憶し、
該第2の格子点の計算済みの最小経路コストが例外なく正の値である場合には、第1の格子点のコストを第1の格子点の最小経路コストとするとともに、第1の格子点を始端候補として記憶し、
すべての前記格子点にて最小経路コストを計算したのちに、その中で最小の値を持つ格子点を終端と定め、
該終端である格子点を始まりとして、格子点から上記親の格子点を繰り返し求めるバックトラック手順を行い、
該バックトラック手順にて前記始端候補と記憶された格子点が前記親の格子点となった際には該格子点を始端と定めて繰り返しを終了し、
得られた終端と始端とを両端としてバックトラック手順で現れた格子点を前記有向辺でつないだ経路を最小コスト経路とすることを特徴とする。
A third configuration of the device for associating two element sequences according to the present invention is as follows.
In the first configuration of the device or the second configuration of the device,
In the third means for obtaining the minimum cost route,
When sequentially calculating the minimum path cost of the path to the grid point for each grid point in the order topologically sorted by the semi-order defined by the directed acyclic graph,
For all of the second grid points that are the starting points of the directed sides that end at the first grid point that is the target for which the minimum path cost is to be calculated,
When there is a negative or zero value in the calculated minimum path cost of the second grid point, the cost of the first grid point is added to the minimum value among the negative or zero values. The obtained value is set as the minimum path cost of the path to the first grid point, and the second grid point having the minimum path cost of the minimum value is stored as the parent grid point of the first grid point;
If the calculated minimum path cost of the second grid point is a positive value without exception, the cost of the first grid point is set as the minimum path cost of the first grid point, and the first grid point Remember the point as a starting point candidate,
After calculating the minimum path cost at all the lattice points, the lattice point having the smallest value among them is defined as the end point,
Starting from the lattice point that is the end, a backtrack procedure for repeatedly obtaining the parent lattice point from the lattice point is performed,
When the lattice point stored as the starting edge candidate in the backtrack procedure becomes the parent lattice point, the lattice point is determined as the starting edge, and the repetition is ended.
A path obtained by connecting the obtained lattice points appearing in the backtrack procedure with the end and the start as both ends and the directed side is defined as a minimum cost path.
本発明に係る2つの要素列の対応付け装置の第4の構成は、
装置の前記第3の構成において、
前記始端候補および前記終端の少なくとも1つについて、前記第3の手段にて決定する際に、あらかじめ定めた条件を満たす格子点のみを、前記始端候補および前記終端と決定する対象とすることを特徴とする。
A fourth configuration of the device for associating two element sequences according to the present invention is as follows.
In the third configuration of the apparatus,
When at least one of the starting edge candidate and the terminal end is determined by the third means, only lattice points that satisfy a predetermined condition are set as objects to be determined as the starting edge candidate and the terminal end. And
本発明に係るプログラムの構成は、前記第1乃至第4の構成に係る要素列間対応付け方法をコンピュータに実行させることを特徴とする。 The configuration of the program according to the present invention is characterized by causing a computer to execute the element sequence correlation method according to the first to fourth configurations.
以上説明したように、本発明によれば、2つの要素列間の対応付けにおいて、第1の特徴である対応付けを決定するために用いるDP平面上に構成する有向非閉路グラフを有向辺が十分な数だけあるものすることにより、スキップや始端終端の位置に制約が少ない柔軟な対応付けが可能となる。また、第2の特徴である、対応付ける要素間のコストであるDP平面上の格子点のコストを、格子点に対応する要素間を対応付けるべきであれば負のコストとし、そうでなければ非負のコストにして、負のコストの格子点と非負のコストの格子点とを混在させることにより、経路コストの最小を得るように経路を決定する動的計画法が適用されると、負のコストを持つ格子点を経由することを積極的に求め、正のコストを持つ格子点を経由することを避けるように、経路が決定される。これにより、制限が無いことにより意図しない対応付けとなる事態を起こさないようになるとともに、負と非負とにコストを定めた基準に沿った対応付けを得ることが出来る。 As described above, according to the present invention, in the association between two element sequences, the directed acyclic graph configured on the DP plane used for determining the association that is the first feature is directed. By having a sufficient number of sides, flexible association with less restrictions on the positions of the skip and the start / end is possible. In addition, the second feature, which is the cost between lattice points on the DP plane, which is the cost between corresponding elements, is a negative cost if the elements corresponding to the lattice points should be associated with each other. When dynamic programming is used to determine the path to obtain the minimum path cost by mixing negative cost grid points and non-negative cost grid points, the negative cost is reduced. The route is determined so as to positively seek to go through a grid point that has, and avoid going through a grid point having a positive cost. As a result, it is possible to prevent the occurrence of an unintended association due to the absence of a restriction, and to obtain an association according to a standard in which costs are defined as negative and non-negative.
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。 The best mode for carrying out the present invention will be described below with reference to the drawings.
最初に上述の式(2)〜(5)で示した従来技術との比較が可能なように、本発明での対応付け方法の定式化を行う。従来技術の説明においてもその定式化は多様な方法のうちの一例を示したが、本発明での定式化も多様な方法のうちの一例となる。定式化は、可能な限り一般性のあるものとしている。 First, the association method in the present invention is formulated so that the comparison with the prior art shown by the above-described equations (2) to (5) is possible. In the description of the prior art, the formulation shows an example of various methods, but the formulation in the present invention is an example of various methods. The formulation is as general as possible.
実施例1における対応付けの対象は、従来技術での定式化と同じく、式(1)に示す2つの要素列、XとYとする。 The correspondence targets in the first embodiment are the two element strings X and Y shown in Formula (1), as in the conventional formulation.
式(2)に示した従来技術の例での対応付けの定式化では、iの値がひとつずつ増える連続性制約を前提としていた。従来技術のDPマッチングにおいてもiの値がひとつずつ増える連続性制約は必須のものではなく、式(2)は非特許文献1第2節に記述された一例に従ったものである。本発明においては、iの値がひとつずつ増える連続性制約は課さない方が一般的であるため、次の式(6)のように対応付けを定式化する。すなわち、単純にiとjとの組の集合(直積の部分集合)Uで対応付けを表す。 In the formulation of the association in the example of the prior art shown in Expression (2), the continuity constraint in which the value of i increases by one is assumed. In the conventional DP matching, the continuity constraint in which the value of i is incremented by one is not essential, and Equation (2) follows the example described in Section 2 of Non-Patent Document 1. In the present invention, since it is common not to impose a continuity constraint in which the value of i increases one by one, the association is formulated as in the following equation (6). That is, the association is simply represented by a set of i and j (a subset of the direct product) U.
式(7)に示すように、本発明によるコストは、値域が非負となるノルムではなく、負の値も値域に含む一般的な関数とする。 As shown in the equation (7), the cost according to the present invention is not a norm in which the value range is non-negative, but a general function including a negative value in the value range.
式(7)のような正負の値を取るコストは、xiとyjとの間の性質を表す非負の物理量(たとえば2点間の距離、ノルム)に対して境界値(Border Value)を設定し、その境界値を非負の物理量から引いた値をコストとすることで実現できる。すなわち、式(7)の関数fは、式(8)のように定義することで実現できる。 The cost of taking a positive or negative value as in equation (7) is the border value for a non-negative physical quantity (for example, distance between two points, norm) representing the property between x i and y j. This can be realized by setting a cost obtained by subtracting the boundary value from a non-negative physical quantity. That is, the function f of Expression (7) can be realized by defining it as Expression (8).
本発明による実施例となる対応付けの最適化問題を、式(1)(6)(7)を用いて、次の式(9)のように定式化する。従来技術の例である式(4)と異なり、式(9)では単調性制約のみを制約条件としている。単調性制約は、DP平面上に有向無閉路グラフが構成される十分条件であり、これにより動的計画法の適用可能が保証される。しかしながら、必要条件ではなく、単調性制約を課さない定式化も考えられる。多くの場合は、単調性制約を課しても適用範囲が狭められることは無い。 The matching optimization problem according to the embodiment of the present invention is formulated as the following equation (9) using equations (1), (6), and (7). Unlike Equation (4), which is an example of the prior art, Equation (9) uses only the monotonicity constraint as the constraint condition. The monotonicity constraint is a sufficient condition that a directed acyclic graph is constructed on the DP plane, thereby ensuring the applicability of dynamic programming. However, it is not a necessary condition, and a formulation that does not impose a monotonic constraint is also conceivable. In many cases, imposing a monotonic constraint will not narrow the scope of application.
式(10)に、本発明による実施例のDP漸化式を示す。この漸化式の1つめの特徴は、最小値選択範囲が固定でなく、iとjとの増加に伴って大きくなることである。2つめの特徴は、始端を一意に定めていないことである。すなわち、最小値選択範囲内に負か0の値の経路の最小コストが無い場合にはそれらを引き継がず、格子点のコストを経路の最小コストとして、始端候補となることである。 Formula (10) shows the DP recurrence formula of the embodiment according to the present invention. The first feature of this recurrence formula is that the minimum value selection range is not fixed and increases as i and j increase. The second feature is that the starting edge is not uniquely determined. That is, when there is no minimum cost of a negative or zero value route in the minimum value selection range, they are not taken over, and the cost of the grid point is set as the minimum cost of the route and becomes a starting candidate.
図3に、本発明による実施例でのDP漸化式の最小値選択範囲を示す。従来技術の図1での最小値選択範囲の大きさは固定であったのに対し、図3では301の注目する特定の格子点(i,j)について、最小値選択範囲はi×j-1の大きさになっている。このため、従来DPマッチングでの計算量はO(IJ)であったのに対して、本発明による対応付けでは、O(I2J2)となる。計算量は増えるが、多項式時間の範囲である。 FIG. 3 shows the minimum value selection range of the DP recurrence formula in the embodiment according to the present invention. While the size of the minimum value selection range in FIG. 1 of the prior art is fixed, in FIG. 3, the minimum value selection range for the specific lattice point (i, j) of 301 is i × j−. The size is one. For this reason, the calculation amount in the conventional DP matching is O (IJ), whereas in the association according to the present invention, it is O (I 2 J 2 ). Although the amount of calculation increases, it is in the range of polynomial time.
図3の最小値選択範囲は特定の格子点301について記しているが、他の格子点についても同様な最小値選択範囲が設定される。これは、動的計画法による最短経路探索が行われる有向無閉路グラフが、有向辺の始点側を上位、終点側を下位とした半順序において、上位下位の順序関係が存在する2つの格子点においては、必ず上位の格子点から下位の格子点へ有向辺を有するものであることを示している。このように本発明の特徴の一つは、動的計画法を適用する有向無閉路グラフの形状として表すことが出来る。 Although the minimum value selection range in FIG. 3 is described for a specific grid point 301, the same minimum value selection range is set for other grid points. This is because the directed acyclic graph in which the shortest path search by dynamic programming is performed has two high order subordinate relations in the semi-order in which the start point side of the directed edge is high and the end point is low. The grid points always have a directed side from the upper grid point to the lower grid point. Thus, one of the features of the present invention can be expressed as a shape of a directed acyclic graph to which dynamic programming is applied.
式(10)によりすべての格子点での経路の最小コストを求めた後、本発明の実施例での終端(ie,je)を、次の式(11)に従って、経路の最小コストが一番小さい格子点として求める。すなわち、終端も固定されていない。すべてのコストが非負の場合は必ずgI,Jが最小となるが、負のコストを導入されているため、gI,Jが最小とは限らない。 After obtaining the minimum cost of the route at all grid points according to equation (10), the end cost (i e , j e ) in the embodiment of the present invention is set to the minimum cost of the route according to the following equation (11). Obtained as the smallest grid point. That is, the end is not fixed. When all costs are non-negative, g I, J is always the minimum, but since negative costs are introduced, g I, J is not necessarily the minimum.
本発明による実施例でも、対応付けは、終端から始端へDP漸化式での最小値の選択に基づくバックトラック手順により得られる。終端は、式(11)に示した条件により確定される。この終端よりバックトラック手順を行い、辿りついた式(10)での始端候補が始端となる。 Also in the embodiment according to the present invention, the association is obtained by a backtrack procedure based on the selection of the minimum value in the DP recurrence formula from the end to the start. The end point is determined by the condition shown in Expression (11). The backtrack procedure is performed from this end point, and the start end candidate in the formula (10) that has been reached becomes the start end.
このように始端終端を固定しない本発明による実施例は、非特許文献1に記された“始端終端のフリー化”の完全な一般化となっている。図4を用いて、本発明による“始端終端のフリー化”の説明を行う。図4中、410のDP平面上には式(6)〜(11)で定式化した本発明による実施例で有り得る最小コストの経路の例が示してあり、420のDP平面上には式(1)〜(5)で定式化した従来DPマッチングで有り得る最小コストの経路の例が示してある。図4中420のDP平面上に示すように、式(1)〜(5)で定式化した従来DPマッチングにおいては、式(4)中に示したu1=1、および、uI=Jの条件により、始端(441)と終端(461)とは固定されており、動的計画法により得られる経路はいずれもこれらを両端としている。これに対して本発明による実施例での要素列間の対応付けではすべての格子点が始端終端となる可能性があるため、図4中410のDP平面上に示すように、始端(431,432,433)、および、終端(451,452,453)を異にした経路が動的計画法により得られる。すなわち、式(11)により得られる終端は固定的でなく、この終端からバックトラックにより辿りつく始端候補も固定的ではない。 The embodiment according to the present invention in which the start end is not fixed as described above is a complete generalization of “free start end” described in Non-Patent Document 1. With reference to FIG. 4, “free start / end termination” according to the present invention will be described. In FIG. 4, an example of a minimum cost path that can be an embodiment according to the present invention formulated by the equations (6) to (11) is shown on the DP plane 410, and the equation ( The example of the path | route of the minimum cost which can be the conventional DP matching formulated in 1)-(5) is shown. As shown on the DP plane 420 in FIG. 4, in the conventional DP matching formulated by the equations (1) to (5), u 1 = 1 and u I = J shown in the equation (4). The start end (441) and the end end (461) are fixed by the above conditions, and any of the paths obtained by the dynamic programming has both ends. On the other hand, since there is a possibility that all the lattice points may be the start end in the association between the element sequences in the embodiment according to the present invention, as shown on the DP plane 410 in FIG. 432, 433) and paths having different end points (451, 452, 453) are obtained by dynamic programming. That is, the end point obtained by the equation (11) is not fixed, and the start end candidate that reaches from the end point by backtracking is not fixed.
図5を用いて、本発明による実施例での負のコストの役割について説明する。すなわち、式(7)(8)に記したコストにより、図3のような最小値選択範囲としても、意図しない極端な対応付けとならない理由を説明する。図5中では負のコストの役割に絞って説明するため、簡略化した表記を用いている。すなわち、格子状の各辺にはその辺の始点から終点へのコストが記しており、これ以外の始点と終点の組み合わせの場合は、図には記されていないがコストを0とする。 The role of negative costs in the embodiment according to the present invention will be described with reference to FIG. That is, the reason why the minimum value selection range as shown in FIG. 3 does not result in unintended extreme association due to the costs described in the equations (7) and (8) will be described. In FIG. 5, a simplified notation is used in order to explain only the role of negative costs. That is, the cost from the start point to the end point of each side of the grid is written on each grid-like side, and in the case of other combinations of the start point and the end point, the cost is set to 0 although not shown in the figure.
図5中510のDP平面上では、記されたコストはすべて正であり、記されていないコストを含めてすべて非負である。この際に左下の丸印の始端(531)から右上の四角印の終端(551)への最小コスト経路は、図に示すように始端と終端とを直接結んだ経路となり、経路の最小コストは0となる。この510のDP平面上の経路は、意図しない極端な対応付けの例となっている。 On the DP plane 510 in FIG. 5, all the costs listed are positive and all are non-negative including the costs not listed. At this time, the minimum cost route from the start end (531) of the lower left circle to the end (551) of the upper right square is a route directly connecting the start and end as shown in the figure, and the minimum cost of the route is 0. The route on the DP plane 510 is an example of an unintended extreme correspondence.
一方、図5中520のDP平面上に記されたコストは、501での対応する辺のコストから10を引いた数値であり、全て負となっている。記されていないコストを合わせて、520のコストはすべて0以下である。この際に左下の丸印の始端(541)から右上の四角印の終端(561)への最小コスト経路は、図に示すように負のコスト値の小さいもの(絶対値が大きいもの)を選んで構成されており、合計コストは、(−8)+(−7)+(−7)+(−9)+(−8)で計算される、−39となる。 On the other hand, the cost indicated on the DP plane 520 in FIG. 5 is a numerical value obtained by subtracting 10 from the cost of the corresponding side at 501 and is all negative. Including the costs not listed, the costs of 520 are all 0 or less. At this time, the minimum cost path from the start point (541) of the lower left circle mark to the end point (561) of the upper right square mark is selected as having a small negative cost value (having a large absolute value) as shown in the figure. The total cost is −39, which is calculated by (−8) + (− 7) + (− 7) + (− 9) + (− 8).
図5で説明したように、負のコストを導入すれば対応付けの個数(|U|)が大きい(経路のエッジの数が多い)ほどコスト最小化に向かう性質を帯びる。逆にすべての対応付けコストが非負であれば、|U| が大きいほどコストが増えて最適解から遠ざかる性質を帯びる.すなわち、負のコストを導入すれば積極的(アグレッシブ) に多くの対応付けの個数(|U|) を得ようとするのに対し,コストが非負であれば対応付けの個数を増やすことには消極的になる。式(1)〜(5)による従来DPマッチングでの傾斜制限や始端終端の固定は、コストの増加を嫌って対応付けを避ける性質に対して、対応付けを強制する働きがある。すなわち、傾斜制限の条件下でコストを生じる対応付けをなるべく避けた解を求めるよう、従来DPマッチングは働く。 As described with reference to FIG. 5, when a negative cost is introduced, the larger the number of associations (| U |) is (the more the number of edges of the path is), the more the cost tends to be minimized. On the other hand, if all the matching costs are non-negative, the cost increases as | U | In other words, if a negative cost is introduced, the number of associations (| U |) will be obtained aggressively, but if the cost is non-negative, the number of associations should be increased. Become passive. Inclination restriction and fixation of the start end in conventional DP matching according to equations (1) to (5) have a function of forcing the association against the property of avoiding the association while avoiding the increase in cost. In other words, the conventional DP matching works so as to obtain a solution that avoids associating as much as possible under conditions of tilt restriction.
これに対して、本発明による実施例では、コストを避けるのではなく、負のコストを求めて積極的に対応付けを増やそうとする方向に最適化が働く。これにより,コストを避けた短絡的な最小解を防ぐことを目的とする、固定的な最小値選択範囲を設ける必要が無くなる。 On the other hand, in the embodiment according to the present invention, optimization works not to avoid cost but to try to increase the association positively by obtaining negative cost. This eliminates the need to provide a fixed minimum value selection range for the purpose of preventing a short-circuited minimum solution that avoids costs.
なお、DPマッチングではなく一般的な動的計画法を有向無閉路グラフに適用する場合、負の重み付けを持つネットワークの最短経路探索問題では、“エッジの数が多い経路”を探索するように性質が変わることは,教科書にも記されている(例えば、R. Sedgewick, Algorithms in Java(登録商標) Third Edition Part 5:Graph Algorithms, Addison Wesley, 2003.など)。 When applying general dynamic programming to directed acyclic graphs instead of DP matching, search for “routes with many edges” in the shortest route search problem for networks with negative weights. Changes in properties are also noted in textbooks (eg, R. Sedgewick, Algorithms in Java® Third Edition Part 5: Graph Algorithms, Addison Wesley, 2003.).
以上、式(6)〜(11)により、本発明による実施例での2つの要素列の対応付け問題の定式化を行った。式(6)〜(11)の実施例ではなるべく一般的な定式化を行っているが、これよりも制約条件を多くしても良い。 As described above, the correspondence problem between two element sequences in the embodiment according to the present invention has been formulated by the equations (6) to (11). In the embodiments of the formulas (6) to (11), a general formulation is performed as much as possible, but more restrictive conditions may be used.
例えば式(10)および図3に示す最小値選択範囲は、適用する対象の性質に合わせて、条件を課して狭くする場合もあり得る。例えば前記第1の要素列の特定の要素については、前記第2の要素列のうち特定の複数要素のいずれかと対応させなければならない条件がある場合、この条件に合わせて部分的に最小値選択範囲を狭くしても良い。 For example, the minimum value selection range shown in Expression (10) and FIG. 3 may be narrowed by imposing conditions according to the properties of the target to be applied. For example, for a specific element in the first element row, if there is a condition that must correspond to any one of a plurality of specific elements in the second element row, a minimum value is partially selected according to this condition. The range may be narrowed.
また、従来のDPマッチングで計算量を削減するために行われている“枝刈り”の処理を、本発明の実施例に適用することも可能である。“枝刈り”は、経路コストが最小となる可能性が小さい経路を見出してその計算を行わないようにする処理である。そのような枝刈りは動的計画法を適用する有向無閉路グラフの形状を変更している訳ではなく、本発明の要件には関わらない。 In addition, the “pruning” process performed to reduce the amount of calculation in the conventional DP matching can be applied to the embodiment of the present invention. “Pruning” is a process for finding a route with a low possibility of minimizing the route cost and not performing the calculation. Such pruning does not change the shape of the directed acyclic graph to which dynamic programming is applied, and does not relate to the requirements of the present invention.
また、始端終端についても、制限を加えても良い。従来DPマッチングのように始端終端を固定としても良いし、終端や始端候補を決める際に条件を課しても良い。例えば終端は、DP平面上で(I,J)から一定距離範囲の格子点の中で、経路の最小コストが最小であるものを選んでも良い。 Moreover, you may add a restriction | limiting also about a start end. As in conventional DP matching, the start end may be fixed, or conditions may be imposed when determining the end and start end candidates. For example, the termination may be selected from the lattice points within a fixed distance range from (I, J) on the DP plane, with the minimum path cost.
次に具体的な数値を伴った対象に対する、本発明の実施例を、図を用いて説明する。対応付けの対象となる2つの要素列を、式(12)に示す通り、2次元平面上の点列とする。 Next, embodiments of the present invention for objects with specific numerical values will be described with reference to the drawings. Two element sequences to be associated are set as point sequences on a two-dimensional plane as shown in Expression (12).
対応する点の間のマンハッタン距離(各座標の差の絶対値の総和)を、コストの基になる物理量とする。すなわち、式(8)での||xi-yj||は、表1のとおりとなる。 The Manhattan distance between the corresponding points (the sum of the absolute values of the differences between the coordinates) is the physical quantity that is the basis of the cost. That is, || x i -y j || in Expression (8) is as shown in Table 1.
図6に、要素間のコストを定める際に表1のマンハッタン距離による物理量から減じる境界値を変えた場合に、得られる対応付けが変わる様子を示す。図6には、縦方向に並んだ“(a)境界値=0”(610)、“(b) 境界値=4”(620)、“(c)境界値=8”(630)のそれぞれの場合について,横方向に並んだ[対応付け1](601)、[対応付け2](602)、[対応付け3](603)の3つの対応付けの合計コストとその計算の内訳が示されている。図6中の661、662、663は、それぞれの対応付けの集合による表現を示す。 FIG. 6 shows how the obtained association changes when the boundary value subtracted from the physical quantity based on the Manhattan distance in Table 1 is changed when determining the cost between elements. In FIG. 6, “(a) boundary value = 0” (610), “(b) boundary value = 4” (620), and “(c) boundary value = 8” (630) arranged in the vertical direction. In the case of [3], the total cost of the three associations [correspondence 1] (601), [association 2] (602), and [association 3] (603) arranged in the horizontal direction and the breakdown of the calculation are shown Has been. Reference numerals 661, 662, and 663 in FIG.
図6中640に式(12)のXの点列を、650にYの点列を、それぞれ図示する。なお、図6中に図示する2次元平面では、x軸は右方向、y軸は下方向、左上端が原点としている。 In FIG. 6, an X point sequence of Formula (12) is shown at 640, and a Y point sequence is shown at 650. In the two-dimensional plane shown in FIG. 6, the x axis is the right direction, the y axis is the downward direction, and the upper left corner is the origin.
図6中641、および、651は、[対応付け1]により対応付けられた点列X中の点、および、点列Y中の点を、矢印で結んで示したものである。同様に、642と652は[対応付け2]の、643と653は[対応付け3]の、対応付けられた点列X中の点、および、点列Y中の点を、矢印で結んで示したものである。 In FIG. 6, reference numerals 641 and 651 denote points in the point sequence X and points in the point sequence Y that are associated by [Association 1] connected by arrows. Similarly, the points 642 and 652 in [Association 2] and 643 and 653 [Association 3] in the point sequence X and the points in the point sequence Y are connected by arrows. It is shown.
なお、図6の例では、分かりやすさのために、対応付けは1対1で,2つ以上の対応があるという制約条件を設けて、対応付けを行っている。 In the example of FIG. 6, for easy understanding, the association is performed by providing a constraint condition that the association is one-to-one and there are two or more correspondences.
図6(a)の“境界値=0”(610)の場合は,傾斜制限の無い従来DPマッチングと同じことになるため、意図しない極端な対応付けである[対応付け1](661、U={(x1,y1), (x4,y3)})での合計コストが1となり、最適解となっている。このコストの内訳を、611に示す。x1とy1とを対応付けることによるコストは、表1中に示した2点間のマンハッタン距離である“0”から、境界値である“0”を引いて、“(0 - 0)”として求められる。x4とy3とを対応付けることによるコストは、表1中に示した2点間のマンハッタン距離である“1”から、境界値である“0”を引いて、“(1 - 0)”として求められる。これら2つのコストを合計した“1”が[対応付け1]の合計コストであり、同様な方法で求めた[対応付け2]の合計コスト(612)、および、[対応付け3]の合計コスト(613)よりも小さく、最小値となっている。 In the case of “boundary value = 0” (610) in FIG. 6 (a), this is the same as the conventional DP matching without tilt restriction, and thus [Uncorresponding extreme association [association 1] (661, U = {(x 1 , y 1 ), (x 4 , y 3 )}), the total cost is 1, which is an optimal solution. A breakdown of this cost is shown at 611. The cost of associating x 1 with y 1 is “(0−0)” by subtracting “0” as the boundary value from “0” as the Manhattan distance between the two points shown in Table 1. As required. The cost of associating x 4 with y 3 is “(1−0)” by subtracting “0” as the boundary value from “1”, which is the Manhattan distance between the two points shown in Table 1. As required. “1”, which is the sum of these two costs, is the total cost of [Association 1]. The total cost of [Association 2] (612) and the total cost of [Association 3] obtained by the same method. It is smaller than (613) and has a minimum value.
図6(b)の“境界値=4”(620)の場合は、「距離が“4”以内であれば類似しているとして対応付けたほうが良く、それ以上であれば対応付けない方が良い」ということを意味する。この基準に従うと、[対応付け2](662、U={(x1,y1), (x2,y2), (x4,y3)})での合計コストが−9となり、最適解となっている。このコストの内訳を、622に示す。x1とy1とを対応付けることによるコストは、表1中に示した2点間のマンハッタン距離である“0”から、境界値である“4”を引いて、“(0 - 4)”として求められる。x2とy2とを対応付けることによるコストは、表1中に示した2点間のマンハッタン距離である“2”から、境界値である“4”を引いて、“(2 - 4)”として求められる。x4とy3とを対応付けることによるコストは、表1中に示した2点間のマンハッタン距離である“1”から、境界値である“4”を引いて、“(1 - 4)”として求められる。これら3つのコストを合計した“−9”が[対応付け2]の合計コストであり、同様な方法で求めた[対応付け1]の合計コスト(621)、および、[対応付け3]の合計コスト(623)よりも小さく、最小値となっている。 In the case of “boundary value = 4” (620) in FIG. 6B, it is better to associate as “similar if the distance is within“ 4 ”, and not to associate otherwise. It means "good". According to this criterion, the total cost in [Association 2] (662, U = {(x 1 , y 1 ), (x 2 , y 2 ), (x 4 , y 3 )}) is −9, It is an optimal solution. A breakdown of this cost is shown at 622. The cost of associating x 1 with y 1 is “(0 − 4)” by subtracting “4” as the boundary value from “0” which is the Manhattan distance between the two points shown in Table 1. As required. The cost of associating x 2 with y 2 is “(2 − 4)” by subtracting the boundary value “4” from the Manhattan distance “2” between the two points shown in Table 1. As required. The cost of associating x 4 with y 3 is “(1-4)” by subtracting the boundary value “4” from the Manhattan distance “1” between the two points shown in Table 1. As required. “−9”, which is the sum of these three costs, is the total cost of [Association 2]. The total cost of [Association 1] (621) obtained by the same method and the sum of [Association 3] It is smaller than the cost (623) and has a minimum value.
図6(c)の“境界値=8”(630)の場合は,「距離が“8”以内であれば対応付けた方が良い」ということを意味し、マス目の縦横が5であるので、ほとんどの場合は遠くても対応付けたほうが良いことになる。この結果、[対応付け3](663、U={(x1,y1), (x2,y2), (x3,y3), (x4,y4)})での合計コストが−22となり、最適解となる。このコストの内訳を、633に示す。x1とy1とを対応付けることによるコストは、表1中に示した2点間のマンハッタン距離である“0”から、境界値である“8”を引いて、“(0 - 8)”として求められる。x2とy2とを対応付けることによるコストは、表1中に示した2点間のマンハッタン距離である“2”から、境界値である“8”を引いて、“(2 - 8)”として求められる。x3とy3とを対応付けることによるコストは、表1中に示した2点間のマンハッタン距離である“5”から、境界値である“8”を引いて、“(5 - 8)”として求められる。x4とy4とを対応付けることによるコストは、表1中に示した2点間のマンハッタン距離である“3”から、境界値である“8”を引いて、“(3 - 8)”として求められる。これら4つのコストを合計した“−22”が[対応付け3]の合計コストであり、同様な方法で求めた[対応付け1]の合計コスト(631)、および、[対応付け2]の合計コスト(632)よりも小さく、最小値となっている。 In the case of “boundary value = 8” (630) in FIG. 6C, it means that “if the distance is within“ 8 ”, it is better to associate”, and the vertical and horizontal dimensions of the square are 5. Therefore, in most cases, it is better to associate them even if they are far away. Total in this result, [correspondence 3] (663, U = { (x 1, y 1), (x 2, y 2), (x 3, y 3), (x 4, y 4)}) The cost is -22, which is an optimal solution. A breakdown of this cost is shown at 633. The cost for associating x 1 with y 1 is “(0-8)” by subtracting “8” as the boundary value from “0”, which is the Manhattan distance between the two points shown in Table 1. As required. The cost of associating x 2 with y 2 is “(2 − 8)” by subtracting the boundary value “8” from the Manhattan distance “2” shown in Table 1 As required. The cost of associating x 3 with y 3 is “(5-8)” by subtracting the boundary value “8” from the Manhattan distance “5” between the two points shown in Table 1. As required. The cost of associating x 4 with y 4 is “(3-8)” by subtracting the boundary value “8” from the Manhattan distance “3” between the two points shown in Table 1. As required. “−22”, which is the sum of these four costs, is the total cost of [Association 3]. The total cost (631) of [Association 1] obtained by the same method and the sum of [Association 2] It is smaller than the cost (632) and is the minimum value.
仮に「2つの点列により構成されるポリラインのうち、人が見て類似したものを探し出す」という目的であれば,図6中の642と652との点列の図示が似ているという意味で、“境界値=4”(620)がこれに比較的適う。例えば漢字書き取り自動採点装置において、正答となる漢字中の画と、これに対応する入力された漢字中の画とについて、画を構成する辺を対応付ける応用へは、この類似したポリラインを探し出す方法が適用可能である。さまざまな応用分野の目的に応じて、この境界値は決めれば良い。単純な方法としては、要素列間のすべての要素の組み合わせにおけるコストの平均値や中央値を境界値とすることが考えられる。 For the purpose of “finding a polyline composed of two point sequences and finding similar ones by human beings”, it means that the point sequences of 642 and 652 in FIG. 6 are similar. “Boundary value = 4” (620) is relatively suitable for this. For example, in an automatic scoring system for writing kanji characters, there is a method to find a similar polyline for the application that associates the edges that make up an image in the correct kanji and the corresponding image in the input kanji. Applicable. This boundary value may be determined according to the purpose of various application fields. As a simple method, it is conceivable to use the average value or the median value of the costs in the combination of all elements between the element sequences as the boundary value.
また、図6の(b)の“境界値=4”(620)の場合、最適解である[対応付け2]において、y4は対応付けから外れている。これは、上述の“始端終端のフリー化”の例となっている。 In addition, in the case of “boundary value = 4” (620) in FIG. 6B, y 4 is out of association in [association 2] which is the optimal solution. This is an example of the above-mentioned “free start / end”.
実施例2では、実施例1の図3に示した最小値選択範囲を採らず、1対1対応とする制約条件を設けた。実施例3では、このように制約条件を変更した場合の、有向無閉路グラフ上での有向辺の数に関わる条件を明らかにするための実施例を示す。 In the second embodiment, the minimum value selection range shown in FIG. Example 3 shows an example for clarifying conditions related to the number of directed edges on a directed acyclic graph when the constraint condition is changed in this way.
実施例3を示すに先立って、実施例1と実施例2とについて、その有向辺の数を示す。 Prior to showing Example 3, the number of directed sides of Example 1 and Example 2 will be shown.
実施例1では、図3に示す最小値選択範囲をすべての前記有向無閉路グラフ上の格子点で取っており、式(1)中のI、Jを用いて、有向無閉路グラフ上での有向辺の数|E|は、次の式(13)のように表される。 In the first embodiment, the minimum value selection range shown in FIG. 3 is taken at all the lattice points on the directed acyclic graph, and I and J in the equation (1) are used on the directed acyclic graph. The number of directed sides | E | at is expressed as the following equation (13).
実施例2では、「1対1の対応」という制約条件を伴っている。式(1)中のI、Jについて、I=4、J=4となっているが、IとJとに値を代入しないで、有向無閉路グラフ上での有向辺の数|E|は、次の式(14)のように表される。なお、表記を簡易にするために、式(14)ではi’=i-1とj’=j-1という変数の置き換えを行っている。 In the second embodiment, there is a constraint condition of “one-to-one correspondence”. For I and J in Equation (1), I = 4 and J = 4, but without assigning values to I and J, the number of directed edges on the directed acyclic graph | E | Is expressed as the following equation (14). In order to simplify the notation, the variables i ′ = i−1 and j ′ = j−1 are replaced in Equation (14).
式(14)は式(13)の値よりも小さくなるが、I2J2に比例する数であることには変わりない。すなわち、図3に示す最小値選択範囲を小さくする制約条件を課した場合でも、制約条件が図3の最小値選択範囲を割合として小さくする場合には、有向辺の数はI2J2に比例する数となる。図1に示した固定的な最小値選択範囲となるような制約条件を課した場合は、有向辺の数はIJに比例する数となる。この有向辺の数の違いが、本発明による効果の有無に直結している。すなわち、本発明の適用に際して、最小値選択範囲を小さくする制約条件を課すことは出来るが、I2J2に比例する数の有向辺を持つ有向無閉路グラフとすることは必要となる。 Equation (14) is smaller than the value of Equation (13), but it is still a number proportional to I 2 J 2 . That is, even when the constraint condition for reducing the minimum value selection range shown in FIG. 3 is imposed, when the constraint condition reduces the minimum value selection range in FIG. 3 as a percentage, the number of directed sides is I 2 J 2. The number is proportional to. When a constraint condition is set such that the fixed minimum value selection range shown in FIG. 1 is provided, the number of directed sides is a number proportional to IJ. This difference in the number of directed sides is directly related to the presence or absence of the effect of the present invention. That is, in applying the present invention, it is possible to impose a constraint condition for reducing the minimum value selection range, but it is necessary to make a directed acyclic graph having a number of directed edges proportional to I 2 J 2. .
実施例3での有向辺の数を表すために、制約条件を課さない場合の有向辺の数を表す関数を、次のようにe(m,n)と定義しておく。すなわち、実施例1の場合であれば、|E|=e(I,J)となる。 In order to represent the number of directed sides in the third embodiment, a function representing the number of directed sides when no constraint is imposed is defined as e (m, n) as follows. That is, in the case of the first embodiment, | E | = e (I, J).
以上、実施例1、および、実施例2での有向無閉路グラフ上での有向辺の数について整理した。 The number of directed edges on the directed acyclic graph in Example 1 and Example 2 has been arranged as described above.
実施例3では、式(1)、(6)〜(11)による実施例1に対して「(xi1, yj2)、もしくは、(xi2, yj1)のいずれかの対応付けを必ず含む(但し、i1< i2, j1< j2)」という制約条件を課す。すなわち、次の式(16)を制約条件として課す。この制約条件は、すべての格子点の最小値選択範囲を一律に制約した実施例2での制約条件と異なり、DP平面上で巨視的に制約条件を課するものである。このため、部分的な格子点での最小値選択範囲に影響する。 In the third embodiment, “(x i1 , y j2 ) or (x i2 , y j1 ) is always associated with the first embodiment according to the expressions (1) and (6) to (11). Include (however, i 1 <i 2 , j 1 <j 2 ) ”. That is, the following equation (16) is imposed as a constraint condition. This constraint condition is macroscopically imposed on the DP plane, unlike the constraint condition in the second embodiment in which the minimum value selection range of all grid points is uniformly restricted. This affects the minimum value selection range at partial grid points.
式(1)、(6)〜(11)、(16)による実施例3の対応付けにおける前記有向無閉路グラフは、図7のハッチングした部分(741、742)の内部に構成されることになる。始端(711)からの経路は、座標が(i1, j2)の格子点731と、座標が(i2, j1)の格子点732とのいずれかを通る。すなわち、始端711から格子点731もしくは格子点732とまでの経路は、始点終点とも741のハッチングした部分にある有向辺を連ねたものである。格子点731もしくは格子点732とから終端721までの経路は、始点終点とも742のハッチングした部分にある有向辺を連ねたものである。なお、図7のハッチング範囲内に有向無閉路グラフがあれば、式(16)が満たされるという訳ではない。 The directed acyclic graph in the correspondence of the third embodiment according to the expressions (1), (6) to (11), and (16) is configured inside the hatched portions (741, 742) in FIG. become. The path from the start end (711) passes through either the lattice point 731 whose coordinates are (i 1 , j 2 ) or the lattice point 732 whose coordinates are (i 2 , j 1 ). In other words, the path from the start end 711 to the lattice point 731 or the lattice point 732 is formed by connecting the directed edges in the hatched portion of the start point 741 and the start point end point. The path from the lattice point 731 or the lattice point 732 to the end point 721 is formed by connecting the directed sides in the hatched portion 742 with the start point and the end point. Note that if there is a directed acyclic graph within the hatched range of FIG. 7, equation (16) is not satisfied.
図7中のハッチング部分での有向辺の数を数えれば良いので、式(16)による制約条件を課した実施例3での有向無閉路グラフの有向辺の数|E|は、式(15)のe(m,n)を用いて、次の式(17)のとおりとなる。式(17)中、始めの3つの項は741のハッチング部分での有向辺の数であり、格子点711と731とを結ぶ線分を対角線とする長方形内の有向辺の数e(i1,j2)と、格子点711と732とを結ぶ線分を対角線とする長方形内の有向辺の数e(i2,j1)とを足したものから、格子点711と751とを結ぶ線分を対角線とする長方形内の有向辺の数e(i1,j1)を引くことによって求めている。終わりの3つの項は742のハッチング部分での有向辺の数である。 Since it is only necessary to count the number of directed edges in the hatched portion in FIG. 7, the number of directed edges | E | in the directed acyclic graph in the third embodiment that imposes the constraint condition according to the equation (16) is: Using e (m, n) in equation (15), the following equation (17) is obtained. In Expression (17), the first three terms are the number of directed sides in the hatched portion of 741, and the number of directed sides in a rectangle whose diagonal line is a line connecting grid points 711 and 731 e ( i 1 , j 2 ) and the number of directed sides e (i 2 , j 1 ) in the rectangle whose diagonal is a line segment connecting the grid points 711 and 732, the grid points 711 and 751 Is obtained by subtracting the number e (i 1 , j 1 ) of directed sides in a rectangle whose diagonal is a line connecting the two. The last three terms are the number of directed edges in the 742 hatched portion.
式(17)の値は、式(13)や式(14)と同様に、I2J2に比例する数となる。 The value of equation (17) is a number proportional to I 2 J 2 , as in equations (13) and (14).
逆に、I2J2に比例する数の有向辺がある有向無閉路グラフであれば、すべての格子点ではなくとも、(i,j)の座標を持つ格子点にi×j個に比例する最小値選択範囲があるような、一群の格子点が必ず存在する。その部分では、境界値により設定された基準に従って、その部分内での任意の個数の要素をスキップして、類似しているとする部分を柔軟に対応付けることが出来るという本発明効果が、制約条件の範囲内で発揮される。 Conversely, if the directed acyclic graph has a number of directed edges proportional to I 2 J 2 , not all grid points, but i × j grid points with coordinates (i, j) There is always a group of grid points such that there is a minimum selection range proportional to. In this part, according to the criteria set by the boundary value, the present invention effect that the arbitrary number of elements in the part can be skipped and the similar parts can be flexibly associated with each other is a constraint condition. It is demonstrated within the range.
本発明による対応付け方式の実装方法の実施例について、図8を用いて説明する。図8は、式(1)、(6)〜(10)に従う本発明による対応付け方式を、プログラミング言語JavaScript(登録商標)により実装したものである。図8のプログラムでは変数として、第1の要素列の要素数であるI、第2の要素列の要素数であるJ、境界値であるBV、xiとyjとの物理量であるmd(マンハッタン距離Manhattan distanceを意識した変数名)が設定済みであることを前提としている。 An embodiment of the associating method according to the present invention will be described with reference to FIG. FIG. 8 shows an implementation of the association method according to the present invention according to the formulas (1) and (6) to (10) using the programming language JavaScript (registered trademark). In the program of FIG. 8, as variables, I is the number of elements of the first element sequence, J is the number of elements of the second element sequence, BV is the boundary value, and md is the physical quantity of x i and y j ( It is assumed that the variable name (conscious of the Manhattan distance) has been set.
図8のプログラム中、nodesが格子点の情報を格納するオブジェクトの2次元配列である。この格子点のオブジェクトには、式(10)中のgi,jに相当し、経路の最小コストを保持するgフィールドと、バックトラックを行うために最小コストを設定した前の格子点のオブジェクトを保持するprevious_nodeフィールドとが設けられている。その他、格子点(i,j)の座標値である第1の要素列の要素番号iと、第2の要素列の要素番号jを保持するフィールドも設けられている。なお、JavaScript(登録商標)においては配列のインデックスは0からであるが、式(6)〜(10)の表記と合わせるため、図8のプログラムではインデックスを1から使用している。 In the program of FIG. 8, nodes is a two-dimensional array of objects that store information on lattice points. The lattice point object corresponds to g i, j in the equation (10), and includes a g field that holds the minimum cost of the route, and the object of the previous lattice point in which the minimum cost is set for backtracking. And a previous_node field for holding the. In addition, a field for holding the element number i of the first element row and the element number j of the second element row which are coordinate values of the lattice point (i, j) is also provided. In JavaScript (registered trademark), the array index is from 0, but in order to match the notations of the expressions (6) to (10), the index in FIG.
図8のプログラム中2行めと4行めとの繰り返しは、すべての格子点を順に処理するためのものである。変数iとjとを共に昇順でループさせれば、単調性制約の元で構成されたDP平面上の有向無閉路グラフの半順序のトポロジカルソート順となり、動的計画法を適用する要件を満たす。 The repetition of the second and fourth lines in the program of FIG. 8 is for processing all the grid points in order. If both variables i and j are looped in ascending order, it becomes the semi-ordered topological sort order of the directed acyclic graph on the DP plane constructed under the monotonic constraint, and the requirement to apply dynamic programming Fulfill.
図8のプログラム中5行めから7行めでは、格子点の初期化を行っている。このうち7行めでは、式(10)の漸化式の始端候補である場合の経路のコストを設定している。この始端候補としての経路コストの値は、後の処理で該格子点が始端候補以外となる場合に、更新される。 In the 5th to 7th lines in the program of FIG. 8, the grid points are initialized. Of these, the seventh line sets the cost of the route in the case of being the starting end candidate of the recurrence formula of Expression (10). The value of the path cost as the starting end candidate is updated when the lattice point becomes other than the starting end candidate in later processing.
図8のプログラム中8行めと9行めとの繰り返しは、格子点に対する最小値選択範囲を順に処理するためのものである。すなわち、式(10)の最小値に対する範囲設定の“1≦it≦i, 1≦jt≦j”に対応するものである。 The repetition of the 8th and 9th lines in the program of FIG. 8 is for sequentially processing the minimum value selection range for the grid points. That is, it corresponds to the range setting “1 ≦ i t ≦ i, 1 ≦ j t ≦ j” for the minimum value of the equation (10).
図8のプログラム中11行めから13行めは、最小値を更新する処理である。11行めで最小値の更新となるか否かを判定し、12行目で最小値を更新し、13行めではバックトラック処理のために前の格子点をpvevious_nodeフィールドに記憶する。8行めと9行めとの繰り返しの終了時に、この11行めから13行めの処理によってpvevious_nodeフィールドが設定されていれば始端候補であり、設定されていれば始端候補ではない。 Lines 11 to 13 in the program of FIG. 8 are processes for updating the minimum value. It is determined whether or not the minimum value is updated in the 11th row, the minimum value is updated in the 12th row, and the previous grid point is stored in the pvevious_node field for backtrack processing in the 13th row. At the end of the repetition of the 8th and 9th lines, if the pvevious_node field is set by the processing from the 11th line to the 13th line, it is a start end candidate, and if it is set, it is not a start end candidate.
図8のプログラム中15行めから22行めは、式(11)に従って終端を求める処理である。 Lines 15 to 22 in the program of FIG. 8 are processes for obtaining the end point according to equation (11).
図8のプログラム中23行めから29行めは、終端からバックトラック処理を行って、対応付けを表す経路を文字列として求める処理である。26行めでは、始端候補に達したことをpvevious_nodeフィールドが設定されていないことにより判定している。得られた対応付け結果は、30行めで出力される。 Lines 23 to 29 in the program of FIG. 8 are processes for performing a backtrack process from the end and obtaining a path representing the correspondence as a character string. In the 26th line, it is determined that the start end candidate has been reached because the pvevious_node field is not set. The obtained association result is output in the 30th line.
図8のプログラムにて、Iに4を、Jに4を、mdに表1の値を設定し、BVをそれぞれ0、4、8の値に設定して、図6に示した結果を得るように動作させるには、前述した「対応付けは1対1、2つ以上の対応」という条件を盛り込む必要がある。例えば「対応付けは1対1」の条件は、8行めと9行めとの繰り返し文中の判定部にて、“<=”を“<”に変更すれば良い。 In the program of FIG. 8, I is set to 4, J is set to 4, md is set to the value of Table 1, and BV is set to the values of 0, 4, and 8, respectively, and the result shown in FIG. 6 is obtained. In order to operate in such a manner, it is necessary to include the above-described condition that “correspondence is one-to-one, two or more correspondences”. For example, the condition of “one-to-one correspondence” may be changed by changing “<=” to “<” in the determination unit in the repetitive sentences in the 8th and 9th lines.
図8のプログラム、もしくは、他のプログラミング言語での同等のプログラムは、CPU、メモリ等を備えた一般的な計算機で実行可能である。また、組み込みシステムとして、図8のプログラム、もしくは、他の言語での同等のプログラムを実行する装置を構成することも、可能である。さらに図8のプログラム中の2行めと4行めとの繰り返しの内部の処理は、前記有向無閉路グラフでの半順序の順序関係を守る範囲で並列化が可能であり、スレッドに分割してマルチコアCPU上の別コアで実行させることも出来る。いずれの実装も、一般的な周知の方法により実現可能である。 The program in FIG. 8 or an equivalent program in another programming language can be executed by a general computer including a CPU, a memory, and the like. It is also possible to configure an apparatus that executes the program of FIG. 8 or an equivalent program in another language as an embedded system. Furthermore, the internal processing of the repetition of the second and fourth lines in the program of FIG. 8 can be parallelized within a range that keeps the partial order relation in the directed acyclic graph, and is divided into threads. It can also be executed by another core on the multi-core CPU. Either implementation can be realized by a general well-known method.
画像や音声信号、文章など、様々な対象について、2つの要素列間の対応付けに利用可能であり、認証、認識、検索などの用途に適用できる。 Various objects such as images, audio signals, and sentences can be used for association between two element strings, and can be applied to uses such as authentication, recognition, and search.
101〜104 最小値選択範囲の例
201 始端
202 終端
300 DP平面
301 注目する特定の格子点
410,420 DP平面
431〜433、441 始端
451〜453、461 終端
510、520 DP平面
531、541 始端
551、561 終端
601〜603 対応付けごとの列
610、620、630 境界値
611〜613、621〜623、631〜633 合計コストとその計算
640、650 点列の図示
641〜643、651〜653 対応付けの対象となった点列の矢印による図示
661〜663 対応付けの集合による表現
700 DP平面
711 始端
721 終端
731、732 制約条件で言及する格子点
741、742 ハッチング部分
751、752 格子点
101-104 Example of minimum value selection range 201 Start end 202 End 300 DP plane 301 Specific lattice points of interest 410, 420 DP planes 431-433, 441 Start end 451-453, 461 End 510, 520 DP plane 531, 541 Start end 551 , 561 Terminals 601 to 603 Columns 610, 620, 630 for each association Boundary values 611 to 613, 621 to 623, 631 to 633 Total cost and calculation 640, 650 Point sequence shown 641 to 643, 651 to 653 661 to 663 shown by arrows of the point sequence that is the target of the representation 700 DP plane 711 Start point 721 End point 731, 732 Lattice points 741 and 742 that are mentioned in the constraint condition Lattice points 751 and 752 Lattice points
Claims (9)
第1の要素列の要素による集合と第2の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第1のステップと、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第1の要素列の要素と第2の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第2のステップと、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで2つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第3のステップと、
求めた最小コスト経路に含まれる格子点の第1の要素列の要素と第2の要素列の要素との組の集合を第1の要素列と第2の要素列との対応付けの結果とする第4のステップと、
を有する、要素列間対応付け方法において、
前記第1のステップでは、
前記有向無閉路グラフにより定義される半順序での、有向辺の始点側を上位、終点側を下位とした順序関係にて、
すべての該順序関係にある上位の格子点と下位の格子点について、該上位の格子点から該下位の格子点への有向辺を設けるように、前記有向無閉路グラフを構成することと、
前記第2のステップでは、
前記要素列の対応付けの目的において、前記格子点を構成する第1の要素列の要素と第2の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値0のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする、要素列間対応付け方法。 When the first element sequence is compared with the second element sequence to obtain an association including one or more pairs of elements of the first element sequence and elements of the second element sequence,
On a lattice space that is a Cartesian product set of a set of elements of the first element sequence and a set of elements of the second element sequence,
A first directed acyclic graph is formed by providing a plurality of directed edges with a point in the lattice space as a lattice point, one lattice point as a start point, and another lattice point as an end point so as not to cause a cycle. And the steps
For all the grid points included as vertices in the directed acyclic graph, the cost is determined for each combination of the elements of the first element sequence and the elements of the second element sequence constituting each grid point. A second step for the cost of the grid points;
A route that connects two or more directed edges in succession by repeating the connection of two directed edges by matching the end point of the directed edge on the directed acyclic graph with the start point of another directed edge. age,
The total cost of the grid points included as the start point or end point of the directed side in the route is defined as the route cost.
The lattice points are sequentially processed in a topologically sorted order according to the semi-order defined by the directed acyclic graph, and the route that minimizes the route cost to the lattice point and the minimum route cost are obtained. A third step of determining a minimum cost path in the directed acyclic graph by dynamic programming;
A set of sets of elements of the first element sequence and elements of the second element sequence of the grid points included in the determined minimum cost path, and a result of associating the first element sequence with the second element sequence A fourth step to:
In the element string matching method having
In the first step,
In a partial order defined by the directed acyclic graph, in an order relationship in which the start point side of the directed edge is higher and the end point side is lower,
Configuring the directed acyclic graph so as to provide directed edges from the upper grid point to the lower grid point for all the upper grid points and the lower grid points in the order relationship; ,
In the second step,
For the purpose of associating the element strings, associating the elements of the first element string and the elements of the second element string constituting the lattice points is a negative cost when the object is met. If the cost is not positive, the cost of the positive value, if not, the value 0 is the cost of the grid point.
Mixing lattice points with negative cost and non-negative cost points,
A method for associating element strings, characterized by
第1の要素列の要素による集合と第2の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第1のステップと、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第1の要素列の要素と第2の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第2のステップと、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで2つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第3のステップと、
求めた最小コスト経路に含まれる格子点の第1の要素列の要素と第2の要素列の要素との組の集合を第1の要素列と第2の要素列との対応付けの結果とする第4のステップと、
を有する、要素列間対応付け方法において、
前記第1のステップでは、
前記第1の要素列の要素数をIとし、前記第2の要素列の要素数をJとし、前記Iと前記Jとの2つの値に応じて、I2J2に比例する数の有向辺を設けて、前記有向無閉路グラフを構成することと、
前記第2のステップでは、
前記要素列の対応付けの目的において、前記格子点を構成する第1の要素列の要素と第2の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値0のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする、要素列間対応付け方法。 When the first element sequence is compared with the second element sequence to obtain an association including one or more pairs of elements of the first element sequence and elements of the second element sequence,
On a lattice space that is a Cartesian product set of a set of elements of the first element sequence and a set of elements of the second element sequence,
A first directed acyclic graph is formed by providing a plurality of directed edges with a point in the lattice space as a lattice point, one lattice point as a start point, and another lattice point as an end point so as not to cause a cycle. And the steps
For all the grid points included as vertices in the directed acyclic graph, the cost is determined for each combination of the elements of the first element sequence and the elements of the second element sequence constituting each grid point. A second step for the cost of the grid points;
A route that connects two or more directed edges in succession by repeating the connection of two directed edges by matching the end point of the directed edge on the directed acyclic graph with the start point of another directed edge. age,
The total cost of the grid points included as the start point or end point of the directed side in the route is defined as the route cost.
The lattice points are sequentially processed in a topologically sorted order according to the semi-order defined by the directed acyclic graph, and the route that minimizes the route cost to the lattice point and the minimum route cost are obtained. A third step of determining a minimum cost path in the directed acyclic graph by dynamic programming;
A set of sets of elements of the first element sequence and elements of the second element sequence of the grid points included in the determined minimum cost path, and a result of associating the first element sequence with the second element sequence A fourth step to:
In the element string matching method having
In the first step,
The number of elements in the first element row is I, the number of elements in the second element row is J, and there are a number proportional to I 2 J 2 according to the two values I and J. Providing a directed edge to construct the directed acyclic graph;
In the second step,
For the purpose of associating the element strings, associating the elements of the first element string and the elements of the second element string constituting the lattice points is a negative cost when the object is met. If the cost is not positive, the cost of the positive value, if not, the value 0 is the cost of the grid point.
Mixing lattice points with negative cost and non-negative cost points,
A method for associating element strings, characterized by
前記有向無閉路グラフにより定義される半順序によりトポロジカルソートした順序で前記格子点ごとに該格子点に至る経路の最小経路コストを順次計算する際に、
最小経路コストを求める対象である第1の格子点を終点とする有向辺の始点となる第2の格子点のすべてについて、
該第2の格子点の計算済みの最小経路コストに負または0の値を持つものがある場合には、その負または0の値の中での最小値に第1の格子点のコストを足した値を、第1の格子点へ至る経路の最小経路コストとし、さらに、該最小値の最小経路コストを有する第2の格子点を第1の格子点の親の格子点として記憶し、
該第2の格子点の計算済みの最小経路コストが例外なく正の値である場合には、第1の格子点のコストを第1の格子点の最小経路コストとするとともに、第1の格子点を始端候補として記憶し、
すべての前記格子点にて最小経路コストを計算したのちに、その中で最小の値を持つ格子点を終端と定め、
該終端である格子点を始まりとして、格子点から上記親の格子点を繰り返し求めるバックトラック手順を行い、
該バックトラック手順にて前記始端候補と記憶された格子点が前記親の格子点となった際には該格子点を始端と定めて繰り返しを終了し、
得られた終端と始端とを両端としてバックトラック手順で現れた格子点を前記有向辺でつないだ経路を最小コスト経路とすることを特徴とする、
請求項1、または請求項2記載の要素列間対応付け方法。 In the third step of obtaining the minimum cost path,
When sequentially calculating the minimum path cost of the path to the grid point for each grid point in the order topologically sorted by the semi-order defined by the directed acyclic graph,
For all of the second grid points that are the starting points of the directed sides that end at the first grid point that is the target for which the minimum path cost is to be calculated,
When there is a negative or zero value in the calculated minimum path cost of the second grid point, the cost of the first grid point is added to the minimum value among the negative or zero values. The obtained value is set as the minimum path cost of the path to the first grid point, and the second grid point having the minimum path cost of the minimum value is stored as the parent grid point of the first grid point;
If the calculated minimum path cost of the second grid point is a positive value without exception, the cost of the first grid point is set as the minimum path cost of the first grid point, and the first grid point Remember the point as a starting point candidate,
After calculating the minimum path cost at all the lattice points, the lattice point having the smallest value among them is defined as the end point,
Starting from the lattice point that is the end, a backtrack procedure for repeatedly obtaining the parent lattice point from the lattice point is performed,
When the lattice point stored as the starting edge candidate in the backtrack procedure becomes the parent lattice point, the lattice point is determined as the starting edge, and the repetition is ended.
A path that connects the obtained end and start to both ends of the lattice points that appeared in the backtrack procedure with the directed side as a minimum cost path,
The element string correlation method according to claim 1 or 2.
第1の要素列の要素による集合と第2の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第1の手段と、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第1の要素列の要素と第2の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第2の手段と、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで2つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第3の手段と、
求めた最小コスト経路に含まれる格子点の第1の要素列の要素と第2の要素列の要素との組の集合を第1の要素列と第2の要素列との対応付けの結果とする第4の手段と、
を有する、要素列間対応付け装置において、
前記第1の手段では、
前記有向無閉路グラフにより定義される半順序での、有向辺の始点側を上位、終点側を下位とした順序関係にて、
すべての該順序関係にある上位の格子点と下位の格子点について、該上位の格子点から該下位の格子点への有向辺を設けるように、前記有向無閉路グラフを構成することと、
前記第2の手段では、
前記要素列の対応付けの目的において、前記格子点を構成する第1の要素列の要素と第2の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値0のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする、要素列間対応付け装置。 When the first element sequence is compared with the second element sequence to obtain an association including one or more pairs of elements of the first element sequence and elements of the second element sequence,
On a lattice space that is a Cartesian product set of a set of elements of the first element sequence and a set of elements of the second element sequence,
A first directed acyclic graph is formed by providing a plurality of directed edges with a point in the lattice space as a lattice point, one lattice point as a start point, and another lattice point as an end point so as not to cause a cycle. Means of
For all the grid points included as vertices in the directed acyclic graph, the cost is determined for each combination of the elements of the first element sequence and the elements of the second element sequence constituting each grid point. A second means for the cost of the grid points;
A route that connects two or more directed edges in succession by repeating the connection of two directed edges by matching the end point of the directed edge on the directed acyclic graph with the start point of another directed edge. age,
The total cost of the grid points included as the start point or end point of the directed side in the route is defined as the route cost.
The lattice points are sequentially processed in a topologically sorted order according to the semi-order defined by the directed acyclic graph, and the route that minimizes the route cost to the lattice point and the minimum route cost are obtained. A third means for determining a minimum cost path in the directed acyclic graph by dynamic programming;
A set of sets of elements of the first element sequence and elements of the second element sequence of the grid points included in the determined minimum cost path, and a result of associating the first element sequence with the second element sequence A fourth means to:
In the inter-element string association device having
In the first means,
In a partial order defined by the directed acyclic graph, in an order relationship in which the start point side of the directed edge is higher and the end point side is lower,
Configuring the directed acyclic graph so as to provide directed edges from the upper grid point to the lower grid point for all the upper grid points and the lower grid points in the order relationship; ,
In the second means,
For the purpose of associating the element strings, associating the elements of the first element string and the elements of the second element string constituting the lattice points is a negative cost when the object is met. If the cost is not positive, the cost of the positive value, if not, the value 0 is the cost of the grid point.
Mixing lattice points with negative cost and non-negative cost points,
A device for associating element strings, characterized by
第1の要素列の要素による集合と第2の要素列の要素による集合との直積集合である格子空間上で、
前記格子空間中の点を格子点として、ひとつの格子点を始点として他の格子点を終点とした有向辺を、閉路が生じないように複数設けて有向無閉路グラフを構成する第1の手段と、
前記有向無閉路グラフに頂点として含まれるすべての前記格子点について、各々の格子点を構成する第1の要素列の要素と第2の要素列の要素との組み合わせごとに定めてコストを該格子点のコストとする第2の手段と、
前記有向無閉路グラフ上の有向辺の終点を他の有向辺の始点と一致させることで2つの有向辺を連ねることを繰り返してひと続きに複数有向辺を連ねたものを経路とし、
前記経路に有向辺の始点または終点として含まれる格子点のコストの合計を経路コストとし、
前記有向無閉路グラフにより定義される半順序により格子点をトポロジカルソートした順序で格子点を順次処理して該格子点への経路コストが最小となる経路とその最小経路コストとを求めていく動的計画法により、前記有向無閉路グラフ中の最小コスト経路を求める第3の手段と、
求めた最小コスト経路に含まれる格子点の第1の要素列の要素と第2の要素列の要素との組の集合を第1の要素列と第2の要素列との対応付けの結果とする第4の手段と、
を有する、要素列間対応付け装置において、
前記第1の手段では、
前記第1の要素列の要素数をIとし、前記第2の要素列の要素数をJとし、前記Iと前記Jとの2つの値に応じて、I2J2に比例する数の有向辺を設けて、前記有向無閉路グラフを構成することと、
前記第2の手段では、
前記要素列の対応付けの目的において、前記格子点を構成する第1の要素列の要素と第2の要素列の要素とを対応付けることが、目的に沿う場合は負の値のコスト、目的に沿わない場合は正の値のコスト、いずれでも無い場合は値0のコスト、を該格子点のコストとすることにより、
負の値のコストを持つ格子点と非負の値のコストを持つ格子点とを混在させることと、
を特徴とする、要素列間対応付け装置。 When the first element sequence is compared with the second element sequence to obtain an association including one or more pairs of elements of the first element sequence and elements of the second element sequence,
On a lattice space that is a Cartesian product set of a set of elements of the first element sequence and a set of elements of the second element sequence,
A first directed acyclic graph is formed by providing a plurality of directed edges with a point in the lattice space as a lattice point, one lattice point as a start point, and another lattice point as an end point so as not to cause a cycle. Means of
For all the grid points included as vertices in the directed acyclic graph, the cost is determined for each combination of the elements of the first element sequence and the elements of the second element sequence constituting each grid point. A second means for the cost of the grid points;
A route that connects two or more directed edges in succession by repeating the connection of two directed edges by matching the end point of the directed edge on the directed acyclic graph with the start point of another directed edge. age,
The total cost of the grid points included as the start point or end point of the directed side in the route is defined as the route cost.
The lattice points are sequentially processed in a topologically sorted order according to the semi-order defined by the directed acyclic graph, and the route that minimizes the route cost to the lattice point and the minimum route cost are obtained. A third means for determining a minimum cost path in the directed acyclic graph by dynamic programming;
A set of sets of elements of the first element sequence and elements of the second element sequence of the grid points included in the determined minimum cost path, and a result of associating the first element sequence with the second element sequence A fourth means to:
In the inter-element string association device having
In the first means,
The number of elements in the first element row is I, the number of elements in the second element row is J, and there are a number proportional to I 2 J 2 according to the two values I and J. Providing a directed edge to construct the directed acyclic graph;
In the second means,
For the purpose of associating the element strings, associating the elements of the first element string and the elements of the second element string constituting the lattice points is a negative cost when the object is met. If the cost is not positive, the cost of the positive value, if not, the value 0 is the cost of the grid point.
Mixing lattice points with negative cost and non-negative cost points,
A device for associating element strings, characterized by
前記有向無閉路グラフにより定義される半順序によりトポロジカルソートした順序で前記格子点ごとに該格子点に至る経路の最小経路コストを順次計算する際に、
最小経路コストを求める対象である第1の格子点を終点とする有向辺の始点となる第2の格子点のすべてについて、
該第2の格子点の計算済みの最小経路コストに負または0の値を持つものがある場合には、その負または0の値の中での最小値に第1の格子点のコストを足した値を、第1の格子点へ至る経路の最小経路コストとし、さらに、該最小値の最小経路コストを有する第2の格子点を第1の格子点の親の格子点として記憶し、
該第2の格子点の計算済みの最小経路コストが例外なく正の値である場合には、第1の格子点のコストを第1の格子点の最小経路コストとするとともに、第1の格子点を始端候補として記憶し、
すべての前記格子点にて最小経路コストを計算したのちに、その中で最小の値を持つ格子点を終端と定め、
該終端である格子点を始まりとして、格子点から上記親の格子点を繰り返し求めるバックトラック手順を行い、
該バックトラック手順にて前記始端候補と記憶された格子点が前記親の格子点となった際には該格子点を始端と定めて繰り返しを終了し、
得られた終端と始端とを両端としてバックトラック手順で現れた格子点を前記有向辺でつないだ経路を最小コスト経路とすることを特徴とする、
請求項5、または請求項6記載の要素列間対応付け装置。 In the third means for obtaining the minimum cost route,
When sequentially calculating the minimum path cost of the path to the grid point for each grid point in the order topologically sorted by the semi-order defined by the directed acyclic graph,
For all of the second grid points that are the starting points of the directed sides that end at the first grid point that is the target for which the minimum path cost is to be calculated,
When there is a negative or zero value in the calculated minimum path cost of the second grid point, the cost of the first grid point is added to the minimum value among the negative or zero values. The obtained value is set as the minimum path cost of the path to the first grid point, and the second grid point having the minimum path cost of the minimum value is stored as the parent grid point of the first grid point;
If the calculated minimum path cost of the second grid point is a positive value without exception, the cost of the first grid point is set as the minimum path cost of the first grid point, and the first grid point Remember the point as a starting point candidate,
After calculating the minimum path cost at all the lattice points, the lattice point having the smallest value among them is defined as the end point,
Starting from the lattice point that is the end, a backtrack procedure for repeatedly obtaining the parent lattice point from the lattice point is performed,
When the lattice point stored as the starting edge candidate in the backtrack procedure becomes the parent lattice point, the lattice point is determined as the starting edge, and the repetition is ended.
A path that connects the obtained end and start to both ends of the lattice points that appeared in the backtrack procedure with the directed side as a minimum cost path,
The element string correlation device according to claim 5 or 6.
Priority Applications (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP2015054744A JP2016177327A (en) | 2015-03-18 | 2015-03-18 | Method of associating two element strings having feature in configuration of directed acyclic graph and cost of lattice point for applying dynamic programming |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
JP2015054744A JP2016177327A (en) | 2015-03-18 | 2015-03-18 | Method of associating two element strings having feature in configuration of directed acyclic graph and cost of lattice point for applying dynamic programming |
Publications (1)
Publication Number | Publication Date |
---|---|
JP2016177327A true JP2016177327A (en) | 2016-10-06 |
Family
ID=57070564
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP2015054744A Pending JP2016177327A (en) | 2015-03-18 | 2015-03-18 | Method of associating two element strings having feature in configuration of directed acyclic graph and cost of lattice point for applying dynamic programming |
Country Status (1)
Country | Link |
---|---|
JP (1) | JP2016177327A (en) |
Cited By (4)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN109460491A (en) * | 2018-10-19 | 2019-03-12 | 中山大学 | Timing shortest path query method based on Neo4j database |
JP2019141578A (en) * | 2018-02-15 | 2019-08-29 | ライカ インストゥルメンツ (シンガポール) プライヴェット リミテッドLeica Instruments (Singapore) Pte. Ltd. | Image processing method and apparatus using elastic mapping of vascular plexus structures |
CN114279457A (en) * | 2021-12-23 | 2022-04-05 | 中南民族大学 | Path planning method, device, equipment and readable storage medium |
CN116167321A (en) * | 2023-01-19 | 2023-05-26 | 深圳华大九天科技有限公司 | Protection ring generation method and device and related products |
-
2015
- 2015-03-18 JP JP2015054744A patent/JP2016177327A/en active Pending
Cited By (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JP2019141578A (en) * | 2018-02-15 | 2019-08-29 | ライカ インストゥルメンツ (シンガポール) プライヴェット リミテッドLeica Instruments (Singapore) Pte. Ltd. | Image processing method and apparatus using elastic mapping of vascular plexus structures |
CN109460491A (en) * | 2018-10-19 | 2019-03-12 | 中山大学 | Timing shortest path query method based on Neo4j database |
CN109460491B (en) * | 2018-10-19 | 2021-12-10 | 中山大学 | Neo4j database-based time sequence shortest path query method |
CN114279457A (en) * | 2021-12-23 | 2022-04-05 | 中南民族大学 | Path planning method, device, equipment and readable storage medium |
CN114279457B (en) * | 2021-12-23 | 2023-10-03 | 中南民族大学 | Path planning method, device, equipment and readable storage medium |
CN116167321A (en) * | 2023-01-19 | 2023-05-26 | 深圳华大九天科技有限公司 | Protection ring generation method and device and related products |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
Lund et al. | Package ‘circular’ | |
KR102178295B1 (en) | Decision model construction method and device, computer device and storage medium | |
Torshin | Optimal dictionaries of the final information on the basis of the solvability criterion and their applications in bioinformatics | |
US10796096B2 (en) | Semantic expression generation method and apparatus | |
JP5554304B2 (en) | Automaton determinizing method, automaton determinizing apparatus and automaton determinizing program | |
US10217241B2 (en) | System and method for compressing graphs via cliques | |
Ngomo | A time-efficient hybrid approach to link discovery | |
JP2016177327A (en) | Method of associating two element strings having feature in configuration of directed acyclic graph and cost of lattice point for applying dynamic programming | |
CN110059264B (en) | Site retrieval method, equipment and computer storage medium based on knowledge graph | |
JP7390250B2 (en) | A system that generates compound structure representations | |
TWI740262B (en) | Method, apparatus for identifying genetic variation and storage medium thereof | |
JP6003705B2 (en) | Information processing apparatus and information processing program | |
CN111143539B (en) | Knowledge graph-based teaching field question-answering method | |
Sarkar et al. | An algorithm for DNA read alignment on quantum accelerators | |
CN110728359B (en) | Method, device, equipment and storage medium for searching model structure | |
JP2016162198A (en) | Parameter learning method, device, and program | |
JP5022252B2 (en) | Expression template generation apparatus, method and program thereof | |
Bilu et al. | Faster algorithms for optimal multiple sequence alignment based on pairwise comparisons | |
JP2012098905A (en) | Character recognition device, character recognition method and program | |
Papamichail et al. | Improved algorithms for approximate string matching | |
KR102509343B1 (en) | Method and system for analyzing layout of image | |
Molloy et al. | FastMulRFS: Statistically consistent polynomial time species tree estimation under gene duplication | |
US20240095520A1 (en) | Representation learning apparatus, method, and non-transitory computer readable medium | |
US20180260520A1 (en) | Systems and methods for aligning sequences to graph reference constructs | |
JP2005182201A (en) | Corresponding point search method, device, and program of image, |