きくらげ観察日記

好きなことを、適当に。

さくらVPSでシリアルコンソールからログインできない

さくらVPSのサーバーに標準で用意されているUbuntuをインストールしてシリアルコンソールを起動してみたところ、なぜかログインできない問題が発生。



デフォルトで用意されているユーザー名がubuntuなの知りませんでした、というオチでした。

Leftist Heapの性質

Leftist Heapは、純粋関数型的にヒープを操作するために用いられるデータ構造です。

Leftist Heapは要素が左に偏っている二分木として実装されます。
データ構造自体は以下のように単純に構成できます。

type 'a heap =
  | E
  | T of 'a * 'a heap * 'a heap

ただし、このデータ構造は以下のような制約を持ちます。

let rank = function
  | E -> 0
  | T (_, _, r) -> 1 + rank r

このような関数rankを定義したとき、ツリーのどのノードT(x, l, r)に対しても、

rank l >= rank r ... (1)

が成り立っていなければなりません。

ちなみに、上の性質を満たしているLeftist Heap tでは、以下の不等式が成り立ちます。

rank t <= log(size t + 1) ... (2)

ただし、size t はtの要素数を表します。

証明:
t = E のとき、

rank t = 0 <= 0 = log(size t + 1)

なので(2)が成立。

l, r がともに(2)を満たしていると仮定して、t = T(x, l, r) のとき、
tについて(2)が成り立たないと仮定すると、rankは整数なので、

rank t >= log(size t + 1) + 1

よって、

rank r = rank t - 1
  >= log(size t + 1)

ところで、仮定よりrは(2)を満たすので、

log(size t + 1) <= rank r <= log(size r + 1)
∴ log(size t + 1) <= log(size r + 1)

logは単調増加なので、

size t <= size r

ところで、明らかに

size r < size t

であるため、矛盾。
したがって、tは(2)を満たす。

以上より、全てのleftist heap tは(2)を満たす ■


この不等式(2)が成り立つことによって、2つのヒープをマージする時に右へ右へと辿っていけばO(logn)でマージを完了させることができます。
長くなってしまったので、具体的な実装はまた今度。

PFDSを読む: 二分木の改良

長年積んでたPFDSを読み始めることにしました。
積んでる間に邦訳が出たらしいのですが、とりあえず気にしない方針で。

まずは単純な二分木

module type SET =
  sig
    type elt
    type set

    val empty : unit -> set
    val insert : elt -> set -> set
    val member : elt -> set -> bool
  end
module type ORDERED =
  sig
    type t

    val eq : t -> t -> bool
    val lt : t -> t -> bool
    val leq : t -> t -> bool
  end

module UnbalancedSet (Elt : ORDERED)
       : SET with type elt = Elt.t =
  struct
    type elt = Elt.t
    type tree =
      | E
      | T of tree * elt * tree
    type set = tree

    let empty () = E

    let rec member x tree = match tree with
      | E -> false
      | T (a, y, b) ->
         if Elt.lt x y then member x a
         else if Elt.lt y x then member x b
         else true

    let rec insert x tree = match tree with
      | E -> T (E, x, E)
      | T (a, y, b) ->
         if Elt.lt x y then T (insert x a, y, b)
         else if Elt.lt y x then T (a, y, insert x b)
         else tree
  end

最も簡単な二分木の実装です。
これを少しずつ改良していきます。

まずは、無駄な比較を減らしましょう。上のコードでは木の深さをdとすると、最大で2d回の比較をおこなうことになってしまいます。
x < y とならないような(= xと等しいかもしれない)yをおぼえていくことによって、この比較の回数をd + 1回に減らすことができます。

