言語処理100本ノック2020

言語処理100本ノック2020 第5章 係り受け解析

はじめに

言語処理100本ノック2020

言語処理100本ノックは東北大学が公開している自然言語処理の問題集です。

とても良質なコンテンツで企業の研修や勉強会で使われています。

そんな言語処理100本ノックが2020年に改定されてました。昨今の状況を鑑みて、深層ニューラルネットワークに関する問題が追加されました。（その他にも細かい変更があります）

この記事では、言語処理100本ノック2020にPythonで取り組んでいきます。

他にも色々な解法があると思うので、一つの解答例としてご活用ください！

全100問の解説に戻る

準備

夏目漱石の小説『吾輩は猫である』の文章（neko.txt）をCaboChaを使って係り受け解析し，その結果をneko.txt.cabochaというファイルに保存せよ．このファイルを用いて，以下の問に対応するプログラムを実装せよ．

cabochaをインストールしていない方はインストールしておいて下さい。Macの場合、下記のコマンドでOKです。

1
brew install cabocha

リンクからneko.txtをダウンロードして、下記のコマンドを実行します。

1
cabocha -f1 < neko.txt > neko.txt.cabocha

これで準備完了です。

40. 係り受け解析結果の読み込み（形態素）

形態素を表すクラスMorphを実装せよ．このクラスは表層形（surface），基本形（base），品詞（pos），品詞細分類1（pos1）をメンバ変数に持つこととする．さらに，CaboChaの解析結果（neko.txt.cabocha）を読み込み，各文をMorphオブジェクトのリストとして表現し，3文目の形態素列を表示せよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Morph:
    def __init__(self, surface, base, pos, pos1):
        self.surface = surface
        self.base = base
        self.pos = pos
        self.pos1 = pos1
    def show(self):
        print (self.surface, self.base, self.pos, self.pos1)
path = 'neko.txt.cabocha'
with open(path) as f:
    text = f.read().split('\n')
result = []
morphs = []
for line in text[:-1]:
    if line == 'EOS':
        result.append(morphs)
        morphs = []
    elif line[0] == '*':
        continue
    else:
        ls = line.split('\t')
        d = {}
        tmp = ls[1].split(',')
        morph = Morph(ls[0],tmp[6],tmp[0],tmp[1])
        morphs.append(morph)
for morphs in result[2]:
    morphs.show()

EOSや解析結果（先頭が*から始まる）などの特殊な行に注意しましょう。

41. 係り受け解析結果の読み込み（文節・係り受け）

40に加えて，文節を表すクラスChunkを実装せよ．このクラスは形態素（Morphオブジェクト）のリスト（morphs），係り先文節インデックス番号（dst），係り元文節インデックス番号のリスト（srcs）をメンバ変数に持つこととする．さらに，入力テキストのCaboChaの解析結果を読み込み，１文をChunkオブジェクトのリストとして表現し，8文目の文節の文字列と係り先を表示せよ．第5章の残りの問題では，ここで作ったプログラムを活用せよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class Morph:
    def __init__(self, surface, base, pos, pos1):
        self.surface = surface
        self.base = base
        self.pos = pos
        self.pos1 = pos1
    def show(self):
        print (self.surface, self.base, self.pos, self.pos1)
        
class Chunk:
    def __init__(self, sentence_id, chunk_id, dst, srcs):
        self.sentence_id = sentence_id
        self.chunk_id = chunk_id
        self.morphs = []
        self.dst = dst
        self.srcs = srcs
    def show_morphs(self):
        morphs = ''
        for morph in self.morphs:
            morphs += morph.surface
        print ("morphs:",morphs)
    def show_chunk_id(self):
        print ("==========")
        print ("chunk_id:",self.chunk_id)
    def show_sentence_id(self):
        if (self.chunk_id == 0):
            print ("====================")
            print ("sentence_id:",self.sentence_id)      
    def show_dst(self):
        print ("dst:",self.dst)     
    def show_srcs(self):
        print ("srcs:",self.srcs[self.chunk_id])            
        
path = 'neko.txt.cabocha'
with open(path) as f:
    text = f.read().split('\n')
result = []
morphs = []
chunks = []
srcs = [[]]
chunk = None
sentence_id = 0
chunk_id = 0

for line in text[:-1]:
    if line == 'EOS':
        result.append(morphs)
        morphs = []
        sentence_id += 1
        chunk_id = 0
        srcs = [[]]

    elif line[0] == '*':
        if chunk:
            chunks.append(chunk)
        dst = int(line.split()[2][:-1])
        diff = dst + 1- len(srcs)
        ex = [[] for _ in range(diff)]
        srcs.extend(ex)
        if dst!=-1:
            srcs[dst].append(chunk_id)
        chunk = Chunk(sentence_id, chunk_id, dst, srcs)
        chunk_id += 1
      
    else:
        ls = line.split('\t')
        d = {}
        tmp = ls[1].split(',')
        morph = Morph(ls[0],tmp[6],tmp[0],tmp[1])
        morphs.append(morph)
        chunk.morphs.append(morph)
        
else:
    chunks.append(chunk)
for i,chunk in enumerate(chunks):
    if chunk.sentence_id == 7:
        chunk.show_sentence_id()
        chunk.show_chunk_id()
        chunk.show_dst()
        chunk.show_srcs()
        chunk.show_morphs()

係り先文節インデックス番号(dst)は解析結果として得られているのでそのまま利用すれば良いですが、
係り元文節インデックス番号のリスト(srcs)は自前で用意する必要があります。

そこでdstの集計と並行して、srcs[dst]を作成します。この時点では文節の数が不明なので、必要に応じてsrcsをextendします。

42. 係り元と係り先の文節の表示

係り元の文節と係り先の文節のテキストをタブ区切り形式ですべて抽出せよ．ただし，句読点などの記号は出力しないようにせよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import itertools
class Morph:
    def __init__(self, surface, base, pos, pos1):
        self.surface = surface
        self.base = base
        self.pos = pos
        self.pos1 = pos1
    def show(self):
        print (self.surface, self.base, self.pos, self.pos1)
        
class Chunk:
    def __init__(self, sentence_id, chunk_id, dst, srcs):
        self.sentence_id = sentence_id
        self.chunk_id = chunk_id
        self.morphs = []
        self.dst = dst
        self.srcs = srcs
    def show_morphs(self):
        morphs = ''
        for morph in self.morphs:
            morphs += morph.surface
        print ("morphs:",morphs)
    def show_chunk_id(self):
        print ("==========")
        print ("chunk_id:",self.chunk_id)
    def show_sentence_id(self):
        if (self.chunk_id == 0):
            print ("====================")
            print ("sentence_id:",self.sentence_id)      
    def show_dst(self):
        print ("dst:",self.dst)     
    def show_srcs(self):
        print ("srcs:",self.srcs[self.chunk_id])            
        
path = 'neko.txt.cabocha'
with open(path) as f:
    text = f.read().split('\n')
result = []
morphs = []
chunks = []
srcs = [[]]
chunk = None
sentence_id = 0
chunk_id = 0

for line in text[:-1]:
    if line == 'EOS':
        result.append(morphs)
        morphs = []
        sentence_id += 1
        chunk_id = 0
        srcs = [[]]

    elif line[0] == '*':
        if chunk:
            chunks.append(chunk)
        dst = int(line.split()[2][:-1])
        diff = dst + 1- len(srcs)
        ex = [[] for _ in range(diff)]
        srcs.extend(ex)
        if dst!=-1:
            srcs[dst].append(chunk_id)
        chunk = Chunk(sentence_id, chunk_id, dst, srcs)
        chunk_id += 1
      
    else:
        ls = line.split('\t')
        d = {}
        tmp = ls[1].split(',')
        morph = Morph(ls[0],tmp[6],tmp[0],tmp[1])
        morphs.append(morph)
        chunk.morphs.append(morph)
        
else:
    chunks.append(chunk)

sentences = [[] for _ in range(len(chunks))]
for chunk in chunks:
    morphs = ''
    for morph in chunk.morphs:
        morphs += morph.surface
    sentences[chunk.sentence_id].append(morphs)

dsts = [[] for _ in range(len(chunks))]
for chunk in chunks:
    dst = sentences[chunk.sentence_id][chunk.dst]
    dsts[chunk.sentence_id].append(dst)
sentences = list(itertools.chain.from_iterable(sentences))
dsts = list(itertools.chain.from_iterable(dsts))
for i, (s, d) in enumerate(zip(sentences, dsts)):
    s = s.replace("　","").replace("。","").replace("、","")
    d = d.replace("　","").replace("。","").replace("、","")
    if s==d or s=='' or d=='':
        continue
    print (s,d)

itertools.chain.from_iterableを使って二次元リストを一次元リストに変換している。

43. 名詞を含む文節が動詞を含む文節に係るものを抽出

名詞を含む文節が，動詞を含む文節に係るとき，これらをタブ区切り形式で抽出せよ．ただし，句読点などの記号は出力しないようにせよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
import itertools
class Morph:
    def __init__(self, surface, base, pos, pos1):
        self.surface = surface
        self.base = base
        self.pos = pos
        self.pos1 = pos1
    def show(self):
        print (self.surface, self.base, self.pos, self.pos1)
        
class Chunk:
    def __init__(self, sentence_id, chunk_id, dst, srcs):
        self.sentence_id = sentence_id
        self.chunk_id = chunk_id
        self.morphs = []
        self.dst = dst
        self.srcs = srcs
        self.has_noun = False
        self.has_verb = False
        self.surfaces = ''
    def show_morphs(self):
        morphs = ''
        for morph in self.morphs:
            morphs += morph.surface
        print ("morphs:",morphs)
    def show_chunk_id(self):
        print ("==========")
        print ("chunk_id:",self.chunk_id)
    def show_sentence_id(self):
        if (self.chunk_id == 0):
            print ("====================")
            print ("sentence_id:",self.sentence_id)      
    def show_dst(self):
        print ("dst:",self.dst)     
    def show_srcs(self):
        print ("srcs:",self.srcs[self.chunk_id])            
        
path = 'neko.txt.cabocha'
with open(path) as f:
    text = f.read().split('\n')
result = []
morphs = []
chunks = []
srcs = [[]]
chunk = None
sentence_id = 0
chunk_id = 0

