🦉

n-gramをHaskellで実装する

2025/09/09に公開

前書き

本記事ではn-gramを関数型言語であるHaskellで実装します。読者は関数型言語やHaskellの初心者レベルを想定しています。

n-gramとは

定義

文字列を連続するn要素ごとに分割する手法です。(nは自然数で文字列の長さ以下) 特に、n=2 のときバイグラム、n=3 のときトリグラムと呼びます。自然言語処理で利用される前処理の手法です。

https://en.wikipedia.org/wiki/N-gram

ちなみにn-gramの定義ですが、日本語版Wikiにはなぜかありません。バイグラムならあるのですが...

Pythonによる実装

定義だけ見てもわかりにくいと思いますので、Pythonでの実装例を出します。

from typing import List

def ngram(n: int, sentence: str) -> List[str]:
    """
    Generates a list of n-grams (substrings of length n) from a given string.

    Args:
        n (int): The length of the n-grams to generate.
        sentence (str): The input string.

    Returns:
        List[str]: A list of n-grams.
    
    Examples:
        >>> ngram(2, "python")
        ['py', 'yt', 'th', 'ho', 'on']
        >>> ngram(3, "banana")
        ['ban', 'ana', 'nan', 'ana']
        >>> ngram(4, "hello")
        ['hell', 'ello']
        >>> ngram(5, "world")
        ['world']
        >>> ngram(6, "test")
        []
    """
    return [sentence[i:i+n] for i in range(len(sentence) - n + 1)]

Haskellのよる実装

Haskellの場合も短く書けますが、後述するようにPythonとはアルゴリズムが異なります。

import Data.List

ngram :: Int -> [a] -> [[a]]
ngram n sentence =
  takeWhile
    (\ys -> length ys == n) 
    (map (take n) (tails sentence))

解説

tails

tails 関数は「すべての末尾リスト」を返します。例えば、helloという文字列の場合、次のような出力をします。

tails "hello"
["hello", "ello", "llo", "lo", "o", ""]

この部分がスライディングウィンドウのスタート位置までのトリミングの役割をしています。

map (take n) ...

次に後ろ側のトリミングをします。これは先頭3要素を取り出すだけです。Haskellの Stringは[Char]の型シノニムであす。takeは[a]型に対して動作しますので、String（=[Char]）にも適用できます。

map (take 3) (tails "hello")
["hel", "ell", "llo", "lo", "o", ""]

takeWhile

takeWhile cond ... で長さが足りていない文字列を削除します。例えば、次のリストであれば、"lo"で takeWhile が打ち切りになり、 ["hel", "ell", "llo"] が戻り値になります。

["hel", "ell", "llo", "lo", "o", ""]

頻度を数える

n-gramの実装ができたので、頻度を数えてみます。sort、group 関数で連続する同一の要素同士をリスト化します。最後にそれぞれの語彙のリストの要素数を数えて表示します。

import Data.List (tails, sort, group)

ngram :: Int -> [a] -> [[a]]
ngram n sentence =
  takeWhile
    (\ys -> length ys == n) 
    (map (take n) (tails sentence))


ngramCount :: Int -> String -> [(String,Int)]
ngramCount n sentence =
  map (\s -> (head s, length s))
  $ group
  $ sort
  $ ngram n sentence

main :: IO ()
main = do
    let sentence = "Where there is a will, there is a way"
    let bigrams = ngramCount 2 sentence
    let trigrams = ngramCount 3 sentence

    putStrLn "Original sentence:"
    putStrLn sentence
    putStrLn ""

    putStrLn "Bigrams (n=2):"
    print bigrams
    
    putStrLn ""
    putStrLn "Trigrams (n=3):"
    print trigrams

出力は以下のようになります。

Original sentence:
Where there is a will, there is a way

Bigrams (n=2):
[(" a",2),(" i",2),(" t",2),(" w",2),(", ",1),("Wh",1),("a ",2),("ay",1),("e ",3),("er",3),("he",3),("il",1),("is",2),("l,",1),("ll",1),("re",3),("s ",2),("th",2),("wa",1),("wi",1)]

Trigrams (n=3):
[(" a ",2),(" is",2),(" th",2),(" wa",1),(" wi",1),(", t",1),("Whe",1),("a w",2),("e i",2),("e t",1),("ere",3),("her",3),("ill",1),("is ",2),("l, ",1),("ll,",1),("re ",3),("s a",2),("the",2),("way",1),("wil",1)]

感想

勢いで夜中書いてみましたが、綺麗に宣言できて満足しています。バグを出しがちなインデックスを使わずに定義できるところが良いですね。

今回は単純に数えるだけでしたが、次はBoW (Bag-of-Word)作成などの集計処理を書いてみようと思います。

前書き