module UnbalancedSet_Ex2_2 (Elt : ORDERED)
       : SET with type elt = Elt.t =
  struct
    ...
    let insert x tree =
      let rec insert' parent x tree = match tree with
        | E ->
           begin match parent with
                 | Some x' when Elt.eq x x' -> E
                 | _ -> T (E, x, E)
           end
        | T (a, y, b) ->
           if Elt.lt x y then T (insert' parent x a, y, b)
           else T (a, y, insert' (Some y) x b)
      in insert' None x tree
  end

これで少しだけ高速化できました。

次に、無駄な要素のコピーを減らしましょう。
現在のところ、以下のようなツリーxsに対して要素4を追加したツリーysを新たに作った場合、xsとysは次のように要素を共有します。

f:id:cloudear8:20170429120145p:plain

しかし、例えばここで追加する要素が0であった場合、xsとysは同じツリーであるにも関わらず、以下のような要素のコピーが行われてしまいます。

f:id:cloudear8:20170429120151p:plain

これを解消するため、追加しようとしている要素を既に持っていた場合、引数のツリーをそのまま返すようにします。

module UnbalancedSet_Ex2_4 (Elt : ORDERED) : SET =
  struct
    ...
    exception Element_Exists
    let insert x tree =
      let rec insert' parent x tree = match tree with
        | E ->
           begin match parent with
                 | Some x' when Elt.eq x x' -> raise Element_Exists
                 | _ -> T (E, x, E)
           end
        | T (a, y, b) ->
           if Elt.lt x y then T (insert' parent x a, y, b)
           else T (a, y, insert' (Some y) x b)
      in try insert' None x tree
         with Element_Exists -> tree
  end

Purely Functional Data Structures

Purely Functional Data Structures

純粋関数型データ構造

純粋関数型データ構造

正規表現エンジン制作入門(2): いろいろなDFA

オートマトンの単位を落としてしまいましたが、正規表現エンジンは作っていきたいと思います。

前回定義したDFAを思い出してみましょう。

inkar-us-i.hatenablog.com

DFAは状態を持ち、入力された文字によってその状態を変えていく機械でした。

f:id:cloudear8:20170224082156p:plain

この図はsが初期状態であり、文字'0'を受け取れば状態aに、'1'を受け取れば状態bに、'2'を受け取れば状態cに遷移し、bが受理状態であるオートマトンを表しています。

このオートマトンを使って、簡単な正規表現を表してみましょう。

[abc]+を受理するオートマトン

f:id:cloudear8:20170224082931p:plain
上図のオートマトン正規表現[abc]+を受理します。初期状態はs0であり、そこからa, b, cのいずれかの文字を受け取ると受理状態s1に遷移します。
矢印が省略されている場合は失敗を意味します。すなわち、このオートマトンは実際は以下のオートマトンの省略になっています。
f:id:cloudear8:20170224083321p:plain
ちなみに、この暗黙的に用意される非受理状態fは前回実装したDFAではNothingで表されます。

このオートマトンを前回実装したDFA型の値として表してみましょう。

-- Examples.hs
-- [abc]+
abcPlus :: DFA Int Char
abcPlus = DFA {
    dfaTransTable = [
        (s0, 'a') --> s1
      , (s0, 'b') --> s1
      , (s0, 'c') --> s1
      , (s1, 'a') --> s1
      , (s1, 'b') --> s1
      , (s1, 'c') --> s1
      ]
  , dfaStart = s0
  , dfaAccepts = [s1]
  } where s0:s1:_ = [0..]

前回も説明しましたが、状態s0, s1の実体は区別できれば何でもいいので、

s0:s1:_ = [0..]

として適当な数値を割り当てています。

試しに実行してみましょう。

>>> abcPlus `accepts` "a"
True
>>> abcPlus `accepts` "b"
True
>>> abcPlus `accepts` "c"
True
>>> abcPlus `accepts` "accabbccbcbc"
True
>>> abcPlus `accepts` "accabbccbcbcd"
False
>>> abcPlus `accepts` "accabbdccbcbc"
False

abcPlusが正規表現[abc]+を表していることがわかると思います。

a(b|cd)*eを受理するオートマトン

このようなオートマトンは以下のように作ることができます。
f:id:cloudear8:20170224091002p:plain
また、このようなオートマトンを表すDFA型の値は以下のように定義することができます。

-- Example.hs
-- a(b|cd)*e
abcde :: DFA Int Char
abcde = DFA {
    dfaTransTable = [
        (s1, 'a') --> s2
      , (s2, 'b') --> s2
      , (s2, 'c') --> s3
      , (s3, 'd') --> s2
      , (s2, 'e') --> s4
      ]
  , dfaStart = s1
  , dfaAccepts = [s4]
  } where s1:s2:s3:s4:_ = [0..]

実行結果:

>>> abcde `accepts` "abcde"
True
>>> abcde `accepts` "ae"
True
>>> abcde `accepts` "abbbbe"
True
>>> abcde `accepts` "acdcdbcde"
True
>>> abcde `accepts` "acbde"
False
>>> abcde `accepts` "abcdcd"
False
>>> abcde `accepts` "abbeb"
False

このようにして実例を見ていくと、正規表現オートマトンで表せそうなことが何となくわかるのではないでしょうか。
それでは次回に続きます。

Haskellでtest/**/*Spec.hsを全部拾ってテストしてくれるやつ

よく忘れるのでメモ

{-# OPTIONS_GHC -F -pgmF hspec-discover #-}

test/Spec.hsにこの1行を書くだけで、test/内の全部のテストを拾い集めて実行してくれるmainを生成してくれます。


明日は正規表現エンジンのこと書きます。

rsyncでポート番号を指定する

本当は正規表現エンジンについての話を書きたかったのですが、最近まとまった時間が取れないので関係ないことを書きます。

タイトルの通り。

$ rsync -e "ssh -p 12345" hoge@fuga.com:/foo/bar/baz/ /piyo/rofi/

これでok

正規表現エンジン制作入門(1): 正規表現とDFA

オートマトンの単位は落としそうですが、今日から数回に分けてHaskell正規表現エンジンを自作していきたいと思います。

完成図

実は既に手元に完成品があるのですが、今回はHaskell正規表現DSLを構築したいと思います。動作例は以下の通り。

>>> str "hoge" `matches` "hoge"
True
>>> str "hoge" `matches` "fuga"
False
>>> ((str "hoge" |: str "fuga") *:) `matches` "hogefugahogefuga"
True
>>> ((str "hoge" |: str "fuga") *:) `matches` "hogefugahogefugafoobar"
False

str "hoge" が文字列 hogeを、|:が論理和を、*:が任意回の繰り返しを表します。

完成品は以下のリポジトリに上げる(予定)です。

github.com

オートマトン

正規表現エンジンを実装するには、まずオートマトンを作る必要があります。
オートマトンは理論上正規表現と等価な表現力を持っており、通常は正規表現をそのまま解析するのではなく、等価なオートマトンに変換してから文字列のマッチなどの処理を行います(たぶん)。
オートマトンは有限種類の状態からなり、入力文字によってその状態を変化させていく仮想的な機械です。文字列の各文字を先頭から順に入力していき、最終的に到達した状態の種類によって入力文字列が正規表現にマッチしたかどうかを判定します。

オートマトンにも種類はいろいろありますが、基本的に以下のような形で表すことができます。

-- Automaton.hs
module Automaton where

-- 以下2つは後でMapのキーにしたりするので、Ordのインスタンスになっています。
type Alphabet a = (Eq a, Ord a) -- アルファベット
type State s = (Eq s, Ord s) -- 状態

-- 後で使う
(-->) :: a -> b -> (a, b)
a --> b = (a, b)
infix 5 -->

-- オートマトン
class Automaton fa where
  type F fa s :: *
  step :: (State s, Alphabet a) => fa s a -> F fa s -> a -> F fa s
  initStates :: (State s, Alphabet a) => fa s a -> F fa s
  isAcceptStates :: (State s, Alphabet a) => fa s a -> F fa s -> Bool

これが状態型sを持ち、文字aの列[a]を認識するオートマトンfa s aの定義になります。
オートマトンは初期状態と呼ばれる値initStatesと、受理状態と呼ばれる値isAcceptStates, 遷移関数と呼ばれる関数stepの3種類からなります。

それぞれの定義にはF fa sという謎の型が使われていますが、これはとりあえずs自体と同等だと思ってください。オートマトンの種類によってはこのsが同時に複数存在したりする可能性があるので、抽象的な定義になっているだけです。

そうやってAutomatonの定義を読み替えると、以下のようになります。

-- 遷移関数
step :: (State s, Alphabet a) => fa s a -> s -> a -> s
-- 初期状態
initStates :: (State s, Alphabet a) => fa s a -> s
-- 受理状態
isAcceptStates :: (State s, Alphabet a) => fa s a -> s -> Bool

オートマトンfaはそれぞれ自分の状態sを持っており、その状態で文字aが入力されると、次の状態が

s' = step fa s a

となるs'に移ります。
初期状態s0のオートマトンfaに文字列a0:a1:a2:..:an:[]を与えた時、オートマトンは以下のように状態を遷移していきます。

s1 = step fa s0 a0
s2 = step fa s1 a1
...
sn = step fa s(n-1) a(n-1)
s(n+1) = step fa sn an

こうして最後にたどり着いた状態s(n+1)がisAcceptStatesを満たせば、その状態は受理状態であり、入力文字列は受理されたと言います。
最終的には、文字列が受理されることとその文字列が正規表現にマッチしていることが同値になるようなオートマトンを構成していくことになります。

今の説明に従って、オートマトンが文字列を「受理」するかどうかを判定する関数を書いてみましょう。

-- Automaton.hs
run :: (Automaton fa, State s, Alphabet a) => fa s a -> F fa s -> [a] -> F fa s
run fa ss [] = ss
run fa ss (a:as) = run fa (step fa ss a) as

-- dfa `accepts` str : dfa が列 str を受理すれば True, そうでなければ False
accepts :: (Automaton fa, State s, Alphabet a) => fa s a -> [a] -> Bool
fa `accepts` as = isAcceptStates fa (run fa (initStates fa) as)

次に、オートマトンの実際の実装例を一つ見てみましょう。以下のデータ型DFAは、オートマトンの中でも最も簡単なものである決定性有限オートマトン(Deterministic Finite Automaton)と言われるものです*1

-- Automaton/DFA.hs
module Automaton.DFA
import qualified Data.Map as M
import qualified Data.Set as S

data DFA state alpha = DFA {
    dfaTransTable :: M.Map (state, alpha) state
  , dfaStart :: state
  , dfaAccepts :: S.Set state
  } deriving (Show, Read)

instance Automaton DFA where
  type F DFA s = Maybe s
  step _ Nothing _ = Nothing
  step dfa (Just s) a = M.lookup (s, a) $ dfaTransTable dfa
  initStates dfa = Just (dfaStart dfa)
  isAcceptStates _ Nothing = False
  isAcceptStates dfa (Just s) = isAcceptState dfa s

isAcceptState :: (State s, Alphabet a) => DFA s a -> s -> Bool
isAcceptState dfa s = S.member s $ dfaAccepts dfa

DFAは初期状態をdfaStart, 受理状態を集合dfaAcceptsで表しており、状態sと文字aが来た時に次に遷移する状態をMapの形で持っています。
DFAの状態(F DFA s)はMaybe s型で表され、Nothingは常に失敗となりますが、これは単にMapに遷移先が書かれていなかった場合に無条件で失敗にするための実装上の都合です。

これを使って、簡単なオートマトンを作ってみましょう。
以下は"ab"の任意回の繰り返しを受理するオートマトンです。

-- Example.hs
{-# LANGUAGE
    OverloadedLists #-}
import Automaton
import Automaton.DFA (DFA(..))

n_times_of_ab :: DFA Int Char
n_times_of_ab = DFA {
    dfaTransTable = [
        (s, 'a') --> a
      , (a, 'b') --> b
      , (b, 'a') --> a
      ]
  , dfaStart = s
  , dfaAccepts = [b]
  } where s:a:b:_ = [0..]

OverloadedListsというGHC拡張が使われていますが、これはMapやSet等*2をリストリテラルと同様の表記で書けるようにするための拡張です。


s, a, bは状態です。区別できれば何でも良いので、s:a:b:_ = [0..]というように適当な数値を代入しています。

初期状態はsで、そこから入力文字'a'を受け取ると状態aになります。状態aから入力文字'b'を受け取ると状態bに移り、状態bから入力文字'c'を受け取ると状態aに戻ります。それ以外の場合は失敗(受理されない)です。

f:id:cloudear8:20170209170509p:plain

最終的に状態bにたどり着いていれば、その文字列は受理されたこととなります。

>>> n_times_of_ab `accepts` "" -- 空文字列は受理しない
False
>>> n_times_of_ab `accepts` "ab" -- "ab" の1回の繰り返しなのでok
True
>>> n_times_of_ab `accepts` "abababab" -- "ab" の4回の繰り返しなのでok
True
>>> n_times_of_ab `accepts` "ababababa" -- aで終わってるのでダメ
False
>>> n_times_of_ab `accepts` "aababab" -- 先頭がaaとなっているのでダメ
False
>>> n_times_of_ab `accepts` "bababab" -- bから始まっているのでダメ
False

*1:DFA自体の厳密な定義についてはここでは触れません。気になる方はWikipediaとかに載っているので読んでみてください。 決定性有限オートマトン - Wikipedia

*2:GHC.Exts.IsListのインスタンスである任意の型