Haskellで自然言語処理100本の1章を解いてみます！

Haskellで自然言語処理100本ノックの第1章を解いてみる。【前編】の続き
まあ１章だけなら対して苦労しないだろうって誰もがツッコミを入れているだろうが。。

05問目の内容が結構ふんだんになってしまった

なのでひとつの記事にしました。

問題と解答に至るまでの過程

05. n-gram

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

まず、n-gramとはなにかから始まってしまう。
とりあえずwikiで調べる。

「N文字インデックス法」「Nグラム法」などともいう。検索対象を単語単位ではなく文字単位で分解し、後続の N-1 文字を含めた状態で出現頻度を求める方法。

はっきりいって↑だけではわからん。(英語版wikiには多少詳しくかいてある。)
他にも調べていくと、

隣り合う(連続する)n個

などと書いてあり、ようやく近づいてくる。
調べを進めていくとどうも

単語n-gramは連続するn個の単語
文字n-gramは連続するn個の文字

という認識らしい。
nが2のときn-gramはbi-gramともいえるようだ。
具体的に見ていくと、

↑のソース

上は"This is a sentence"に対する単語n-gramである。
文字n-gramは最小単位を単語ではなく文字にしたバージョンであるとみていいだろう。

では、Haskellではどのようにしてn-gram関数をかくのか？
リストの先頭のnつをとって、次はリストの先頭をのぞいたリストから先頭のnつをとって、....
といけるので**再帰による定義**ができるように思える。
実際、takeとdropを使って、

ngram

ngram :: Int -> [a] -> [[a]]
ngram n xs  | n <= length xs = take n xs : ngram n (drop 1 xs)
            | otherwise      = []

のように再帰で記述できる。

ただ、ググると他にもいろいろ方法はあるようだ。
見たものに共通して見られるのは

tailsとmapとtake

map (take n) . tails

を使用する方法である。
tails関数は部分リストのリストを生成する関数で、たとえば"sentence"に対してtailsを適用すると、

tails

Prelude Data.List> tails "sentence"
["sentence","entence","ntence","tence","ence","nce","ce","e",""]

のようになり、一番大きい要素がリストの先頭となる。
そんなわけで、map (take n)を引き続き適用すると

tailsとmapとtake

Prelude Data.List> map (take 2) . tails $ "sentence"
["se","en","nt","te","en","nc","ce","e",""]

といった結果になる。
あとはtakeなり、filterなりをかませば期待する結果が得られる。
というわけで解答は以下のようになりました。

05.hs

module Main where

import qualified Data.List as List
import qualified System.IO as IO

-- 解答その1
ngram :: Int -> [a] -> [[a]]
ngram n xs  | n <= List.length xs = List.take n xs : ngram n (List.drop 1 xs)
            | otherwise           = []
-- 解答その2
ngram' :: Int -> [a] -> [[a]]
ngram' n = List.filter (\xs -> List.length xs == n) . List.map (List.take n) . List.tails

main :: IO()
main = do
    let sentence = "I am an NLPer"
        wbigram = Main.ngram 2 $ List.words sentence  -- 単語bi-gram
        cbigram = Main.ngram 2 sentence               -- 文字bi-gram
    IO.print wbigram
    IO.print cbigram

出力

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