1995年3月17日
二次元配列間の距離について
情報処理学会研究報告アルゴリズム(AL)
- 巻
- 1995
- 号
- 32
- 開始ページ
- 29
- 終了ページ
- 36
- 記述言語
- 日本語
- 掲載種別
- 出版者・発行元
- 一般社団法人情報処理学会
二次元配列の近似マッチング問題として従来提案されてきたものは縦方向と横方向の扱いが異なる不自然なものであった。本稿では、より自然な近似マッチングを行うために、縦方向と横方向が対等に考慮される二次元配列間の距離(誤差)を定義する。そして、MAX?2SAT問題を還元することにより、一般的にはこの距離を計算することはNP困難であることを示す。一方、特殊な、しかし、ある程度現実的な場合には最短経路問題に帰着させることにより多項式時間で計算できることも示す。This paper proposes an editing distance problem between two-dimensional arrays, in which rows are treated in the same way as in columns. This problem is important for approximate pattern matching between two-dimensional arrays. The problem is proved to be NP-hand by a reduction from MAX-2SAT. However a polynomial time algorithm is shown for a special case, in which the problem is reduced to the shortest path problem.
- リンク情報
-
- CiNii Articles
- http://ci.nii.ac.jp/naid/110002812285
- CiNii Books
- http://ci.nii.ac.jp/ncid/AN1009593X
- URL
- http://id.nii.ac.jp/1001/00032359/
- ID情報
-
- ISSN : 0919-6072
- CiNii Articles ID : 110002812285
- CiNii Books ID : AN1009593X