ナード戦隊データマン

機械学習, 自然言語処理, データサイエンスについてのブログ

htmlの構造的な類似性を評価する

htmlの構造的類似性とは、2つのHTMLに対して、コンテンツを除いたHTMLツリーがどの程度似ているかを表す指標です。

単純なアルゴリズム

sdiff等のツールを使えば、2つの文書から相違する部分を抜き出すことができます。Automatic Acquisition of Chinese–English Parallel Corpus from the Web1 の中では、以下の計算方法で構造的スコアを計算しています。

S = sdiffの相違行数 / 合計行数

このスコアの場合、スコアが低いほど類似性が高いということになります。

何に使えるのか

構造スコアを使うことにより、相互翻訳されたWebページを発見することができます。例えば、

の2つのページの構造が似ていた場合、相互翻訳されている可能性が高いと判断することができます。これにより、この2つのページからパラレルコーパスを作成することができます。一般に、クローリングの中で構造スコアのような指標をもちいて相互翻訳ページを見つければ、Webから巨大なパラレルコーパスを作成できます。

コード

以下のpythonコードではsdiffは使っていませんが、difflibというライブラリによって構造スコアを計算しています。

import re
from difflib import SequenceMatcher


def extract(data):
    regex = re.compile(r"<.+?>")
    data_fix = re.findall(regex, data)
    data_fix1 = [
        re.sub(r'<\s*([a-z][a-z0-9]*)\s.*?(/?>)', r"<\1\2", x)
        for x in data_fix
    ]
    return '\n'.join(data_fix), '\n'.join(data_fix1)


def html_similarity(data1, data2, alpha=0.3):
    x1, x2 = extract(data1)
    y1, y2 = extract(data2)
    seq1 = SequenceMatcher(None, x1, y1)
    seq2 = SequenceMatcher(None, x2, y2)
    result = seq1.ratio() * alpha + seq2.ratio() * (1 - alpha)
    return result


if __name__ == "__main__":
    import sys
    with open(sys.argv[1]) as f:
        data1 = f.read()

    with open(sys.argv[2]) as f:
        data2 = f.read()

    print(html_similarity(data1, data2))

実行例

[コマンド]

python3 hsim.py doc1.html doc2.html

[出力]

0.849068608469161

補足

パラレルコーパスをWebのクローリングによって作成する場合、構造スコアの他に「ファイル長」を使うことができます。2つのファイルのファイル長の比率がある範囲に収まるかどうかを判定することで、相互翻訳ページの判定に使えます。この場合、ファイル長特徴量と構造スコア特徴量の2つをKNNに学習させれば、より良い候補選択方法をモデリングすることが可能です。ただし、その場合は教師データが必要になります。

また、相互翻訳されたページのペアを見つけても、そこからさらに文のペアを抽出しなければなりません。これは、bilingual sentence alignmentと呼ばれるタスク(?)です。この場合、HTMLの構造が利用できるような方法2を使うと良いかもしれません。

参考