for line in text[:-1]:
    if line == 'EOS':
        result.append(morphs)
        morphs = []
        sentence_id += 1
        chunk_id = 0
        srcs = [[]]

    elif line[0] == '*':
        if chunk:
            chunks.append(chunk)
        dst = int(line.split()[2][:-1])
        diff = dst + 1- len(srcs)
        ex = [[] for _ in range(diff)]
        srcs.extend(ex)
        if dst!=-1:
            srcs[dst].append(chunk_id)
        chunk = Chunk(sentence_id, chunk_id, dst, srcs)
        chunk_id += 1
      
    else:
        ls = line.split('\t')
        d = {}
        tmp = ls[1].split(',')
        morph = Morph(ls[0],tmp[6],tmp[0],tmp[1])
        morphs.append(morph)
        chunk.morphs.append(morph)
        
else:
    chunks.append(chunk)

sentences = [[] for _ in range(len(chunks))]
for chunk in chunks:
    for morph in chunk.morphs:
        chunk.surfaces += morph.surface
        if morph.pos == '動詞':
            chunk.has_verb = True
        elif morph.pos == '名詞':
            chunk.has_noun = True

    
    sentences[chunk.sentence_id].append(chunk)

dsts = [[] for _ in range(len(chunks))]
for chunk in chunks:
    dst = sentences[chunk.sentence_id][chunk.dst]
    dsts[chunk.sentence_id].append(dst)
sentences = list(itertools.chain.from_iterable(sentences))
dsts = list(itertools.chain.from_iterable(dsts))
for i, (sentence, dst) in enumerate(zip(sentences, dsts)):
    if sentence.has_noun and dst.has_verb:
        s = sentence.surfaces
        d = dst.surfaces

        s = s.replace("　","").replace("。","").replace("、","")
        d = d.replace("　","").replace("。","").replace("、","")
        if s==d or s=='' or d=='':
                continue
        print (s,d)

クラスChunkに以下のインスタンス変数を追加しました。

1
2
3
self.has_noun = False
self.has_verb = False
self.surfaces = ''

44. 係り受け木の可視化

与えられた文の係り受け木を有向グラフとして可視化せよ．可視化には，係り受け木をDOT言語に変換し，Graphvizを用いるとよい．また，Pythonから有向グラフを直接的に可視化するには，pydotを使うとよい

準備

今回はpydotを利用した。必要があればインストールする。

1
pip install pydot

pydotはgraphvizのインターフェイスを提供するものなので、graphviz本体も必要があればインストールする。

1
brew install graphviz

pydotの基本

公式の情報が見当たりませんでしたので、こちらを参考にさせていただきました。

グラフの構築

1
graph = pydot.Dot()
1
graph = pydot.Dot(graph_type='digraph') # 有向グラフ
1
graph = pydot.Dot(graph_type='graph') # # 無向グラフ

ノードの追加

1
2
node_a = pydot.Node("Node A")
node_b = pydot.Node("Node B")

エッジの追加

1
graph.add_edge(pydot.Edge(node_a, node_b))

グラフを画像として保存

1
graph.write_png('output.png')

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import itertools
import pydot
class Morph:
    def __init__(self, surface, base, pos, pos1):
        self.surface = surface
        self.base = base
        self.pos = pos
        self.pos1 = pos1
    def show(self):
        print (self.surface, self.base, self.pos, self.pos1)
        
class Chunk:
    def __init__(self, sentence_id, chunk_id, dst, srcs):
        self.sentence_id = sentence_id
        self.chunk_id = chunk_id
        self.morphs = []
        self.dst = dst
        self.srcs = srcs
        self.has_noun = False
        self.has_verb = False
        self.surfaces = ''
    def show_morphs(self):
        morphs = ''
        for morph in self.morphs:
            morphs += morph.surface
        print ("morphs:",morphs)
    def show_chunk_id(self):
        print ("==========")
        print ("chunk_id:",self.chunk_id)
    def show_sentence_id(self):
        if (self.chunk_id == 0):
            print ("====================")
            print ("sentence_id:",self.sentence_id)      
    def show_dst(self):
        print ("dst:",self.dst)     
    def show_srcs(self):
        print ("srcs:",self.srcs[self.chunk_id])            
        
path = 'neko.txt.cabocha'
with open(path) as f:
    text = f.read().split('\n')
result = []
morphs = []
chunks = []
srcs = [[]]
chunk = None
sentence_id = 0
chunk_id = 0

for line in text[:-1]:
    if line == 'EOS':
        result.append(morphs)
        morphs = []
        sentence_id += 1
        chunk_id = 0
        srcs = [[]]

    elif line[0] == '*':
        if chunk:
            chunks.append(chunk)
        dst = int(line.split()[2][:-1])
        diff = dst + 1- len(srcs)
        ex = [[] for _ in range(diff)]
        srcs.extend(ex)
        if dst!=-1:
            srcs[dst].append(chunk_id)
        chunk = Chunk(sentence_id, chunk_id, dst, srcs)
        chunk_id += 1
      
    else:
        ls = line.split('\t')
        d = {}
        tmp = ls[1].split(',')
        morph = Morph(ls[0],tmp[6],tmp[0],tmp[1])
        morphs.append(morph)
        chunk.morphs.append(morph)
        
else:
    chunks.append(chunk)

sentences = [[] for _ in range(len(chunks))]
for chunk in chunks:
    for morph in chunk.morphs:
        chunk.surfaces += morph.surface

    sentences[chunk.sentence_id].append(chunk)
graph = pydot.Dot(graph_type='digraph') # 無向グラフを指定したければ(graph_type='graph')とする
nodes = []
for chunk in sentences[7]: # 例として8番目の文章を使う
    node = pydot.Node(chunk.surfaces)
    graph.add_node(node)
    nodes.append((node,chunk.dst))
for node, dst in nodes:
    if dst != -1:
        graph.add_edge(pydot.Edge(node, nodes[dst][0]))
graph.write_png('output44.png')

下記のような画像が出力されれば成功です。

45. 動詞の格パターンの抽出

今回用いている文章をコーパスと見なし，日本語の述語が取りうる格を調査したい． 動詞を述語，動詞に係っている文節の助詞を格と考え，述語と格をタブ区切り形式で出力せよ． ただし，出力は以下の仕様を満たすようにせよ．

  • 動詞を含む文節において，最左の動詞の基本形を述語とする
  • 述語に係る助詞を格とする
  • 述語に係る助詞（文節）が複数あるときは，すべての助詞をスペース区切りで辞書順に並べる

「吾輩はここで始めて人間というものを見た」という例文（neko.txt.cabochaの8文目）を考える． この文は「始める」と「見る」の２つの動詞を含み，「始める」に係る文節は「ここで」，「見る」に係る文節は「吾輩は」と「ものを」と解析された場合は，次のような出力になるはずである．

1
2
始める  で
見る    は を

このプログラムの出力をファイルに保存し，以下の事項をUNIXコマンドを用いて確認せよ．

  • コーパス中で頻出する述語と格パターンの組み合わせ
  • 「する」「見る」「与える」という動詞の格パターン（コーパス中で出現頻度の高い順に並べよ）

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
import itertools
class Morph:
    def __init__(self, surface, base, pos, pos1):
        self.surface = surface
        self.base = base
        self.pos = pos
        self.pos1 = pos1
    def show(self):
        print (self.surface, self.base, self.pos, self.pos1)
        
class Chunk:
    def __init__(self, sentence_id, chunk_id, dst, srcs):
        self.sentence_id = sentence_id
        self.chunk_id = chunk_id
        self.morphs = []
        self.dst = dst
        self.srcs = srcs
        self.has_noun = False
        self.has_verb = False
        self.has_particle = False
        self.surfaces = ''
        self.first_verb = None
        self.particle = []
    def show_morphs(self):
        morphs = ''
        for morph in self.morphs:
            morphs += morph.surface
        print ("morphs:",morphs)
    def show_chunk_id(self):
        print ("==========")
        print ("chunk_id:",self.chunk_id)
    def show_sentence_id(self):
        if (self.chunk_id == 0):
            print ("====================")
            print ("sentence_id:",self.sentence_id)      
    def show_dst(self):
        print ("dst:",self.dst)     
    def show_srcs(self):
        print ("srcs:",self.srcs[self.chunk_id])            
        
path = 'neko.txt.cabocha'
with open(path) as f:
    text = f.read().split('\n')
result = []
morphs = []
chunks = []
srcs = [[]]
chunk = None
sentence_id = 0
chunk_id = 0

for line in text[:-1]:
    if line == 'EOS':
        result.append(morphs)
        morphs = []
        sentence_id += 1
        chunk_id = 0
        srcs = [[]]

    elif line[0] == '*':
        if chunk:
            chunks.append(chunk)
        dst = int(line.split()[2][:-1])
        diff = dst + 1- len(srcs)
        ex = [[] for _ in range(diff)]
        srcs.extend(ex)
        if dst!=-1:
            srcs[dst].append(chunk_id)
        chunk = Chunk(sentence_id, chunk_id, dst, srcs)
        chunk_id += 1
      
    else:
        ls = line.split('\t')
        d = {}
        tmp = ls[1].split(',')
        morph = Morph(ls[0],tmp[6],tmp[0],tmp[1])
        morphs.append(morph)
        chunk.morphs.append(morph)
        
else:
    chunks.append(chunk)

sentences = [[] for _ in range(len(chunks))]
for chunk in chunks:
    for morph in chunk.morphs:
        chunk.surfaces += morph.surface
        if morph.pos == '動詞':
            if chunk.has_verb == False:
                chunk.first_verb = morph.base
            chunk.has_verb = True
        elif morph.pos == '名詞':
            chunk.has_noun = True
        elif morph.pos == '助詞':
            chunk.has_particle = True
            chunk.particle.append(morph.surface)

    
    sentences[chunk.sentence_id].append(chunk)

dsts = [[] for _ in range(len(chunks))]
for chunk in chunks:
    dst = sentences[chunk.sentence_id][chunk.dst]
    dsts[chunk.sentence_id].append(dst)
    
with open('45.txt', mode='w') as f:
    for i,(sentence,dst) in enumerate(zip(sentences,dsts)):
        dic = {}
        for s,d in zip(sentence,dst):
            if s.particle and d.first_verb:
                old = dic.get(d.first_verb, [])
                dic[d.first_verb] = old + s.particle

        for k,v in dic.items():
            output = k+'\t'+" ".join(sorted(v))+'\n'
            f.write(output)

確認

