imHo RSSフィード

2011-02-24

2.2.3 正規化

Normalization (equivalence classing of terms)

  • まったく同じじゃなくてもマッチして欲しい
    • USAとU.S.A.とか
  • トークンの正規化(Token normalization)
    • もっとも標準的な方法は等価クラス(equivalence classes)で、集合の1つの名前にする
    • 例えば、トークンanti-discriminatoryとantidiscriinatoryの両方を語句antidiscriminatoryにマップする場合、文書テキストとクエリの両方に行い、サーチすればどちらも復元できる
  • ハイフンなどの文字を削除するだけのマッピングルールは、ルールを簡単に書けるのは利点だけど、文字を足したりするのが簡単じゃない
    • 手動で類似語リストを作ると、carとautomobileというように拡張できる(9章)
  • 2種類の方法:
    1. 一般的な方法は、正規化していないトークンをインデクスし、複数ボキャブラリエントリのクエリ展開リストで正しいクエリ語句を考慮する
    2. インデクスの構築時に展開をする。文書がautomobileを含んでいたら、carとインデクスする(また通常、逆もしかり)、など
  • 両方とも等価クラスに比べると効率的ではない、がより柔軟
アクセントとdiacritics

Accents and diacritics.

  • ウムラウトとか
  • 意味が異なる単語もあるが、入力めんどいので一緒に扱う
大文字小文字

Capitalization/case-folding.

  • 一般的な戦略は、すべて小文字にする
  • 機械学習で頑張る手もあるが、どうせユーザは小文字でクエリを入力するので、あまり役に立たない
英語でのその他の問題

Other issues in English.

  • ne'er = never
  • 3/12/91 = Mar. 12 1991 (U.S.), or 3 Dec 1991 (Europe)
他の言語

Other languages.

  • 英語はWWWの主流で、ウェブページの60%が英語(2007)だが、今後英語以外も伸びるだろう
  • フランス語:女性形男性形、複数単数
  • ドイツ語:ウムラウト
  • 日本語:複数の表記法で、単語を分けない
  • 日本語は難しい表記法としてよく知られている

2011-02-16

C言語を使えるようにするには

  1. 本のように、gccで出力したアセンブリソースをnasmでアセンブルできるようにコンバートする
  2. gccでオブジェクトファイルを吐き出して、objdumpで情報を取り出す

取り出しても、まだリンク作業が残ってる。素直に本の内容に従っておくか、またはC言語をあきらめるか。

ブートローダではcソースをコンパイルしてリンクしたバイナリファイルbootpack.hrbを0x00280000にコピーして、最終的に0x0028001bを呼び出すんだけど、全然意味がわかってない。0x1bは.hrbファイルのプログラムエリアの開始位置だとしても、0x00280000はなんだろう…。実行プログラムはリロケータブルになってるのかな?

またブートローダでメモリの0x8000以降に読み込んだものを0x00100000にコピーしてるのも謎。

IPLから読み込まれるブートプログラムをnasmで

3章でIPLから読み込まれるブートプログラムをnasmでアセンブルするように変更する。というかtools/nask - hrb-wikiに書いてあった。

  • [INSTRSET "i486p"]の宣言を省く
  • RESB x はnasmでは「0クリアするよ!」というワーニングが出るので、TIMES x DB 0 に変更
  • ALIGNB x も同様に出るので、ALIGNB x, DB 0 に変更

edimg.exeでファイルを連結すると、たぶんフロッピーディスクでのファイル配置でFATが0x2600に、ファイル本体が0x4200に配置されるんだろうけど、とりあえず無視して単にcatで連結

$ cat ipl.bin boot.bin > fdimage0.bin

してORG 0x8200にして、iplからのジャンプ先を0x8200にしてもうまく動いた。

本では3章の終わりにC言語を導入するんだけど、それどうしようかな…。

2011-02-15

自作OS入門をnasmで

自作OS入門を読み返してみてるけど、これ相当すごい本じゃないか?タイマ割り込みやタスクスイッチあたりが熱い。

でいろいろツールを揃えてくれているのはいいんだけど、それらのツールのことはよくわからないので、ブラックボックスをできるだけ少なくしたい。ということで、アセンブラをnask.exeじゃなくてnasmにしてやってみる。x86アセンブラ全然知らんけど。

