22371


**下記が50％だとすると、**

> 天下  
>  天一

* * *

**下記は類似度何％になるでしょうか？**  
・一致数4 ÷ 全文字数22 × 100 ＝ 22％でしょうか？  
・また、この場合、「天下」から見た「天下一武道会へ出場してみたいけど」も、「天下一武道会へ出場してみたいけど」から見た「天下」の類似度も同じ？

> 天下  
>  天下一武道会へ出場してみたいけど

* * *

その他、どんな「算出方法」や「考え方」があるか知りたいです


CC BY-SA 3.0
2016-02-21T04:21:58.920
22333
2016-02-22T04:33:21.867
7886
question
アルゴリズム
異なる文字数の、文字列類似度の算出方法は？


定番といえるようなアルゴリズムがあるのかどうか、私が検索した限りでは見つけられませんでした。「レーベンシュタイン距離」を用いるなら、想定される最大コストをmc,レーベンシュタイン距離をldとして、

**類似度(%) = (mc-ld)/mc * 100**

とすると、  
**'天下':'天一'->50%  
'天下':'天下一武道会へ出場してみたいけど'->12%  
'天下一武道会へ出場してみたいけど':'天下'->12%  
'天下':'武道会へ出場してみたいけど'->0%  
'天一':'天下一武道会へ出場してみたいけど'->12%**  
なんて結果になります。

レーベンシュタイン距離の計算はネットで見つけたJavaScript版のIterative with full
matrix相当のもの、「想定される最大のコスト」は`mc = Math.max(str1.length,
str2.length)`で計算しています。(どちらもサロゲートペアの文字は考慮されていません。)

どなたかが、定番のアルゴリズムを見つけてこられた場合、単なるお茶濁しとなりますが、参考まで。


CC BY-SA 3.0
2016-02-21T05:57:00.310
22338
2016-02-21T05:57:00.310
13972
22333
answer


クラスタリングを利用するという手もあります。  
この場合、学習データにより、類似度が異なることになります。  
<http://qiita.com/shima_x/items/196e8d823412e45680e9>

なんらかのジャンルにより異なった結果が欲しい場合は、こちらが適しているかと思いますが、単純にどの程度編集すると、その文字列になるのかという解が欲しいのであれば、すでに提示されている方法が適していると思います。


CC BY-SA 3.0
2016-02-22T04:33:21.867
22371
2016-02-22T04:33:21.867
4956
22333
answer