Knuth-Morris-PrattアルゴリズムのHaskellでの実装の解説

はじめにのまえに

この記事はHaskell Advent Calendar 2019の19日目の記事の補足です。よくばってネタを増やしすぎたので、一部の話題をこちらにわけました。もとの記事でも、かんたんに説明していますが、こちらのほうがより、ていねいな説明になっています。

はじめに

文字列のなかから「特定の並びの文字列の位置」を抽出するアルゴリズムで、有名なものにBoyer-MooreアルゴリズムとKnuth-Morris-Prattアルゴリズム(以下、KMPアルゴリズムと表記)とがある。後者のHaskellによる実装について解説する。実装は「関数プログラミング 珠玉のプログラミングデザイン(以下PFADと表記する)」のものを紹介する。

サンプルコード

サンプルコードは、つぎのリポジトリに置いてある。参考にしてほしい。

GitHub: YoshikuniJujo/test_haskell/tribial/qiita/knuth_morris_pratt_algorithm/try-knuth-morris-pratt-algorithm

何のための解説か

KMPアルゴリズムの「実装の正しさ」についてはPFADで示されている。つぎのような「正しいことが自明なコード」が、まずは紹介される。

matches ws = map length . filter (endswith ws) . inits
endswith ws xs = ws `elem` tails xs

このコードからはじめて、等値性を示しながら最終的なコードへと「式変形」していく。その論理の展開を追いかけるのは、わくわくする体験だ。その過程は数学的で、うつくしい。ただ、その論理的な展開から、最終的なコードが「何をやっているのか」を読み解くのは、なかなかむずかしい。すくなくとも、僕にはむずかしかった。なので、最終的なコードが何をやっているのかを「直観的に」つかむのにやくだつように、この解説を書こうと思う。

KMPアルゴリズムは何をするアルゴリズムか

KMPアルゴリズムは「文字列のなかに特定の並びがどこにあるかを示す」ためのアルゴリズムだ。たとえば、つぎのような例をみてみよう。

文字列: ababcabcab
探したい並び: abcab

このとき、このアルゴリズムがかえす値は7, 10となる。

1234567890
ababcabcab

探したい並びの末尾の文字が(先頭を1として)何番目になるかをかえす。ここで、解説用のStackプロジェクトを作成しよう。

% stack new try-knuth-morris-pratt-algorithm
% cd try-knuth-morris-pratt-algorithm

「正しいことが自明なコード」を実際に動かしてみよう。ファイルapp/Main.hsの内容は適当に変更しておく。

app/Main.hs

module Main where

main :: IO ()
main = putStrLn "dummy"

で、src/Lib.hsを、つぎのように編集する。

src/Lib.hs

module Lib where

import Data.List

matches :: Eq a => [a] -> [a] -> [Int]
matches ws = map length . filter (endswith ws) . inits

endswith :: Eq a => [a] -> [a] -> Bool
endswith ws xs = ws `elem` tails xs

関数initsは、あたえられたリストlと0 <= n <= length lとなるすべてのnについて、「lのはじめのn個ぶん」であるようなリストのリストをかえす。「lのはじめのn個ぶん」であるようなリストのうち、おわりのところの並びがwsになっているようなものだけをあつめて、それらの長さをもとめれば、もとめたい「特定の並びの位置」を得ることができる。

関数endswithは「おわりが特定の並びになっているかどうか」をかえす。「lのおわりのn個ぶん」であるようなリストのなかに、「特定の並びws」が存在するかどうかをチェックしている。試してみよう。

% stack ghci
> matches "abcab" "ababcabcab"
[7,10]
> matches "ababcababd" "ababcababdababcababcababd"
[10,25]

KMPアルゴリズムのHaskellによる実装

で、PFADでは上記のコードから等値性を示しながら、KMPアルゴリズム(実際にはMPアルゴリズムまで)を導くわけだけど、ここでは最終的なコードについて、「直観的な説明」を試みる。

どのような実装か

状態機械(オートマトン)を作り、それに対して「探索される文字列」を1文字ずつ入力していく。で特定の状態になったときに入力された文字のインデックスをリストに追加していく。ちなみに、(たぶん)ここで作る状態機械は決定性有限状態機械だ。

Wikipedia: 決定性有限状態機械

状態機械では入力ごとに「ある状態」から「つぎの状態」へと遷移する。その状態をここでは木で表現することにする。

src/KnuthMorrisPrattAlgorithm.hs

