similar_text 関数を見つけて、いじっていましたが、パーセンテージの出力にはいつも驚かされます。以下の例を参照してください。
php: similar_text()Docsで言及されているように使用されるアルゴリズムに関する情報を見つけようとしました:
<?php
$p = 0;
similar_text('aaaaaaaaaa', 'aaaaa', $p);
echo $p . "<hr>";
//66.666666666667
//Since 5 out of 10 chars match, I would expect a 50% match
similar_text('aaaaaaaaaaaaaaaaaaaa', 'aaaaa', $p);
echo $p . "<hr>";
//40
//5 out of 20 > not 25% ?
similar_text('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', 'aaaaa', $p);
echo $p . "<hr>";
//9.5238095238095
//5 out of 100 > not 5% ?
//Example from PHP.net
//Why is turning the strings around changing the result?
similar_text('PHP IS GREAT', 'WITH MYSQL', $p);
echo $p . "<hr>"; //27.272727272727
similar_text('WITH MYSQL', 'PHP IS GREAT', $p);
echo $p . "<hr>"; //18.181818181818
?>
これが実際にどのように機能するかを誰か説明できますか?
アップデート：
コメントのおかげで、パーセンテージは実際には同様の文字の数 * 200 / length1 + length 2 を使用して計算されることがわかりました
Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len);
これで、パーセンテージが予想よりも高い理由が説明できます。95 中 5 の文字列を使用すると、10 になるので使用できます。
similar_text('aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', 'aaaaa', $p);
echo $p . "<hr>";
//10
//5 out of 95 = 5 * 200 / (5 + 95) = 10
しかし、PHP が文字列の向きを変えたときに異なる結果を返す理由はまだわかりません。dfsq が提供する JS コードはこれを行いません。PHP のソース コードを見ると、次の行の違いしかわかりませんが、私は AC プログラマーではありません。違いが何であるかについての洞察をいただければ幸いです。
JS で:
for (l = 0;(p + l < firstLength) && (q + l < secondLength) && (first.charAt(p + l) === second.charAt(q + l)); l++);
PHP の場合: (php_similar_str 関数)
for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);
ソース：
/* {{{ proto int similar_text(string str1, string str2 [, float percent])
Calculates the similarity between two strings */
PHP_FUNCTION(similar_text)
{
char *t1, *t2;
zval **percent = NULL;
int ac = ZEND_NUM_ARGS();
int sim;
int t1_len, t2_len;
if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "ss|Z", &t1, &t1_len, &t2, &t2_len, &percent) == FAILURE) {
return;
}
if (ac > 2) {
convert_to_double_ex(percent);
}
if (t1_len + t2_len == 0) {
if (ac > 2) {
Z_DVAL_PP(percent) = 0;
}
RETURN_LONG(0);
}
sim = php_similar_char(t1, t1_len, t2, t2_len);
if (ac > 2) {
Z_DVAL_PP(percent) = sim * 200.0 / (t1_len + t2_len);
}
RETURN_LONG(sim);
}
/* }}} */
/* {{{ php_similar_str
*/
static void php_similar_str(const char *txt1, int len1, const char *txt2, int len2, int *pos1, int *pos2, int *max)
{
char *p, *q;
char *end1 = (char *) txt1 + len1;
char *end2 = (char *) txt2 + len2;
int l;
*max = 0;
for (p = (char *) txt1; p < end1; p++) {
for (q = (char *) txt2; q < end2; q++) {
for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++);
if (l > *max) {
*max = l;
*pos1 = p - txt1;
*pos2 = q - txt2;
}
}
}
}
/* }}} */
/* {{{ php_similar_char
*/
static int php_similar_char(const char *txt1, int len1, const char *txt2, int len2)
{
int sum;
int pos1, pos2, max;
php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max);
if ((sum = max)) {
if (pos1 && pos2) {
sum += php_similar_char(txt1, pos1,
txt2, pos2);
}
if ((pos1 + max < len1) && (pos2 + max < len2)) {
sum += php_similar_char(txt1 + pos1 + max, len1 - pos1 - max,
txt2 + pos2 + max, len2 - pos2 - max);
}
}
return sum;
}
/* }}} */
Javascript のソース: javascript と同様のテキスト ポート