nasmは403 Forbiddenからダウンロード。2日目のhelloos04での510バイト目までを0で埋めるための「resb 0x7dfe-$」が、nasmではエラーになる。nasmでは$と$$を使って、「resb 0x01fe-($-$$)」と書くようです(WeBlog of Sky color OS自作入門-Hello World...)。あとジャンプ命令JMPにshortとつけないと EB xx じゃなくて E9 xx xx という、オフセットが2バイトの命令になってしまう。勝手に選んでくれればいいのに。

; hello-os
; TAB=4

	ORG	0x7c00		; このプログラムがどこに読み込まれるのか

; 以下は標準的なFAT12フォーマットフロッピーディスクのための記述

	JMP SHORT	entry
	DB	0x90
	DB	"HELLOIPL"	; ブートセクタの名前を自由に書いてよい(8バイト)
	DW	512		; 1セクタの大きさ(512にしなければいけない)
	DB	1		; クラスタの大きさ(1セクタにしなければいけない)
	DW	1		; FATがどこから始まるか(普通は1セクタ目からにする)
	DB	2		; FATの個数(2にしなければいけない)
	DW	224		; ルートディレクトリ領域の大きさ(普通は224エントリにする)
	DW	2880		; このドライブの大きさ(2880セクタにしなければいけない)
	DB	0xf0		; メディアのタイプ(0xf0にしなければいけない)
	DW	9		; FAT領域の長さ(9セクタにしなければいけない)
	DW	18		; 1トラックにいくつのセクタがあるか(18にしなければいけない)
	DW	2		; ヘッドの数(2にしなければいけない)
	DD	0		; パーティションを使ってないのでここは必ず0
	DD	2880		; このドライブ大きさをもう一度書く
	DB	0,0,0x29	; よくわからないけどこの値にしておくといいらしい
	DD	0xffffffff	; たぶんボリュームシリアル番号
	DB	"HELLO-OS   "	; ディスクの名前(11バイト)
	DB	"FAT12   "	; フォーマットの名前(8バイト)
	RESB	18		; とりあえず18バイトあけておく

; プログラム本体

entry:
	MOV	AX,0		; レジスタ初期化
	MOV	SS,AX
	MOV	SP,0x7c00
	MOV	DS,AX
	MOV	ES,AX

	MOV	SI,msg
putloop:
	MOV	AL,[SI]
	ADD	SI,1		; SIに1を足す
	CMP	AL,0
	JE SHORT	fin
	MOV	AH,0x0e		; 一文字表示ファンクション
	MOV	BX,15		; カラーコード
	INT	0x10		; ビデオBIOS呼び出し
	JMP	putloop
fin:
	HLT			; 何かあるまでCPUを停止させる
	JMP SHORT	fin	; 無限ループ

msg:
	DB	0x0a, 0x0a	; 改行を2つ
	DB	"hello, world"
	DB	0x0a		; 改行
	DB	0

	RESB	0x01fe-($-$$)	; 510バイト目までを0x00で埋める命令

	DB	0x55, 0xaa	; 最後にマーカーが必要
  • あとは、QEMUの実行に必要なbios.binとvgabios.binがなんなのかわからない…。

2011-02-12

「OS自作入門」入門

OS自作入門を改めてチャレンジ。この本の内容はいいんだけど、ビルドにいろんな独自ツールを使ってて、そのソースが公開されてない?のでどういうことが行われるのかわかりづらいところが難点。

■1章

1.4Mバイトのバイナリファイルを作成して、フロッピーディスクのイメージとする。最初のセクタから512バイト分ブートローダとして0x7c00に読み込まれて実行が始まる。AH=0x0eを入れてINT 0x10を呼び出して文字を表示。naskという自作アセンブラが使われているが、ソースがない。出力ファイル名を.imgにするとバイナリ生成?

■2章

プログラムをアセンブリ言語で書き直し。ブートセクタ512バイトだけnaskでアセンブルして、あとはedimgで生成する。

..\z_tools\edimg.exe   imgin:../z_tools/fdimg0at.tek   wbinimg src:ipl.bin len:512 from:0 to:0   imgout:helloos.img
  • fdimg0at.tek: 構造は謎
0000: 89 FF FF FF 01 00 00 00  4F 53 41 53 4B 43 4D 50   ・    OSASKCMP 
0010: 02 20 01 21 FF 93 1E 53  DB 9C E8 6D 3A FB 31 6A      !・Sロ懆m:・j 
0020: A1 2F DF 49 63 FB E8 23  A9 02 73 52 43 87 8A 9E   。/゚Ic輭#ゥ sRC?・
0030: 32 3A 30 8E 8E 74 78 9F  C2 FB 00                   :0試tx淞・

