Hatena::ブログ(Diary)

Haskell はスケるよ このページをアンテナに追加 RSSフィード

2006 | 04 | 05 | 06 | 09 | 10 | 12 |
2007 | 01 | 02 | 03 | 05 | 07 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 11 |
2009 | 02 | 03 | 05 | 10 | 12 |
2010 | 01 |
2012 | 12 |

2012-12-30 ブログ引っ越した このエントリーを含むブックマーク

3年近くもほったらかしだったけど、衝動的にレンタルサーバを借りてブログを立ち上げた。

 cf. blog.panicblanket.com

過去記事も一通り移行済みだけど、ここも残しておきます。

2010-01-30

本買った

プログラミングClojure

プログラミングClojure

本屋で見かけたのでついうっかりと。Scalaの本は迷った挙句にやめたのに……大きさが手頃だからかも。

で,第1章 Getting Started と第2章 Clojureひとめぐり だけ読んでみた。以下メモ。

  • JVMの上で動くLisp リ・ローデッド。
  • カッコはやや少ない。
  • 関数型。
  • Javaのクラスが利用できる。
  • 並行プログラミングが簡単。
  • 動的型。
  • 一般にデータは変更不可能だけど,リファレンスは状態を持つことができる。
 user=> #{}
 #{}
 user=> (def visitors (ref #{}))
 #'user/visitors
 user=> (dosync (alter visitors conj "Stu"))
 #{"Stu"}
 user=> {:Lisp "McCarty", :Clojure "Hickey"}
 {:Lisp "McCarty", :Clojure "Hickey"}
  • :(コロン)出始まってるのはキーワードRuby の Symbol のようなもの。
  • マップは関数としても働く。引数としてキーを与えると対応する値が返る。
 user=> ({:Lisp "McCarty", :Clojure "Hickey"} :Clojure)
 "Hickey"
  • キーも関数として働く。引数としてマップを与えるとキーに対応する値が返る。
 user=> (:Clojure {:Lisp "McCarty", :Clojure "Hickey"})
 "Hickey"
 user=> (defn is-small? [number]
   (if (< number 100)
     "yes"
     (do
       (println "Saw a big number" number)
       "no")))
 #'user/is-small?
 user=> (is-small? 101)
 Saw a big number 101
 "no"

2009-12-16

suffix array ってのは

こないだのを参考にしてくれたらしい。

なんだか俺のコードよりもHaskellらしく見えるよ。

ところで,リンク先のコードだと検索するたびに suffix array というか suffix のリストを作っているように見える。俺の理解では,suffix array を利用するメリットというのは,suffix array を作るときには大量にメモリを必要とするけど検索するときには必要ない,ってことだと思うんだけど。


それはそれとして forever という関数を初めて知った。今度使ってみよう。

2009-12-12

簡単なWebサーチエンジンの作り方を試す

気がつけば12月も中旬だよ……。

少し前になるけど,「あとで試す」タグをつけといたやつをやってみる。これ↓:

具体的な手順はこっちのページで公開されている。


さて,順にやってみよう。

課題1-1

与えられた文字列のsuffix arrayを作成するプログラムを作成せよ.

 import Data.List
 
 suffixArray :: String -> [Int]
 suffixArray xs = map fst $ sort' $ zip [1..] $ init $ tails xs
   where
     sort' = sortBy (\a b -> compare (snd a) (snd b))

実行例:

 *Main> suffixArray "abcbccab"
 [7,1,8,2,4,6,3,5]

課題1-2

与えられた文字列に対し,その部分文字列を入力し,部分文字列が出現する全位置を列挙する検索プログラムを作成せよ.(ヒント: suffix array上の2分探索を行う)

二分探索とはいうものの,検索対象の部分文字列の出現箇所すべてを列挙するには,中央の値(suffix)の右か左を単純に無視してしまうわけには行かない。場合によっては左右両方にあるかもしれないから。なので,まずは整理してみる。

  1. 検索文字列よりも小さい → 左にはない。右を検索。
  2. 検索文字列と等しい → 当たり。左にはないが,まだ右にはあるかもしれないので検索。
  3. 検索文字列よりも大きい → これはさらに2ケースに分けられる。
    1. 検索文字列がプレフィックスになっている → 当たり。さらに左にも右にもあるかもしれないので両方を検索。
    2. 検索文字列がプレフィックスになっていない → 右にはない。左を検索。

これをコードにするとこうだ:

 import Data.List
 
 suffixArray :: String -> [Int]
 suffixArray xs = map fst $ sort' $ zip [1..] $ init $ tails xs
   where
     sort' = sortBy (\a b -> compare (snd a) (snd b))
 
 suffixOf :: String -> Int -> String
 suffixOf s n = drop (n-1) s
 
 search :: String -> [Int] ->  String -> [Int]
 search _ []  _  = []
 search s ary sb = let n = (length ary) `div` 2
                       sfx = suffixOf s (ary !! n)
                   in
                   if sfx < sb then
                       search s (drop (n+1) ary) sb
                     else if sfx == sb then
                       (ary !! n) : search s (drop (n+1) ary) sb
                     else if isPrefixOf sb sfx then
                       (search s (take n ary) sb) ++ [ary !! n] ++ (search s (drop (n+1) ary) sb)
                     else
                       search s (take n ary) sb

実行例:

 *Main> search "abcbccab" (suffixArray "abcbccab") "ab"
 [7,1]

課題1-3

指定された1個のHTMLテキストファイルをメモリ中に読み込んで1個の文字列とし,それに対する suffix array をメモリ中に作成し,ユーザから入力された文字列を検索して,入力文字列が出現する全位置を列挙するプログラムを作成せよ.

ファイルを読み込んで,searchを適用して,あとは適当にフォーマットして出力すればいいだけだ。ファイルは課題のページからリンクしてるこのページをダウンロードして使った(ファイル名決めうち)。

 module Main where
 
 import Data.List
 import System.Environment ( getArgs )
 
 -------------------------------------------------------------------------------
 
 filename = "CodeConvTOC.doc.html"
 
 main :: IO ()
 main = do argv <- getArgs
           contents <- readFile filename
           substring <- return $ head argv
           mapM_ (putStrLn . format contents) $ search contents (suffixArray contents) substring
 
 format :: String -> Int -> String
 format str pos = show pos ++ ": " ++ take 10 (suffixOf str pos)
 
 -------------------------------------------------------------------------------
 
 suffixArray :: String -> [Int]
 suffixArray xs = map fst $ sort' $ zip [1..] $ init $ tails xs
   where
     sort' = sortBy (\a b -> compare (snd a) (snd b))
 
 suffixOf :: String -> Int -> String
 suffixOf s n = drop (n-1) s
 
 search :: String -> [Int] ->  String -> [Int]
 search _ []  _  = []
 search s ary sb = let n = (length ary) `div` 2
                       sfx = suffixOf s (ary !! n)
                   in
                   if sfx < sb then
                       search s (drop (n+1) ary) sb
                     else if sfx == sb then
                       (ary !! n) : search s (drop (n+1) ary) sb
                     else if isPrefixOf sb sfx then
                       (search s (take n ary) sb) ++ [ary !! n] ++ (search s (drop (n+1) ary) sb)
                     else
                       search s (take n ary) sb
 
 -------------------------------------------------------------------------------

実行例:

 ^o^ >runhaskell suffixArray.hs File
 10208: File Examp
 1959: File Names
 1664: File Names
 2250: File Organ
 1815: File Suffi
 2422: Files</a>

課題1-4

ちょっと時間があいたけど続き。

以下の手順で,複数ファイルに対して全文検索を行うプログラムを作成せよ.

1. 指定された1個以上のm個のファイルをメモリ内で連結した長い文字列を作る.そのときにファイルの境 界に,テキストファイル中には通常は現れない文字(例えばヌル文字'\0'等)を入れ,検索時に複数ファイルを またいだ文字列にマッチしないようにしておく.

2. 1.で作った作った長い文字列中の文字位置から元のファイル名を得られるようにするための表を作る. 例えば,file1.html, file2.html, file3.htmlがそれぞれ100, 200, 300のファイルサイズをもつとき,[("file 1.html", 100), ("file2.html", 200), ("file3.html", 300)]というような表を作る(効率的な方法,プログ ラムしやすい方法を各自工夫せよ).

3. 課題1-3で作成したプログラムと,1.および2.で作ったデータを用いて,ユーザから入力された文字列を 検索し,入力文字列が出現するファイル名とファイル内の位置(ファイルの先頭から数えた文字数)を全て列 挙するプログラムを作成せよ.

課題1-3から変えたとこだけ:

 main :: IO ()
 main = do argv <- getArgs
           files <- mapM readFile $ tail argv
           let contents = concat $ intersperse "\0" files
           let table = makeFileTable (tail argv) $ map length files
           let substring = head argv
           mapM_ (putStrLn . format table contents) $ search contents (suffixArray contents) substri ng
 
 -------------------------------------------------------------------------------
 
 format :: [(String, Int)] -> String -> Int -> String
 format t str pos = let (f, p) = filePos t pos
                    in
                    f ++ ": " ++ show p ++ ": " ++ take 15 (suffixOf str pos)
 
 -------------------------------------------------------------------------------
 
 makeFileTable :: [String] -> [Int] -> [(String, Int)]
 makeFileTable fs ls = zip fs $ snd $ mapAccumL (\a x -> (a+x+1, a)) 1 ls
 
 
 filePos :: [(String, Int)] -> Int -> (String, Int)
 filePos (f:[])     n              = (fst f, n - snd f + 1)
 filePos (f1:f2:fs) n | snd f2 < n = filePos (f2:fs) n
                      | otherwise  = (fst f1, n - snd f1 + 1)
 
 -------------------------------------------------------------------------------

元ファイルの表はファイル名とその開始位置をタプルにした。

実行例:

 ^o^ >runhaskell suffixArray.hs Intro CodeConvTOC.doc.html CodeCOnventions.doc.html
 CodeConvTOC.doc.html: 1063: Introduction</a
 CodeCOnventions.doc.html: 517: Introduction</h

今日はここまで。続きは明日……やれるといいなぁ。

2009-10-21

ISBN 出版者記号の割り当て規則

ISBNを扱うのに ISBN Tools というライブラリを使っている。

なんでかっていうと ISBN_Tools.hyphenate_isbn13 っていうメソッドがあって,数字だけのISBNをハイフンの入ったISBNに変換してくれるのが使えると思ったからだ。

こんな感じ:

 irb(main):006:0> ISBN_Tools.hyphenate_isbn13('9780672328848')
 => "978-0-6723-2884-8"

ところがこのメソッド,肝心の日本(グループ番号4)に対応してくれてない。

ソースを見たところ,data/ranges.dat にグループ番号と出版者記号の定義を追加すればいいみたいだ。

というわけでちょっと調べてみた。


日本国内のことなんだから日本のISBNを管理しているところへいけばいいんだろう,と思ったんだけど,その日本図書コード管理センターのサイトの中を探してみても規則で割り当ててるのか,どうもどこにも載ってない。

同じ不満をもっる人がネットのあちこちにいるみたいだな。どうなってんだ。

で,結局 ISBN の本家 International ISBN Agency のサイトPDFを見つけた。これでいいんだよな。

これによると日本の出版者記号は下のような規則になっているようだ。

2ケタ00〜19
3ケタ200〜699
4ケタ7000〜8499
5ケタ85000〜89999
6ケタ900000〜949999
7ケタ9500000〜9999999

さて,ISBN Tools に戻ろう。

調べた成果を反映するには前述の data/ranges.dat に次の1行を追加すればいい。

 4,00..19,200..699,7000..8499,85000..89999,900000..949999,9500000..9999999

カンマ区切りになってて,はじめの値がグループ番号,2つめ以降に出版者記号の連続する範囲を列挙している。これで日本の出版者にも対応するようになった。

 irb(main):007:0> ISBN_Tools.hyphenate_isbn13('9784863540224')
 => "978-4-8635-4022-4"

10ケタのISBNでもできる。

 irb(main):008:0> ISBN_Tools.hyphenate_isbn10('4873110238')
 => "4-87311-023-8"