Nimで言語処理100本ノック(第1章: 準備運動)

はじめに

この記事はNim Advent Calendar 2022の11日目の記事です。

10日目の記事はmeganeoさんのなにか書きます、
13日目の記事はnimble-pteromysさんのNimで言語処理100本ノック(第2章: UNIXコマンド)になります。ありがとうございます！

概要

最近、気になっている言語Nim。実践的な問題に取り組んでみようと思い探していると、言語処理100本ノックというものを見つけました。まだ不慣れですし、後半になると私には実践的すぎて難しいかもしれませんが、とりあえずやれるところまでやっていこうと思います。(この記事は第1章: 準備運動の内容に取り組みました。)

環境

Nim version: 1.6.10

00. 文字列の逆順

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

逆順にするときに、algorithmモジュールのreversed関数を使うと、出力がseq型のためバラバラになってしまいました。

import std/algorithm

let str = "stressed"
echo str.reversed # @['d', 'e', 's', 's', 'e', 'r', 't', 's']

くっつけるには、strutilsモジュールのjoin関数を使いましょう（Wandbox）。

import std/[algorithm, strutils]

let str = "stressed"
echo str.reversed.join # desserts

調べたところ、そもそもバラバラにせずに逆順にするにはunicodeモジュールのreversed関数を使えば良いようです（Wandbox）。これであれば2バイト以上の文字でも安心して反転できるので良いですね。

import std/unicode

let str = "stressed"
echo str.reversed # desserts

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

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

1バイト文字ではないので直感的に1文字目を取り出そうとすると正確に取り出せません．

echo "パタトクカシーー"[0]
echo "パタトクカシーー"[0..2] # 3バイト分スライス
# パ

unicodeモジュールにはRune型と呼ばれるユニコードでの符号点(一意の通し番号)を1つ分保持する型があり、同モジュールのtoRunes関数は引数として与えられた文字列をRune型が含まれたseq型に変換します。

import std/unicode

let runes = toRunes("パタトクカシーー")
echo runes
echo runes[0] # パ

ここまでいけば、後は1,3,5,7文字目を取り出せば完成です。言われた通り取り出して結合するのもいいですが、せっかくならスライスして取り出してみたいところです。

import std/unicode
import strides

let runes = toRunes("パタトクカシーー")
echo runes[0..runes.len-1 @: 2] # パトカー
echo runes[runes.len @: 2]      # パトカー  L@:n なら0始点のスライスの全長をLで表す

stridesモジュールを使うとHSliceにstride(step)の要素を追加したStridedSliceを使ってPythonのスライスのように振る舞わせることができます。

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

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

import std/[unicode, sequtils, strutils]

let str1 = "パトカー".toRunes
let str2 = "タクシー".toRunes
echo zip(str1, str2).mapIt($it[0] & $it[1]).join
# パタトクカシーー

sequtilsモジュールのzip関数がタプルのseqを返すので、それにit[0]等でアクセスしてstring型に変えてから結合します（Wandbox）。

03. 円周率

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

import std/[strutils, sequtils]

let str = 
    "Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics."
    .multiReplace((".", ""), (",", "")) # ,と.を除去
let splits = str.split(' ')

echo splits.mapIt(it.len) # 文字列の一覧に変換
# @[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]

multiReplace関数で置換を一度に複数回行います（Wandbox）。置換後の文字列が元の入力文字列よりも長くない場合は、必要なメモリ割当は一度だけになるようです。

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文字を取り出し，取り出した文字列から単語の位置（先頭から何番目の単語か）への連想配列（辞書型もしくはマップ型）を作成せよ．

import std/[strutils, sugar, tables]

let splits = 
    "Hi He Lied Because Boron Could Not Oxidize Fluorine. New Nations Might Also Sign Peace Security Clause. Arthur King Can."
    .split(' ') # ,と.は除去する必要がない
let oneChar = [1, 5, 6, 7, 8, 9, 15, 16, 19] # 1文字だけ取り出す単語位置配列

var elementTable = initOrderedTable[string, int]() # 入れた順で連想配列を作る
for i, d in splits.pairs:
    if i+1 in oneChar: 
        elementTable[d.substr(0, 0)] = i+1 # 文字列から単語の位置への連想配列
    else: 
        elementTable[d.substr(0, 1)] = i+1
echo elementTable
# {"H": 1, "He": 2, "Li": 3, "Be": 4, "B": 5, "C": 6, "N": 7, "O": 8, "F": 9, "Ne": 10, "Na": 11, "Mi": 12, "Al": 13, "Si": 14, "P": 15, "S": 16, "Cl": 17, "Ar": 18, "K": 19, "Ca": 20}

tablesモジュールには通常のハッシュテーブルであるTable、挿入順を記憶するOrderedTable、コンテナ（文字列、シーケンス、配列など）のアイテム数をカウントするCountTableが定義されています。今回は挿入順を記憶する必要はありませんが、一応OrderedTableを使用しました（Wandbox）。

せっかくなのでsugarモジュールのcollect関数を使用したかったのですが、うまく行きませんでした（環境はnim 1.6.10）。

echo collect(initTable[string, int]()):
    for i, d in splits.pairs:
        if i+1 in oneChar: {d.substr(0, 0): i+1}
        else: {d.substr(0, 1): i+1}

# 上記コードを同様なエラーになる程度に簡単化
let testTable = collect:
  for d in splits: 
    if true: {d: d} else: {d: d}
echo testTable

色々試したところif文が絡むとおかしくなるようです。これはバグなのか、そもそもcollectのサポート的にif文をサポートしないのか、分かる方がいれば教えてください。

05. n-gram

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

そもそも、n-gramとはどういったものなのでしょうか。

任意の文字列や文書を連続したn個の文字で分割するテキスト分割方法．特に，nが1の場合をユニグラム（uni-gram），2の場合をバイグラム（bi-gram），3の場合をトライグラム（tri-gram）と呼ぶ．最初の分割後は1文字ずつ移動して順次分割を行う．
コトバンク（図書館情報学用語辞典 第5版「Nグラム」の解説）

今回の例"I am an NLPer"を文字N-gramと単語N-gramにしてみましょう（参考: N-gramの作り方）。

文字N-gram

uni-gram: 連続した1個の文字で分割

"I", " ", "a", "m", " ", "a", "n", " ", "N", "L", "P", "e", "r"

bi-gram: 基準が1文字ずつ移動しながら連続した2個の文字で分割

"I ", " a", "am", "m ", " a", "an", "n ", " N", "NL", "LP", "Pe", "er"

tri-gram: 基準が1文字ずつ移動しながら連続した3個の文字で分割

"I a", " am", "am ", "m a", " an", "an ", "n N", " NL", "NLP", "LPe", "Per"

単語N-gram

uni-gram: 連続した1個の単語で分割

["I"], ["am"], ["an"], ["NLPer"]

bi-gram: 基準が1単語ずつ移動しながら連続した2個の単語で分割

["I", "am"], ["am", "an"], ["an", "NLPer"]

tri-gram: 基準が1単語ずつ移動しながら連続した3個の単語で分割

["I", "am", "an"], ["am", "an", "NLPer"]

実装としては、先に1単語ごとのシーケンス、1文字ごとのシーケンス(そのままの文字列でいい)に分けておきます。そして、N=1の時はその要素の一つずつ、N=2の時は二つずつ、N=3の時は三つずつ取り出す関数を作成すればいいでしょう（Wandbox）。

import std/[sugar, strutils]

proc n_gram(target: string | seq[string], n: Positive): seq[string] | seq[seq[string]] = 
  # 基準を1文字(単語)ずつずらしながらn文字分抜き出す
  return collect(for i in 0..target.len-n: target[i ..< i+n])

let str = "I am an NLPer"
echo n_gram(str.split(), 2)  # 単語bi-gram
# @[@["I", "am"], @["am", "an"], @["an", "NLPer"]]
echo n_gram(str, 2)          # 文字bi-gram
# @["I ", " a", "am", "m ", " a", "an", "n ", " N", "NL", "LP", "Pe", "er"]

06. 集合

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

import std/[sugar, sets]

proc n_gram(target: string | seq[string], n: Positive): seq[string] | seq[seq[string]] = 
  return collect(for i in 0..target.len-n: target[i ..< i+n])

let X = n_gram("paraparaparadise", 2).toHashSet    # 文字bi-gramの集合
let Y = n_gram("paragraph"       , 2).toHashSet
dump X          # = {"se", "ap", "di", "is", "pa", "ad", "ar", "ra"}
dump Y          # = {"gr", "ph", "pa", "ap", "ag", "ar", "ra"}
dump X + Y      # = {"se", "gr", "ph", "ap", "ag", "di", "is", "pa", "ad", "ar", "ra"}  # 和集合
dump X * Y      # = {"ap", "pa", "ar", "ra"}  # 積集合
dump X - Y      # = {"se", "ad", "di", "is"}  # 差集合
dump "se" in X  # = true  # Xに含まれるか
dump "se" in Y  # = false # Yに含まれるか

setsモジュールには、通常のハッシュ集合であるHashSetと挿入順を記憶するOrderedSetが定義されており、今回は和集合等の演算子が定義されているHashSetを使用しました（Wandbox）。

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

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

import std/strformat

proc genStr(x: int, y: string, z: float): string = 
  return fmt"{x}時の{y}は{z}"

let 
    x=12
    y="気温"
    z=22.4
echo genStr(x, y, z)

strformatモジュールには、文字列フォーマットができる演算子fmtと&が定義されています。fmtの場合は、raw文字列リテラル(受け取った文字をそのまま)として解釈するなどの細かな違いがあるようです（Nimの文字列フォーマット strformat）。今回はfmtを用いていますが、これらの挙動の違いは影響しない事例なのでどちらでも構いません（Wandbox）。

08. 暗号文

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

• 英小文字ならば(219 - 文字コード)の文字に置換
• その他の文字はそのまま出力
  この関数を用い，英語のメッセージを暗号化・復号化せよ．

import std/strutils

proc cipher(argstr: string): string = 
  result = argstr # コピー
  for i, s in result: 
    if s.isLowerAscii: 
      result[i] = chr(219-s.ord)

let str = "abc"
echo cipher(str)

(戻り値がvoidでない)procでは、暗黙にresult変数が定義され、型のデフォルト値で初期化されます。
systemモジュールのord関数で内部でのint値(文字コード)に変換します。同モジュールのchr関数は0..255の値をchar型に変換します（Wandbox）。

09. Typoglycemia

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

import std/[strutils, sequtils, random]

randomize() # 乱数発生器初期化

let str = "I couldn't believe that I could actually understand what I was reading : the phenomenal power of the human mind ."
var splits = str.split()

splits.applyIt(if it.len <= 4: it else: (var temp = it[1..^2]; temp.shuffle(); it[0]&temp.join&it[^1])) # shuffledはない
echo splits.join(" ")

randomモジュールのshuffle関数で指定したシーケンスの一連の要素をシャッフルします。指定したシーケンスの中身が入れ替わるので、何かvar変数に置いておく必要があるようです（Wandbox）。