05.係り受け解析/049.名詞間の係り受けパスの抽出.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "文中のすべての名詞句のペアを結ぶ最短係り受けパスを抽出せよ．ただし，名詞句ペアの文節番号がiとj（i<j）のとき，係り受けパスは以下の仕様を満たすものとする．\n",
    "\n",
    "- 問題48と同様に，パスは開始文節から終了文節に至るまでの各文節の表現（表層形の形態素列）を\"->\"で連結して表現する\n",
    "- 文節iとjに含まれる名詞句はそれぞれ，XとYに置換する\n",
    "\n",
    "また，係り受けパスの形状は，以下の2通りが考えられる．\n",
    "\n",
    "- 文節iから構文木の根に至る経路上に文節jが存在する場合: 文節iから文節jのパスを表示\n",
    "- 上記以外で，文節iと文節jから構文木の根に至る経路上で共通の文節kで交わる場合: 文節iから文節kに至る直前のパスと文節jから文節kに至る直前までのパス，文節kの内容を\"|\"で連結して表示\n",
    "\n",
    "例えば，「吾輩はここで始めて人間というものを見た。」という文（neko.txt.cabochaの8文目）から，次のような出力が得られるはずである．\n",
    "\n",
    "```\n",
    "Xは | Yで -> 始めて -> 人間という -> ものを | 見た\n",
    "Xは | Yという -> ものを | 見た\n",
    "Xは | Yを | 見た\n",
    "Xで -> 始めて -> Y\n",
    "Xで -> 始めて -> 人間という -> Y\n",
    "Xという -> Y\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- パターン1: XとYが別経路：|で区切る、Yは名詞部分のみの置き換え\n",
    "- パターン2：XとYが同じ経路：Yは文節全体を置き換え"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 区切り文字\n",
    "separator = re.compile('\\t|,')\n",
    "\n",
    "# 係り受け\n",
    "dependancy = re.compile(r'''(?:\\*\\s\\d+\\s) # キャプチャ対象外\n",
    "                            (-?\\d+)       # 数字(係り先)\n",
    "                          ''', re.VERBOSE)\n",
    "NOUN_REPLACE = '@@noun@@'\n",
    "SEP1 = ' -> '\n",
    "SEP2 = ' | '"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Morph:\n",
    "    def __init__(self, line):\n",
    "        \n",
    "        #タブとカンマで分割\n",
    "        cols = separator.split(line)\n",
    "        \n",
    "        self.surface = cols[0] # 表層形(surface)\n",
    "        self.base = cols[7]    # 基本形(base)\n",
    "        self.pos = cols[1]     # 品詞(pos)\n",
    "        self.pos1 = cols[2]    # 品詞細分類1(pos1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Chunk:\n",
    "    def __init__(self, morphs, dst):\n",
    "        self.morphs = morphs\n",
    "        self.dst  = dst  # 係り先文節インデックス番号\n",
    "        self.dsts = []\n",
    "        \n",
    "        self.phrase = ''\n",
    "        self.phrase_noun = ''\n",
    "        self.noun = False\n",
    "        \n",
    "        for morph in morphs:\n",
    "            if morph.pos != '記号':\n",
    "                self.phrase += morph.surface # 記号以外の場合文節作成\n",
    "                if morph.pos == '名詞':\n",
    "                    \n",
    "                    # 初めての名詞の場合、名詞句として扱う\n",
    "                    if self.noun == False:\n",
    "                        self.noun = True\n",
    "                        self.phrase_noun += NOUN_REPLACE\n",
    "                        continue\n",
    "                    \n",
    "                    # ひとつ前が名詞で対象だった場合は表層系を置き換えない\n",
    "                    elif self.noun and self.phrase_noun.endswith(NOUN_REPLACE):\n",
    "                        continue\n",
    "                        \n",
    "                # 置換やスキップ以外の場合は、そのまま表層系を追加\n",
    "                self.phrase_noun += morph.surface"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 2 µs, sys: 1e+03 ns, total: 3 µs\n",
      "Wall time: 6.44 µs\n"
     ]
    }
   ],
   "source": [
    "%time\n",
    "\n",
    "morphs = []\n",
    "chunks = []\n",
    "sentences = []\n",
    "\n",
    "with open('./neko.txt.cabocha') as f:\n",
    "    \n",
    "    for line in f:\n",
    "        dependancies = dependancy.match(line)\n",
    "        \n",
    "        # EOSまたは係り受け解析結果でない場合\n",
    "        if not (line == 'EOS\\n' or dependancies):\n",
    "            morphs.append(Morph(line))\n",
    "            \n",
    "        # EOSまたは係り受け解析結果で、形態素解析結果がある場合\n",
    "        elif len(morphs) > 0:\n",
    "            chunks.append(Chunk(morphs, dst))\n",
    "            morphs = []\n",
    "       \n",
    "        # 係り受け結果の場合\n",
    "        if dependancies:\n",
    "            dst = int(dependancies.group(1))\n",
    "        \n",
    "        # EOSで係り受け結果がある場合\n",
    "        if line == 'EOS\\n' and len(chunks) > 0:\n",
    "            \n",
    "            # 係り先を追加していく(効率化のため最終行から\n",
    "            追加していく)\n",
    "            for chunk in chunks[::-1]:\n",
    "                if chunk.dst!= -1:\n",
    "                    chunk.dsts.extend([chunk.dst])\n",
    "                    if chunks[chunk.dst].dst != -1:\n",
    "                        chunk.dsts.extend(chunks[chunk.dst].dsts)\n",
    "            sentences.append(chunks)\n",
    "            chunks = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def output_result(i, chunk, sentence):\n",
    "    print('\\tX:', i, chunk.phrase, chunk.dsts)\n",
    "    \n",
    "    # 名詞句(X)の次からYを探索するループ\n",
    "    for i_y, y_chunk in enumerate(sentence[i+1:], i+1):\n",
    "        \n",
    "        # 名詞句の場合Yとする\n",
    "        if y_chunk.noun:\n",
    "            \n",
    "            # Yの情報出力\n",
    "            print('\\t\\tY:', i_y, y_chunk.phrase)\n",
    "            \n",
    "            result = ''\n",
    "            \n",
    "            # Yが経路(係り先)に含まれる場合\n",
    "            if i_y in chunk.dsts:\n",
    "                \n",
    "                result = '\\t\\t\\tP1:' + '\\t' + sentence[i].phrase_noun.replace(NOUN_REPLACE, 'X') + SEP1\n",
    "                \n",
    "                # XからYまでを出力\n",
    "                for i_path in chunk.dsts:\n",
    "                    \n",
    "                    # Yに到達したら終了\n",
    "                    if i_path == i_y:\n",
    "                        result += 'Y'\n",
    "                        break\n",
    "                    else:\n",
    "                        result += sentence[i_path].phrase + SEP1\n",
    "            \n",
    "            # Yが経路(係り先)に含まれない場合\n",
    "            else:\n",
    "                result = '\\t\\t\\tP2:' + '\\t' + sentence[i].phrase_noun.replace(NOUN_REPLACE, 'X')\n",
    "                \n",
    "                # 積集合での最小値で共通の文節を求める\n",
    "                i_goal = min(set(chunk.dsts).intersection(set(sentence[i_y].dsts)))\n",
    "                \n",
    "                # Xから共通文節の前、Yまで\n",
    "                for i_path in chunk.dsts:                    \n",
    "                    if i_path == i_goal:\n",
    "                        result += SEP2 + sentence[i_y].phrase_noun.replace(NOUN_REPLACE, 'Y')\n",
    "                        break\n",
    "                    else:\n",
    "                        result += SEP1 + sentence[i_path].phrase                 \n",
    "                \n",
    "                # Yの係り先から共通文節まで\n",
    "                for i_path in sentence[i_y].dsts:\n",
    "                    if i_path == i_goal:\n",
    "                        result += SEP2 + sentence[i_goal].phrase\n",
    "                    else:\n",
    "                        result += SEP1 + sentence[i_path].phrase\n",
    "            print(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 \t 一\n",
      "1 \t 吾輩は猫である\n",
      "2 \t 名前はまだ無い\n",
      "\tX: 0 名前は [2]\n",
      "3 \t どこで生れたかとんと見当がつかぬ\n",
      "\tX: 0 どこで [1, 2, 4]\n",
      "\t\tY: 2 かとんと\n",
      "\t\t\tP1:\tXで -> 生れた -> Y\n",
      "\t\tY: 3 見当が\n",
      "\t\t\tP2:\tXで -> 生れた -> かとんと | Yが | つかぬ\n",
      "\tX: 2 かとんと [4]\n",
      "\t\tY: 3 見当が\n",
      "\t\t\tP2:\tXと | Yが | つかぬ\n",
      "\tX: 3 見当が [4]\n",
      "4 \t 何でも薄暗いじめじめした所でニャーニャー泣いていた事だけは記憶している\n",
      "\tX: 0 何でも [1, 5, 7]\n",
      "\t\tY: 3 した所で\n",
      "\t\t\tP2:\tXでも -> 薄暗い | Yで | 泣いて -> 記憶している\n",
      "\t\tY: 6 いた事だけは\n",
      "\t\t\tP2:\tXでも -> 薄暗い -> 泣いて | Yだけは | 記憶している\n",
      "\t\tY: 7 記憶している\n",
      "\t\t\tP1:\tXでも -> 薄暗い -> 泣いて -> Y\n",
      "\tX: 3 した所で [5, 7]\n",
      "\t\tY: 6 いた事だけは\n",
      "\t\t\tP2:\tXで -> 泣いて | Yだけは | 記憶している\n",
      "\t\tY: 7 記憶している\n",
      "\t\t\tP1:\tXで -> 泣いて -> Y\n",
      "\tX: 6 いた事だけは [7]\n",
      "\t\tY: 7 記憶している\n",
      "\t\t\tP1:\tXだけは -> Y\n",
      "5 \t 吾輩はここで始めて人間というものを見た\n",
      "\tX: 0 吾輩は [5]\n",
      "\t\tY: 1 ここで\n",
      "\t\t\tP2:\tXは | Yで -> 始めて -> 人間という -> ものを | 見た\n",
      "\t\tY: 3 人間という\n",
      "\t\t\tP2:\tXは | Yという -> ものを | 見た\n",
      "\t\tY: 4 ものを\n",
      "\t\t\tP2:\tXは | Yを | 見た\n",
      "\tX: 1 ここで [2, 3, 4, 5]\n",
      "\t\tY: 3 人間という\n",
      "\t\t\tP1:\tXで -> 始めて -> Y\n",
      "\t\tY: 4 ものを\n",
      "\t\t\tP1:\tXで -> 始めて -> 人間という -> Y\n",
      "\tX: 3 人間という [4, 5]\n",
      "\t\tY: 4 ものを\n",
      "\t\t\tP1:\tXという -> Y\n",
      "\tX: 4 ものを [5]\n",
      "6 \t しかもあとで聞くとそれは書生という人間中で一番獰悪な種族であったそうだ\n",
      "\tX: 1 あとで [2, 9]\n",
      "\t\tY: 3 それは\n",
      "\t\t\tP2:\tXで -> 聞くと | Yは | そうだ\n",
      "\t\tY: 4 書生という\n",
      "\t\t\tP2:\tXで -> 聞くと | Yという -> 人間中で -> 種族であった | そうだ\n",
      "\t\tY: 5 人間中で\n",
      "\t\t\tP2:\tXで -> 聞くと | Yで -> 種族であった | そうだ\n",
      "\t\tY: 6 一番\n",
      "\t\t\tP2:\tXで -> 聞くと | Y -> 獰悪な -> 種族であった | そうだ\n",
      "\t\tY: 7 獰悪な\n",
      "\t\t\tP2:\tXで -> 聞くと | Yな -> 種族であった | そうだ\n",
      "\t\tY: 8 種族であった\n",
      "\t\t\tP2:\tXで -> 聞くと | Yであった | そうだ\n",
      "\t\tY: 9 そうだ\n",
      "\t\t\tP1:\tXで -> 聞くと -> Y\n",
      "\tX: 3 それは [9]\n",
      "\t\tY: 4 書生という\n",
      "\t\t\tP2:\tXは | Yという -> 人間中で -> 種族であった | そうだ\n",
      "\t\tY: 5 人間中で\n",
      "\t\t\tP2:\tXは | Yで -> 種族であった | そうだ\n",
      "\t\tY: 6 一番\n",
      "\t\t\tP2:\tXは | Y -> 獰悪な -> 種族であった | そうだ\n",
      "\t\tY: 7 獰悪な\n",
      "\t\t\tP2:\tXは | Yな -> 種族であった | そうだ\n",
      "\t\tY: 8 種族であった\n",
      "\t\t\tP2:\tXは | Yであった | そうだ\n",
      "\t\tY: 9 そうだ\n",
      "\t\t\tP1:\tXは -> Y\n",
      "\tX: 4 書生という [5, 8, 9]\n",
      "\t\tY: 5 人間中で\n",
      "\t\t\tP1:\tXという -> Y\n",
      "\t\tY: 6 一番\n",
      "\t\t\tP2:\tXという -> 人間中で | Y -> 獰悪な | 種族であった -> そうだ\n",
      "\t\tY: 7 獰悪な\n",
      "\t\t\tP2:\tXという -> 人間中で | Yな | 種族であった -> そうだ\n",
      "\t\tY: 8 種族であった\n",
      "\t\t\tP1:\tXという -> 人間中で -> Y\n",
      "\t\tY: 9 そうだ\n",
      "\t\t\tP1:\tXという -> 人間中で -> 種族であった -> Y\n",
      "\tX: 5 人間中で [8, 9]\n",
      "\t\tY: 6 一番\n",
      "\t\t\tP2:\tXで | Y -> 獰悪な | 種族であった -> そうだ\n",
      "\t\tY: 7 獰悪な\n",
      "\t\t\tP2:\tXで | Yな | 種族であった -> そうだ\n",
      "\t\tY: 8 種族であった\n",
      "\t\t\tP1:\tXで -> Y\n",
      "\t\tY: 9 そうだ\n",
      "\t\t\tP1:\tXで -> 種族であった -> Y\n",
      "\tX: 6 一番 [7, 8, 9]\n",
      "\t\tY: 7 獰悪な\n",
      "\t\t\tP1:\tX -> Y\n",
      "\t\tY: 8 種族であった\n",
      "\t\t\tP1:\tX -> 獰悪な -> Y\n",
      "\t\tY: 9 そうだ\n",
      "\t\t\tP1:\tX -> 獰悪な -> 種族であった -> Y\n",
      "\tX: 7 獰悪な [8, 9]\n",
      "\t\tY: 8 種族であった\n",
      "\t\t\tP1:\tXな -> Y\n",
      "\t\tY: 9 そうだ\n",
      "\t\t\tP1:\tXな -> 種族であった -> Y\n",
      "\tX: 8 種族であった [9]\n",
      "\t\tY: 9 そうだ\n",
      "\t\t\tP1:\tXであった -> Y\n"
     ]
    }
   ],
   "source": [
    "for i_sentence, sentence in enumerate(sentences):\n",
    "    \n",
    "    # 文出力\n",
    "    print(i_sentence, '\\t', ''.join([chunk.phrase for chunk in sentence]))\n",
    "    for i_chunk, chunk in enumerate(sentence):\n",
    "        \n",
    "        # 文節が名詞句の場合\n",
    "        if chunk.noun and chunk.dst != -1:\n",
    "            output_result(i_chunk, chunk, sentence)\n",
    "\n",
    "    # 多いので制限\n",
    "    if i_sentence > 5:\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}