■HTML parser
これ何？
HTMLのファイルからHTMLタグツリーを作ります。それだけ。
特徴として
1.1-pass
2.ルールベース
3.テキストもノードにする
4.強引にツリーにする
などがあります。ただし、属性は無視します。
応用としては、
1.リンク抽出
2.タグ整形
などなど。
何やってるの？
全体の流れは以下の通り。
1.ファイルの読み込み
2.ノードの分割
3.深さの決定
4.各ノードの設定
1.ファイルの読み込み
まず、最初にHTMLファイルをstring(C++)で読み込みます。javaだとstring bufferかな？
<html><body>test</body></html>
2.ノードの分割
そしてそれをタグに分割します。C++ではSTLのvector<string>にpush_backします。javaだとArrayListにaddかも。
<html>
<body>
test
</body>
</html>
このとき、テキストもノードとして扱います。
3.深さの決定
一番重要な部分はここです。各ノードがどの深さにあるべきかを決めます。
深さを決めるのには、基本的にスタックにpush、popをします。基本的には、
・開きタグが出現→スタックにpush
・テキストが出現→何もしない
・閉じタグが出現→スタックからpop
という動作を行います。
上の例の場合です。
スタックの状態
<html> → push
<html>
-------- → <html>の深さは1
<body> → push
<body>
<html>
---------- → <body>の深さは2
test → 何もしない
<body>
<html>
---------- → スタックには積まない。深さはそのまま2。
</body> → pop
<html>
---------- →</body>の深さは2。それから取り除く。
</html> → pop
---------- →</html>の深さは1。それから取り除く。
となり、最終的に
<html>：1
<body>：2
test ：2
</body>：2
</html>：1
となる。基本的にはこれだけ。
しかし、世の中のHTMLは上のように正しい(valid)ものばかりではありません。例えば、次のようなものがあります。
<html>
<body>
test
</html>
この例では<body>の閉じタグである</body>が省略されています。そこで、このような場合に対応するために採用しているのが、以下のようなルールです。
<body>, </html>, 2
これは、<body>タグがスタックの先頭のとき、</html>が出現した場合には、スタックから2つ分popするという意味です。
このようなルールにより、すべてのノードの深さを決定します。
4.各ノードの設定
深さが決まれば、各ノードの子ノードと親ノードを求めればツリー構造が出来上がります。子ノードを決定するには、あるノードの深さより深いノードを探します。また、親ノードを決定するには、あるノードの深さより一つ浅いノードを探してきます。
このようにしてHTMLタグツリーを作っています。
ダウンロード
フリーです。ソースのみなので各自makeしてください。C++です。STL使っているので、libstdc++が必要かもしれないです。
開発環境
とりあえず、動作確認はdebain woodyで、gcc 3.3.5で行いました。他にもある程度行っているので、体外動くはずです。
カウンター
total -
昨日 -
今日 -
最終更新：2006年10月18日 23:02