1
sort 45.txt | uniq -c | sort -n -r | head
1
2
3
4
5
6
7
8
9
10
417 云う	と
256 する	を
212 思う	と
158 ある	が
156 見る	て
145 なる	に
110 する	に
 87 見える	と
 81 見る	を
 68 する	と
1
grep "^する\t" 45.txt | sort | uniq -c | sort -n -r | head
1
2
3
4
5
6
7
8
9
10
256 する	を
110 する	に
 68 する	と
 67 する	に を
 67 する	が
 54 する	て を
 37 する	は
 36 する	が を
 30 する	で を
 30 する	て
1
grep "^見る\t" 45.txt | sort | uniq -c | sort -n -r | head
1
2
3
4
5
6
7
8
9
10
156 見る	て
 81 見る	を
 17 見る	から
 16 見る	て て
 14 見る	て を
 12 見る	から て
 12 見る	と
 10 見る	で
  9 見る	て は
  7 見る	に
1
grep "^与える\t" 45.txt | sort | uniq -c | sort -n -r | head
1
2
3
4
5
6
7
8
9
10
3 与える	に を
2 与える	て に は を
1 与える	けれども に は を
1 与える	から が て て と に は は を
1 与える	つつ て に に は を
1 与える	だけ で に を
1 与える	たり て に を
1 与える	に に対して のみ は は も
1 与える	か じゃあ て と は を
1 与える	か として ば を を

46. 動詞の格フレーム情報の抽出

45のプログラムを改変し，述語と格パターンに続けて項（述語に係っている文節そのもの）をタブ区切り形式で出力せよ．45の仕様に加えて，以下の仕様を満たすようにせよ．

  • 項は述語に係っている文節の単語列とする（末尾の助詞を取り除く必要はない）
  • 述語に係る文節が複数あるときは，助詞と同一の基準・順序でスペース区切りで並べる

「吾輩はここで始めて人間というものを見た」という例文（neko.txt.cabochaの8文目）を考える． この文は「始める」と「見る」の２つの動詞を含み，「始める」に係る文節は「ここで」，「見る」に係る文節は「吾輩は」と「ものを」と解析された場合は，次のような出力になるはずである．

1
2
始める  で      ここで
見る    は を   吾輩は ものを

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import itertools
class Morph:
    def __init__(self, surface, base, pos, pos1):
        self.surface = surface
        self.base = base
        self.pos = pos
        self.pos1 = pos1
    def show(self):
        print (self.surface, self.base, self.pos, self.pos1)
        
class Chunk:
    def __init__(self, sentence_id, chunk_id, dst, srcs):
        self.sentence_id = sentence_id
        self.chunk_id = chunk_id
        self.morphs = []
        self.dst = dst
        self.srcs = srcs
        self.has_noun = False
        self.has_verb = False
        self.has_particle = False
        self.surfaces = ''
        self.first_verb = None
        self.particle = []
    def show_morphs(self):
        morphs = ''
        for morph in self.morphs:
            morphs += morph.surface
        print ("morphs:",morphs)
    def show_chunk_id(self):
        print ("==========")
        print ("chunk_id:",self.chunk_id)
    def show_sentence_id(self):
        if (self.chunk_id == 0):
            print ("====================")
            print ("sentence_id:",self.sentence_id)      
    def show_dst(self):
        print ("dst:",self.dst)     
    def show_srcs(self):
        print ("srcs:",self.srcs[self.chunk_id])            
        
path = 'neko.txt.cabocha'
with open(path) as f:
    text = f.read().split('\n')
result = []
morphs = []
chunks = []
srcs = [[]]
chunk = None
sentence_id = 0
chunk_id = 0

for line in text[:-1]:
    if line == 'EOS':
        result.append(morphs)
        morphs = []
        sentence_id += 1
        chunk_id = 0
        srcs = [[]]

    elif line[0] == '*':
        if chunk:
            chunks.append(chunk)
        dst = int(line.split()[2][:-1])
        diff = dst + 1- len(srcs)
        ex = [[] for _ in range(diff)]
        srcs.extend(ex)
        if dst!=-1:
            srcs[dst].append(chunk_id)
        chunk = Chunk(sentence_id, chunk_id, dst, srcs)
        chunk_id += 1
      
    else:
        ls = line.split('\t')
        d = {}
        tmp = ls[1].split(',')
        morph = Morph(ls[0],tmp[6],tmp[0],tmp[1])
        morphs.append(morph)
        chunk.morphs.append(morph)
        
else:
    chunks.append(chunk)

sentences = [[] for _ in range(len(chunks))]
for chunk in chunks:
    for morph in chunk.morphs:
        chunk.surfaces += morph.surface
        if morph.pos == '動詞':
            if chunk.has_verb == False:
                chunk.first_verb = morph.base
            chunk.has_verb = True
        elif morph.pos == '名詞':
            chunk.has_noun = True
        elif morph.pos == '助詞':
            chunk.has_particle = True
            chunk.particle.append(morph.surface)

    
    sentences[chunk.sentence_id].append(chunk)

dsts = [[] for _ in range(len(chunks))]
for chunk in chunks:
    dst = sentences[chunk.sentence_id][chunk.dst]
    dsts[chunk.sentence_id].append(dst)
    
with open('46.txt', mode='w') as f:
    for i,(sentence,dst) in enumerate(zip(sentences,dsts)):
        dic = {}

        for s,d in zip(sentence,dst):
            if s.particle and d.first_verb:
                old = dic.get(d.first_verb, [])
                surfaces = s.surfaces.replace("　","").replace("。","").replace("、","")
                for p in s.particle:
                    dic[d.first_verb] = old + [[p, surfaces]]
        for k,v in dic.items():
            ls = sorted(v)
            ls = list(zip(*ls))
            output = k+'\t'+" ".join(ls[0])+'\t'+" ".join(ls[1])+'\n'
            f.write(output)

47. 機能動詞構文のマイニング

動詞のヲ格にサ変接続名詞が入っている場合のみに着目したい．46のプログラムを以下の仕様を満たすように改変せよ．

  • 「サ変接続名詞+を（助詞）」で構成される文節が動詞に係る場合のみを対象とする
  • 述語は「サ変接続名詞+を+動詞の基本形」とし，文節中に複数の動詞があるときは，最左の動詞を用いる
  • 述語に係る助詞（文節）が複数あるときは，すべての助詞をスペース区切りで辞書順に並べる
  • 述語に係る文節が複数ある場合は，すべての項をスペース区切りで並べる（助詞の並び順と揃えよ）

例えば「別段くるにも及ばんさと、主人は手紙に返事をする。」という文から，以下の出力が得られるはずである．

1
返事をする      と に は        及ばんさと 手紙に 主人は

このプログラムの出力をファイルに保存し，以下の事項をUNIXコマンドを用いて確認せよ．

  • コーパス中で頻出する述語（サ変接続名詞+を+動詞）
  • コーパス中で頻出する述語と助詞パターン

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
import itertools
class Morph:
    def __init__(self, surface, base, pos, pos1):
        self.surface = surface
        self.base = base
        self.pos = pos
        self.pos1 = pos1
    
    def show(self):
        print (self.surface, self.base, self.pos, self.pos1)
        
class Chunk:
    def __init__(self, sentence_id, chunk_id, dst, srcs):
        self.sentence_id = sentence_id
        self.chunk_id = chunk_id
        self.morphs = []
        self.dst = dst
        self.srcs = srcs
        self.has_noun = False
        self.has_verb = False
        self.has_particle = False
        self.surfaces = ''
        self.first_verb = None
        self.particle = []
        self.sahen_wo = False

    def show_morphs(self):
        morphs = ''
        for morph in self.morphs:
            morphs += morph.surface
        print ("morphs:",morphs)
    def show_chunk_id(self):
        print ("==========")
        print ("chunk_id:",self.chunk_id)
    def show_sentence_id(self):
        if (self.chunk_id == 0):
            print ("====================")
            print ("sentence_id:",self.sentence_id)      
    def show_dst(self):
        print ("dst:",self.dst)     
    def show_srcs(self):
        print ("srcs:",self.srcs[self.chunk_id])            
        
path = 'neko.txt.cabocha'

with open(path) as f:
    text = f.read().split('\n')
result = []
morphs = []
chunks = []
srcs = [[]]
chunk = None
sentence_id = 0
chunk_id = 0

for line in text[:-1]:
    if line == 'EOS':
        result.append(morphs)
        morphs = []
        sentence_id += 1
        chunk_id = 0
        srcs = [[]]

    elif line[0] == '*':
        if chunk:
            chunks.append(chunk)
        dst = int(line.split()[2][:-1])
        diff = dst + 1- len(srcs)
        ex = [[] for _ in range(diff)]
        srcs.extend(ex)
        if dst!=-1:
            srcs[dst].append(chunk_id)
        chunk = Chunk(sentence_id, chunk_id, dst, srcs)
        chunk_id += 1
      
    else:
        ls = line.split('\t')
        d = {}
        tmp = ls[1].split(',')
        morph = Morph(ls[0],tmp[6],tmp[0],tmp[1])
        morphs.append(morph)
        chunk.morphs.append(morph)
        
else:
    chunks.append(chunk)

sentences = [[] for _ in range(len(chunks))]
sahen_wo = None
for chunk in chunks:
    sahen = False

    for morph in chunk.morphs:
        
        chunk.surfaces += morph.surface

        if morph.pos == '動詞':
            
            if chunk.has_verb == False and sahen_wo:
                chunk.first_verb = sahen_wo + morph.base
                sahen_wo = None
            chunk.has_verb = True
            
        elif morph.surface == 'を' and morph.pos == '助詞' and sahen:
            sahen_wo = sahen + 'を'
         
            
        elif morph.pos == '助詞':
            chunk.has_particle = True
            chunk.particle.append(morph.surface)
            
        if morph.pos1 == 'サ変接続':
            sahen = morph.surface
        else:
            sahen = False
    
    sentences[chunk.sentence_id].append(chunk)

dsts = [[] for _ in range(len(chunks))]
for chunk in chunks:
    dst = sentences[chunk.sentence_id][chunk.dst]
    dsts[chunk.sentence_id].append(dst)
    
with open('47.txt', mode='w') as f:
    for i,(sentence,dst) in enumerate(zip(sentences,dsts)):
        dic = {}

        for s,d in zip(sentence,dst):
            if s.particle and d.first_verb:
                old = dic.get(d.first_verb, [])
                surfaces = s.surfaces.replace("　","").replace("。","").replace("、","")
                for p in s.particle:
                    dic[d.first_verb] = old + [[p, surfaces]]
        for k,v in dic.items():
            ls = sorted(v)
            ls = list(zip(*ls))
            output = k+'\t'+" ".join(ls[0])+'\t'+" ".join(ls[1])+'\n'
            print (output)
            f.write(output)

文節をまたいで、サ変接続名詞+を（助詞）扱うためにグローバル変数sahen_woを用意しましたが、もう少し良い方法がありそうです。

1
cut -f 1  47.txt | sort | uniq -c | sort -n -r | head
1
2
3
4
5
6
7
8
9
10
26 返事をする
19 挨拶をする
12 話をする
 8 質問をする
 7 喧嘩をする
 6 真似をする
 5 質問をかける
 5 相談をする
 5 注意をする
 5 昼寝をする
1
cut -f 1,2  47.txt | sort | uniq -c | sort -n -r | head
1
2
3
4
5
6
7
8
9
10
6 返事をする	と
4 返事をする	と は
4 挨拶をする	と
3 質問をかける	と は
3 挨拶をする	から
3 喧嘩をする	と
2 同情を表する	て と は
2 休養を要する	は
2 挨拶をする	と も
2 講義をする	で

48. 名詞から根へのパスの抽出

文中のすべての名詞を含む文節に対し，その文節から構文木の根に至るパスを抽出せよ． ただし，構文木上のパスは以下の仕様を満たすものとする．

  • 各文節は（表層形の）形態素列で表現する
  • パスの開始文節から終了文節に至るまで，各文節の表現を” -> “で連結する

「吾輩はここで始めて人間というものを見た」という文（neko.txt.cabochaの8文目）から，次のような出力が得られるはずである．

1
2
3
4
吾輩は -> 見た
ここで -> 始めて -> 人間という -> ものを -> 見た
人間という -> ものを -> 見た
ものを -> 見た

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
import itertools
class Morph:
    def __init__(self, surface, base, pos, pos1):
        self.surface = surface
        self.base = base
        self.pos = pos
        self.pos1 = pos1
    
    def show(self):
        print (self.surface, self.base, self.pos, self.pos1)
        
class Chunk:
    def __init__(self, sentence_id, chunk_id, dst, srcs):
        self.sentence_id = sentence_id
        self.chunk_id = chunk_id
        self.morphs = []
        self.dst = dst
        self.srcs = srcs
        self.has_noun = False
        self.has_verb = False
        self.has_particle = False
        self.surfaces = ''
        self.first_verb = None
        self.particle = []
        self.sahen_wo = False

    def show_morphs(self):
        morphs = ''
        for morph in self.morphs:
            morphs += morph.surface
        print ("morphs:",morphs)
    def show_chunk_id(self):
        print ("==========")
        print ("chunk_id:",self.chunk_id)
    def show_sentence_id(self):
        if (self.chunk_id == 0):
            print ("====================")
            print ("sentence_id:",self.sentence_id)      
    def show_dst(self):
        print ("dst:",self.dst)     
    def show_srcs(self):
        print ("srcs:",self.srcs[self.chunk_id])          
        
path = 'neko.txt.cabocha'
with open(path) as f:
    text = f.read().split('\n')
result = []
morphs = []
chunks = []
srcs = [[]]
chunk = None
sentence_id = 0
chunk_id = 0

for line in text[:-1]:
    if line == 'EOS':
        result.append(morphs)
        morphs = []
        sentence_id += 1
        chunk_id = 0
        srcs = [[]]

    elif line[0] == '*':
        if chunk:
            chunks.append(chunk)
        dst = int(line.split()[2][:-1])
        diff = dst + 1- len(srcs)
        ex = [[] for _ in range(diff)]
        srcs.extend(ex)
        if dst!=-1:
            srcs[dst].append(chunk_id)
        chunk = Chunk(sentence_id, chunk_id, dst, srcs)
        chunk_id += 1
      
    else:
        ls = line.split('\t')
        d = {}
        tmp = ls[1].split(',')
        morph = Morph(ls[0],tmp[6],tmp[0],tmp[1])
        morphs.append(morph)
        chunk.morphs.append(morph)
        
else:
    chunks.append(chunk)

sentences = [[] for _ in range(len(chunks))]
for chunk in chunks:
    morphs = ''
    for morph in chunk.morphs:
        morphs += morph.surface
        if morph.pos == '名詞':
            chunk.has_noun = True
    sentences[chunk.sentence_id].append([morphs,chunk.dst,chunk.has_noun])

def rec(sentence,d,ans):
    if d == -1:
        return ans
    else:
        return rec(sentence,sentence[d][1],ans+' -> '+sentence[d][0])

with open('48.txt', mode='w') as f:
    for i, sentence in enumerate(sentences):
        for s,d,has_noun in sentence:
            if has_noun:
                ans = rec(sentence,d,s)
                ans = ans.replace("　","").replace("。","").replace("、","")
                print (ans)
                f.write(ans+'\n')

再帰関数recを導入した。

49. 名詞間の係り受けパスの抽出

文中のすべての名詞句のペアを結ぶ最短係り受けパスを抽出せよ．ただし，名詞句ペアの文節番号がiとj（i<j）のとき，係り受けパスは以下の仕様を満たすものとする

  • 問題48と同様に，パスは開始文節から終了文節に至るまでの各文節の表現（表層形の形態素列）を” -> “で連結して表現する
  • 文節iとjに含まれる名詞句はそれぞれ，XとYに置換する

また，係り受けパスの形状は，以下の2通りが考えられる．

  • 文節iから構文木の根に至る経路上に文節jが存在する場合: 文節iから文節jのパスを表示
  • 上記以外で，文節iと文節jから構文木の根に至る経路上で共通の文節kで交わる場合: 文節iから文節kに至る直前のパスと文節jから文節kに至る直前までのパス，文節kの内容を” | “で連結して表示

例えば，「吾輩はここで始めて人間というものを見た。」という文（neko.txt.cabochaの8文目）から，次のような出力が得られるはずである．

1
2
3
4
5
6
Xは | Yで -> 始めて -> 人間という -> ものを | 見た
Xは | Yという -> ものを | 見た
Xは | Yを | 見た
Xで -> 始めて -> Y
Xで -> 始めて -> 人間という -> Y
Xという -> Y
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import itertools
class Morph:
    def __init__(self, surface, base, pos, pos1):
        self.surface = surface
        self.base = base
        self.pos = pos
        self.pos1 = pos1
    
    def show(self):
        print (self.surface, self.base, self.pos, self.pos1)
        
class Chunk:
    def __init__(self, sentence_id, chunk_id, dst, srcs):
        self.sentence_id = sentence_id
        self.chunk_id = chunk_id
        self.morphs = []
        self.dst = dst
        self.srcs = srcs
        self.has_noun = False
        self.has_verb = False
        self.has_particle = False
        self.surfaces = ''
        self.first_verb = None
        self.first_noun = None
        self.particle = []
        self.sahen_wo = False

    def show_morphs(self):
        morphs = ''
        for morph in self.morphs:
            morphs += morph.surface
        print ("morphs:",morphs)
    def show_chunk_id(self):
        print ("==========")
        print ("chunk_id:",self.chunk_id)
    def show_sentence_id(self):
        if (self.chunk_id == 0):
            print ("====================")
            print ("sentence_id:",self.sentence_id)      
    def show_dst(self):
        print ("dst:",self.dst)     
    def show_srcs(self):
        print ("srcs:",self.srcs[self.chunk_id])          
        
path = 'neko.txt.cabocha'
with open(path) as f:
    text = f.read().split('\n')
result = []
morphs = []
chunks = []
srcs = [[]]
chunk = None
sentence_id = 0
chunk_id = 0

for line in text[:-1]:
    if line == 'EOS':
        result.append(morphs)
        morphs = []
        sentence_id += 1
        chunk_id = 0
        srcs = [[]]

    elif line[0] == '*':
        if chunk:
            chunks.append(chunk)
        dst = int(line.split()[2][:-1])
        diff = dst + 1- len(srcs)
        ex = [[] for _ in range(diff)]
        srcs.extend(ex)
        if dst!=-1:
            srcs[dst].append(chunk_id)
        chunk = Chunk(sentence_id, chunk_id, dst, srcs)
        chunk_id += 1
      
    else:
        ls = line.split('\t')
        d = {}
        tmp = ls[1].split(',')
        morph = Morph(ls[0],tmp[6],tmp[0],tmp[1])
        morphs.append(morph)
        chunk.morphs.append(morph)
        
else:
    chunks.append(chunk)

sentences = [[] for _ in range(len(chunks))]
for chunk in chunks:
    morphs = ''
    for morph in chunk.morphs:
        
        if morph.pos == '名詞':
            chunk.has_noun = True
            chunk.first_noun = morph.surface
        morphs += morph.surface
    sentences[chunk.sentence_id].append([morphs,chunk.dst,chunk.has_noun,chunk.first_noun])

def rec(sentence,d,ans):
    if d == -1:
        return ans
    else:
        return rec(sentence,sentence[d][1],ans+' -> '+sentence[d][0])
def get_path(d,ls):
    ls += [d]
    if d == -1:
        return ls
    else:
        return get_path(sentence[d][1],ls)

def gen_arrow(path, xy):
    new = []
    for i,node in enumerate(path):
        if node == match:
            break
        morph = sentence[node][0]
        if i==0:
            morph = morph.replace(sentence[node][3], xy)
        new.append(morph)
    return ' -> '.join(new)
    
with open('49.txt', mode='w') as f:
    for i, sentence in enumerate(sentences):
#         if i!=7:
#             continue
        ls_path = []
        for j,(s,d,has_noun,first_noun) in enumerate(sentence):
            if has_noun:
                ans = rec(sentence,d,s)
                ans = ans.replace("　","").replace("。","").replace("、","")
                ls_path.append(get_path(d,[j]))

        for  pi, pj in itertools.combinations(ls_path,2):
            for ni in pi:
                if ni in pj:
                    match = ni
                    break
            ans = ''
            ans += gen_arrow(pi, 'X')
            ans += ' | '
            ans += gen_arrow(pj, 'Y')
            ans += ' | '

            if '|  |' in ans:
                ans = ans.replace('|  |','->')
                ans += 'Y'
            else:
                ans += sentence[match][0]
            ans = ans.replace("　","").replace("。","").replace("、","")

            print (ans)
            f.write(ans+'\n')

