ランキングで似た配列を探す。似ている確率も求めたい

Question

「要素数が固定の配列」「あるいは先頭から要素を5つぐらいを切り取った配列」で、
「自分と似た配列」を「似ている確率順」で表示させたいのですが、どうすればいいでしょうか？

■似ている
・内容が一致
・順番も一致？
・一致している数？
・先頭からの要素数が一致している方が優先？

特にこうしたい、という強い希望があるわけではないのですが、「似ている配列」を求めたいとき、どういう方法が考えられるのか知りたく、質問しました

To_aru_User · Accepted Answer

【実装例】
http://ideone.com/b1T4dS

<?php
 
$arrs = array(
    'arr1' => array(1, 2, 3, 4, 5),  
    'arr2' => array(101, 102, 103, 104, 105),  
    'arr3' => array(3, 4, 2, 5, 1),
    'arr4' => array(5, 3, 4, 2, 1),
);

foreach ($arrs as $base_name => $base_arr) {
    $copies = $arrs;
    unset($copies[$base_name]);
    echo "【{$base_name}の他に対する類似度】
";
    $base_str = implode("\0", $base_arr);
    $results = array();
    foreach ($copies as $target_name => $target_arr) {
        $target_str = implode("\0", $target_arr);
        similar_text($base_str, $target_str, $percent);
        $results[$target_name] = $percent;
    }
    arsort($results);
    foreach ($results as $target_name => $percent) {
        printf("%s -> %01.2f%%
", $target_name, $percent);
    }
    echo "
";
}

To_aru_User · Answer

implode関数とsimilar_text関数を組み合わせれば比較的ラクに書けそうな気がします。

implode()
http://php.net/manual/ja/function.implode.php

これを使って比較する配列の要素を一度全て結合し、文字列としてください。
結合文字はカンマだと中身の文字列と被る可能性があるので、NULL文字辺りを入れとけばいいんじゃないでしょうか。

similar_text()
http://php.net/manual/ja/function.similar-text.php

類似性を3番目の参照渡しにした引数で受け取ってください。
このアルゴリズムは渡す順序によって計算結果に差が出るみたいです。
そんなに気にする必要もなさそうですが。

pixie-grasper · Answer

「似ている」の定義にもよりますが・・・

グラフにした時の形が似ている、つまり、例えば
{1,2,3,4,5}と{101,102,103,104,105}が「完璧に似ている」というのであれば、引き算した結果の配列{100,100,100,100,100}の分散を求めて、0に近い順に出力すれば良いでしょう。

数字を色に置き換えて2つ並べた時に似ているように見えるのを似ているというのであれば、
例えばレーベンシュタイン距離(編集距離)が短い順に出力する、等の方法が考えられます。
http://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2

配列の要素が一致しているが、同順である必要がないというのであれば、一旦その中身をソートしてからレーベンシュタイン距離を測る、等の工夫が考えられます。

ランキングで似た配列を探す。似ている確率も求めたい

【実装例】

implode関数とsimilar_text関数を組み合わせれば比較的ラクに書けそうな気がします。

「似ている」の定義にもよりますが・・・

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング