FileMappedInputStream: 2GB以上のファイルに対応
MappedByteBuffer + InputStream: ファイルにマッピングされたランダムアクセス可能な入力ストリーム - sileの日記で作成したクラスの巨大ファイル対応版。
2GB以上のファイルでも扱うことが可能。
import java.io.IOException; import java.io.InputStream; import java.io.FileInputStream; import java.nio.ByteBuffer; import java.nio.channels.FileChannel; public class FileMappedInputStream extends InputStream { private final ByteBuffer[] maps; private int cur = 0; private int end_map; public FileMappedInputStream(String filepath) throws IOException { final FileChannel cnl = new FileInputStream(filepath).getChannel(); try { final int map_num = (int)(cnl.size()/Integer.MAX_VALUE)+1; maps = new ByteBuffer[map_num]; for(int i=0; i < map_num; i++) { final int offset = Integer.MAX_VALUE*i; final int length = (int)Math.min(Integer.MAX_VALUE, cnl.size()-offset); maps[i] = cnl.map(FileChannel.MapMode.READ_ONLY, offset, length); } end_map = maps.length; } finally { cnl.close(); } } private FileMappedInputStream(FileMappedInputStream src) { cur = src.cur; end_map = src.end_map; maps = new ByteBuffer[src.maps.length]; for(int i=0; i < maps.length; i++) // ByteBuffer複製: // - メモリ領域は共有されたまま // - 位置情報(position,limit)等は複製先と複製元で別に保持される maps[i] = src.maps[i].duplicate(); } private boolean eos() { if(end_map == cur) return true; if(maps[cur].hasRemaining()==false) { cur++; return eos(); } return false; } public InputStream range(long start, int length) throws IOException { final int map_n = (int)(start/Integer.MAX_VALUE); final long offset = start%Integer.MAX_VALUE; final long limit = offset+length; cur = map_n; maps[cur].clear().position((int)offset); if(limit < Integer.MAX_VALUE) { maps[cur].limit((int)limit); end_map = cur+1; } else { maps[cur].limit(maps[cur].capacity()); maps[cur+1].clear().limit((int)(limit-Integer.MAX_VALUE)); end_map = cur+2; } return this; } // 複数の範囲から平行して入力を行ないたい場合用のメソッド。 // // 第三引数(copy)にtrueを渡した場合に返されるインスタンスは、 // 読み込み位置情報などを他と共有することがないので、安全。 public InputStream range(long start, int length, boolean copy) throws IOException { if(copy) return new FileMappedInputStream(this).range(start, length); else return range(start, length); } @Override public int read() throws IOException { if(eos()) return -1; return (int)(maps[cur].get())&0xFF; } @Override public int read(byte[] bytes, int offset, int length) throws IOException { if(eos()) return -1; if(length < maps[cur].remaining()) { maps[cur].get(bytes, offset, length); return length; } else { final int len = maps[cur].remaining(); maps[cur].get(bytes, offset, len); if(eos()) return len; return len + read(bytes, offset+len, length-len); } } @Override public int read(byte[] bytes) throws IOException { return read(bytes, 0, bytes.length); } }
浮動小数点数のIEEE754形式への変換
倍精度浮動小数点数をIEEE754形式のビット表現(整数値)にエンコードする方法。
(defun encode-double-float (float) (declare (double-float float)) (multiple-value-bind (fraction exponent sign) (integer-decode-float float) (let ((code 0)) (setf (ldb (byte 1 63) code) (if (plusp sign) 0 1) (ldb (byte 11 52) code) (+ exponent 52 1023) (ldb (byte 52 0) code) fraction) code)))
デコード。
(defun decode-double-float (code) (let ((sign (ldb (byte 1 63) code)) (exponent (ldb (byte 11 52) code)) (fraction (ldb (byte 52 0) code))) (assert (not (and (= exponent #b11111111111) (= fraction 0)))) ; infinity (assert (not (and (= exponent #b11111111111) (/= fraction 0)))); NaN (* (if (zerop sign) 1 -1) (scale-float (+ 1.0d0 (* fraction (expt 2 -52))) (- exponent 1023)))))
実行例。
(encode-double-float 1234.5678d0) --> 4653144502051863213 (format t "~b" *) 100000010010011010010100100010101101101010111001111101010101101 --> NIL (decode-double-float 4653144502051863213) --> 1234.5678d0
Igo: JavaScriptで形態素解析
Igo: GoogleAppEngineで形態素解析サーバで用意したサーバ(※追加修正あり。後述)を使って形態素解析を行うJavaScriptを書いてみた。
制限
結構制限が多い。
形態素解析JavaScript
形態素解析を行うJavaScript関数群。
やっていることは、ほとんどigo-morp.appspot.comに対してリクエストを投げているだけ。
http://igo-morp.appspot.com/igo.jsに配置。
// ファイル: http://igo-morp.appspot.com/igo.js function igo_common(method, text, callback_name) { var enc_text = encodeURIComponent(text); var query = "text="+enc_text+"&callback="+callback_name; var url = "http://igo-morp.appspot.com/"+method+"_jsonp?"+query; var elem = document.createElement('div'); elem.innerHTML = "<script type='text/javascript' src='"+url+"'><\/script>"; document.getElementById("igo_jsonp_block").appendChild(elem); } // 形態素解析を行う。 // - text: 対象テキスト // - callback_name: コールバック関数の名前 // // コールバック関数は形態素解析終了後に呼び出される一引数関数 // - callback(parse_result) // -- parse_result: [[形態素名,素性文字列]] function igo_parse(text, callback_name) { igo_common("parse", text, callback_name); } // 分かち書きを行う。 // - text: 対象テキスト // - callback_name: コールバック関数の名前 // // コールバック関数は分かち書き終了後に呼び出される一引数関数 // - callback(wakati_result) // -- parse_result: [形態素名] function igo_wakati(text, callback_name) { igo_common("wakati", text, callback_name); } document.write("<div id='igo_jsonp_block'></div>");
サンプル
形態素解析を行うサンプルHTML。
http://igo-morp.appspot.com/js-morp-sample.html
<html> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> <script type="text/javascript" src="http://igo-morp.appspot.com/igo.js"></script> <!-- callback function --> <script type="text/javascript" language="javascript"> <!-- function parse_callback(rlt) { var result =document.getElementById("result"); var text=""; for(var i=0; i < rlt.length; i++) text += rlt[i][0] + "\t" + rlt[i][1] + "\n"; result.innerHTML = text; } function parse() { var text=document.getElementById("text").value; igo_parse(text, "parse_callback"); return false; } --> </script> <title>形態素解析サンプル</title> </head> <body> <!-- input text --> <form onsubmit="return parse()"> <textarea id="text" cols="30" rows="10"></textarea> <br /> <input type="submit" value="analyze" > </form> <br /> <!-- result --> <pre id="result"></pre> </body> </html>
形態素解析サーバ変更点
- http://igo-morp.appspot.com/parse_jsonp?text=[解析対象テキスト(UTF-8)]&callback=[コールバック関数の名前]
- POST可
- "callback(形態素名, 素性文字列);"が返される
- http://igo-morp.appspot.com/wakati_jsonp?text=[解析対象テキスト(UTF-8)]&callback=[コールバック関数の名前]
- POST可
- "callback([形態素名]);"が返される
追加したファイル。
web.xml:
<?xml version="1.0" encoding="utf-8"?> <!DOCTYPE web-app PUBLIC "-//Sun Microsystems, Inc.//DTD Web Application 2.3//EN" "http://java.sun.com/dtd/web-app_2_3.dtd"> <web-app xmlns="http://java.sun.com/xml/ns/javaee" version="2.5"> <servlet> <servlet-name>wakati</servlet-name> <servlet-class>WakatiServlet</servlet-class> </servlet> <servlet-mapping> <servlet-name>wakati</servlet-name> <url-pattern>/wakati</url-pattern> </servlet-mapping> <servlet> <servlet-name>parse</servlet-name> <servlet-class>ParseServlet</servlet-class> </servlet> <servlet-mapping> <servlet-name>parse</servlet-name> <url-pattern>/parse</url-pattern> </servlet-mapping> <welcome-file-list> <welcome-file>igo.jsp</welcome-file> </welcome-file-list> <!-- ここから下が追加分 --> <servlet> <servlet-name>wakati_jsonp</servlet-name> <servlet-class>WakatiJSONPServlet</servlet-class> </servlet> <servlet-mapping> <servlet-name>wakati_jsonp</servlet-name> <url-pattern>/wakati_jsonp</url-pattern> </servlet-mapping> <servlet> <servlet-name>parse_jsonp</servlet-name> <servlet-class>ParseJSONPServlet</servlet-class> </servlet> <servlet-mapping> <servlet-name>parse_jsonp</servlet-name> <url-pattern>/parse_jsonp</url-pattern> </servlet-mapping> </web-app>
ParseJSONPServer.java:
import java.io.IOException; import javax.servlet.http.*; import net.reduls.igo.Morpheme; import net.arnx.jsonic.JSON; import java.util.ArrayList; public class ParseJSONPServlet extends HttpServlet { public void doGet(HttpServletRequest req, HttpServletResponse resp) throws IOException { String text = req.getParameter("text"); String callback = req.getParameter("callback"); if(text==null) text = ""; if(callback==null) callback="callback"; ArrayList<ArrayList<String>> morps = new ArrayList<ArrayList<String>>(); resp.setContentType("Content-type: text/plain; charset=UTF-8"); for(Morpheme m : Igo.parse(text)) { ArrayList<String> morp = new ArrayList<String>(2); morp.add(m.surface); morp.add(m.feature); morps.add(morp); } resp.getWriter().println(callback+"("+JSON.encode(morps)+");"); } public void doPost(HttpServletRequest req, HttpServletResponse resp) throws IOException { doGet(req,resp); } }
WakatiJSONPServer.java:
import java.io.IOException; import javax.servlet.http.*; import net.arnx.jsonic.JSON; public class WakatiJSONPServlet extends HttpServlet { public void doGet(HttpServletRequest req, HttpServletResponse resp) throws IOException { String text = req.getParameter("text"); String callback = req.getParameter("callback"); if(text==null) text = ""; if(callback==null) callback="callback"; resp.setContentType("Content-type: text/plain; charset=UTF-8"); resp.getWriter().println(callback+"("+JSON.encode(Igo.wakati(text))+");"); } public void doPost(HttpServletRequest req, HttpServletResponse resp) throws IOException { doGet(req,resp); } }
行をバイト列として読み込む
テキストファイルの各行をバイト列として読み込むマクロを定義。
SBCL等のように文字列を内部的にユニコードとして表現している処理系では、テキストファイルを読み込む際、そのファイルが不正なバイト列を含んでいると読み込みに失敗することがあるので、その対処として。
;;;; エラーの例 ;;;; sbcl-1.0.40 ;;;; ;; 普通の行読み込みマクロを定義 (defmacro each-file-line ((line filepath) &body body) `(with-open-file (#1=#:in ,filepath) (loop FOR ,line = (read-line #1# nil nil) WHILE ,line DO (progn ,@BODY)))) ;;;; ;; 不正なバイト列を含むテキストファイルの作成 (with-open-file (out "sample.txt" :direction :output :element-type '(unsigned-byte 8)) (write-sequence (sb-ext:string-to-octets "一行目") out) (write-byte (char-code #\Newline) out) ;; 二行目はバイト列を反転させる (write-sequence (reverse (sb-ext:string-to-octets "ニ行目")) out) (write-byte (char-code #\Newline) out) (write-sequence (sb-ext:string-to-octets "三行目") out) (write-byte (char-code #\Newline) out)) ;;; ;; 読み込み (each-file-line (line "sample.txt") (print line)) "一行目" ;; これ以降はエラーメッセージ debugger invoked on a SB-INT:STREAM-DECODING-ERROR in thread #<THREAD "initial thread" RUNNING {A9F5831}>: decoding error on stream #<SB-SYS:FD-STREAM for "file sample.txt" {BAF5001}> (:EXTERNAL-FORMAT :UTF-8): the octet sequence (174) cannot be decoded. Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL. restarts (invokable by number or by possibly-abbreviated name): 0: [ATTEMPT-RESYNC ] Attempt to resync the stream at a character boundary and continue. 1: [FORCE-END-OF-FILE] Force an end of file. 2: [INPUT-REPLACEMENT] Use string as replacement input, attempt to resync at a character boundary and continue. 3: [ABORT ] Exit debugger, returning to top level. (SB-INT:STREAM-DECODING-ERROR #<SB-SYS:FD-STREAM for "file sample.txt" {BAF5001}> (174))
こういったファイルを読み込むために作成したのが以下のマクロ(と関数)。
;;;; ファイルの各行をバイト列として読み込むマクロの定義 ;;;; バイト列の正当性は検査しないので、上述のようなエラーは起こらない ;;;;;;;; ;;;; 型やスペシャル変数の定義 (deftype octet () '(unsigned-byte 8)) ; バイト (deftype octets () '(vector octet)) ; バイト列 (deftype simple-octets () '(simple-array octet)) ; バイト列その２ (defparameter *line-feed* #\Newline) ; 改行文字。簡単のために改行コードは一つの文字で指定されると仮定する。 (defparameter *BUFFER-SIZE-LIMIT* 102400) ; ファイル読み込み時のバッファのサイズ最大値 ;;;;;;;; ;;;; バイト行読み込みマクロ ;;;; (subseq line-bytes start end) => 各行のバイト列 (defmacro each-file-line-bytes ((line-bytes start end filepath) &body body) `(each-file-line-bytes-impl ; 実際の処理はeach-file-line-bytes-impl関数に任せる (lambda (,line-bytes ,start ,end) (declare (simple-octets ,line-bytes) ((mod #.array-dimension-limit) ,start ,end)) ,@body) ,filepath)) ;;;;;;;; ;;;; 実際にバイト行の読み込みを行う関数 (declaim (inline each-file-line-bytes-impl)) (defun each-file-line-bytes-impl (fn filepath) (declare #+SBCL (sb-ext:muffle-conditions sb-ext:compiler-note) ; コンパイル時の警告抑制 (function fn) (optimize (speed 3) (safety 0) (debug 0))) (with-open-file (in filepath :element-type 'octet) (let* ((buffer-size (min (or (file-length in) #1=*BUFFER-SIZE-LIMIT*) #1#)) (buf (make-array buffer-size :element-type 'octet)) ; 読み込み用のバッファ (read-start 0) ; バッファの読み込み開始位置。前回読み込んだ内容がバッファに残っている場合に、0以上の値となる (lf (char-code *line-feed*)) ; 改行文字の値 (stack '())) ; 一行がbuffer-size以上の場合に、溢れた分のバイト列を保持するスタック ;; バッファのサイズ分だけバイト列を読み込む (loop FOR read-len = (read-sequence buf in :start read-start) DO ;; バッファ内の改行文字を探して、(見つかった場合)ユーザが渡した関数を呼び出すループ (loop WITH start = 0 FOR lf-pos = (position lf buf :start read-start :end read-len) ; 改行文字検索 THEN (position lf buf :start start :end read-len) WHILE lf-pos DO ;; バイト列と行の範囲を渡して、fn関数を呼び出す (if (null stack) (funcall fn buf start lf-pos) ; バッファサイズ内に行が収まっている場合 (let ((bytes (apply #'concatenate 'octets (nreverse (cons (subseq buf start lf-pos) stack))))) (funcall fn bytes 0 (length bytes)) ; バッファサイズよりも大きい場合 (setf stack nil))) ;; 行の開始位置更新 (setf start (1+ lf-pos)) FINALLY (setf read-start 0) (if (zerop start) ;; バッファ内に改行が無かった場合: 内容をスタックに保存しておく (push (copy-seq buf) stack) ;; バッファ内に改行が有った場合: 最後の改行以降のバイト列を、先頭に移動する (progn (setf read-start (- read-len start)) (replace buf buf :end1 read-start :start2 start :end2 read-len)))) ;; EOFチェック (when (< read-len buffer-size) (return))))))
読み込み例。
;; each-file-lineで読み込みに失敗したファイルの各行の中身 (each-file-line-bytes (line-bytes start end "sample.txt") (print (subseq line-bytes start end))) #(228 184 128 232 161 140 231 155 174) #(174 155 231 140 161 232 139 131 227) #(228 184 137 232 161 140 231 155 174) --> NIL ;; バイト列を自分で文字列に変換し、出力する (require :creole) ; バイト列<->文字列変換ライブラリ: http://sourceforge.jp/projects/creole (each-file-line-bytes (line-bytes start end "sample.txt") (print (creole:octets-to-string line-bytes :start start :end end))) "一行目" "??猡苃?" ; 変な文字列に変換されるが、エラーは起こらない "三行目" --> NIL
linuxのwcコマンドとの比較。
$ ls huge.txt # 大きなテキストファイル -rw-r--r-- 1 user user 285M 2010-09-22 10:13 huge.txt # wcコマンド $ time wc -l huge.txt 549828 huge.txt # 55万行 real 0m0.198s # 0.2秒 user 0m0.120s sys 0m0.076s
;; each-file-line-bytesを使った行数カウント関数を定義 (defun wc (filepath &aux (count 0)) (declare (fixnum count)) (each-file-line-bytes (bytes start end filepath) (declare (ignore bytes start end)) (incf count)) (time (wc "huge.txt")) count) Evaluation took: 0.519 seconds of real time ; 0.5秒 0.516032 seconds of total run time (0.404025 user, 0.112007 system) 99.42% CPU 1,034,343,720 processor cycles 106,480 bytes consed --> 549828 ; 55万行
追記
不正なテキストファイル読み込み時のエラー対策として上記マクロを作成した、と書いたが、SBCLの場合、次の様にすれば不正なバイト列を含むテキストでも読み込むことが可能。
;; デコーディング失敗時のコンディション通知を受け取り、処理する (handler-bind ((sb-int:stream-decoding-error (lambda (condition) (declare (ignore condition)) ;; 不正なバイト列はスキップする (invoke-restart (find-restart 'sb-int:attempt-resync)) ;; 不正なバイト列を別の文字(文字列)で置き換えたい場合は、次のリスタートを使用する ;; (invoke-restart (find-restart 'sb-impl::input-replacement) #\?) ))) (each-file-line (line "sample.txt") (print line))) "一行目" "猡苃" ; エラーが起こったバイト列は抜かしてデコードされた文字列 "三行目" --> NIL
なのでeach-file-line-bytesマクロは、せっかく作ったけど不要かもしれない。
Nグラム
Nグラムを取り出すC++のクラスを作成したのでメモ。
UTF-8のみ対応。
/* * ファイル名: ngram.hh */ #ifndef TOKENIZER_NGRAM_HH #define TOKENIZER_NGRAM_HH #include <algorithm> #include <vector> #include <cstring> namespace Tokenizer { class Ngram { public: Ngram(unsigned min, unsigned max) : min(std::max(min, 1u)), max(std::min(max, 32u)) {} template<class Callback> void each_token(const char* text, Callback& fn) const { std::vector<unsigned> char_start_pos; const unsigned len = strlen(text); for(unsigned i=0; i < len; i++) { if(!(text[i]&0x80)) char_start_pos.push_back(i); // ascii else if (text[i]&0x40) char_start_pos.push_back(i); // start of a UTF-8 character byte sequence } char_start_pos.push_back(len); for(unsigned i=0; i < char_start_pos.size(); i++) for(unsigned n=min; n <= max; n++) if(i+n < char_start_pos.size()) fn(text+char_start_pos[i], text+char_start_pos[i+n]); } private: const unsigned min; const unsigned max; }; } #endif
使用例:
/* * ファイル名: ngram.cc */ #include <string> #include <iostream> #include <cstdlib> #include "ngram.hh" void print_ngram(const char* beg, const char* end) { std::cout << std::string(beg,end) << std::endl; }; int main(int argc, char** argv) { if(argc != 3) { std::cerr << "Usage: ngram <min> <max>" << std::endl; return 1; } Tokenizer::Ngram ngram(atoi(argv[1]), atoi(argv[2])); std::string line; while(std::getline(std::cin, line)) ngram.each_token(line.c_str(), print_ngram); return 0; }
実行例:
$ g++ -o ngram ngram.cc $ echo '「そりゃまたなぜです」' | ./ngram 1 3 「 「そ 「そり そ そり そりゃ り りゃ りゃま ゃ ゃま ゃまた ま また またな た たな たなぜ な なぜ なぜで ぜ ぜで ぜです で です です」 す す」 」 $ echo '「そりゃまたなぜです」' | ./ngram 4 9 「そりゃ 「そりゃま 「そりゃまた 「そりゃまたな 「そりゃまたなぜ 「そりゃまたなぜで そりゃま そりゃまた そりゃまたな そりゃまたなぜ そりゃまたなぜで そりゃまたなぜです りゃまた りゃまたな りゃまたなぜ りゃまたなぜで りゃまたなぜです りゃまたなぜです」 ゃまたな ゃまたなぜ ゃまたなぜで ゃまたなぜです ゃまたなぜです」 またなぜ またなぜで またなぜです またなぜです」 たなぜで たなぜです たなぜです」 なぜです なぜです」 ぜです」
キュー
FIFOのキュー。
これもたまに使いたくなるので、実装(の一つ)をメモしておく。
(declaim (inline make-queue enqueue dequeue queue-empty-p queue-to-list)) (defun make-queue (&optional initial-contents) (declare (optimize (speed 3) (safety 0))) (let ((que (cons nil initial-contents))) ; queue = (cons 要素リストの末尾への参照 要素リスト) (setf (car que) (last que)) que)) (defun enqueue (x que) (declare (optimize (speed 3) (safety 0))) (setf (car que) ; 2] 要素リストの末尾への参照を更新する(新しい末尾=(list x)を参照するようにする) (setf (cdar que) (list x))) ; 1] 末尾に要素を追加する que) (defun dequeue (que) (declare (optimize (speed 3) (safety 0))) (prog1 (pop (cdr que)) ; 要素リストからpop (when (null (cdr que)) (setf (car que) que)))) ; 要素リストが空になった場合は、参照を貼り直す必要がある (defun queue-empty-p (que) (declare (optimize (speed 3) (safety 0))) (eq (car que) que)) (defun queue-to-list (que) (declare (optimize (speed 3) (safety 0))) (cdr que))
使用例:
(defvar q (make-queue '(:a :b :c))) --> Q (setf *print-circle* t) ; 循環参照(?)があるため、*print-circle*をtにしないと出力が終わらなくなる --> T q --> (#1=(:C) :A :B . #1#) (dequeue q) --> :A q --> (#1=(:C) :B . #1#) (enqueue 1 q) --> (#1=(1) :B :C . #1#) (dequeue q) --> :B (queue-to-list q) --> (:C 1) (dequeue q) (dequeue q) (queue-empty-p q) --> T (dequeue q) --> NIL ; 空の場合はnilを返す
BASE64
;; 8byte整数を等価なビットリストに変換 ;; ex: 10 = #b00001010 => (0 0 0 0 1 0 1 0) (defun octet-to-bytes (octet) (loop FOR i FROM 7 DOWNTO 0 COLLECT (ldb (byte 1 i) octet))) ;; listがdivisorで割り切れない場合、足りない分だけpadding-valueで埋める (defun padding (list divisor padding-value) (append list (loop REPEAT (abs (nth-value 1 (ceiling (length list) divisor))) COLLECT padding-value))) (defun cdddddr (list) (nthcdr 6 list)) ;; バイト列をBASE64文字列に変換する (let ((table "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/")) (defun octets-to-base64 (octets) (let ((bytes ;; バイト列をビットリストに変換 (loop FOR octet ACROSS octets NCONC (octet-to-bytes octet)))) (coerce (padding ;; bytesから6ビットずつ取り出す (loop FOR (a b c d e f) ON (padding bytes 6 0) BY #'cdddddr COLLECT ;; 変換表を参照して、6ビット値を対応する文字に変換 (aref table (+ (ash a 5) (ash b 4) (ash c 3) (ash d 2) (ash e 1) (ash f 0)))) 4 #\=) ;; 変換後の文字の数が4の倍数でない場合は、足りない分を#\=で埋める 'string))))