最後に

全100問の解説に戻る

記事情報

  • 投稿日：2020年5月9日
  • 最終更新日：2020年5月9日
言語処理100本ノック2020

言語処理100本ノック2020 第4章 形態素解析

はじめに

言語処理100本ノック2020

言語処理100本ノックは東北大学が公開している自然言語処理の問題集です。

とても良質なコンテンツで企業の研修や勉強会で使われています。

そんな言語処理100本ノックが2020年に改定されてました。昨今の状況を鑑みて、深層ニューラルネットワークに関する問題が追加されました。（その他にも細かい変更があります）

この記事では、言語処理100本ノック2020にPythonで取り組んでいきます。

他にも色々な解法があると思うので、一つの解答例としてご活用ください！

全100問の解説に戻る

準備

夏目漱石の小説『吾輩は猫である』の文章（neko.txt）をMeCabを使って形態素解析し，その結果をneko.txt.mecabというファイルに保存せよ．このファイルを用いて，以下の問に対応するプログラムを実装せよ．

mecabをインストールしていない方はインストールしておいて下さい。Macの場合、下記のコマンドでOKです。

1
2
brew install mecab
brew install mecab-ipadic

リンクからneko.txtをダウンロードして、下記のコマンドを実行します。

1
mecab < neko.txt > neko.txt.mecab

これで準備完了です。

30. 形態素解析結果の読み込み

形態素解析結果（neko.txt.mecab）を読み込むプログラムを実装せよ．ただし，各形態素は表層形（surface），基本形（base），品詞（pos），品詞細分類1（pos1）をキーとするマッピング型に格納し，1文を形態素（マッピング型）のリストとして表現せよ．第4章の残りの問題では，ここで作ったプログラムを活用せよ．

1
2
3
4
5
6
7
8
9
10
11
12
path = 'neko.txt.mecab'
with open(path) as f:
    text = f.read().split('\n')
result = []
for line in text:
    if line == 'EOS':
        continue
    ls = line.split('\t')
    d = {}
    tmp = ls[1].split(',')
    d = {'surface':ls[0], 'base':tmp[6], 'pos':tmp[0], 'pos1':tmp[1]}
    result.append(d)

MeCabの公式ページによると、出力フォーマットは以下のようになるとあったので、これを参考にした。

表層形\t品詞,品詞細分類1,品詞細分類2,品詞細分類3,活用型,活用形,原形,読み,発音

31. 動詞

動詞の表層形をすべて抽出せよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
path = 'neko.txt.mecab'
with open(path) as f:
    text = f.read().split('\n')
result = []
for line in text[:-1]:
    if line == 'EOS':
        continue
    ls = line.split('\t')
    d = {}
    tmp = ls[1].split(',')
    d = {'surface':ls[0], 'base':tmp[6], 'pos':tmp[0], 'pos1':tmp[1]}
    result.append(d)
[d['surface'] for d in result if d['pos'] == '動詞' ]

表層形は、baseをキーにして格納されています。

32. 動詞の原形

動詞の原形をすべて抽出せよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
path = 'neko.txt.mecab'
with open(path) as f:
    text = f.read().split('\n')
result = []
for line in text[:-1]:
    if line == 'EOS':
        continue
    ls = line.split('\t')
    d = {}
    tmp = ls[1].split(',')
    d = {'surface':ls[0], 'base':tmp[6], 'pos':tmp[0], 'pos1':tmp[1]}
    result.append(d)
[d['base'] for d in result if d['pos'] == '動詞' ]

原形は、baseをキーにして格納されています。

33. 「AのB」

2つの名詞が「の」で連結されている名詞句を抽出せよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
path = 'neko.txt.mecab'
with open(path) as f:
    text = f.read().split('\n')
result = []
for line in text[:-1]:
    if line == 'EOS':
        continue
    ls = line.split('\t')
    d = {}
    tmp = ls[1].split(',')
    d = {'surface':ls[0], 'base':tmp[6], 'pos':tmp[0], 'pos1':tmp[1]}
    result.append(d)
noun_phrase = []
for i in range(len(result)-2):
    if (result[i]['pos'] == '名詞' and result[i+1]['surface'] == 'の' and result[i+2]['pos'] == '名詞'):
        noun_phrase.append(result[i]['surface']+result[i+1]['surface']+result[i+2]['surface'])
print (noun_phrase)

ループを回して、愚直に条件を確認しています

34. 名詞の連接

名詞の連接（連続して出現する名詞）を最長一致で抽出せよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
path = 'neko.txt.mecab'
with open(path) as f:
    text = f.read().split('\n')
result = []
for line in text[:-1]:
    if line == 'EOS':
        continue
    ls = line.split('\t')
    d = {}
    tmp = ls[1].split(',')
    d = {'surface':ls[0], 'base':tmp[6], 'pos':tmp[0], 'pos1':tmp[1]}
    result.append(d)

ls_noun = []
noun = ''
for d in result:
    if d['pos']=='名詞':
            noun += d['surface']
    else:
        if noun != '':
            ls_noun.append(noun)
            noun = ''
else:
    if noun != '':
        ls_noun.append(noun)
        noun = ''
print (ls_noun)

名詞を連結して貯めておき、名詞以外が出現したらリストに追加しています。

35. 単語の出現頻度

文章中に出現する単語とその出現頻度を求め，出現頻度の高い順に並べよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import Counter
path = 'neko.txt.mecab'
with open(path) as f:
    text = f.read().split('\n')
result = []
for line in text[:-1]:
    if line == 'EOS':
        continue
    ls = line.split('\t')
    d = {}
    tmp = ls[1].split(',')
    d = {'surface':ls[0], 'base':tmp[6], 'pos':tmp[0], 'pos1':tmp[1]}
    result.append(d)


surface =  [d['surface'] for d in result]
c = Counter(surface)
print (c.most_common())

標準ライブラリのcollections.Counterを使うと良いでしょう。

36. 頻度上位10語

出現頻度が高い10語とその出現頻度をグラフ（例えば棒グラフなど）で表示せよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from collections import Counter
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'AppleGothic'
path = 'neko.txt.mecab'
with open(path) as f:
    text = f.read().split('\n')
result = []
for line in text[:-1]:
    if line == 'EOS':
        continue
    ls = line.split('\t')
    d = {}
    tmp = ls[1].split(',')
    d = {'surface':ls[0], 'base':tmp[6], 'pos':tmp[0], 'pos1':tmp[1]}
    result.append(d)


surface =  [d['surface'] for d in result]
c = Counter(surface)
target = list(zip(*c.most_common(10)))
plt.bar(*target)
plt.show()

上位を取得する際にはCounter.most_commonが便利です。

37. 「猫」と共起頻度の高い上位10語

「猫」とよく共起する（共起頻度が高い）10語とその出現頻度をグラフ（例えば棒グラフなど）で表示せよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
from collections import Counter
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'AppleGothic'
path = 'neko.txt.mecab'
with open(path) as f:
    text = f.read().split('\n')
result = []
tmp_cooccurrence = []
cooccurrence = []
inCat = False

for line in text[:-1]:
    if line == 'EOS':
        if inCat:
            cooccurrence.extend(tmp_cooccurrence)
        else:
            pass
        tmp_cooccurrence = []
        inCat = False
        continue
            
    ls = line.split('\t')
    d = {}
    tmp = ls[1].split(',')
    d = {'surface':ls[0], 'base':tmp[6], 'pos':tmp[0], 'pos1':tmp[1]}
    result.append(d)
    if ls[0]!='猫':
        tmp_cooccurrence.append(ls[0])
    else:
        inCat = True


c = Counter(cooccurrence)
target = list(zip(*c.most_common(10)))
plt.bar(*target)
plt.show()

猫が出現する文章に含まれる単語をリストに保存していけば良いです。

38. ヒストグラム

単語の出現頻度のヒストグラム（横軸に出現頻度，縦軸に出現頻度をとる単語の種類数を棒グラフで表したもの）を描け．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import Counter
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'AppleGothic'
path = 'neko.txt.mecab'
with open(path) as f:
    text = f.read().split('\n')
result = []
for line in text[:-1]:
    if line == 'EOS':
        continue
    ls = line.split('\t')
    d = {}
    tmp = ls[1].split(',')
    d = {'surface':ls[0], 'base':tmp[6], 'pos':tmp[0], 'pos1':tmp[1]}
    result.append(d)


surface =  [d['surface'] for d in result]
c = Counter(surface)
plt.hist(c.values(),  range = (1,10))
plt.show()

plt.histでヒストグラムを作成します。

39. Zipfの法則

単語の出現頻度順位を横軸，その出現頻度を縦軸として，両対数グラフをプロットせよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import Counter
import matplotlib.pyplot as plt
import numpy as np
plt.rcParams['font.family'] = 'AppleGothic'
path = 'neko.txt.mecab'
with open(path) as f:
    text = f.read().split('\n')
result = []
for line in text[:-1]:
    if line == 'EOS':
        continue
    ls = line.split('\t')
    d = {}
    tmp = ls[1].split(',')
    d = {'surface':ls[0], 'base':tmp[6], 'pos':tmp[0], 'pos1':tmp[1]}
    result.append(d)
surface =  [d['surface'] for d in result]
c = Counter(surface)
v = [kv[1] for kv in c.most_common()]
plt.scatter(np.log(range(len(v))),np.log(v))
plt.show()

データをnp.logで変換しました。軸を対数で取っても良いと思います。

最後に

全100問の解説に戻る

記事情報

  • 投稿日：2020年5月9日
  • 最終更新日：2020年5月9日
言語処理100本ノック2020

言語処理100本ノック2020 第2章 UNIXコマンド

はじめに

言語処理100本ノック2020

言語処理100本ノックは東北大学が公開している自然言語処理の問題集です。

とても良質なコンテンツで企業の研修や勉強会で使われています。

そんな言語処理100本ノックが2020年に改定されてました。昨今の状況を鑑みて、深層ニューラルネットワークに関する問題が追加されました。（その他にも細かい変更があります）

この記事では、言語処理100本ノック2020にPythonで取り組んでいきます。

他にも色々な解法があると思うので、一つの解答例としてご活用ください！

全100問の解説に戻る

10. 行数のカウント

行数をカウントせよ．確認にはwcコマンドを用いよ．

この章はPandasを使ってみようと思います。

