Similarity and Edit distance

ページのリロード後も設定を持ち越す、という動作を実装する。先に書いたとおり、難しいのはリロード前に wasavi を起動させ設定を追加した textarea が、リロード後に必ずしも同じノードパスとは限らない、という点だ。これは、ノードパスを文字列化したもののレーベンシュタイン距離をとり、適当な閾値以内かどうか、で判断すれば良いと思う。

一方、ページのリロードではなくフォームの送信のように URL が変化する場合もある。また、URL のパスは同一でも、クエリ文字列やフラグメントが微妙に変化する場合もある。つまり URL についても類似性を見る必要があるかもしれない。例えば example.com/?foo=bar 上の textarea に対する設定は、example.com/?foo=baz をブラウズしたときも同様に再現されてほしい。ただしこれは微妙かもしれない。クエリ文字列やフラグメントが 1 文字変化しただけでまったく異なる内容を提供される場合もないとは言えないからだ。しかし、類似性を見て得る情報はしょせんエディタの設定だ。間違えたところで、今のところはそんなに危険というわけでもないので、まあいいだろう。

URL については構成部品ごとに分けて考える必要があると思う。パス部分は曖昧な類似性は関係ない。同じか否かで見る。一方クエリ文字列は難しい。& で連結される key=value の部分は順不同だからだ。?foo=1&bar=2&baz=3 と ?baz=3&foo=1&bar=2 は実質同じクエリ文字列だが、レーベンシュタイン距離は結構な値になる。そうすると、クエリ文字列の類似性はレーベンシュタイン距離ではなく、trigram による similarity measure を見たほうがいいかもしれない。

 * * *

そんな感じで組んでみた。覚えておく URL は直近の 30 件、類似性の閾値は 0.8 とした。

Leave a Reply

Your email address will not be published. Required fields are marked *