{-# LANGUAGE LambdaCase #-}
{-# OPTIONS_GHC -Wall -fno-warn-tabs #-}

module KnuthMorrisPrattAlgorithm where

data Rep a = Null | Node a (Rep a) (Rep a)

この木をつぎのように利用する。Eq a => aのような型の値を「文字」と呼び、Eq a => [a]のような型の値を「文字列」と呼ぶことにする。

• Eq a => Rep [a]を状態として利用する
• Node [] l rのときは、文字列のマッチに並びのすべての文字を使いきった状態なので、つぎの文字の入力時には「マッチは失敗」となり、左の枝lに状態が遷移する
• Node (v : vs) l rのようなときに、入力を文字xとすると
  • v /= xならば左の枝lに状態が遷移する
  • v == xならば右の枝rに状態が遷移する
• 探索する文字のパターンをwsとしたとき、状態の初期値はNode ws ...とする

つまり、パターンと文字列とを比較していき、文字列がパターンに一致しているあいだは右の枝をたどり、一致しない文字が出現したところで左の枝をたどるということ。

状態遷移を表す関数step

状態遷移を表す関数stepを定義する。

src/KnuthMorrisPrattAlgorithm.hs

step :: Eq a => Rep [a] -> Rep [a] -> a -> Rep [a]
step rt = op
        where
        op Null _ = rt
        op (Node [] l _) x = op l x
        op (Node (v : _) l r) x
                | v == x = r
                | otherwise = op l x

関数stepの第1引数rtは「初期状態」だ。ローカルな関数opでは、状態がNullなら、つぎは初期状態に遷移する。値構築子Nodeの第1引数のリストが空リストであれば、並びのすべての文字でのマッチが終了したことであり、新たな文字の入力に対するマッチは失敗ということになり、左の枝を試すことになる。空リストでなければ、リストの先頭の要素と入力された文字とを比較して、一致すればマッチは成功し右の枝に遷移する。そうでなければマッチは失敗ということになり、左の枝をたどったさきの状態であらためてマッチするかどうか試す。

単純な状態遷移の例

"abc"を探索する木を定義してみる。

src/KnuthMorrisPrattAlgorithm.hs

sampleTreeAbc :: Rep String
sampletreeAbc =
        Node "abc" Null . Node "bc" Null . Node "c" Null $ Node "" Null Null

試してみよう。

% stack ghci
> (\(Node vs _ _) -> vs) <$> scanl (step sampleTreeAbc) sampleTreeAbc "abxabcd"
["abc","bc","c","abc","bc","c","","abc"]

関数stepの第1引数には木の初期値を指定する。これは「マッチに失敗した」ときに、はじめにもどるためだ。第2引数は「現在の状態」になる。第3引数は、それぞれの入力だ。関数scanlはだいたいfoldlとおなじだけど、foldlで「状態」がたどる経過をリストにしてかえす。"abc"を探す木に"abxabcd"という入力をあたえた。Node vs _ _のvsの部分をとりだすと上記のようなリストになった。これは、つぎのようになっていることを示す。

• 初期状態はNode "abc" _ _
• 'a'がマッチし状態はNode "bc" _ _のようになる
• 'b'がマッチし状態はNode "c" _ _
• 'x'はマッチしないので、左の枝をたどるとNullであり、さらに再帰的に関数opが適用されて、初期状態のNode "abc" _ _になる
• 同様に'a', 'b', 'c'がつぎつぎとマッチして、状態がNode "" _ _のようになり、これは「パターンをみつけた」ということ
• 'd'の入力で初期状態にもどる

もうすこし複雑な状態遷移の例

こんどは、もうすこし複雑な例として"aabc"を探索する状態機械を定義してみよう。

src/KnuthMorrisPrattAlgorithm.hs

sampleTreeAabc :: Rep String
sampleTreeAabc = let
        rt = Node "aabc" Null . Node "abc" rt
                . Node "bc" (step rt rt 'a') . Node "c" rt $ Node "" rt Null in
        rt

コードの説明のまえに試してみよう。

> :reload
> (\(Node vs _ _) -> vs) <$> scanl (step sampleTreeAabc) sampleTreeAabc "aaabcd"
["aabc","abc","bc","bc","c","","aabc"]

これは、つぎのようになっていることを示す(状態Node vs _ _をvsと表記する)。

• 初期状態は"aabc"
• 'a'が入力され、状態"abc"に遷移
• 'a'が入力され、状態"bc"に遷移
• 'b'が期待されるが'a'が入力されるので左の枝に遷移
  • 左の枝はstep rt rt 'a'と定義されている
  • つまり状態"abc"だ
  • この状態に対して'a'が入力されるので、右の枝に遷移して状態"bc"になる
• 'b', 'c'が入力され、探索は成功
• 'd'が入力され状態は初期値になる

状態sampleTreeAabcの定義のなかで、みっつめのNodeであるNode "bc" l rに注目する。この状態であるということは、すでに'a', 'a'と読み込んできたということ。もしここでマッチしなかったとき遷移すべき状態は初期状態ではなく「すでに'a'がひとつ読み込まれている状態」であるはずだ。なので、Node "bc" l rのlの部分はstep rt rt 'a'となっている。

マッチに失敗した場合には、どうなる?

マッチに失敗した場合には、「『それまで成功してきた文字列から先頭の1文字を削ったもの』を入力したあとの状態」に遷移させる必要がある。「それまで成功してきた文字列」が「探索している並びの先頭部分」に一致することが、ひとつのポイントだ。それによって「遷移先」を「文字列の入力」を待つことなく「探索する並び」のみから決めることができる。

たとえば、"ababcd"のような並びを探索したいような場合、もしも、'a', 'b', 'a', 'b'ときて、'c'とのマッチに失敗したとする。このときに遷移するべき状態は初期状態ではなく'a', 'b'と2文字読み込んだ状態だ。はじめの一文字で、マッチしなければ初期状態にもどることを考えると、'a', 'b'と2文字読み込んだ状態と'b', 'a', 'b'と3文字読み込んだ状態とは、おなじことだ。

つまり、パターンwsのうちusまで読み込んだところで、マッチに失敗した場合に、もどるべき状態は初期状態に対して「読み込んだ文字列usの先頭を削った文字列(tail us)」を、入力した状態だ。

状態遷移をあらわす木を生成する関数grep

ここまでの話をふまえて、状態遷移をあらわす木を生成する関数をみてみよう。

src/KnuthMorrisPrattAlgorithm.hs

grep :: Eq a => Rep [a] -> Rep [a] -> [a] -> Rep [a]
grep _ l [] = Node [] l Null
grep rt l va@(v : vs) = Node va l (grep rt (step rt l v) vs)

関数grepの第二引数lは、かえされる木の左の枝になる。で、この引数lの変化に注目する。

• l0 -> なにも読み込んでいない状態
• l1 = step rt l0 v0 -> v0を読み込んだ状態
• l2 = step rt l1 v1 -> v0, v1を読み込んだ状態
• l3 = step rt l2 v2 -> v0, v1, v2を読み込んだ状態
• ...

このように、右の枝で削られていく文字を入力として、つぎつぎに状態を遷移させていくかたちになっている。ここで、初期値l0にNullを指定してやることで、はじめの文字を読みとばすことになる。

状態機械を動かす

実際に探索をおこなう関数を定義する。

src/KnuthMorrisPrattAlgorithm.hs

run :: Eq a => [a] -> [a] -> [Rep [a]]
run ws = scanl (step root) root where root = grep root Null ws

grepの第1引数は木の初期値である。第2引数のNullによって、「失敗したときに遷移する状態」が並びwsの1文字めを読まないようにする。関数step rootが1文字ずつの入力に対する状態遷移をあらわす関数だ。scanlで状態遷移の履歴をリストにためていく。あとは、状態遷移の履歴のなかでNode vs _ _におけるvsが空文字列("")になっているものの位置をもとめればいい。

src/KnuthMorrisPrattAlgorithm.hs

matches :: Eq a => [a] -> [a] -> [Int]
matches ws = (fst <$>) . filter (ok . snd) . zip [0 ..] . run ws

ok :: Rep [a] -> Bool
ok = \case Null -> False; Node vs _ _ -> null vs

試してみよう。

> :module KnuthMorrisPrattAlgorithm
> matches "abcab" "ababcabcab"
[7,10]

MPアルゴリズムからKMPアルゴリズムへ

ここまでだと、じつはKnuth-Morris-Prattアルゴリズムではなくて、Morris-Prattアルゴリズムであるようだ。MPではなくKMPにするためには、もうすこし最適化しなければならない。基本的な考えかたは、つぎのとおりだ。

• "ababcd"の"aba"までマッチして失敗したなら、最後の入力は'b'ではありえない
• つまり、遷移先である左の枝が'b'とのマッチをテストしているとしたら、その状態はとばすことができる

つぎのような関数nextを定義する。

src/KnuthMorrisPrattAlgorithm.hs

next :: Eq a => Rep [a] -> a -> Rep [a]
next t@Null _ = t
next t@(Node [] _ _) _ = t
next t@(Node (v : _) l _) x | v == x = next l x | otherwise = t

この関数nextは第1引数の「状態」が、第2引数xについて「xであることをチェックする状態」であったときに、「そのチェックが失敗したときの状態」である左の枝で、その状態を再帰的に置き換える。で関数grepをつぎのように変更する。

src/KnuthMorrisPrattAlgorithm.hs

grep :: Eq a => Rep [a] -> Rep [a] -> [a] -> Rep [a]
grep _ l [] = Node [] l Null
grep rt l va@(v : vs) = Node va (next l v) (grep rt (step rt l v) vs)

Node va l (grep ...のlを(next l v)で置き換えた。これで、はれてKMPアルゴリズムになった。

中断と途中からの継続を可能にする

たとえば、端末から入力された文字列をあつかうとする。入力を1行ずつ取りこみつつ、複数行にまたがる並びも検出できるようにしたい。つぎのような例を考える。

探索したい並び: madamimadam
入力:
madam
im
adam

状態機械の状態を明示的にあつかいたい。そのような関数を定義しよう。まずは、「状態」をあらわす型を定義する。Rep [a]でもよさそうだけど、関数stepには第2引数の「現在の状態」だけではなく、第1引数の「初期状態」も必要になるので、両方をまとめた型を定義するとよさそうだ。

src/KnuthMorrisPrattAlgorithm.hs

data KmpState a = KmpState {
        rootRep :: Rep [a],
        currentRep :: Rep [a] }

これに対して、初期状態を生成する関数、状態を遷移させる関数、それと「みつけた」かどうかをチェックする関数を定義する。

src/KnuthMorrisPrattAlgorithm.hs

initialState :: Eq a => [a] -> KmpState a
initialState ws = KmpState root root where root = grep root Null ws

nextState :: Eq a => KmpState a -> a -> KmpState a
nextState st x = st { currentRep = step (rootRep st) (currentRep st) x }

found :: KmpState a -> Bool
found = ok . currentRep

それぞれ、定義ずみの関数をKmpState a型をあつかうようにラップしているだけだ。モジュール宣言を、つぎのように修正する。

src/KnuthMorrisPrattAlgorithm.hs

module KnuthMorrisPrattAlgorithm (
        matches, KmpState, initialState, nextState, found ) where

これらの関数を試してみよう。モジュールTryKmpStateを作成する。

src/TryKmpState.hs

{-# OPTIONS_GHC -Wall -fno-warn-tabs #-}

module TryKmpState where

import KnuthMorrisPrattAlgorithm

checkMatch :: Eq a => KmpState a -> [a] -> Maybe (KmpState a)
checkMatch st [] = if found st then Nothing else Just st
checkMatch st (x : xs)
        | found st = Nothing
        | otherwise = checkMatch (st `nextState` x) xs

checkLines :: KmpState Char -> IO ()
checkLines st = do
        cs <- getLine
        case checkMatch st cs of
                Nothing -> putStrLn "found"
                Just st' -> checkLines st'

関数checkMatchは探している並びがみつかるまでは、Just値として新しい状態をかえす。探している並びがみつかったらNothingをかえす。関数checkLinesは1行読みこんで、読みこんだ文字列に関数checkMatchを適用し、みつかったとき(Nothing)は"found"を表示し、まだみつかっていないとき(Just st')は、新しい状態を引数にして関数checkMatchを再帰的に呼び出している。試してみる。

% stack ghci
> :module KnuthMorrisPrattAlgorithm TryKmpState
> checkLines $ initialState "madamimadam"
madam
madam
madam
im
adam
found

うまくいったようだ。これで複数回にわたる入力をひとつの文字(などの)列として探索の対象とすることができる。

まとめ

Knuth-Morris-PrattアルゴリズムのHaskellでの実装について、直観的に理解するための解説だ。「関数プログラミング 珠玉のアルゴリズムデザイン」には、より数学的で厳密な導出法が記載されている。また、ここでは「状態」を明示的に引数としてとり、返り値としてかえすような使いかたについても試してみた。