1
2
3
import pandas as pd
df = pd.read_csv('popular-names.txt', delimiter='\t', header=None)
print (len(df))

pandasで表形式のデータを読み込む際はread_csvを用います。read_csvはdelimiterを適切に指定することで、csvファイル以外にも使えます。また、header=Noneをつけないとファイルの一行目がヘッダーとして読み込まれてしまうので注意しましょう。

1
wc popular-names.txt

11. タブをスペースに置換

タブ1文字につきスペース1文字に置換せよ．確認にはsedコマンド，trコマンド，もしくはexpandコマンドを用いよ．

1
2
3
import pandas as pd
df = pd.read_csv('popular-names.txt', delimiter='\t', header=None)
df.to_csv('space.txt', sep=' ',header=False, index=False)

保存する際はto_csvを使います。その際にsepで区切り文字を指定します。保存する際に、DataFrameのヘッダーやインデックスが出力されないように注意します。

1
sed 's/\t/ /g' popular-names.txt > replaced.txt

12. 1列目をcol1.txtに，2列目をcol2.txtに保存

各行の1列目だけを抜き出したものをcol1.txtに，2列目だけを抜き出したものをcol2.txtとしてファイルに保存せよ．確認にはcutコマンドを用いよ．

1
2
3
4
import pandas as pd
df = pd.read_csv('popular-names.txt', delimiter='\t', header=None)
df.iloc[:,0].to_csv('col1.txt', sep=' ',header=False, index=False)
df.iloc[:,1].to_csv('col2.txt', sep=' ',header=False, index=False)

ilocを使うことで行や列を指定して取得することができます。

1
2
cut -f 1  popular-names.txt > col1.txt
cut -f 2  popular-names.txt > col2.txt

13. col1.txtとcol2.txtをマージ

12で作ったcol1.txtとcol2.txtを結合し，元のファイルの1列目と2列目をタブ区切りで並べたテキストファイルを作成せよ．確認にはpasteコマンドを用いよ．

1
2
3
4
5
import pandas as pd
df1 = pd.read_csv('col1.txt', delimiter='\t', header=None)
df2 = pd.read_csv('col2.txt', delimiter='\t', header=None)
df = pd.concat([df1, df2], axis=1)
df.to_csv('col1_2.txt', sep='\t',header=False, index=False)

concatで結合ができます。横方向に連結したいのでaxis=1を指定します。

1
paste col1.txt col2.txt > col1_2.txt

14. 先頭からN行を出力

自然数Nをコマンドライン引数などの手段で受け取り，入力のうち先頭のN行だけを表示せよ．確認にはheadコマンドを用いよ．

1
2
3
import pandas as pd
df = pd.read_csv('popular-names.txt', delimiter='\t', header=None)
print (df.head(5))

headで指定した行数を確認することができます。

1
head -n 5 popular-names.txt

15. 末尾のN行を出力

自然数Nをコマンドライン引数などの手段で受け取り，入力のうち末尾のN行だけを表示せよ．確認にはtailコマンドを用いよ．

1
2
3
import pandas as pd
df = pd.read_csv('popular-names.txt', delimiter='\t', header=None)
print (df.tail(5))

Pandasで先頭から取得する場合はhead、末尾から取得する場合はtailを使います。UNIXコマンドと同様ですね。

1
tail -n 5 popular-names.txt

16. ファイルをN分割する

自然数Nをコマンドライン引数などの手段で受け取り，入力のファイルを行単位でN分割せよ．同様の処理をsplitコマンドで実現せよ．

