本研究の目的は,Webにある膨大な数のレシピの集合が本質的にどの程度の多様性を持っているのか,足りないのか十分なのか,何が足りないのかを明らかにすることである.そこで本研究では,(i)自然言語処理技術によりレシピ記述から手順構造を抽出し,(ii)手順と記述の観点からレシピ間の関係を解析するとともに,(iii)全体の知識を使って補完可能な欠損を補完することで,レシピ集合が持つ本質的な多様性を解析する機構を構築する.今年度は以下の2点を行った.(1) 国際化に向けた英語対応:Webレシピの急増は日本だけでなく世界で起こっている現象である.米国最大手のAllrecipesの月間ページビューは推定2,000万件で,クックパッドの実に3倍以上である.さらに料理レシピが世界の情報処理の研究対象として国際的に認知されつつある.そこで,平成28年度,英文係り受け解析器RASPの開発で著名なJohn Carroll氏の協力を得て,英文レシピのフローグラフコーパスを開発した.今年度はこれを我々が開発した手法で実装することで,固有表現認識精度が84.8%,固有表現が正しく認識されているときの依存関係推定精度74.1%を達成した.また,和文と英文のレシピの構造的な相違を統計分析により明らかにした.(2) レシピテキストの記述粒度の自動変換:肉じゃがやハンバーグのような代表的な和食は数千からときに数万のレシピが見つかる.同じ料理名をもつレシピのうち,その主たる調理方法が似通っているとき,それらは似た調理手順を説明した異なる記述であると考える.ここで,片方のレシピがもち,もう片方のレシピが持っていない説明は,その手順の詳細説明であると考えられることから,この関係を用いて詳細記述を生成した.また,双方が持つノードはその手法の主幹であることから,それらを取り出したフローを簡略な表現と位置付けた.
1 0 0 0 じゃばら折りの複雑さに関する研究
- 著者
- 伊藤 剛志 清見 礼 今堀 慎治 上原 隆平
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 研究報告アルゴリズム(AL) (ISSN:09196072)
- 巻号頁・発行日
- vol.2009, no.9, pp.1-8, 2009-01-23
本稿では 「じゃばら折り」 に関する新しい折り紙の問題を提案する.本問題では与えられた n 個の山折り/谷折りの割り当てに対して,紙をその割り当てに従って等間隔に折ることを目的とする.扱う紙のモデルは以下の通り. (1) 紙は厚み 0 で重ねて一度に複数枚折ることができる. (2) それぞれの折り状態は平坦である. (3) それぞれの折り目はそこで最後に折られたときの折り状態を記憶する. (4) 紙は n 箇所の折り目を除いて剛体である.このモデルにおいて,与えられた割り当てを実現する効率の良い折り操作を見つけることがこの問題の目的である.一般の山谷割り当てに対する問題を単位長折り問題と呼び,山谷割り当てが 「MV MV MV ...」という形をしているときは特にじゃばら折り問題と呼ぶことにする.アルゴリズムの複雑さは折りの回数によって測り,折りを開く回数は無視する.この問題には自明な上界、と自明な下界 log (n + 1) が存在する.本稿ではまず以下の非自明な 2 つの上界を示す. (a) どんな山谷割り当てでも高々 [n/2] + [log (n+1)] 1 回の折りで実現することができる. (b) 任意の ∊>0 に対してじゃばら折りは 0 (n∊) 回の折りで実現することができる.次に以下の非自明な下界を示す. (c) ほとんどすべての山谷割り当ては Ω (n/log n) 回折らなければ作ることができない結果 (b) と (c) より,じゃばら折り問題は単位長折り問題の中では簡単な部類に入ることがわかった.We introduce a new origami problem about pleats foldings. For a given assignment of n creases of mountains and valleys, we make a strip of paper well-creased according to the assignment at regular intervals. We assume that (1) paper has 0 thickness and some layers beneath a crease can be folded simultaneously, (2) each folded state is flat, (3) each crease remembers its last folded state made at the crease, and (4) the paper is rigid except at the n given creases. On this model, we aim to find efficient ways of folding a given mountain-valley assignment. We call this problem unit folding problem for general patterns, and pleats folding problem when the mountain-valley assignment is "MVMVMV…" The complexity is measured by the number of foldings and the cost of unfoldings is ignored. Trivially, we have an upper bound n and a lower bound log [(n+1).] We first give some nontrivial upper bounds: (a) any mountain-valley assignment can be made by [n / 2 ] + [log (n+1) ] foldings, and (b) a pleats folding can be made by O (n∊) foldings for any ∊>0. Next, we also give a nontrivial lower bound: (c) almost all mountain-valley assignments require Ω(log n / n) foldings. The results (b) and (c) imply that a pleats folding is easy in the unit folding problem.