2006-11-05 [長年日記]
■文書の類似度とデータ圧縮と符号化と
単純で全く実用的ではないが、問題をうまく捉えるのに有効な答え、てのもあるなぁ、と思ったので記しておく。
■ 2 つの文(日本語のもの)の間の類似度を算出するアルゴリズムを紹介してください。
http://q.hatena.ne.jp/1162484151
2つの文書を単純に結合して適当なロスレス圧縮なアルゴリズムにかける。より圧縮できた場合は文書の類似度が高い。
ロスレス圧縮の基礎である符号化。
よりたくさん出てくるパターンにより短いデータ長の符号を与えると、全体のデータ長は小さくなる。といのが基本的な考え方。
2つの文書を結合して圧縮した時に符号化によってデータ長を減少できるということは、前後の2つの文書に共通のパターンが多い、ということでもある。
実際にはこの手法は単純すぎて、ある1つの文書がまずあって、それ以外に複数の文書がある場合に先の文書により近いのがどれか? という様なケースでないと使えない。
そうでないケース、例えば4つの文書があってその中でもっとも類似しているペアを捜す、なんていうケースではうまくいかないだろうな。
一応追記
を見つけた。
ところで、あらかじめ文書集合とそれらに対する適切な分類があるならばともかく、2つの文の類似度というのはそれほど明らかな(例えば10人が10人とも同じ判断をするような)ものではないだろう。
(1)私は歯科医で、職場に平日の午後通っています。
(2)私は建築家で、職場に平日の午後通っています。
(3)私は平日の午後、職場から歯科医に通っています。
さて、(2)と(3)のどちらがより(1)に近い?
(1)私は言葉の意味を調べるのによくGoogleを使います。
(2)私は言葉の意味を調べるのによく辞書を使います。
(3)gooの辞書は言葉の意味を調べるのに便利です。
(1)と(2)、(2)と(3)、(3)と(1)、どれが一番類似度が高い?
追記 2006/11/8
回答としては#2は妥当だと思う。
エディットグラフを使う方法は、最短距離を類似度とする以外にエディットグラフ上に引かれた斜線の数を数えるというのもありかなぁ、と考えていた。単純な数では文字列の長さ(n*mの大きさ)に依存するので、その辺は正規化する必要はありそう。
他のアイディアとして、
- 最短経路上の斜線の重みを大きくする
- 対角線上の斜線(n≠mだと対角線状の平行四辺形上の斜線か?)の重みを大きくする
- 2本以上つながった斜線の重みを大きくする
などか。
n-gram で切り出してソートした結果から、エディットグラフの最短距離をとる(この場合はエディットグラフの軸にくるのは文字ではなくて、n文字の文字列に変わる)というのもいけるかなぁ? どうだろう。
上に書いた圧縮処理で類似度を測る方法は、短い「文」では難しいだろう。圧縮のちょっと手前、符号の作成までをおこなって符号表から類似度を考えるというのもありか。
短い符号に長いパターンが結びついていれば類似度が高い、と言えるのではないか?
■病気で摘出した臓器を別の患者に移植するのは10年前には行われている
のニュースの件で、
しかしドミノ移植と呼ばれる、移植によって取り出された臓器を別の患者に移植することは行われています。
Log of ROYGB - 病気で摘出した臓器を移植する
という記事を読んだ。不勉強ゆえ知らなかったので、ざっと"ドミノ移植"で検索すると確かに、1990年代なかばには肝臓のドミノ移植の事例が出てきている。
「病気で摘出した臓器を別の患者に移植」というのは普通の人の感覚に照らすと非常にセンセーショナルだが、一概に禁止事項にすればいいというものでもないらしい。
■via はラテン語で「道」
英語だと "way".