More than 3 years have passed since last update.

言語処理100本ノック2020年版を解いてみた【第1章：準備運動 05〜09】

Last updated at 2020-07-23Posted at 2020-04-22

東北大乾・岡崎研（現乾・鈴木研）で作成された、新人研修の一つであるプログラミング基礎勉強会の教材『言語処理100本ノック 2020年版』をPython（3.7）で解いた記事の第2弾です。

独学でPythonを勉強してきたので、間違いやもっと効率の良い方法があるかもしれません。
改善点を見つけた際はご指摘いただけると幸いです。

ソースコードはGitHubにも公開しています。

第1章: 準備運動

テキストや文字列を扱う題材に取り組みながら，プログラミング言語のやや高度なトピックを復習します．

05.n-gram

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

n-gramとは

任意の文書や文字列などにおける任意のn文字が連続した文字列のことである。

とあり、bi-gramは2文字連続した文字列を表します。

参考：n-gramとは何？ Weblio辞書

05.py

def n_gram(target, n):
    return [target[index: index + n] for index in range(len(target) - n + 1)]


words = "I am an NLPer"
print(n_gram(words.split(), 2))
# >> [['I', 'am'], ['am', 'an'], ['an', 'NLPer']]
print(n_gram(words, 2))
# >> ['I ', ' a', 'am', 'm ', ' a', 'an', 'n ', ' N', 'NL', 'LP', 'Pe', 'er']

今回もスライスを活用します。
n_gram関数内では、与えられたリスト・文字列に対してインデックスを1つずつずらしながら指定数の要素を抽出したリストを返します。

単語bi-gramは、入力文字列をスペースでsplitメソッドを利用して分割して引数として渡します。
文字bi-gramは、そのまま与えられたものを文字列としてスライスします。

06.集合

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

06.py

def n_gram(target, n):
    return [target[index: index + n] for index in range(len(target) - n + 1)]


word1 = "paraparaparadise"
word2 = "paragraph"
x = set(n_gram(word1, 2))
y = set(n_gram(word2, 2))
# x = {'is', 'ra', 'ad', 'se', 'ar', 'ap', 'pa', 'di'}
# y = {'ag', 'gr', 'ra', 'ar', 'ap', 'pa', 'ph'}

# 和集合
print(x | y)
# >> {'ph', 'ap', 'is', 'ad', 'pa', 'se', 'di', 'ar', 'gr', 'ag', 'ra'}

# 積集合
print(x & y)
# >> {'ar', 'pa', 'ap', 'ra'}

# 差集合
print(x - y)
# >> {'di', 'is', 'se', 'ad'}

print(y - x)
# >> {'ph', 'ag', 'gr'}

print('se' in x)
# >> True

print('se' in y)
# >> False

文字bi-gramを作成する部分は先程と同様なので、説明は割愛します。
PythonではSet型を使うことで集合が扱えます。
n_gram関数から返ってきたbi-gramのリストをSet型に変換して、それぞれの集合を求めます。

文字列が含まれるかはinを用いると判定することができます。

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

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

07.py

def something_at_that_time(hour, something, predicate):
    return "{}時の{}は{}".format(str(hour), something, str(predicate))


x = 12
y = "気温"
z = 22.4
print(something_at_that_time(x, y, z))

テンプレートによる文生成には、formatメソッドが便利です。
文字列内に{}を入れて、入れた{}の順にformatメソッドの引数で文字列を指定すると、{}を文字列に変換できます。

{h1}のように{}内に変数を入れて、"{h1}".format(h1=変数A)とキーワード引数で指定も可能です。

変換する文字列のフォーマット（小数点何桁や、ゼロ詰めなど）を定義することもできます。

08. 暗号文

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

英小文字ならば(219 - 文字コード)の文字に置換
その他の文字はそのまま出力

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

08.py

def cipher(string):
    encyption = ""
    for i in list(string):
        if i.islower():
            encyption += chr((219 - ord(i)))
        else:
            encyption += i
    return encyption


test = "Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can."
encyption = cipher(test)
print(encyption)
# >> Hr Hv Lrvw Bvxzfhv Blilm Clfow Nlg Ocrwrav Foflirmv. Nvd Nzgrlmh Mrtsg Aohl Srtm Pvzxv Svxfirgb Cozfhv. Aigsfi Krmt Czm.
normal = cipher(encyption)
print(normal)
# >> Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can.

文字列を引数に取るcipher関数で暗号化・復号化を行います。
設問にあるように、英小文字の場合はその文字をord関数でUnicodeコードポイントを取得し、219から引くことで暗号化後のUnicodeコードポイントを取得、chr関数でUnicodeコードポイントから文字に変換しています。

復号化も同じく219から引くことでできるところが、この問題のミソですね。

09. Typoglycemia

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

先頭と末尾の文字だけあっていれば、あいだの文字の順番がバラバラでも人間は読めてしまうという特性の再現です。

09.py

import random

input_line = "I couldn't believe that I could actually understand what I was reading : the phenomenal power of the human mind ."
words_list = input_line.split()
ans = []
for i in words_list:
    if len(i) <= 4:
        ans.append(i)
        continue
    char = list(i)
    middle_char = char[1:len(i) - 1]
    ans.append(char[0] + "".join(random.sample(middle_char, len(middle_char))) + char[-1])
print(" ".join(ans))
# >> I cod'nult bvieele that I culod auclatly unserdatnd what I was rdienag : the panmhoeenl poewr of the hmaun mind .

※ randomモジュールの関数random()を使っているので、実行ごとに答えが異なります。

この問題は、まず単語ごとにリスト化し、1単語ずつ処理を行います。
もし、単語が4文字以下であれば、解答単語リストにそのまま追加します。

ifの処理に入らなかった場合、単語を更に文字列にリスト化して、間の文字をスライスで抽出します。
解答単語リストには、最初の文字と最後の文字は固定で、間の部分は抽出した文字のリストからすべての要素をランダムに重複なしで並べ替えてリスト化し、joinメソッドで結合して文字列化し、最初と最後の文字と連結したものを追加します。

最終的に、解答単語リストを引数に空白に対してjoinメソッドを実行して答えとなります。

まとめ

この記事では言語処理100本ノック2020年版第1章：準備運動の問題番号05〜09までを解いてみました。

set型は意外とよく使いますし、文字と文字コードの変換は言語処理ならではという感じで、今回もとても勉強になりました。

まだまだ未熟なので、よりよい解答がありましたらぜひご指摘ください！！
よろしくお願いいたします。

つづき

前回まで

言語処理100本ノック2020年版を解いてみた【第1章：準備運動 00〜04】

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up