発見的グラフ探索法を用いた日本語形態素解析

• Item type: SIG Technical Reports(1)
• 公開日: 1989-09-21
• タイトル: 発見的グラフ探索法を用いた日本語形態素解析
• タイトル / 言語: en
• タイトル: A JAPANESE MORPHOLOGICAL ANALYSIS USING HEURISTIC SEARCH ALGORITHM
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 松下電器産業（株）情報通信東京研究所
• 著者所属: 松下電器産業（株）情報通信東京研究所
• 著者所属(英): en
• 著者所属(英): Tokyo Information and Communications Reseach Laboratory, Matsushita Electric Industrial Co., Ltd.
• 著者所属(英): en
• 著者所属(英): Tokyo Information and Communications Reseach Laboratory, Matsushita Electric Industrial Co., Ltd.
• 著者名: 長尾, 健司; 菅野祐司
• 著者名(英): Kenji, Nagao; Yuji, Kanno
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフ探索のアルゴリズムA＊を、探索コストが、最小コスト＋α（αは任意の正定数）以下の範囲で、m番目（mは任意整数）までのパスを取り出すことができるように拡張し、これをベースに、高速な形態素解析を実現した。この形態素解析アルゴリズムの時間計算量は、入力文字列長をLとすると、O(L^2)となり（αやmに無関係ゆえ）求める解の範囲を大きくしても、処理の負荷は大きくならないという特徴がある。本稿では、合わせて、本アルゴリズムをもとに、文節数最小法を実現し、最小文節数の解析をただ一つ取り出す場合と、最小文節数＋1以内の解析を全て取り出す場合の実験を行い、処理時間がさほど変わらないことを確認し、アルゴリズムの有効性を立証する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: An efficient algorithm for Japanese mirphological analysis has been developed based on a heuristic graph search procedure which is a new extension of the A*. This extension enebles to find m paths of which costs are the least and less than or equal to the minimal cost +α, where m and α are a given integer and an arbitrary positive value, respectively. This algorithm runs in O(L^2) steps for an input Japanese sentence of which length is L. The advantage of this algorithm is its speed since the running time to find m paths is comparable to the time for finding the minimal one. This is exoected from the fact that the function, O(L^2), is independent of m or α. The experiments have been carried out on a system in which the costs of graphs are determined by Minimum Pause Group Method.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10115061
• 書誌情報: 情報処理学会研究報告自然言語処理（NL）; 巻 1989, 号 77(1989-NL-074), p. 73-80, 発行日 1989-09-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会