1
2
3
4
5
6
7
N = 3
import pandas as pd
df = pd.read_csv('popular-names.txt', delimiter='\t', header=None)
step = - (-len(df) // N)
for n in range(N):
    df_split = df.iloc[n*step:(n+1)*step]
    df_split.to_csv('popular-names'+str(n)+'.txt', sep='\t',header=False, index=False)

Pythonで切り上げ除算をする際は以下のように実装すると良いです。

1
step = - (-len(df) // N)
1
split -n 3 popuar-names.txt

17. １列目の文字列の異なり

1列目の文字列の種類（異なる文字列の集合）を求めよ．確認にはcut, sort, uniqコマンドを用いよ．

1
2
3
4
5
import pandas as pd
df = pd.read_csv('popular-names.txt', delimiter='\t', header=None)
new = df[0].unique()
new.sort()
print (new)

uniqueを使うことで集合を求めることができます。

1
cut -f 1  popular-names.txt | sort | uniq

uniqはソートされていることを前提としています。そのため、前処理としてsortが必要です。

18. 各行を3コラム目の数値の降順にソート

各行を3コラム目の数値の逆順で整列せよ（注意: 各行の内容は変更せずに並び替えよ）．確認にはsortコマンドを用いよ（この問題はコマンドで実行した時の結果と合わなくてもよい）．

1
2
3
4
import pandas as pd
df = pd.read_csv('popular-names.txt', delimiter='\t', header=None)
new = df[2].sort_values(ascending=False)
print (new)

sort_valuesでソートできます。

1
cut -f 3  popular-names.txt | sort -n -r

sortはデフォルトでは文字列としてソートをするため、-nオプションで数値としてソートする必要があります。-rオプションで降順ソートになります。

19. 各行の1コラム目の文字列の出現頻度を求め，出現頻度の高い順に並べる

各行の1列目の文字列の出現頻度を求め，その高い順に並べて表示せよ．確認にはcut, uniq, sortコマンドを用いよ．

1
2
3
4
5
6
7
8
import pandas as pd
df = pd.read_csv('popular-names.txt', delimiter='\t', header=None)
vc = df[0].value_counts()
vc = pd.DataFrame(vc)
vc = vc.reset_index()
vc.columns = ['name','count']
vc = vc.sort_values(['count','name'],ascending=[False,False])
print (vc)

value_countsを用いることで出現頻度の高い順に並べ替えることができます。その後の処理はUNIXコマンドと結果を合わせるためにnameをソートしています。

1
cut -f 1  popular-names.txt | sort | uniq -c | sort -n -r

uniqは-cオプションでカウントすることができます。

最後に

全100問の解説に戻る

記事情報

  • 投稿日：2020年5月9日
  • 最終更新日：2020年5月9日
言語処理100本ノック2020

言語処理100本ノック2020 第3章 正規表現

はじめに

言語処理100本ノック2020

言語処理100本ノックは東北大学が公開している自然言語処理の問題集です。

とても良質なコンテンツで企業の研修や勉強会で使われています。

そんな言語処理100本ノックが2020年に改定されてました。昨今の状況を鑑みて、深層ニューラルネットワークに関する問題が追加されました。（その他にも細かい変更があります）

この記事では、言語処理100本ノック2020にPythonで取り組んでいきます。

他にも色々な解法があると思うので、一つの解答例としてご活用ください！

全100問の解説に戻る

20. JSONデータの読み込み

Wikipedia記事のJSONファイルを読み込み，「イギリス」に関する記事本文を表示せよ．問題21-29では，ここで抽出した記事本文に対して実行せよ．

1
2
3
4
import pandas as pd
wiki = pd.read_json('jawiki-country.json.gz', lines = True)
uk = wiki[wiki['title']=='イギリス'].text.values
print (uk)

pd.read_jsonでjsonを読み込みます。gzipのままでも問題ありません。
タイトルはtitleカラムに、本文はtextカラムに保存されています。valuesはnumpy.ndarrayに変換する処理です。

21. カテゴリ名を含む行を抽出

記事中でカテゴリ名を宣言している行を抽出せよ．

1
2
3
4
5
6
7
8
9
import pandas as pd
import re
pattern = re.compile('Category')
wiki = pd.read_json('jawiki-country.json.gz', lines = True)
uk = wiki[wiki['title']=='イギリス'].text.values
ls = uk[0].split('\n')
for line in ls:
    if re.search(pattern, line):
        print (line)

re.searchがマッチングに失敗した場合にNoneを返却することを利用しています。

22. カテゴリ名の抽出

記事のカテゴリ名を（行単位ではなく名前で）抽出せよ．

1
2
3
4
5
6
7
8
9
import pandas as pd
import re
wiki = pd.read_json('jawiki-country.json.gz', lines = True)
uk = wiki[wiki['title']=='イギリス'].text.values
ls = uk[0].split('\n')
for line in ls:
    if re.search(pattern, line):
        line = line.replace('[[','').replace('Category:','').replace(']]','').replace('|*','').replace('|元','')
        print (line)

正規表現で全てを記述せず、後処理としてreplaceで削除を行なっています。

23. セクション構造

記事中に含まれるセクション名とそのレベル（例えば”== セクション名 ==”なら1）を表示せよ．

1
2
3
4
5
6
7
8
9
10
import pandas as pd
import re
pattern = re.compile('^=+.*=+$') # 1回以上の=で始まり、1回以上の=で終わる文字列
wiki = pd.read_json('jawiki-country.json.gz', lines = True)
uk = wiki[wiki['title']=='イギリス'].text.values
ls = uk[0].split('\n')
for line in ls:
    if re.search(pattern, line):
        level = line.count('=') // 2 - 1
        print(line.replace('=',''), level )

同じパターンでなんどもマッチングをとる場合、re.compileで事前にコンパイルすると効率が良いです。

24. ファイル参照の抽出

記事から参照されているメディアファイルをすべて抜き出せ．

1
2
3
4
5
6
7
8
9
10
import pandas as pd
import re
pattern = re.compile('File|ファイル:(.+?)\|')
wiki = pd.read_json('jawiki-country.json.gz', lines = True)
uk = wiki[wiki['title']=='イギリス'].text.values
ls = uk[0].split('\n')
for line in ls:
    r = re.findall(pattern, line)
    if r:
        print (r[0])

パターンマッチと同時に、丸括弧()で指定した部分文字列を抽出することができます。

25. テンプレートの抽出

記事中に含まれる「基礎情報」テンプレートのフィールド名と値を抽出し，辞書オブジェクトとして格納せよ．

1
2
3
4
5
6
7
8
9
10
11
12
import pandas as pd
import re
pattern = re.compile('\|(.+?)\s=\s*(.+)')
wiki = pd.read_json('jawiki-country.json.gz', lines = True)
uk = wiki[wiki['title']=='イギリス'].text.values
ls = uk[0].split('\n')
d = {}
for line in ls:
    r = re.search(pattern, line)
    if r:
        d[r[1]]=r[2]
print (d)

|の後にkey=valueのようなフォーマットで記録されている。=の後にスペースが入っている場合とそうでない場合があるので注意。

1
2
\s 空白文字
* 直前のパターンの0回以上の繰り返し

26. 強調マークアップの除去

25の処理時に，テンプレートの値からMediaWikiの強調マークアップ（弱い強調，強調，強い強調のすべて）を除去してテキストに変換せよ（参考: マークアップ早見表）．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

import pandas as pd
import re
pattern = re.compile('\|(.+?)\s=\s*(.+)')
p_emp = re.compile('\'{2,}(.+?)\'{2,}')
wiki = pd.read_json('jawiki-country.json.gz', lines = True)
uk = wiki[wiki['title']=='イギリス'].text.values
ls = uk[0].split('\n')
d = {}
for line in ls:
    r = re.search(pattern, line)
    if r:
        d[r[1]]=r[2]
    r = re.sub(p_emp,'\\1', line)
    print (r)
print (d)

27. 内部リンクの除去

26の処理に加えて，テンプレートの値からMediaWikiの内部リンクマークアップを除去し，テキストに変換せよ（参考: マークアップ早見表）．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import pandas as pd
import re
pattern = re.compile('\|(.+?)\s=\s*(.+)')
p_emp = re.compile('\'{2,}(.+?)\'{2,}')
p_link = re.compile('\[\[(.+?)\]\]')
wiki = pd.read_json('jawiki-country.json.gz', lines = True)
uk = wiki[wiki['title']=='イギリス'].text.values
lines = uk[0]
lines = re.sub(p_emp,'\\1', lines)
lines = re.sub(p_link,'\\1', lines)
ls = lines.split('\n')
d = {}
for line in ls:
    r = re.search(pattern, line)
    if r:
        d[r[1]]=r[2]
print (d)

\[\[(.+?)\]\]で[[]]で括られたテキストを抽出しています。

28. MediaWikiマークアップの除去

27の処理に加えて，テンプレートの値からMediaWikiマークアップを可能な限り除去し，国の基本情報を整形せよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import pandas as pd
import re
pattern = re.compile('\|(.+?)\s=\s*(.+)')
p_emp = re.compile('\'{2,}(.+?)\'{2,}')
p_link = re.compile('\[\[(.+?)\]\]')
p_refbr = re.compile('<[br|ref][^>]*?>.+?<\/[br|ref][^>]*?>')
wiki = pd.read_json('jawiki-country.json.gz', lines = True)
uk = wiki[wiki['title']=='イギリス'].text.values
lines = uk[0]
lines = re.sub(p_emp,'\\1', lines)
lines = re.sub(p_link,'\\1', lines)
lines = re.sub(p_refbr,'', lines)
ls = lines.split('\n')
d = {}
for line in ls:
    r = re.search(pattern, line)
    if r:
        d[r[1]]=r[2]
print (d)

br|refで<br>タグや<ref>を除去しています。 他にもやるべきことはまだまだありそうです。

29. 国旗画像のURLを取得する

テンプレートの内容を利用し，国旗画像のURLを取得せよ．（ヒント: MediaWiki APIのimageinfoを呼び出して，ファイル参照をURLに変換すればよい

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import pandas as pd
import re
import requests
pattern = re.compile('\|(.+?)\s=\s*(.+)')
wiki = pd.read_json('jawiki-country.json.gz', lines = True)
uk = wiki[wiki['title']=='イギリス'].text.values
ls = uk[0].split('\n')
d = {}
for line in ls:
    r = re.search(pattern, line)
    if r:
        d[r[1]]=r[2]
        
S = requests.Session()
URL = "https://commons.wikimedia.org/w/api.php"
PARAMS = {
    "action": "query",
    "format": "json",
    "titles": "File:" + d['国旗画像'],
    "prop": "imageinfo",
    "iiprop":"url"
}
R = S.get(url=URL, params=PARAMS)
DATA = R.json()
PAGES = DATA['query']['pages']
for k, v in PAGES.items():
    print (v['imageinfo'][0]['url'])

公式のサンプルコードを参考にしました。

最後に

全100問の解説に戻る

記事情報

  • 投稿日：2020年5月9日
  • 最終更新日：2020年5月9日
言語処理100本ノック2020

言語処理100本ノック2020 第1章 準備運動

はじめに

言語処理100本ノック2020

言語処理100本ノックは東北大学が公開している自然言語処理の問題集です。

とても良質なコンテンツで企業の研修や勉強会で使われています。

そんな言語処理100本ノックが2020年に改定されてました。昨今の状況を鑑みて、深層ニューラルネットワークに関する問題が追加されました。（その他にも細かい変更があります）

この記事では、言語処理100本ノック2020にPythonで取り組んでいきます。

他にも色々な解法があると思うので、一つの解答例としてご活用ください！

全100問の解説に戻る

00. 文字列の逆順

文字列”stressed”の文字を逆に（末尾から先頭に向かって）並べた文字列を得よ．

1
2
s = 'stressed'
print (s[::-1])

pythonの文字列はスライスを利用することで逆順に取得することができます。

01. 「パタトクカシーー」

「パタトクカシーー」という文字列の1,3,5,7文字目を取り出して連結した文字列を得よ．

1
2
s = 'パタトクカシーー'
print (s[::2])

ストライド（ステップ）を利用するのが良いでしょう。

02. 「パトカー」＋「タクシー」＝「パタトクカシーー」

「パトカー」＋「タクシー」の文字を先頭から交互に連結して文字列「パタトクカシーー」を得よ．

1
2
3
s1 = 'パトカー'
s2 = 'タクシー'
print (''.join([a+b for a,b in zip(s1,s2)]))

zipを使って二つの文字列に対してループを回すのが良いでしょう。
最後の''.join()は文字列のリストを結合し文字列に変換する処理です。

03. 円周率

“Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics.”という文を単語に分解し，各単語の（アルファベットの）文字数を先頭から出現順に並べたリストを作成せよ．

1
2
3
s = "Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics."
s = s.replace(',','').replace('.','')
[len(w) for w in s.split()]

まず、単語の文字数を数えるのに邪魔なので、,や.を削除します。その後split()を利用して文章を半角スペースを区切り文字として分割します。

04. 元素記号

“Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can.”という文を単語に分解し，1, 5, 6, 7, 8, 9, 15, 16, 19番目の単語は先頭の1文字，それ以外の単語は先頭に2文字を取り出し，取り出した文字列から単語の位置（先頭から何番目の単語か）への連想配列（辞書型もしくはマップ型）を作成せよ．

1
2
3
4
5
6
7
8
9
10
11
s = "Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can."
s = s.replace('.','')
idx = [1, 5, 6, 7, 8, 9, 15, 16, 19]
mp = {}
for i,w in enumerate(s.split()):
    if (i+1) in idx:
        v = w[:1]
    else:
        v = w[:2]
    mp[v] = i+1
print (mp)

前回の問題の知識に加えて、辞書の扱いが求められます。
pythonでは辞書は{}のようにして作成します。

05. n-gram

与えられたシーケンス（文字列やリストなど）からn-gramを作る関数を作成せよ．この関数を用い，”I am an NLPer”という文から単語bi-gram，文字bi-gramを得よ．

1
2
3
4
5
6
7
8
def ngram(S, n):
    r = []
    for i in range(len(S) - n + 1):
        r.append(S[i:i+n])
    return r
s = 'I am an NLPer'
print (ngram(s.split(),2))
print (ngram(s,2))

スライスを利用することで、n-gramを表現できます。スライスは文字列にもリストにも利用できるため、単語bi-gramにも文字bi-gramにも使えます。

06. 集合

“paraparaparadise”と”paragraph”に含まれる文字bi-gramの集合を，それぞれ, XとYとして求め，XとYの和集合，積集合，差集合を求めよ．さらに，’se’というbi-gramがXおよびYに含まれるかどうかを調べよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def ngram(S, n):
    r = []
    for i in range(len(S) - n + 1):
        r.append(S[i:i+n])
    return r
s1 = 'paraparaparadise'
s2 = 'paragraph'
st1 = set(ngram(s1, 2))
st2 = set(ngram(s2, 2))
print(st1 | st2)
print(st1 & st2)
print(st1 - st2)
print('se' in st1)
print('se' in st2)

bi-gramを作るために先ほどのn-gramを使いまわします。pythonの集合演算について理解しておけば問題ないでしょう。

07. テンプレートによる文生成

引数x, y, zを受け取り「x時のyはz」という文字列を返す関数を実装せよ．さらに，x=12, y=”気温”, z=22.4として，実行結果を確認せよ．

1
2
3
4
5
6
def temperature(x,y,z):
    return str(x)+'時の'+str(y)+'は'+str(z)
x = 12
y = '気温'
z = 22.4
print (temperature(x,y,z))

入力を結合するだけです。strを利用して文字列に変換するのを忘れずに。

08. 暗号文

与えられた文字列の各文字を，以下の仕様で変換する関数cipherを実装せよ．

- 英小文字ならば(219 - 文字コード)の文字に置換

- その他の文字はそのまま出力

この関数を用い，英語のメッセージを暗号化・復号化せよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
def cipher(S):
    new = []
    for s in S:
        if 97 <= ord(s) <= 122:
            s = chr(219 - ord(s))
        new.append(s)
    return ''.join(new)
        
s = 'I am an NLPer'
new = cipher(s)
print (new)

print (cipher(new))

ordはpythonの組み込み関数で、Unicodeコードポイントを表す整数を返します。chrはその逆で、整数を受け取り文字を返します。

97がaを、122がzを表します。

つまり、文字をordで整数に変換し、219から引いてchrに戻すということは以下のような変換を行なっていることになるのです。

この変換を再び行うと元の文字に戻ることがわかると思います。

1
2
3
4
a -> z
b -> y
...
z -> a

09. Typoglycemia

スペースで区切られた単語列に対して，各単語の先頭と末尾の文字は残し，それ以外の文字の順序をランダムに並び替えるプログラムを作成せよ．ただし，長さが４以下の単語は並び替えないこととする．適当な英語の文（例えば”I couldn’t believe that I could actually understand what I was reading : the phenomenal power of the human mind .”）を与え，その実行結果を確認せよ．

1
2
3
4
5
6
7
8
9
10
11
12
13
import random
s = 'I couldn’t believe that I could actually understand what I was reading : the phenomenal power of the human mind .'
ans = []
text = s.split()
for word in text:
    if (len(word)>4):
        mid = list(word[1:-1])
        random.shuffle(mid)
        word = word[0] + ''.join(mid) + word[-1]
        ans.append(word)
    else:
        ans.append(word)
print (' '.join(ans))

ランダムに並び変えるために、標準ライブラリrandomを使うと良いでしょう。

最後に

全100問の解説に戻る

記事情報

  • 投稿日：2020年5月9日
  • 最終更新日：2020年5月9日
競プロ初中級者100問

JOI2013本選1 電飾

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2013ho/tasks/joi2013ho1
https://www.ioi-jp.org/joi/2012/2013-ho/index.html

ポイント

  • 逐次的に交互列を探す。これはO(N)で求まる。
  • 三つの交互列が並んでいる時、中央の交互列を反転させることで全体として一つの交互列となる。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
N = int(input())
A = map(int, input().split())

old = ''
cnt = 0
left = []
for a in A:
    if a==old:
        left.append(cnt)
        cnt = 1
    else:
        cnt += 1
    old = a
left.append(cnt)
left+=[0,0] # 要素数が3以上になることを保証

ans = 0
for i in range(len(left)-2):
    ans = max(ans, sum(left[i:i+3]))
print (ans)

記事情報

  • 投稿日：2020年5月9日
  • 最終更新日：2020年5月9日
競プロ初中級者100問

Square869120Countest#6B - AtCoder Market

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_b

この問題は全探索を用いて部分点を得ることができます。満点解法には数学的思考が必要です。

方針

  • Aに対して最適な入口xは、Bに対して最適な出口yをそれぞれ独立に考えることができます。そのため、ここではAとxについて考察します。
  • 絶対値|x-A_i|の和が最小値となるようなxは、以下のような値です。
    • Aの要素数が奇数の場合・・・xをAの中央値とします。
    • Aの要素数が偶数の場合、中央の2値を(A_m,A_m+1)として、区間[A_m,A_m+1]のうちの任意の値とします。

実装上は結局、A[N//2]とすれば十分です。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
N = int(input())
A = []
B = []
for n in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
A.sort()
B.sort()
am = A[N//2]
bm = B[N//2]

ans = 0
for a,b in zip(A,B):
    ans += abs(a-b) # AからB
    ans += abs(a-am) # 入口からA
    ans += abs(b-bm) # 出口からB
print (ans)

記事情報

  • 投稿日：2020年5月8日
  • 最終更新日：2020年5月8日
競プロ初中級者100問

ITP1 7B 組み合わせの数

この記事で使うアルゴリズム

全探索

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_7_B&lang=ja

この問題は全探索を用いて解くことができます。

ポイント

Pythonで組み合わせを列挙する場合は、combinationsを用いると良いです。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from itertools import combinations
nx = []
while(1):
    n, x = map(int,input().split())
    if n==0 and x==0:
        break
    nx.append((n,x))

for n,x in nx:
    cnt = 0
    for c in list(combinations(range(1,n+1),3)):
        if sum(c)==x:
            cnt += 1
    print (cnt)

記事情報

  • 投稿日：2020年5月8日
  • 最終更新日：2020年5月10日
競プロ初中級者100問

JOI2008本戦A 碁石ならべ

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_a
https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf#page=2

方針

愚直にルールにしたがってシミュレーションを行うと、計算量はO(n^2)となり間に合いません。

少し考察すると色がどこで変わったかだけを記録すると効率が良いとわかります。

これはスタックで実装することができ、計算量はO(n)です。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
N = int(input())
C = []
for n in range(N):
    c = int(input())
    C.append(c)

stack = []
old = None
for n in range(N):
    c = C[n]
    if (n%2==1): # iが偶数の場合（nが奇数）
        if old != c: # 色が異なれば
            stack.pop() # 反転させる（最後の反対色の記録を取り除く）
            if len(stack)==0: # スタックを空にしない
                stack.append(0)
    else:
        if old != c: # 違う色が出た時
            stack.append(n) # 色の始まりを記録する
    old = c
if old == 0: # スタック上の記録では、白黒は交互に格納されているので最後が白なら
    stack.append(n+1) # n+1を格納しておく。これは、後ほどストライド2で差分を計算するため
if len(stack)%2 == 1:
    stack.insert(0,0) # ストライド2で差分を計算するため、要素数を偶数にする
print (sum(stack[1::2]) - sum(stack[::2]))

記事情報

  • 投稿日：2020年5月8日
  • 最終更新日：2020年5月8日
競プロ初中級者100問

分野別 初中級者が解くべき過去問精選100問

このページは何？

このブログでは、レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】で2-3節にまとめられている100問をPythonで解いています。

AtCoder で水色コーダー、つまりレーティング 1200 を少ない問題数で達成するために、茶色コーダー・緑コーダーにとって適切な教育的良問を 100 問集めました。

分野ごとに問題が分けられています。また、アルゴリズムの確認問題から応用問題まで幅広い層の問題がありますので、是非解いてみることをおすすめします。難しい問題もあるので、水色コーダーを目指す人は 100 問中 70 問正解を目安に頑張ってください。

100 問全部解けたら、水色コーダーどころか青色コーダーくらいの実力が付くと思います。そのため、既に水色コーダー以上であっても、100 問全部を解いていない場合は、解く価値が大きいと思います。

このページは、各解説記事へのリンクをまとめています。

リンク

全探索：全列挙

  1. ITP1 7B 組み合わせの数

  2. ABC106B 105

  3. ABC122B ATCoder

  4. パ研杯2019 3C カラオケ

全探索：工夫して通り数を減らす全列挙

  1. ABC095C Half and Half

  2. 三井住友信託銀行プログラミングコンテスト2019D Lucky PIN

  3. JOI2007本戦C 最古の遺跡

  4. Square869120Countest#6B - AtCoder Market

  5. JOI2008予選4 星座探し

全探索：ビット全探索

  1. ALDS1 5A 総当たり

  2. ABC128C Switches

  3. ABC002D 派閥

  4. JOI2008予選5 おせんべい

  5. Square869120Contest#4B Buildings are Colorful!

全探索：順列全探索

  1. ABC145C Average Length

  2. ABC150C Count Order

  3. ALDS1 13A 8クイーン問題

二分探索

  1. ALDS1 4B 二分探索

  2. JOI2009本選2 ピザ

  3. ABC077C Snuke Festival

  4. ABC023D 射撃王

  5. ARC054B ムーアの法則

  6. JOI2008本選C ダーツ

深さ優先探索

  1. ALDS1 11B 深さ優先探索

  2. AOJ1160 島はいくつある？

  3. ABC138D Ki

  4. JOI2009予選D 薄氷渡り

幅優先探索

  1. ALDS1 11C 幅優先探索

  2. ABC007C 幅優先探索

  3. JOI2011予選E チーズ

  4. JOI2012予選E イルミネーション

  5. AOJ1166 迷図と命ず

  6. ABC088D Grid Repainting

動的計画法：ナップザック DP

  1. ALDS1 10A フィボナッチ数列

  2. DPL1B 0-1ナップザック問題

  3. DPL1C ナップザック問題

  4. DPL1A コイン問題

  5. ALDS1 10C 最長共通部分列

ナップサックDPまたはその亜種

  1. JOI2011予選D 1年生

  2. JOI2012予選D パスタ

  3. JOI2013予選D 暑い日々

  4. JOI2015予選D シルクロード

  5. パ研杯2019 3D パ研軍旗

  6. AOJ1167 ポロック予想

  7. AOJ2199 Differential Pulse Code Modulation

動的計画法：区間 DP

  1. ALDS1 10B 連鎖行列積

  2. JOI2015本選B ケーキの切り分け２

  3. AOJ1611 ダルマ落とし

動的計画法：bit DP

  1. DPL2A 巡回セールスマン問題

動的計画法：その他

  1. DPL1D 最長増加部分列

  2. ABC006D トランプ挿入ソート

  3. ABC134E Sequence Decomposing

最短経路問題：ダイクストラ法

  1. GRL1A 単一始点最短経路

  2. JOI2008予選F 船旅

  3. JOI2016予選E ゾンビ島

  4. JOI2014予選E タクシー

最短経路問題：ワーシャルフロイド法

  1. GRL1C 全点対間最短経路

  2. ABC012D バスと避けられない運命

  3. ABC079D Wall

  4. ABC074D Restoring Road Network

最小全域木問題

  1. GRL2A 最小全域木

  2. ABC065D Built?

高速な素数判定法

  1. NTL1A 素因数分解

  2. ABC084D 2017-like Number

高速なべき乗計算

  1. NTL1B べき乗

  2. Square869120Countest#1E - 散歩 (E869120 and Path Length)

逆元を使う問題

  1. ABC034C 経路

  2. ABC145D Knight

  3. ABC021D 多重ループ

累積和

  1. 全国統一プログラミング王決定戦本戦A Abundant Resources

  2. JOI2010本選A 旅人

  3. JOI2011本戦A 惑星探索

  4. ABC106D AtCoder Express 2

  1. GigaCode2019D 家の建設

いもす法

  1. ABC014C AtColor

  2. AOJ2013 大崎

  3. JOI2015本選A 鉄道旅行

Union-Find

  1. DSL1A 互いに素な集合

  2. ABC075C Bridge

  3. ABC120D Decayed Bridge

その他のテクニック

圧縮

  1. JOI2008本戦A 碁石ならべ

  2. JOI2013本選1 電飾

単純な幾何計算

  1. Square869120Contest#5B - Emblem

  2. ABC144D Water Bottle

実装問題

  1. AOJ1193 連鎖消滅パズル

数学的な問題

  1. ABC149B Greedy Takahashi

  2. ABC139D ModSum

  3. ABC150D Semi Common Multiple

  4. 三井住友信託銀行プログラミングコンテスト2019E Colorful Hats 2

  5. DDCC2020予選D Digit Sum Replace

  6. Tenka1 Programmer Beginner Contest 2018D Crossing

オススメの書籍

この三冊を買っておけば間違い無いです。

終わりに

他にも様々なテーマでまとめ記事を書いているのでよろしければご覧ください。

まとめ記事の一覧

MENTAというサービスでプログラミング学習のサポートをしています。競技プログラミングについてもサポートできるので、ご興味がある方はぜひMENTAのDMでご連絡いただければと思います。

記事情報

  • 投稿日：2020年5月8日
  • 最終更新日：2022年1月8日