■3章

ブートローダ部だけじゃなくて以降をメモリに読み込み。AH=0x02にしてINT 0x13でディスクから読み込み。ブートセクタは0x7c00〜0x7dffに読み込んだのに、続きは0x8200から?セクタは1オリジン?

で、ブートローダによって読み込まれるプログラムの作成。それをedimgでつなげる

$(EDIMG)   imgin:../z_tools/fdimg0at.tek wbinimg src:ipl.bin len:512 from:0 to:0 copy from:haribote.sys to:@: imgout:haribote.img

んだけど、なぜファイル名が0x2600に、ファイルの中身が0x4200に入るのかが不明。バイナリファイルの作り方によっては、別にファイル名とかなくて、セクタ2からプログラムを置いてもいいのかな?

で0x8000+0x4200=0xc200にプログラムがロードされるので、ブートローダからそこにジャンプするようにする。別にファイル名情報とかは見てない。

AH=0x00にしてINT 0x10でビデオモード切替。

で、C言語導入。gcc(を改変したもの)で.gasというgcc用のアセンブリソースにして、それをgas2naskでnask用に変換して、naskでアセンブル。ここで出てくる.objファイルは以前の単なるバイナリと違って.txtとか.bssとか見えるんだけど、.nasソースに

[FORMAT "WCOFF"]

と書かれているからっぽい。obj2bimで.bim(バイナリイメージ)ファイルに変換、bim2hrbで.hrbに変換。.hrbは単なるバイナリファイルで、アセンブリで作ったバイナリと単に連結するだけ。C側のエントリがHariMainになるのはharibote.rulで指定されているからとか:

format:
	/* このセクションでリンクの方針を記述 */
	code(align:1, logic:0x24,      file:0x24);
	data(align:4, logic:stack_end, file:code_end);

file:
	/* このセクションでコマンドラインに書ききれなかった
		.ojbファイル、.libファイルを記載 */
	/* なお、このセクションはフルパスで書いてもよい。 */
	/* 例:  c:/osask/gg00libc.lib;  */
	../z_tools/haribote/harilibc.lib;
	../z_tools/haribote/golibc.lib;

label:
	/* 必ずリンクしなければいけないラベルを指定 */
	/* エントリポイントを指定すればいいと思ってください */
	_HariStartup;

	/* 上記3セクションの順序は入れ替えてはいけません! */

harilibc.libとかgolibc.libはどのように作ったか不明。WCOFFとは別フォーマットぽい?harilibc.libは「 /」で始まってるけど、golibc.libは「〜OSASKCMP」となっている。

次に低レベルなことをやらせるために、Cから.nasのアセンブラのルーチンを呼び出せるようにする。.nasから出した.objと.cから出した.objをobj2bimでリンクして、ラベルを解決してる?

とりあえず3章まで。

  • C言語使えるのは便利だけど、その部分も自分でやらんとわからんなぁ
  • USBメモリに入れてブートさせてみたいけど、やりかたわからず…

2011-02-01

2.2.2 一般語(停止語)の削除

Dropping common terms: stop words

  • 文書の選択に役立たない非常に一般的な単語がボキャブラリ全体から抽出される
    • これらの単語は停止語(stop words)と呼ばれる
    • 停止語を決定する一般的な戦略は収集頻度(collection frequency)の類(文書コレクション中に各語句が合計何回登場するか)
    • よく出る単語から手作業で取り出し、停止リスト(stop list)とする、インデクスするときには捨てられる
    • 停止リストの例:a an and are as at be by for from has he in is it its of on that the to was were will with
    • 停止リストはシステムが格納すべき位置の数を非常に減らすことができる
    • 弊害も:To be or not to be, Let it be, I don't want to be, ...
  • IRシステムの一般的なトレンドは、極めて多くのストップリスト(200-300語句)から始まって非常に少ないストップリスト(7-12語句)からストップリストなしになっている
    • ウェブサーチエンジンは一般的にストップリストを使わない
    • 最近のIRシステムは言語の統計を利用して共通単語をよりよい方法で扱う
    • 7.1.5でインパクトソートされたインデクスでどのようにして位置リストのスキャンを早めに打ち切り、共通単語でもそんなに処理コストがかからない方法を示す